{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:22Z","timestamp":1760202562248,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,5,1]],"date-time":"2008-05-01T00:00:00Z","timestamp":1209600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/E010865\/1"],"award-info":[{"award-number":["EP\/E010865\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,5]]},"abstract":"<jats:p>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\u2014up to isomorphism\u2014a unique most compact one, \u201cthe core\u201d, 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.<\/jats:p>","DOI":"10.1145\/1346330.1346334","type":"journal-article","created":{"date-parts":[[2008,5,15]],"date-time":"2008-05-15T18:28:05Z","timestamp":1210876085000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":51,"title":["Efficient core computation in data exchange"],"prefix":"10.1145","volume":"55","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Nash","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,15]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison Wesley Reading MA.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.v47:4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320112"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208017"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Ceri S. Gottlob G. and Tanca L. 1990. Logic Programming and Databases. Springer-Verlag New York.   Ceri S. Gottlob G. and Tanca L. 1990. Logic Programming and Databases. Springer-Verlag New York.","DOI":"10.1007\/978-3-642-83952-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT). 225--241","author":"Deutsch A.","key":"e_1_2_1_11_1","unstructured":"Deutsch , A. , and Tannen , V . 2003. Reformulation of XML Queries and constraints . In Proceedings of the International Conference on Database Theory (ICDT). 225--241 . Deutsch, A., and Tannen, V. 2003. Reformulation of XML Queries and constraints. In Proceedings of the International Conference on Database Theory (ICDT). 225--241."},{"key":"e_1_2_1_12_1","unstructured":"Downey R. Fellows M. and Tailor U. 1996. The parameterized complexity of relational database queries and an improved characterization of W&lsqb;1&rsqb;. In Combinatorics Complexity and Logic\u2014Proceedings DMTCS'96 D. S. Bridges C. S. Calude J. Gibbons S. Reeves and I. H. Witten Eds.  Downey R. Fellows M. and Tailor U. 1996. The parameterized complexity of relational database queries and an improved characterization of W&lsqb;1&rsqb;. In Combinatorics Complexity and Logic\u2014Proceedings DMTCS'96 D. S. Bridges C. S. Calude J. Gibbons S. Reeves and I. H. Witten Eds."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag New York.  Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322347"},{"key":"e_1_2_1_15_1","unstructured":"Fagin R. 2005. Extending the core greedy algorithm to allow target TGDS with singleton left-hand sides. Unpublished manuscript.  Fagin R. 2005. Extending the core greedy algorithm to allow target TGDS with singleton left-hand sides. Unpublished manuscript."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1O16\/j.tcs.2004.10.033"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773163"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065187"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90069-N"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214118"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00078-3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00030-8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142358"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701396807"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/637411.637428"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055573"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065176"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"volume-title":"The Theory of Relational Databases","author":"Maier D.","key":"e_1_2_1_34_1","unstructured":"Maier , D. 1983. The Theory of Relational Databases . Computer Science Press , Rockville, MD . Maier, D. 1983. The Theory of Relational Databases. Computer Science Press, Rockville, MD."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_2_1_36_1","unstructured":"Moret B. M. E. and Shapiro H. D. 1991. Algorithms from P to NP (Vol. 1): Design and Efficiency. Benjamin-Cummings Publishing Co. Inc. Redwood City CA.   Moret B. M. E. and Shapiro H. D. 1991. Algorithms from P to NP (Vol. 1): Design and Efficiency. Benjamin-Cummings Publishing Co. Inc. Redwood City CA."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_1_38_1","volume-title":"Tech. Rep. DBAI-TR-2008-01","author":"Pichler R.","year":"2008","unstructured":"Pichler , R. , and Savenkov , V . 2008 . Implementing core computation for data exchange. Tech. Rep. DBAI-TR-2008-01 , Institut f\u00fcr Informationssysteme, Technische Universit\u00e4t Wien, A-1040 Vienna, Austria . Pichler, R., and Savenkov, V. 2008. Implementing core computation for data exchange. Tech. Rep. DBAI-TR-2008-01, Institut f\u00fcr Informationssysteme, Technische Universit\u00e4t Wien, A-1040 Vienna, Austria."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press","author":"Qian X.","year":"1996","unstructured":"Qian , X. 1996 . Query folding . In Proceedings of the IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press , Los Alamitos, CA, 48--55. Qian, X. 1996. Query folding. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). IEEE Computer Society Press, Los Alamitos, CA, 48--55."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055587"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346334","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1346330.1346334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:58Z","timestamp":1750253938000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1346330.1346334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["10.1145\/1346330.1346334"],"URL":"https:\/\/doi.org\/10.1145\/1346330.1346334","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2008,5]]},"assertion":[{"value":"2006-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}