{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:22:53Z","timestamp":1773886973135,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2004,12,12]],"date-time":"2004-12-12T00:00:00Z","timestamp":1102809600000},"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":[[2004,12,12]]},"abstract":"<jats:p>\n            We investigate the incremental validation of XML documents with respect to DTDs, specialized DTDs, and XML Schemas, under updates consisting of element tag renamings, insertions, and deletions. DTDs are modeled as extended context-free grammars. \"Specialized DTDs\" allow the decoupling of element types from element tags. XML Schemas are abstracted as specialized DTDs with limitations on the type assignment. For DTDs and XML Schemas, we exhibit an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) incremental validation algorithm using an auxiliary structure of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the size of the document and\n            <jats:italic>m<\/jats:italic>\n            the number of updates. The algorithm does not handle the incremental validation of XML Schema wrt renaming of internal nodes, which is handled by the specialized DTDs incremental validation algorithm. For specialized DTDs, we provide an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) incremental algorithm, again using an auxiliary structure of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ). This is a significant improvement over brute-force re-validation from scratch.We exhibit a restricted class of DTDs called\n            <jats:italic>local<\/jats:italic>\n            that arise commonly in practice and for which incremental validation can be done in practically constant time by maintaining only a list of counters. We present implementations of both general incremental validation and local validation on an XML database built on top of a relational database.Our experimentation includes a study of the applicability of local validation in practice, results on the calibration of parameters of the auxiliary data structure, and results on the performance comparison between the general incremental validation technique, the local validation technique, and brute-force validation from scratch.\n          <\/jats:p>","DOI":"10.1145\/1042046.1042050","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"710-751","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":65,"title":["Incremental validation of XML documents"],"prefix":"10.1145","volume":"29","author":[{"given":"Andrey","family":"Balmin","sequence":"first","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}]},{"given":"Yannis","family":"Papakonstantinou","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, CA"}]},{"given":"Victor","family":"Vianu","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, CA"}]}],"member":"320","published-online":{"date-parts":[[2004,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0113-1"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 20th International Conference on Data Engineering (ICDE'04)","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 20th International Conference on Data Engineering (ICDE'04) . IEEE Computer Society Press, Los Alamitos, CA. Barbosa, D., Mendelzon, A., Libkin, L., Mignet, L., and Arenas, M. 2004. Efficient incremental validation of xml documents. In Proceedings of the 20th International Conference on Data Engineering (ICDE'04). IEEE Computer Society Press, Los Alamitos, CA."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 7th International Conference on Database Theory. Lecture Notes in Computer Science","volume":"1540","author":"Beeri C.","unstructured":"Beeri , C. and Milo , T . 1999. Schemas for integration and translation of structured and semi-structured data . In Proceedings of the 7th International Conference on Database Theory. Lecture Notes in Computer Science , vol. 1540 . Springer, New York, NY. Beeri, C. and Milo, T. 1999. Schemas for integration and translation of structured and semi-structured data. In Proceedings of the 7th International Conference on Database Theory. Lecture Notes in Computer Science, vol. 1540. Springer, New York, NY."},{"key":"e_1_2_1_4_1","unstructured":"Bruggemann-Klein A. Murata M. and Wood D. 2001. Regular tree and regular hedge languages over non-ranked alphabets. Tech. rep. HKUST-TCSC-2001-05. Hong Kong University of Science and Technology Computer Science Center Hong Kong. Available online at http:\/\/www.cs.ust.hk\/tcsc\/RR\/2001-05.ps.gz.  Bruggemann-Klein A. Murata M. and Wood D. 2001. Regular tree and regular hedge languages over non-ranked alphabets. Tech. rep. HKUST-TCSC-2001-05. Hong Kong University of Science and Technology Computer Science Center Hong Kong. Available online at http:\/\/www.cs.ust.hk\/tcsc\/RR\/2001-05.ps.gz."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2695"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Fifth International Workshop on the Web and Databases, WebDB. Informal proceedings, 43--48","author":"Choi B.","year":"2002","unstructured":"Choi , B. 2002 . What are real DTDs like? In Proceedings of the Fifth International Workshop on the Web and Databases, WebDB. Informal proceedings, 43--48 . Choi, B. 2002. What are real DTDs like? In Proceedings of the Fifth International Workshop on the Web and Databases, WebDB. Informal proceedings, 43--48."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Cluet S. Delobel C. Simeon J. and Smaga K. 1998. Your mediators need data conversion! In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. ACM Press New York NY 177--188.   Cluet S. Delobel C. Simeon J. and Smaga K. 1998. Your mediators need data conversion! In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. ACM Press New York NY 177--188.","DOI":"10.1145\/276305.276321"},{"key":"e_1_2_1_8_1","unstructured":"Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220204"},{"key":"e_1_2_1_10_1","volume-title":"Database Systems: The Complete Book","author":"Garcia-Molina H.","year":"2001","unstructured":"Garcia-Molina , H. , Ullman , J. , and Widom , J . 2001 . Database Systems: The Complete Book . Prentice Hall , Upper Saddle River, NJ. Garcia-Molina, H., Ullman, J., and Widom, J. 2001. Database Systems: The Complete Book. Prentice Hall, Upper Saddle River, NJ."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/322203.322215"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2002.1029839"},{"key":"e_1_2_1_13_1","unstructured":"Ipedo. Ipedo XML Database: Technical overview. Available online at http:\/\/www.ipedo.com\/downloads\/products_ixd_technical_overview.pdf.  Ipedo. Ipedo XML Database: Technical overview. Available online at http:\/\/www.ipedo.com\/downloads\/products_ixd_technical_overview.pdf."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/582153.582175"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/200994.200996"},{"key":"e_1_2_1_16_1","unstructured":"Levine C. 1997. Standard benchmarks for database systems. Presented at Sigmod 97. Available online at http:\/\/www.tpc.org\/information\/sessions\/sigmod\/indexc.htm.  Levine C. 1997. Standard benchmarks for database systems. Presented at Sigmod 97. Available online at http:\/\/www.tpc.org\/information\/sessions\/sigmod\/indexc.htm."},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 22nd Seminar on Current Trends in Theory and Practice of Informatics(SOFSEM '95)","author":"Li W.","unstructured":"Li , W. 1995. A simple and efficient incremental LL(1) parsing . In Proceedings of the 22nd Seminar on Current Trends in Theory and Practice of Informatics(SOFSEM '95) . Lecture Notes in Computer Science , vol. 1012 . Springer , New York, NY . Li, W. 1995. A simple and efficient incremental LL(1) parsing. In Proceedings of the 22nd Seminar on Current Trends in Theory and Practice of Informatics(SOFSEM '95). Lecture Notes in Computer Science, vol. 1012. Springer, New York, NY."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/647200.718725"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90159-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-0551(90)90020-P"},{"key":"e_1_2_1_22_1","volume-title":"16th International Workshop (CSL","volume":"2471","author":"Neven F.","year":"2002","unstructured":"Neven , F. 2002 . Automata, logic and XML. In Computer Science Logic , 16th International Workshop (CSL 2002). Lecture Notes in Computer Science , vol. 2471 . Springer, New York, NY. Available online at http:\/\/alpha.luc.ac.be\/lucg5503\/publs.html. Neven, F. 2002. Automata, logic and XML. In Computer Science Logic, 16th International Workshop (CSL 2002). Lecture Notes in Computer Science, vol. 2471. Springer, New York, NY. Available online at http:\/\/alpha.luc.ac.be\/lucg5503\/publs.html."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335173"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1520"},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Computer Science","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"Petrone L.","unstructured":"Petrone , L. 1995. Reusing batch parsers as incremental parsers . In Foundations of Software Technology and Theoretical Computer Science . Lecture Notes in Computer Science , vol. 1026 . Springer , New York, NY . Petrone, L. 1995. Reusing batch parsers as incremental parsers. In Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1026. Springer, New York, NY."},{"key":"e_1_2_1_26_1","unstructured":"RELAX NG. Available online at http:\/\/www.relaxng.org.  RELAX NG. Available online at http:\/\/www.relaxng.org."},{"key":"e_1_2_1_27_1","unstructured":"Segoufin L. 2002. Personal communication.  Segoufin L. 2002. Personal communication."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases (VLDB'99)","author":"Shanmugasundaram J.","unstructured":"Shanmugasundaram , J. , Tufte , K. , Zhang , C. , He , G. , DeWitt , D. J. , and Naughton , J. F . 1999. Relational databases for querying XML documents: Limitations and opportunities . In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB'99) , Edinburgh, Scotland, UK. Morgan Kaufmann, San Francisco, CA, 302--314. Shanmugasundaram, J., Tufte, K., Zhang, C., He, G., DeWitt, D. J., and Naughton, J. F. 1999. Relational databases for querying XML documents: Limitations and opportunities. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB'99), Edinburgh, Scotland, UK. Morgan Kaufmann, San Francisco, CA, 302--314."},{"key":"e_1_2_1_29_1","volume-title":"International Workshop on Programming Language Technologies for XML (PLAN-X 2004). Informal proceedings.","author":"Sur G.","unstructured":"Sur , G. , Hammer , J. , and Simeon , J . 2004. UpdateX---an XQuery-based language for processing updates in XML . In International Workshop on Programming Language Technologies for XML (PLAN-X 2004). Informal proceedings. Sur, G., Hammer, J., and Simeon, J. 2004. UpdateX---an XQuery-based language for processing updates in XML. In International Workshop on Programming Language Technologies for XML (PLAN-X 2004). Informal proceedings."},{"key":"e_1_2_1_30_1","volume-title":"Updating XML. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press","author":"Tatarinov I.","unstructured":"Tatarinov , I. , Ives , Z. , Halevy , A. , and Weld , D . 2001 . Updating XML. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press , New York, NY. Tatarinov, I., Ives, Z., Halevy, A., and Weld, D. 2001. Updating XML. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press, New York, NY."},{"key":"e_1_2_1_31_1","unstructured":"TPC-C. Benchmark. Available online at http:\/\/www.tpc.org\/tpcc\/.  TPC-C. Benchmark. Available online at http:\/\/www.tpc.org\/tpcc\/."},{"key":"e_1_2_1_32_1","volume-title":"Introduction to Circuit Complexity","author":"Vollmer H.","unstructured":"Vollmer , H. 1999. Introduction to Circuit Complexity . Springer Verlag , New York, NY . Vollmer, H. 1999. Introduction to Circuit Complexity. Springer Verlag, New York, NY."},{"key":"e_1_2_1_33_1","unstructured":"W3C. 1998. The extensible markup language (XML). W3C Recomendation. Available online at http:\/\/www.w3c.org\/XML.  W3C. 1998. The extensible markup language (XML). W3C Recomendation. Available online at http:\/\/www.w3c.org\/XML."},{"key":"e_1_2_1_34_1","unstructured":"W3C. 2001. XML schema definition. W3C Recomendation. Available online at http:\/\/www. w3c.org\/XML\/Schema.  W3C. 2001. XML schema definition. W3C Recomendation. Available online at http:\/\/www. w3c.org\/XML\/Schema."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/293677.293678"},{"key":"e_1_2_1_36_1","unstructured":"Well. WellLogML DTD. Available online at http:\/\/www.posc.org\/ebiz\/WellLogML\/.  Well. WellLogML DTD. Available online at http:\/\/www.posc.org\/ebiz\/WellLogML\/."},{"key":"e_1_2_1_37_1","unstructured":"XML Edt. XML editor products. Available online at http:\/\/www.perfectxml.com\/soft.asp?cat=6.  XML Edt. XML editor products. Available online at http:\/\/www.perfectxml.com\/soft.asp?cat=6."},{"key":"e_1_2_1_38_1","unstructured":"XMLmind. XMLmind XML Editor. Available online at http:\/\/www.xmlmind.com\/xmleditor\/.  XMLmind. XMLmind XML Editor. Available online at http:\/\/www.xmlmind.com\/xmleditor\/."},{"key":"e_1_2_1_39_1","unstructured":"XMLspy document editor. Available online at http:\/\/www.xmlspy.com\/products_doc.html.  XMLspy document editor. Available online at http:\/\/www.xmlspy.com\/products_doc.html."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1042046.1042050","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1042046.1042050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:15Z","timestamp":1750286595000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1042046.1042050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,12,12]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,12,12]]}},"alternative-id":["10.1145\/1042046.1042050"],"URL":"https:\/\/doi.org\/10.1145\/1042046.1042050","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,12,12]]},"assertion":[{"value":"2004-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}