ISBN 978-3-8439-0071-3

978-3-8439-0071-3, Reihe Informatik

Andreas M. Weiner
Cost-Based XQuery Optimization in Native XML Database Systems

245 Seiten, Dissertation Technische Universität Kaiserslautern (2011), Softcover, A5

Zusammenfassung / Abstract

Over the past three decades, the history of query processing in database management systems has shown that cost-based query optimization is an effective approach for finding sufficient low-level evaluation strategies for queries written in high-level declarative query languages like SQL.

In recent years, the eXtensible Markup Language (XML) has been established as the de-facto standard for exchanging semi-structured data between individuals, business partners, and various organizations. Today's native XML database management systems (XDBMSs) provide a stable infrastructure for efficiently storing, indexing, and querying small-to-large XML documents.

In 2007, the W3C introduced XQuery as a semi-declarative programming language that is now considered to be the language of choice to query XML documents.

Nowadays, in an XDBMS, we can dispose of a potpourri of various join operators (structural joins and value-based joins) and a still growing set of indexes as low-level building blocks for query processing. For the evaluation of an XQuery expression in an XDBMS, numerous semantically equivalent combinations of these operations are possible. Choosing the most efficient one out of a tremendously large set of combinations is crucial for effective query processing in throughput-oriented systems. To achieve this goal, the cost of each building block is modeled as the sum of IO cost and CPU cost. Using these formulae, a query optimizer can choose the cheapest one out of several alternative building blocks and, finally, combine them in an optimal way.

In this thesis, we assess how and whether concepts and techniques of relational cost-based query optimization can be reused in the context of XDBMSs to optimize XQuery expressions. Furthermore, we show which new techniques make cost-based optimization even more effective in such systems.