{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:58:30Z","timestamp":1750309110092,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"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":[[2008,11]]},"abstract":"<jats:p>An effective approach to support XML updates is to use XQuery extended with update operations. This approach results in very expressive languages which are convenient for users but are difficult to optimize or reason about. A crucial question underlying many static analysis problems for such languages, from optimization to view maintenance, is whether two expressions commute. Unfortunately, commutativity is undecidable for most existing XML update languages. In this article, we propose a conservative analysis for an expressive XML update language that can be used to determine commutativity. The approach relies on a form of path analysis that computes upper bounds for the nodes that are accessed or modified in a given expression. Our main result is a theorem that can be used to identify commuting expressions. We illustrate how the technique applies to concrete examples of query optimization in the presence of updates.<\/jats:p>","DOI":"10.1145\/1412331.1412341","type":"journal-article","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T15:32:31Z","timestamp":1228923151000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Commutativity analysis for XML updates"],"prefix":"10.1145","volume":"33","author":[{"given":"Giorgio","family":"Ghelli","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kristoffer","family":"Rose","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Sim\u00e9on","sequence":"additional","affiliation":[{"name":"IBM Research, Yorktown Heights, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,12,12]]},"reference":[{"volume-title":"Proceedings of the International Workshop on XQuery Implementation, Experience and Perspectives (XIME-P '05)","author":"Benedikt M.","key":"e_1_2_1_1_1","unstructured":"Benedikt , M. , Bonifati , A. , Flesca , S. , and Vyas , A . 2005a. Adding updates to XQuery: Semantics, optimization, and static analysis . In Proceedings of the International Workshop on XQuery Implementation, Experience and Perspectives (XIME-P '05) . Benedikt, M., Bonifati, A., Flesca, S., and Vyas, A. 2005a. Adding updates to XQuery: Semantics, optimization, and static analysis. In Proceedings of the International Workshop on XQuery Implementation, Experience and Perspectives (XIME-P '05)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11513988_37"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.030"},{"key":"e_1_2_1_4_1","unstructured":"Biron P. V. and Malhotra A. 2001. XML schema part 2: Datatypes. W3C recommendation. http:\/\/www.w3.org\/TR\/2001\/REC-xmlschema-2-20010502.  Biron P. V. and Malhotra A. 2001. XML schema part 2: Datatypes. W3C recommendation. http:\/\/www.w3.org\/TR\/2001\/REC-xmlschema-2-20010502."},{"key":"e_1_2_1_5_1","unstructured":"Boag S. Chamberlin D. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2007. XQuery 1.0: An XML query language. W3C recommendation. http:\/\/www.w3.org\/TR\/2007\/REC-xquery-20070123\/.  Boag S. Chamberlin D. Fern\u00e1ndez M. F. Florescu D. Robie J. and Sim\u00e9on J. 2007. XQuery 1.0: An XML query language. W3C recommendation. http:\/\/www.w3.org\/TR\/2007\/REC-xquery-20070123\/."},{"key":"e_1_2_1_6_1","unstructured":"Bray T. Hollander D. and Layman A. 1999. Namespaces in XML. W3C recommendation World Wide Web Consortium. http:\/\/www.w3.org\/TR\/REC-xml-names.  Bray T. Hollander D. and Layman A. 1999. Namespaces in XML. W3C recommendation World Wide Web Consortium. http:\/\/www.w3.org\/TR\/REC-xml-names."},{"volume-title":"Proceedings of the 3rd International Workshop on XQuery Implementation, Experience, and Perspectives (XIME-P' 06)","author":"Chamberlin D.","key":"e_1_2_1_7_1","unstructured":"Chamberlin , D. , Carey , M. , Florescu , D. , Kossman , D. , and Robie , J . 2006. XQuery P: Programming with XQuery . In Proceedings of the 3rd International Workshop on XQuery Implementation, Experience, and Perspectives (XIME-P' 06) . Chamberlin, D., Carey, M., Florescu, D., Kossman, D., and Robie, J. 2006. XQuery P: Programming with XQuery. In Proceedings of the 3rd International Workshop on XQuery Implementation, Experience, and Perspectives (XIME-P' 06)."},{"key":"e_1_2_1_8_1","unstructured":"Chamberlin D. Florescu D. Melton J. Robie J. and Sim\u00e9on J. 2007. XQuery update facility. W3C working draft. http:\/\/www.w3.org\/TR\/2007\/WD-xquery-update-10-20070828\/.  Chamberlin D. Florescu D. Melton J. Robie J. and Sim\u00e9on J. 2007. XQuery update facility. W3C working draft. http:\/\/www.w3.org\/TR\/2007\/WD-xquery-update-10-20070828\/."},{"volume-title":"Proceedings of the 5th International Symposium on Formal Methods for Components and Objects (FMCO).","author":"Cooper E.","key":"e_1_2_1_9_1","unstructured":"Cooper , E. , Lindley , S. , Wadler , P. , and Yallop , J . 2006. Links: Web programming without tears . In Proceedings of the 5th International Symposium on Formal Methods for Components and Objects (FMCO). Cooper, E., Lindley, S., Wadler, P., and Yallop, J. 2006. Links: Web programming without tears. In Proceedings of the 5th International Symposium on Formal Methods for Components and Objects (FMCO)."},{"volume-title":"Proceedings of the 11th Italian Symposium on Advanced Database Systems (SEBD'03)","author":"Dekeyser S.","key":"e_1_2_1_10_1","unstructured":"Dekeyser , S. , Hidders , J. , and Paredaens , J . 2003. Instance independent concurrency control for semistructured databases . In Proceedings of the 11th Italian Symposium on Advanced Database Systems (SEBD'03) . 323--334. Dekeyser, S., Hidders, J., and Paredaens, J. 2003. Instance independent concurrency control for semistructured databases. In Proceedings of the 11th Italian Symposium on Advanced Database Systems (SEBD'03). 323--334."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:WWWJ.0000015864.75561.98"},{"key":"e_1_2_1_12_1","unstructured":"Draper D. Fankhauser P. Fern\u00e1ndez M. Malhotra A. Rose K. Rys M. Sim\u00e9on J. and Wadler P. 2006. XQuery 1.0 and XPath 2.0 formal semantics W3C recommendation. http:\/\/www.w3.org\/TR\/REC-xquery-semantics-20070123\/.  Draper D. Fankhauser P. Fern\u00e1ndez M. Malhotra A. Rose K. Rys M. Sim\u00e9on J. and Wadler P. 2006. XQuery 1.0 and XPath 2.0 formal semantics W3C recommendation. http:\/\/www.w3.org\/TR\/REC-xquery-semantics-20070123\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298557"},{"key":"e_1_2_1_14_1","unstructured":"Fern\u00e1ndez M. Malhotra A. Marsh J. Nagy M. and Walsh N. 2007. XQuery 1.0 and XPath 2.0 data model. W3C recommendation. http:\/\/www.w3.org\/TR\/2007\/REC-xpath-datamodel-20070123\/.  Fern\u00e1ndez M. Malhotra A. Marsh J. Nagy M. and Walsh N. 2007. XQuery 1.0 and XPath 2.0 data model. W3C recommendation. http:\/\/www.w3.org\/TR\/2007\/REC-xpath-datamodel-20070123\/."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11896548_17"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_26"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/IDEAS.2005.39"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841920_7"},{"volume-title":"Proceedings of the ACM Fall Joint Computer Conference. ACM","author":"Lanin V.","key":"e_1_2_1_19_1","unstructured":"Lanin , V. and Shasha , D . 1986. A symmetric concurrent b-tree algorithm . In Proceedings of the ACM Fall Joint Computer Conference. ACM , New York, 380--389. Lanin, V. and Shasha, D. 1986. A symmetric concurrent b-tree algorithm. In Proceedings of the ACM Fall Joint Computer Conference. ACM, New York, 380--389."},{"volume-title":"Design and implementation of a data manipulation processor for an XML query processor. Diplomarbeit","author":"Lehti P.","key":"e_1_2_1_20_1","unstructured":"Lehti , P. 2001. Design and implementation of a data manipulation processor for an XML query processor. Diplomarbeit , Technical University of Darmstadt , Darmstadt, Germany . Lehti, P. 2001. Design and implementation of a data manipulation processor for an XML query processor. Diplomarbeit, Technical University of Darmstadt, Darmstadt, Germany."},{"volume-title":"Proceedings of the 19th International Conference on Very Large Data Bases (VLDB '93)","author":"Levy A. Y.","key":"e_1_2_1_21_1","unstructured":"Levy , A. Y. and Sagiv , Y . 1993. Queries independent of updates . In Proceedings of the 19th International Conference on Very Large Data Bases (VLDB '93) . Morgan Kaufmann, 171--181. Levy, A. Y. and Sagiv, Y. 1993. Queries independent of updates. In Proceedings of the 19th International Conference on Very Large Data Bases (VLDB '93). Morgan Kaufmann, 171--181."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB '03)","author":"Marian A.","key":"e_1_2_1_22_1","unstructured":"Marian , A. and Sim\u00e9on , J . 2003. Projecting XML documents . In Proceedings of the International Conference on Very Large Data Bases (VLDB '03) , 213--224. Marian, A. and Sim\u00e9on, J. 2003. Projecting XML documents. In Proceedings of the International Conference on Very Large Data Bases (VLDB '03), 213--224."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375720"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2613"},{"key":"e_1_2_1_26_1","unstructured":"Wadler P. 1999. Two semantics of XPath. Discussion note for W3C XSLT Working Group. http:\/\/homepages.inf.ed.ac.uk\/wadler\/papers\/xpath-semantics\/.  Wadler P. 1999. Two semantics of XPath. Discussion note for W3C XSLT Working Group. http:\/\/homepages.inf.ed.ac.uk\/wadler\/papers\/xpath-semantics\/."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412341","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412331.1412341","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:51Z","timestamp":1750286931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412331.1412341"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["10.1145\/1412331.1412341"],"URL":"https:\/\/doi.org\/10.1145\/1412331.1412341","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2008,11]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}