Incremental processing of twig queries

Abstract

Queries on XML databases are typically expressed as twig patterns. The query processing problem then reduces to finding all occurrences of these twig patterns in an XML database. Traditionally, these queries have been executed using techniques such as structural joins and holistic twig joins. We, in this thesis propose and implement a novel methodology for answering twig pattern queries using pre-computations of solutions in lieu of re-execution of frequent queries against a dynamic XML database. Upon updates, the incremental maintenance of pre-computations reuses the information that already exists without having to re-compute the pre-computations against the entire document.We present here two such pre-computation algorithms that can be used to determine the existence of a query pattern and the number of matches in an XML database. We also present the complexity analysis and experimental results illustrating the efficiency of these two algorithms.