Constructing search spaces for materialized view selection

Research output: Contribution to conferencePaperpeer-review

30 Scopus citations


Deciding which views to materialize is an important problem in the design of a Data Warehouse. Solving this problem requires generating a space of candidate view sets from which an optimal or near-optimal one is chosen for materialization. In this paper we address the problem of constructing this search space. This is an intricate issue because it requires detecting and exploiting common subexpressions among queries and views. Our approach suggests adding to the alternative evaluation plans of multiple queries views called closest common derivators (CCDs) and rewriting the queries using CCDs. A CCD of two queries is a view that is as close to the queries as possible and that allows both queries to be (partially or completely) rewritten using itself. CCDs generalize previous definitions of common subexpressions. Using a declarative query graph representation for queries we provide necessary and sufficient conditions for a view to be a CCD of two queries. We exploit these results to describe a procedure for generating all the CCDs of two queries and for rewriting the queries using each of their CCDs.

Original languageEnglish (US)
Number of pages10
StatePublished - 2004
Externally publishedYes
EventDOLAP 2004: Proceedings of the Seventh ACM International Workshop on Data Warehousing and OLAP - Washington, DC, United States
Duration: Nov 12 2004Nov 13 2004


OtherDOLAP 2004: Proceedings of the Seventh ACM International Workshop on Data Warehousing and OLAP
Country/TerritoryUnited States
CityWashington, DC

All Science Journal Classification (ASJC) codes

  • General Engineering


  • Common subexpression
  • Materialized view
  • Query
  • Query graph
  • Query rewriting


Dive into the research topics of 'Constructing search spaces for materialized view selection'. Together they form a unique fingerprint.

Cite this