{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T19:27:11Z","timestamp":1791055631182,"version":"4.1.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,4,1]],"date-time":"2013-04-01T00:00:00Z","timestamp":1364774400000},"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":[[2013,4]]},"abstract":"<jats:p>\n            We propose a mapping from a database conceptual design to a schema for XML that produces highly connected and nested XML structures. We first introduce two alternative definitions of the mapping, one modeling entities as global XML elements and expressing relationships among them in terms of keys and key references (flat design), the other one encoding relationships by properly including the elements for some entities into the elements for other entities (nest design). Then we provide a benchmark evaluation of the two solutions showing that the nest approach, compared to the flat one, leads to improvements in both query and validation performances. This motivates us to systematically investigate the best way to nest XML structures. We identify two different nesting solutions: a maximum\n            <jats:italic>depth<\/jats:italic>\n            nesting, that keeps low the number of costly join operations that are necessary to reconstruct information at query time using the mapped schema, and a maximum\n            <jats:italic>density<\/jats:italic>\n            nesting, that minimizes the number of schema constraints used in the mapping of the conceptual schema, thus reducing the validation overhead. On the one hand, the problem of finding a maximum depth nesting turns out to be NP-complete and, moreover, it admits no constant ratio approximation algorithm. On the other hand, we devise a graph-theoretic algorithm, NiduX, that solves the maximum density problem in linear time. Interestingly, NiduX finds the optimal solution for the harder maximum depth problem whenever the conceptual design graph is either acyclic or complete. In randomly generated intermediate cases of the graph topology, we experimentally show that NiduX finds a good approximation of the optimal solution.\n          <\/jats:p>","DOI":"10.1145\/2445583.2445589","type":"journal-article","created":{"date-parts":[[2013,4,23]],"date-time":"2013-04-23T13:04:26Z","timestamp":1366722266000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A graph-theoretic approach to map conceptual designs to XML schemas"],"prefix":"10.1145","volume":"38","author":[{"given":"Massimo","family":"Franceschet","sequence":"first","affiliation":[{"name":"University of Udine"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Donatella","family":"Gubiani","sequence":"additional","affiliation":[{"name":"University of Udine"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Angelo","family":"Montanari","sequence":"additional","affiliation":[{"name":"University of Udine"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carla","family":"Piazza","sequence":"additional","affiliation":[{"name":"University of Udine"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,4,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4371(99)00291-5"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0998"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 19th International Conference on Conceptual Modeling. Springer, 309--322","author":"Bird B."},{"key":"e_1_2_1_5_1","unstructured":"Boncz P. Grust T. van Keulen M. Manegold S. Rittinger J. and Teubner J. 2011. MonetDB\/XQuery. MonetDB database system with XQuery front-end. http:\/\/monetdb.cwi.nl\/XQuery\/index.html.  Boncz P. Grust T. van Keulen M. Manegold S. Rittinger J. and Teubner J. 2011. MonetDB\/XQuery. MonetDB database system with XQuery front-end. http:\/\/monetdb.cwi.nl\/XQuery\/index.html."},{"key":"e_1_2_1_6_1","first-page":"376","article-title":"A theorem on trees","volume":"23","author":"Cayley A.","year":"1889","journal-title":"Q. J. Math."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141277.1141388"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 19th International Conference on Conceptual Modeling. Springer, 558--571","author":"Conrad R."},{"key":"e_1_2_1_9_1","unstructured":"DBIS Research Group. 2011. BaseX: Processing and visualizing XML with a native XML database. http:\/\/www.inf.uni-konstanz.de\/dbis\/basex\/.  DBIS Research Group. 2011. BaseX: Processing and visualizing XML with a native XML database. http:\/\/www.inf.uni-konstanz.de\/dbis\/basex\/."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 2nd International Conference on Web Information Systems Engineering. IEEE Computer Society, 171--180","author":"Dobbie G."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00361-X"},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"Converting relationships to XML nested structures","volume":"28","author":"Duta A.","year":"2004","journal-title":"J. Inf. Org. Sci."},{"key":"e_1_2_1_13_1","unstructured":"Elmasri R. and Navathe S. 2010. Fundamentals of Database Systems. 6th edn. Addison-Wesley.   Elmasri R. and Navathe S. 2010. Fundamentals of Database Systems. 6th edn. Addison-Wesley."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2004.09.010"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2007.10.004"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218194006002744"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2005.06.010"},{"key":"e_1_2_1_18_1","unstructured":"Franceschet M. Gubiani D. Montanari A. and Piazza C. 2012. From entity relationship to XML Schema: a graph-theoretic approach. Tech. rep. UDMI\/01\/12\/RR University of Udine.  Franceschet M. Gubiani D. Montanari A. and Piazza C. 2012. From entity relationship to XML Schema: a graph-theoretic approach. Tech. rep. UDMI\/01\/12\/RR University of Udine."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00265-4"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 15th Italian Symposium on Advanced Database Systems. 495--498","author":"Gubiani D."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:WWWJ.0000040896.89535.6b"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523689"},{"key":"e_1_2_1_23_1","unstructured":"Kay M. 2011. Saxon. The XSLT and XQuery processor. http:\/\/saxon.sourceforge.net.  Kay M. 2011. Saxon. The XSLT and XQuery processor. http:\/\/saxon.sourceforge.net."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/andp.18471481202"},{"key":"e_1_2_1_25_1","first-page":"396","article-title":"Automatic generation of XML DTDs from conceptual database schemas","volume":"1","author":"Kleiner C.","year":"2001","journal-title":"GI Jahrestagung"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science. Springer, 232--243","author":"Krishnan R."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/584792.584840"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 26th International Conference on Conceptual Modeling. Springer, 19--30","author":"Link S."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11775300_43"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-005-4263-5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/IMSCCS.2006.237"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 4th Asia-Pacific Conference on Conceptual Modelling. Australian Computer Society, 37--48","author":"Necasky M.","year":"2007"},{"key":"e_1_2_1_33_1","unstructured":"Papadimitriou C. 1995. Computational Complexity. Addison Wesley Longman.  Papadimitriou C. 1995. Computational Complexity. Addison Wesley Longman."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 15th Italian Symposium on Advanced Database Systems. 192--199","author":"Pigozzo P."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/338407.338680"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases. ACM, 974--985","author":"Schmidt A."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1363686.1363926"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-009-0272-1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/767141.767144"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.105"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 13th International Conference on Database Systems for Advanced Applications. Springer, 4--18","author":"Zhou R."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2445583.2445589","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2445583.2445589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:09Z","timestamp":1750239249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2445583.2445589"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1145\/2445583.2445589"],"URL":"https:\/\/doi.org\/10.1145\/2445583.2445589","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"2011-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}