B. ten Cate
- XPath, transitive closure logic, and nested tree walking automata
- 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (SIGMOD/PODS 2008), Vancouver, Canada
- Book/source title
- PODS’08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
- Pages (from-to)
- Vancouver: ACM
- Document type
- Conference contribution
- Faculty of Science (FNWI)
- Informatics Institute (IVI)
We consider the navigational core of XPath, extended with two operators: the Kleene star for taking the transitive closure of path expressions, and a subtree relativisation operator, allowing one to restrict attention to a specific subtree while evaluating a subexpression. We show that the expressive power of this XPath dialect equals that of FO(MTC), first order logic extended with monadic transitive closure. We also give a characterization in terms of nested tree-walking automata. Using the latter we then proceed to show that the language is strictly less expressive than MSO. This solves an open question about the relative expressive power of FO(MTC) and MSO on trees. We also investigate the complexity for our XPath dialect. We show that query evaluation be done in polynomial time (combined complexity), but that satisfiability and query containment (as well as emptiness for our automaton model) are 2ExpTime-complete (it is ExpTime-complete for Core XPath).
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.