{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:34Z","timestamp":1750308754278,"version":"3.41.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,2,1]],"date-time":"2006-02-01T00:00:00Z","timestamp":1138752000000},"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. Internet Technol."],"published-print":{"date-parts":[[2006,2]]},"abstract":"<jats:p>\n            Managing multiple versions of XML documents represents a critical requirement for many applications. Recently, there has been much work on supporting complex queries on XML data (e.g., regular path expressions, structural projections, etc.). In this article, we examine the problem of implementing efficiently such complex queries on multiversion XML documents. Our approach relies on a numbering scheme, whereby durable node numbers (DNNs) are used to preserve the order among the nodes of the XML tree while remaining invariant with respect to updates. Using the document's DNNs, we show that many complex queries are reduced to combinations of\n            <jats:italic>range version retrieval<\/jats:italic>\n            queries. We thus examine three alternative storage organizations\/indexing schemes to efficiently evaluate range version retrieval queries in this environment. A thorough performance analysis is then presented to reveal the advantages of each scheme.\n          <\/jats:p>","DOI":"10.1145\/1125274.1125277","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"53-84","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Supporting complex queries on multiversion XML documents"],"prefix":"10.1145","volume":"6","author":[{"given":"Shu-Yao","family":"Chien","sequence":"first","affiliation":[{"name":"NCR"}]},{"given":"Vassilis J.","family":"Tsotras","sequence":"additional","affiliation":[{"name":"University of California, Riverside"}]},{"given":"Carlo","family":"Zaniolo","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles"}]},{"given":"Donghui","family":"Zhang","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA"}]}],"member":"320","published-online":{"date-parts":[[2006,2]]},"reference":[{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Abiteboul S.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/s007990050005","article-title":"The Lorel query language for semistructured data","volume":"1","author":"Abiteboul S.","year":"1997","journal-title":"Journal of Digital Libraries"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 141--154","author":"Al-Khalifa S.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050028"},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). ACM","author":"Beckmann N.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Beech D.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","unstructured":"Bosak J. 1999. The plays of Shakespeare in XML. http:\/\/www.oasis-open.org\/cover\/bosakShakespeare200.html.  Bosak J. 1999. The plays of Shakespeare in XML. http:\/\/www.oasis-open.org\/cover\/bosakShakespeare200.html."},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). ACM","author":"Bruno N.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). ACM","author":"Buneman P.","key":"e_1_2_1_9_1"},{"volume-title":"Proceedings of the WWW Conference. 1171--1187","author":"Ceri S.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the International Workshop on the Web and Databases (WebDB). 1--25","author":"Chamberlin D.","key":"e_1_2_1_11_1"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Chawathe S.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). ACM","author":"Chawathe S.","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of the International Workshop on the Web and Databases (WebDB). 184--200","author":"Chien S.-Y.","key":"e_1_2_1_14_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 291--300","author":"Chien S.-Y.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0079-4"},{"volume-title":"Proceedings of the International Conference on Web Information Systems Engineering (WISE). 232--244","author":"Chien S.-Y.","key":"e_1_2_1_17_1"},{"volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT). 161--178","author":"Chien S.-Y.","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 263--274","author":"Chien S.-Y.","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of the ACM International Symposium on Principles of Database Systems (PODS). ACM","author":"Cohen E.","key":"e_1_2_1_20_1"},{"volume-title":"Proceedings of the WWW Conference. 1155--1169","author":"Deutsch A.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Diao Y.","key":"e_1_2_1_22_1"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 14--23","author":"Fernandez M.","key":"e_1_2_1_23_1"},{"volume-title":"Proceedings of the International Workshop on the Web and Databases (WebDB).","author":"Fiebig T.","key":"e_1_2_1_24_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).","author":"Gottlob G.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/640990.640992"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Gottlob G.","key":"e_1_2_1_27_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB).","year":"2003","author":"Halverson A.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.755613"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Jiang H.","key":"e_1_2_1_30_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 451--460","author":"Jiang L.","key":"e_1_2_1_31_1"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Kaplan H.","key":"e_1_2_1_32_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 455--462","author":"Katz R. H.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.667079"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01354880"},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). 426--435","author":"Lanka S.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","unstructured":"Leblang D. 1994. The CM challenge: Configuration management that works. In Configuration Management W. F. Tichy ed. Wiley 1--38.   Leblang D. 1994. The CM challenge: Configuration management that works. In Configuration Management W. F. Tichy ed. Wiley 1--38."},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). 10","author":"Levy A.","key":"e_1_2_1_38_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 361--370","author":"Li Q.","key":"e_1_2_1_39_1"},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). 315--324","author":"Lomet D.","key":"e_1_2_1_40_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 581--590","author":"Marian A.","key":"e_1_2_1_41_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 315--326","author":"McHugh J.","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.404027"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Rao P.","key":"e_1_2_1_44_1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1109\/TSE.1975.6312866","article-title":"The source code control system","volume":"4","author":"Rochkind M. J.","year":"1975","journal-title":"IEEE Transactions on Software Engineering SE-1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/319806.319816"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 302--314","author":"Shanmugasundaram J.","key":"e_1_2_1_47_1"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). 431--440","author":"Tao Y.","key":"e_1_2_1_48_1"},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). 10","author":"Tatarinov I.","key":"e_1_2_1_49_1"},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). 5--10","author":"Tian F.","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380150703"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(95)00011-R"},{"volume-title":"Proceedings of the International Workshop on Research Issues on Data Engineering (RIDE).","author":"Vagena Z.","key":"e_1_2_1_53_1"},{"volume-title":"Proceedings of the International Workshop on the Web and Databases (WebDB).","author":"Vagena Z.","key":"e_1_2_1_54_1"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.599929"},{"volume-title":"Proceedings of the ACM\/SIGMOD Annual Conference on Management of Data (SIGMOD). 10","author":"Wang H.","key":"e_1_2_1_56_1"},{"volume-title":"WWW distributed authoring and versioning, last modified","year":"2001","author":"Webdav","key":"e_1_2_1_57_1"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Wei W.","key":"e_1_2_1_58_1"},{"volume-title":"Proceedings of the DocEng Conference. 10","author":"Wong R.","key":"e_1_2_1_59_1"},{"key":"e_1_2_1_60_1","unstructured":"WWW Consortium 1999. XML path language (XPath) version 1.0. http:\/\/www.w3.org\/TR\/xpath.html.  WWW Consortium 1999. XML path language (XPath) version 1.0. http:\/\/www.w3.org\/TR\/xpath.html."},{"key":"e_1_2_1_61_1","unstructured":"WWW Consortium 2001. XQuery 1.0: An XML query language. W3C working draft (work in progress) http:\/\/www.w3.org\/TR\/xquery.  WWW Consortium 2001. XQuery 1.0: An XML query language. W3C working draft (work in progress) http:\/\/www.w3.org\/TR\/xquery."},{"volume-title":"Proceedings of the ACM International Symposium on Principles of Database Systems (PODS). 10","author":"Zhang D.","key":"e_1_2_1_62_1"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1125274.1125277","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1125274.1125277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:23Z","timestamp":1750278143000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1125274.1125277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,2]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,2]]}},"alternative-id":["10.1145\/1125274.1125277"],"URL":"https:\/\/doi.org\/10.1145\/1125274.1125277","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"type":"print","value":"1533-5399"},{"type":"electronic","value":"1557-6051"}],"subject":[],"published":{"date-parts":[[2006,2]]},"assertion":[{"value":"2006-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}