Efficient core computation in data exchange

ABSTRACT

Data exchange deals with inserting data from one database into another database having a different schema. Fagin et al. [2005] have shown that among the universal solutions of a solvable data exchange problem, there exists—up to isomorphism—a unique most compact one, “the core”, and have convincingly argued that this core should be the database to be materialized. They stated as an important open problem whether the core can be computed in polynomial time in the general setting where the mapping between the source and target schemas is given by source-to-target constraints that are arbitrary tuple generating dependencies (tgds) and target constraints consisting of equality generating dependencies (egds) and a weakly acyclic set of tgds. In this article, we solve this problem by developing new methods for efficiently computing the core of a universal solution. This positive result shows that data exchange based on cores is feasible and applicable in a very general setting. In addition to our main result, we use the method of hypertree decompositions to derive new algorithms and upper bounds for query containment checking and computing cores of arbitrary database instances. We also show that computing the core of a data exchange problem is fixed-parameter intractable with respect to a number of relevant parameters, and that computing cores is NP-complete if the rule bodies of target tgds are augmented by a special predicate that distinguishes a null value from a constant data 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: Adler, I. 2004. Marshals, monotone marshals, and hypertree-width. J. Graph Theory 47, 4, 275--296.
• 3: Isolde Adler , Georg Gottlob , Martin Grohe, Hypertree width and related hypergraph invariants, European Journal of Combinatorics, v.28 n.8, p.2167-2181, November, 2007 [doi>10.1016/j.ejc.2007.04.013]
• 4: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 5: 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]
• 6: Aho, A., Sagiv, J., and Ullman, J. 1979c. Equivalence of relational expressions. SIAM J. Comput. 8, 2, 218--246.
• 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: Stefano Ceri , Georg Gottlob , Letizia Tanca, Logic programming and databases, Springer-Verlag New York, Inc., New York, NY, 1990
• 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: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 12: Downey, R., Fellows, M., and Tailor, U. 1996. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Combinatorics, Complexity, and Logic—Proceedings DMTCS'96, D. S. Bridges, C. S. Calude, J. Gibbons, S. Reeves, and I. H. Witten, Eds.
• 13: Downey, R. G., and Fellows, M. R. 1999. Parameterized Complexity. Springer-Verlag, New York.
• 14: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 15: Fagin, R. 2005. Extending the core greedy algorithm to allow target TGDS with singleton left-hand sides. Unpublished manuscript.
• 16: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 17: 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]
• 18: 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]
• 19: Georg Gottlob, Computing cores for data exchange: new algorithms and practical solutions, 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.1065187]
• 20: Georg Gottlob , Christian G. Fermüller, Removing redundancy from a clause, Artificial Intelligence, v.61 n.2, p.263-289, June 1993 [doi>10.1016/0004-3702(93)90069-N]
• 21: 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]
• 22: 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]
• 23: Georg Gottlob , Nicola Leone , Francesco Scarcello, 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]
• 24: Gottlob, G., Leone, N., and Scarcello, F. 2002. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. 64, 3, 579--627.
• 25: 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]
• 26: Georg Gottlob , Alan Nash, Data exchange: computing cores in polynomial time, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142358]
• 27: 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]
• 28: Martin Grohe, Parameterized complexity for the database theorist, ACM SIGMOD Record, v.31 n.4, December 2002 [doi>10.1145/637411.637428]
• 29: 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]
• 30: Pavol Hell , Jaroslav Nešetřil, The core of a graph, Discrete Mathematics, v.109 n.1-3, p.117-126, Nov. 12, 1992 [doi>10.1016/0012-365X(92)90282-K]
• 31: 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]
• 32: 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]
• 33: 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]
• 34: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 35: 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]
• 36: Bernard M. E. Moret , Henry D. Shapiro, Algorithms from P to NP (vol. 1): design and efficiency, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 37: 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]
• 38: Pichler, R., and Savenkov, V. 2008. Implementing core computation for data exchange. Tech. Rep. DBAI-TR-2008-01, Institut für Informationssysteme, Technische Universität Wien, A-1040 Vienna, Austria.
• 39: Xiaolei Qian, Query Folding, Proceedings of the Twelfth International Conference on Data Engineering, p.48-55, February 26-March 01, 1996
• 40: Robertson, N., and Seymour, P. 1986. Graph minors II: Algorithmic aspects of tree-width. J. Algor. 7, 309--322.
• 41: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.12 Interoperability
            Subjects: Data mapping

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Relational databases; Rule-based databases
      H.2.5 Heterogeneous Databases

General Terms:
Algorithms, Theory

Keywords:
Chase, complexity, conjunctive queries, constraints, core, data exchange, data integration, dependencies, query evaluation, tractability, universal solutions