Incremental XPath evaluation

ABSTRACT

We study the problem of incrementally maintaining an XPath query on an XML database under updates. The updates we consider are node insertion, node deletion, and node relabeling. Our main results are that downward XPath queries can be incrementally maintained in time O(depth(D) · poly(Q)) and conjunctive forward XPath queries in time O(depth(D)· log(width(D))·poly(Q)), where D is the size of the database, Q the size of the query, and depth(D) and width(D) are the nesting depth and maximum number of siblings in the database, respectively. The auxiliary data structures for maintenance are linear in D and polynomial in Q in all these cases.

REFERENCES

• 1: Andrey Balmin , Yannis Papakonstantinou , Victor Vianu, Incremental validation of XML documents, ACM Transactions on Database Systems (TODS), v.29 n.4, December 2004 [doi>10.1145/1042046.1042050]
• 2: Ziv Bar-Yossef , Marcus Fontoura , Vanja Josifovski, On the memory requirements of XPath evaluation over XML streams, Journal of Computer and System Sciences, v.73 n.3, p.391-441, May, 2007 [doi>10.1016/j.jcss.2006.10.002]
• 3: Denilson Barbosa , Alberto O. Mendelzon , Leonid Libkin , Laurent Mignet , Marcelo Arenas, Efficient Incremental Validation of XML Documents, Proceedings of the 20th International Conference on Data Engineering, p.671, March 30-April 02, 2004
• 4: Michael Benedikt , Christoph Koch, XPath leashed, ACM Computing Surveys (CSUR), v.41 n.1, p.1-54, December 2008 [doi>10.1145/1456650.1456653]
• 5: Mikolaj Bojańczyk , Pawel Parys, XPath evaluation in linear time, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376951]
• 6: Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems (TODS), v.30 n.2, p.444-491, June 2005 [doi>10.1145/1071610.1071614]
• 7: Georg Gottlob , Christoph Koch , Reinhard Pichler , Luc Segoufin, The complexity of XPath query evaluation and XML typing, Journal of the ACM (JACM), v.52 n.2, p.284-335, March 2005 [doi>10.1145/1059513.1059520]
• 8: M. Götz, C. Koch, and W. Martens. Efficient algorithms for the tree homeomorphism problem. In DBPL, pages 17--31, 2007.
• 9: Martin Grohe , Christoph Koch , Nicole Schweikardt, Tight lower bounds for query processing on streaming and external memory data, Theoretical Computer Science, v.380 n.1-2, p.199-217, July 2007 [doi>10.1016/j.tcs.2007.02.062]
• 10: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 11: Leonid Libkin , Cristina Sirangelo, Reasoning about XML with Temporal Logics and Automata, Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, November 22-27, 2008, Doha, Qatar [doi>10.1007/978-3-540-89439-1_7]
• 12: Hidetaka Matsumura , Keishi Tajima, Incremental evaluation of a monotone XPath fragment, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099609]
• 13: Patrick O'Neil , Elizabeth O'Neil , Shankar Pal , Istvan Cseri , Gideon Schaller , Nigel Westbury, ORDPATHs: insert-friendly XML node labels, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007686]
• 14: Makoto Onizuka , Fong Yee Chan , Ryusuke Michigami , Takashi Honishi, Incremental maintenance for materialized XPath/XSLT views, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060843]
• 15: Sushant Patnaik , Neil Immerman, Dyn-FO: a parallel, dynamic complexity class, Journal of Computer and System Sciences, v.55 n.2, p.199-209, Oct. 1997 [doi>10.1006/jcss.1997.1520]
• 16: Arsany Sawires , Junichi Tatemura , Oliver Po , Divyakant Agrawal , Amr El Abbadi , K. Selçuk Candan, Maintaining XPath views in loosely coupled systems, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 17: Arsany Sawires , Junichi Tatemura , Oliver Po , Divyakant Agrawal , K. SelÇuk Candan, Incremental maintenance of path-expression views, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066208]
• 18: Nicole Schweikardt, Machine models and lower bounds for query processing, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265537]
• 19: Thomas Schwentick, XPath query containment, ACM SIGMOD Record, v.33 n.1, March 2004 [doi>10.1145/974121.974140]
• 20: O. Shmueli and A. Itai. Incremental view maintenance. In SIGMOD, pages 240--255, 1984.
• 21: Balder ten Cate , Carsten Lutz, The complexity of query containment in expressive fragments of XPath 2.0, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265541]