{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:41Z","timestamp":1750308761479,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000268","name":"Biotechnology and Biological Sciences Research Council","doi-asserted-by":"publisher","award":["BB\/D006473\/1"],"award-info":[{"award-number":["BB\/D006473\/1"]}],"id":[{"id":"10.13039\/501100000268","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["60228006"],"award-info":[{"award-number":["60228006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ERSRC","award":["GR\/S63205\/01GR\/T27433\/01"],"award-info":[{"award-number":["GR\/S63205\/01GR\/T27433\/01"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            A fundamental concern of data integration in an XML context is the ability to\n            <jats:italic>embed<\/jats:italic>\n            one or more source documents in a target document so that (a) the target document conforms to a target schema and (b) the information in the source documents is\n            <jats:italic>preserved<\/jats:italic>\n            . In this paper, information preservation for XML is formally studied, and the results of this study guide the definition of a novel notion of\n            <jats:italic>schema embedding<\/jats:italic>\n            between two XML DTD schemas represented as graphs. Schema embedding generalizes the conventional notion of graph similarity by allowing an edge in a source DTD schema to be mapped to a path in the target DTD. Instance-level embeddings can be derived from the schema embedding in a straightforward manner, such that conformance to a target schema and information preservation are guaranteed. We show that it is NP-complete to find an embedding between two DTD schemas. We also outline efficient heuristic algorithms to find candidate embeddings, which have proved effective by our experimental study. These yield the first systematic and effective approach to finding information preserving XML mappings.\n          <\/jats:p>","DOI":"10.1145\/1331904.1331908","type":"journal-article","created":{"date-parts":[[2008,3,25]],"date-time":"2008-03-25T14:01:40Z","timestamp":1206453700000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Information preserving XML schema embedding"],"prefix":"10.1145","volume":"33","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh and Lucent Technologies"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip","family":"Bohannon","sequence":"additional","affiliation":[{"name":"Yahoo! Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,3,21]]},"reference":[{"volume-title":"Web: From Relations to Semistructured Data and XML. Morgan Kaufman.","year":"2000","author":"Abiteboul S.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90010-1"},{"key":"e_1_2_1_4_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00032-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065171"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066238"},{"volume-title":"Proceedings of International Conference on Very Large Databases (VLDB).","author":"Barbosa D.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065172"},{"volume-title":"Proceedings of International Conference on Very Large Databases (VLDB).","author":"Bohannon P.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of International Conference on Database Theory (ICDT).","author":"Buneman P.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014899909753"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543646"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.917566"},{"key":"e_1_2_1_15_1","unstructured":"Clark J. 1999. XSL Transformations (XSLT). W3C Recommendation. http:\/\/www.w3.org\/TR\/xslt.  Clark J. 1999. XSL Transformations (XSLT). W3C Recommendation. http:\/\/www.w3.org\/TR\/xslt."},{"key":"e_1_2_1_16_1","unstructured":"Clark J. and DeRose S. 1999. XML Path Language (XPath). W3C Working Draft.  Clark J. and DeRose S. 1999. XML Path Language (XPath). W3C Working Draft."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375731"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80034-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142359"},{"volume-title":"2000. XML Schema Part 0: Primer","author":"Fallside D. C.","key":"e_1_2_1_20_1"},{"volume-title":"IEEE International Conference on Data Engineering (ICDE).","author":"Fan W.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567117"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065188"},{"key":"e_1_2_1_24_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.   Garey M. and Johnson D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/369275.369284"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.1318562"},{"key":"e_1_2_1_27_1","unstructured":"Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addision Wesley.   Hopcroft J. E. and Ullman J. D. 1979. Introduction to Automata Theory Languages and Computation. Addision Wesley."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215061"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872798"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065176"},{"volume-title":"Proceedings of International Conference on Very Large Databases (VLDB).","author":"Lakshmanan L.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543644"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-023X(99)00044-0"},{"volume-title":"Proceedings of International Conference on Very Large Databases (VLDB).","author":"Madhavan J.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_28"},{"volume-title":"Proceedings of IEEE International Conference on Data Engineering (ICDE).","author":"Melnik S.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872782"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/373626.373713"},{"volume-title":"Proceedings of International Conference on Very Large Databases (VLDB).","author":"Miller R. J.","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(94)90024-8"},{"volume-title":"Proceedings of International Conference on Very Large Databases (VLDB).","author":"Milo T.","key":"e_1_2_1_42_1"},{"volume-title":"Proceedings International Database Engineering & Applications Symposium (IDEAS).","author":"Palopoli L.","key":"e_1_2_1_43_1"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335173"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100057"},{"key":"e_1_2_1_46_1","unstructured":"Sim\u00e9on J. and Fernandez M. Galax. http:\/\/db.bell-labs.com\/galax.  Sim\u00e9on J. and Fernandez M. Galax. http:\/\/db.bell-labs.com\/galax."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322273"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Wadler P. 2000. A formal semantics for patterns in xsl. Tech. rep. Bell Labs.  Wadler P. 2000. A formal semantics for patterns in xsl. Tech. rep. Bell Labs.","DOI":"10.1162\/10996620052104302"},{"key":"e_1_2_1_49_1","unstructured":"Xerces and Xalan. http:\/\/xml.apache.org.  Xerces and Xalan. http:\/\/xml.apache.org."},{"volume-title":"Handbook of Formal Languages","author":"Yu S.","key":"e_1_2_1_50_1"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1331904.1331908","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1331904.1331908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:28Z","timestamp":1750278148000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1331904.1331908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1331904.1331908"],"URL":"https:\/\/doi.org\/10.1145\/1331904.1331908","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2006-06-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-03-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}