An Automata-Theoretic Approach to Regular XPath

Proc. of the 12th Int. Symposium on Database Programming Languages (DBPL 2009). Volume 5708 of Lecture Notes in Computer Science. 2009.

In this paper we present Regular XPath (RXPath), which is a natural extension of XPath with regular expressions over paths that has the same computational properties as XPath: linear-time query evaluation and exponential-time reasoning. To establish these results, we devise a unifying automata-theoretic framework based on two-way weak alternating tree automata. Specifically, we consider automata that have infinite runs on finite trees. This enables us to leverage and simplify existing automata-theoretic machinery and develop algorithms both for query evaluation and for reasoning over queries. With respect to the latter problem, we consider RXPath as a constraint language, and study constraint satisfiability, and query satisfiability and containment under constraints in the setting of RXPath.

@inproceedings{DBPL-2009,
   title = "An Automata-Theoretic Approach to Regular XPath",
   year = "2009",
   author = "Diego Calvanese and De Giacomo, Giuseppe and Maurizio
Lenzerini and Moshe Y. Vardi",
   booktitle = "Proc. of the 12th Int. Symposium on Database Programming
Languages (DBPL 2009)",
   pages = "18--35",
   volume = "5708",
   publisher = "Springer",
   series = "Lecture Notes in Computer Science",
   doi = "10.1007/978-3-642-03793-1_2",
}