XML Query optimization

Abstract

XML has been widely used for data exchange as well as for representing and manipulating semi-structured data. To efficiently process XML queries becomes increasingly important and has received significant research attention lately. This thesis focuses on the optimization of XML queries with respect to a large fragment of XML queries known as tree pattern queries (TPQs). It focuses on two important optimization aspects: query minimization and query answering using views. For query minimization, prior work has focused on minimizing TPQs corresponding to the XPath semantics, with or without constraints. We present a study on the minimization of TPQs with a richer class of constraints. In this thesis, we also present a study on the minimization of Generalized TPQs (GTPQs), which correspond to a large fragment of queries expressible using XQuery with or without constraints. Our work is the first to study the minimization of GTPQs in the presence of constraints. For query answering using views, prior work on XML query processing with views has focused predominantly on query rewriting, which is a logical optimization issue. This thesis presents a study on an important physical optimization issue of how to efficiently evaluate TPQs using materialized views. We have proposed novel approaches to the above problems. Our experimental studies demonstrate the efficiency and effectiveness of these approaches.