Introduction I. Context

The success stories of the database technology keep companies continuously demanding more and more ecient services (such as data storage, query processing/optimization, security, transaction processing, recovery management, etc.) to deal with dimensions that Big Data brought.

They include: large volumes of high velocity, complex and variable data that require advanced techniques and technologies to enable the capture, storage, distribution and management analysis of the information. These dimensions have been rapidly advocated by the database community, where several thematic conferences and products have been launched. We would like to draw attention to another dimension, which in our opinion, does not get the same buzz as the traditional dimensions. It concerns the sharing in the world of database. The sharing may concern several database entities: data, resource, and queries.

From data perspective nowadays, large amounts of data are continuously generated in many domains like Life Science Research, Natural Resource Exploration, Natural Catastrophe Prevention, Trac Flow Optimization, Social Networks, Business Competition, etc. These data need to be collected, stored and analyzed in order to be well exploited by organization's managers and researchers to perform day-to-day company's tasks such as: (i) decisions making, (ii) generation of added-value to be more competitive and (iii) sharing the whole or fragments of their data stored in storage systems with other users and communities. Recently, large and small companies and organizations raise demands for more data sharing. Usually these data are stored in DBMSs. For instance, the Competition and Markets Authority (CMA) has ordered Britain's high street banks to adopt opening banking principles to increase data-sharing between nancial service organisations 1 . In other disciplines such as behavioral Science, the 1 http://www.experian.co.uk/blogs/latest-thinking/a-new-era-of-data-sharing-how-the-cma-is-shaking-up-retail-banking/ 3 CHAPTER 1. INTRODUCTION data sharing contributes in facilitating the reproduction of computational research [START_REF] De La Sablonnière | Facilitating data sharing in the behavioural sciences[END_REF]. The need of data sharing pushes several countries (such as Australia, Ireland, etc.) to legislate the usage sharing policy (for privacy issues) in several sectors including government sector 2 .

From computation resources and storage systems perspective, database storage systems are evolving towards decentralized commodity clusters that can scale in terms of capacity, processing power, and network throughput. The eorts that have been deployed to design such systems share simultaneously physical resources and data between applications [START_REF] Flouris | Orchestra: Extensible block-level support for resource and data sharing in networked storage systems[END_REF]. Cloud computing largely contributed in augmenting sharing capabilities of these systems thanks to their nice characteristics: elasticity, exibility, on-demand storage and computing services.

Queries which represent one of the most important entities of the database technology are also concerned by the sharing phenomenon. The query sharing got a particular interest in 80's,

where Timos Sellis identied a new phenomenon known by query interaction and gave rise to a new problem called Multi-Query Optimization (MQO) [START_REF] Sellis | Multiple-query optimization[END_REF]. Solving this problem aims at optimizing the global performance of a query workload, by augmenting the reuse of intermediate query results. One of the main characteristics of this research problem is that it has been tackled throughout all query languages associated to all database generations: traditional databases (RDB-SQL) [START_REF] Sellis | Multiple-query optimization[END_REF], object oriented databases (OODB -OQL) [START_REF]Readings in Object-Oriented Database Systems[END_REF], semantic databases (SDB -Sparql ) [START_REF] Le | Scalable multi-query optimization for sparql[END_REF][START_REF] Goasdoué | View selection in semantic web databases[END_REF], distributed databases [START_REF] Kementsietsidis | Scalable multiquery optimization for exploratory queries over federated scientic databases[END_REF], stream database (STDB -CQL) [START_REF] Dobra | Sketch-based multi-query processing over data streams[END_REF], data warehouses (SQL OLAP ) [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF], etc. as shown in Figure 1.1. The advent of MapReduce for large-scale data analysis brings the notion of job sharing. Hence, MQO has proved to be a serious candidate to exploit the common jobs and then factorize them [START_REF] Nykiel | Sharing across multiple mapreduce jobs[END_REF]. The main idea of this work has been borrowed from multi-query optimizations developed in traditional databases.

To integrate the actual reality, the query sharing has to consider a new dimension representing the volume of queries that storage systems have to deal with. This volume is motivated by the explosion of E-commerce Web sites, social media, etc. For instance, in Amazon, 100 million queries for various objects can arrive at its databases. The same fact is identied in Alibaba the giant Chinese E-commerce site. These queries are complex (require heavy operations such as joins and aggregations [START_REF] Bellatreche | Roupar: Routinely and mixed querydriven approach for data partitioning[END_REF]) and repetitive. Another aspect that contributes in increasing the number of queries that a particular DBMS has to handle is the recommendation and the exploration of queries [START_REF] Eirinaki | Querie: Collaborative database exploration[END_REF]. Faced to this situation, the traditional query sharing has to be revisited to integrate the volume of queries.

Based on this discussion, we claim that any data storage system has to deal with three joint dimensions: data volume, query volume (we call it big queries) and query sharing issues. The data volume impacts seriously the performance of queries. Having ecient methods to accelerate data processing becomes more important and urgent than ever, and hence they receive 2 http://www.legislation.nsw.gov.au/acts/2015-60.pdf I. CONTEXT special attention from academic and industrial researchers. This is well illustrated by the huge number of proposals, aiming at optimizing queries at the logical level [START_REF] Shapiro | Exploiting upper and lower bounds in top-down query optimization[END_REF][START_REF] Lee | Optimizing large join queries using a graph-based approach[END_REF][START_REF] Slivinskas | Bringing order to query optimization[END_REF][START_REF] Lerner | Aquery: Query language for ordered data, optimization techniques, and experiments[END_REF][START_REF] Reiss | A characterization of the sensitivity of query optimization to storage access cost parameters[END_REF][START_REF] Wang | Multi-query optimization in mapreduce framework[END_REF][START_REF] Dalvi | Pipelining in multi-query optimization[END_REF][START_REF] Seshadri | Optimizing multiple queries in distributed data stream systems[END_REF], the physical level [START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF][START_REF] Cong | Optimality, scalability and stability study of partitioning and placement algorithms[END_REF][START_REF] Baril | Selection of materialized views: A cost-based approach[END_REF][START_REF] Bellatreche | Bringing together partitioning, materialized views and indexes to optimize performance of relational data warehouses[END_REF][START_REF] Chaves | Towards materialized view selection for distributed databases[END_REF][START_REF] Curino | Schism: a workload-driven approach to database replication and partitioning[END_REF][START_REF] Kerkad | L'interaction au service de l'optimisation à grande èchelle des entrepôts de données relationnels[END_REF] and the deployment level [START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF].

The query sharing has largely contributed in optimizing queries [START_REF] Goasdoué | View selection in semantic web databases[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF] and physical design [START_REF] O'gorman | Multiple query optimization by cacheaware middleware using query teamwork[END_REF]7]). These eorts ignore the volume of queries.

Thus, we would like to issue a think tank about sharing among large amount of queries. This think tank is discussed in the context of relational data warehouses usually modeled by a star schema or its variants (ex. snowake schemas) that provide a query centric view of the data. Another important characteristic of this schema is that it increases the interaction among OLAP (Online Analytical Processing) queries, since they perform joins involving the central fact table(s) and peripheral tables, called dimensions.

Fig. 1.1 MQO in database generations

As we said before, data and queries are related to the advanced deployment platforms such as parallel, database clusters, etc. [START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF]. Designing a database in a such platform requires sensitive steps/phases, such as: (1) partition data into many fragments, (2) allocate the fragments in their corresponding processing nodes, and (3) give a query processing strategy over processing nodes, to ensure load balancing of queries. Data partitioning, data allocation and query load balancing problems have, as main inputs: a workload of queries, the characteristics of processing nodes and the database schema.

To deal with the volume of interacted queries, the development of advanced data structures that capture their sharing is widely recommended in dening intelligent algorithms. The graph theory and its data structures largely contribute in solving complex problems involving large scale of search space, such as data partitioning for centralized databases, where traditional CHAPTER 1. INTRODUCTION graph representations have been used by several researchers: (i) Navathe et al. [START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF][START_REF] Navathe | A mixed fragmentation methodology for initial distributed database design[END_REF] to dene vertical and horizontal data partitioning algorithms for relational databases and (ii)

Bellatreche et al. [START_REF] Bellatreche | Algorithms and support for horizontal class partitioning in object-oriented databases[END_REF] for horizontal partitioning in the context of object oriented databases.

Recently, Curino et al. [START_REF] Curino | Schism: a workload-driven approach to database replication and partitioning[END_REF] propose a generalization of the graph concept: hypergraphs, to partition and replicate the instances of a particular database in the case of distributed OLTP (Online Transaction Processing), where the processing of distributed transactions is expensive due to consensus protocol, distributed locks and communication cost. In this context, the nodes and the edges of a such graph represent respectively, instances of the database and transactions, where each edge is weighted by a number of transactions. A such the graph can be very huge, since its nodes are associated to the number of tuples of a database. To manipulate this very big graph, the authors are motivated to use hypergraph-partitioning algorithms that can ensure the scalability. In which, Hypergraph partitioning is well studied by the Electronic Design Automation (EDA) to test electronic circuit, besides, a large panoply of partitioning libraries exist such as hMETIS and Zoltan-PHG.

This motivates us to explore hypergraphs in dealing with large volume of interacted queries (since they were used to dealing with large number of instances). As a consequence, we approached, Mentors Graphics company located in Grenoble -France, a leader in EDA software to get their expertise in hypergraph usage and elaborate an analogy between our problem and their nding. This collaboration was fruitful, since after several months of collaboration, we succeed to nd an analogy between an electronic circuit and an unied query plan, by representing it as a hypergraph. We also adjust the using of their tools to be exploited for our problem.

Once this hypergraph is generated, we consider it in logical and physical optimizations and the deployment phase of the life cycle of a data warehouse design. This rich experience will be wholly discussed in this thesis.

II. Thesis objectives and contributions

Due to the large spectrum of topics that we studied in this thesis, covering: logical optimizations of queries; physical optimizations; data warehousing; optimization structures selection; multi-query optimization problem, cost models, deployment phase, hypergraphs, etc. It is necessary to present a synthetic survey on (i) the data warehouse technology, its life cycle that includes several phases (requirement collection, conceptual phase, logical phase, ETL (Extract, Transform, Load), deployment phase, physical phase and exploitation phase), (ii) logical and physical query optimizations, knowing that the former have been largely studied in the context of the traditional databases, whereas the latter have been amplied in the context of the data warehouses, and (iii) the deployment phase on a parallel database architecture.

Since we deal with the phenomenon of big queries and their interactions, we have to show the importance of a scalable data structure that easily captures this interaction, and can be used as a support to dene intelligent algorithms with less computation and high quality for selecting logical and physical optimizations. We have also to consider case studies to deploy our ndings. To do so, we consider the problem of selecting two optimizations structures which are the materialized views (MV ) and the horizontal partitioning for centralized and parallel environment. We have also developed a tool to assist designers and DBA (Database Administrator) when dealing with the physical design involving the interaction among queries.

II.1. Contributions

This section highlights the contributions of the thesis. First, we discuss the typical design of data warehouse to provide a general understanding of the design choices and deployment architectures. We will focus on The logical and physical optimizations, because they are the most important tasks of query optimizers. Another point concerns the deployment phase of the life cycle of the data warehouse.

From these overviews, we discuss the origin of our data structure to represent the query interaction issued from our collaboration with Mentors Graphics company. We would like to share this experience and the eorts provided to nd an analogy between our problem and electronic circuit.

Parallel to the denition of this structure, many other developments have been conducted to understand the algorithms and the tools used by VLSI (Very-Large-Scale Integration) community and adapt them to our context. Once, this adaptation is done, we consider two workload-driven problems: the selection of materialized views and the selection of horizontal partitioning. Furthermore, we discuss how we can improve the life cycle of the deployment phase by integrating our nding that concerns our data structure and its associated algorithms. Finally, we investigate the scalability of our algorithms and the quality of their solutions, by stressing them in terms of database size, size of queries, etc.

II.1.1. Survey of Logical and Physical Optimizations

We conduct an in-depth analysis of how the state-of-art database manages the interaction among queries and how it is used in logical, physical optimizations and the deployment phase of the life cycle of the data warehouse. Based on this survey, we give new classications of the existing studies and techniques used in the context of query optimization, and a clarication of the process of selecting optimization structures during the physical design phase, considered as one of the major phase. This material was published in the following paper: [47] Ahcène Boukorca, Ladjel We present an analogy between electronic circuit and unied query graph, that is usually generated by merging individual query trees. Note that the leaves of a tree are operands either variables standing for relations or particular, constant relations. Interior nodes are algebraic operators, applied to their child or children. On the other hand, a logical circuit is composed of gates (or standard cells) that perform logical operations and connected by metal wires [START_REF] Papa | Hypergraph partitioning and clustering[END_REF]. The same electrical signal may propagate from one gate to several other gates such a connection is called a net, and can be conveniently represented by a hyperedge.

The hypergraph corresponding to a logic circuit directly maps gates to vertices and nets to hyperedges. Figure 1.2 shows the usage of hypergraphs in representing logical circuit. The processors in today's PCs contain tens of millions of microscopic transistors. This scalability is usually ensured by graph partitioning techniques [START_REF] Papa | Hypergraph partitioning and clustering[END_REF]. We can cite for instance PaToH (Partitioning Tool for Hypergraphs) [START_REF] Catalyürek | Patoh: a multilevel hypergraph partitioning tool[END_REF] and hMETIS -Hypergraph & Circuit Partitioning 3 .

hMETIS is a set of programs for partitioning hypergraphs such as those corresponding to VLSI circuits.

Making the analogy between our problem and electronic circuit allows us borrowing techniques and tools of the EDA community and adapting them to the generation of an unied query plan from numerous queries. Our nding is then exploited to solve the problem of MQO and to evaluate its eciency and quality against the most popular study of the state-of-art. This material was published in the following paper: [50] The query interaction represented by a unied query plan (UQP) is lying at the intersection of two worlds: the world of multi-query optimization and the world of physical design. An 3 http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview II. THESIS OBJECTIVES AND CONTRIBUTIONS optimal unied query plan is not necessary good for all instances of the physical design problem [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Yang | A framework for designing materialized views in data warehousing environment[END_REF]. Thus, it is needed to choose a good plan as input in order to produce a good set of an optimization structure candidates. Moreover, a good UQP for an optimization structure (OS ), is not necessary good for another structure. Choosing the best a UQP requires enumerating all possible plans, what is impossible because of the huge number of possible plans in the case of big workloads (big-queries ). On the other side, the size of candidates proposed by any UQP in big-queries context, may be very big. As a consequence, nding the optimal optimization structure conguration becomes very dicult or even impossible (complexity of combinatorial algorithms).

To overcome these problems, we have proposed a new approach that incorporates the knowledge related to optimization structures when generating UQP, in order to minimize their enumeration cost. Our proposal captures query interaction in an UQP, by dividing the initial problems in several small disjoint sub-problems, which can be executed in parallel. Dividing multi-query optimization search space implies splitting the set of candidate elements in several small subsets, which minimizes the complexity of combinatorial algorithms to select the best conguration of an optimization structure. Our approach works around the hypergraph: a data structure (DS) used to model query interaction. This DS supports a big number of candidate elements and has already the adequate algorithms to partition the initial conguration into several sub-congurations with minimum loss of its characteristic (query interaction). The approach is inspired from the hypergraph partitioning and its contributions in testing logical circuits.

More concretely, we propose a greedy approach that produces an adequate UQP for an OS, called OS-oriented UQP, by injecting optimization structure knowledge in the process of UQP generation.

This proposal was published in the following paper:

[52] Ahcène Boukorca, Zoé Faget, Ladjel Bellatreche: What-if Physical Design for Multiple Query Plan Generation. 25th International Conference on Database and Expert Systems Applications (DEXA), pp.492-506, Munich, Germany, September 1-4, 2014.

To evaluate the eciency and eectiveness of our approach, we consider two traditional optimization structures: materialized views and horizontal partitioning both are based on a workload of queries, but use dierent constraints. For materialized views, we evaluate our proposal for static and dynamic cases, with taking account or not of the problem of query scheduling.

This material was published in the following paper: [49] Since queries are used by all phases of the deployment steps: data partitioning, data allocation and load balancing, we think that it could be interesting to push our reection of incorporating our hypergraph structure in all query sensitive problems, in the deployment phase. The promising results obtained in a project in our lab, that aims at proposing a joint approach to deploy a data warehouse in a parallel architecture [START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF], motivate us to integrate the dimension of the interaction among queries to deploy a data warehouse in a parallel architecture, especially the horizontal data partitioning and data allocation.

This material was published in the following paper: [START_REF] Boukorca | HYPAD: hyper-graph-driven approach for parallel data warehouse design[END_REF] Ahcène Boukorca, Ladjel Bellatreche, Soumia Benkrid: HYPAD: Hyper-Graph-Driven Approach for Parallel Data Warehouse Design. 15th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP), pp. 770-783, Zhangjiajie, China, November 18-20, 2015. Based on our ndings, it will be opportune to develop an advisor inspired from the well-known tools developed by commercial editors and academicians to assist both designers and DBAs during their deployment activities and administration tasks when selecting optimization structures.

As a consequence, we develop a tool called Big-Queries that combines two main functionalities: selecting optimization structures and deploying a DW in parallel machines. This interface allows DBA visualizing the state of his/her database that concerns three aspects: (i) tables of the target data warehouse (their descriptions, denition and domain of each attribute), (ii) the used workload (their SQL descriptions, access frequency of each query, selectivity factors of selection and join predicates), and (iii) resources required by physical design phase (size of the buer, page size, the constraints related to our OS), (iv) the interaction among queries visualized as hypergraphs, the dierent schemes related to our OS (materialized views and horizontal partitioning), the deployment schema with their respective costs (inputs/outputs, maintenance costs, storage costs). It is doted of gateway connection to several types of DBMS (Oracle11g, Oracle 12c, PostgreSQL).

Big-queries tool is available in the forge of our laboratory: http://www.lias-lab.fr/forge/ projects/bigqueries.

Repartition of thesis chapters

The remainder of the manuscript is organized as follows:

Chapter 2: provides the necessary background to understand our contributions. In this chapter, we start by zooming on data warehousing technology on which our experiments validation are done. Thereafter, we detail the parameters that aect response query processing time, materialized views, data partitioning and mulit-query optimization problems, and we give overviews of designing parallel data warehouse.

Chapter 3: details our main contribution that consists at using graph theory to overcome the of managing big-queries. The contribution aims at merging the MQO and physical design problems to generate target candidates for a specic optimization technique (MV , index, and data partitioning). This is done by injecting OS knowledge in the generation of UQP.

Chapter 4: presents the application of our oriented-UQP approach in the selection of dierent OS. First, the UQP is applied for MV selection issue with and without constraints, and exploited in dynamic materialization with query scheduling. Secondly, the UQP is used for horizontal data partitioning (HDP ).

CHAPTER 1. INTRODUCTION

Chapter 5: details our approach to design a parallel data warehouse taking into account query interaction that represented by unied query plan.

Chapter 6: gives a description of our tool Big-Queries used to validate our work.

Conclusion: concludes the thesis by providing a summary and an evaluation of the presented work. This chapter also discusses several opportunities for future work.

The main contributions of this thesis are presented in chapters 3, 4, 5 and 6. Figure 1.3 shows schematically the main axes of this work and their distribution in each chapter.

Part I Backgrounds

Chapter 2

Abstract

This chapter is divided into two parts: (i) the background that presents dierent concepts and denitions related to the context of our study which represents the data warehouse. A special focus on its design life cycle is given. It includes the following phases: (a) elicitation of user requirements, (b) the conceptual modelling, (c) the logical modelling, (d) ETL (Extract, Transform, Load), (e) the deployment, (f) the physical modelling, and (g) the exploitation phase. This background aims at facilitating the presentation and the understanding the set of our contributions that covers three chained phases: logical, deployment and physical. (ii) Due to the complexity of these phases, we propose to present state of art related to logical and physical optimizations of queries running on centralized and parallel platforms. In this state of art, we also discuss the role of interaction between queries a phenomenon well present in the context of relational data warehouses.

I. Introduction

Processing and optimization of queries in all database generations (traditional databases, object oriented databases, XML databases, data warehouses, graph databases, factorized databases, etc.) strongly depend on the proprieties of their: logical models, query languages and physical models, which are the funnel of all other phases of the database life cycle. This situation oers two main types of query optimizations: (i) logical optimizations and (ii) physical optimizations.

As regards the rst type of optimizations, when a query is issued by a user or an application, it is parsed to check whether the query is correctly specied, resolve any names and references, verify consistency, and perform authorization tests. When the query passes these tests, it is converted into an internal representation that can be easily processed by the subsequent phases.

Then, the "query rewrite" module transforms the query into an equivalent form by carrying out a number of optimizations oered by the properties of the used query languages (e.g. algebraic properties the relational model) [START_REF] Pitoura | Query optimization[END_REF]. In the context of very large databases requiring complex queries involving joins and aggregations, the logical optimizations are not enough [START_REF] Chaudhuri | Self-tuning database systems: A decade of progress[END_REF].

As a consequence, the physical optimizations (such as materialized views, indexes, partitioning, data compression, etc.), selected during the physical phase (P YP), are necessary. These optimizations are crucial for performance of the nal database/data warehouse, since they deal with decisions about selecting physical storage structures and access methods for data les.

It should be noticed that the PYP exploits the properties of the deployment platform of the target databases/data warehouses.

The query processing and optimization have been one of the most active research topics in the Core Databases and Information Systems. By scholar.googling "query processing databases", in 2016, we nd 11 300 entries. Queries can be executed either in an isolated way or in a joint manner. In this later, the exploitation of common intermediate results of the queries is usually considered when selecting optimization structures. The problems related to query optimization and physical design are both known as hard tasks. They integrate several parameters belonging to various phases of the life cycle of database/data warehouse design: conceptual, logical and deployment and constraints (e.g. storage, maintenance, energy). Consequently, their search spaces may be very large [START_REF] Sellis | On the multiple query optimization problem[END_REF][START_REF] Cluet | On the complexity of generating optimal left-deep processing trees with cross products[END_REF][START_REF] Pellenkoft | The complexity of transformationbased join enumeration[END_REF][START_REF] Scheufele | On the complexity of generating optimal plans with cross products (extended abstract)[END_REF][START_REF] Chaudhuri | Index selection for databases: A hardness study and a principled heuristic solution[END_REF][START_REF] Bellatreche | Referential horizontal partitioning selection problem in data warehouses: Hardness study and selection algorithms[END_REF]. To reduce the complexity of these problems, pruning of these search spaces is mandatory [START_REF] Labio | Physical database design for data warehouses[END_REF].

In early researches on databases, the majority of the studies were focused on logical optimizations. The importance of physical optimizations and especially physical design, were amplied as query optimizers became sophisticated to cope with complex decision support queries that share intermediate results [START_REF] Chaudhuri | Self-tuning database systems: A decade of progress[END_REF]. To strengthen our nding, we consider the multi-query optimization, initially discussed by Professor Timos Sellis in 1988 [START_REF] Sellis | Multiple-query optimization[END_REF], in the context of logical optimizations. It aims at exploiting common sub-expressions to reduce evaluation cost of queries. Modelling this problem has been exploited by the process of physical optimization structures such as materialized views [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF]. This clearly shows the strong dependency between logical (LOP ) and physical (P OP) optimizations. This means that if a change in the LOP often results in a change in that of POP. With the explosion of data volumes, the increasing needs of end users and decision makers in terms of exploring data [START_REF] Kalinin | Searchlight: Enabling integrated search and exploration over large multidimensional data[END_REF] and recommending queries [START_REF] Aligon | A collaborative ltering approach for recommending OLAP sessions[END_REF], and the diversity of deployment platforms motivate us to consider the dependency between logical and physical optimizations in the context of big-queries. In this chapter, we introduce the foundations on which this work is built, and position our contributions.

This chapter begins with an overview of the data warehouse technology, its architecture, its design life cycle (Section II). In Section III, we present factors that inuence the logical and physical optimizations of OLAP queries. Section discusses the most popular data structures used in database context. Finally, Section V concludes the background material.

II. The Data Warehousing Technology

Traditional databases, called operational databases, are designed for building day-to-day applications. They aim at ensuring fast and concurrent accesses to data while guaranteeing consistency. They are based on the On-Line Transaction Processing (OLTP) paradigm. These databases are designed with high normalization degree using functional dependencies and normal forms [START_REF] Elmasri | Fundamentals of database systems[END_REF]. Generally, the OLTP transactions access and return few records [START_REF] Elmasri | Fundamentals of database systems[END_REF]. On the other hand, analytical requirements imposed by big companies such as Wal-Mart [START_REF] Westerman | Data Warehousing Using the Wal-Mart Model[END_REF] need to aggregate a large volume of historical data from many tables (using joins). Unfortunately, operational databases fail to support analytical queries. This is because they were not designed to store the historical data and process them in ecient way. These limitations largely contributed to the birth of a new technology which is the data warehousing that supports On-Line Analytical Processing (OLAP).

A Data Warehouse (DW ) aims at supporting decision's making. It collects data from various heterogeneous, autonomous, evolving and distributed data sources, transforms and cleans them and nally loads them into new data structures designed to support OLAP queries. These structures are represented by a hypercube, with dimensions corresponding to various business perspectives, and their cells contain the measures to be analyzed.

In the sequel, we give an overview related to a DW. A brief description of the conventional architecture, query languages and designing steps of a DW are discussed. A large discussion about the logical and physical optimizations is also given.

II.1. Denitions

Denition 1. DW is a repository of integrated data issued from dierent sources for data analytic purposes [START_REF] Kimball | The data warehouse toolkit: the complete guide to dimensional modeling[END_REF]. More technically, a DW is dened as a collection of subject-oriented, integrated, non-volatile, and time-varying data to support management decisions [START_REF] Vaisman | Data Warehouse Systems: Design and Implementation[END_REF].

Below, we explain the four key characteristics of a DW [START_REF] Vaisman | Data Warehouse Systems: Design and Implementation[END_REF]:

II. THE DATA WAREHOUSING TECHNOLOGY Subject oriented: means that the DW focuses on analytical needs which depend on the nature of activities performed by the companies (e.g. inventory management, product sales recommendation, etc.).

Integrated: means that data are extracted from several organizational and external sources have to be integrated after the processes of cleaning, transformation usually performed through an Extraction, Transformation, and Loading Process (ETL).

Non-volatile: means that durability of data is guaranteed by disallowing data modication and removal, thus expanding the scope of the data to long period than operation systems usually oer.

Time varying: indicates the possibility of keeping, for the same information, dierent values related to its changes (evolution).

Denition 2. On-Line Analytical Processing (OLAP) deals with analytical queries that handle a heavy load of data which involves aggregation of values captured by scanning all records in a database [START_REF] Cabibbo | Querying multidimensional databases[END_REF].

Denition 3. Multidimensional model is a data representation in an n-dimensional space [START_REF] Gray | Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals[END_REF]. Usually called data cube or hypercube. It is used as a data structure to save data and to facilitate the optimization of OLAP queries.

A multidimensional model is composed of a set of dimensions and set of facts. A dimension is composed of either one level or one or more hierarchies. A level is analogous to an entity type in Entity-Relationship model [START_REF] Chen | The entity relationship model toward a unied view of data[END_REF]. A hierarchy comprises several related levels (e.g. year -→ semester -→ month -→ day). A dimension may contain several hierarchies. Levels in a hierarchy permit analyzing data at various granularities or level of details. These levels impact the query processing and optimization (e.g., the case of bitmap join indexes [START_REF] Bellatreche | A data mining approach for selecting bitmap join indices[END_REF]). Denition 4. Data mart: is a specialized data warehouse oriented for a specic business line or a team (department) [START_REF] Golfarelli | Data Warehouse Design: Modern Principles and Methodologies[END_REF].

II.2. Data warehouse architecture

In the literature, the general architecture of a DW is composed of ve tiers [START_REF] Kimball | The data warehouse toolkit: the complete guide to dimensional modeling[END_REF] as shown in 3). The ETL process needs an intermediate temporary database called data staging area [START_REF] Vassiliadis | A survey of extracttransformload technology[END_REF], which is used to temporarily save extracted data to facilitate the integration and transformation processes before their loading into the DW.

3. The data warehouses tier: represents the data repository dedicated to store a DW or several data marts. The DWs and data marts are described by Meta-data that denes the semantic of data and organizational rules, policies, and constraints related to data items [START_REF] Golfarelli | Data Warehouse Design: Modern Principles and Methodologies[END_REF].

4. The OLAP tier: is composed of OLAP server usually used for business use of multidi-II. THE DATA WAREHOUSING TECHNOLOGY mensional data representation.

5. The end user tier: contains tools allowing users to exploit the DW contents. It includes: (1) tools to execute OLAP queries. (2) reporting and statistical tools to provide dashboards following the decision requirements, and (3) data mining tools to discover some valuable knowledge from data currently stored in the DW. To load data, the end user tools can use the OLAP server, DW, or data marts.

II.3. Data warehouse design methods

In this section, we present dierent phases of the life-cycle of its design inherited from traditional databases. Usually, it includes the following phases: data source analysis, elicitation of requirements, conceptual, logical, deployment, and physical design. ETL is appended as a design phase responsible for analytical processing [START_REF] Khouri | Cycle de vie sémantique de conception de systèmes de stockage et de manipulation de données[END_REF]. Phases depicted in Figure 2.3 have to be follow when designing a DW.

Requirements specification

Conceptual design

Logical design ETL design

Deployment design

Physical design

Fig. 2.3 Phases in data warehouse design

Data Sources. As we said before a DW is built from heterogeneous data sources, with different data representations, and provenance. The heterogeneity poses serious problems when designing the DW. This is due to the presence of conicts that may exist among sources. Goh et al. [START_REF] Goh | Context interchange: New features and formalisms for the intelligent integration of information[END_REF] suggest the following taxonomy of conicts: naming conicts, scaling conicts, confounding conicts and representation conicts. These conicts may be encountered at schema level and at data level.

Naming conicts: occur when naming schemes of concepts dier signicantly. The most frequently case is the presence of synonyms and homonyms. For instance, the status of a person means her familial status or her employment status.

Scaling conicts: occur when dierent reference systems are used to measure a value (for example price of a product can be given in Dollar or in Euro).

Confounding conicts: occur when concepts seem to have the same meaning, but dier in reality due to dierent measuring contexts. For example, the weight of a person depends on the date where it was measured. Among properties describing a data source, we can distinguish two types of properties: context dependent properties (e.g. the weight of a person) and context non-dependent properties (gender of a person).

Representation conicts : arise when two source schemas describe the same concept in dierent ways. For example, in one source, student's name is represented by two elements FirstName and LastName and in another one it is represented by only one element Name.

The data sources may be grouped into ve main categories [START_REF] Ponniah | Data Warehousing Fundamentals for IT Professionals[END_REF]: (i) production data, (ii) internal data, (iii) archived data, (iv) external data and (v) experimental data. The production data come from the various operational systems of the enterprise. The internal data include the data stored in spreadsheets, documents, customer proles, databases which are not connected to the operational systems. External data such as data produced by external agencies, weather forecast services, social network, and recently knowledge bases such as Yago [START_REF] Hoart | YAGO2: exploring and querying world knowledge in time, space, context, and many languages[END_REF], etc. play an crucial role in DW design of adding new values to the warehouses [START_REF] Berkani | A value-added approach to design BI applications[END_REF]. Recently, the computational science community such as physics, aeronautic, etc. is building warehouses from the experiment results. We can cite for instance, the example of project AiiDA 1 .

The data of sources range from traditional ones, to semantic data, passing by graph databases [START_REF] Hitzler | Foundations of semantic web technologies[END_REF][START_REF] Etcheverry | Enhancing olap analysis with web cubes[END_REF]).

Data Warehouse Requirements. As any product, the development of a DW application is based on functional and non-functional requirements [START_REF] Golfarelli | Data Warehouse Design: Modern Principles and Methodologies[END_REF]. Note that functional requirements describe the functionalities, the functioning, and the usage of the DW applications to satisfy the goals and expectations of decision makers. These requirements are known as business requirements [START_REF] Brucker | Securebpmn: modeling and enforcing access control requirements in business processes[END_REF] that represent high-level objectives of the organization for the DW application. They identify the primary benets that the DW technology brings to the organization and its users. They express business opportunities, business objectives and describe the typical users and organizations requirements and their added-values. Other functional requirements are associated to users of the DW (called user requirements) describe the tasks that the users must be able to accomplish with thanks to the DW application. User requirements must be collected from people who will actually use and work with this technology. Therefore, these users can describe both the tasks they need to perform with the DW. These requirements are modelled using several formalisms such as: UML use cases, scenario descriptions and goals [START_REF] Boukhari | Intégration et exploitation de besoins en entreprise étendue fondées sur la sémantique[END_REF].

Non-functional requirements, called quality attributes are either optional requirements or needs/constraints [START_REF] Lauesen | Task descriptions as functional requirements[END_REF], they are detailed in system architecture. They describe how the system will do the following objectives: the security, the performance (e.g. response time, refresh time, processing time, data import/export, load time), the capacity (bandwidth transactions per hour, memory storage), the availability, the data integrity, the scalability, the energy, etc. This type of requirements has to be validated over the majority of the phases of the DW life-cycle.

Conceptual Design. It aims at deriving an implementation-independent and expressive conceptual schema according to the conceptual model. As said in [START_REF] Vaisman | Data Warehouse Systems: Design and Implementation[END_REF] that database community 1 http://www.aiida.net/ II. THE DATA WAREHOUSING TECHNOLOGY agreed for several decades that conceptual models allow better communication between designers in terms of understanding application requirements. However, there is no well-established conceptual model for multidimensional data. Several formalisms mainly borrowed from traditional databases exist to design the conceptual model of a DW: E/R model [START_REF] Golfarelli | Conceptual design of data warehouses from e/r schemes[END_REF][START_REF] Sapia | Extending the e/r model for the multidimensional paradigm[END_REF],

