Schema-based semantic query optimization for XML queries

Abstract

Semantic query optimization is an approach to optimizing a query with respect to some semantic information such as structural information and integrity constraints. This thesis presents new schema-based semantic query optimization techniques, which rely on available structural information, for XML queries. The techniques described in the thesis resolve several open problems in the field of schema-based query optimization for XML queries.

First, we present a new technique called the two-phase query pruning that consists of the preprocessing phase and the pruning phase. Our two-phase query pruning is effective in optimizing multiple regular path expressions, and is more scalable and efficient than the combination of the previous query pruning and post-processing in that it never deals with exponentially many combinations of sub-results produced from all the regular path expressions. Several experiments we conducted show that the two-phase query pruning outperforms the previous approach.

Second, another new technique called structural function inlining is presented. Based on the technique, we develop a new approach to optimizing and typing structurally recursive queries. The approach produces an optimal algebraic expression for a query with regard to available type information. Furthermore, it yields a precise result type for the query. Our experiments show that the number of node lookups by our approach is on the average 3.7 times and up to 279.8 times smaller than that by the current approach in evaluating structurally recursive queries.