Computing cores for data exchange: new algorithms and practical solutions

ABSTRACT

Data Exchange is the problem of inserting data structured under a source schema into a target schema of different structure (possibly with integrity constraints), while reflecting the source data as accurately as possible. We study computational issues related to data exchange in the setting of Fagin, Kolaitis, and Popa(PODS'03). We use the technique of hypertree decompositions to derive improved algorithms for computing the core of a relational instance with labeled nulls, a problem we show to be fixed-parameter intractable with respect to the block size of the input instances. We show that computing the core of a data exchange problem is tractable for two large and useful classes of target constraints. The first class includes functional dependencies and weakly acyclic inclusion dependencies. The second class consists of full tuple generating dependencies and arbitrary equation generating dependencies. Finally, we show that computing cores is NP-hard in presence of a system-predicate NULL(x), which is true iff x is a null value.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 3: A. Aho, J. Sagiv, and J. Ullman. Equivalence of Relational Expressions. SIAM J. Comput. 8:2, 1979.
• 4: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 5: Marcelo Arenas , Pablo Barceló , Ronald Fagin , Leonid Libkin, Locally consistent transformations and query answering in data exchange, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055592]
• 6: Paolo Atzeni , Edward P. F. Chan, Independent database schemes under functional and inclusion dependencies, Acta Informatica, v.28 n.9, p.777-799, Nov. 1991
• 7: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 8: M. A. Casanova, R. Fagin, and C. H. Papadimitriou. Inclusion Dependencies and Their Interaction with Functional Dependencies. JCSS 28:1, 1984.
• 9: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 10: Chandra Chekuri , Anand Rajaraman, Conjunctive query containment revisited, Theoretical Computer Science, v.239 n.2, p.211-229, May 28, 2000 [doi>10.1016/S0304-3975(99)00220-0]
• 11: R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, 1999.
• 12: R. G. Downey and M. R. Fellows and U. Tailor. The parameterized Complexity of Relational Database Queries and an Improved Characterization of W{1}. In D. S. Bridges et al., editors, Combinatorics, Complexity, and Logic -- Proc. DMTCS'96.
• 13: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 14: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.90-101, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773163]
• 15: Jörg Flum , Markus Frick , Martin Grohe, Query evaluation via tree-decompositions, Journal of the ACM (JACM), v.49 n.6, p.716-752, November 2002 [doi>10.1145/602220.602222]
• 16: G. Gottlob. Computing Cores for Data Exchange: New Algorithms and Practical Solutions. Extended version of the present paper. Currently available at: www.dbai.tuwien.ac.at/staff/gottlob/extcore.pdf
• 17: G. Gottlob , A. Leitsch, On the efficiency of subsumption algorithms, Journal of the ACM (JACM), v.32 n.2, p.280-295, April 1985 [doi>10.1145/3149.214118]
• 18: G. Gottlob, N. Leone, and F. Scarcello. Hypertree Decompositions and Tractable queries. Journal of Computer and System Sciences 64:3, pp. 579--627, 2002.
• 19: The complexity of acyclic conjunctive queries, Journal of the ACM (JACM), v.48 n.3, p.431-498, May 2001 [doi>10.1145/382780.382783]
• 20: Georg Gottlob , Nicola Leone , Francesco Scarcello, Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width, Journal of Computer and System Sciences, v.66 n.4, p.775-808, 1 June 2003 [doi>10.1016/S0022-0000(03)00030-8]
• 21: A comparison of structural CSP decomposition methods, Artificial Intelligence, v.124 n.2, p.243-282, Dec. 2000 [doi>10.1016/S0004-3702(00)00078-3]
• 22: Georg Gottlob , Reinhard Pichler, Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width, SIAM Journal on Computing, v.33 n.2, p.351-378, 2004 [doi>10.1137/S0097539701396807]
• 23: Claudio Gutierrez , Carlos Hurtado , Alberto O. Mendelzon, Foundations of semantic web databases, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055573]
• 24: Martin Grohe, Parameterized complexity for the database theorist, ACM SIGMOD Record, v.31 n.4, December 2002 [doi>10.1145/637411.637428]
• 25: Tomasz Imielinski, Abstraction in query processing, Journal of the ACM (JACM), v.38 n.3, p.533-557, July 1991 [doi>10.1145/116825.116832]
• 26: Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065176]
• 27: Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Journal of Computer and System Sciences, v.61 n.2, p.302-332, Oct. 2000 [doi>10.1006/jcss.2000.1713]
• 28: M. Levene, G. Loizou. How to Prevent Interaction of Functional and Inclusion Dependencies. Information Processing Letters 71:3--4, pp. 115--125, 1999.
• 29: Mark Levene , George Loizou, Guaranteeing no interaction between functional dependencies and tree-like inclusion dependencies, Theoretical Computer Science, v.254 n.1-2, p.683-690, March 6, 2001 [doi>10.1016/S0304-3975(00)00394-7]
• 30: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 31: Heikki Mannila , Kari-Jouko Räihä, The design of relational databases, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 32: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 33: Renée J. Miller , Laura M. Haas , Mauricio A. Hernández, Schema Mapping as Query Discovery, Proceedings of the 26th International Conference on Very Large Data Bases, p.77-88, September 10-14, 2000
• 34: L. Popa, Y. Velegrakis, R. Miller, M. Hernández, and R. Fagin. Translating Web Data. VLDB 2002.
• 35: Christos H. Papadimitriou , Mihalis Yannakakis, On the complexity of database queries, Journal of Computer and System Sciences, v.58 n.3, p.407-427, June 1999 [doi>10.1006/jcss.1999.1626]
• 36: Xiaolei Qian, Query Folding, Proceedings of the Twelfth International Conference on Data Engineering, p.48-55, February 26-March 01, 1996
• 37: N. Robertson and P. D. Seymour. Graph Minors II. Algorithmic Aspects of Tree-Width. J. Algorithms, 7:309--322, 1986.
• 38: Francesco Scarcello , Gianluigi Greco , Nicola Leone, Weighted hypertree decompositions and optimal query plans, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055587]
• 39: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 40: M. Yannakakis. Algorithms for Acyclic Database Schemes. VLDB 1981, pp. 82--94.