Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach Christoph Koch   View Paper (PDF)   Return to XML Query Processing III (Session A7) Abstract We propose a new, highly scalable and effi- cient technique for evaluating node-selecting queries on XML trees which is based on re- cent advances in the theory of tree automata. Our query processing techniques require only two linear passes over the XML data on disk, and their main memory requirements are in principle independent of the size of the data. The overall running time is O(m + n), where m only depends on the query and n is the size of the data. The query language supported is very expressive and captures exactly all node-selecting queries answerable with only a bounded amount of memory (thus, all queries that can be answered by any form of finite- state system on XML trees). Visiting each tree node only twice is optimal, and current automata-based approaches to answering path queries on XML streams, which work using one linear scan of the stream, are consider- ably less expressive. These technical results - which give rise to expressive query engines that deal more ef- ciently with large amounts of data in sec- ondary storage - are complemented with an experimental evaluation of our work. ©2004 Association for Computing Machinery