{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T18:31:06Z","timestamp":1781893866498,"version":"3.54.5"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T00:00:00Z","timestamp":1286841600000},"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":[[2010,11]]},"abstract":"<jats:p>\n            Incremental view maintenance for XPath queries asks to maintain a materialized XPath view over an XML database. It assumes an underlying XML database\n            <jats:italic>D<\/jats:italic>\n            and a query\n            <jats:italic>Q<\/jats:italic>\n            . One is given a sequence of updates\n            <jats:italic>U<\/jats:italic>\n            to\n            <jats:italic>D<\/jats:italic>\n            , and the problem is to compute the result of\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>U<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            )): the result of evaluating query\n            <jats:italic>Q<\/jats:italic>\n            on database\n            <jats:italic>D<\/jats:italic>\n            after having applied updates\n            <jats:italic>U<\/jats:italic>\n            . This article initiates a systematic study of the Boolean version of this problem. In the Boolean version, one only wants to know whether\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>U<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            )) is empty or not.\n          <\/jats:p>\n          <jats:p>\n            In order to quickly answer this question, we are allowed to maintain an auxiliary data structure. The complexity of the maintenance algorithms is measured in, (1) the size of the auxiliary data structure, (2) the worst-case time per update needed to compute\n            <jats:italic>Q<\/jats:italic>\n            (\n            <jats:italic>U<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            )), and (3) the worst-case time per update needed to bring the auxiliary data structure up to date. We allow three kinds of updates: node insertion, node deletion, and node relabeling. Our main results are that downward XPath queries can be incrementally maintained in time O(depth(\n            <jats:italic>D<\/jats:italic>\n            )\u00b7poly(|\n            <jats:italic>Q<\/jats:italic>\n            |)) per update and conjunctive forward XPath queries in time O(depth(\n            <jats:italic>D<\/jats:italic>\n            ) \u00b7 log(width(\n            <jats:italic>D<\/jats:italic>\n            ))\u00b7poly(|\n            <jats:italic>Q<\/jats:italic>\n            |)) per update, where |\n            <jats:italic>Q<\/jats:italic>\n            | is the size of the query, and depth(\n            <jats:italic>D<\/jats:italic>\n            ) and width(\n            <jats:italic>D<\/jats:italic>\n            ) are the nesting depth and maximum number of siblings in database\n            <jats:italic>D<\/jats:italic>\n            , respectively. The auxiliary data structures for maintenance are linear in |\n            <jats:italic>D<\/jats:italic>\n            | and polynomial in |\n            <jats:italic>Q<\/jats:italic>\n            | in all these cases.\n          <\/jats:p>","DOI":"10.1145\/1862919.1862926","type":"journal-article","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T15:55:04Z","timestamp":1292860504000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Incremental XPath evaluation"],"prefix":"10.1145","volume":"35","author":[{"given":"Henrik","family":"Bj\u00f6rklund","sequence":"first","affiliation":[{"name":"Ume\u00e5 University, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wouter","family":"Gelade","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[{"name":"Technical University of Dortmund, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,10,12]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Abiteboul S. Bourhis P. and Marinoiu B. 2007. Incremental view maintenance for active documents. In Journ\u00e9es Bases de Donn\u00e9es Avanc\u00e9es (BDA).  Abiteboul S. Bourhis P. and Marinoiu B. 2007. Incremental view maintenance for active documents. In Journ\u00e9es Bases de Donn\u00e9es Avanc\u00e9es (BDA)."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516483"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1042046.1042050"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.002"},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). IEEE Computer Society, Washington DC, 671--682","author":"Barbosa D.","unstructured":"Barbosa , D. , Mendelzon , A. , Libkin , L. , Mignet , L. , and Arenas , M . 2004. Efficient incremental validation of XML documents . In Proceedings of the International Conference on Data Engineering (ICDE). IEEE Computer Society, Washington DC, 671--682 . Barbosa, D., Mendelzon, A., Libkin, L., Mignet, L., and Arenas, M. 2004. Efficient incremental validation of XML documents. In Proceedings of the International Conference on Data Engineering (ICDE). IEEE Computer Society, Washington DC, 671--682."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1456650.1456653"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514915"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376951"},{"key":"e_1_2_2_10_1","volume-title":"XML Path Language (XPath) version 1.0. Tech. rep","author":"Clark J.","unstructured":"Clark , J. and DeRose , S. 1999. XML Path Language (XPath) version 1.0. Tech. rep ., World Wide Web Consortium . http:\/\/www.w3.org\/TR\/xpath\/. Clark, J. and DeRose, S. 1999. XML Path Language (XPath) version 1.0. Tech. rep., World Wide Web Consortium. http:\/\/www.w3.org\/TR\/xpath\/."},{"key":"e_1_2_2_11_1","first-page":"46","article-title":"Maintaining transitive closure of graphs in SQL","volume":"5","author":"Dong G.","year":"1999","unstructured":"Dong , G. , Libkin , L. , Su , J. , and Wong , L. 1999 . Maintaining transitive closure of graphs in SQL . Int. J. Inform. Technol. 5 , 1, 46 -- 78 . Dong, G., Libkin, L., Su, J., and Wong, L. 1999. Maintaining transitive closure of graphs in SQL. Int. J. Inform. Technol. 5, 1, 46--78.","journal-title":"Int. J. Inform. Technol."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00017-8"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/344788.344808"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530820"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Germany, 481--492","author":"Gelade W.","unstructured":"Gelade , W. , Marquardt , M. , and Schwentick , T . 2009. The dynamic complexity of formal languages . In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Germany, 481--492 . Gelade, W., Marquardt, M., and Schwentick, T. 2009. The dynamic complexity of formal languages. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Germany, 481--492."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00095-6"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071614"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059520"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2009.03.010"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223849"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.062"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322295"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89439-1_7"},{"key":"e_1_2_2_26_1","volume-title":"Proceedings of the International Symposium on Database Programming Languages (DBPL)","author":"Libkin L.","unstructured":"Libkin , L. and Wong , L . 1997. Incremental recomputation of recursive queries with nested sets and aggregate functions . In Proceedings of the International Symposium on Database Programming Languages (DBPL) . Springer, Germany, 222--238. Libkin, L. and Wong, L. 1997. Incremental recomputation of recursive queries with nested sets and aggregate functions. In Proceedings of the International Symposium on Database Programming Languages (DBPL). Springer, Germany, 222--238."},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the International Database Engineering and Applications Symposium (IDEAS). 197--205","author":"Liu J.","unstructured":"Liu , J. , Vincent , M. , and Mohania , M . 1999. Incremental maintenance of nested relational views . In Proceedings of the International Database Engineering and Applications Symposium (IDEAS). 197--205 . Liu, J., Vincent, M., and Mohania, M. 1999. Incremental maintenance of nested relational views. In Proceedings of the International Database Engineering and Applications Symposium (IDEAS). 197--205."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.035"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099609"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962448"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007686"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060843"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1093382.1093384"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559805"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1520"},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM Press","author":"Sawires A.","unstructured":"Sawires , A. , Tatemura , J. , Po , O. , Agrawal , D. , Abbadi , A. E. , and Candan , K. S . 2006. Maintaining XPath views in loosely coupled systems . In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM Press , New York, 583--594. Sawires, A., Tatemura, J., Po, O., Agrawal, D., Abbadi, A. E., and Candan, K. S. 2006. Maintaining XPath views in loosely coupled systems. In Proceedings of the International Conference on Very Large Data Bases (VLDB). ACM Press, New York, 583--594."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066208"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265537"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/974121.974140"},{"key":"e_1_2_2_42_1","volume-title":"Proceedings of the International Symposium on Management of Data (SIGMOD). ACM Press","author":"Shmueli O.","unstructured":"Shmueli , O. and Itai , A . 1984. Incremental view maintenance . In Proceedings of the International Symposium on Management of Data (SIGMOD). ACM Press , New York, 240--255. Shmueli, O. and Itai, A. 1984. Incremental view maintenance. In Proceedings of the International Symposium on Management of Data (SIGMOD). ACM Press, New York, 240--255."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90047-L"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568321"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/646252.685998"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862919.1862926","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1862919.1862926","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:14:51Z","timestamp":1750281291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862919.1862926"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,12]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.1145\/1862919.1862926"],"URL":"https:\/\/doi.org\/10.1145\/1862919.1862926","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,12]]},"assertion":[{"value":"2009-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}