{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:39:38Z","timestamp":1753889978168,"version":"3.41.2"},"reference-count":44,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2011,9,8]],"date-time":"2011-09-08T00:00:00Z","timestamp":1315440000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>It is known that the composition of schema mappings, each specified by\nsource-to-target tgds (st-tgds), can be specified by a second-order tgd (SO\ntgd). We consider the question of what happens when target constraints are\nallowed. Specifically, we consider the question of specifying the composition\nof standard schema mappings (those specified by st-tgds, target egds, and a\nweakly acyclic set of target tgds). We show that SO tgds, even with the\nassistance of arbitrary source constraints and target constraints, cannot\nspecify in general the composition of two standard schema mappings. Therefore,\nwe introduce source-to-target second-order dependencies (st-SO dependencies),\nwhich are similar to SO tgds, but allow equations in the conclusion. We show\nthat st-SO dependencies (along with target egds and target tgds) are sufficient\nto express the composition of every finite sequence of standard schema\nmappings, and further, every st-SO dependency specifies such a composition. In\naddition to this expressive power, we show that st-SO dependencies enjoy other\ndesirable properties. In particular, they have a polynomial-time chase that\ngenerates a universal solution. This universal solution can be used to find the\ncertain answers to unions of conjunctive queries in polynomial time. It is easy\nto show that the composition of an arbitrary number of standard schema mappings\nis equivalent to the composition of only two standard schema mappings. We show\nthat surprisingly, the analogous result holds also for schema mappings\nspecified by just st-tgds (no target constraints). This is proven by showing\nthat every SO tgd is equivalent to an unnested SO tgd (one where there is no\nnesting of function symbols). Similarly, we prove unnesting results for st-SO\ndependencies, with the same types of consequences.<\/jats:p>","DOI":"10.2168\/lmcs-7(3:13)2011","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T13:45:24Z","timestamp":1415972724000},"source":"Crossref","is-referenced-by-count":2,"title":["Composition with Target Constraints"],"prefix":"10.46298","volume":"Volume 7, Issue 3","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[]},{"given":"Ronald","family":"Fagin","sequence":"additional","affiliation":[]},{"given":"Alan","family":"Nash","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2011,9,8]]},"reference":[{"unstructured":"F. Afrati and N. Kiourtis. Query Answering Using Views in the Presence of Dependencies. InNew Trends in Information Integration (NTII), pages 8-11, 2008.","key":"10.2168\/LMCS-7(3:13)2011_AK08"},{"doi-asserted-by":"publisher","key":"10.2168\/LMCS-7(3:13)2011_AK09","DOI":"10.1145\/1514894.1514899"},{"doi-asserted-by":"crossref","unstructured":"F. Afrati, C. Li, and V. Pavlaki. Data Exchange in the Presence of Arithmetic Comparisons. InExtending Data Base Technology (EDBT), pages 487-498, 2008.","key":"10.2168\/LMCS-7(3:13)2011_ALP08a","DOI":"10.1145\/1353343.1353403"},{"doi-asserted-by":"crossref","unstructured":"F. Afrati, C. Li, and V. Pavlaki. Data Exchange: Query Answering for Incomplete Data Sources. In3rd International Conference on Scalable Information Systems, 2009.","key":"10.2168\/LMCS-7(3:13)2011_ALP08b","DOI":"10.4108\/ICST.INFOSCALE2008.3476"},{"doi-asserted-by":"crossref","unstructured":"M. Arenas, P. Barcel\u00f3, R. Fagin, and L. Libkin. Locally Consistent Transformations and Query Answering in Data Exchange. In23rd ACM Symposium on Principles of Database Systems (PODS), pages 229-240, 2004.","key":"10.2168\/LMCS-7(3:13)2011_ABFL04","DOI":"10.1145\/1055558.1055592"},{"doi-asserted-by":"publisher","key":"10.2168\/LMCS-7(3:13)2011_AFN10","DOI":"10.1145\/1804669.1804687"},{"doi-asserted-by":"crossref","unstructured":"M. Arenas, J. P\u00e9rez, and C. Riveros. The Recovery of a Schema Mapping: Bringing Back Exchanged Data. In27th ACM Symposium on Principles of Database Systems (PODS), pages 13-22, 2008.","key":"10.2168\/LMCS-7(3:13)2011_APR08","DOI":"10.1145\/1376916.1376920"},{"issue":"1","key":"10.2168\/LMCS-7(3:13)2011_Ba09","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1145\/1558334.1558341","volume":"38","author":"P. Barcel\u00f3","year":"2009","journal-title":"SIGMOD Record"},{"unstructured":"P. A. Bernstein. Applying Model Management to Classical Meta-Data Problems. InConference on Innovative Data Systems Research (CIDR), pages 209-220, 2003.","key":"10.2168\/LMCS-7(3:13)2011_Bernstein03"},{"issue":"1","key":"10.2168\/LMCS-7(3:13)2011_CFP84","first-page":"29","volume":"20","author":"M. Casanova, R. Fagin, and C. Papadimitr","year":"1984","journal-title":"J. Computer and System Sciences"},{"doi-asserted-by":"publisher","key":"10.2168\/LMCS-7(3:13)2011_CDO09","DOI":"10.1145\/1514894.1514905"},{"doi-asserted-by":"crossref","unstructured":"R. Chirkova and M. Genesereth. Equivalence of {SQL Queries in Presence of Embedded Dependencies}. In28th ACM Symposium on Principles of Database Systems (PODS), pages 217-226, 2009.","key":"10.2168\/LMCS-7(3:13)2011_CG09","DOI":"10.1145\/1559795.1559829"},{"unstructured":"S. S. Cosmadakis and P. C. Kanellakis. Functional and Inclusion Dependencies: A Graph Theoretic Approach. InAdvances in Computing Research, volume 3, pages 163-184. 1986.","key":"10.2168\/LMCS-7(3:13)2011_CK86"},{"doi-asserted-by":"crossref","unstructured":"A. Deutsch, A. Nash, and J. Remmel. The Chase Revisited. In27th ACM Symposium on Principles of Database Systems (PODS), pages 149-158, 2008.","key":"10.2168\/LMCS-7(3:13)2011_DNR08","DOI":"10.1145\/1376916.1376938"},{"issue":"1","key":"10.2168\/LMCS-7(3:13)2011_DPT06","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/1121995.1122010","volume":"35","author":"A. Deutsch, L. Popa, and V. Tannen","year":"2006","journal-title":"SIGMOD Record"},{"doi-asserted-by":"crossref","unstructured":"A. Deutsch and V. Tannen. Reformulation of XML Queries and Constraints. InInternational Conference on Database Theory (ICDT), pages 225-241, 2003.","key":"10.2168\/LMCS-7(3:13)2011_DT03","DOI":"10.1007\/3-540-36285-1_15"},{"issue":"1","key":"10.2168\/LMCS-7(3:13)2011_DGL00","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0743-1066(99)00025-4","volume":"43","author":"O. M. Duschka, M. R. Genesereth, and A.","year":"2000","journal-title":"J. Log. Program."},{"doi-asserted-by":"crossref","unstructured":"H. B. Enderton.A Mathematical Introduction to Logic: Second Edition. Academic Press, 2001.","key":"10.2168\/LMCS-7(3:13)2011_En01","DOI":"10.1016\/B978-0-08-049646-7.50005-9"},{"doi-asserted-by":"publisher","key":"10.2168\/LMCS-7(3:13)2011_Fa07","DOI":"10.1145\/1292609.1292615"},{"unstructured":"R. Fagin, L. Haas, M. Hernandez, R. Miller, L. Popa, and Y. Velegrakis. Clio: Schema Mapping Creation and Data Exchange. In A. Borgida, V. Chaudhri, P. Giorgini, and E. Yu, editors,Conceptual Modeling: Foundations and Applications, Essays in Honor of John Mylopoulos, volume 5600 ofLecture Notes in Computer Science, pages 198-236. Springer-Verlag, 2009.","key":"10.2168\/LMCS-7(3:13)2011_FHHMPV09"},{"doi-asserted-by":"crossref","unstructured":"R. Fagin, P. Kolaitis, A. Nash, and L. Popa. Towards a Theory of Schema-Mapping Optimization. In27th ACM Symposium on Principles of Database Systems (PODS), pages 33-42, 2008.","key":"10.2168\/LMCS-7(3:13)2011_FKNP08","DOI":"10.1145\/1376916.1376922"},{"issue":"4","key":"10.2168\/LMCS-7(3:13)2011_FKPT05","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1145\/1114244.1114249","volume":"30","author":"R. Fagin, P. G. Kolaitis, L. Popa, and W","year":"2005","journal-title":"\u00c3\u0085CM Trans. Database Syst."},{"issue":"1","key":"10.2168\/LMCS-7(3:13)2011_FSV95","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1006\/inco.1995.1100","volume":"120","author":"R. Fagin, L. Stockmeyer, and M. Vardi","year":"1995","journal-title":"Information and Computation"},{"unstructured":"A. Fuxman, M. A. Hern\u00e1ndez, C. T. H. Ho, R. J. Miller, P. Papotti, and L. Popa. Nested Mappings: Schema Mapping Reloaded. InVery Large Data Bases (VLDB), pages 67-78, 2006.","key":"10.2168\/LMCS-7(3:13)2011_FHHMPP06"},{"issue":"4","key":"10.2168\/LMCS-7(3:13)2011_FKMT06","doi-asserted-by":"crossref","first-page":"1454","DOI":"10.1145\/1189769.1189778","volume":"31","author":"A. Fuxman, P. Kolaitis, R. Miller, and W","year":"2006","journal-title":"ACM Transactions on Database Systems"},{"doi-asserted-by":"crossref","unstructured":"H. Gaifman. On Local and Non-local Properties. InHerbrand Symposium Logic Colloquium, North Holland, pages 105-135, 1982.","key":"10.2168\/LMCS-7(3:13)2011_Gai82","DOI":"10.1016\/S0049-237X(08)71879-2"},{"doi-asserted-by":"crossref","unstructured":"G. D. Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. On Reconciling Data Exchange, Data Integration, and Peer Data Management. In26th ACM Symposium on Principles of Database Systems (PODS), pages 133-142, 2007.","key":"10.2168\/LMCS-7(3:13)2011_GLLR07","DOI":"10.1145\/1265530.1265549"},{"doi-asserted-by":"publisher","key":"10.2168\/LMCS-7(3:13)2011_GN08","DOI":"10.1145\/1346330.1346334"},{"issue":"3","key":"10.2168\/LMCS-7(3:13)2011_GS08","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1093\/comjnl\/bxm056","volume":"51","author":"G. Gottlob and S. Szeider","year":"2008","journal-title":"Computer Journal"},{"unstructured":"T. Green, G. Karvounarakis, Z. Ives, and V. Tannen. Update Exchange with Mappings and Provenance. InInternational Conference on Very Large Data Bases (VLDB), pages 675-686, 2007.","key":"10.2168\/LMCS-7(3:13)2011_GKIT07"},{"doi-asserted-by":"crossref","unstructured":"W. P. Hanf. Model-theoretic Methods in the Study of Elementary Logic. InThe Theory of Models; Addison, Henkin, and Tarski, eds., North Holland, pages 132-145, 1965.","key":"10.2168\/LMCS-7(3:13)2011_Han65","DOI":"10.1016\/B978-0-7204-2233-7.50020-4"},{"doi-asserted-by":"crossref","unstructured":"A. Hernich and N. Schweikardt. {CWA-solutions for Data Exchange Settings with Target Dependencies}. In26th ACM Symposium on Principles of Database Systems (PODS), pages 113-122, 2007.","key":"10.2168\/LMCS-7(3:13)2011_HS07","DOI":"10.1145\/1265530.1265547"},{"unstructured":"G. Karvounaraki and V. Tannen. Conjunctive Queries and Mappings with Unequalities. Technical Report MS-CIS-08-37, University of Pennsylvania, 2008.","key":"10.2168\/LMCS-7(3:13)2011_KT08"},{"doi-asserted-by":"crossref","unstructured":"P. G. Kolaitis. Schema Mappings, Data Exchange, and Metadata Management. In24th ACM Symposium on Principles of Database Systems (PODS), pages 61-75, 2005.","key":"10.2168\/LMCS-7(3:13)2011_Ko05","DOI":"10.1145\/1065167.1065176"},{"doi-asserted-by":"crossref","unstructured":"M. Lenzerini. Data Integration: A Theoretical Perspective. In21st ACM Symposium on Principles of Database Systems (PODS), pages 233-246, 2002.","key":"10.2168\/LMCS-7(3:13)2011_Len02","DOI":"10.1145\/543613.543644"},{"doi-asserted-by":"crossref","unstructured":"L. Libkin.Elements of Finite Model Theory. Springer-Verlag, 1st edition, 2004.","key":"10.2168\/LMCS-7(3:13)2011_fmt-book","DOI":"10.1007\/978-3-662-07003-1"},{"doi-asserted-by":"crossref","unstructured":"L. Libkin and C. Sirangelo. Data Exchange and Schema Mappings in Open and Closed Worlds. In27th ACM Symposium on Principles of Database Systems (PODS), pages 139-148, 2008.","key":"10.2168\/LMCS-7(3:13)2011_LS08","DOI":"10.1145\/1376916.1376937"},{"doi-asserted-by":"crossref","unstructured":"J. Madhavan and A. Y. Halevy. Composing Mappings Among Data Sources. InInternational Conference on Very Large Data Bases (VLDB), pages 572-583, 2003.","key":"10.2168\/LMCS-7(3:13)2011_MH03","DOI":"10.1016\/B978-012722442-8\/50057-4"},{"doi-asserted-by":"crossref","unstructured":"M. Meier. Towards Rule-Based Minimization of {RDF Graphs under Constraints}. InWeb Reasoning and Rule Systems, volume 5341 ofLecture Notes in Computer Science, pages 89-103. Springer-Verlag, 2008.","key":"10.2168\/LMCS-7(3:13)2011_Me08","DOI":"10.1007\/978-3-540-88737-9_8"},{"doi-asserted-by":"crossref","unstructured":"S. Melnik.Generic Model Management: Concepts and Algorithms, volume 2967 ofLecture Notes in Computer Science. Springer, 2004.","key":"10.2168\/LMCS-7(3:13)2011_Me04","DOI":"10.1007\/b97859"},{"doi-asserted-by":"crossref","unstructured":"A. Nash, P. A. Bernstein, and S. Melnik. Composition of Mappings Given by Embedded Dependencies. In24th ACM Symposium on Principles of Database Systems (PODS), pages 172-183, 2005.","key":"10.2168\/LMCS-7(3:13)2011_NBM05","DOI":"10.1145\/1065167.1065189"},{"issue":"7","key":"10.2168\/LMCS-7(3:13)2011_PT09","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/j.datak.2009.02.005","volume":"68","author":"P. Papotti and R. Torlone","year":"2009","journal-title":"Data and Knowledge Engineering"},{"doi-asserted-by":"publisher","key":"10.2168\/LMCS-7(3:13)2011_tK09","DOI":"10.1145\/1514894.1514903"},{"doi-asserted-by":"crossref","unstructured":"P. Vassiliadis, A. Simitsis, and S. Skiadopoulos. On the Logical Modeling of ETL Processes. InInternational Conference on Advanced Information Systems Engineering (CAiSE), pages 782-786, 2002.","key":"10.2168\/LMCS-7(3:13)2011_VSS02","DOI":"10.1145\/583890.583893"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/905\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/905\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:58:53Z","timestamp":1681243133000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/905"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,8]]},"references-count":44,"URL":"https:\/\/doi.org\/10.2168\/lmcs-7(3:13)2011","relation":{"is-same-as":[{"id-type":"arxiv","id":"1106.3745","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1106.3745","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2011,9,8]]},"article-number":"905"}}