Coupling Materialized View Selection to Multi Query Optimization: Hyper Graph Approach

Ahcene Boukorca, Ladjel Bellatreche, Sid-Ahmed Benali Senouci and Zoé Faget
Additional contact information
Ahcene Boukorca: LIAS/ISAE-ENSMA, Poitiers University, Poitiers, France
Ladjel Bellatreche: LIAS/ISAE-ENSMA, Poitiers University, Poitiers, France
Sid-Ahmed Benali Senouci: Mentors Graphics, Montbonnot-Saint-Martin, France
Zoé Faget: LIAS/ISAE-ENSMA, Poitiers University, Poitiers, France

International Journal of Data Warehousing and Mining (IJDWM), 2015, vol. 11, issue 2, 62-84

Abstract: Materialized views are queries whose results are stored and maintained in order to facilitate access to data in their underlying base tables of extremely large databases. Selecting the best materialized views for a given query workload is a hard problem. Studies on view selection have considered sharing common sub expressions and other multi-query optimization techniques. Multi-Query Optimization is a well-studied domain in traditional and advanced databases. It aims at optimizing a workload of queries by finding and reusing common sub-expression between queries. Finding the best shared expression is known as a NP-hard problem. The shared expressions usually identified by graph structure have been used to be candidate for materialized views. This shows the strong interdependency between the problems of materialized view selection (PVS) and multi query optimization (PMQO), since the PVS uses the graph structure of the PMQO. Exploring the existing works on PVS considering the interaction between PVS and PMQO figures two main categories of studies: (i) those considering the PMQO as a black box where the output is the graph and (ii) those preparing the graph to guide the materialized view selection process. In this category, the graph generation is based on individual query plans, an approach that does not scale, especially with the explosion of Big Data applications requiring large number of complex queries with high interaction. To ensure a scalable solution, this work proposes a new technique to generate a global processing plan without using individual plans by borrowing techniques used in the electronic design automation (EDA) domain. This paper first presents a rich state of art regarding the PVS and a classification of the most important existing work. Secondly, an analogy between the MQO problem and the EDA domain, in which large circuits are manipulated, is established. Thirdly, it proposes to model the problem with hypergraphs which are massively used to design and test integrated circuits. Fourthly, it proposes a deterministic algorithm to select materialized views using the global processing plan. Finally, experiments are conducted to show the scalability of our approach.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
https://services.igi-global.com/resolvedoi/resolve ... 018/ijdwm.2015040104 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jdwm00:v:11:y:2015:i:2:p:62-84

Access Statistics for this article

International Journal of Data Warehousing and Mining (IJDWM) is currently edited by Eric Pardede

More articles in International Journal of Data Warehousing and Mining (IJDWM) from IGI Global
Bibliographic data for series maintained by Journal Editor ().