S3: Processing tree-pattern XML queries with all logical operators

摘要

XML is a tree-based data representation format which combines data and structure. Therefore, XML queries not only contain predicates to filter data but also refer to relationships between document elements searched. The existing elements in an XML query are connected to each other using a tree-pattern structure, called Query Tree Pattern (QTP). Finding elements of a document, which satisfy the given QTP, is the main task during query execution. To optimize this processing, we presented two methods in [13]. Instead of directly executing the QTP against the document, our methods first evaluate a guidance structure, called QueryGuide. Using the extracted information, called match pattern, we provided a focused document access and minimized the required I/O. However, we only supported the logical operator AND (called AND-QTPs).In this paper, we use a new structure, called Evaluation Tree, to execute QTPs. We also extend our method to support QTPs having logical operators OR, XOR, and NOT. Parsing QTPs into some AND-QTPs is typically assumed non-efficient. To process QTPs having logical operators OR and NOT, we therefore parse them but we use an efficient method to prevent redundant I/O and QTP matching. This is done by optimizing the selection of match patterns which were derived from the QueryGuide during QTP parsing. As a result, QTP execution is not inefficient anymore.