XPath Whole Query Optimization
Preprint
Abstract
Previous work reports about SXSI, a fast XPath engine which executes tree automata over compressed XML indexes. Here, reasons are investigated why SXSI is so fast. It is shown that tree automata can be used as a general framework for fine grained XML query optimization. We define the "relevant nodes" of a query as those nodes that a minimal automaton must touch in order to answer the query. This notion allows to skip many subtrees during execution, and, with the help of particular tree indexes, even allows to skip internal nodes of the tree. We efficiently approximate runs over relevant nodes by means of on-the-fly removal of alternation and non-determinism of (alternating) tree automata. We also introduce many implementation techniques which allows us to efficiently evaluate tree automata, even in the absence of special indexes. Through extensive experiments, we demonstrate the impact of the different optimization techniques.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Efficient XPath query processing2008
- The complexity of XPath query evaluation and XML typingJournal of the ACM, 2005
- N-Ary Queries by Tree AutomataLecture Notes in Computer Science, 2005
- Processing XML streams with deterministic automata and stream indexesACM Transactions on Database Systems, 2004
- Compiling regular patternsACM SIGPLAN Notices, 2003
- Query automata over finite treesTheoretical Computer Science, 2002
- Efficient Algorithms for Processing XPath Queries2002
- Locating Matches of Tree Patterns in Forests1998
- Fast text searching for regular expressions or automaton searching on triesJournal of the ACM, 1996
- Attribute grammar paradigms—a high-level methodology in language implementationACM Computing Surveys, 1995