Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

Datenbanksysteme für Business, Technologie und Web (BTW) P-180, 207-226 (2011).

Gesellschaft für Informatik, Bonn

Copyright © Gesellschaft für Informatik, Bonn


Advanced cardinality estimation in the XML query graph model

Andreas M. Weiner (Technische Universität Kaiserslautern)


Reliable cardinality estimation is one of the key prerequisites for effective cost-based query optimization in database systems. The XML Query Graph Model (XQGM) is a tuple-based XQuery algebra that can be used to represent XQuery expressions in native XML database management systems. This paper enhances previous works on reliable cardinality estimation for XQuery and introduces several inference rules that deal with the unique features of XQGM, such as native support for Structural Joins, nesting, and multi-way merging. These rules allow to estimate the runtime cardinalities of XQGM operators. Using this approach, we can support classical join reordering with appropriate statistical information, perform cost-based query unnesting, and help to find the best evaluation strategy for value-based joins. The effectiveness of our approach for query optimization is evaluated using the query optimizer of XTC.

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-274-1

Last changed 24.02.2014 18:54:53