Template-Based Bitmap View Selection for Optimizing Queries over Tree Data

Xiaoying Wu, Dimitri Theodoratos

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Developing and exploiting flexible techniques for optimizing the evaluation of queries over loosely structured data (e.g. tree or graph databases) is of crucial importance for modern database applications. In this context, we consider a new type of views which can be materialized as compressed bitmaps over tree data. We introduce the concept of view structural template to define classes of views. We then define and address a novel view selection problem (called view class selection (VCS) problem) where the goal is to select classes of bitmap views in order to optimize the overall evaluation cost of all tree pattern queries (TPQs) that can be issued against a database while satisfying a space constraint and ensuring that all the TPQs can be answered using exclusively the materialized views. We show that the VCS problem is NP-hard and we design two heuristic greedy algorithms which iteratively generate new batches of candidate view classes and make them available for selection. Each algorithm uses a different view class expansion technique to enable the systematic generation of candidate view classes from classes with smaller templates. We run extensive experiments to evaluate both the effectiveness of the algorithms and their efficiency on real, benchmark and synthetic datasets. Our algorithms are able to suggest high quality selections of view classes in a reasonable amount of time.

Original languageEnglish (US)
Article number1650005
JournalInternational Journal of Cooperative Information Systems
Volume25
Issue number3
DOIs
StatePublished - Sep 1 2016

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications

Keywords

  • Tree pattern query optimization
  • bitmap materialized views
  • query templates
  • tree data
  • view selection

Fingerprint

Dive into the research topics of 'Template-Based Bitmap View Selection for Optimizing Queries over Tree Data'. Together they form a unique fingerprint.

Cite this