{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T03:16:17Z","timestamp":1768706177248,"version":"3.49.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:00:00Z","timestamp":1133395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p>\n            A schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). A fundamental problem is composing schema mappings: given two successive schema mappings, derive a schema mapping between the source schema of the first and the target schema of the second that has the same effect as applying successively the two schema mappings.In this article, we give a rigorous semantics to the composition of schema mappings and investigate the definability and computational complexity of the composition of two schema mappings. We first study the important case of schema mappings in which the specification is given by a finite set of source-to-target tuple-generating dependencies (source-to-target tgds). We show that the composition of a finite set of full source-to-target tgds with a finite set of tgds is always definable by a finite set of source-to-target tgds, but the composition of a finite set of source-to-target tgds with a finite set of full source-to-target tgds may not be definable by any set (finite or infinite) of source-to-target tgds; furthermore, it may not be definable by any formula of least fixed-point logic, and the associated composition query may be NP-complete. After this, we introduce a class of existential second-order formulas with function symbols and equalities, which we call\n            <jats:italic>second-order tgds<\/jats:italic>\n            , and make a case that they are the \u201cright\u201d language for composing schema mappings. Specifically, we show that second-order tgds form the smallest class (up to logical equivalence) that contains every source-to-target tgd and is closed under conjunction and composition. Allowing equalities in second-order tgds turns out to be of the essence, even though the \u201cobvious\u201d way to define second-order tgds does not require equalities. We show that second-order tgds without equalities are not sufficiently expressive to define the composition of finite sets of source-to-target tgds. Finally, we show that second-order tgds possess good properties for data exchange and query answering: the chase procedure can be extended to second-order tgds so that it produces polynomial-time computable universal solutions in data exchange settings specified by second-order tgds.\n          <\/jats:p>","DOI":"10.1145\/1114244.1114249","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"994-1055","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":173,"title":["Composing schema mappings"],"prefix":"10.1145","volume":"30","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]},{"given":"Lucian","family":"Popa","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]},{"given":"Wang-Chiew","family":"Tan","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA"}]}],"member":"320","published-online":{"date-parts":[[2005,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_1_2_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_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213006"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR). 209--220","author":"Bernstein P. A.","year":"2003","unstructured":"Bernstein , P. A. 2003 . Applying model management to classical meta-data problems . In Proceedings of the Conference on Innovative Data Systems Research (CIDR). 209--220 . Bernstein, P. A. 2003. Applying model management to classical meta-data problems. In Proceedings of the Conference on Innovative Data Systems Research (CIDR). 209--220."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2703"},{"key":"e_1_2_1_8_1","unstructured":"Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd Edition. Springer-Verlag New York.  Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory 2nd Edition. Springer-Verlag New York."},{"key":"e_1_2_1_9_1","volume-title":"A Mathematical Introduction to Logic","author":"Enderton H. B.","unstructured":"Enderton , H. B. 2001. A Mathematical Introduction to Logic , 2 nd Edition. Academic Press , Orlando, FL . Enderton, H. B. 2001. A Mathematical Introduction to Logic, 2nd Edition. Academic Press, Orlando, FL.","edition":"2"},{"key":"e_1_2_1_10_1","volume-title":"SIAM-AMS Proceedings","volume":"7","author":"Fagin R.","year":"1974","unstructured":"Fagin , R. 1974 . Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation , SIAM-AMS Proceedings , Vol. 7 , R. M. Karp, Ed. 43--73. Fagin, R. 1974. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, R. M. Karp, Ed. 43--73."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322347"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1085304.1085309"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773163"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055572"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167245"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775231"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Immerman N. 1999. Descriptive Complexity. Springer-Verlag New York.  Immerman N. 1999. Descriptive Complexity. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 572--583","author":"Madhavan J.","unstructured":"Madhavan , J. and Halevy , A. Y . 2003. Composing mappings among data sources . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 572--583 . Madhavan, J. and Halevy, A. Y. 2003. Composing mappings among data sources. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 572--583."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 77--88","author":"Miller R. J.","unstructured":"Miller , R. J. , Haas , L. M. , and Hern\u00e1ndez , M . 2000. Schema mapping as query discovery . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 77--88 . Miller, R. J., Haas, L. M., and Hern\u00e1ndez, M. 2000. Schema mapping as query discovery. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 77--88."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 598--609","author":"Popa L.","unstructured":"Popa , L. , Velegrakis , Y. , Miller , R. J. , Hernandez , M. A. , and Fagin , R . 2002. Translating web data . In Proceedings of the International Conference on Very Large Data Bases (VLDB). 598--609 . Popa, L., Velegrakis, Y., Miller, R. J., Hernandez, M. A., and Fagin, R. 2002. Translating web data. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 598--609."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Advanced Information Systems Engineering (CAiSE). 782--786","author":"Vassiliadis P.","unstructured":"Vassiliadis , P. , Simitsis , A. , and Skiadopoulos , S . 2002. On the logical modeling of ETL processes . In Proceedings of the International Conference on Advanced Information Systems Engineering (CAiSE). 782--786 . Vassiliadis, P., Simitsis, A., and Skiadopoulos, S. 2002. On the logical modeling of ETL processes. In Proceedings of the International Conference on Advanced Information Systems Engineering (CAiSE). 782--786."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1114244.1114249","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1114244.1114249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:37Z","timestamp":1750262917000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1114244.1114249"}},"subtitle":["Second-order dependencies to the rescue"],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1145\/1114244.1114249"],"URL":"https:\/\/doi.org\/10.1145\/1114244.1114249","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]},"assertion":[{"value":"2005-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}