XPath evaluation in linear time with polynomial combined complexity

ABSTRACT

We consider a fragment of XPath 1.0, where attribute and text values may be compared. We show that for any unary query in this fragment, the set of nodes that satisfy the query can be calculated in time linear in the document size and polynomial in the size of the query. The previous algorithm for this fragment also had linear data complexity but exponential complexity in the query size.

REFERENCES

• 1: Michael A. Bender , Martin Farach-Colton, The LCA Problem Revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.88-94, April 10-14, 2000
• 2: Michael Benedikt , Christoph Koch, XPath leashed, ACM Computing Surveys (CSUR), v.41 n.1, p.1-54, December 2008 [doi>10.1145/1456650.1456653]
• 3: 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]
• 4: J. Clark and S. DeRose. XML Path language (XPath) version 1.0, W3C recommendation. Technical report, W3C, 1999.
• 5: G. Gottlob, C. Koch, and R. Pichler. XPath query evaluation: Improving time and space eficiency. In ICDE'03, pages 379--390, 2003.
• 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: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 8: J. Kärkkäinen and P. Sanders. Simple linear work suffix array construction. In International Conference on Automata, Languages and Programming, volume 2719 of Lecture Notes in Computer Science, pages 943--955, 2003.
• 9: Frank Neven, Automata theory for XML researchers, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601869]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages, Theory

Keywords:
tree with data, xml, xpath