Optimizing XML queries: Bitmapped materialized views vs. indexes

Xiaoying Wu, Dimitri Theodoratos, Wendy Hui Wang, Timos Sellis

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

Optimizing queries using materialized views has not been addressed adequately in the context of XML due to the many limitations associated with the definition and usability of materialized views in traditional XML query evaluation models. In this paper, we address the XML query optimization problem using materialized views in the framework of the inverted lists evaluation model which has been established as the most prominent one for evaluating queries on large persistent XML data. Under this framework, we propose a novel approach which instead of materializing the answer of a view materializes exactly the sublists of the inverted lists that are necessary for computing the answer of the view. A further originality of our approach is that the view materializations are stored as compressed bitmaps. This technique not only minimizes the materialization space but also reduces CPU and I/O costs by translating view materialization processing into bitwise operations. Our approach departs from the traditional approach which identifies a compensating expression that rewrites the query using the materialized views. Instead, it computes the query answer by executing holistic stack-based algorithms on the view materializations. We experimentally compared our approach with recent outstanding structural summary and B-tree based approaches. In order to make the comparison more competitive we also proposed an extension of a structural index approach to resolve combinatorial explosion problems. Our experimental results show that our compressed bitmapped materialized views approach is the most efficient, robust, and stable one for optimizing XML queries. It obtains significant performance savings at a very small space overhead and has negligible optimization time even for a large number of materialized views in the view pool.

Original languageEnglish (US)
Pages (from-to)863-884
Number of pages22
JournalInformation Systems
Volume38
Issue number6
DOIs
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture

Keywords

  • Bitmap materialized views
  • Optimization of tree-pattern queries
  • XML
  • XPath query evaluation
  • using views

Fingerprint

Dive into the research topics of 'Optimizing XML queries: Bitmapped materialized views vs. indexes'. Together they form a unique fingerprint.

Cite this