object-oriented model [3,[START_REF] Trujillo | Designing data warehouses with oo conceptual models[END_REF][START_REF] Luján-Mora | A uml prole for multidimensional modeling in data warehouses[END_REF], and non-graphical representation [START_REF] Pedersen | A foundation for capturing and querying complex multidimensional data[END_REF]. The quality of a DW conceptual model is evaluated using testing methods [START_REF] Tort | An approach to test-driven development of conceptual schemas[END_REF].

Logical Design. There are three main approaches to represent logical model of a DW, depending on how the data cube is stored: (i) the relational ROLAP (ROLAP), which stores data cube in relational databases and uses an extension of SQL language to process these data.

Two main schemes are oered by ROLAP: the star schema and snowake schema. Figures 2.4a

and 2.4b show, respectively, an example of DW star and snowake schemes of SSB benchmark [START_REF] O'neil | Star schema benchmark[END_REF]. A star schema consists of a one or several large fact table (s) connected to multiple dimension tables via foreign keys. Dimension tables are relatively small compared to the fact table and are rarely updated. They are typically non normalized so that the number of needed join operations is reduced. To avoid redundancy, the dimension tables of a star schema can be normalized. There is a debate on the benets of having such normalized dimension tables, since it will, in general, slow down query processing, but in some cases it provides a necessary logical separation of data such as in the case of the demographic information [START_REF] Levene | Why is the snowake schema a good data warehouse design?[END_REF]. (ii) multi- ETL design. ETL processes are responsible for extracting and transforming data from heterogeneous business information sources to nally loading them into the target warehouse. This phase plays a crucial role in the process of the DW design. The quality of the warehouse strongly depends on ETL (the garbage in garbage out principle) [2]. The dierent steps of ETL need to understand dierent schemes (conceptual, logical and physical) of data sources [START_REF] Simitsis | Optimizing etl processes in data warehouses[END_REF][START_REF] Bellatreche | Semantic data warehouse design: From ETL to deployment à la carte[END_REF][START_REF] Vassiliadis | A generic and customizable framework for the design of etl scenarios[END_REF][START_REF] Vassiliadis | Modeling etl activities as graphs[END_REF][START_REF] Trujillo | A uml based approach for modeling etl processes in data warehouses[END_REF]2,[START_REF] Wilkinson | Leveraging business process models for etl design[END_REF][START_REF] Tziovara | Deciding the physical implementation of etl workows[END_REF]. Several commercial and academic tools of ETL are also available such as: Oracle Warehouse Builder (OWB), SAP Data Services, Talend Studio for Data Integration, Pentaho Data Integration, etc.

2 .

The rst studies on ETL were concentrated on the physical models of data sources that includes the deployment platform (centralized, parallel, etc.) and the storage models used by the physical models (e.g. tables, les). In [START_REF] Tziovara | Deciding the physical implementation of etl workows[END_REF], a set of algorithms was proposed to optimize the physical ETL design. Alkis et al. [START_REF] Simitsis | Optimizing etl processes in data warehouses[END_REF] propose algorithms for optimizing the eciency and performance of ETL process. Other non-functional requirements such as freshness, recoverability, and reliability have been also considered [START_REF] Simitsis | Optimizing etl workows for fault-tolerance[END_REF]. The work of [START_REF] Nakuçi | Bijoux: Data generator for evaluating ETL process quality[END_REF] proposes an automated data generation algorithm assuming the existing physical models for ETL to deal with the problem of data growing.

Other initiatives attempted to move backward ETL from physical models to logical models.

[262] proposed an ETL work-ow modelled as a graph, where nodes of the graph are activities, record-sets, attributes, and the edges are the relationship between nodes dening ETL transformations. It should be noticed that graphs contributing in modelling ETL activities.

In [START_REF] Vassiliadis | A generic and customizable framework for the design of etl scenarios[END_REF], a formal logical ETL model is given using Logical Data Language (LDL) [START_REF] Shmueli | Logical diagnosis of ldl programs[END_REF] as a formal language for expressing the operational semantics of ETL activities. Such works assume that ETL workow knows the logical models of data sources and the elements of their schemes (relations, attributes).

Another move backward to conceptual models has been also identied, where approaches based on ad-hoc formalisms [START_REF] Vassiliadis | Conceptual modeling for etl processes[END_REF], standard languages using UML [START_REF] Trujillo | A uml based approach for modeling etl processes in data warehouses[END_REF], model driven architecture (MDA) [START_REF] Trujillo | An mda approach for the development of data warehouses[END_REF], Business Process Model and Notation(BPMN) [START_REF] Wilkinson | Leveraging business process models for etl design[END_REF][START_REF] Akkaoui | Bpmn-based conceptual modeling of etl processes[END_REF] and mapping modelling [START_REF] Calvanese | Description logics for conceptual data modeling[END_REF][START_REF] Luján-Mora | Data mapping diagrams for data warehouse design with uml[END_REF]. However, these approaches are based on semi-formal formalisms and do not allow the representation of semantic operations. They are only concentrated on the graphical design of ETL processes without specifying the operations and transformations needed to overcome the arising structural and semantic conicts. Some works use ontologies as external resources to facilitate and automate the conceptual design of ETL process. [START_REF] Skoutas | Ontology-based conceptual design of etl processes for both structured and semi-structured data[END_REF] automated the ETL process by constructing an OWL ontology linking schemes of semi-structured and structured (relational) sources to a target data warehouse (DW ) schema. Other studies have been concentrated on semantic models of data sources such as the work of [START_REF] Nebot | Building data warehouses with semantic web data[END_REF] that considers data source provided by the semantic Web and annotated by OWL ontologies. However, the ETL process 2 https://www.etltool.com/list-of-etl-tools/ II. THE DATA WAREHOUSING TECHNOLOGY in this work is dependent on the storage model used for instances which is the triples. Note that after each research progress on ETL, its operations have to be specied and rewritten.

This situation motivates researchers to make ETL more generic. In [START_REF] Vassiliadis | Modeling etl activities as graphs[END_REF], the authors propose a generic model of ETL activities that plays the role of a pivot model, where it can dene 10 generic ETL operator [START_REF] Skoutas | Ontology-based conceptual design of ETL processes for both structured and semi-structured data[END_REF]. The signature of each operator is personalized to the context where target data source contains integrated record-sets related to attributes extracted from sources satisfying constraints:

1. Retrieve(S, A, R): retrieves record-sets R related to attributes A from Source S; 10. Store(T, A, R): loads record-sets R related to attributes A in target data source T , Building the ETL process is potentially one of the biggest tasks of building a warehouse; it is complex, time consuming, and takes the lion's share of design and implementation eorts of any warehouse project. This is because it requires several tasks and competencies in terms of modelling, work-ows, and implementations. Non-functional requirements such as quality and the performance are taken into account when designing ETL [START_REF] Vassiliadis | Conceptual modeling for etl processes[END_REF][START_REF] Simitsis | Mapping conceptual to logical models for etl processes[END_REF][START_REF] Bowen | Getting Started with Talend Open Studio for Data Integration[END_REF]. In this thesis, we assume that ETL phase is already performed.

Deployment Phase. This phase consists in choosing the adequate platform in which the target warehouse will be deployed. Several platforms can candidates to store the warehouse: centralized, database clusters, parallel machines, Cloud, etc. The choice of the deployment platform depends on the company budget and the xed non-functional requirements [START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF].

CHAPTER 2. BACKGROUND & STATE OF ART

Physical design. It is a crucial phase of the DW life cycle. Note that the majority of nonfunctional requirements are evaluated during this phase. It uses the inputs of deployment and the logical phases. In this design, optimization structures such as materialized views, indexes, data partitioning, etc. are selected to optimize one or several non-functional requirements such as query performance and energy.

Since, we concentrate on processing and optimizing big queries that take into account the logical, deployment and physical phases, a special focus on deployment and physical phases will be given in next sections.

II.4. Summary

Based on the above discussion, we gure out the presence of diversity that concerns all phases of the life cycle that designers have to consider when designing a DW application. If we project this diversity on our contributions (related to processing and optimizing big queries), we have identied four main dimensions that have to be taken into account when oering adequate optimizations of these queries:

1. the chosen logical model (LM) of the DW application identied during the logical phase of the life cycle;

2. the used query language (QL) oered by the DBMS;

3. the used deployment platform (DP ) including the target DBMS and hardware;

4. the available logical and physical optimizations (P O) oered by the DBMS that have to be exploited by DBA either in isolated or joint manners to ensure the performance of her/his workload.

Once these dimensions are chosen, they give the signature of a warehouse application. The particularity of these dimensions is that the rst three are generally supposed as frozen, and the last one may vary according the DBA expertise and the query optimization requirements.

Example 1. To illustrate these four dimensions that we considered as the core of our think tank, The objective of our problem is to optimize the workload W by: exploiting as much as possible the characteristics of each input.

To taking better advantages of these characteristics, we propose in next sections to review each dimension and their interaction. In this thesis, we concentrate on a SQL language for ROLAP DW. This language uses several operators with a rich set of properties on their compositions that impact the deployment and the physical design phases. These properties are described in the Appendix XII.

In the rst generation of query processing, the queries were treated in isolation. In 1988, the concept of multi-query optimization has been introduced in [START_REF] Sellis | Multiple-query optimization[END_REF].

Denition 5. Multiple query optimization (MQO) (called also global query optimization) exploits the interaction among queries by the means of intermediate results of a given the workload [START_REF] Sellis | Multiple-query optimization[END_REF].

To understand this phenomenon of MQO, let us consider the following example. This phenomenon has been largely exploited by logical and physical optimizations as we will show in next Sections.

III.3. Dimension 3: Logical and Physical Optimizations

As we said before, in this dimension, we distinguish two main types of optimizations: logical and physical.

III.3.1. Logical Optimizations

The logical optimizations are related to dierent operations that a query optimizer has to performed when generating the best query plan (for a given query) among numerous plans. This is done by the exploitation of the properties of relational algebra. Note that all plans are equivalent in terms of their nal output, but vary in their costs. This cost quanties a metric of a non functional requirement such as the amount of time that they need to run [START_REF] Ioannidis | Query optimization[END_REF]. One of the main task of a query optimizer is to select the plan with minimum amount of time. This requires smart algorithms associated with advanced data structures.

More concretely, the query trees and plans are one the most important inputs of any query optimizer. The process of executing a given query passes through four main steps: (i) parsing, (ii) rewriting, (iii) planning/optimizing, and (iv) executing. The parser checks the query string for valid syntax using a set of grammar rules, then translates the query into an equivalent relational algebra expression. The output is the query tree. The rewriter processes and rewrites the tree using a set of rules. The planner/optimizer creates an optimal execution plan using a cost model that accounted for CPU costs as well Inputs Outputs (IO) costs. This type of optimization is called cost-based optimizations. Figure 2.6 summarizes the dierent steps of a query optimizer.

A cost model species the arithmetic formulas that are used to estimate the cost corresponding a given non functional requirement metric of execution plans (e.g., execution time, energy consuming, etc.). For every dierent join implementation, for every dierent index type access, and in general for every distinct kind of step that can be found in an execution plan, there is a formula that gives its costs [START_REF] Ioannidis | Query optimization[END_REF]. In Appendix I, we detail our used cost models.

The discussion that we had above concerns queries executed in isolation way. If all queries are considered in a batch fashion, the problem of MQO arises. It can be dened as follows:

for given a set of queries Q={Q 1 , . Example 3. To illustrate the process of selecting the best plan of queries in isolated and joint ways, let us consider the queries discussed in Example 3, where we suppose that the base relations R 1 , R 2 , R 3 and R 4 have respectively a scan cost of 1000, 10, 50 and 70 units and we assume the absence of any optimization structure. The query optimizer suggests individual best plans for each query and the DBMS uses these plans to execute the queries independently. As shown in Figures 2.7a and 2.7b, the optimal plans of the queries

Q 1 and Q 2 are (σ att 1 =val (R 1 ) R 2 ) R 3 and (σ att 1 =val (R 1 ) R 3 ) R 4
respectively. The total cost of the two queries is 20 380 units. However, we remark that the intermediate result (σ att 1 =val (R 1 ) R 3 ) can be shared by both queries. As shown in Figure 2.7c, the global plan has a total cost of 14430 units. So, by using MQO technique, we can easily reduce the execution cost by about 30%. (c) Multi query plan

R 3 R 2 Q 1 att1=val R 1
(Q 1 &Q 2 )

Fig. 2.7 Example of MQO benet

In the above example, the process of merging individual plans is straightforward. But, in a large workload, nding the best merging of dierent query plans is a hard problem. Since 80, it has been widely studied [START_REF] Chen | The implementation and performance evaluation of the adms query optimizer: Integrating query result caching and matching[END_REF][START_REF] Cosar | Multiple query optimization with depth-rst branch-and-bound and dynamic query ordering[END_REF][START_REF] Finkelstein | Common expression analysis in database applications[END_REF][START_REF] Park | Using common subexpressions to optimize multiple queries[END_REF][START_REF] Sellis | On the multiple query optimization problem[END_REF][START_REF] Sellis | Multiple-query optimization[END_REF][START_REF] Shim | Improvements on a heuristic algorithm for multiple-query optimization[END_REF][START_REF] Subramanian | Cost-based optimization of decision support queries using transient-views[END_REF][START_REF] Zhao | Simultaneous optimization and evaluation of multiple dimensional queries[END_REF]. Sellis [START_REF] Sellis | Multiple-query optimization[END_REF] proposed an A * algorithm search algorithm to produce a global execution plan based on all possible local plans of each query. Alternatively, the local plan is constructed by either a dynamic programming algorithm [START_REF] Park | Using common subexpressions to optimize multiple queries[END_REF] or a branch bound algorithm [START_REF] Grant | On optimizing the evaluation of a set of expressions[END_REF]. Subsequently, the local plans are merged into a single global plan such that the results of common sub-expressions can be shared as much as possible. These methods may take considerable memory resource and time to generate an optimized plan. Accordingly, many heuristic algorithms are proposed to improve signicantly the generation time. They reduce the size of the search space for A * algorithm, but they produce a sub-optimal global plan.

Logical optimizations have a great impact on physical optimizations, as we will show in the next sections.

III.3.2. Physical Optimizations

Physical optimizations have been amplied by the explosion of data and the necessity to optimize them [START_REF] Chaudhuri | Self-tuning database systems: A decade of progress[END_REF]. These optimizations are ensured by the means of advanced structures such as materialized views, advanced indexing, data partitioning, etc. In this section, we describe the most used database optimization structures (OS ). A particular interest to the OS used by our study. We start by materialized views that is a redundant OS and is widely used to optimize OLAP queries in the context of the DW. Materialized views are used to pre-compute either stored aggregated data or joins with/without aggregations. So, materialized views are suitable for queries with expensive joins or aggregations. Once materialized views are selected, all queries will be rewritten using materialized views (this process is known as query rewriting). A rewriting of a query Q using views is a query expression Q referencing to these views. The query rewriting is done transparently by the query optimizer. To generate the best rewriting for a given query, a cost-based selection method is used [START_REF] Bello | Materialized views in oracle[END_REF]. Views selection problem. The database administrator cannot materialize all candidate views, as he/she is constrained by some resources like, disk space, computation time, maintenance overhead and cost required for query rewriting process [START_REF] Harinarayan | Implementing data cubes eciently[END_REF]. Hence, he/she needs to pick an appropriate set of views to materialize under some resource constraints.

Formally, view selection problem (V SP) is dened as follows: given:

1. a set of most frequently used queries Q = {Q 1 , Q 2 , ..., Q n }, where each query Q i has an access frequency f i (1 ≤ i ≤ n);

2. a set of constraints C (e.g., storage cost, maintenance cost, etc.); The VSP consists in selecting a set of materialized views that satises the N FR and respect the constraints C.

Generation of the plan

From the above generic formalization, several variants of the VSP can be derived, by instantiating either the set of N FR or the constraints. The most important variants are:

minimizing the query processing cost subject to storage size constraint [START_REF] Gupta | Selection of views to materialize in a data warehouse[END_REF];

minimizing query cost and maintenance cost subject to storage space constraint [START_REF] Lawrence | Dynamic view selection for OLAP[END_REF];

minimizing query cost under a maintenance constraint [START_REF] Gupta | Selection and maintenance of views in a data warehouse[END_REF], and minimizing query processing and energy consumption under storage constraint [START_REF] Roukh | Eco-dmw: Eco-design methodology for data warehouses[END_REF].

The problems corresponding to these variants known as an NP-hard problem [START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF]. Several algorithms were proposed to deal with variants. For a complete classication of these algorithms, we recommend the readers to refer to the survey paper of Mami et al. [START_REF] Mami | A survey of view selection methods[END_REF] which divides algorithms in the following categories: deterministic algorithms [START_REF] Shukla | Materialized view selection for multidimensional datasets[END_REF][START_REF] De Souza | Ecient materialization and use of views in data warehouses[END_REF][START_REF] Theodoratos | Data warehouse conguration[END_REF], randomized algorithms [START_REF] Ioannidis | Randomized algorithms for optimizing large join queries[END_REF], evolutionary algorithms [START_REF] Roukh | Eco-dmw: Eco-design methodology for data warehouses[END_REF] and hybrid algorithms [START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF].

The analysis of dierent variants of the VSP allows us giving a multidimensional representation (called the VSP cube) of these studies including three dimensions which are: Non-functional requirements, used algorithms, and constraints (Figure2.9). This cube can instantiate any work dealing with the VSP. views in a static manner, where it assumes that the queries are a priori known [START_REF] Gupta | Selection of views to materialize in a data warehouse[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF]. To relax this hypothesis, a dynamic selection has been proposed. Algorithms in this selection may be divided into two categories, based on their incoming workload [START_REF] Daneshpour | Dynamic view management system for query prediction to view materialization[END_REF]: algorithms in the rst category suppose that the query workload is predened [START_REF] Phan | Dynamic materialization of query views for data warehouse workloads[END_REF], whereas in the second category, the workload is unknown [START_REF] Kotidis | Dynamat: a dynamic view management system for data warehouses[END_REF][START_REF] Scheuermann | Watchman: A data warehouse intelligent cache manager[END_REF].

Our discussion on MV selection algorithms is guided by two dimensions: the constraints and the N F R.

Chronologically, the rst studies related to the VSP assume the absence of the constraints [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Yang | A framework for designing materialized views in data warehousing environment[END_REF]. After that and due to the large size of the stored selected materialized views, the storage space becomes the main constraint that the selection process has to integrated [START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF]. Then, maintenance cost becomes an important parameter since the selected materialized views need to be updated once the base tables change [START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF]. Some studies considered both constraints [START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF].

N F R that the selected materialized views have to satisfy span several objectives: the minimization of query response time [START_REF] Ross | Materialized view maintenance and integrity constraint checking: Trading space for time[END_REF], the satisfaction of the maintenance cost [START_REF] Gupta | Selection of views to materialize in a data warehouse[END_REF].

Recently, we enriched these objectives by considering the energy consumption when executing a workload [START_REF] Roukh | Eco-dmw: Eco-design methodology for data warehouses[END_REF]. These objectives may be combined to give rise a multi-objective formalization of the problem of materialized view section problem such as in [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF] (where response time and maintenance cost were considered) and in [START_REF] Roukh | Eco-dmw: Eco-design methodology for data warehouses[END_REF] (where response time and consuming energy are used).

The process of selecting materialized views passes through the identication of view candidates to be materialized. The number of these views can be very large [START_REF] Gupta | Selection and maintenance of views in a data warehouse[END_REF]. Several research eorts have been conducted to represent eciently the search space of the VSP. Many data structures

Q Q Fig. 2.

Example of AND-OR graph

Q Q Q Q R1 R2 R3 R4 R5 Fig. 2.11 Example of acyclic graph V 1 V 3 V 8 None V 4 V 5 V 2 V 7
Fig. Syntactical Analysis: is a technique used by many algorithms that identify the candidate views directly by analysing synthetically the workload [5,[START_REF] Chaves | Towards materialized view selection for distributed databases[END_REF].

Query plan: it has been used by some algorithms to identify candidate views and rewrite queries [START_REF] Theodoratos | View selection for designing the global data warehouse[END_REF][START_REF] Theodoratos | Data warehouse conguration[END_REF].

VSP may be either combined or not with the MQO problem. The work of Yang et al. [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF] is the pioneer in the context of DW that deals with two interdependent problems: (a) constructing an optimal global plan of queries and (b) use this plan to select views to be materialized. MVPP and the plan with the minimum cost will be chosen. This algorithm is costly in terms of computation. To simplify the previous algorithm, a second algorithm is proposed based on 0-1 integer programming. The view selection algorithm is performed in two steps: (1) generation of materialized views candidates which have positive benet between query processing and view maintenance. This benet corresponds to the sum of query processing using the view minus the maintenance cost of this view, (2) only candidate nodes with positive benet are selected to be materialized [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Yang | A framework for designing materialized views in data warehousing environment[END_REF].

In [START_REF] Goasdoué | View selection in semantic web databases[END_REF][START_REF] Bery | Conception physique des bases de données a base ontologique : le cas des vues matérialisées[END_REF], a connection between MQO and the process of selecting materialized views for Sparql queries in the context of semantic databases has been established.

Based on this discussion, the traditional classication proposed in [START_REF] Mami | A survey of view selection methods[END_REF][START_REF] Roukh | Eco-dmw: Eco-design methodology for data warehouses[END_REF] can be enriched.

In addition to the traditional dimensions (the used constraints, non-functional requirements, type of selection algorithms), we can include other dimensions such as: nature of the selection (static/dynamic), used data structures to represent the search space, involving MQO. Figure 2.13 summarizes this classication.

View maintenance problem. Note that materialized views store data from base tables. In order to keep the views in the data warehouse up to date, it is necessary to maintain them in response to the changes at the base tables. This process of updating views is called view maintenance which has generated a great deal of interest in the past years. Views can be either recomputed from scratch, or incrementally maintained by propagating the base data changes onto the views. As re-computing the views can be prohibitively expensive, the incremental maintenance of views is of signicant value [START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF].

Data Partitioning . Data partitioning is an OS that divides the data of database into distinct small parts called fragment. It aims at minimizing the unnecessary accesses to tables.

Initially, it is considered as a logical database design technique which facilitates ecient execution of queries by reducing the irrelevant data accessed [START_REF] Bellatreche | Algorithms and support for horizontal class partitioning in object-oriented databases[END_REF]. Nowadays, it is one of important aspect of physical design [6]. It is a divide-and-conquer approach that improves query performance, operational scalability, and the management of ever-increasing amounts of data. Constraints Unbounded [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Theodoratos | Data warehouse conguration[END_REF] DiskSpace [START_REF] Theodoratos | View selection for designing the global data warehouse[END_REF][START_REF] Harinarayan | Implementing data cubes eciently[END_REF]5] Update cost [START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF][START_REF] Mami | Modeling view selection as a constraint satisfaction problem[END_REF] Performance guarantee [START_REF] Hanusse | A view selection algorithm with performance guarantee[END_REF] The both [START_REF] Mami | Modeling view selection as a constraint satisfaction problem[END_REF] Data Structures AND/OR Graph [START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF][START_REF] Baril | Selection of materialized views: A cost-based approach[END_REF][START_REF] Derakhshan | Parallel simulated annealing for materialized view selection in data warehousing environments[END_REF] MVPP [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF] Lattice [START_REF] Harinarayan | Implementing data cubes eciently[END_REF][START_REF] Kalnis | View selection using randomized search[END_REF][START_REF] Yu | Materialized view selection as constrained evolutionary optimization[END_REF] Syntactical Analysis [5,[START_REF] Chaves | Towards materialized view selection for distributed databases[END_REF] Query plan [START_REF] Theodoratos | View selection for designing the global data warehouse[END_REF][START_REF] Theodoratos | Data warehouse conguration[END_REF] Algorithms Deterministic [START_REF] Ross | Materialized view maintenance and integrity constraint checking: Trading space for time[END_REF][START_REF] Harinarayan | Implementing data cubes eciently[END_REF] Randomize [START_REF] Yu | Materialized view selection as constrained evolutionary optimization[END_REF][START_REF] Derakhshan | Parallel simulated annealing for materialized view selection in data warehousing environments[END_REF][START_REF] Kalnis | View selection using randomized search[END_REF] Evolutionary [START_REF] Horng | Materialized view selection using genetic algorithms in a data warehouse system[END_REF][START_REF] Zhang | Genetic algorithm for materialized view selection in data warehouse environments[END_REF] Hybrid [START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF][START_REF] Mami | Modeling view selection as a constraint satisfaction problem[END_REF]

MQO

Using MQO [START_REF] Mistry | Materialized view selection and maintenance using multi-query optimization[END_REF][START_REF] Roy | Ecient and extensible algorithms for multi query optimization[END_REF][START_REF] Mistry | Materialized view selection and maintenance using multi-query optimization[END_REF] Without [START_REF] Shukla | Materialized view selection for multidimensional datasets[END_REF][START_REF] Shukla | Materialized view selection for multidimensional datasets[END_REF][START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF][START_REF] Ioannidis | Randomized algorithms for optimizing large join queries[END_REF] Goal Maintenance [START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF] Processing [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Zhang | Genetic algorithm for materialized view selection in data warehouse environments[END_REF][START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF] Fig. 2.13 Classication of view selection techniques also been widely used in the distributed and parallel databases.

Three types of data partitioning exists: horizontal, vertical and mixed.

Horizontal data partitioning allows tables, indexes and materialized views to be partitioned into disjoint sets of rows that are physically stored and accessed separately [6] or in parallel. Horizontal partitioning may have a signicant impact on performance of queries and manageability of very large data warehouses. It has the ability to be combined with other optimization structures like indexes, materialized views. Splitting a table, a materialized view or an index into smaller pieces makes all operations on individual pieces much faster. Contrary to materialized views and indexes, data partitioning does not replicate data, thereby reducing space requirements and minimizing update overhead [START_REF] Papadomanolakis | Autopart: Automating schema design for large scientic databases using data partitioning[END_REF].

A native database denition language support is available for horizontal partitioning, where several fragmentation modes are available in Oracle 11G DBMS: range, list and hash. In the range partitioning, an access path ( In the context of relational data warehouse, derived horizontal partitioning is well adapted.

In other words, to partition a data warehouse, the best way is to partition some/all dimension tables using their predicates, and then partition the fact table based on the fragmentation schemas of dimension tables [START_REF] Bellatreche | Referential horizontal partitioning selection problem in data warehouses: Hardness study and selection algorithms[END_REF]. This fragmentation takes into consideration star join queries requirements (these queries impose restrictions on the dimension values that are used for selecting specic facts; these facts are further grouped and aggregated according to the user demands). To illustrate this fragmentation, let us suppose a relational warehouse modelled by a star schema with d dimension tables and a fact table F . Among these dimension tables, g tables are fragmented (g ≤ d). Each dimension table

D i (1 ≤ i ≤ g) is partitioned into m i fragments: {D i1 , D i2 , ..., D im i }, where each fragment D ij is dened as: D ij = σ cl i j (D i ), where cl i j and σ (1 ≤ i ≤ g, 1 ≤ j ≤ m i ) represent a conjunction of simple
predicates and the selection operator, respectively. Thus, the fragmentation schema of the fact table F is dened as follows:

F i = F D 1j D 2k ... D gl , (1 ≤ i ≤ m i ),
where represents the semi join operation.

The number of schemes N equals to the number of fragments of fact tables and can be as the product of the number of fragments of each dimension tables.

N = d i=1 F rag i (2.1)
which F rag i is the number of fragments of g dimension tables.

Derived horizontal partitioning (or referential partitioning in Oracle DBMS) has two main advantages in relational data warehouses, in addition to classical benets of data partitioning: (1) pre-computing joins between fact table and dimension tables participating in the fragmentation process of the fact table [START_REF] Bellatreche | Pruning search space of physical database design[END_REF] and (2) optimizing selections dened on dimension tables.

The derived horizontal partitioning of a DW has been formalized as follows [START_REF] Bellatreche | Referential horizontal partitioning selection problem in data warehouses: Hardness study and selection algorithms[END_REF]: Given:

DW with a set of d dimension tables {D 1 , D 2 , ..., D d } and a fact table F ; a workload of queries Q and a maintenance constraint W xed by DBA that represents the maximal number of fact fragments that he/she can maintain.

The referential horizontal partitioning problem consists in (1) identifying candidate dimension table(s), (2) splitting them using single partitioning mode and (3) using their partitioning schemes to decompose the fact table into N fragments, such that: (a) the cost of evaluating all queries is minimized and (b) N ≤ W . This problem has been proven as a NP-complete problem [START_REF] Bellatreche | Referential horizontal partitioning selection problem in data warehouses: Hardness study and selection algorithms[END_REF].

Vertical data partitioning can be viewed as a redundant structure even if it results in little storage overhead. The vertical partitioning of a table T splits it into two or more tables, called, sub-tables or vertical fragments, each of which contains a subset of the columns in T . Note that the key columns are duplicated in each vertical fragment, to allow "reconstruction" of an original row in T . Since many queries access only a small subset of the columns in a table, vertical partitioning can reduce the amount of data that needs to be scanned to answer the query. Unlike horizontal partitioning, indexes or materialized views, in most of today's commercial database systems there is no native database denition language support for dening vertical partitions of a table [6].

To vertically partition a table with m non primary keys, the number of possible fragments is equal to B(m), which is the m th Bell number [START_REF] Özsu | Principles of distributed database systems[END_REF]. For large values of m, B(m) ∼ = m m . For example, for m = 10; B(10) ∼ = 115 975. These values indicate that it is futile to attempt to obtain optimal solutions to the vertical partitioning problem. Many algorithms were proposed and classied into two categories: grouping and splitting [START_REF] Özsu | Principles of distributed database systems[END_REF]. Grouping starts by assigning each attribute to one fragment, and at each step, joins some fragments until some criteria is satised. Splitting starts with a table and decides on benecial partitioning based on the query frequencies.

In the data warehousing environment, [START_REF] Golfarelli | Materialization of fragmented views in multidimensional databases[END_REF] proposed an approach for materializing views in vertical fragments, each including a subset of measures possibly taken from dierent cubes, aggregated on the same grouping set. This approach may unify two or more views into a single fragment.

The above partitioning techniques can be mixed. In this thesis, we mainly focus on horizontal data partitioning.

Classical methodology of HDP In DW, horizontal data partitioning follows two main phases [START_REF] Boukhalfa | De la conception physique aux outils d administration et de tuning des entrepôts de données[END_REF]:

preparation phase: in this phase selection predicates and candidate tables are identied.

Once this identication done, each domain of a fragmentation attribute (belonging to a selection predicate) is divided into sub-domains. Finally, the set of minterms is generated [START_REF] Özsu | Principles of distributed database systems[END_REF] selection phase that identies the nal partitioning schema using a given algorithm.

Correction rules for HDP In horizontal data partitioning, the partitioning process is veried using three rules: completeness, disjunction, reconstruction [START_REF] Boukhalfa | De la conception physique aux outils d administration et de tuning des entrepôts de données[END_REF]. To understand these rules, we suppose that we have a table T partitioned into k fragments {T 1 , .., T k }.

Completeness: means that for all tuples in the table T must be existing at list in one fragment

T i , 1 ≤ i ≤ k.
This rule ensures that no loss of data and all data exist in the partitioned schema.

Disjunction: means that for all instances i in the fragment T j , no other fragment T k that contains this instance i. This rules ensures that non redundant of data.

Reconstruction: means that the original table T can be formed using the set of fragments

T i , 1 ≤ i ≤ k.
This rule ensures that data partitioning is a reversible operation.

A Taxonomy of data partitioning approaches Due to its importance, the data partitioning has been widely studied in the literature. By analysing these studies, we propose to classify using the following criteria: type of partitioning, type of databases, type of algorithms, the platform and the using of data structure (Figure 2.15).

Type of partition: There are three types of data partitions, vertical data partition [START_REF] Navathe | Vertical partitioning algorithms for database design[END_REF][START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF], horizontal data partitioning [START_REF] Bellatreche | Utilisation des vues materialisees, des index et de la fragmentation dans la conception logique et physique d'un entrepot de donnees[END_REF][START_REF] Cuzzocrea | Fragmenting very large xml data warehouses via k-means clustering algorithm[END_REF][START_REF] Taniar | A taxonomy of indexing schemes for parallel database systems[END_REF][START_REF] Zilio | Partitioning key selection for a sharednothing parallel database system[END_REF], and hybrid data partitioning [START_REF] Boukhalfa | De la conception physique aux outils d administration et de tuning des entrepôts de données[END_REF][START_REF] Dageville | Automatic sql tuning in oracle 10g[END_REF][START_REF] Rao | Automating physical database design in a parallel database[END_REF][START_REF] Stöhr | Warlock: A data allocation tool for parallel warehouses[END_REF][START_REF] Nehme | Automated partitioning design in parallel database systems[END_REF][START_REF] Pavlo | Skew-aware automatic database partitioning in shared-nothing, parallel oltp systems[END_REF].

Type of database: Data partitioning has been applied in all database generations: relational databases [START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF][START_REF] Gorla | Strategic Advancements in Utilizing Data Mining and Warehousing Technologies: New Concepts and Developments: New Concepts and Developments[END_REF], object-databases [START_REF] Rao | Automating physical database design in a parallel database[END_REF][START_REF] Nehme | Automated partitioning design in parallel database systems[END_REF][START_REF] Navathe | A mixed fragmentation methodology for initial distributed database design[END_REF][START_REF] Bellatreche | Vertical fragmentation in distributed object database systems with complex attributes and methods[END_REF], deductive database [START_REF] Mohania | Some issues in design of distributed deductive databases[END_REF], DW [START_REF] Bellatreche | Utilisation des vues materialisees, des index et de la fragmentation dans la conception logique et physique d'un entrepot de donnees[END_REF][START_REF] Boukhalfa | De la conception physique aux outils d administration et de tuning des entrepôts de données[END_REF][START_REF] Noaman | A horizontal fragmentation algorithm for the fact relation in a distributed data warehouse[END_REF], and recently in graph databases [START_REF] Peng | Query workload-based RDF graph fragmentation and allocation[END_REF]. Also data partitioning are applied on some optimization structures like indexes [START_REF] Taniar | A taxonomy of indexing schemes for parallel database systems[END_REF].

The used Algorithms: In the rst generation of the existing work, the problem is treated without any constraint: based on Minterms [START_REF] Ceri | Horizontal data partitioning in database design[END_REF][START_REF] Özsu | Principles of distributed database systems[END_REF] or anity [START_REF] Karlapalem | Redesign of distributed relational databases[END_REF]. In the second generation, the maintenance constraint is considered that is dened by the maximum number of fragments, in which cost based approaches have been proposed [START_REF] Bellatreche | Algorithms and support for horizontal class partitioning in object-oriented databases[END_REF]. In this generation, others techniques based on data mining are proposed [START_REF] Mahboubi | Enhancing xml data warehouse query performance by fragmentation[END_REF]. Choosing the best predicates is not a easy task. Another point is the ignorance of the interaction between queries, except the work of Kerkad et al. [START_REF] Kerkad | Queen-bee: query interaction-aware for buer allocation and scheduling problem[END_REF][START_REF] Kerkad | L'interaction au service de l'optimisation à grande èchelle des entrepôts de données relationnels[END_REF]. Figure 2.14 shows the evolution approaches of HDP.

Hard approaches (Minterms)

Simple approaches (Affinity) Cost Model Based approaches

Data Mining Based approaches

Query Interaction Based approaches

Fig. 2.14 The evolution of HDP approaches

Platforms: used to allocate the fragments dierentiate data partitioning approach, in which it can be centralized platform [START_REF] Boukhalfa | De la conception physique aux outils d administration et de tuning des entrepôts de données[END_REF][START_REF] Bellatreche | Utilisation des vues materialisees, des index et de la fragmentation dans la conception logique et physique d'un entrepot de donnees[END_REF][START_REF] Cuzzocrea | Fragmenting very large xml data warehouses via k-means clustering algorithm[END_REF][START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF][START_REF] Navathe | Vertical partitioning algorithms for database design[END_REF][START_REF] Gorla | Strategic Advancements in Utilizing Data Mining and Warehousing Technologies: New Concepts and Developments: New Concepts and Developments[END_REF][START_REF] Cheng | A genetic algorithm-based clustering approach for database partitioning[END_REF], distributed platform [START_REF] Bellatreche | Vertical fragmentation in distributed object database systems with complex attributes and methods[END_REF][START_REF] Navathe | A mixed fragmentation methodology for initial distributed database design[END_REF][START_REF] Noaman | A horizontal fragmentation algorithm for the fact relation in a distributed data warehouse[END_REF] or parallel platform [START_REF] Zilio | Partitioning key selection for a sharednothing parallel database system[END_REF][START_REF] Stöhr | Warlock: A data allocation tool for parallel warehouses[END_REF][START_REF] Rao | Automating physical database design in a parallel database[END_REF][START_REF] Taniar | A taxonomy of indexing schemes for parallel database systems[END_REF][START_REF] Nehme | Automated partitioning design in parallel database systems[END_REF][START_REF] Pavlo | Skew-aware automatic database partitioning in shared-nothing, parallel oltp systems[END_REF][START_REF] Datta | A case for parallelism in data warehousing and olap[END_REF].

Data structures: used to represent the candidates or the result of the process of data partitioning, in which, the most used is the array structures like anity Matrix [START_REF] Navathe | Vertical partitioning algorithms for database design[END_REF][START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF], graphs [START_REF] Wu | An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation[END_REF] and hypergraphs [START_REF] Curino | Schism: a workload-driven approach to database replication and partitioning[END_REF];

III.3.3. HDP in Distributed Environments

In the context of distributed databases, the fragmentation/partitioning is tightly coupled with the so-called fragment allocation problem [START_REF] Hauglid | Dyfram: dynamic fragmentation and replica management in distributed database systems[END_REF]. Indeed, in real-life application scenarios, these two processes, even thought inter-related, are tackled in an isolated manner. This evidence has generated two dierent research contexts. The rst one is focused on the data fragmentation problem, whereas the second one on the issue of allocating partition-generated fragments. Also, this dichotomy implies the presence of two dierent cost models for the fragmentation and allocation phases, respectively. As a consequence, the fragmentation cost model very often does not Data partition methods Type of partitioning HDP [START_REF] Bellatreche | Utilisation des vues materialisees, des index et de la fragmentation dans la conception logique et physique d'un entrepot de donnees[END_REF][START_REF] Cuzzocrea | Fragmenting very large xml data warehouses via k-means clustering algorithm[END_REF][START_REF] Taniar | A taxonomy of indexing schemes for parallel database systems[END_REF] Vertical [START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF][START_REF] Navathe | Vertical partitioning algorithms for database design[END_REF][START_REF] Gorla | Strategic Advancements in Utilizing Data Mining and Warehousing Technologies: New Concepts and Developments: New Concepts and Developments[END_REF] Mixed [START_REF] Cheng | A genetic algorithm-based clustering approach for database partitioning[END_REF][START_REF] Navathe | A mixed fragmentation methodology for initial distributed database design[END_REF] Type of databases Database [START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF][START_REF] Gorla | Strategic Advancements in Utilizing Data Mining and Warehousing Technologies: New Concepts and Developments: New Concepts and Developments[END_REF] Object DB [START_REF] Navathe | A mixed fragmentation methodology for initial distributed database design[END_REF][START_REF] Bellatreche | Vertical fragmentation in distributed object database systems with complex attributes and methods[END_REF] DW [START_REF] Bellatreche | Utilisation des vues materialisees, des index et de la fragmentation dans la conception logique et physique d'un entrepot de donnees[END_REF][START_REF] Boukhalfa | De la conception physique aux outils d administration et de tuning des entrepôts de données[END_REF][START_REF] Noaman | A horizontal fragmentation algorithm for the fact relation in a distributed data warehouse[END_REF] Index [START_REF] Taniar | A taxonomy of indexing schemes for parallel database systems[END_REF] XML DB [START_REF] Cuzzocrea | Fragmenting very large xml data warehouses via k-means clustering algorithm[END_REF] Partitioning Algrithms Anity [START_REF] Navathe | Vertical partitioning algorithms for database design[END_REF][START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF] Glouton [START_REF] Datta | A case for parallelism in data warehousing and olap[END_REF][START_REF] Rao | Automating physical database design in a parallel database[END_REF][START_REF] Stöhr | Warlock: A data allocation tool for parallel warehouses[END_REF] Data Mining [START_REF] Cuzzocrea | Fragmenting very large xml data warehouses via k-means clustering algorithm[END_REF][START_REF] Cheng | A genetic algorithm-based clustering approach for database partitioning[END_REF] Genetic [START_REF] Nehme | Automated partitioning design in parallel database systems[END_REF] Gl+Graph [START_REF] Bellatreche | Utilisation des vues materialisees, des index et de la fragmentation dans la conception logique et physique d'un entrepot de donnees[END_REF][START_REF] Noaman | A horizontal fragmentation algorithm for the fact relation in a distributed data warehouse[END_REF][START_REF] Gorla | Strategic Advancements in Utilizing Data Mining and Warehousing Technologies: New Concepts and Developments: New Concepts and Developments[END_REF] Deploiement plateform Centralized [START_REF] Boukhalfa | De la conception physique aux outils d administration et de tuning des entrepôts de données[END_REF][START_REF] Bellatreche | Utilisation des vues materialisees, des index et de la fragmentation dans la conception logique et physique d'un entrepot de donnees[END_REF][START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF] Distributed [START_REF] Bellatreche | Vertical fragmentation in distributed object database systems with complex attributes and methods[END_REF][START_REF] Navathe | A mixed fragmentation methodology for initial distributed database design[END_REF][START_REF] Noaman | A horizontal fragmentation algorithm for the fact relation in a distributed data warehouse[END_REF] Parallel [START_REF] Taniar | A taxonomy of indexing schemes for parallel database systems[END_REF][START_REF] Pavlo | Skew-aware automatic database partitioning in shared-nothing, parallel oltp systems[END_REF][START_REF] Datta | A case for parallelism in data warehousing and olap[END_REF] Data Structure Graph [START_REF] Wu | An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation[END_REF] Matrix [START_REF] Navathe | Vertical partitioning algorithms for database design[END_REF][START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF] Hypergraph [START_REF] Curino | Schism: a workload-driven approach to database replication and partitioning[END_REF] Fig. 2.15 Taxonomy of data partitioning methods take into account the yet-relevant allocation parameters. To face-o deriving drawbacks, several approaches have been proposed with the goal of integrating the two distinct fragmentation and allocation processes, usually according to a sequential manner.

In line with this approach, Furtado [START_REF] Furtado | Experimental evidence on partitioning in parallel data warehouses[END_REF] discusses partitioning strategies for node-partitioned data warehouses. The main suggestion coming from [START_REF] Furtado | Experimental evidence on partitioning in parallel data warehouses[END_REF] can be synthesized in a best-practice recommendation stating to partition the fact table on the basis of the larger dimension tables (given a ranking threshold). In more detail, each larger dimension table is rst partitioned by means of the Hash mode approach via its primary key. Then, the fact table is again partitioned by means of the Hash mode approach via foreign keys referencing the larger dimension tables. Finally, the so-generated fragments are allocated according to two alternative strategies, namely round robin and random. Smaller dimension tables are instead fully-replicated across the nodes of the target data warehouse. The fragmentation approach [START_REF] Furtado | Experimental evidence on partitioning in parallel data warehouses[END_REF] does not take into account specic star query requirements, being such queries very often executed against data warehouses, and it does not consider the critical issues of controlling the number of generated fragments, like in [START_REF] Stöhr | Multi-dimensional database allocation for parallel data warehouses[END_REF][START_REF] Bellatreche | Referential horizontal partitioning selection problem in data warehouses: Hardness study and selection algorithms[END_REF].

In [START_REF] Lima | Parallel OLAP query processing in database clusters with data replication[END_REF], Lima et al. focus the attention on data allocation issues for database clusters. Authors recognize that how to place data/fragments on the dierent PC of a database cluster in the dependence of a given criterion/goal (e.g., query performance) plays a critical role, hence the following two straightforward approaches can be advocated: (i ) full replication of the target database on all the PC, or (ii ) meaningful partition of data/fragments across the PC. Starting from this main intuition, authors propose an approach that combines partition and replication for OLAP-style workloads against database clusters. In more detail, the fact table is partitioned and replicated across nodes using the so-called chained de-clustering, while dimension tables are fully-replicated across nodes. This comprehensive approach enables the middleware layer to perform load balancing tasks among replicas, with the goal of improving query response time.

Furthermore, the usage of chained de-clustering for replicating fact table partitions across nodes allows the designer not to detail the way of selecting the number of replicas to be used during the replication phase. Just like [START_REF] Furtado | Experimental evidence on partitioning in parallel data warehouses[END_REF], [START_REF] Lima | Parallel OLAP query processing in database clusters with data replication[END_REF] does not control the number of generated fact table fragments.

In [START_REF] Stöhr | Multi-dimensional database allocation for parallel data warehouses[END_REF], Stöhr et al. propose an approach for constructing and managing a data warehouse on a disk-shared parallel machine having K disks. Here, the data warehouse is modeled via a star schema with one fact table and a number of dimension tables. The fragmentation process is performed as follows: each dimension table is virtually partitioned by means of the Interval mode on attributes belonging to the lower levels of dimensional hierarchies, and the fact table is consequentially partitioned on the basis of so-partitioned dimension tables. Dimension tables and ad-hoc B -tree indexing data structures are duplicated over each disk of the parallel machine. To speed-up queries, bitmap join indexes are selected over fact table fragments via using attributes of dimension tables belonging to the higher levels of dimensional hierarchies.

Note that this approach may generate a number of fragments N F largely greater than the available number of disks K. To ensure a high parallelism degree and ecient load balancing, a round robin allocation of fact fragments and associated bitmap indexes over the K disks is nally performed, with the goal of placing bitmap indexes that are associated to the same fact fragment onto consecutive disks. In [START_REF] Stöhr | Warlock: A data allocation tool for parallel warehouses[END_REF], the same authors further extend they research by proposing a data allocation tool, called Warlock, for parallel data warehouses. The novelty of Warlock consists in taking into account the number of nal fact fragments that the designer is interested to. Finally, in [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF] an innovative design methodology for data warehouses over sharednothing architectures that initially argues to perform fragmentation and allocation jointly is proposed. Table 2.1 summarizes main characteristics of comparison approaches for designing data warehouses in distributed environments via fragmentation and allocation paradigms. Index selection problem. The task of index selection is to automatically select an appropriate set of indices for a data warehouse (having a fact table and dimension tables) and a workload under resource constraints (storage, maintenance, etc.). It is challenging for the following reasons [START_REF] Chaudhuri | Index selection for databases: A hardness study and a principled heuristic solution[END_REF]: The size of a relational data warehouse schema may be large (many tables with several columns), and indices can be dened on a set of columns. Therefore, the search space of indices that are relevant to a workload can be very large [START_REF] Bellatreche | A data mining approach for selecting bitmap join indices[END_REF]. To deal with this problem, most selection approaches use two main phases: (1) generation of candidate attributes and (2) selection of a nal conguration. The rst phase prunes the search space of index selection problem, by eliminating non relevant attributes. In the second phase, the nal indices are selected using greedy algorithms [START_REF] Chaudhuri | An ecient, cost-driven index selection tool for microsoft sql server[END_REF], linear programming algorithms [START_REF] Chaudhuri | Index selection for databases: A hardness study and a principled heuristic solution[END_REF], etc. The quality of the nal set of indices depends essentially on the pruning phase. To prune the search space of index candidates, many approaches were proposed [START_REF] Chaudhuri | Index selection for databases: A hardness study and a principled heuristic solution[END_REF][START_REF] Bellatreche | A data mining approach for selecting bitmap join indices[END_REF][START_REF] Bellatreche | Pruning search space of physical database design[END_REF], that can be classied into two categories: heuristic enumeration-driven approaches and data mining driven approaches.

In heuristic enumeration-driven approaches, heuristics are used. For instance, in [START_REF] Chaudhuri | An ecient, cost-driven index selection tool for microsoft sql server[END_REF], a greedy algorithm is proposed that uses optimizer cost of SQL Server to accept or reject a given conguration of indices. The weakness of this work is that it imposes the number of generated candidates. IBM DB2 Advisor is another example belonging to this category [START_REF] Valentin | Db2 advisor: An optimizer smart enough to recommend its own indexes[END_REF], where the query parser is used to pick up selection attributes used in workload queries. The generated candidates are obtained by a few simple combinations of selection attributes [START_REF] Valentin | Db2 advisor: An optimizer smart enough to recommend its own indexes[END_REF].

In data mining-driven approaches, the pruning process is done using data mining techniques, like in [START_REF] Bellatreche | A data mining approach for selecting bitmap join indices[END_REF]. In this approach, the number of index candidates is not a priori known as in the rst category. The basic idea is to generate frequent closed itemsets representing groups of attributes that could participate in selecting the nal conguration of bitmap join indexes. A data mining based approach has been developed for selecting bitmap join indexes [START_REF] Bellatreche | A data mining approach for selecting bitmap join indices[END_REF].

III.3.4. MQO and physical design problems

In the section, we present the unication of the problem of MQO and the physical design.

MQO and MV problems MQO contributes largely in dierent stages of materialized views:

in the selection of the best views [START_REF] Baralis | Materialized view selection in a multidimensional database[END_REF][START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF] and in their maintenance [START_REF] Herzog | Global optimization and parallelization of integrity constraint checks[END_REF][START_REF] Mistry | Materialized view selection and maintenance using multi-query optimization[END_REF][START_REF] Ross | Materialized view maintenance and integrity constraint checking: Trading space for time[END_REF].

Construction of the UQP is performed following a bottom up scenario. Initially, the authors select the join local plans of each query. These plans are merged in a single UQP, called in [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF] Multi-Views Processing Plan (MVPP). Each intermediate node of the MVPP is tagged with the cost of the processing data and the maintenance cost in the case if it is materialized.

Then, the MVPP is used as an input for selection algorithms.

MQO and data partitioning problems

To the best of our knowledge, the work proposed by Kerkad et al. [START_REF] Bellatreche | Roupar: Routinely and mixed querydriven approach for data partitioning[END_REF] is the only work that exploits query interaction for resolving the problem of horizontal data partitioning in the context of relational data warehouses. More correctly, it uses the sub-domains of attributes obtained by applying selection predicates of the queries to prune the search space of the horizontal partitioning problem and identies the selection predicates candidates for partitioning by considering the most inuenced attributes and their sub-domains in terms of reducing the cost of the UQP.

MQO and Buer management and query scheduling

The query ordering has used to improve MQO algorithm [START_REF] Cosar | Multiple query optimization with depth-rst branch-and-bound and dynamic query ordering[END_REF]. Hence, Kerkad et al., [START_REF] Kerkad | Queen-bee: query interaction-aware for buer allocation and scheduling problem[END_REF], have proposed a new technique of using intermediate results to solve the buer management and query scheduling problems, in which the intermediate results have been used to dene a strategy for managing the buer (allocation/deallocation) and schedule queries. In [START_REF] Zukowski | Cooperative scans: dynamic bandwidth sharing in a dbms[END_REF] a cooperative scans have been proposed

to improve sharing between queries by dynamic scheduling queries that share the scans of data from base tables.

MQO and caching of query results

Another related area is caching of query results. MQO can optimize a batch of queries given together, caching takes a sequence of queries over time, deciding what to materialize and keep in the cache as each query is processed [START_REF] Zhao | Simultaneous optimization and evaluation of multiple dimensional queries[END_REF][START_REF] Kotidis | Dynamat: a dynamic view management system for data warehouses[END_REF][START_REF] Chen | The implementation and performance evaluation of the adms query optimizer: Integrating query result caching and matching[END_REF].

It should be noticed that the algorithms used in these dierent selections are workload sensitive.

Since, the used queries are too small, these algorithms may suer from scalability in the context of big queries.

The queries are also one of the main components of the deployment phase that we discuss it in the following section.

III.4. Dimension 4: Deployment Phase

The DBMS hosting a DW application is deployed in a hardware platform that oers storage layers. It should be noticed that the logical and physical optimizations strongly depends on the deployment platforms of the target DW. The deployment phase of the life cycle design of DW uses is one of the consumers of OLAP queries. There exist two fundamental types of architecture suitable for deploying database applications. The most well-known and ubiquitous architectural type is the centralized DBMS architecture. It is very well dened and mature. The other type is distributed and parallel DBMS.

In this section, we consider an example of parallel DW. This is motivated by the spectacular explosion of the data volume and the queries. The terms "parallel DW " and distributed /dw are very often used interchangeably. In practice, however, the distinction between the two has historically been quite signicant. Distributed DWs, much like distributed databases, grew out of a need to place processing logic and data in proximity to the users who might be utilizing them. In general, multi-location organizations (motivated by globalization) consist of a few distinct sites, each typically associated with a subset of the information contained in the global data pool. In the DW context, this has traditionally led to the development of some form of federated architecture. In contrast to monolithic, centralized DWs, federated models are usually constructed as a cooperative coalition of departmental or process specic data marts [START_REF] Bellatreche | What can partitioning do for your data warehouses and data marts? In IDEAS[END_REF]. For the most part, design and implementation issues in such environments are similar to those of distributed operational DBMS [START_REF] Özsu | Principles of distributed database systems[END_REF]. For example, it is important to provide a single transparent conceptual model for the distinct sites and to divide data to reduce the eects of network latency and bandwidth limitations.

Choice of the Platform Data Partitioning

Fragment Allocation

Fragment Replication

Query Processing

Load Balancing

Fig. 2.16 Life cycle of the parallel database design

Designing a parallel DW goes through a well-identied life cycle including six main steps (Figure 2.16) [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF]: (1) choosing the hardware architecture, (2) partitioning the target DW, (3) allocating the so-generated fragments over available nodes, (4) replicating fragments for eciency purposes, (5) dening ecient query processing strategies and (6) dening ecient load balancing strategies. Each one of these steps will be detailed in the following paragraphs.

1. The choice of the platform: The choice of the deployment platform is a pre-condition to achieve the scalability and availability of data. Hardware architectures are classied into ve main categories: (i) shared-memory, (ii) shared-disk, (iii) shared-nothing, (iv) shared-something and (v) shared-everything. As we said before, the Shared-everything architecture has been adopted by DW for parallelization purpose. Shared memory and shared disk architectures have the advantage that they are relatively easy to administer as the hardware transparently performs much of the magic. This architecture has been recommended by the leaders of Gamma project as the reference architecture for supporting high-performance data warehouses modelled in terms of relational star schemes. That being said, shared everything designs also tend to be quite expensive and have limited scalability in terms of both the CPU count and the number of available disk heads. In Petabyte-scale DW environments, either or both of these constraints might represent a serious performance limitation. As the choice of the hardware architecture is inuenced by price, high-performance features, extensibility and data availability, clusters of workstations are very often used as a valid alternative to Shared-Nothing architectures (e.g., [START_REF] Lima | Parallel OLAP query processing in database clusters with data replication[END_REF]). Figure 2.17 summarizes these architectures. 3. Data allocation consists in placing generated fragments over nodes of a reference paral-CHAPTER 2. BACKGROUND & STATE OF ART lel machine. This allocation may be either redundant (with replication) or non-redundant (without replication) [START_REF] Apers | Data allocation in distributed database systems[END_REF]. Once fragments are placed, global queries are executed over the processing nodes according to parallel computing paradigms. In more detail, parallel query processing on top of a parallel DW (a critical task within the family of parallel computing tasks) includes the following phases [START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF]: (i) rewriting the global query according to the xed DW partitioning schema; (ii) scheduling the evaluation of so-generated sub-queries over the parallel machine according to a suitable allocation schema. Generating and evaluating sub-queries such that the query workload is evenly balanced across all the processing nodes is the most dicult task in the parallel processing above.

CPU

4. Replication of fragments. is related to two major problems: (1) replica creation and

(2) maintenance of materialized replicas. Our study focuses on the problem of creating replicas which is strongly inuenced by the number of replicas and their placement.

Indeed, the reference Replica Placement Problem (RPP) consists in choosing the best replica placement on the distributed system in order to optimize given performance criteria. The optimal replica placement problem has been shown to be an NP-Hard problem [START_REF] Wolfson | Distributed algorithms for dynamic replication of data[END_REF]. Therefore, it is often solved by means of approximate solutions in a feasible time, and a relevant amount of work has been devoted to this paradigm in the literature [START_REF] Lima | Parallel OLAP query processing in database clusters with data replication[END_REF].

Three complexes problems related to replication technique: (1) the selection of candidate fragments to be replicated and how much, (2) the placement of replicas and, (3) the updating methods. Replication techniques and updating replicas can be classied into two strategy [START_REF] Gray | The dangers of replication and a solution[END_REF].

5. Load balancing of queries Once partitioning, allocation and replication data are done; load balancing of queries occurs to rewrite each query in many sub-queries and aect them over processing nodes. The main challenge is to ensure the most equilibrate work of processing nodes to response a query or workload, and minimize the average processing time, in which minimize the dierence of consuming time from node to anther.

To obtain a good load balancing, it is necessary to determine the best degree of parallelism and choose wisely the processing nodes for executing a query. The load balancing process has four steps [START_REF] Märtens | Dynamic query scheduling in parallel data warehouses[END_REF]:

partitioning of the workload: The coordinator node handles to partition the workload of queries into a set of sub-queries according to the horizontal partitioning scheme for the database. Indeed, the horizontal partitioning produces sub-queries that can run on independent processing nodes. The size of fragments aect the quality of load balancing, the small fragments ensures more exibility and reduces the eects of skew. Thus, each sub-query is characterized by its size that corresponds to the access time of loading fragments from disks.

Selection of processing nodes: For each sub-query, all possible processing nodes are determined by the placement pattern of fragments on the processing nodes and the cache status of each node.

Scheduling of sub-queries: Sub-queries are assigned to processing nodes, in which all nodes have approximately the same workload. Scheduling sub-queries is to minimize the average response time of tasks and maximize the degree of resource utilization. The determination of the distribution of the nal charge is predetermined by the data allocation, system architecture, the cache, and the dependencies between data. The scheduling of sub-queries also denes the order of query execution.

Processing of sub-queries : When sub-queries are aected to processing nodes, they start to verify the existence of fragments on its disks (If the needed fragments are not found, they get a copy from its neighbours). Once all fragments are available, the execution of sub-queries start.

A good load balancing is critical to the performance of a parallel system where the response time corresponds to later processing node. Load balancing can be inuenced by several problems: competition control (parallel execution requires simultaneous access to shared resources.), interference and communication, and the skewed distribution [START_REF] Ceri | Horizontal data partitioning in database design[END_REF].

The bad balancing is mainly aected by the skewed distribution of data and / or processing. Walton et al. [START_REF] Walton | A taxonomy and performance model of data skew eects in parallel joins[END_REF] have classied the eects of a poor distribution of data in a parallel execution as follows:

Attribute Value Skew: it occurs when the attribute values are not distributed uniformly over processing nodes. This means that some attribute values appear with much higher frequencies than others.

tuples Placement Skew: is the consequence when the initial partition and allocation based on attributes with poor distribution of values.

Selectivity Skew: is due to the variation of the selectivity of the selection predicates between processing nodes.

Redistribution Skew: occurs when there is a dierence between the distribution of values of join keys.

Result Size Skew: It occurs when there is a big dierence between the size of the results obtained by each processing nodes.

Capacity Skew: It represents the workload that each processor is able to process it. This may be due to heterogeneity for the architecture and the operating system such as memory size, version of the operating system, computing power, storage capacity.

Processing Skew: It occurs when there a dierence of the execution time of the sub-queries on the processing nodes.

III.4.1. Metrics of deployment quality

To evaluate the quality of deployment two main metrics are used: speed-up and scale up. The speeding factor (Speed-Up) measures the performance gain obtained by increasing the number of processing nodes. If a query Q, needs T s units (e.g., seconds) to be executed sequentially, and T p units to be executed in parallel manner on p processing nodes, the speed-up is dened as follow:

speed -up(p) = T s T p (2.
2)

The scaling factor (Scale-Up) measures the change of query response time following a proportional increase of database size and the number of processing nodes. The scale-up is ideal if it is still equal to 1 (called also linear scaling).

Let db 1 and db 2 be two databases with the following sizes: size(db 1 ) and size(db 2 ). If size(db 2 ) = N * size(db 2 ), and T db i ,p i is query response time of the query Q on the db i using p i processing nodes, the scale factor is dened as follows:

scale

-up = T db 1 ,p 1 T db 2 ,N * p 1 (2.3)
Based on the above discussion, we can give a formalization of the parallel DW design: Given: a logical schema of data warehouse that contains a fact table F , and a set

D of d dimension tables D ={D 1 , .., D d } ; a workload Q of k queries Q ={Q 1 , .., Q n }, each query i q has a access frequency f i , for for 1 ≤ i ≤ n; a set N of M processing nodes N ={N 1 , .., N M }, in which each N i has a storage capacity S i , for 1 ≤ i ≤ M ;
a set of non-functional requirements like the maximum query response time (response max ); technical constraints like maximum number of fragments W .

The problem of designing a parallel consists in fragmenting the DW and then allocating its obtained fragments over the nodes that the overall the cost of executing queries is minimized and the used constraints are satised [START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF].

IV. DATA STRUCTURES AND ACCESS ALGORITHMS Implementation Level

Access Level Optimization Level Fig. 2.18 Data structures and algorithms space of data processing in databases IV. Data structures and access algorithms

In this section, we discuss the dierent usages of data structures in the context of databases.

We can distinguish three main usages: (i) representation and modelling stored data, (ii) supports for algorithms dedicated to all problems that we can nd in dierent phases of the life cycle of the design, and (iii) representation of access methods. So, these data structures span three levels concerning optimizations, accesses and implementations.

The implementation level describes data modelling (logically and physically) and access algorithms to retrieve, add or update data from and to storage devices. The access level describes the real implementations of optimizations structures such as MV, indexes, logical query plan, data partitioning, data cube. The optimization level contributes in implementing and resolving traditional optimization problems (e.g., physical design, ETL, deployment, etc.).

Figure 2.18 shows the three dimensions describing the roles of DS in the context of databases.

In the following, we overview some data structures used in dierent levels.

IV.1. Data structures in implementation level

In the implementation level, the data are stored in secondary storage devices (e.g., hard disks), where DS are used to represent data. In the logical DS, data are represented by many formats like, le, unstructured data, key-value, semi-structured data like XML le [START_REF] Li | Indexing and querying xml data for regular path expressions[END_REF], table [START_REF] Selinger | Access path selection in a relational database management system[END_REF], row-store [1], column-store [START_REF] Lamb | The vertica analytic database: C-store 7 years later[END_REF]1,[START_REF] Stonebraker | C-store: a column-oriented dbms[END_REF], etc. In the physical DS, data are stored based on specic format of le system, like HDFS 3 , NTFS 4 , etc. The le system depends on the type of storage devices (Hard disk, Flash memory, etc.). For example, data in HDFS, the data are chopped up in several blocks of 64 Note that, these DS are used to store data and accessing algorithms, dene the eciency of any DBMS [START_REF] Lin | The tv-tree: An index structure for highdimensional data[END_REF][START_REF] Debnath | Flashstore: high throughput persistent key-value store[END_REF]. So, In physically store, data are allocated generally, on pages, cluster and sectors. And in the logically store, data are stored as many formats like, les, tables [START_REF] Chen | The entity relationship model toward a unied view of data[END_REF], binary [START_REF] Theoharis | Benchmarking database representations of rdf/s stores[END_REF], key-values [START_REF] Dean | Mapreduce: simplied data processing on large clusters[END_REF], triplet [START_REF] Bery | Conception physique des bases de données a base ontologique : le cas des vues matérialisées[END_REF].

In this level, the main problems related to data are: reading, adding, deleting, and updating.

Due to the data volume, having ecient access methods to nd quickly a target data in storage devices is necessary. As a consequence, many optimization structures like indexes have been proposed and implemented.

Hence, in the implementation level, access methods are involved for several purposes: to represent data, to resolve a set of related problems (read, delete, insert data), and to use a set of access techniques to facilitate and accelerate resolving related problems.

IV.2. Data structures in access level

In the access level, data concerns mainly optimization techniques to speed up queries. The query optimization covers two main aspects: the physical design, identication of the best query plans. To ensure their eciency, the optimization structures have to contain a summary of all or a part of original data needed by queries to avoid as much as possible costly accesses to original data.

IV.3. Data structures in Optimization level

In the optimization level, the DBA is always working to nd the optimal conguration corresponding to one or several OS. Selecting optimal OS has three main steps:

1. the representation of the search space by one or more data structures;

2. the reduction of the search space in small set of solution candidates to minimize the complexity of selection algorithm;

3. the selection of the optimal conguration based using naive or advanced algorithms (evolutionary algorithms, systematic algorithms, randomize algorithms, etc.).

The elements of search space and the set of candidates of OS are dened using one or more DS. Often; it is impossible to list all their elements which require dening the search space using Abstract Data Type (ADT), like graph and tree. Applying rules and heuristics on these ADT gives an innite possible OS, there they can be represented by a DS like array, graph, tree, linked lists, etc.

The main related problems in this level are selecting the optimal OS under constraints, that they often considered as combinatorial problems with NP-hard complexity [START_REF] Gupta | Selection of views to materialize under a maintenance cost constraint[END_REF][START_REF] Chaudhuri | Index selection for databases: A hardness study and a principled heuristic solution[END_REF][START_REF] Sacca | Database partitioning in a cluster of processors[END_REF]. Accordingly, the researchers have always used dierent types of heuristics to reduce the complexity of the problem and then identify a near optimal solution.

To summarize, in the optimization level, the elements of possible search space are usually dened using ADT and the elements of candidate OS are dened using one or more DS. The main problems related to data are the selection of the optimal conguration of one or more OS. Figure ?? gives the modelling space of data in the optimization level.

IV.4. Discussion

In this chapter, we show the role of the interaction among queries in physical design and deployment phases. This interaction has certainly exploited by researchers to propose large spectrum of algorithms [START_REF] Mami | A survey of view selection methods[END_REF]: deterministic algorithms, randomized algorithms, genetic algorithms, hybrid algorithms. These algorithms explore the nodes of the global plan of the interacted queries to identify the optimization schemes. These algorithms do not highlight their data structures.

In the context of big queries, the presence of exible and scalable data structure is recommended to dene advanced and ecient algorithms. Note that the global plan is a graph, usually can be partitioned to ensure scalability of algorithms. Graph partitioning is a fundamental problem, with applications to many areas such as parallel computing and VLSI layout. The goal of graph partitioning is to split the nodes in graph into several disjoint parts such that a predened objective function, for example, ratio-cut, or normalized cut, is minimal. This partitioning saves the characteristics of the initial search space represented by the global plan.

Another point that we realized when analyzing these studies is the absence of a connexion between the problem of physical design and the problem of MQO. More precisely, to select an optimization structure such as materialized views, the majority of the proposals use a sequential methodology meaning that they assume that the problem MQO is already solved and then they use its solution to run their algorithms. Due to the strong interdependency between these two problems, a joint methodology is recommended.

V. Conclusion

This chapter gave an overview, accompanied with analysis and comparison of the dierent concepts used in our thesis. We started by introducing the data warehousing technology including its design and exploitation by OLAP queries. The performance of the exploitation process is linked to the physical design of the life cycle of the data warehouse design that includes: user requirements, conceptual, logical, deployment and physical phases. Afterwards, we concentrated our discussion on the OLAP queries and their characteristics: they are routinely and share common intermediate results. In the Era of very large database applications, their optimization has become a crucial issue. The characteristics of OLAP queries force us to use multi-query optimization solutions. Finally, based on this overview, we deduced the following:

to optimize very large queries dened on extremely large databases, we need a scalable data structures associated with advanced algorithms.

I. Introduction

As we have mentioned in the previous chapters, the generation of unied query plan for a workload with high interacted queries is an NP-hard problem [START_REF] Sellis | On the multiple query optimization problem[END_REF]. Several research eorts have been triggered to tackle this problem, where a large panoply of algorithms have been proposed that can be divide into three main categories: (a) dynamic programming algorithms [START_REF] Toroslu | Dynamic programming solution for multiple query optimization problem[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF], (b) genetic algorithms [START_REF] Bayir | Genetic algorithm for the multiple-query optimization problem[END_REF] and (c) randomized algorithms [START_REF] Ioannidis | Randomized algorithms for optimizing large join queries[END_REF]. We would like to mention that these algorithms have been tested for workloads with small sets of queries and can require high computation time. Facing this situation, we have two scenarios: (i) reproduction of the existing algorithms. However, it is not obvious that a particular algorithm Coarsening is reproducible to a sucient extent with this technique to deal with a large scale search space and (ii) revisit our problem and solve it dierently, by integrating the volume and sharing of queries. In this thesis, we adopt the second scenario.

The database technology has a great experience in using advanced data structures such as graphs, hypergraphs, tree (for indexing), etc. These structures are used either to speed up the data access or as a support for algorithms dealing with large scale search space. We can cite the example of the problem of vertical partitioning in relational databases. Shamkant B. Navathe which is one of the pioneer who dealt with this problem, proposed a graphical algorithm with less computational complexity than his rst algorithms [START_REF] Navathe | Vertical partitioning algorithms for database design[END_REF][START_REF] Navathe | Vertical partitioning algorithms for database design[END_REF] that generates all meaningful fragments simultaneously [START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF]. The eorts spent Shamkant B. Navathe were concentrated to the transformation of the vertical partitioning problem to a graph.

A unied query plan has been already represented by traditional graph. The presence of node sharing of OLAP queries makes our problem similar to electronic circuit, where the hypergraph corresponding to a logical circuit directly maps gates to vertices and nets (connection between gates) to hyperedges [START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF]. Therefore, the hardness of our study is to make the analogy between these two worlds: unied query plan generation and logical circuits. Finally, our problem will be transported in the context of EDA.

By the means of this Chapter, we would like to share our collaboration with Mentor Graphics in terms of exploitation of their rich ndings in terms of algorithms and tools.

This chapter begins by the presentation of the hypergraph theory (Section II) and their usages.

Section III focuses on the analogy between the electronic design automation (EDA) and multiquery optimization problems. In the section IV, we detail our approach, in which we describe hypergraph representation and partitioning, and we show the mapping between the hypergraph and the unied query plan. The hardness study of our problem is given in Section V. Section VI describes the set of experiments that we conduct to validate our proposal. Finally, Section VII concludes the chapter.

II. Hypergraphs and their usages

Hypergraphs give more expressive than traditional graphs in modeling sets of objects. This characteristic allow the hypergraphs capturing any relationship between a group of objects, whereas graphs can only capture binary relationships [START_REF] Çatalyürek | Decomposing irregularly sparse matrices for parallel matrix-vector multiplication[END_REF][START_REF] Pinar | Decomposing linear programs for parallel solution[END_REF]. This specicity gives more exibility in accurately formulating several important problems in combinatorial scientic computing [START_REF] Yzelman | Cache-oblivious sparse matrix-vector multiplication by using sparse matrix partitioning methods[END_REF].

Since 20 years, the hypergraph theory contributes in modeling and solving several problems in various domains such as location problems [START_REF] Klamt | Hypergraphs and cellular networks[END_REF][START_REF] Klamt | Hypergraphs and cellular networks[END_REF], combinatorial problems [START_REF] Berge | Hypergraphs: combinatorics of nite sets[END_REF] and so on [START_REF] Devine | Parallel hypergraph partitioning for scientic computing[END_REF][START_REF] Konstantinova | Application of hypergraph theory in chemistry[END_REF][START_REF] Bretto | Hypergraph-based image representation[END_REF][START_REF] Ducournau | A reductive approach to hypergraph clustering: An application to image segmentation[END_REF][START_REF] Vazquez | Population stratication using a statistical model on hypergraphs[END_REF].

The major particularity that hypergraphs oers is their ability in dividing the search space of a complex problem into several sub search spaces. Thus, hypergraph partitioning signicantly reduces the complexity of the studied problems. The wide applicability of hypergraph theory has motivated the development of fast partitioning tools, some are standardized. We can cite the examples of as hM eT iS 1 [START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF][START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF][START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF], PaToH 2 [START_REF] Catalyürek | Patoh: a multilevel hypergraph partitioning tool[END_REF], and Mondriaan 3 [START_REF] Vastenhouw | A two-dimensional data distribution method for parallel sparse matrix-vector multiplication[END_REF]. In addition, we nd also parallel partitioning tools such as Parkway 4 [250] and Zoltan 5 [START_REF] Devine | Parallel hypergraph partitioning for scientic computing[END_REF].

This section presents a review of hypergraph theory and their applications to resolve combinatorial problems, with a special focus on database related problems.

II.1. Denitions

In this section, we present some fundamental denitions and underlying notions to understand the hypergraph and its partitioning algorithms.

Denition 8. Hypergraph: A hypergraph H =(V,E) is dened as a set V ={v 1 , .., v n }, of nodes (vertices) and a set E ={e 1 , .., e m } of hyperedges, where every hyperedge e connects a non-empty subset of nodes.

We said that the hyperedge e ∈ E connects the vertex v ∈ V if, and only if, v ∈ e.

A weight and costs can be respectively associated with vertices and hyperedges of a hypergraph. Denition 11. Hypergraph partition: A partition of the hypergraph H (V,E), denoted by Π ={V 1 ,V 2 ,..,V k }, is a nite collection of subsets of V, called parts, such that :

each subset V i is a non-empty subset of vertices, i.e., V i = ∅, for 1 ≤ i ≥ k; all subsets are pairwise disjoint, i.e., V i ∩ V j = ∅, for 1 ≤ i < j ≥ k;
the union of all subsets is equal to

V. i.e., ∪ v i =V, for 1 ≤ i < j ≥ k.
When the number of subsets |Π| = k and k > 2, the partition Π is called a k -way or a multi-way partition. Otherwise (when k = 2), we call Π as a hypergraph bi-partitioning (it called also bisections).

Denition 12. Connectivity of hyperedge: In a partition Π of H (V,E), we say that a hyperedge e ∈ E connects the part P i , if e connects at least one node from V i , and we say that e connect the part P i or e connect the subset V i . We denote by P e as the list of parts V i connected by the hyperedge e. The connectivity of hyperedge e denoted by |P e |, is the number of distinct parts connected by e.

II.2. Hypergraph partitioning algorithms

Denition 15. Hypergraph partitioning: can be dened as the task of dividing a hypergraph into two or more partitions while minimizing the cutsize and maintaining a given balance criterion ε among partitions weights.

II.2.1. Objectives of Hypergraph partitioning

Hypergraph partitioning is commonly used to model decomposition of problems, where the interconnection within the decomposition (partition) is minimized. The decomposition is evaluated using a cost that represents a quantitative measure of partition quality (integer or real value). This cost expresses the objective of the partitioning, which aims at minimizing or maximizing this cost. Several cost objectives used to partition the hypergraph. Most of them use the number of hyperedge cuts. Therefore, the partitioning aims at nding the partition with a minimum cut. For example, in VLSI placement, reducing hyperedges cut corresponds a minimizing needed wires between gates. In parallel computation the minimum cut corresponds at minimum of communication inter processors.

II.2.2. Formalization of Hypergraph partitioning

Formally, hypergraph partitioning is dened as: Inputs:

-a hypergraph H (V ,E ); -an integer k > 1 that represents the suitable partitions; -a real value balance criterion 0 < ε < 1.

Outputs:

a partition Π ={P 1 , .., P k }, with corresponding part weights f w (P i ), 1 ≤ i ≤ k.

Constraints:

f w (P i )<(1+ε)*W avg , for all 1 ≤ i ≤ k, where W avg is the average weight.

Objective: minimization of the number of cut of hyperedge cutsize. The objective function may use other costs. This partitioning has to ensure a balance between the weights of dierent result parts. This balance is considered as partitioning constraints. The weight of a given part is calculated as the sum of the weights of its vertices. Let f w (P i ) be the weight of a part P i , which is dened as the sum of the weights of its vertices V i , as shown in the following equation:

f w (P i ) = v∈Vi w[v] (3.1)
To ensure the balance constraint, we need the average weight W avg of parts and an allowed predetermined maximum imbalance ratio ε, where 0 < ε < 1. The average weights W avg , is dened as:

W avg = ( v∈V w[v])/k (3.2)
where k is the number of partitions. A partition is said to be balanced, if each partition P i satises the following criterion :

f w (P i ) ≤ W avg * (1 + ε); 1 ≤ i ≤ k (3.3)
The cost of hypergraph partitioning Π can be dened by:

cost(Π) = e∈C(Π) c[e]

II.2.3. Methods of Hypergraph partitioning

Numerous approaches exist for solving the hypergraph partitioning problem that can be classied into four categories.

Exhaustive Enumeration that produces all possible partitioning. At the end, it selects the partition with optimal cost dened by the designers. This method gives the optimal solution, but it has exponential complexity, since it requires an exploration of the search space [START_REF] Caldwell | Optimal partitioners and end-case placers for standard-cell layout[END_REF].

Branch and Bound is proposed to improve the above approach by implementing a depth left tree of partial partitioning. This tree allows having faster a sub-optimal solution by verifying the balance constraints in each node. It prunes the illegal solutions. Despite its performance, it may have an exponential complexity [START_REF] Caldwell | Optimal partitioners and end-case placers for standard-cell layout[END_REF].

Fiduccia-Mattheyses is proposed to scale partitioning algorithms [START_REF] Fiduccia | A linear-time heuristic for improving network partitions[END_REF], which is a linear heuristic that improves a partitioning using iterative passes wherein each vertex is moved exactly once. Passes are generally applied until little or no improvement remains. Initial solutions are often produced using a simple randomized algorithm.

Multilevel Fiduccia-Mattheyses Framework consists of three main components:

clustering, top-level partitioning and renement (these steps will be detailed below).

Other methods exist for solving hypergraph partitioning problem such as simulated annealing and Tabu search [START_REF] Eles | System level hardware/software partitioning based on simulated annealing and tabu search[END_REF], spectral techniques [START_REF] Alpert | Multi-way partitioning via spacelling curves and dynamic programming[END_REF], network-ow driven algorithms [START_REF] Yang | Ecient network ow based min-cut balanced partitioning[END_REF], and incidental ow-solver [START_REF] Hur | Hybrid techniques for standard cell placement[END_REF][START_REF] Hur | Relaxation and clustering in a local search framework: application to linear placement[END_REF].

G 0 G 1 G 2 G3 G4 G 0 G 1 G 2

G3

Initial Partitioning Phase

Uncoarsening phase

Coarsen ing phase Fig. 3

.2 Cut hyperedge splitting during recursive bisection

The Multilevel hypergraph partitioning is the most used technique for hypergraph partitioning.

It goes through three phases: coarsening, initial partitioning, and uncoarsening. In the rst phase, a bottom-up multilevel clustering is successively applied on the original hypergraph, by adopting various heuristics, until the number of vertices reaches a predetermined threshold value in the coarsened graph. In the second phase, the coarsest graph is bi-partitioned using various bottom-up heuristics. In the third phase, the partition found in the second phase is successively projected back towards the original graph by rening the projected partitions on intermediate level uncoarser graphs using various top-down iterative improvement heuristics.

The following sub-sections briey summarize these three phases illustrated in Figure 3.2.

Coarsening Phase

In this phase, for given hypergraph H = (V ,E ), undergo the object of sequence of successive approximations, the hypergraph is coarsened into a sequence of smaller hypergraphs

H 1 =(V 1 ,E 1 ), H 2 =(V 2 ,E 2 ) ... H m =(V m ,E m ). satisfying |V 1 | > |V 2 | >...>|V m |,
and the number of vertices in the coarsest approximation V m has some xed upper bound that depends on the solicited number of parts in the partition (k ).

In [START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF], Karypis et al., give some desirable characteristics that a coarsening algorithm should possess: a near-optimal partition of the coarsest hypergraph H m should project to a near-optimal partition of H.

Coarsening Approaches

The early algorithms for coarsening graph [START_REF] Bui | Improving the performance of the kernighan-lin and simulated annealing graph bisection algorithms[END_REF][START_REF] Hendrickson | An improved spectral graph partitioning algorithm for mapping parallel computations[END_REF] use a purely random edge matching scheme.

Unmatched vertices are only allowed to match with other unmatched vertices, resulting in vertex clusters of size two. In [START_REF] Barnard | Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems[END_REF], Simon and Barnard coarsen the graph by rst computing a maximal independent set of vertices V ⊆ V i , such that for any two vertices u, v ∈ V , there is no hyperedge in E that connects u and v. Then constructing the coarse vertices by matching vertices in the maximal independent set with their neighbors.

Toyonaga et al. [START_REF] Toyonaga | A new approach of fractaldimension based module clustering for vlsi layout[END_REF] sort the hyperedges in non-decreasing order by cardinality and then traverse the sorted list of hyperedges, with vertices of a hyperedge forming a cluster if they have not been matched previously as part of another hyperedge. Karypis et al. [START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF][START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF] sort the hyperedges in a non-increasing order of weight and then hyperedges of the same weight are sorted in a nondecreasing order of cardinality. The sorted set of hyperedges is then traversed and vertices of a hyperedge form a cluster if they have not been matched previously as part of another hyperedge.

Initial Partitioning Phase

The goal in this phase is to nd a bipartition on the coarsest hypergraph H m , that satises the partition balance constraint and optimizes the objective function.

Eectively, any heuristic optimization algorithm that can be applied to hypergraph partitioning may be used to compute the initial partition. For example, Hauck and Borriello [START_REF] Hauck | An evaluation of bipartitioning techniques[END_REF] evaluate a number of simple methods for generating a starting feasible partition, prior to using a heuristic partitioning algorithm. Random partition creation by randomly chosen vertices is proposed to improve the previous algorithms in terms of the quality of the generated partitions and the runtime. Similar initial partition generation methods are also used in [START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF][START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF].

In [START_REF] Caldwell | Improved algorithms for hypergraph bipartitioning[END_REF], the authors have introduced a relaxation balance constraint of random computation by adding deterministic computation. Generally, the quality of these algorithms is sensitive to the choice of the initial random vertex.

Uncoarsening Phase

During this phase, a partition of the coarsest hypergraph is projected through each successive ner hypergraph, where at each level i (for i = m, m -1,. . . , 1), bipartition Π i found on H i is projected back to a bipartition Π i-1 on H i-1 . A simple algorithm for projecting a partition which runs in O (n) time proceeds as follows:

The vertices of a hypergraph H i (H i ,E i ) are traversed, and for each vertex v ∈ V i , the part corresponding to the coarse vertex g(v) ∈ V i+1 is noted from Π i+1 and v is assigned to the same part in Π i . Typically, iterative improvement algorithms based on the KL/FM framework are used. Although [START_REF] Saab | An eective multilevel algorithm for bisecting graphs and hypergraphs[END_REF] uses a Tabu search-based algorithm.

II.3. Applications of hypergraph theory

Recently, the hypergraph theory [START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF] allowed a hyperedge to connect an arbitrary number of vertices instead of two in regular graphs. Therefore, it provides better understanding of large range of real systems. The hypergraph theory is very useful in many domains like (1) in chemistry search they are used to giving more convenient description of molecular structures [START_REF] Konstantinova | Application of hypergraph theory in chemistry[END_REF].

(2) In telecommunication, where they are used to modeling cellular mobile communication systems to dene the groups of cells that cannot use simultaneously the same channel under predene distance [START_REF] Klamt | Hypergraphs and cellular networks[END_REF]. (3) In image processing in which they are used to segmenting images [START_REF] Bretto | Hypergraph-based image representation[END_REF][START_REF] Ducournau | A reductive approach to hypergraph clustering: An application to image segmentation[END_REF]. (4) Other domains like recommendation [START_REF] Blattner | B-rank: A top n recommendation algorithm[END_REF][START_REF] Shang | Collaborative ltering with diusion-based similarity on tripartite graphs[END_REF], analyzing public health [START_REF] Vazquez | Population stratication using a statistical model on hypergraphs[END_REF], etc.

In the following, we detail some practical applications of hypergraph theory.

Data mining implementation: hypergraph has been exploited by researchers in data mining, where data are clustered in several groups, such that the intra-cluster similarity is maximized, while inter-cluster similarity is minimized [START_REF] Hagen | On implementation choices for iterative improvement partitioning algorithms[END_REF][START_REF] Boley | Partitioning-based clustering for web document categorization[END_REF][START_REF] Hébert | A data mining formalization to improve hypergraph minimal transversal computation[END_REF]. The set of vertices and hyperedges of the hypergraph corresponds respectively to the set of data items and the set of relations between them.

Database schemes modeling: a database can be viewed as a set of attributes and set of relations between these attributes. This property has motivated some works to introduce hypergraph theory to model relational database schemes [START_REF] Fagin | Degrees of acyclicity for hypergraphs and relational database schemes[END_REF]. The vertices of hypergraph is the set of attributes, and the set of hyperedges is the set of relations between these attributes. Other applications have been discussed in the previous chapters.

VLSI computer-aided design: the application of hypergraph partitioning within VLSI design has been well-addressed in literature [START_REF] Alpert | Recent directions in netlist partitioning: a survey[END_REF][START_REF] Kahng | Futures for partitioning in physical design[END_REF][START_REF] Cong | Optimality, scalability and stability study of partitioning and placement algorithms[END_REF]. The hypergraph partitioning problem is used to facilitate the task of designing modern integrated circuits that have a very large number of components. A hypergraph is used to represent the connectivity information from the circuit specication. Each vertex in the hypergraph represents a gate in the circuit and each hyperedge represents a connection inter-gates [START_REF] Alpert | Recent directions in netlist partitioning: a survey[END_REF]. Hypergraph partitioning allows dividing a circuit specication into clusters of components, such that the cluster interconnect is minimized. Each component can then be assembled independently, speeding up the design and the integration processes.

Social network analysis: there is a tendency to use hypergraph theory to analyze social networks. In this context, the vertices and hyperedges of a hypergraph represent respectively the type of actors (e.g., peoples, groups, etc.) and the relationships between them. The corresponding hypergraphs are used for many proposes such as: forensics III. ANALOGY BETWEEN UQP AND EDA analysis to solve crimes (e.g., identifying the regions of twitter [START_REF] Gentry | twitter: R based twitter client[END_REF]) and for identifying topological features to understand tagged networks [START_REF] Zlati¢ | Hypergraph topological quantities for tagged social networks[END_REF].

II.4. Discussion

In many applications of hypergraph theory, the size of input grows continually and rapidly. For example, the number of transistors in VLSI design problem continues to grow exponentially in which today tens of millions gates and in the near-future hundreds of millions are needed to design logical circuits. Same situation concerns the social network medias, where the number of worldwide users is expected to reach some 2.95 billion by 2020, around a third of Earth's entire population 6 . The success story of hypergraphs, where they have has proved their motivates us to use them in our context of big queries.

III. Analogy between UQP and EDA

In this section, we present the analogy between MQO problem and electronic design automation (EDA). This analogy is the motivation to brow EDA techniques and tools to be used in our problems.

III.1. Analogy between UQP and Electronic circuit

An UQP can be represented using an directed acyclic graph those nodes (vertices), represent the query operators which are binary and unary. The edges describe the data ow between operators, where loading data start from the leaf nodes and each intermediate node passes its results computing to their connected nodes, until root nodes (that describe the nal results).

Similarly, a logical circuit can be represented by directed acyclic graph those nodes represent theirs gates (ports) that can be associated to many inputs/outputs. An edge describes the data ux between gates that denes the sense of transforming data from one gate to another. The leaf nodes capture data from external source, whereas intermediate nodes modify the captured data and transform them to the connected nodes. The root nodes contain the results of electronic circuit function. Hence, an UQP can be considered as electronic circuit with only unary and/or binary ports.

Example

Consider the star schema benchmark SSB 7 [START_REF] O'neil | The star schema benchmark and augmented fact table indexing[END_REF]. The DW contains a fact table Lineorder and four dimension tables: Customer, Supplier, Part and Dates. This schema is queried by a set of 30 queries of SSB benchmark. Step 1: parses each SQL query of our workload to identify the logical operations (nodes). Step 2: models the join nodes by a hypergraph, where the vertices represents the set of join nodes and the hyperedge set represents the workload of queries 8 . Step 3: generates connected components using hypergraph partitioning algorithms. The result is a set of disjoint components of queries. Each component is represented by a sub-hypergraph (SH i ).

UQP

Step 4: transforms each sub-hypergraph into an oriented graph using a mathematical cost model and implementation algorithms to order the nodes. This step is crucial, since we can plug any OS knowledge consumer of unied graph such as materialized views, horizontal partitioning, etc.

Step 5: merges the graphs resulting from the previous transformation to generate the global unied query processing (UQP).

IV

Syntax analysis

The syntax analysis allows verifying the consistency of parse tree nodes. The leaves nodes of the parse tree represent the atomic elements. They are the lexical elements of the query such as keywords (e.g., SELECT, WHERE, FROM ), names of relations and attributes, constants, logical and arithmetic operators, etc. The other nodes of the parsed tree represent a composite element formed by many atomic elements like Condition, other sub query. In Figure 3.9, the composite elements are reported by elements between "<" and ">". Figure 3.9 shows the parsed tree of SQL query presented in the Figure3.

Semantic checking of the parsed tree

The semantic parse tree checking is an intermediate step aiming at verifying the syntactical and the semantic rules of the query. The checking process follows these main tasks:

checking whether every relation, attribute, or view mentioned in the FROM-clause belongs to the schema of database or data warehouse (using the meta-model).

checking whether every attribute mentioned in the SELECT/WHERE-clause belongs to the relations appeared in the FROM-clause.

checking whether attributes' types are respected in the Condition-clause.

Views checking

In this step, each virtual view in the query parse tree will be replaced by a sub-parse tree that represents the sub-query constructing this view. Note that in the case of materialized views, there is no substitution, because these latter are considered as base tables (relations). Figure 3.10 shows the replacement of a virtual view by its sub-parse tree.

V R2 Q X X R1 R4 X R3 R2 Q X X R1 View V

IV.1.2. Logical query plan selection

The logical query optimization is founded on the algebraic equivalences. In fact, many equivalent expressions can be generated for a query [START_REF] Bosma | The magma algebra system i: The user language[END_REF] (cf. Chapter I) A query is composed of dierent operations which follow algebraic laws (commutativity, associativity, and distributivity), and can be applied in both directions: from left to right, and from right to left. So, a huge space of equivalent expressions can be derived for one query. Finding a better plan, during the logical step is not possible, since many implementation details required for the cost estimation may be missed and eventually further added to the plan (during the physical phase).

The generation of the logical plan of a query presented as a parsed tree, goes through two principal steps: (1) transforming this tree to a logical query plan, and (2) improving the logical query plan using algebraic laws, and (3) selecting an appropriate logical plan.

Parse tree translation

Transforming the parsed tree into more preferred logical query plans is performed through two steps: (i) the nodes of the parsed tree are replaced by one or several operators of relational algebra. (ii) the query optimizer applies the algebraic laws on the resulting query expression to generate an expression more appropriate to be physically processed thereafter. The translation applies the following rules:

Relations are loaded from <FromList> of the parsed tree; Selections σ C correspond to every C captured from <conditions> of the parsed tree; Projections Π L correspond to each attribute present in the list L captured from <SelList>.

the initial logical plan corresponds to the cross product of the relations, two by two, and second a selection σ C , and nally a project Π L . Figure 3.12 gives an example of an initial logical query plan associated to the query in Figure 3.8.

If the condition represents a sub-query, then it will be replaced by an expression of relation algebra following the previous steps.

IV.2. Hypergraph generation

An hypergraph H is a set of vertices V and a set of hyperedges E. In our case, V represents a set of join nodes, such that for each vertex v i ∈ V, corresponds a join node n j . The same way, E represents the workload of queries Q, such that for each hyperedge e i ∈ E corresponds a query q j . A hyperedge e i connecting a set of vertices corresponds to a join nodes that participate on the execution of the query q j . As shown in Figure 3 given, where the hyperedge e 23 corresponds to query q 23 and connects the join nodes: n 28 , n 30 , n 32 and n 33 . The hypere-dge e 2 corresponds to query q 2 and connects one join node n 1 . The set of join nodes will be partitioned into several disjoint sub-sets, called connected components. Each component can be processed independently to generate a local UQP by ordering the nodes. Table 3.1 summarizes the mapping between the graph vision and the query vision.

IV.3. Hypergraph partitioning

As we explain in the section III, the hypergraph partitioning allows us to group queries in many sets, in which queries inside each set share the maximum of intermediate results and have minimum interaction with the others queries. To partition our hypergraph, we adapt an existing algorithm derived from graph theory to aggregate the join nodes into small connected components. The partition process is applied on initial hypergraph H (V ,E ) and the result of hypergraph partitioning is k sub-hypergraphs that are a hypergraphs H i (V i ,E i ), where |E i | ≤ M , for all 1≤ i ≤ k. Our partitioning algorithm has the following steps: Table 3.1 Analogy Graph Query.

1. Firstly, we adapt the code of the multilevel hypergraph partitioning (hM eT iS) to split our hypergraph into several partitions such as no cut of hyperedges. hM eT iS is a free software library developed by the Karypis laboratory. This software allows parallel and serial partitioning. As we said before, it divides a hypergraph into k partitions (new hypergraphs) such that the number of hyperedges cut is minimal [START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF][START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF]. In our context, the exact number of partitions to construct is unknown. In the same time, we want to get all possible disjoint partitions (connected components). To do so, we adapt the original algorithm to our problem by bi-partitions until no partition can be repartitioned without cutting hyperedges. More precisely, the algorithm behaves as follows: (i) the set of vertices will be divided if and only if the number of hyperedges cutting is null. (ii)

Each bisection result of the hypergraph partitioning will be divided in the same way until no more divisible hypergraph is found.

2. Secondly, we use hM eT iS programs to partition each sub-hypergraph H i (V i ,E i ), such as |E i | ≥ M . The sub-hypergraph H i will be partitioned into k partitions such as k =(|E i |/ M )+1.

IV.4. Transforming hypergraph to UQP

After the partitioning process of the hypergraph into several small sub-hypergraps, the generation of UQP becomes a simple transformation of each sub-hypergraph into an oriented graph and nally merging of resulting graphs. In this thesis, we assume that the queries of our workload are represented only left-deep plan, so for a join unied query plan will have many connected components. Each component contains a query plan that shared at least one join node. The rst join node, called pivot node(pivot), which is shared by all queries of its component. The pivot has a direct impact on the other nodes of its component. So, the quality of component depends to the pivot nodes. Hence, the generation of OS-oriented UQP becomes at nding the adequate pivot node that denes the components of the OS-oriented UQP.

To generate the local UQP (for one sub-hypergraph), the join hypergraph must be transformed into oriented join graphs G. Adding an arc to a graph corresponds to establishing an order between two join nodes. We start by the pivot node which is preferred for the OS that is identied using a function translating the knowledge of OS (see Chapter 4). The pivot node will be added to the oriented graph (G) and deleted from the hypergraph. This operation is repeated until all nodes are added to the graph.

Algorithm 1: transformHyperGraph(Hypergraph H) end if 17: end while Algorithm 1 describes the transformation steps of a hypergraph into an oriented graph.

Transforming a hypergraph into an oriented graph UQP is a two-part process. On one hand, we select a pivot node from the hypergraph to be removed, while on the other hand the corresponding join node is added to the UQP. This process is repeated until there are no more vertices in the hypergraph is found. Hence, the transformation has three steps: (1) choosing the pivot node (pivot), depending on the target OS. (2) transforming the pivot node from the hypergraph to the oriented graph. (3) removing the pivot node from the hypergraph. Figure 3.15 shows the transformation steps of a hypergraph into an oriented graph. In which, we have as input the hypergraph H (V ,E )=({n 20 , n 21 , n 22 , n 24 , n 25 , n 26 , n 28 },{Q 5 ,Q 14 ,Q 16 }). In the rst step, the node n 20 is chosen as the pivot node, which is determined by two selections S 1 and S 2 . The transformation starts by inserting the rst join node corresponding to n 20 into the oriented graph (basically in the rst step, the oriented graph don't contain any nodes), and deleting the n 20 from the hypergraph H. In which produces two other sub-hypergraphs : H 1 (V 1 ,E 1 )=({ n 21 , n 24 , n 25 , n 26 },{Q 5 ,Q 14 }) and H 2 (V 2 ,E 2 )=({ n 22 , n 28 },{Q 16 }). In the in descending order of their benefit Fig. 3.15 Transformation steps of a join hypergraph to an oriented graph second step, the n 24 (determined by two selection S 1 and S 3 ) is chosen as pivot node. The pivot node will be added into the graph after the node n 20 (so, the right predecessor becomes n 20 instead S 1 ). The removing the n 24 from H 1 will generate two other sub-hypergraphs H 1 1 =({n 25 , n 26 },{Q 5 }) and H 1 2 =({n 21 },{Q 14 }). These operations (choose pivot node, inset node into oriented graph and removing node from hypergraph), will be repeated until no nodes into any sub-hypergraph, and as consequence we obtain the nal oriented graph (UQP).

IV.4.1. Finding the pivot node

The choice of pivot node from the hypergraph at a given point is made through a benet function which takes into account the characteristics of the specic problem. The function computes the benet relative to the targeted OS for each remaining node of the section and adds the node with maximum benet. For more details on the benet function, see Chapter 4.

Algorithm 2: f indP ivot (Hypergraph H)

1: benef itemax ← 0; 2: for all v i ∈ V do 3:
nbr ← nbrU se (v i ); {nbr: number of hyperedges that connect v i } 4:

benef it ← getBenef it(v i ) {calculate the benet of v i following the OS } 5:

if benef it > benef itemax then 6:

benef itemax ← benef it; The benet is the number of reuse multiplied by the processing cost minus the cost processing to generate the intermediate result.

IV.4.2. Remove the pivot node from hypergraph

The removing of pivot node impacts on the hypergraph. A hypergraph is the disjoint union of connected section. Two hyperedges belong to the same connected section if there is a connected path of hyperedges between them. Let S be a hypergraph and v i ∈ S be a vertex being removed. When a vertex is removed from a section, the remaining nodes of that section are aected in dierent ways depending on the following case:

Let vertex v j and v j two vertices the same hypergraph (section) the dierent cases when removing a vertex are: Case 1: v i and v j belongs to the same hyperedge and there is no hyperedge to which v j belongs and not v i . The remove of v i , v j is unchanged.

Case 2: v i and v j belongs to the same hyperedge and there exists an hyperedge to which v j belongs and not v i . The remove of v i , v j is duplicated, one unchanged and one renamed with v j Case 3: v i and v j do not belong to the same hyperedge. The remove of v i , v j is unchanged.

A resulting UQP

We denote by t(S,v) the transformation that removes the vertex,v from section S. In Figure 3.16, we apply t(S,v), which means we remove the node C from S. If C is the vertex being removed, then D is type 1 (there is an hyperedge to which both C and D belong, but no hyperedge to which D belongs but not C), B is type 2 (there is a hyperedge to which both C and B belong, and there is a hyperedge to which B belongs but not C), and A is type 3 (there is no hyperedge to which A and C belong). Figure 3.16 shows the eect of t(S,C) on section S, the result being three new sections S 1 , S 2 ,S 3 . Figure 3.17 We note that the node n 18 belong the case 2, which needs to be duplicated into the node n 33 in the second hypergraph, when removing n 28 . the nodes n 29 , n 30 , n 31 , n 32 and n 33 , belong in the case 1. the nodes n 17 , n 16 , n 19 , and n 20 belong the case 3.

IV.5. Merging the local UQP

The transformation step allows transforming a set of n hypergraphs {H

1 (V 1 ,E 1 ),..,H n (V n ,E n )}, to n oriented graphs {G 1 (V 1 ,E 1 ),..,G n (V n ,E n )}.
The n oriented graphs are disjoints and their merging is quite easy which gives the graph G (V " ,E "), where

V" = 1 ≤ i ≤ n (V ) (3.5) E" = 1 ≤ i ≤ n (E ) (3.6)

V. Complexity of the algorithms

As we explained in the previous sections, our approach has three main sequential steps. The complexity of each step is given separately:

The rst step consists in parsing the queries to identify the involved operations in order to construct the hypergraph. This task has a linear complexity O(N * P ) where N and P represent respectively the number of queries and the maximal number of operations used by a given query. In the context of DW, if we have D dimension tables, we have as maximum (D + 1) selections (by assuming the selection are grouped), D joins, D projections and one aggregation so P =3*D +2.

The second step concerns the process of hypergraph partitioning performed by hM eT iS algorithm. The complexity of hM eT iS has been studied by Han et al. [START_REF] Han | Clustering in a high-dimensional space using hypergraph models[END_REF], where it was shown that for a K-way partitioning the complexity is O((V + N )log(K)), where V is the number of vertices (in our case, it has the number of logical operations involved in the workload) and N is the number of edges (number of queries).

The last step is the transformation of each sub-hypergraph into oriented graphs. During this step, we need to successively identify the pivot node (pivot) and then remove it from the sub-hypergraph until all nodes have been removed. Hence, identication of the pivot, the cost of each node of the sub-hypergraph is computed. Therefore, the complexity is O(V 2 ), where V is the number of nodes inside the component. Each component has a limited number of queries and can be transformed independently, which allows our approach to scale.

In our approach, the queries and their operations (join nodes) are presented by a hypergraph.

A hyperedge that represents a query can represent all possible orders between their nodes. This hyperedge can connect thousands of nodes. So our approach can scale with the number of dimension tables. Note that our transformation algorithm is applied in the context of star schema. If the structure of the schema changes (e.g. snowake), new transformations are required.

VI.1. Experimental setting

In this section, we present an experimental validation of our approach. We developed a simulator tool in Java Environment. This tool is composed by the following modules.

Two UQP generation modules associated to the two studied optimization structures (materialized views and horizontal data partitioning). Each module contains several roles:

(1) the parsing SQL-queries to get all selection, join, projection and aggregation nodes,

(2) the hypergraph construction, (3) hypergraph partitioning that adapts hM eT iS tool, (4) the transformation of each hypergraph into an UQP using the appropriate benet function according to the targeted OS (the benet function is detailed in the next Chapter), ( 5) the merging process that assembles all selection, join, projection and aggregation nodes to generate the nal UQP and ( 6) the display functionalities that use Cytoscape 9plug-in to display the global processing plan.

The MV selection module that takes an UQP as input and produces candidate views to be materialized (detailed in the next Chapter).

We have implemented another module implementing the of Yang et al.'s approach [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF], by its two proposed algorithms: feasible solution and 0-1 integer programming (cf. Chapter 2). To do so, we were obliged to develop the following functions: (a) generation of individual plan tree, (b) MVPP generation, using merging individual plans, (c) 0-1 matrix representation of using queries and plans (d) selecting materialized views, (e) and an estimation of query processing using materialized views (by the means of query rewriting capabilities).

Regarding the data sets used by our experiments, we consider the Star Schema Benchmark (SSB) [START_REF] O'neil | The star schema benchmark and augmented fact table indexing[END_REF] with dierent data sizes (01 Gb and 100 Gb).

VI.2. The obtained results

VI.2.1. UQP generation scalability

Size of components

In the rst experiments, we evaluate the process of partitioning a workload of queries in several subsets, where each subset contains queries that have high interaction between them. In this case we suppose that no cutting of hyperedges exists. We consider dierent query workloads randomly generated using SSB query generator [START_REF] O'neil | The star schema benchmark and augmented fact table indexing[END_REF] and a 100 Gb data warehouse.

We run our UQP generation tool and we calculate the number of components and their sizes (the number of queries in a component). As shown in the Table 3 [START_REF] Sellis | Multiple-query optimization[END_REF] needs more than ve days to generate a UQP for 30 queries. Yang's algorithm [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF] needs 10 hours generate a UQP for 20 00 queries. On the other hand, our algorithm takes about ve minutes to generate a UQP for 10 000 queries, for both OS (MV and HDP). This proves the scalability of our approach (Figure 3.20).

Quality of the unied query plan

To evaluate the quality of our approach, we consider the process of materialized view selection using the traditional approaches (e.g. Yang's algorithm [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF]) in generating UQP and our nding. Therefore, we run consider a workload of 30 queries and a 100 Gb SSB data warehouse SSB deployed in Oracle 11g DBMS. We use a server of 32 GB of RAM with Intel Xeon Processor E5530 (8M Cache, 2.40 GHz). The quality of each conguration is estimated using a cost model developed in our Lab (see Appendix IV).

VII. Conclusion

In this chapter, we rst identied the limitations of the existing studies dealing with the problem of generation of an optimal UQP. It should be noticed that this generation is crucial for the process of selecting OS. Secondly, with the fruitful collaboration with Graphics, Inc. realized for a long period to understand each other's, to nd a correct analogy and get familiar with their tools. Once the analogy found, we adapt the EDA partitioning algorithms and tools to our problem to generate the best UQP for a given workload. The experimental results prove Fig. 3.22 Workload execution times the eectiveness and the eciency of our approach when applied to a large workload of queries.

We also showed the impact of using our generated UQP for selecting materialized views.

I. Introduction

In the rst generation of database, the query interaction phenomenon has mainly been studied to resolve the problem of multi-query optimization (MQO) without considering OS [START_REF] Sellis | Multiple-query optimization[END_REF][START_REF] Sellis | On the multiple query optimization problem[END_REF][START_REF] Park | Using common subexpressions to optimize multiple queries[END_REF]. Afterwards, and after 10 years of waiting, it has been integrated to the process of selecting OS, especially materialized views [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Gupta | Selection and maintenance of views in a data warehouse[END_REF] in 1999. This is due to the query interaction brought by data warehousing. Recently, the query interaction has been revisited and exploited to deal with the classical database problems problem such as horizontal data partitioning schema selection [START_REF] Kerkad | L'interaction au service de l'optimisation à grande èchelle des entrepôts de données relationnels[END_REF], query scheduling [START_REF] Kerkad | L'interaction au service de l'optimisation à grande èchelle des entrepôts de données relationnels[END_REF][START_REF] Thomas | Scheduling and caching in multiquery optimization[END_REF], buer management [START_REF] Kerkad | L'interaction au service de l'optimisation à grande èchelle des entrepôts de données relationnels[END_REF], query caching in the context of distributed data stream [START_REF] Seshadri | Optimizing multiple queries in distributed data stream systems[END_REF]. As we said before (cf. Chapter 2), and to the best of our knowledge, the work of Kamalakar Karlapalem group, when he was in Hong Kong University of Science and Technology, was the pioneer that showed the dependency between the generated of UQP and the selection of materialized views [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Yang | A framework for designing materialized views in data warehousing environment[END_REF], but he misses to generalize his ndings to consider other OS.

Recall that the generation of the optimal UQP needs the enumeration of all possible UQP, which is not realistic in the context of big-queries. Furthermore, an UQP of big-queries can oer an exponential number of OS candidate. This makes the process of choosing the optimal conguration for OS hard. So, to facilitate the exploration of these candidates, subdividing their search space is recommended. In this chapter, we propose a scalable methodology to select the best OS based on UQP that incorporates OS knowledge's in the UQP generation process. Our methodology uses the hypergraph theory to generate the UQP (see Chapter 2), in which it captures the query interaction in two ways: (i) dividing the initial problem in a set of several disjoint small subproblems, which each one concerns a component of queries that will be exploited by the OS selection algorithm. This may contribute in reducing the overall complexity of the selection process. (ii) Injecting the OS knowledge when constructing the near-optimal UQP. Figure 4.2 shows the our methodology of constructing an OS-oriented UQP.

Queries UQP Solution Space

Candidate UQP

Algorithm

Algorithm

OS knowledge

Selected OS

Multiple Query Optimization

Physical Design

UQP Generation

OS

Selection

Fig. 4.2 Injecting OS knowledge in MQO for physical design problems

To conrm our claim regarding the strong dependencies between the processes of generation of OS and UQP, we consider two problems: the selection of materialized views (considered as redundant structures) and the selection of horizontal partitioning (considered as a nonredundant structure). This chapter begins by describing our methodology to generated OS-oriented UQP (Section II). Section III shows the methods used to resolve our two problems by considering several constraints and scenarios. Section IV presents our experiments that conrm our proposal.

Finally, Section V concludes this chapter.

II. A new approach for selecting OS

To transform an hypergraph to unied query plan by injecting OS knowledge, we need to dene a benet function that reects the non-functional requirements using OS (like minimizing the processing nodes, energy). This benet function is used to nd the important node (pivot node), that will be deleted from the hypergraph and add it, gradually to the UQP.

As detailed in the previous Chapter 2, the generation of UQP follows ve main steps:

Step 1: parses the SQL query to identify the logical operations (nodes).

Step 2: models the join nodes by a hypergraph, where the vertices set represents the set of join nodes and the hyperedge set represents the workload of queries.

Step 3: generates connected components using hypergraph partitioning algorithms.

Step 4: transforms each sub-hypergraph into an oriented graph using a cost model and implementation algorithms to order the nodes, in which the algorithms use OS knowledge.

Step 5: merges the graphs resulting from previous transformation to generate the global unied query processing (UQP).

To have a specic generation of OS-oriented UQP, the injection OS knowledge's in the step 4 is necessary. More concretely, it corresponds to dene a benet function to represent OS related the considered non-function requirement in the general formalization of the OS selection problem.

II.1. Generation of MV-oriented UQP

All views that have positive benet, are considered as potential materialized views. Intuitively, the views with minimum processing cost time have more chance to be selected. Hence, the non-functional requirement (minimizing query processing cost) can be translated to the benet function of each node n i , as follows:

benef it(n i ) = (nbr-1) * cost process (n i ) -cost mat (n i ) (4.1)
where nbr is the number of queries using n i , given that each node must be generated at least once before their use by queries, which gives the benet of reuse depends to the number of reusing nodes (nbr-1). cost process (n i ) is the processing cost and cost mat (n i )is the materialization cost of n i . Vertices of the hypergraph which maximize the benet function are selected rst so that their benet will propagates towards as much queries as possible.

II.2. Generation of HDP-oriented UQP

Using the selection predicate of a pivot node (that corresponds to the elected query), can eciently improve the quality of the nal partitioning schema by feeding the elected query with a HDP-oriented UQP.

To this end, we push down join operations for which the gain on their selection predicates is maximum. Nodes that have selection predicates with extreme selectivity factors (too high or too low) are ignored. The benet function of the node n i , corresponds to the participation of resulting fragments when their selection predicates are chosen. So, the benet function of the horizontal data partitioning is :

benef it(n i ) = (cost noF rag (n i ) -cost f rag (n i )) * nbr (4.2)
where:

nbr: is the number of queries using n i , cost f rag (n i ) is the processing cost of the node if its predicate selected for partitioning, and cost noF rag (n i ) is the processing cost of the node without data partitioning.

To satisfy the data partitioning constraints (maximum of fragments, and ignoring selection predicates with extremely selectivity), the procedure of identifying the pivot node has be modied, as follows, to be more sensitive to the chosen OS: Algorithm 4: getP ivotN odeHDP (Hypergraph H)

III. Application of OS-oriented UQP

In this section, we give two applications of OS-oriented UQP to resolve the problem of selecting materialized views and to dene the schema of horizontal data partitioning.

III.1. UQP as input for selecting materialized views

The MV-oriented UQP is used to propose candidate views with and without the storage space constraint.

III.1.1. New Formalization of MV selection

MV selection in DW using MV-oriented UQP is formalized as following:

Inputs:

-a DW with fact table F and d dimension tables {D 1 , ..,

D d }, -a workload Q of n queries, Q ={Q 1 , .., Q n }.
-a MV-oriented UQP that represents the unied query plan for Q.

Outputs:

-a set of materialized views to be materialized.

Constraints:

-a set of constraints S, related to store the selected views.

Objectives:

-the total query processing is minimized and the set of constraints is satised.

Resolving MV selection problem starts by proposing candidate views that are the join operations in the UQP (join nodes are chosen because they consume the most time to response a query). Only nodes with positive benet will be selected as candidate, in which nodes are ordered in descending order, following their benet. The benet of node is the cost of its processing minus the cost of materializing it.

III.1.2. Description of selection algorithm

We look to materialized views independently in each connected component (C C). In each selection of a view, the algorithm recalculates the benet of the remaining nodes by taking into account already selected nodes until no node with positive benet is found. Algorithm 5 details the dierent steps of our selection of view in each component. To select all views that optimize workload, we repeat the previous algorithm for each component in the UQP (Algorithm 6).

M V ← selectM V C (c); {get selected MV, Algorithm 5} 7: M V f inal ← M V f inal ∪ M V
Q of n queries, Q ={Q 1 , .., Q n }.
-set of m candidate views to be materialized V ={v 1 , .., v m }.

-a disk allocation policy (e.g., FIFO).

Outputs:

-scheduled queries of the workload into a new ordered set.

Constraints:

-a set of constraints S, like disk space to materialize views.

Objectives:

-the workload have the least execution cost.

The M V P considering QSP takes (i) A DW and (ii) a set of queries, (iii) a set of intermediate nodes candidates for materialization; a constraint representing the limited storage size. The problem aims at providing: (i) a scheduled set of queries and (ii) a set of MV that minimize the overall processing cost of queries and satisfying the storage constraint.

Consequently, we address the problem of dynamic materialized view selection by considering the query scheduling. A formalization of the problem of view selection considering the re-ordering of numerous queries is given as follows.

Inputs:

-a DW with fact table F and d dimension tables {D 1 , ..,

D d }, -a workload Q of n queries, Q ={Q 1 , .., Q n }.
-a MV-oriented UQP that represents the unied query plan for Q, -a disk allocation policy (e.g., FIFO).

Outputs:

-scheduled queries of the workload into a new ordered set.

-set of m candidate views to be materialized, V ={v 1 , .., v m }.

Constraints:

-a set of constraints S, like disk space to materialize views.

Objectives:

-the workload have the least execution cost, -satisfy all constraints, like the space occupied, in each period, by MV satises the space constraint.

Dynamic materialization with query scheduling has three main modules: the rst selects MV candidate, the second orders the queries and the third manages views materialization. These modules are discussed in the next sections.

III.2.2. MV Selection algorithm

Note that all nodes of the global plan are candidate for materialization which may represent a huge number. For instance, in our experiments, we consider 1 000 queries involving 1552 join nodes. As a consequence, a pruning mechanism is needed. It shall take into account the benet of the nodes and their constraints related to their storage and maintenance. To do so, we dene some functions: cost W O (q i , Φ): the processing cost of the query q i without view(s).

cost W V (q i , V j ): the query processing cost of query q i using the materialized view V j .

cost M at (V j ): the maintenance cost of the view V j .

Size(V j ): the cost needed to store the view V j .

We dene the benet of a given view V j (denoted by Benef it(V j )) by:

benef it(V j ) = cost W O (V j ) -cost W V (V j ) -cost M at (V j ) (4.3)
where cost W O (V j ) and cost W V (V j ) represent respectively the total processing cost of queries without/with the view V j . Instead of treating the whole search space including all candidates as in the usual approaches for MV, we propose to use a divide-conquer approach, where the search space is divided into several sub search spaces, where each one corresponds to a connected component of UQP. Contrary to the existing studies where they allocate the whole storage constraint to all views candidate, our approach allocates this storage to each component to be fair. Then, each component C k is processed individually, where its nodes are sorted according their benets and their ability to satisfy the storage constraint. Three selection cases are possible. Let N C k be the set of nodes of C k having a greater benet. The top nodes satisfying the storage constraint are selected.

III.2.3. Query scheduling

To avoid massively view dropping, we schedule queries. This is done by respecting the following principle: when a view is materialized, it should optimize the maximum of queries before its dropping. Therefore, we propose the following procedure supported by an example in which we consider a connected component with 14 queries (Figure 4. 3-a).

1. The identication of node(s) of each component with maximal benet (called queen nodes). In our example, four queen nodes are selected: {qn 1 , qn 2 , qn 3 , qn 4 } (represented by solid nodes in Figure 4.3-a). pruning the search space using elected query, that correspond to the rst query of pivot node.

IV. Experimental Evaluation and Analysis

IV.1. Experimental setting

In this section, we present an experimental validation of our approach. We developed a simulator tool in Java Environment. This tool consists in the following modules. HDP module, that takes a UQP as input and generates a Horizontal Partition Schema.

Another module is developed to implement approach of Yang et al., [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF] considering their two algorithms: feasible solution and 0-1 integer programming. We have developed the following functions: (a) generation of individual plan tree, (b) MVPP generation, using merging individual plans, (c) 0-1 matrix representation of using queries and plans (d) selecting materialized views, (e) and an estimation of query processing using materialized views.

Our tests are run in star schema DW context, which we have chosen a star schema DW. We have used Star Schema Benchmark (SSB) [START_REF] O'neil | The star schema benchmark and augmented fact table indexing[END_REF] with dierent sizes (01 Gb and 100 Gb) of data. for executing a given query. To perform this experiment, we developed a simulator tool using Java Environment. The tool can automatically extract the data warehouse's meta-data characteristics. The data warehouse used in our test is SSB (Start Schema Benchmark) [START_REF] O'neil | Star schema benchmark[END_REF]. Its size is 100Go, with a facts table Lineorder of 600 millions of tuples and four dimension tables: Part, Customer, Supplier and Dates. We used a SSB query Generator to generate 10000 queries for SSB data warehouse. Our evaluation is conducted using those queries, which cover most types of OLAP queries.

We proceed to generate MV-oriented UQP and HDP-oriented UQP for dierent workloads of queries varying from 30 to ten thousands (10000) queries. The resulting UQP are then used by two dierent OS-selection algorithms : the MV-selection algorithm and the HDP-selection algorithm. As shown in Figure 4.4 we see that the MV-oriented UQP always produces a better set of candidate views to materialize than the HDP-oriented UQP. Reciprocally, Figure 4.5 shows that the HDP-oriented UQP always leads to a better fragmentation schema than the MV-oriented UQP. The dierence in performance gain increases with the number of queries.

IV.2.2. Oracle Validation

Finally, in order to validate our theoretical results, we select materialized views candidates and the fragmentation schema using our OS-oriented UQP generation modules for two workloads of 500 and 3000 queries respectively, and we deploy the results in Oracle 11g DBMS.

IV.3. The quality of OS-oriented UQP IV.3.1. Theoretical validation

To evaluate the impact of our obtained MV-oriented UQP on the problem of selecting materialized views. We compare the algorithm detailed above and compare it against Yang et al. [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF]. To estimate the query processing and views maintenance costs in our tests, we used a To perform this experiment, Ww consider a workload of 30 OLAP queries running on two data warehouses (1GB and 100GB). The obtained results are described in Figure 4.12. They show that our method is rather slightly better than its competitor.

To test our approach for a large number of queries, we conduct a series of tests with workload of varying sizes (generated randomly using SSB-query generator ). The dierent types of queries are: queries 1-joins, 2-joins, 3-joins and 4-joins; with also aggregation and group-by. For each workload, its UQP is generated and MV selection algorithm is applied. We estimate the cost of the workload with and without using views (cost with and cost without respectively), and we calculate the optimization rate (1-cost with /cost without ). As shown in Figure 4.13, our approach becomes more interesting as the number of queries increase (90% optimization rate for a workload of 10000 queries). [START_REF] O'neil | The star schema benchmark and augmented fact table indexing[END_REF] with 100 GB of data. We consider a workload of 30 queries running on the data warehouse with 100 GB. The obtained results described in Figure 4. In the rst experiments, we test the interest of dynamic and query scheduling on optimizing queries. To perform our experiments, we consider a data warehouse with dierent sizes (1Gb, 10Gb, 100Gb and 1 Tb) and a workload of 30 queries, the candidate nodes are selected using our approach. Three scenarios are considered: (i) naive scenario in which nodes are materialized till the saturation of storage space, (ii) materializing without scheduling using our dynamic approach and considering the workload as pre-ordered 2 and (iii) materializing with query scheduling. The overall cost of queries in terms of inputs/outputs is then computed by varying the storage constraint. Figure 4.15 summarizes the obtained results. The main lesson is: the dynamic materialization with query scheduling outperforms the other scenarios whatever the size of the data warehouse. This shows the interest of incorporating the query scheduling in materializing views.

In the second experiments: we test the performance of our approach compared with two existing approaches: Phan et al.'s method [START_REF] Phan | Dynamic materialization of query views for data warehouse workloads[END_REF], and Yang et al.'s method [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF]. For Phan method, we have developed the following algorithms: (i) a genetic algorithm to nd an optimal query permutation by emulating Darwinian natural selection of 1000 generations; (ii) algorithm to select candidate nodes which are the nodes that have greater benet have been selected as candidates (in Phan et al.'s, they are used DB2 advisor to have those all nodes with greater benet); (iii) pruning algorithm of candidate views using their benet; (iv) an evaluation algorithm to estimate the total net benet of using pruned candidate views set by query workload;

(v) algorithm to manage the cache of the views (LRU ). For Yang et al. approach's [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF], we 2 The query scheduling module of our approach in this case is obsolete. ). Despite this, the sole use of these structures is not sucient to gain eciency during the evaluation complex OLAP queries over relational DW. To deal with this data deluge and simultaneously satisfy the requirements of company's decision makers, distributed and parallel platforms have been proposed as a robust and scalable solution to store, process and analyze data, with the layers of modern analytic infrastructures [START_REF] Eavis | High performance analytics with the r3-cache[END_REF]. Editors of DBMS already propose turnkey parallel platforms to companies to adopt these solutions (e.g., Teradata). Another alternative is to go to the Cloud (e.g. Amazon Redshift). Note that these solutions may become rapidly expensive when data size grows. For instance, the cost of storing 1 Tera-bytes of data per year in Amazon Redshift is about 5 500 USD. Several eorts have been deployed to ensure a balance between low cost and high performance solutions to manage this deluge of data. Several initiatives have been deployed to avoid turnkey parallel platforms, by constructing a series of commodity DBMS systems, "glued together" with a thin partition-aware wrapper layer. Google's search clusters reportedly consist of tens of thousands of shared-nothing nodes, each costing around $700 [START_REF] Dewitt | How to build a high-performance data warehouse[END_REF]. Such clusters of PCs are frequently termed grid computers. Other initiatives combine the cheapest DBMS and Cloud technology. We can consider the example of Alibaba company. In their recent works published in VLDB 2014 [START_REF] Cao | Realization of the low cost and high performance mysql cloud database[END_REF], they propose a MySQL driven solutions to deal with the data deluge over the Cloud.

The most used parallel DW systems are Oracle Exadata, Teradata, IBM Netezza, Microsoft SQL server Parallel data warehouse, Greenplum.

Regardless of the way in which a parallel DW is designed, it requires integrating our ndings in the discussed phases. These steps are quite sensitive to the workload. We have already shown the strong interaction between the UQP and the horizontal partitioning selection in the context of centralized DW. Since the partitioning is a pre-condition of any parallel database design [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF] and its schema is used by all steps of the parallel DW life design life cycle, it is worthy to integrate the volume and sharing of queries in this design.

In this chapter, we discuss this integration. To do so, we propose and experimentally assess an innovative methodology guided by the big query interaction for designing Parallel RDW 1 http://www.economist.com/node/15579717 (P RDW ) on shared nothing database cluster architecture. To explore the large number of queries, we use UQP that helps us in visualizing our workload and partitions it, if necessary, into several components to reduce the complexity of the design. Then, we focus on two major problems when designing P RDW which are data partitioning and fragment allocation.

The chapter is organized as follows. Section II discusses the main alternatives in designing parallel relationalDW . Section III depicts a motivating example. Section IV contains the details of our P RDW design methodology. Section V provides our experimental results obtained from testing the performance of our approach using dataset of the Star Schema Benchmark (SSB).

Finally, Section VI concludes the chapter and discusses some open issues.

II. Parallel Database Design Alternatives

Based on the above discussion, we assert that parallel DW design can be modelled by the following tuple [START_REF] Benkrid | A global paradigm for designing parallel relational data warehouses in distributed environments[END_REF]: < Arch, DP, DA, DR, LB >, where: Arch denotes the parallel architec- ture, DP the data partitioning scheme, DA the data allocation scheme, DR the data replication scheme and LB the load balancing scheme, respectively. Note that the problem corresponding to each component of the above tuple is NP-hard [START_REF] Apers | Data allocation in distributed database systems[END_REF][START_REF] Wolfson | Distributed algorithms for dynamic replication of data[END_REF].

Two main methodologies exist to deal with the problem of parallel DW design: iterative design and conjoint design. Iterative design methodologies have been proposed in the context of traditional distributed and parallel database design [START_REF] Saccà | Database partitioning in a cluster of processors[END_REF][START_REF] Stöhr | Warlock: A data allocation tool for parallel warehouses[END_REF][START_REF] Rao | Automating physical database design in a parallel database[END_REF][START_REF] Furtado | Experimental evidence on partitioning in parallel data warehouses[END_REF]. The idea underlying this class of methodologies consists in rst fragmenting the relational DW using any partitioning algorithm, and then allocating the so-generated fragments by means of any allocation algorithm. In the most general case, each partitioning and allocation algorithm has its own cost model. The main limitation of iterative design is represented by the fact that they neglect the inter-dependency between the data partitioning and the fragment allocation phase, respectively. Figure 5.1 (a) summarizes the steps of iterative design methodologies. To overcome these limitations, the combined design methodologies were proposed in [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF]. They consist in merging some phases of the life cycle of the distributed/parallel life cycle. The main idea of this merging is that a phase is performed knowing the requirements of the next step. Three main variants of this methodology are distinguished (Figure 5.1 ((b),(c),(d)). The conjoint design methodologies that have been addressed in Soumia BENKRID thesis, elaborated in our laboratory LIAS [START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF] and tested in Teradata machine [START_REF] Bellatreche | Verication of partitioning and allocation techniques on teradata DBMS[END_REF].

Figure 5.1 (b) depicts an architecture, where the basic idea consists in rst partitioning the DW using any partitioning algorithm and then determining how fragments are allocated to the nodes by also determining replication of fragments. The main advantage of this architecture is that it takes into account the inter-dependency between allocation and replication, which are closely related [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF]. The main limitation is the fact that it neglects the inter-dependency between the data partitioning and fragment allocation. Figure 5.1 (c) shows a second variant of the conjoint design, in which the DW is rst horizontally partitioned into fragments, and then fragments are allocated to nodes within the same phase as in [START_REF] Saccà | Database partitioning in a cluster of processors[END_REF]. After that, a replication algorithm is The basic dierence between the four reference architectures depicted in Figure 5.1 is represented by the selection of partitioning attributes. The iterative approach determines the partitioning attributes using a cost model that neglects the inter-dependency between partitioning, allocation and replication.

Formally, our parallel DW design problem that considers the dierent phases of the life cycle can be formalized as the following Constraint Optimization Problem. Given:

Inputs:

-a parallel platform (P P) with P nodes N = {N 1 , N 2 , . . . , N P }; -a relational DW modeled according to a star schema and composed of one fact table F and d dimension tables D = {D 1 , D 2 , . . . , D d } (similarly to [START_REF] Lima | Parallel OLAP query processing in database clusters with data replication[END_REF], we suppose that all dimension tables are replicated over the nodes of the parallel platform and can t in main memory); -a set of star join queries Q = {Q 1 , Q 2 , . . . , Q L } to be executed over PP, each query Q l characterized by an access frequency f l .

Outputs: -data allocation strategy of fragments over processing nodes;

-query processing strategy over processing nodes.

Constraints:

-the maintenance constraint W representing the number of fragments that the designer considers relevant for his/her target allocation process (note that this number must be greater than the number of nodes, i.e. W P ) -the replication constraint R, such that R ≤ P, representing the number of fragment copies that the designer considers relevant for his/her parallel query processing; -the attribute skewness constraint Ω representing the degree of non-uniform value distributions of the attribute sub-domain chosen by the designer for the selection of the partitioning attributes; -the data placement constraint α representing the degree of data placement skew that the designer allows for the placement of data; -the load balancing constraint δ representing the data processing skew that the designer considers relevant for his/her target query processing.

The problem of designing a DW over the parallel platform (P P ) consists in fragmenting the fact table F based on the partitioning schemes of some/all dimension tables into N , N >> P fragments and allocating them and the replicated fragments over dierent nodes of the parallel platform such that the total cost of executing all the queries in Q can be minimized while all constraints of the problem are satised. In this thesis, we focus on the variant of DW parallel design in which the partitioning and allocation phases are combined. This design has been called F &A design [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF]. In the next section, we show the impact of considering query interaction on the horizontal partitioning.

III. Motivating Example

, To the best of our knowledge, even some studies of P RDW design considering the interaction between queries exist, but none considers the Big Interacted Queries Phenomenon. In this section, we study the impact of this phenomenon in two phases: data partitioning and fragment allocation. To illustrate this nding, let us consider an example with a P RDW with the following conguration:

A star schema composed of one fact table: Lineorder and four dimension tables : Supplier, Dates, Customer, and Part.

On the top of this schema, 10 star queries {Q 1 , .., Q 10 }. The unied plan is described in , ...} and V alue ∈ Domain(Attribute)), a join operation, denoted by J i and a projection operation denoted by π. We note that seven (7) selections and joins are identied.

The candidate attributes with their respective domains to perform the partitioning are given in Figure 5.

Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Q 8 Q 10 Q 7 Q 9 J 2 J 3 J 4 J 5 J 6 J 7
S ,1995,1996,1997,1998 d_year

C 1 ={Q 1 ,Q 2 ,Q 5 ,Q 7 ,Q 8 ,Q 10 } C2={Q 3 ,Q 4 ,Q 6 ,Q 9 }
F 1 ={s_region='America' and c_nation='France'} F 2 ={s_region='America' and c_nation='United State'} F 3 ={s_region='America' and c_nation='China'} F 4 ={s_region='America' and c_nation='United Kingdom'} F 5 ={s_region <> 'America'}

C 1 = {Q 1 , Q 2 , Q 5 , Q 7 , Q 8 , Q 10 } and C 2 = {Q 3 , Q 4 , Q 6 , Q 9 }.
Each component contains a set of queries that share at least one join operation. The rst shared join node is called the pivot node of the component and the set of selection predicates of its branches called set of landmark predicates.

In our case, we have two pivot nodes (J 1 for the component C 1 and J 2 for the component C 2 ) with their sets of landmark predicates are {s_region = "America"} and {d_year = 1998}, respectively.

Note that the pivot node notion is quite important, since it guides the partitioning process of a component by the means of its set of landmark predicates. A landmark predicate partitions its corresponding table (a leaf node of the plan) into two partitions, one with all instances satisfying the predicate (e.g., s_region = "America") and another representing the ELSE partition (s_region = "America"). Note that the partitioning of dimension tables will be propagated to partition the fact table. This partitioning is called derived partitioning [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF]. This initial partitioning schema of a component will be rened by considering other predicates of the set of landmark predicates and other predicates do not belonging to pivot node (e.g., S 4 ).

In the case, where the obtained fragments of each component are allocated over these nodes in round robin fashion, the maximum number of algebraic operations will be executed over all the cluster nodes. Therefore, queries of a given partitioned component (e.g., C 1 ) will get benet from this process.

The remaining fragment of the initial component (F 5 in our example) will be concerned by the partitioning process of the component C 2 . The above partitioning and allocation reasoning applied to C 2 (Figure 5.2-g). Note that the queries of the component C 2 need fragments of the component C 1 .

A partitioning order has to be dened among components. In our proposal, we favorite the component involving most costly queries. The components with an empty landmark predicate set are not considered for the partitioning process.

IV. UQP as a service for designing PRDW

In this section, we consider that data partitioning and allocation are performed iteratively and exploits the query interaction. First of all, we start with the data partitioning phase then the allocation of the obtained fragments.

IV.1. The Data Partitioning Phase

The problem of data partitioning in the context of P RDW may be formalized as follows:

Inputs :

-a DW with fact table

F and d dimension tables {D 1 , .., D d }, -a workload Q of n queries, Q ={Q 1 , .., Q n }, -a DataBase Clusters (DBC ) with M processing nodes, N ={N 1 , .., N M };
Outputs : -a data partitioning schema.

Constraints : -disk spaces of nodes, and maintenance cost representing the maximum number of generated fragments that the designer want to have (W ).

Objective: -minimize the make-span of the workload Q over DBC and satisfy the cited constraints.

IV. UQP AS A SERVICE FOR DESIGNING PRDW

IV.2. Partitioning Algorithm Description

The algorithm aims at ensuring equitable node processing by generating eective data partitioning and fragments allocation schemes using query interaction. The partitioning process is guided by sharing expensive operations (e.g. joins), where data needed to process these operations (determined using landmarks predicate), will be partitioned and distributed over cluster-nodes.

The sharing operations are described using the UQP where they are regrouped in several components. Thus, the partitioning is driven by one operation shared by one or more components Identifying of landmark predicates: an UQP composed of a set of components, in which each component has pivot node that corresponds to the rst join operation, and the landmark predicate corresponds to selection predicate of its branch.

Annotation of UQP: is a operation to represent each component of the UQP by a landmark predicate.

Generation of partial data partitioning schema: is an operation to generate a partial partitioning schema of one component (sub-set of queries).

Generation of partial fragments allocation:: is an operation to generate a partial fragments allocation of one component (sub-set of queries).

IV.2.1. Annotation of UQP

Each Landmark Predicate, noted by lp, represents one or more components but each component is represented by only one landmark predicate. We call Components Area of lp (C A lp ), all components represented by lp. Hence, the query workload can be represented by a set of Landmark Predicates, called LP . Each landmark predicate lp, is annotated by a weight w(l p ) which equals to the sum of processing cost of all queries of their component area

(C A lp ). Let isComponentArea(Q i , l p ) a boolean function that returns 1 if Q i is in the component area of l p , 0 otherwise. W (l p ) is dened as follows: W (l p ) = L i=1 Cost(Q i ) × isComponentArea(Q i , l p ) (5.1)
The elements of landmark predicate list LP , are sorted in the descending order of their landmark predicates weights W (l p ).

IV.2.2. Generation of Partial Data Partitioning Schema

We use an incremental partitioning, where in each step, we generate a data partition schema for a subset of queries presented by component area. For each component area, we start by a fragment preparation that splits data into two fragments, using a landmark selection predicate of the component area. The rst is the initial fragment (noted Candidate F rag ) that will be used to generate the partial data partition schema and the second is the remaining partition (noted N oCandidate F rag ), which will be kept the next partitioning step. We note that the rst fragment is all data to be partitioned (e.g., fact table). In the following, we give the steps of our Partial Data Partitioning:

Preparation of attributes partitioning. We identify all possible attributes which have more than value in their sub-domains in the denition of the fragment object to the partial partition. These attributes are divided into two categories: the rst category called rst candidates (FC ) contains attributes not used by the queries in the component area, and the remaining attributes are called second candidates (SC ). The partition starts using rst candidates (FC ) to split the fragment such that each query can be processed by the maximum of cluster nodes. When there is none attribute in FC, the partition process uses SC to select attribute partition.

Iterative fragment splitting. The partial partitioning is a sequence of splitting operations, where each split is applied on one fragment to produce two fragments. So, the partial partition schema starts with on fragment and it increases by one in each splitting.

Each split is applied on the most voluminous fragment. The volume is dened by the selectivity factor that equal the multiplication of selectivity factors of all attributes that participate on the denition of the fragment, and the selectivity of attribute is the sum of the selectivity of their sub-domain. The splitting attribute corresponds to the attribute that has the minimum values in its sub-domain, and the splitting operation divides the sub-domain of n values into two sub-domains, each one has n/2 values if n is pair else one sub-domain has (n + 1)/2 values and the other has (n -1)/2 values. The splitting process continues until produce m fragments (m is number of cluster nodes) are produced.

The previous steps are repeated for all component areas.

IV.2.3. Generation of Partial Fragment Allocation Schema

To allocate each Partial Data Partitioning Schema generated, we use a round robin placement, in which the allocation unit is a fragment. The placement algorithm is simple: we aect the voluminous fragment in the node that has the maximum free space, and so on.

After placement process, the system veries the maintenance constraint. With the existence of big-queries (big number of components), the number of fragments can be superior to the predened threshold W . In this case, it will be necessary to merge fragments in each cluster node. The merging starts with the smallest fragments.

Once the data placement schema is generated, we compute the cost of executing the set of queries Q over M nodes in terms of number of inputs-outputs.

V. Experimental Evaluation and Analysis

This section reports the results of an experimental evaluation of our proposed approach. Our simulation conducted on a computer with 3.4GHz Intel(R) Core(TM) i7-3770 equipped with 8GB RAM. Algorithms were carried out in Java programming language. For the hardware architecture, we simulate a homogeneous Database Cluster of 8 to 128 nodes. The dataset from the Star Schema Benchmark (SSB) [START_REF] O'neil | The star schema benchmark and augmented fact table indexing[END_REF], it has dierent sizes (from 100 GB to 2TB).

Algorithm 9: Partial data partition algorithm (partialP artition) f rag ← getBigF ragment(P P S);{get the volumounus fragement in P P S} (f rag 1 , f rag 2 ) ← split(f rag, att);{Split the fragment using attribut att} 19:

add(f rag 1 , P P S); {add f rag 1 to P P S} 20:

add(f rag 2 , P P S); {add f rag 2 to P P S} 21: delete(f rag, P P S); {delete f rag from P P S}

22:

nbrF rag ← nbrF rag + 1;

23: end while

Several workloads randomly generated, are used (their sizes vary from 32 to 10 000 queries).

In all experiments the query processing are estimated as the number of I/O. Our tests have two objectives: (i) compare the performance of this approach with a recent good approach of PRDW designing [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF] and (ii) check the quality and scalability where workload and databases size change.

V.1. BQ-Design vs. F &A As a rst experiment, we study the performance of our proposed methodology BQ-Design, compared against F &A approach [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF], where allocation phase is done at partitioning phase; the fragmentation phase uses a Genetic Algorithm and the allocation phase is based in innovative matrix-based formalism and a related fuzzy k-means clustering. For each PRDW design methodology, we set the fragmentation threshold W to 500 and we measured the query execution time versus the variation of the number of database cluster nodes M over the interval 120 V. EXPERIMENTAL EVALUATION AND ANALYSIS [8:32]. Figure 5.4 shows the results obtained and conrms to us that the BQ-Design approach outperforms the F &A one; since oers 18%-39% savings. The F &A approach has proven that is practical and reliable a real-life parallel processing database system, Teradata DBMS [START_REF] Bellatreche | Eectively and eciently designing and querying parallel relational data warehouses on heterogeneous database clusters: The f&a approach[END_REF]. To check BQ-Design quality when changing the number of cluster, we conduct the same experiment, we calculate the speed up factor for each approach.

Fig. 5.8 The impact of workload size on data distribution quality

The rst experiments studies the impact of the workload size on the quality of data distribution.

To do so, we used 32 cluster nodes, dataset with 2 TB and two workloads with 100 and 1000 queries respectively. By analyzing the obtained results in

VI. Conclusion

In this chapter, we motivated the consideration of the query interaction in designing parallel DW under concurrent analytical queries. We proposed a new scalable P RDW designing approach that can generate eective data partition and data placement schemes. The main steps of our approach are: (i) capturing of interaction among queries (HDP -oriented UQP).

(ii) Generation of landmark predicates that performed by using connected components that compose the UQP. (iii) Elaboration of modular data partition and data allocation, guided by the components of UQP.

Our approach has been compared against the most important state of art works and the obtained results show the eciency and eectiveness of our approach. It has been tested under big size workload (10 000 queries) and shows its scalability.

I. Introduction

To assist administrators in their physical design tasks, several commercial advisor tools were proposed to suggest recommendations to DBA for choosing optimization structures. We can cite, for instance, the Microsoft AutoAdmin, Database Tuning Advisor (which is part of Microsoft SQL Server 2005) [4], the DB2 Design Advisor [START_REF] Valentin | Db2 advisor: An optimizer smart enough to recommend its own indexes[END_REF] and the Oracle Advisor [START_REF] Bayer | The universal b-tree for multidimensional indexing: General concepts[END_REF]. Recently, The Azure SQL Database 1 provides recommendations for creating and dropping indexes, parameterizing queries, and xing schema issues. The recommendations that are best suited for a query workload are recommended. Other advisors have been also developed by academicians. Parinda ( [START_REF] Maier | PARINDA: an interactive physical designer for postgresql[END_REF], developed by Data-Intensive Applications and Systems Laboratory of the EPFL School, Lausanne, Switzerland, and SimulPh.D. [START_REF] Bellatreche | A physical design simulator tool[END_REF][START_REF] Bellatreche | Primary and referential horizontal partitioning selection problems: Concepts, algorithms and advisor tool[END_REF], developed in our laboratory LIAS/ISAE-ENSMA, and RITA (An Index-Tuning Advisor for Replicated Databases) [START_REF] Tran | RITA: an index-tuning advisor for replicated databases[END_REF] a joint work between Oracle, Google and the University of California, Santa Cruz and EPFL, etc. These advisors are DBMS-dependent and mainly concentrated in developing self-managing systems that can relegate many of the database designer's more mundane and time-consuming tasks [START_REF] Zilio | Db2 design advisor: integrated automatic physical database design[END_REF]. These tools use cost models of their optimizers. Some of these tools focus on one OS such as RITA elaborated for indexes, whereas the majority deals with several OS. Table Table:advisors recapitulates these advisors in terms of used OS.

These tools intensively use cost models to suggest recommendations. They are not designed to deal with volume of interacted queries. To overcome this limitation, we propose a new tool, called Big-Queries that exploits the query interaction of numerous and complex queries. In the section III, we describe the main modules of the framework. Section IV gives a technical description of the frameworks. Finally, Section V concludes this chapter.

II. System architecture

In this section, we describe the architecture of Big-Queries. It is composed of four components: feature extractor, UQP generator, physical design advisor and deployment advisor. The feature extractor gets all needed parameters like database parameters. The UQP generator transforms query interaction of workload in UQP, using a set of tools and algorithms inspired from hypergraphs theories. The physical design advisor is a set of tools that help the DBA to select OS following non-functional requirements and it estimates the quality of a schema before their deployment in real system. The deployment advisor is a set of tools that help the DBA to propose a deployment schema (data partitioning and allocation) tacking account many parameters like the processing nodes, parallel execution, etc.

The framework architecture of our demonstration is described in Fig6.2. In the following sections, we will briey present our underlying models.

II.1. Features Extractor

Features extractor allows to get databases parameters, system parameters (storage device, buer, processing nodes, etc), related query properties (selectivity, operators, tables), OS constraints (injected by the DBA). These properties are extracted automatically using databases statistical model, parsing queries and dierent les.

II.2. UQP Generator

The UQP generator is used to transform a set of queries into an unied query plan. It uses a set hypergraphs algorithms (in our case, we have used multi-level hypergraph partitioning algorithms [START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF]), UQP generator generates an unied query plan oriented for a specic OS (See Chapter 3). It uses a mathematical model called (cost model), to estimate the cost of query, logical operation, workload of queries or related OS costs. The cost model uses parameters of queries, system catalog (Buer, disk space, processor capability, main memory characteristics, system architecture, etc), See Annexe annexe02. Big-queries can generate the UQP in specic format that can be visualized directly Cytoscape Plug-in 2 as show in the Figure 6.3. For each optimization structure, the physical design advisor can give an estimation of the execution time within that structure. This assists DBA to take a decision about its selecting or not.

II.4. Deployment Advisor

Deployment advisor proposes a data partitioning and data allocation for designing Parallel RDW (P RDW ) on shared nothing database cluster architecture. It allows simulating the quality of parallel DW before their implementation in real machine.

III. System Modules

We develop our Big-queries is composed of a set of independent modules to integrate any algorithm. This means that, the DBA can plug any OS selection algorithm for the studied structures (UQP, MV, HDP schema, allocation schema). All these modules will be discussed in the next sections.

III.1. Query parser module

In this module, users can give either a single SQL query or workload to be executed. Queries supported vary from simple transactional operations to more complex reporting operations involving several large size tables. The parser takes as an input a text written in a specic language such as SQL and converts it into a parsed tree. To check whether every relation, attribute, or view mentioned in the FROM-clause belongs to the schema of database or data warehouse (using the meta-model).

To check whether every attribute mentioned in the SELECT/WHERE-clause belongs to the relations appeared in the FROM-clause.

To check whether attributes' types are respected in the Condition-clause. a verication whether views are involved in the current query or not. Each virtual view in the query parse tree will be replaced by a sub-parse tree that represents the subquery constructing this view. Note that in the case of materialized views, there is no substitution, because these latter are considered as base tables (relations).

III.2. Logical query plan generator

The module of selection the logical query is based on the algebraic equivalences. A query is composed of dierent operations which follow algebraic laws (commutativity, associativity, and distributivity), and can be applied in both directions: from left to right, and from right to left.

The generation of the logical plan of a query follows two principal steps: (1) transforming the parsed tree to a logical query plan, and (2) improving the logical query plan using algebraic laws, and (3) selecting an appropriate logical plan using a cost model. The module query processing cost estimator, allows estimating the cost of query or set of queries taking account or not of optimization structures (materialized views and horizontal data partitioning). To estimate query processing cost, this module needs to rewrite queries following selected optimization structures.

In the relational model, the query is processed using a tree-like physical plan, where each node represents an algebraic operator (selection, join, projection) and each operator is tagged by The real cost of query processing is done by time unite (e.g., second), that corresponds to consuming time from the starting query processing until the result is given by the DBMS.

This cost depends on two parameters: (1) The input/output cost that is the time of loaded data from storage devices (in our case: Hard disk ). ( 2) The CPU cost (C CPU ) that depends on the physical layout, input/output and the number of arithmetic and logical operations. Parallel to using cost models to estimate query processing and to select the optimal plan, other cost models are used in selecting the optimal OS as MV and HDP. In addition, each OS has its own cost functions that estimate their impacts in query execution time and physical parameter like disk space.

The cost model used to develop our estimator module is detailed in the appendix IV. Fig. 6.12 Gateway connexion of database

The set of software of our simulator represents applications that give a graphic interface to evaluate a solution without monopolizing of a real design of physical nodes processing. They use a mathematical model to simulate the functionality of the target system with its physical parameters. So, these softwares can give good indicates about query processing, material architecture, system properties in a short amount of time with lower cost. The simulation allows the comparison of many scenarios by measuring the performance of dierent data.

V. Conclusion

In this chapter, we presented our Big-queries advisor composed of a set of tools to help the DBA to perform the database physical design and deployment. Big-queries takes advantages of the hypergraph theory to exploit in ecient way the volume of interacted queries to select OS and the deployment platform for a given DW application. Our tool is considered as the core of the simulation of all processes that we discussed in this thesis thanks to our algorithms and cost models. Currently, we are integrating other OS such as indexes and replication of data fragments over cluster nodes.

Part III Conclusion and Perspectives

Wrap-up

In this chapter, we summarize the contributions of our thesis, discuss the results and provide an overview of possible future issues.

I. Summary

Processing large amount of queries issued by advanced applications involving mass data issued from social media, E-commerce Web sites, scientic experiments, etc., as social network, E-commerce, scientic, sensors, etc. has to consider the interaction among queries. This interaction is materialized by the reuse of common intermediate results of these queries. Another important point that motivates our claim is the crucial role that queries play in dierent phases of the life cycle of database/data warehouse design, especially for physical and deployment phases.

It should be noticed that various advisors and tools developed by the most important editors of commercial and academic DBMS either in the context of centralized databases (e.g., DB2

Advsiors [START_REF] Valentin | Db2 advisor: An optimizer smart enough to recommend its own indexes[END_REF], Database Tuning Advisor for Microsoft SQL Server [4], [START_REF] Maier | PARINDA: an interactive physical designer for postgresql[END_REF] for PostgreSQL, etc.) or in distributed databases (e.g. Schism [START_REF] Curino | Schism: a workload-driven approach to database replication and partitioning[END_REF]) exist. They aim at recommending to administrators optimization congurations such as indexes and materialized views. The majority of them are based on workloads. Hence, the question of integrating the volume and interaction of queries is no longer about why doing that, but instead how we can do it in an ecient manner, and for which phases ? Therefore, this thesis revisits the multi-query optimization a classical concept introduced in 80's , and leverages it by our two dimensions which are query volume and sharing. Our methodology was designed to rst dene a data structure adapted to our study, and then to evaluate its eciency and eectiveness regarding two famous problems of the physical design of a relational data warehouses which are materialized view selection and horizontal data partitioning, as well as the problem of parallel data warehouse design.

We would like to mention that our thesis covers large spectrum of topics: multi-query optimizations, data warehouses, physical design, deployment phase, hypergraphs, cost models, etc. To facilitate the presentation of our nding, we xed some objectives: (i) to conduct a survey of the most important concepts, techniques, algorithms and tools presented in this thesis. This objective forced us to be more precise and to present comparison and analysis of the studied concepts. (ii) to clearly outline our collaboration with Mentor Graphics that yields the analogy between the problem of representing a unied query plan of a workload and an electronic circuit. This collaboration is the key success of our thesis, since it brings us several positive results at research (discovering a new discipline) and personal terms (working, sharing and transmitting our problems and knowledge to the engineers of Mentor Graphics). (iiii) to choose relevant case studies for the deployment of our hypergraph structures, (iv) to develop a tool that capitalizes our nding and assists designers and administrators during their tasks and nally (v) to conduct intensive experiments using our developed simulators within commercial DBMS (Oracle in our case) to evaluate the quality of our ndings.

I.1. Surveys of Logical and Physical Optimizations

We have elaborated an in-depth analysis of how state-of-the-art database manage the interaction among queries and how it is exploited in logical, physical optimizations and the deployment phase of the life cycle of the data warehouse. Based on these surveys, we provided new classications related to logical and physical optimizations that concern multi-query optimization, generic formalization of the problem of the physical design, examples of its instances: materialized views, indexes and horizontal data partitioning, and dierent used algorithms with their implementation environments (centralized, distributed and parallel architectures).

I.2. Hypergraphs driven Data Structure for Management of Volume and Sharing of Queries

The rst contribution of our thesis is the fruit of our collaboration with Mentor Graphics Company to nd an analogy between an electronic circuit and a unied query graph. This collaboration gave rise to an approach called SONIC (Scalable Multi-query OptimizatioN through Integrated Circuits). This latter is based on a hypergraph structure that can represent any unied query plan, by ignoring the query order as done in the most traditional approaches [START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF]. Once it is generated, it is explored by a greedy algorithm that partitions it by the means of hypergraphs partitioning library (HMETIS), and selects the most important node of each partition (called pivot node) that can be candidate for sharing. The pivot node is similar to the principle of queen-bee.

Our approach was validated to evaluate its eciency in terms of execution time and quality by considering the process of selecting materialized views.

Furthermore, we investigated the scaling behavior of our approach by considering very large

I.4. Query Interaction in the Deployment Phase

We investigated the role of our hypergraph structures in the process of designing parallel warehouses. Due to the complexity of this phase that includes several steps: data partitioning, data allocation, load balancing, etc. we have only focused on the two rst phases; data partitioning and data allocation. We thus presented HYPAD approach (HYper-graph-driven approach for PArallel Data warehouse design) that does the following tasks: (i) capture of interaction among queries. (ii) Generation of landmark predicates using connected components that compose the unied query plan. (iii) Elaboration of modular data partition and data allocation, guided by the components of the unied query plan. Our approach is compared against the most important state of art works and the obtained results show its eciency and eectiveness. It has been tested under big size workload (10000 queries), that shows its scalability. Note that mathematical cost models have been elaborated and used by our simulator.

I.5. Big-Queries

We presented our tool textitBigQueries, a sort of advisor that takes advantages of the interaction among a large amount of queries. Actually, it gives recommendations for selecting two optimization structures in isolated way: materialized views and horizontal partitioning. It is a modular tool, that can: (1) oer DBA the possibility to select dierent optimization structures, based on the interaction of queries, (2) give an estimation of query performance, (3) generates and displays a unied query plan and (4) recommends optimization congurations regarding the deployment phase that suggests partitioning schemes and fragment allocation schema for a given workload. The functional architectures of these two tools have been elaborated based on existing academic and commercial advisors and tools. We would like to mention that Big-Queries tool has been used in Graduate Master course "Big Data" given in Poitiers University.

Based on the feedbacks of students, it has been incrementally improved in terms of interface and dierent functionalities such as cost models.

Our tools are open sources and available at the forge of our laboratory LIAS (http://www.liaslab.fr/forge/projects/bigqueries). Actually, 86 downloads have been done, which represents an asset for students and researchers.

II. Future Work

In this section, we identify open issues related to the set of our contributions. We dierentiate between two major classes of issues, namely the hypergraph structure and its usages.

II.1. Hypergraph Structure

In this case of issues, we distinguish three main challenges that have to be addressed in the near future: testing of other hypergraph partitioning tool, dynamic construction of hypergraph and exploratory algorithms.

II.2. Testing Other Partitioning Hypergraph Tools

The popularity of hypergraphs and the increasing demands of IT companies in using them, motivate the research community to develop eective hypergraph partitioning tools: hMeTiS [START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF], PaToH [START_REF] Catalyürek | Patoh: a multilevel hypergraph partitioning tool[END_REF] Mondriaan [START_REF] Vastenhouw | A two-dimensional data distribution method for parallel sparse matrix-vector multiplication[END_REF], and parallel tools such Parkway [START_REF] Trifunovic | Parkway 2.0: A parallel multilevel hypergraph partitioning tool[END_REF], and Zoltan [START_REF] Boman | The zoltan and isorropia parallel toolkits for combinatorial scientic computing: Partitioning, ordering and coloring[END_REF]. In this thesis, we only used one tool, which is hMeTis. The exploration of other tools is necessary to evaluate the impact of the partitioning on the obtained results.

II.3. Dynamic Construction of Hypergraphs

In our study, we assume that the workload is known in advance. The construction of our hypergraph is based on this static workload. In many applications of graph algorithms, including communication networks, VLSI design, graphics, and assembly planning, graphs are subject to discrete changes, such as insertions or deletions of vertices or edges. In the last two decades there has been a growing interest in such dynamically changing graphs, and a whole body of algorithmic techniques and data structures has been discovered [START_REF] Demetrescu | Trade-os for dynamic graph problems[END_REF]. Two types of problems concern dynamic graphs : partially dynamic graphs subject only to either insertions, or dele-II. FUTURE WORK tions, but not both at the same time. Fully dynamic Graphs subject to intermixed sequences of insertions and deletions.

These ndings have to be integrated in our proposal, by proposing an algebra to construct incremently our hypergraph. The dynamic aspect of graphs complicates the partitioning algorithms. The usage of library managing dynamic graphs such as graph stream is recommended (http://graphstream-project.org/).

II.4. Advanced Algorithms to Explore our Hypergraphs

In our thesis, we use simple algorithms (greedy) to explore our hypergraphs to select dierent pivot nodes. Hence, it would be benecial to investigate the eciency of advanced algorithms such as evolutionary ones.

II.5. Hypergraph for Mixed Workload

Today's enterprise systems are partitioned into the so-called Online Transaction Processing (OLTP) and Online Analytical Processing (OLAP). In this thesis, we have mentioned the work performed by Curino et al. [START_REF] Curino | Schism: a workload-driven approach to database replication and partitioning[END_REF] about database replication and partitioning considering OLTP transactions that use hypergraphs. In this thesis, we particularity focused on OLAP workload.

Merging these two hypergraphs structures is a nice opportunity to consider the problem of mixed workload management. To do so, the development of metrics to measure performance of the mixed workload have to be elaborated in our context.

II.6. Consideration of others problems in the Deployment Phase

Use hypergraph structures to include other complex phases in designing parallel data warehouse, as data replication and load balancing. Also, including other dimensions in designing parallel data warehouses, as optimization structures (materialized views and indexes), in which we will use hypergraph structures to propose a new model of selecting OS in this new context.

II.7. Other Usages of our Findings

In our proposal, we concentrate our eorts on selecting materialized views and data partitioning.

Note that there is a large panoply of optimization structures, where their selection is driven by workloads such as indexes, vertical partitioning, etc. Our nding has to be extended to integrate any optimization structure. To do so, we have to make our tool more generic to allow developers to enrich it by other structures.

Another usage of our nding may concern the query recommendation and relaxation. A recommended or relaxed query is a super or sub query that already exists in the system.

Part IV Appendices

Cost models III. Introduction

In the relational model, each query is processed using a tree-like physical plan, where each node represents an algebraic operator (selection, join, projection) and each operator is tagged by an implementation algorithm. Estimating query processing cost implies the estimation of the execution cost of each operator, which needs also to calculate their cardinalities to estimate the above operators.

The real cost of query processing is done by a time unit (e.g., second) that corresponds to consuming time from the starting query processing until the result is given by the DBMS.

This cost depends on two main parameters: (1) The inputs/outputs cost (C I/O ) that gives the time of loaded data from storage devices (in our case: Hard disk ) to the main memory. (2) The CPU cost (C CPU ) that depends on the physical layout, input/output and the number of arithmetic and logical operations. Fig. 7.1, gives an overview and the parameters implied in the processes of estimating query processing cost.

Parallel to using cost models to estimate query processing and to select the optimal plan, other cost models are widely used in database physical design. They usually used in selecting the optimal OS as MV, indexes, data partitioning, etc. In addition, each OS has related cost functions that estimate their impacts in query execution time and physical parameter like disk space.

In this Chapter, we develop the cost models and their parameters used in our work.

IV. Cardinality estimation

The cardinality of a relation or an intermediate result is the number of its tuples. The cardinality considered as the main input of any estimation functions of query processing cost or selecting OS. Accordingly, the quality of any cost model depends on the quality of cardinality estimation functions. Many works have shown that error estimation of cardinality implies choosing bad plan that can be thousands times slower. [START_REF] Tzoumas | Eciently adapting graphical models for selectivity estimation[END_REF][START_REF] Moerkotte | Preventing bad plans by bounding the impact of cardinality estimation errors[END_REF].

To estimate the cardinality of intermediate results, it is necessary to have statistics about data distribution in base relations. So, to estimate cardinality or intermediate results, any query optimizer uses tools to get and update the statistics of data distribution in databases and then it applies functions on this statistic according query parameters.

IV.1. Statistics computation

The quality of a query optimizer is tightly tied to the quality of cost estimation functions, which are, in turn, based on the cardinality estimation. Accordingly, bad statistics can easily alter the execution plan, and the availability of good statistics can readily improve the quality of the best processing plan [START_REF] Chaudhuri | An overview of data warehousing and olap technology[END_REF]. Statistics are periodically re-computed by the DBMS, or right after updating base relations. Today, most of existing DBMS have implemented statistics catalogs [START_REF] Cannon | Ecient implementation of the fuzzy c-means clustering algorithms[END_REF][START_REF] Bruno | Exploiting statistics on query expressions for optimization[END_REF]. Although the fact that they do not undergo a radical change in a short period, their computation may be very costly [START_REF] Chaudhuri | Autoadmin 'what-if ' index analysis utility[END_REF][START_REF] Bruno | Ecient creation of statistics over query expressions[END_REF]. These statistics can be categorized into three categories: distribution of attribute values, like number of tuples, average size of column/tuple, distinct and maximum/minimum values of attributes. To reduce the complexity of statistics computation issue, many DBMS assumes that there is a uniform distribution of values [START_REF] Rao | Automating physical database design in a parallel database[END_REF][START_REF] Foster | The anatomy of the grid: Enabling scalable virtual organizations[END_REF]

IV.2.1. Cardinality of selection

The selection applied to one relation using one or more predicates. Let p, a selection predicate applied to a relation R. We denote σ p (R) as the result of this selection. To do so, we need an extra parameter called the selectivity factor of the predicate p, which is dened as the part of rows satisfying the predicate, and its value is between 0 and 1. In other words, it is the probability to pick each tuple from relations to be used as arguments of operators. Let f p be the selectivity factor of the predicate p. f p is dened as :

f p = |σ(R)| |R| (7.1)
Therefore, the cardinality of the selection result can be dened as:

|σ p (R)| = f p * |R| (7.2) Predicate p Selectivity f p ¬(p) 1-f p p 1 ∧ p 2 f p 1 *f p 2 p 1 ∨ p 2 f p 1 + f p 2 -f p 1 * f p 2 A =val 1 /|A| A =B 1 /max(|A|, |B|) A >val (maxA -val) /(maxA -minA) A <val (val -minA) /(maxA -minA) val 1 A val 2 (val 2 -val 1 ) /(maxA -minA) Table 7.

Selectivity estimation of complex predicates

To estimate the cardinality, we suppose that we have uniform values in columns. One predicate p can involve more than one attribute or value. So, the predicate p can be simple when it has one value or complex when it involves boolean operators linking several simple predicates (like p 1 and p 2 ). The selectivity of complex predicates can be easily computed based on their simple predicates. In the Table 7.2, we summarize the selectivity estimation formulas, where A and B denote attributes, val, val 1 and val 2 denote constants, max A is the maximum value in the column A, |A| is the number of distinct values in the attribute A. Note that, the optimizer can use logical equivalents to detect if the condition equivalent to FALSE, and in this case the cardinality is clear that equivalent to 0.

IV.2.2. Cardinality of projection

The cardinality of the result of a projection on the relation R i is, in principle, the cardinality of R i itself:

|Π A (R)| = |R| (7.3)
such that A, is an attribute or a set of attributes.

Sometimes, the query optimizer eliminates duplicate tuples to improve query plan, because when these latter are used by other operators like join, the result is the same. In this case, the cardinality is equal to:

|Π A (R)| = |A| (7.4)

IV.2.3. Cardinality of Cross product

The cardinality of the result of a cross product of two relations is the multiplication of their cardinalities.

|R 1 × R 2 | = |R 1 |×|R 2 | (7.
|R 1 R 2 | = max(|R 1 |, |R 2 |)/max(|b R1 |, |b R2 |) (7.6)
The same goes for multiple join attributes. We suppose that B are a set of the attributes involved in the join, the cardinality becomes:

|R 1 R 2 | = max(|R 1 |, |R 2 |)/max(|bi R1 |, |bi R2 |), ∀b i ∈ B (7.7)
If we assume that J R 1 R 2 is the probability that two rows verify join conditions, the cardinality of the result of that join can be calculated as follows:

|R 1 R 2 | = max(|R 1 |, |R 2 |)×J R 1 R 2 (7.8)

IV.2.5. Cardinality of aggregation

The number of tuples generated from an aggregation corresponds to the number of the resulting groups. This latter can be between 1 and |R|, so the cardinality of the result of the aggregation equals to:

|Γ (R)| = |R| /2 (7.9)

IV.2.6. Cardinality of Union

The maximum of tuples number generated from the union of two relations R 1 and R

2 (R 1 ∪ R 2 ),
is the sum of their cardinalities |R 1 | and |R 1 |, and the minimum is the maximum between |R 1 | and |R 2 |. So, the cardinality of the union can be the average of maximum and minimum values.

|R 1 ∪ R 2 | = max(|R 1 |, |R 2 |) + min(|R1|, |R2 |) /2 (7.10)

IV.2.7. Cardinality of intersection

The cardinality of the result of the intersection of two relations R 1 and R 2 (R 1 ∩ R 2 ), is in the range of 0 to the minimum cardinality of the two relations. So, the cardinality can be considered as the average value:

|R 1 ∩ R 2 | = min(|R1|, |R2 |) /2 (7.11)

IV.2.8. Cardinality of dierence

The maximum of tuples generated from the dierence of two relations R 1 and R

2 (R 1 \ R 2 ), is the cardinality of R 1 (|R 1 |) and the minimum is |R 1 |-|R 2 |.
So, the cardinality of the dierence can be considered as the average:

|R 1 \ R 2 | = (|R1| -|R2 |) /2 (7.12)

V. Cost estimation

The execution cost of an operator is the sum of two measures: (1) Input/output (C I/O ) which is the time of loading/storing data from/to the disk, and (2) CPU cost (C CPU ) consumed by arithmetic and comparison functions processed by the CPU. Note that, in the context of distributed databases (interconnected sites), the network ow involves additionally a network cost (C net ). The C net of a query is the necessary time to transfer all data and sub-results between sites and nally to produce the result.

Recently, with green computing, another measure has been considered is query cost estimation, which is the power and energy consumption cost. In this case, the challenge is to reduce energy [START_REF] Tsirogiannis | Analyzing the energy eciency of a database server[END_REF] and CO 2 pollution.

The query is executed following its physical plan that shows the data ow between its dierent operators. The total I/O and CPU costs of a query is the sum of the cost of each operator (op) occurring in the physical execution plan. For a given query the total costs are:

C I/O = op∈UQP C I/O (op) (7.13) C CPU = op∈UQP C CPU (op) (7.14)
The system can execute operators in parallel, which makes the summation of the I/O and CPU costs insignicant. For these reasons, researchers have proposed many techniques to calculate the total cost of the query, as described below.

Weighted sum of costs: The total cost C Q is equal to a weighted sum of the I/O and CPU costs [START_REF] Selinger | Access path selection in a relational database management system[END_REF]:

C Q =C I/O +w × C CPU (7.15)
where w is an adaptive variable between I/O and CPU costs. The weight w increases when CPU takes more time in executing operators and decreases when I/O takes more time to load/store processes.

Sum of the cost: due to the diculty of dening the relation between CPU and I/O cost by the weight value, some propositions ignore it [START_REF] Harris | Join algorithm costs revisited[END_REF]. Hence, the total cost becomes the sum of CPU and I/O costs:

C Q =C I/O +C CPU (7.16)
Maximum of the cost: In the previous approaches, the concurrency between CPU processing time and I/O loading time is totally ignored. The time execution becomes the maximum between CPU and I/O costs [START_REF] Cheng | An ecient hybrid join algorithm: A db2 prototype[END_REF].

C Q = Max(C I/O +C CPU ) (7.17) V.1

. Cost model parameters

As shown in Fig. 7.1, estimation function depends on many parameters like buer size, storage devices, system architectures, etc. [START_REF] Sevcik | Data base system performance prediction using an analytical model[END_REF]. Next, we describe these parameters:

V.1.1. Storage devices

Query processing time is sensitive to the storage access parameters [START_REF] Reiss | A characterization of the sensitivity of query optimization to storage access cost parameters[END_REF]. The complexity of storage systems has been increasing, and so do the cost parameters. The execution of a query can involve various types of storage devices like hard disks, ash disks, and main memory.

These storage devices can be classied into three categories according to their storage capacity, seek speed, and reading one-byte cost:

1. Cache: is founded using the same chip of the micro-processor, data can be accessed in a few nanoseconds.

2. Main Memory: data can be accessed between 10 to 100 nanoseconds range.

3. Secondary storage: covers all types of hard/optical disks, ash memory, etc. They access and read data in milliseconds, and most of them are made of magnetic disks, and have the following parameters: storage layout: like time of reading one page using direct access or sequential access; storage device: like number of cylinder, track, sectors, seek cost, etc.

V.1.2. Database Buer

A part or all intermediate results can be directly stored in the buer for future use by parent operators, what minimizes their input cost. Thus, the buer size and management algorithm become necessary to estimate the I/O cost of intermediate results [START_REF] Wolf | Optimal buer partitioning for the nested block join algorithm[END_REF].

V.1.3. Access paths data can be loaded from tables using sequential or random access. Each access mode has its specic cost.

V.1.4. Query parameters

Cost estimating functions take as input the query in the form of a physical plan that contains selection, join, projection, aggregation, and grouping operations. Each operator has a predicate like selection and join predicates. These latter are used to estimate the cardinality of intermediate results (For more details, see Section IV). In our work, we consider a workload of k queries, W ={Q 1 , .., Q k }, where each query Q i has a frequency of use f i . The nodes are interconnected using high-speed network and their processing are coordinated by one node called coordinator node. M p [i][j] has a value 1 if the fragment F i is allocated in the processing node N j , and a value 0 otherwise. The size of data stored in each processing node N j will be calculated using the following equation: Indexes: Index has three costs to dened, rstly the cost of updating index following updating in the indexed object. Cost of updating the structure of the index like bitmap index and the cost of processing queries that equal to the scan index generally in the main memory and the cost of accessing to data.

V.1.5. Database parameters

size(N j ) = M i=1 ||F i || × M p [i][j]
Data partitioning: the number of partitions, size of each partitions. To estimate the selection cardinality, the selectivity will be calculated for each partition.

V.2. Estimation functions for query processing

As has been previously mentioned, the cost of an operator or the whole query plan can be represented by two costs: CPU and I/O.

V.2.1. CPU cost

CPU cost is the number of CPU cycles necessary to compare dierent tuples. To estimate this number, it is necessary to know the cardinality of the input(s) and the output of each operator in the query execution plan. Once the input cardinality is estimated, it only remains to add

V.2.2. I/O cost

We assume that every operator is responsible for conveying its result to the next operator through main memory.

For our cost model, we consider some parameters, as depicted in Cost of a Selection: a selection on a relation R reduces the size of R: horizontally by a selectivity factor f R and vertically by a ltering factor φ R,q (only q attributes are retained). We dene φ q R as the ratio of the size of q columns from one tuple in the relation R, φ q R can be dened as:

φ q R = c∈q (L a (R c ))/L t (R) (7.27)
The output cost of a selection operation dened as:

P output = f R * ||R|| * φ q R (7.28)
For the input cost, all tuples of R are scanned, except if R comes sorted by restriction attributes, then only tuples satisfying the selection condition will be scanned. So, the input cost can be calculated as follows: Hypergraph partitioning is an important problem and has extensive applications in many domains like VLSI design [START_REF] Alpert | Recent directions in netlist partitioning: a survey[END_REF], transportation management, and data-mining [START_REF] Han | Clustering in a high-dimensional space using hypergraph models[END_REF], dening of molecular structures in chemistry search [START_REF] Konstantinova | Application of hypergraph theory in chemistry[END_REF], supervise of cellular mobile communication [START_REF] Klamt | Hypergraphs and cellular networks[END_REF], image segmentation [START_REF] Bretto | Hypergraph-based image representation[END_REF][START_REF] Ducournau | A reductive approach to hypergraph clustering: An application to image segmentation[END_REF], etc.

P input = ||R|| , if R is not sorted f R × ||R|| , if R is sorted (7.
C I/O = ||R|| + f R * ||R|| * φ q R , if R does not come sorted f R × ||R|| + f R * ||R|| * φ q R , if
P input = ||R 1 || + ||R 2 || + ||H T || , if no pipeline max(||R 1 ||, ||R 2 ||) + ||H T || , if pipeline (7.38) P interm = 0 , if ||H T || ≤ (M -||R 1 ||) |R 1 |×||H T || , otherwise
Hypergraph partitioning is to partition the vertices of a hypergraph in k -roughly equal parts, such that the number of hyperedges connecting vertices in dierent parts is minimized.

In this chapter, we detail a hypergraph partitioning package, called hM eT iS [START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF][START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF] CType: is the type of vertex grouping schema to use during the coarsening phase. It is an integer parameter and the possible values are:

1: means that hM eT iS selects the hybrid rst-choice schema. This schema is a combination of the rst-choice and greedy rst-choice schema.

2: means that hM eT iS selects the rst-choice schema. In this schema, vertices are grouped together if they are present in multiple hyperedges. Groups of vertices of arbitrary size are allowed to be collapsed together.

3: means that hM eT iS selects the greedy rst-choice schema. In this schema, vertices are grouped based on the rst choice schema, but the grouping is biased in favor of faster reduction in the number of the hyperedges that remain in the coarse hypergraphs.

4: means that hM eT iS selects the hyperedge schema. In this schemz vertices are grouped together that correspond to entire hyperedges. 5: means that hM eT iS selects the edge schema. In this schema, pairs of vertices are grouped together if they are connected by multiple hyperedges.

You may have to experiment with this parameter to see which schema works better for the classes of hypergraphs that you are using. In our experiments we have used the value 1.

RType: This is the type of renement policy to use during the uncoarsening phase. It is an integer parameter and the possible values are:

1: means that hM eT iS selects the Fiduccia-Mattheyses (F M ) renement schema used by hM eT iS tool.

2: means that hM eT iS selects the one-way F M renement schema, where, during each iteration of the F M algorithm, vertices are allowed to move only in a single direction.

3: means that hM eT iS selects the early-exit F M renement schema. In this case, the FM iteration is aborted if the quality of the solution does not improve after a relatively small number of vertex moves.

In our case, we have used the value 1 that correspondent to using Fiduccia-Mattheyses that is recommended by the developer of hM eT iS [START_REF] Karypis | A parallel algorithm for multilevel graph partitioning and sparse matrix ordering[END_REF].

Vcycle: This parameter selects the type of V-cycle renement to be used by the algorithm. It is an integer parameter and the possible values are: 169 CHAPTER 7. HMETIS: A HYPERGRAPH PARTITIONING PACKAGE 0: means that hM eT iS does not perform any form of V -cycle renement. means that hM eT iS performs V -cycle renement on the nal solution of each bisection step.

2: means that hM eT iS performs V -cycle renement on each intermediate solution whose quality is equally good or better than the best found so far.

3: means that hM eT iS performs V -cycle renement on each intermediate solution.

That is, each one of the Nruns bisections is also rened using V-cycles.

In our experiments , we have used the third choice that best time/quality tradeos.

Reconst This parameter is used to select the schema to be used in dealing with hyperedges that are being cut during the recursive bisection. It is an integer parameter and the possible values are: 0: means that hM eT iS removes any hyperedges that were cut while constructing the two smaller hypergraphs in the recursive bisection step.

1: means that hM eT iS reconstructs the hyperedges that are being cut, so that each of the two partitions retain the portion of the hyperedge that corresponds to its set of vertices.

Reconst with the value 0, gives a good quality of k-way partitioning.

dbglvl This is used to request hM eT iS to print debugging information. The value of dbglvl is computed as the sum of codes associated with each option of hM eT iS. The various options and their values are as follows: 0: show no additional information. 1: show information about the coarsening phase. For example, if we want to see all information about the multiple runs the value of dbglvl should be 8 + 16 = 24.

Relational Algebra

As the traditional relational queries, ROLAP queries are based on relational algebra which is one of the two formal query languages associated with the relational model [START_REF] Ramakrishnan | Database Management Systems[END_REF]. Queries in this algebra can be viewed as a composition of a collection of operators (called a query expression).

These operators are classied into two main categories: unary operations (e.g., selection(σ), projection ( )) need only one relation/intermediate result;

binary operations (e.g., join ( ), union, intersection, etc.) need two relations/intermediate results.

A query expression can be represented by a tree, whose leaves and internal nodes represent respectively: base tables and relational algebra operators applied to node's children. The tree is executed from leaves to root. For a given tree, there exists numerous equivalent query trees (due the properties (laws) of the relational algebra). This makes its optimization undecidable.

Commutative and associative laws: the most of the operators (Join, Union, Intersection, Cross Product) are commutative and associative.

Selection laws: One of the most important action of a query optimizer (specially in selecting a good logical query plan) is to push down selections in a query in order to minimize the size of the manipulated relations. To perform this operations, some laws exist: splitting laws: when the selection involves multiple predicates connected by AND or OR, the condition will be broken into many sub-conditions as follows: intermédiaires des requêtes [START_REF] Sellis | Multiple-query optimization[END_REF]. Cette interaction de requêtes a largement contribué à l'optimisation des requêtes [START_REF] Goasdoué | View selection in semantic web databases[END_REF][START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF] et à la conception physique [START_REF] O'gorman | Multiple query optimization by cacheaware middleware using query teamwork[END_REF]7]). Mais ces eorts ont ignorés le volume de requêtes.

σ C 1 AND C 2 (R) =σ C 1 (σ C 2 (R)) (7.40) σ C 1 OR C 2 (R) =σ C 1 (σ C 2 (R))
X ∪ ∅ = X, X ∪ X = X, X ∩ ∅ = X, X ∩ X = X, X \ ∅ = X, ∅ \ X = ∅, X \ X = ∅, Basic laws X ∪ Y = Y ∪ X, X ∩ Y = Y ∩ X, X \ Y = Y \ X Commutativity X ∪ (Y ∪ Z) = (X ∪ Y ) ∪ Z, X ∩ (Y ∩ Z) = (X ∩ Y ) ∩ Z, X \ (Y \ Z) = (X \ Y ) \ Z
Le volume de données a un impact sérieux les performances des requêtes. Avoir des méthodes ecaces pour accélérer le traitement des données devient plus important et urgent que jamais, et par conséquent, ils reçoivent une attention particulière de chercheurs universitaires et industriels. Ceci est bien illustré par le grand nombre de propositions, vise à optimiser les requêtes au niveau logique [START_REF] Shapiro | Exploiting upper and lower bounds in top-down query optimization[END_REF][START_REF] Lee | Optimizing large join queries using a graph-based approach[END_REF][START_REF] Slivinskas | Bringing order to query optimization[END_REF][START_REF] Lerner | Aquery: Query language for ordered data, optimization techniques, and experiments[END_REF][START_REF] Reiss | A characterization of the sensitivity of query optimization to storage access cost parameters[END_REF][START_REF] Wang | Multi-query optimization in mapreduce framework[END_REF][START_REF] Dalvi | Pipelining in multi-query optimization[END_REF][START_REF] Seshadri | Optimizing multiple queries in distributed data stream systems[END_REF], au niveau physique [START_REF] Zhang | An evolutionary approach to materialized views selection in a data warehouse environment[END_REF][START_REF] Cong | Optimality, scalability and stability study of partitioning and placement algorithms[END_REF][START_REF] Baril | Selection of materialized views: A cost-based approach[END_REF][START_REF] Bellatreche | Bringing together partitioning, materialized views and indexes to optimize performance of relational data warehouses[END_REF][START_REF] Chaves | Towards materialized view selection for distributed databases[END_REF][START_REF] Curino | Schism: a workload-driven approach to database replication and partitioning[END_REF][START_REF] Kerkad | L'interaction au service de l'optimisation à grande èchelle des entrepôts de données relationnels[END_REF] et au niveau de déploiement [START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF].

En se basant sur cette discussion, nous prétendons que tout système de stockage de données doit faire face à trois dimensions communes : volume de données, le volume de requêtes (nous l'appelons big-queries) et les questions de partage de la requête. Face à cette situation, le partage de la requête traditionnelle doit être revu pour intégrer les requêtes nombreuses. Par conséquent, nous aimerions émettre un groupe de réexions sur le partage entre les requêtes de grande quantité. Ce groupe de réexion est discuté dans le contexte des entrepôts de données relationnels, généralement modélisées par un schéma en étoile ou ses variantes (ex. schémas de ocon de neige) qui fournissent une vue centrée de requête sur les données. Une autre caractéristique importante est que ce schéma augmente l'interaction entre les requêtes OLAP, car ils eectuent des jointures impliquant une (des) table(s) de fait centrale(s) et tables périphériques, Le chapitre 5 détaille notre approche de conception d'un entrepôt de données parallèle en tenant compte de l'interaction entre les requêtes, représentée par un plan unié de de requêtes.

Le chapitre 6 donne une description de l'outil Big-queries, dévelopé dans notre laboratoire pour valider les contribution.

Le chapitre 7 résume et conclut la thèse en discutant les résultats.

Résumé

L'apparition du phénomène Big-Data, a conduit à l'arrivée de nouvelles besoins croissants et urgents de partage de données qui a engendré un grand nombre de requêtes que les SGBD doivent gérer. Ce problème a été aggravé par d'autres besoins de recommandation et d'exploration des requêtes. Vu que le traitement de données est toujours possible grâce aux solutions liées à l'optimisation de requêtes, la conception physique et l'architecture de déploiement, où ces solutions sont des résultats de problèmes combinatoires basés sur les requêtes, il est indispensable de revoir les méthodes traditionnelles pour répondre aux nouvelles besoins de passage à l'échelle. Cette thèse s'intéresse à ce problème de nombreuses requêtes et propose une approche, implémentée par un Framework appelé Big-Quereis, qui passe à l'échelle et basée sur le hypergraph, une structure de données exible, qui a une grande puissance de modélisation et permet des formulations précises de nombreux problèmes de combinatoire informatique. Cette approche est le fruit de collaboration avec l'entreprise Mentor Graphics. Elle vise à capturer l'interaction de requêtes dans un plan unié de requêtes et utiliser des algorithmes de partitionnement pour assurer le passage à l'échelle et avoir des structures d'optimisation optimales (vues matérialisées et partitionnement de données). Ce plan unié est utilisé dans la phase de déploiement des entrepôts de données parallèles, par le partitionnement de données en fragments et l'allocation de ces fragments dans les n÷uds de calcule correspondants. Une étude expérimentale intensive a montré l'intérêt de notre approche en termes de passage à l'échelle des algorithmes et de réduction de temps de réponse de requêtes.

Mots-clefs : Conception physique, Entrepôt de données, Hypergraphe, Vues matérialisées, fragmentation de données.

Abstract

The emergence of the phenomenon Big-Data conducts to the introduction of new increased and urgent needs to share data between users and communities, which has engender a large number of queries that DBMS must handle. This problem has been compounded by other needs of recommendation and exploration of queries. Since data processing is still possible through solutions of query optimization, physical design and deployment architectures, in which these solutions are the results of combinatorial problems based on queries, it is essential to review traditional methods to respond to new needs of scalability. This thesis focuses on the problem of numerous queries and proposes a scalable approach implemented on framework called Big-queries and based on the hypergraph, a exible data structure, which has a larger modeling power and may allow accurate formulation of many problems of combinatorial scientic computing. This approach is the result of collaboration with the company Mentor Graphics. It aims to capture the queries interaction in an unied query plan and to use partitioning algorithms to ensure scalability and to optimal optimization structures (materialized views and data partitioning). Also, the unied plan is used in the deployment phase of parallel data warehouses, by allowing data partitioning in fragments and allocating these fragments in the correspond processing nodes. Intensive experimental study showed the interest of our approach in terms of scaling algorithms and minimization of query response time.

[ 141 ]

 141 Dhouha Jemal, Rim Faiz, Ahcène Boukorca, Ladjel Bellatreche: MapReduce-DBMS: An Integration Model for Big Data Management and Optimization. 26th International Conference on Database and Expert Systems Applications (DEXA), pp. 430-439, Valencia, Spain, September 1-4, 2015 II.1.5. The development of Advisor Big-queries

  Fig. 1.3 Repartition of thesis chapters

Figure 2 . 1 shows

 21 an example of a cube representing sales activities. It has three dimensions: Product, Time, and Customer.

Figure 2 . 2 . 1 .

 221 Figure 2.2.1. Data sources tier: represents the operational activities that are saved in operational databases, XML les, etc. Data sources can be internal (produced inside the companies) or external (from the Web).

Fig. 2 . 2

 22 Fig. 2.1 An example of multidimensional model representation

Fig. 2 . 4

 24 Fig. 2.4 Examples SSB schemes

Figure 2 .

 2 5 presents an UML model illustrating our proposal.

Fig. 2 . 5 UML

 25 Fig. 2.5 UML Model of our Big-Queries Optimization Problem

Figure 2 .

 2 8 illustrates this process. Two major problems related to materialized views are: (a) the view selection problem and (b) the view maintenance problem.

Fig. 2 . 8

 28 Fig. 2.8 The query rewriting process

Fig. 2 . 9

 29 Fig. 2.9 Views Selection Problem

CHAPTER

Fig. 2 .

 2 Fig. 2.17 Data warehouse system architectures

  Let w[v] and c[e] denote respectively the weight of vertex v and the cost of hyperedge e. Denition 9. Vertex degree: The degree of vertex v ∈ V, denoted by d(v), is dened as the number of distinct hyperedges in E that connect v. Denition 10. Hyperedge size: The hyperedge size (length) of the edge e ∈ E denoted by |e|, is dened as it cardinality.

Denition 13 .

 13 Cut hyperedge: A hyperedge e ∈ E is cut if it connects more than one part (i.e., |P e | >1), and uncut otherwise (i.e., |P e | =1).As shown in Figure3.1, the bi-partitioning, has produced two cut of hyperedges (e 1 and e 3 ), which each one is split into two hyperedges. The rst on e 1 and e 1 , and the second on e 3 and e 3 . Denition 14. Cutset: A cutset of a partition Π denoted by C(Π), is the set of hyperedges that are cut by Π. So, a hyperedge in the C(Π) has vertices in at least two distinct parts. The cardinality of the cutset is called the partition cutsize.

  (3.4) where C(Π) and c[e] represent respectively the cut set and the cost of the hyperedge e.

  the successive coarser hypergraphs should have signicantly fewer large hyperedges than the original hypergraph. the sum of the hyperedge weights in the successive coarser hypergraphs should decrease as quickly as possible

Figure 3 .Fig. 3 . 3

 333 Fig. 3.3 An example of UQP of 30 queries

Figure 3 .

 3 Figure 3.4 shows an UQP designed as an electronic circuit by replacing its intermediate results by electronics ports (AN D, OR, XOR).

Fig. 3 . 4 Fig. 3 . 5 Fig. 3 . 6

 343536 Fig. 3.4 Electronic circuit corresponding to the UQP

  Since, we are assuming SPJ (Select-Project-Join) queries, three types of nodes are distinguished: (a) selection nodes are determined by the selection predicate. Each predicate has a selectivity factor; (b) join nodes are determined by a join predicate and two selection nodes and (c) projection nodes are determined by a predicate which correspond to a set of columns projected by the query.

Fig. 3 .

 3 Fig. 3.7 UQP generation approach

. 1 .

 1 Query workload representation IV.1.1. Parsing queryThe parser takes as input a SQL query and converts it into a parsed tree. This process is done by: a syntactic analysis to give the basic grammar elements of the text query in the form of a parse tree; a semantic checking of the parsed tree by verifying the used relations and attributes, query clauses, etc.; CHAPTER 3. MODELING QUERY INTERACTION USING HYPERGRAPHS a verication whether views are involved in the current query or not.

Fig. 3 . 8 Fig. 3 . 9

 3839 Fig. 3.8 Example of a text written query

Fig. 3 .

 3 Fig. 3.10 Virtual view substitution.

Figure 3 .Fig. 3 .

 33 Fig. 3.11 Logical plan generation steps

Fig. 3 .

 3 Fig. 3.12 Example of rst translating parse tree

V

  = {v i } set of vertices {n j } set of join nodes

Figure 3 .

 3 Figure 3.14 presents the join hypergraph partitioning of the hypergraph shown in the Figure 3.13, where three connected components corresponding to three new hypergraphs are obtained.

  pivot Algorithm 2 allows nding the vertex (node) which is the pivot in the hypergraph H. This pivot corresponds to the node which has the best possible benet of intermediate results reuse.

Fig. 3 .

 3 Fig. 3.16 Example of transformation Fig. 3.17 A resulting UQP

  shows the result of transformations t(S,C),t(S 1 ,B A ),t (S 2 ,B C , t(S 3 ,D C ) on the example of Figure 3.16. So, removing the pivot node from the hypergraph can generate a partitioning of the hypergraph into two disjoint hypergraphs H 1 and H 2 by Algorithm 3. H 1 includes all hyperedges that including the pivot and H 2 has the other hyperedges. Both hypergraphs are transformed the same way into oriented graphsG.

Fig. 3 .

 3 Fig. 3.18 An Example of hypergraph partitioning with node as a pivot

Figure 3 .

 3 Figure 3.18 shows an example of the result of hypergraph partitioning with the pivot n 28 . We note that the node n 18 belong the case 2, which needs to be duplicated into the node n 33 in the second hypergraph, when removing n 28 . the nodes n 29 , n 30 , n 31 , n 32 and n 33 , belong in the case 1. the nodes n 17 , n 16 , n 19 , and n 20 belong the case 3.

Figure 3 .Fig. 3 .Fig. 3 .

 333 Fig.3.19 Execution time to generate an UQP using Sellis's Algorithm[START_REF] Sellis | Multiple-query optimization[END_REF]

Fig. 3 .

 3 Fig. 3.21 Individual queries execution time

Fig. 4 . 1

 41 Fig. 4.1 Overlap between MQO and physical design problems

Algorithm 5 : 10 :

 510 Materialized views selection from component: selectMVC (Component C) 1: Input : C; {Component} 2: Output : L M V ; {List of materialized views} ; 3: L M V ← φ; {initialize materialized views set} 4: L ← getAllCandidateN odes (C ); {All nodes of C that have positive benet} 5: calculateBenef it (L[0],L); calculate the benet of each node of L 6: descendingOrder (L); {Descending order of the candidate nodes set} 7: while benef it (L[0]) and L <> φ do 8: add (L[0],L M V ); {Add the rst candidate node to the selected nodes set} 9: delete (L[0],L); calculateBenef it (L[0],L); re-calculate the benet of each node of L 11: descendingOrder (L); 12: end while Algorithm 6: Materialized views selection from UQP: selectFinalMV (UQP p) 1: Input : p; {UQP } 2: Output : M V f inal ; {List of materialized views} ; 3: M V f inal ← φ; {initialize materialized views set} 4: C ← getComponents (UQP); {All connected component} 5: for all c ∈ C do 6:

2 .

 2 Ordering queen nodes: Let N C k be the number of nodes of the component C k . Their ordering is based on their benet. The benet of the queen nodes are propagated to their 96 III. APPLICATION OF OS-ORIENTED UQP Algorithm 7: Materialized views selection from component: selectMVC (Component C,space S) 1: Input : C; {Component} 2: Input : S; {disk space} 3: Output : L M V ; {List of materialized views} ; 4: L M V ← φ; {initialize materialized views set} 5: L ← getAllCandidateN odes (C ); {All nodes of C that have positive benet} 6: calculateBenef it (L[0],L); calculate the benet of each node of L 7: descendingOrder (L); {Descending order of the candidate nodes set} 8: diskSpace ← 0; 9: while benef it (L[0]) and diskSpace ≤ S and L <> φ do 10: add (L[0],L M V ); {Add the rst candidate node to the selected nodes set} 11: diskSpace ← diskSpace + size(L[0]); 12: delete (L[0],L); 13: calculateBenef it (L[0],L); re-calculate the benet of each node of L 14: descendingOrder (L); 15: end while queries. As a consequence, each query may be assigned to a weight representing the sum of the benet of its nodes. These weight are then used to schedule the queries based on their overall benet (Figure 4.3-d). III.2.4. Manage Views materialization Till now, materialized views candidate are identied and the order of queries. Based on the different cost models, it can easily decide on materializing or de-materializing views by performing simulation using Algorithm 8. Algorithm 8: materializeView (mv ) 1: cost ← estimateM aintenance(mv);{Estimate the maintenance cost of the view } 2: changeStat(mv, true);{ change the stat of the view as materialized} 3: diskSpace ← diskSpace -sizeOf (mv); 4: return cost; III.3. UQP as input for selecting data partitioning schema III.3.1. Formalization of the problem The horizontal data partitioning is formulated as following: on the UQP. Note that, all selection predicate discarding selection with high or low selectivity factors.HDP schema is represented by xed coding, which is juxtaposition of arrays representing attributes sub-domain. incremental encoding generation using successive vertical and horizontal split of the initial array representations, which represent the selection predicate.

Two

  UQP generation modules, one for each optimization structure (materialized views and horizontal data partitioning). Each module contains several functions : (1) a parsing SQL-queries function to get all selection, join, projection and aggregation nodes,(2) hypergraph generation function to represent the queries by an hypergraph of nodes,(3) hypergraph partitioning function that uses hM eT iS tools to partition the hypergraph into several connected sections, (4) a transformation function, to transform each hypergraph into an UQP using the appropriate benet function according to the targeted OS, (5) a merging function that assembles all selection, join, projection and aggregation nodes to generate the nal UQP, (6) a display function that uses Cytoscape 1 plug-in to display the global processing plan. a MV selection module, that takes an UQP as input and produces candidate views to be materialized.

Fig. 4 . 4

 44 Fig. 4.4 Total cost of workload using MV selected using MV-oriented UQP and HDPoriented UQP

Figures 4 .

 4 Fig. 4.5 Total cost of workload using HDP selected using MV-oriented UQP and HDPoriented UQP

Fig. 4 . 6

 46 Fig. 4.6 Dierent costs using MV in Oracle for 500 queries

and 4. 11 .

 11 Theoretical results are conrmed by Oracle experiments.

Fig. 4 . 8 Fig. 4 .Fig. 4 .

 4844 Fig. 4.8 Execution costs using HDP in Oracle for 500 queries

Fig. 4 .

 4 Fig. 4.13 Optimization rate of query processing cost using MV

  Fig. 4.14 Oracle validation of MV selection without constraint

Fig. 4 . 2 . 105 CHAPTER 4 . 3 .

 4210543 Fig. 4.15 Advantage of dynamic materialization with query scheduling

Fig. 4 .

 4 Fig. 4.16 Performance of dynamic materialization approach

Fig. 5 . 1

 51 Fig. 5.1 Iterative and Variants of Conjoint Design Methodologies.

113 CHAPTER 5 .

 1135 QUERY INTERACTION SERVING THE DEPLOYMENT PHASE -data partitioning schema;

Figure 5 .

 5 Figure 5.2-a. Three types of nodes of this plan are distinguished: a selection operation, denoted by S i (with the form Attribute θ value, where Attribute ∈ T able, θ ∈ {=, <, >

  2-c.A database cluster with four nodes N = {N 1 , .., N 4 }.

F 5 Fig. 5 .

 55 Fig. 5.2 UQP Representation example

(Fig. 5 . 3

 53 Fig. 5.3 Flowchart for P RDW design methodology

  13:if |F C| > 0 then 14:att ← getSmallAttribut(F C, f rag);{get the small candidate attribut}[START_REF] Barnard | Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems[END_REF]

Fig. 5 . 4

 54 Fig. 5.4 Computational Overhead Performance of BQ-Design against F &A Design

Fig. 5 . 5

 55 Fig. 5.5 Performance of BQ-Design against F &A Design Approach

  Figure 5.5, shows that this factor

Fig. 5

 5 Fig. 5.7 Queries Makspen

Figure 5 . 8 ,

 58 Fig. 5.9 Scale-up of BQ-Design when workload size increase

Figure 5 .

 5 Fig. 5.10 Scale-up of BQ-Design when database size increase

Figure 5 . 9 ,

 59 shows that BQ-Design can scale-up where workload size increase.

  The query interaction presented by an unied query plan (UQP), that is generated thanks to hypergraph partitioning techniques. Big-Queries has two main objectives: the rst objective consists in recommending materialized views and horizontal data partitioning congurations for a given workload.(2) The second objective consists in taking prot from our experience in centralized database in terms of query volume and sharing experience and deploying it in the context of parallel DW design.

Fig. 6 . 1

 61 Fig. 6.1 Functionalities of Big-Queries Tool

130 IIFig. 6 .

 1306 Fig. 6.2 Big-Queries system architecture

Fig. 6 . 3

 63 Fig. 6.3 Example of an UQP of an component of workload

Figure 6 .Fig. 6 . 4

 664 Fig. 6.4 Example of the result of query parser

Figure 6 .IFig. 6 . 5

 665 Fig. 6.5 Example of presenting logical plan of a query

and 6 .Fig. 6 . 6

 666 Fig. 6.6 Example of presenting an hypergraph of workload

Fig. 6 . 7

 67 Fig. 6.7 Example of presenting components of workload

Fig. 6 . 8

 68 Fig. 6.8 Overview of cost estimation process

Figure 6 . 8 ,

 68 Figure 6.8, gives an overview and the parameters implied in the processes of estimating query processing cost.

Fig. 7 . 1

 71 Fig. 7.1 Overview of cost estimation process

5 )IV. 2 . 4 . 1 R 2 |

 52412 Cardinality of Join In our work, we have considered only the natural join. The natural join between two relations involves only the equality of two attributes. So we study the join R 1 (A, b) R 2 (b, C), where b is the attribute of the join predicate, and A, C denote a set of attributes. The cardinality of the join result |R depends on the values of the attribute b. For example: If R 1 and R 2 have disjoint sets of b -values, |R 1 R 2 | =0; If b is the key of R 2 and the foreign key of R 1 , so each tuple of R 1 joins exactly one tuple in R 2 , and |R 1 R 2 | =|R 1 |. In the general case, we suppose that b R1 and b R2 are the b attribute of R 1 and R 2 respectively, and r 1 is a tuple of R 1 , and r 2 of R 2 . if |b R1 | > |b R2 |, then b-value of r 2 is one value that appears in the b-value of R 1 . Hence, the probability that r 1 and r 2 share the same b-value is 1/|b R1 |. Similarly, if |b R1 | < |b R2 | , then the probability that r 1 and r 2 share the same b-value is 1/|b R2 |. In join operation, the possible comparison of pairs r 1 and r 2 is |R 1 | *|R 2 |, So the cardinality of the result of a natural join is:

Fig. 7 . 2 ,

 72 illustrates an example of a SN -DBC. The communication between nodes produces an extra cost called communication cost (C net ). It can expressed using an M × M matrix CC, where either columns or lines represent the processing nodes (N i 1 ≤ i ≤ M ) and the value CC[i][j] represents the number of pages transferred from the processing node N i to the processing node N j in a period of time. Thus, the total Parameters name Description DBC cluster of M processing nodes N ={N 1 , .., N M } M number of processing nodes S i storage capacity of the processing node N i N F number of fragments W threshold of data partitioning |F i | cardinality of the fragment F i ||F i || size of the fragment F i in pages M u matrix of use of fragments

  OS parametersMV: update frequency and if they are automatically rewritten or not.

  for one page t net network transfer time for one page ||R|| size on pages of the relation R |R| cardinality of the relation R (number of tuples) L t (R) tuple length for the relation R L a (C R ) the average length of the column C of the relation R |R C | number of distinct value of the column C of the relation R f R selectivity factor for selection f on the relation R π R selectivity factor for projection π on the relation R J R 1 R 2selectivity factor for join J on the relations R 1 and R 2

29 )

 29 Selection operator do not produce any intermediate result (P interm =0). Hence, the I/O cost dened as:

  Benchmark Query Templates VI. Introduction In our work, we have used a SSB-Query generator, that randomly generates a workload based on list of template. The generator tool randomizes the values of selection and the number of tables by using the following templates: VII. List of query template Q:1.1 select sum ( l o _ e x t e n d e d p r i c e * l o _ d i s c o u n t ) a s r e v e n u e from l i n e o r d e r , d a t e s where l o _ o r d e r d a t e = d _ d a t e k e y and d _ y e a r = [ Y ] and l o _ d i s c o u n t b e t w e e n [ DL ] and [ DH ] | [ DL]= and [ DH ] and [ DH] > [DL ] and l o _ q u a n t i t y [COMP] 2 5 ; Q:1.2 select sum ( l o _ e x t e n d e d p r i c e * l o _ d i s c o u n t ) a s r e v e n u e from l i n e o r d e r , d a t e s where l o _ o r d e r d a t e = d _ d a t e k e y and d_yearmonthnum = [YMN] and l o _ d i s c o u n t b e t w e e n [ DL ] and [ DH ] and l o _ q u a n t i t y b e t w e e n [ QL ] and [QH ] ; Q:1.3 select sum ( l o _ e x t e n d e d p r i c e * l o _ d i s c o u n t ) a s r e v e n u e from l i n e o r d e r , d a t e s where hMetiS: A hypergraph partitioning Package VIII. Introduction A hypergraph is a generalization of a graph, where the set of edges is replaced by a set of hyperedges. A hyperedge extends the notion of an edge by allowing more than two vertices to be connected by a hyperedge.

2 :

 2 show information about the initial partitioning phase. 4: show information about the renement phase. 8: show information about the multiple runs. 16: show additional information about the multiple runs.

Fig. 7 . 4

 74 Fig. 7.4 Overview of dierent operator in relational model

AssociativityX

  ∪ (Y ∩ Z) = (X ∩ Y ) ∪ (X ∩ Z), X ∩ (Y ∪ Z) = (X ∪ Y ) ∩ (X ∪ Z), (X ∪ Y ) \ Z) = (X \ Z) ∪ (Y \ Z), DistributivityTable 7.5 Overviews of laws for Set operations ordering laws: the order of sequence of selections is not important (commutative properties). σ c 1 (σ c 2 (R)) =σ c 2 (σ c 1 (R))pushing laws: there are three types of pushing selection through binary operations, depending on which arguments the selection is pushed.the selection must be pushed to the both of arguments (like in the union operation); the selection must be pushed to one of argument and the second argument is optional (like in the intersection and dierence operations) the selection must be pushed only to one argument (like join cross product operations). Example 5. Let us Consider two relations R (a,b) and S (b,c) and the expression σ a=2 AND b<val (R S). The condition (a=2) applies only to R and the condition (b<val) applies only to S. Pushing process needs three steps: Résumé Contexte Aujourd'hui, une grande quantité de données sont générées en continu dans de nombreux de domaines tels que la science de la vie, l'exploitation des ressources naturelles, la prévention des catastrophes naturelles, l'optimisation des ux de circulation, les réseaux sociaux, la concurrence commerciale, etc. Ces données doivent être collectées, stockées et analysées an d'être bien exploité par les gestionnaires des entreprises et les chercheurs pour eectuer leurs tâches quotidiennes. Une autre réalité, est que ces données souvent nécessitent d'être partagées avec d'autres utilisateurs et communautés. Où le partage de données commence à devenir un besoin vital pour la réussite de plusieurs entreprises. Par exemple, l'Autorité de la concurrence et des marchés (CMA) a ordonner les grandes banques de Grande-Bretagne à adopter l'ouverture des principes bancaires pour augmenter le partage des données entre les organismes de services nanciers 2 . Le partage de données entre un nombre important d'utilisateurs impliquera l'apparition du phénomène d'un nombre volumineux de requêtes que les systèmes de stockage et les systèmes de gestion de base de données doivent faire face. Ce nombre est motivé par l'explosion de site web de E-commerce, média sociaux, etc. A titre d'exemple, Amazon, 100 million de requêtes peut arriver à ses bases de données. Le même constat est détecté sur le géant chinois d'E-commerce Alibaba. Ces requêtes sont complexes et répétitives et nécessitent des opérations lourdes comme les jointures et les agrégations. Aussi, la gestion de la recommandation et de l'exploration des contribue fortement à augmenter le nombre de requêtes d'un SGBD particulier [99]. Partant de ressources de calcul et les perspectives des systèmes de stockage, les systèmes de stockage des bases de données optent vers la décentralisation des produits pour être capable d'évoluer en termes de capacité, de puissance de traitement, et de débit de communication. Des eorts ont été déployés pour concevoir ces systèmes pour partager simultanément les res-2 http://www.experian.co.uk/blogs/latest-thinking/a-new-era-of-data-sharing-how-the-cma-is-shaking-up-retail-banking/ sources physiques et les données entre les applications [106]. Le Cloud Computing a largement contribué à augmenter les capacités de partage de ces systèmes grâce à leurs caractéristiques : l'élasticité, la souplesse, le stockage et le calcule à la demande. Par conséquent, les données et les requêtes sont devenues liées aux plateformes avancées de déploiement, comme le parallèle, clusters, etc. [36]. Concevoir une base de données dans une telle plateformes exige des phases sensibles telles que : (1) la fragmentation de données on plusieurs fragments ; (2) l'allocation de ces fragments dans leurs n÷uds de calcules correspondants, et (3) la stratégie d'exécution des requêtes, pour assurer l'équilibre de charge des requêtes. En outre, Les requêtes qui représentent l'un des entités les plus importants dans la technologie des bases de données, sont aussi concernés par le phénomène de partage de données. Le partage entre les requêtes connus sous le nom : Interaction de requêtes. Mr Timos Sellis a donné la naissance d'un nouveau problème appelée optimisation multi-requêtes, qui vise à optimiser l'exécution globale d'une charge de requêtes par l'augmentation de la réutilisation des résultats

  appelés dimensions.Pour faire face au volume de requêtes interagi, le développement des structures de données évolutif qui capturent le partage est largement recommandé dans la dénition des algorithmes intelligents. La théorie des graphes et ses structures de données à contribué largement à résoudre des problèmes complexes impliquant à grande espace de recherche, telles que (1) le fragmentation vertical et horizontale dans les bases de données relationnelles[START_REF] Navathe | Vertical partitioning for database design: a graphical algorithm[END_REF][START_REF] Navathe | A mixed fragmentation methodology for initial distributed database design[END_REF], (2) le fragmentation horizontale dans les bases de données orientés objets[START_REF] Bellatreche | Algorithms and support for horizontal class partitioning in object-oriented databases[END_REF] (3), et récemment, Curino et al.[START_REF] Curino | Schism: a workload-driven approach to database replication and partitioning[END_REF] ont proposé la généralisation du concept de graph par un hypergraphe pour partitionner et répliquer les instances d'une base de données dans le cas distribuée. Où les sommets et les hyperarêtes de l'hypergraphe graphe représentent respectivement les instances de la base de données et les transactions. Un tel graphe peut être très vaste, puisqu'il est associé au nombre de tuples d'une base de données. Cela a rendu son partitionnement nécessaire pour assurer le passage à l'échelle de ses algorithmes.Le partitionnement de Hypergraphe est bien étudié par le Design Automation électronique ( de eda) pour tester le circuit électronique, en outre, une grande panoplie de bibliothèques de partitionnement existent tels que hMETIS et Zoltan-PHG. Cela nous motive à explorer hypergraphes pour faire face le phénomène du grand volume de requêtes. En conséquence, nous avons approché à la société Graphics Mentors situé à Grenoble-France, un leader de l'automatisation de la conception électronique, pour obtenir leur expertise dans l'utilisation de hypergraphe et d'élaborer une analogie entre notre problème et leur conclusion. Cette collaboration a fructueuse, puisque, après plusieurs mois de collaboration, nous réussissons à trouver une analogie entre un circuit électronique et un plan uniée de requêtes, en le présentant comme un hypergraphe. Nous approprions aussi leurs outils. Une fois que ce paragraphe est généré, nous le considérons dans l'optimisation logique et physique et de la phase de déploiement du cycle de vie d'une conception de l'entrepôt de données. Cette riche expérience sera entièrement discutée dans cette thèse.Objectifs de la thèseLes principaux objectifs xés pour cette thèse sont : En raison du large éventail de sujets que nous avons étudiés dans cette thèse qui couvre : l'optimisations logiques de requêtes, l'optimisations physiques, l'entreposage de données, lasélection de structures d'optimisation ; l'optimisation multi-requête, la phase de déploiement, les hypergraphes, etc., il est nécessaire de présenter une étude de synthèse de tous ces aspects.Puisque nous traitons le phénomène de big-queries et leurs interactions, nous devons montrer l'importance d'une structure de données évolutive qui capte facilement cette interaction, et utilisable comme un support pour dénir des algorithmes intelligents avec moins de calculs et de haute qualité.Nous devons également tenir compte des études de cas pour déployer notre approche. Pour ce faire, nous considérons le problème de la sélection de deux optimisations structures qui sont les vues matérialisées et le fragmentation horizontal pour environnement centralisé et parallèle.Nous avons également développé un outil pour aider les concepteurs et les administrateurs de base de données pour perfectionner la conception physique en se basant sur l'interaction entre les requêtes.Solutions proposéesCette section présente les contributions de la thèse. Tout d'abord, nous discutons la conception typique de l'entrepôt de données pour fournir une compréhension générale des choix de conception et d'architectures de déploiement. Nous nous concentrerons sur l'optimisation logique et physique, parce qu'ils sont les tâches les plus importantes d'optimiseurs de requêtes. Un autre point concerne la phase de déploiement du cycle de vie de l'entrepôt de données.A partir de ces vues d'ensemble, nous discutons de l'origine de notre structure de données pour représenter l'interaction des requêtes émise à partir de notre collaboration avec la société Mentors Graphics. Nous aimerions partager cette expérience et les eorts fournis pour trouver une analogie entre notre problème et le circuit électronique.Parallèlement à la dénition de cette structure, de nombreux autres développements ont été menées pour comprendre les algorithmes et les outils utilisés par la communauté VLSI et de les adapter à notre contexte. Une fois, cette adaptation a été fait, nous considérons deux problèmes dirigé par la charge de requêtes : la sélection des vues matérialisées et la détermination du schéma de la fragmentation horizontal. De plus, nous examinons comment améliorer le cycle de vie de la phase de déploiement en intégrant notre constatation selon laquelle notre structure de données et ses algorithmes sont associés. Enn, nous étudions le passage à l'échelle de nos algorithmes et la qualité de leurs solutions, en les soulignant en termes de taille de base de données, la taille des requêtes, etc.Enquête sur l'optimisation logiques et physique : Nous procédons à une analyse en profondeur de la façon dont l'état de l'art des bases de données gère l'interaction entre les requêtes et comment elle est utilisée dans l'optimisation logique et physique, et la phase de déploiement du cycle de vie de l'entrepôt de données. En se basant sur cette enquête, nous donnons de nouvelles classications des études existantes et les techniques utilisées dans le cadre de l'optimisation des requêtes, et une clarication du processus de sélection des structures d'optimisation lors de la phase de conception physique, qui est considéré comme l'un de la phase majeure. Enn, nous proposons une méthodologie de référence pour traiter le processus de sélection de ces optimisations en présence de l'interaction de la requête.Hypergraphs comme structure de données : Faire l'analogie entre notre problème de génération d'un plan unié de requêtes et le problème de conception des circuits électroniques. Cette analogie nous permet d'emprunter des techniques et des outils de la communauté EDA et en les adaptant à la génération d'un plan unié de requêtes. Où le problème est modélésé en utilisant les hypergraphe qui fournissent support pour dénir des algorithmes qui passe à l'échelle. Cette évolutivité est généralement assurée par des techniques de partitionnement de graphes[START_REF] Papa | Hypergraph partitioning and clustering[END_REF]. Plusieurs outils de partitionnement des hypergraphes ont été proposés, comme : PaToH[START_REF] Catalyürek | Patoh: a multilevel hypergraph partitioning tool[END_REF] Le développement d'un outil d'aide "Big-queries" : Sur la base de nos conclusions, nous avons développé un outil d'aide, inspiré des outils bien connus développés par des éditeurs commerciaux et universitaires pour aider les concepteurs et les DBAs au cours de leurs activités de déploiement et durant les tâches d'administration, comme la sélection des structures d'optimisation. Cette interface permet au DBA de visualiser l'état de sa base de données qui concerne trois aspect : (1) les tables du DW en question, (2) la charge de requêtes utilisée, (3) les ressources requises pour la conception physique, (4) l'interaction de requêtes visualisée par un hypergraph, le schéma des diérent structures d'optimisation (MV et HDP), le schéma de déploiement et le coût relative. L'outil est doté d'une passerelle de connexion au diérent type de SGBD (oracle11g, Oracle12c et PostgresSQl). L'outil big queries est disponible dans le forge de notre laboratoire http://www.lias-lab. fr/forge/projects/bigqueries. Plan du Mémoire La première partie du manuscrit contient le chapitre qui fournit le contexte nécessaire pour comprendre nos contributions. Dans ce chapitre, nous commençons par un zoom sur la technologie d'entreposage de données sur lesquelles nos expériences de validation sont eectuées. Par la suite, nous détaillons les paramètres qui inuent sur le temps de réponse de traitement des requêtes : vues matérialisées, fragmentation de données et le problème d'optimisation multiple de requêtes, et nous donnons un aperçu de la conception de l'entrepôt de données parallèle. La deuxième partie du manuscrit est consacrée à la contribution. Elle commence par le chapitre 3, qui détail notre principale contribution qui consiste à utiliser la théorie des graphes pour surmonter la gestion des grands-requêtes. La contribution vise à la fusion de la MQO et les problèmes de conception physique pour générer des candidats cibles pour une technique d'optimisation spécique (MV, index, et fragmentation de données). Ceci est réalisé en injectant de la connaissance des structures d'optimisation dans la génération de UQP. Le chapitre 4 présente l'application de notre UQP orienté structure d'optimisation, où il est appliqué pour la sélection des vues matérialisées avec et sans contraintes, et est exploité dans la matérialisation dynamique avec ordonnancement des requêtes. En plus, est utilisé pour la fragmentation horizontale de données.

1 i 2 i 3 i 4 i 5 o 1 o 2 g 1 g 2 g 3 g 4 g 10 g 9 g 5 g 6 g 7 g 8 g 11 g 12 i 3 i 4 i 5 o 1 o 2 g 1 g 2 g 3 g 4 g 10 g 9 g 8 g 11 g 12 i 1 i 2 g 5 g 6 g 7

	Fig. 1.2 From Logical Circuit to a HyperGraph
	II.1.3. What-if Unied Query Plan Generation

Ahcène Boukorca, Ladjel Bellatreche, Sid-Ahmed Benali Senouci, Zoé Faget: SONIC: Scalable Multi-query OptimizatioN through Integrated Circuits. 24th International Conference on Database and Expert Systems Applications (DEXA), pp. 278-292, Prague, Czech Republic, August 26-29, 2013.

i

  Ahcène Boukorca, Ladjel Bellatreche, Alfredo Cuzzocrea: SLEMAS: An Approach for Selecting Materialized Views Under Query Scheduling Constraints. 20th International Conference on Management of Data (COMAD), pp. 66-73, Hyderabad, India, December 17-19, 2014.[212] Amine Roukh, Ladjel Bellatreche, Ahcène Boukorca, Selma Bouarar: Eco-DMW: Eco-Design Methodology for Data warehouses. Proceedings of the ACM Eighteenth In-ternational Workshop on Data Warehousing and OLAP (DOLAP), pp. 1-10, Melbourne, VIC, Australia, October 19-23 2015.

II.1.4. Query Interaction in the Deployment Phase

  Background & State of Art Contents I Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

II

The Data Warehousing Technology . . . . . . . . . . . . . . . . . . . . . . . 18 III Factors Impacting Query Processing and Optimization . . . . . . . . . . . . 27 IV Data structures and access algorithms . . . . . . . . . . . . . . . . . . . . . 51 V Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2 .

 2 Extract(S, A, R, CS): enables selection and extraction of data from source S satisfying constraint CS;

3. M erge(S, A

1 , A 2 , R 1 , R 2 ): merges record-sets R 1 and R 2 belonging to the same source S; 4. U nion(S 1 , S 2 , A 1 , A 2 , R 1 , R 2 ): unies record-sets R 1 and R 2 belonging to dierent sources S 1 and S 2 respectively; 5. F ilter(S, A, R, CS ): lters incoming record-sets R, allowing only records with values satisfying constraints CS ; 6. Join(S, A 1 , A 2 , R 1 , R 2 ): joins record-sets R 1 and R 2 having common attributes; 7. Convert(S, A, R, F S , F T ): converts incoming record-sets R from the format F S of source S to the format of the target data source F T ; 8. Aggregate(S, A, R, F ): aggregates incoming record-set R applying the aggregation function F (count, sum, avg, max) dened in the target source. 9. DD(R): detects and deletes duplicate values on the incoming record-sets R;

  III. FACTORS IMPACTING QUERY PROCESSING AND OPTIMIZATIONExample 2. Let Q 1 and Q 2 be two queries. Q 1 has joins between the base relations R 1 ,R 2 and R 3 with a selection on R 1 using the predicate p (att1=val) . Q 2 has joins between base relations R 1 ,R 3 and R 4 and the same selection as Q 1 . Their query trees are given in isolated way in

	Figures 2.7a and 2.7a. Figure 2.7c presents a merging of these two tree by exploiting a common
	node.

SQL Query Parse Rewrite Grammar Rules Rewriting rules Optimized Algebra Tree Plan Optimize Multi Plan Best Execution Plan Search Strategy Execute Query OutPut Execution Strategy Cost Models Database Data/Statistics Relational Algebra Tree DX NL MJ SQ HJ Fig. 2.6 Query optimizer steps

  ., Q n } to be optimized, each query Q i has a set of possible individual local plans P i ={p 1 , .., p k i }; MQO consists in nding a global execution plan obtained by merging individual plans such that the query processing cost of all queries is minimized.

	III. FACTORS IMPACTING QUERY PROCESSING AND OPTIMIZATION

  2.12 Example of

	Lattice Graph
	have been used to represent and/or to prune the search space. The most used data structures
	are:
	AND/OR view graph: is a directed acyclic graph (DAG), which can be seen as the
	union of all possible execution plans of each query. It is composed of two types of nodes:
	operation and equivalent nodes. Each operation node corresponds to an operation in the
	query plan (selection, join, projection, etc.). Each equivalence node corresponds to a set
	of equivalent logical expressions (i.e., that yield the same result). The operation node
	have only equivalent nodes as children and equivalent nodes have only operation nodes as
	children. Many algorithms have been proposed in the literature to exploit this structure
	[120, 180, 213, 14, 178, 93]. Figure 2.10 gives an example of AND/OR graph, for a query.
	Multi-View Processing Plan (MVPP): is a directed acyclic graph in which the
	root nodes represent the queries, the leaf nodes correspond to the relations (base tables),
	and the intermediate nodes represent dierent operations used by the queries such as:
	selection, join, projection, etc. MVPP has been introduced by Yang et al. [273, 273].
	Figure 2.11 gives an example of a MVPP.
	Data Cube Lattice: is a directed acyclic graph, proposed in the context of multidi-
	mensional data warehousing, which the nodes represent the queries or views (the views
	are characterized by grouping operation), and the edges dene the relationship between
	views in each nodes [125, 144, 275]. Figure 2.12 gives an example of Latice graph.

  2. BACKGROUND & STATE OF ARTConstruction of the global plan is performed following the bottom up scenario. Initially, the authors select the join local plans of each query (logical plans that have only join operations).

	These plans are merged in a single plan, called Multi-Views Processing Plan MVPP. The plan
	represented by an acyclic graph. This plan has four levels: at level 0, we nd the leave nodes
	representing the base tables of the DW. At level 1, we nd nodes which represent the results
	of unary algebraic operations such as selection and projection. At level 2, we nd nodes rep-
	resenting binary operations such as join, union, etc. The last level represents the results of
	each query. Each intermediate node of the graph is tagged with the cost of each operation
	and its maintenance cost. Two algorithms are proposed for selecting the best MVPP which
	has the minimum cost. The rst algorithm, called A feasible solution, generates all possible

table ,

 , Customer Europe =σ Region= EU ROP E (Customer) Customer Others =σ Region<> EU ROP E (Customer)

	CHAPTER 2. BACKGROUND & STATE OF ART
	of the above mentioned partition techniques and the partitioning key is based on a virtual
	column. Virtual columns are not stored on disk and only exist as meta-data.
	Two versions of horizontal partitioning are available [195]: primary and derived horizontal
	partitioning. Primary horizontal partitioning of a table is performed using predicates
	dened on that relation. It can be performed using the dierent fragmentation modes
	above cited. Derived horizontal partitioning is the partitioning of a table that results
	from predicates dened in other table(s). The derived partitioning of a table R according
	to a fragmentation schema of table S is feasible if and only if there is a join link between
	R and S.
	Example 4. Using star schema of DW shown in Figure 2.4, that contains a fact table
	Lineorder and four dimension tables Customer,Supplier,Product and Dates. If the table
	Customer is candidate for partitioning, it may be divided using the attribute Region as
	follows:
	The execution of the query that gives the European orders may be rewritten as follows:
	SELECT Count ( * ) FROM C u s t o m e r PARTITION ( CustomerEurope ) C , L i n e o r d e r L WHERE L . CID=C . CID ;
	The fragmentation of the Customer table can be propagated on the fact table Lineorder
	as follows:
	view, and index) is decomposed
	according to a range of values of a given set of columns. The hash mode decomposes the
	data according to a hash function (provided by the system) applied to the values of the
	partitioning columns. The list partitioning splits a table according to the listed values of
	a column. These methods can be combined to generate composite partitioning (List-List,
	Range-Range, Hash-Hash, Range-List, etc.). Another mode of horizontal partitioning is
	also available in Oracle11g, called virtual column based Partitioning. It is dened by one

Lineorder Europe =Lineorder Customer Europe Lineorder Others =Lineorder Customer Others

	Consequently, the search of number of European orders may be optimized as follows:
	SELECT Count ( * ) FROM L i n e o r d e r PARTITION(LineorderEurope ) ;

Table 2 .

 2 Indexing has been at the foundation of performance tuning for databases for many years. A database index is a data structure that improves the speed of operations in a table.Indexes can be created using one or more columns. An index can be either clustered or nonclustered. It can be dened on one table, fragment, views or many tables using a join index[START_REF] Neil | Multi-table joins through bitmapped join indices[END_REF]. The traditional indexing strategies used in database systems do not work well in data warehousing environments since most OLTP queries are point queries. B-trees, which are used in most common relational database systems, are geared towards such point queries. In the data warehouse context, indexing refers to two dierent things: (a) indexing techniques and (b) index selection problem.Indexing techniques. A number of indexing strategies have been suggested for data ware-

		1 A Comparison of main approaches
		Fragmentation & Allocation	Design	Environment	Control over
				the Number of Fragments
	[83]	Yes	Sequential	Grid	Yes
	[108]	Yes	Sequential	DB Cluster	No
	[171]	Yes	Sequential	DB Cluster	No
	[237]	Yes	Sequential	Disk-Shared	No
	[27]	Yes	Combined	Shared-Nothing	Yes

houses: Value-List Index, Projection Index, Bitmap Index, Bit-sliced Index, Data Index, Join Index, and Star Join Index. Bitmap index is probably the most important result obtained in the data warehouse physical optimization eld. The bitmap index is more suitable for low cardinality attributes, since its size strictly depends on the number of distinct values of the column on which it is built. Besides disk space saving (due to their binary representation and potential compression), such index speeds up queries having Boolean operations (such as AND, OR and NOT) and COUNT operations. Bitmap join index is proposed to speed up join operations. In its simplest form, it can be dened as a bitmap index on a table R based on a single column of another table S, where S commonly joins with R in a specic way.

  .g., for reading, the basic implementation of the algorithm is to read page by page.

	CHAPTER 2. BACKGROUND & STATE OF ART
	algorithms, e
	MB. Each DS needs basic operations like reading,
	adding, updating, deleting or nding a value of data, which they are implemented with many
	3 https://hadoop.apache.org/docs/r1.2.1/hdfs_design.html 4 https://technet.microsoft.com/en-us/library/cc781134%28v=ws.10%29.aspx
	51

  The rst hypergraph contains the hyperedges that use the pivot, and the second

	6:	end if
	7: end for
	8: for all v i ∈ H 2 .V do
	9:	if v i ∈ H 1 .V then
	10:	putN ewID (v i , H 2 ); {new ID for duplicate node }
	11:	end if
	12: end for
	Algorithm 3 allows partitioning a hypergraph into two disjoint hypergraphs using a node as
	a pivot.

Algorithm 3: partitionP ivot (Vertex pivot, Hypergraph H 1 , Hypergraph H 1 ) 1: for all e i ∈ H do 2: if pivot ∈ e i then 3: addT oGraph (e i , H 1 ); {add the hyperedge e i to H 1 } 4: else 5: addT oGraph (e i , H 2 ); {add the hyperedge e i to H 2 }

  .2, the number of components increases when the number of queries increases. Most components are small in terms of CHAPTER 3. MODELING QUERY INTERACTION USING HYPERGRAPHS number of queries which reduces considerably the complexity of optimizing the queries of each component. We can see also that the biggest component is still relatively small compared to the initial workload. For example, the biggest component of our 10 000 queries workload only has 357 queries.

	Nbr of queries Nbr of components Max of queries/Component
	100	20	15
	200	38	31
	400	72	62
	500	89	83
	800	120	123
	1000	140	154
	2000	204	178
	5000	488	234
	8000	703	278
	10000	945	357
	Table 3.2 Component according to workload
	VI.2.2. Quality of hypergraph partitioning
	Computing cost

A battery of tests has been conducted to evaluate the UQP generation module against Yang's and Sellis's modules. In each test, we change the number of input queries to monitor the behavior of each algorithm. The set of the results are given in Figure

3

.19. It should be noticed that Sellis's algorithm

  selectivity (selectP redicate) > threshold min and selectivity (selectP redicate)

	1: benef itemax ← 0;
	2: for all v i ∈ V do
	3:	selectPredicate ← getSelectionP redicat (v i ); { get the selection predicate of the
		dimension table of the node}
	4:
		<threshold max then
	5:	candidateP redicate ← selectP redicate; {ignore nodes with selectivity too
		high(threshold max ) or too low (threshold min ) ots selection predicates }
	6:	nbr ← nbrU se (v i ); {nbr: number of hyperedges that connect v i }
	7:	benef it ← getBenef it(v i , nbr) {the benet calculated using the equation 4}
	8:	if benef it > benef itemax then
	9:	benef itemax ← benef it;
	10:	pivot ← v i ;
	11:	end if
	12:	end if
	13: end for
	14: return pivot

if

  Before formalizing the MV Problem (M V P ) considering the Query Scheduling Problem (QSP , we think it would be wiser to propose a separate formalization of both M V P and QSP . The MV problem considering QSP takes (i) A DW and (ii) a set of queries Q, (iii) a set of DW with fact table F and d dimension tables {D 1 , .., D d },-a workload

	Inputs:
	-a
	intermediate nodes candidates for materialization; a constraint representing the limited storage
	size. The problem aims at providing: (i) a scheduled set of queries and (ii) MV, minimizing
	the overall processing cost of and satisfying the storage constraint.
	Query scheduling problem (QSP ) is formalized as follows:

; 8: end for III.2. UQP as input for dynamic materialization and query scheduling Traditional selection of views supposes consider a static workload. To relax this hypothesis, we propose a on demand dynamic materialized of views. If a view is no longer ecient, it will be removed from materialized view pool. To do so, we have to integrate query scheduling module in the process of this materialization.

III.2.1. Formalization of the problem

  1: Input : lp; { landmark predicate} 2: Input : CA lp ; {List of components each one contains a set of queries} 3: Input : f ragment; {The candidate fragment} 4: Input : m; {number of cluster nodes} 5: Output: P P S; {partial partition schema} 6: Output: noncandidate; {A fragment for the next partial partition } 7: (candidate, noncandidate) ← split(f ragment, lp);{Split the fragment using lp} 8: (F C, SC) ← preparAttribute(candidate, CA lp );{select candidate attributes} 9: nbrF rag ← 1;{number of fragment in P P S } 10: P P S ← candidate;{initiate the P P S} 11: while nbrF rag < m do

	12:

Table 6 .

 6 1 Presentation of well-known administration advisors

	Big-queries plays the role of simulator that uses mathematical cost models (developed in Ap-
	pendix 1) to quantify the quality of the dierent recommendations. This chapter gives an
	overview of Big-queries tool, its dierent components and examples of its usages.
	1 https://azure.microsoft.com/en-us/documentation/articles/sql-database-advisor/
	129

  .3. What if Unied Query Plan Generation The second contribution of our thesis concerns the incorporation of the what-if question in the physical design phase of advanced databases such as data warehouses. This incorporation is performed by merging two problems: the multi-query optimization and the physical structure selection, usually performed in a sequential way. As a consequence, we proposed to consider the question which is what-if physical design for multiple query plan generation. A formalization of our problem has been given and instantiated with two optimization structures: materialized views in static and dynamic contexts, and horizontal data partitioning. The hypergraph data structure used for generating the best multiple query plan facilitate the development of algorithms for selecting our optimization structures, where metrics related to each structures are injected into the process of multiple query plan generation. Mathematical cost models estimating the query processing cost are also developed. We conducted intensive experiments using theoretical and a real validation in Oracle 11g. The results approve our what-if issue and the theoretical results are conrmed by Oracle experiments that demonstrate the quality of our cost models.

	I. SUMMARY
	workloads of queries, and identied a high scalability of our generated unied query plan on
	selecting materialized views.

I

  . max value for an attribute A in the relation R min A min value for an attributeA in the relation R L a (A R i ) average length of a value of attribute A of relation R i (in bytes) L t (R i )average length of a tuple of relation R i in bytes

	Parameters name Description
	R i	a relation that may represents fact or dimension tables
	|R i |	number of tuples of the relation R i
	||R i ||	number of pages on which the relation R i is stored
	|A|	number of distinct values of the attribute A
	max A

Table 7 .

 7 1 Cardinality estimation parameters DBMS Hardware parameters that include network, hard disk characteristics (e.g. bandwidth and time of reading one page).Statistics of using access methods (index, MV, etc.), like spent-time to scan an index.

IV.2. Intermediate results cardinality

Cardinality estimation of the intermediate results depends on the type of the current operator in the physical query plan. Next, we present basic functions used to estimate the cardinality of intermediate results for every operator type (selection, projection, join, etc.). Note that the goal of cardinality estimation is not to give an exact information, but instead an estimation to select a good physical query plan or to select near-optimal OS. For a given relation or an intermediate result R i , we denote its cardinality by |R i |. We need some notations to present our functions, as depicted in Table

7

.1. Our cost functions based on the work of Selinger et al.

[START_REF] Selinger | Access path selection in a relational database management system[END_REF]

.

  The schema of databases is always considered as input for any cost model, used for estimating the cardinality of intermediate results and to identify OS characteristics. In our work, we have used a star schema of DW, that has one fact table F and d dimension tables D ={D 1 , .., D d }. Two important parameters are associated to each table F or D i (1≤ i ≤ d): cardinality denoted by |F | and |D i | respectively, and the real table size generally given in bytes (in our case we have used the pagesize unit, P S =8192 bytes), denoted by ||F ||. Other parameters are needed like tuple and columns average size (for more details, see Table 7.1). V.1.6. Deployment parameters DB or DW can be deployed according to dierent architectures (SMP,MPP and Shared nothing (More details, see Chapter 2). In our tests, we have used Shared Nothing Database Cluster, denoted by SN-DBC ; and centralized DB. The SN-DBC is composed of M processing nodes (servers) N ={N 1 , .., N m }, where each node N i has a storage capacity S i to store a part of data.

Table 7 .

 7 3 Data partitioning schema parameters lines and columns of the matrix are the N F fragment and M processing nodes respectively.

Table 7 .

 7 4 Cost function parameters the CPU cost of the comparison functions for each CPU cycle. The number of CPU cycles is easy to compute for most comparison types (like boolean and number). However, it gets more complicated when comparing string values. In our work, we have ignored this measure, because

C I/O is by far the most dominant cost in the context of very large DW.

Table 7

 7 P op , if the cost represented by number of I/O pages T op , if the cost represented by elapsed time(7.21) where P op is the number of pages read or written during the execution of the operator op, and T op is the elapsed time while running the operator op. P op and T op are dened as:P operator = P input + P interm + P output (7.22)T operator = T input + T interm + T output(7.23) where P input and T input are the number of pages and time consumed in reading the input relation(s) respectively. P output and T output are respectively, the number of pages and time consumed in forwarding output relation(s) to the next parent operator (task) or to disk, assuming that the nal output stream is written to disk for subsequent usage. P interm and T interm are the number of pages and time consumed in storing intermediate results on disk. For some operators, P interm and T interm are null. T operator can be directly estimated from P operator by using calibrating database parameters to dene the average time for loading pages using network or disk. Knowing that unary operators need one relation to be read unlike binary ones, which need two relations; the input cost of any operator is dened as:P input * t disk , if unary operators P input 1 * t disk + P input 2 * t disk ,if binary operators without using pipeline max(P input 1 * t disk , P input 2 * t disk ), if binary operators with using pipeline(7.24) The output and intermediate costs remain the same whether for unary or binary operators:T output = P output * t disk(7.25) T interm = P interm * t disk(7.26) Next, we give the I/O cost for each type of operator:

		
	T input =	
		

.4: The processing cost is concerned with measuring execution time, which is directly inuenced by the number of I/O pages. Thus, we represent the C I/O of any operator (op) either by loaded pages number or time seconds, as follows: C I/O (op) =

  Merge Join Algorithm The merge join algorithm is only used when both relations come sorted on the join attribute. Relations are retrieved in parallel. So, P interm is null, and P input is computed as follows:Hash Join Algorithm We assume that R 1 is the outer relation. So, the hash table is built for R 2 and ||R 2 || ≤ ||R 1 ||. The cost of creating the hash table HT is the cost of loading R 2 and writing it to the disk. Then HT and R 1 are joined following a nested loop join such that HT is the inner relation. If we suppose that J hash is the percentage of tuples of R 2 that depends on the join selectivity factor and on the hash function, then the cost of input P input and intermediate P interm will be dened

	P input = max(||R 1 ||, ||R 2 ||)	(7.36)
	as:
	||H T || = J hash ×||R 2 ||	(7.37)
	R comes sorted	(7.30)

  hM eT iS algorithms hM eT iS is a software package for partitioning large hypergraphs, especially those arising in circuit design. The algorithms in hM eT iS are based on multilevel hypergraph partitioning described in[START_REF] Karypis | Multilevel hypergraph partitioning: applications in vlsi domain[END_REF][START_REF] Karypis | A parallel algorithm for multilevel graph partitioning and sparse matrix ordering[END_REF][START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF]. Multilevel partitioning algorithms are illustrated in chapter the third chapter (section II), that reduce the size of the graph (or hypergraph) by collapsing vertices 1 hM eT iS is copyrighted by the regents of the University of Minnesota. This work was supported by IST/B-MDO and by Army High Performance Computing Research Center under the auspices of the Department of the Army Nruns: This is the number of the dierent bisections that are performed by hM eT iS. It is a number greater or equal to one, and instructs hM eT iS to compute Nruns dierent bisections, and select the best as the nal solution. A default value of 10 is used.

1

, used in our works.

IX. Overview of hM eT iS

IX.1.

  Keywords: Physical Design, Data Warehouse, Hypergraph, Materialized Views, Data Partitioning Secteur de recherche : Informatique et applications LABORATOIRE D'INFORMATIQUE ET D'AUTOMATIQUE POUR LES SYSTEMES Ecole Nationale Supérieure de Mécanique et d'Aérotechnique Téléport 2 1, avenue Clément Ader BP 40109 86961 Chasseneuil-Futuroscope Cedex Tél : 05.49.49.80.63 Fax : 05.49.49.80.64

In our work, we focus on only by join nodes that are the costly nodes and the other operations are pushed as far down the logical query tree as possible.

http://www.cytoscape.org

http://www.cytoscape.org

http://www.cytoscape.org

d_year ,s _ c i t y , p_brand ;

. Notre conclusion est ensuite exploitée pour résoudre le problème d'optimisation multi-requêtes et d'évaluer son ecacité et qualité contre les approches les plus populaires de l'art state-of.What-if pour la génération du plan unié de requêtes : L'interaction de requêtes représentées par un UQP est située à l'intersection de deux mondes : le mode de l'optimisation multiple de requêtes et le monde de conception physique. L'interaction de requête participe ecacement à résoudre les problèmes de conception physiques par la proposition d'un ensemble de candidats. Mais un UQP n'est pas nécessaire qu'il est bien pour les instances du conception physique[START_REF] Yang | Algorithms for materialized view design in data warehousing environment[END_REF][START_REF] Yang | A framework for designing materialized views in data warehousing environment[END_REF], d'où la nécessité de choisir un bon plan pour produire de bons candidats de structures d'optimisation. En outre, un bon UQP pour une structure d'optimisation, ne soit pas nécessaire bon pour une autre structure. En plus, la sélection du meilleur UQP exige l'énumération de tous les plans possibles, ce qui est impossible en raison du grand nombre de plans possibles, ce qui peut être innie dans le cas de Big-queries. De l'autre côté, le nombre de candidats proposés par un UQP dans le contexte de Big-query, peut être très grand.En conséquence, trouver la conguration optimale de la structure d'optimisation devient très dicile, voire impossible (complexité des algorithmes combinatoires).Pour surmonter ces problèmes, nous avons proposé une nouvelle approche qui utilise l'hypergraphes et les algorithmes de partitionnement pour intègre les connaissances liées aux structures d'optimisation lors de la génération du UQP orienté structure d'optimisation, an de minimiser leur coût d'énumération. Notre proposition capture l'interaction de la requête dans un UQP, en divisant les problèmes initiaux dans plusieurs petits sousproblèmes disjoints, qui peuvent être exécutées en parallèle. La division de l'espace de recherche du problème de l'optimisation multiple de requêtes implique la division de l'ensemble des éléments candidats dans plusieurs petits sous-ensembles, ce qui minimise la complexité des algorithmes combinatoires pour sélectionner la meilleure conguration d'une structure d'optimisation.Pour évaluer l'ecience et l'ecacité de notre approche, nous considérons deux structures d'optimisation traditionnelles : vues matérialisées et la fragmentation horizontal.L'interaction de requêtes dans la phase de déploiement : Comme les requêtes sont utilisées par toutes les phases de déploiement : fragmentation de données, allocation de données et équilibrage de charge, nous pensons que cela pourrait être intéressant de pousser notre réexion d'intégrer notre structure de hypergraphe dans tous les problèmes sensibles de la requête. En complétant le travail de déploiement d'un entrepôt de données dans une architecture parallèle du Soumia BENKRID[START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF], réalisé dans notre lab, la dimension Interaction de requêtes a été intégrés à ses algorithmes, en particulier l'allocation et la fragmentation horizontale de données.3 http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview

CHAPTER 2. BACKGROUND & STATE OF ART

The next chapter, we present in details our scalable data structure based on hypergraphs to represent queries and their intermediate results.

Part II Contributions

Chapter 3 Modeling Query Interaction using Hypergraphs

Abstract

In this chapter, we present our rst contribution that concerns the proposition of hypergraph driven data structure which is the fruit of our collaboration with Mentor Graphics, Inc. In the EDA domain, we manipulate logical circuits with millions of gates. For simulation and testing purposes, the hypergraph data structures are widely used. This manage this volume, simulation and testing algorithms use the divide and conquer principle. As a consequence, several hypergraph partitioning libraries exit. This situation motivates us to nd an analogy between the representation of a unied query plan and a logical circuit. Once this analogy established, we adapt EDA hypergraph algorithms and tools to our problem. Intensive experiments are conducted to evaluate the eciency and the quality of our proposal.

Chapter 4 What-if UQP Analysis

Abstract

Capturing the sharing of queries through a hypergraph driven scalable and ecient data structure is a good opportunity to evaluate the impact of changes of UQP on the process of selecting optimization structures (OS ). As we said in the previous chapters that the majority of algorithms selecting OS in the context of relational data warehouse consider an a priori generated UQP and then use it to run their selection algorithms.

As a consequence, they assume that the two processes are dependent. The aims of this chapter at contradicting this assumption, by showing the strong dependency between UQP and OS. This means that each OS has its own UQP.

Fig. 4.3 Example of query scheduling method

Inputs :

-a DW with fact table F and d dimension tables {D 1 , ..,

-a threshold M , that denes the maximum of possible fragments.

Outputs : -a data partitioning schema.

Constraints : -a threshold M that denes the maximum of possible fragments.

III.3.2. Algorithm description

We have used an horizontal data partitioning algorithm, developed in our lab [50].

V. Conclusion

In this chapter, we discussed an example-driven approach to select optimization structures (materialized views and horizontal data partitioning) basing on OS-oriented UQP. The issue of nding candidate set of optimization structures dwarfed when compared to the complexity and ambiguity associated with Big-queries. In the next chapter, we will discuss the exampledriven of modeling parallel data warehousing.

Chapter 5 Query

Abstract

In this chapter, we detail our contribution that consists at using OS-oriented UQP to resolve the problem of parallel data warehouse deployment design. This design is complex, since it requires several phases: data partitioning, fragment allocation, load balancing, query processing, etc. The main particularity of these phases is their property to take into account the workload. Therefore, it is appropriate to generalize our nding in unifying UQP and MQO in the context of parallel data warehouse design.

is not linear since BQ-Design does not ensure a load balancing processing. To determine the cause of this imbalance processing, our second experiment is the study of the data placement distribution of BQ-Design. To this end, we x the number of nodes to M=8 and we check the amount of data stored in each node. As sketched in the gure 5.6, both approaches (F &A, BQ-Design) suers by data placement skew with 43% and 48% respectively. This is due to the selectivity skew. Indeed, both approaches are based on the multi-level partitioning that is based on the splitting of the attribute's domain. This type of splitting depends on the nature of the distribution of the attribute's domain.

Fig. 5.6 BQ-Design Data Placement Distribution

In the third experiment, we focused on the eect of the size of the workload on the performance of BQ-Design comparing with F &A approach. Here, we xed the number of nodes to M = 16

and we ranged the workload size over the interval [30 :60] in order to study how the BQ-Design query performance varies accordingly. Figure 5.7 gives more detail from the execution of a workload of 30 queries under 16 processing. For BQ-Design, all queries benet from the partitioning schema but for F &A only queries using the fragmentation attributes benet from the partitioning.

V.2. BQ-Design Scalability

In this step, the experiments show the impact of the volume of queries and the size of the DW on the quality BQ-Design. We used dierent workload sizes (from 100 to 10 000 queries), ranged the number of nodes over the interval [8:128], and varied the size of data warehouses (100GB, 1TB, and 2TB). We note that the following tests are applied only by BQ-Design tool because the F &A approach does not scale when many queries are used.

Abstract

In this chapter, we present Big-Queries, a database design advisor that assists a DBA during her/his administration tasks when dealing with interaction numerous queries.

Specically, Big-queries provides the following functionalities:

III.7. Deployment designer

Deployment designer allows generating eective data partitioning and fragments allocation schemes by exploiting the query interaction and oering equitable node processing. The partitioning process is guided by sharing expensive operations (e.g. joins). The data needed to process these operations are partitioned and allocated over cluster-nodes.

IV. Implementation

In this section, we present the technical implementation of the framework. The framework has been implemented using the Java programming language. The choice was rather obvious, Java being a solid tool for software development, being platform independent, very robust and reliable and having excellent libraries (including libraries for user interface development). Big-queries framework is developed in windows and Linux environments (Java JDK 1.8. environment). Figure 6.11 shows the main interface of the framework.

The parameters that inuences the cost model in Costmodel!SN -DBC system are:

Data partitioning parameters : In a SN -DBC architecture, data are partitioned over many clusters. Let N F be the number of fragments generated by the process of data partitioning P c ={F 1 , .., F NF }. It is dened as follows:

Such as F d i is the number of fragments of the table D i , and it is assigned the default value

(1) whenever the table does not participate in the partitioning process [START_REF] Boukhalfa | De la conception physique aux outils d administration et de tuning des entrepôts de données[END_REF]. To avoid the explosion of fragments number that causes a diculty to DBA in its maintenance task [START_REF] Bellatreche | An evolutionary approach to schema partitioning selection in a data warehouse[END_REF], a threshold W that delimits the maximum number of fragments N F is therefore required. For any partitioning schema, it is necessary to know which fragment is used by each query. This is done using a matrix called matrix of use M u . The columns and lines of the matrix correspond to k queries and N F fragments respectively. M u [i][j] equal to value 1 if the query Q i use the fragment F j and 0 otherwise. Table 7.3, illustrates the parameters of fragments.

Data allocation parameters : In N S -DBC, the set of fragments are allocated to processing nodes N . If each fragment is allocated to one and only one cluster node, we call it no-redundancy allocation, and redundancy allocation otherwise. To ease the localization of fragments, the system uses a binary matrix of placement (M p ) [START_REF] Benkrid | Le déploiement, une phase à part entière dans le cycle de vie des entrepôts de données : application aux plateformes parallèles[END_REF]. The Cost of a Projection: In projection, there are not redundant attributes to be removed, i.e., the input is exactly the attributes to be forwarded to the parent operator.

If the projection must sort its input, the P interm becomes:

Cost of a Join

We consider the classic join operator that is applied on two relations R 1 an R 2 , and produces an output relation R 1 R 2 equivalent to:

P input and P interim depends on the used join algorithm, as follows:

Nested loop algorithm In the nested loop algorithm, the outer relation should be the smallest one, in order to reduce the number of iterations [START_REF] Kim | On optimizing an sql-like nested query[END_REF]. However, if only one relation ts in main memory, it is used as the inner relation to avoid repeated disk accesses.

Let R 1 and R 2 be the relations implied in the join operator, where R 1 is the outer relation. So, ||R 2 || ≤ M ≤ ||R 1 || As we have shown previously, P input is dened as:

For the intermediate cost, it diers whether inner relation (R 1 ) can t in memory or not. If it does, the cost of the join is equal to the CPU-cost. Otherwise, R 1 must be stored on disk and be repeatedly read from it for every tuple of the outer relation (R 2 ). So, the P interm can be dened as:

But if the inner relation is already sorted, the comparison will be repeated only for tuples satisfying condition predicate. CHAPTER 7. HMETIS: A HYPERGRAPH PARTITIONING PACKAGE and edges, partition the smaller graph (initial partitioning phase), and then uncoarsen it to construct a partition for the original graph (uncoarsening and renement phase). The highly tuned algorithms employed on hM eT iS allow it to quickly produce high-quality partitions for a large variety of hypergraphs.

IX.2. Advantages of hM eT iS

The advantages of hM eT iS compared to other similar algorithms are the following:

Quality of partitions : Experiments on a large number of hypergraphs arising in various domains including VLSI, databases, and data mining show that hM eT iS produces partitions that are consistently better than those produced by other widely used algorithms [START_REF] Karypis | A parallel algorithm for multilevel graph partitioning and sparse matrix ordering[END_REF].

Consuming of execution time : Experiments on a wide range of hypergraphs has

shown that hM eT iS is one to two orders of magnitude faster than other widely used partitioning algorithms.

X. Using of hmetis program

The program hM eT iS is invoked by providing 9 or 10 command line arguments as follows:

hmetis HGraphFile Nparts UBfactor Nruns CType RType Vcycle Reconst dbglvl or hmetis HGraphFile FixFile Nparts UBfactor Nruns CType RType Vcycle Reconst dbglvl

The meaning of the various parameters is as follows:

HGraphFile : is the name of the le that stores the hypergraph.

FixFile is the name of the le that stores information about the pre-assignment of vertices to partitions.

Nparts: is the number of desired partitions. hM eT iS can partition a hypergraph into an arbitrary number of partitions, using recursive bisection. That is, for a 4-way partition.

UBfactor: This parameter is used to specify the allowed imbalance between the partitions during recursive bisection. This is an integer number between 1 and 49, and species the allowed load imbalance in the following way. Consider a hypergraph with n vertices, each having a unit weight, and let b be the UBfactor. The number of vertices assigned to each one of the two partitions will be between (50 -UBfactor )n/100 and (50 + UBfactor )n/100, at each bi-sections.

X.2. Format of the Fix File

The FixFile is used to specify the vertices that are pre-assigned to certain partitions. In general, when computing a k-way partitioning, up to k sets of vertices can be specied, such that each set is pre-assigned to one of the k partitions. For a hypergraph with |V | vertices, the FixFile consists of |V | lines with a single number per line. The i th line of the le contains either the partition number to which the i th vertex is pre-assigned to, or -1 if that vertex can be assigned to any partition . Note that the partition numbers start from 0.

X.3. Format of Output File

The output of hM eT iS is a partition le. The partition le of a hypergraph with |V | vertices, consists of |V | lines with a single number per line. The i th line of the le contains the partition number that the i th vertex belongs to.

X.4. hM eT iS Library Interface

The hypergraph partitioning algorithms in hM eT iS can also be accessed directly using the stand-alone library libhmetis.a. This library provides the routine HMETIS_PartRecursive(). ubfactor: This is the relative imbalance factor to be used at each bisection step. Its meaning is identical to the UBfactor parameter described above. options: This is an array of 9 integers that is used to pass parameters for the various phases of the algorithm. If options[0]=0 then default values are used. If options[0]=1, then the remaining elements of options are interpreted as follows:

options [1]: is the Nruns parameter of hM eT iS, described above. 172 XI. GENERAL GUIDELINES options [2]: is the CType parameter of hM eT iS, described above. options [3]: is the RType parameter of hM eT iS, described above. options [4]: is the Vcycle parameter of hM eT iS, described above. options [5]: is the Reconst parameter of hM eT iS, described above. options [6]: determines whether or not there are sets of vertices that need to be pre-assigned to certain partitions. A value of 0 indicates that no pre-assignment is desired, whereas a value of 1 indicates that there are sets of vertices that need to be pre-assigned. options [7]: determines the random seed to be used to initialize the random number generator of hM eT iS. A negative value indicates that a randomly generated seed should be used (default behavior).

options [START_REF] Akkaoui | Bpmn-based conceptual modeling of etl processes[END_REF]: is the dbglvl parameter of hM eT iS, described above.

XI. General Guidelines

The hM eT iS program allows controlling the multilevel hypergraph bisection paradigm by providing a variety of algorithms for performing the various phases. In particular, it allows checking the following tasks:

1. How the vertices are grouped together during the coarsening phase. This is done by using the CType parameter.

2. How the quality of the bisection is renement during the uncoarsening phase. This is done by using the RType parameter.

Depending on the classes of the hypergraphs that are partitioned, these default settings may not necessarily be optimal. You should experiment with these parameters to see which schemes work better for your classes of problems.

XII. System Requirements

hM eT iS has been written in C language and it has been extensively tested on Sun, SGI, Linux, and IBM. Even though, hM eT iS contains no known bugs. hM eT iS and its updates are made available at: http://www.cs.umn.edu/~metis.

Table 7.6 Relation algebra properties splitting selection using the logical operator AND, the expression becomes σ a=2 (σ b<val (R S)); push the selection with the condition b<val to S, the expression becomes σ a=2 (R σ b<val (S)); push the rst condition to R, the expression becomes σ a=2 (R) σ b<val (S).

Projection laws: the projection can be pushed down like selection to minimize the size of relation by reducing the size of tuples and then minimizing the cost of query processing.

Pushing down projection must veries some conditions: the projection in the expression must eliminate only the attributes that are not used by all above operators; the projection must add the join attributes if there is above join operators; the projection must add all attributes used to dene a condition in above operators (join, selection, etc.).

Joins laws More than the join operators are commutative and associative, they can be dened using selection on one or both relations that verify a join condition. So, R C S =σ C (R × S)