{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:31:25Z","timestamp":1750307485657,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2010,10,1]],"date-time":"2010-10-01T00:00:00Z","timestamp":1285891200000},"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":["J. ACM"],"published-print":{"date-parts":[[2010,10]]},"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). The notion of an inverse of a schema mapping is subtle, because a schema mapping may associate many target instances with each source instance, and many source instances with each target instance. In PODS 2006, Fagin defined a notion of the inverse of a schema mapping. This notion is tailored to the types of schema mappings that commonly arise in practice (those specified by \u201csource-to-target tuple-generating dependencies\u201d, or\n            <jats:italic>s-t tgds<\/jats:italic>\n            ). We resolve the key open problem of the complexity of deciding whether there is an inverse. We also explore a number of interesting questions, including: What is the structure of an inverse? When is the inverse unique? How many nonequivalent inverses can there be? When does an inverse have an inverse? How big must an inverse be? Surprisingly, these questions are all interrelated. We show that for schema mappings M specified by\n            <jats:italic>full<\/jats:italic>\n            s-t tgds (those with no existential quantifiers), if M has an inverse, then it has a polynomial-size inverse of a particularly nice form, and there is a polynomial-time algorithm for generating it. We introduce the notion of \u201cessential conjunctions\u201d (or \u201cessential atoms\u201d in the full case), and show that they play a crucial role in the study of inverses. We use them to give greatly simplified proofs of some known results about inverses. What emerges is a much deeper understanding about this fundamental and complex operator.\n          <\/jats:p>","DOI":"10.1145\/1857914.1857915","type":"journal-article","created":{"date-parts":[[2010,11,3]],"date-time":"2010-11-03T14:16:37Z","timestamp":1288793797000},"page":"1-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["The structure of inverses in schema mappings"],"prefix":"10.1145","volume":"57","author":[{"given":"Ronald","family":"Fagin","sequence":"first","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]},{"given":"Alan","family":"Nash","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]}],"member":"320","published-online":{"date-parts":[[2010,11,5]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/1620585.1620589"},{"volume-title":"Proceedings of the Conference on Innovative Data Systems Research. 209--220","year":"2003","author":"Bernstein P. A.","key":"e_1_2_1_2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/1247480.1247482"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/0022-247X(68)90133-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1292609.1292615"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1O16\/j.tcs.2004.10.033"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/1114244.1114249"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/1366102.1366108"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/1559795.1559800"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1065167.1065176"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/543613.543644"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 572--583","author":"Madhavan J.","key":"e_1_2_1_12_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/320107.320115"},{"volume-title":"Generic Model Management: Concepts and Algorithms","author":"Melnik S.","series-title":"Lecture Notes in Computer Science","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/1206049.1206053"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1857914.1857915","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1857914.1857915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:09:10Z","timestamp":1750248550000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1857914.1857915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":15,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["10.1145\/1857914.1857915"],"URL":"https:\/\/doi.org\/10.1145\/1857914.1857915","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2010,10]]},"assertion":[{"value":"2008-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}