Hadj Mahboubi
email: hadj.mahboubi@eric.univ-lyon2.fr

Jérôme Darmont
email: jerome.darmont@univ-lyon2.fr

Data Mining-based Fragmentation of XML Data Warehouses

Keywords:

With the multiplication of XML data sources, many XML data warehouse models have been proposed to handle data heterogeneity and complexity in a way relational data warehouses fail to achieve. However, XML-native database systems currently suffer from limited performances, both in terms of manageable data volume and response time. Fragmentation helps address both these issues. Derived horizontal fragmentation is typically used in relational data warehouses and can definitely be adapted to the XML context. However, the number of fragments produced by classical algorithms is difficult to control. In this paper, we propose the use of a k-means-based fragmentation approach that allows to master the number of fragments through its k parameter. We experimentally compare its efficiency to classical derived horizontal fragmentation algorithms adapted to XML data warehouses and show its superiority.

INTRODUCTION

XML data sources that are pertinent for decision-support are becoming increasingly common with XML becoming a standard for representing complex business data [START_REF] Beyer | Extending XQuery for Analytics[END_REF]. However, they bear specificities (e.g., heterogeneous number and order of dimensions or complex measures in facts, ragged dimension hierarchies, etc.) that would be intricate to handle in a relational environment. Hence, many efforts toward XML data warehousing have been achieved in the past few years [START_REF] Boussaïd | X-Warehousing: An XML-Based Approach for Warehousing Complex Data[END_REF][START_REF] Pokorný | XML Data Warehouse: Modelling and Querying[END_REF][START_REF] Zhang | X-warehouse: building query pattern-driven data[END_REF], as well as efforts for extending the XQuery language with near On-Line Analytical Processing (OLAP) capabilities, such as advanced grouping and aggregation features [START_REF] Beyer | Extending XQuery for Analytics[END_REF][START_REF] Hachicha | Expressing OLAP operators with the TAX XML algebra[END_REF][START_REF] Wiwatwattana | X ∧ 3: A Cube Operator for XML OLAP[END_REF].

In this context, performance is a critical issue, since XMLnative database systems currently suffer from limited performances, both in terms of manageable data volume and response time for complex analytical queries. These issues are typical of data warehouses and can be addressed by fragmentation. Fragmentation consists in splitting a data set into several fragments such that their combination yields the original warehouse without loss nor information addition. Fragmentation can subsequently lead to distribute the target data warehouse, e.g., on a data grid [START_REF] De Carvalho Costa | Data Warehouses in Grids with High QoS[END_REF]. In the relational context, derived horizontal fragmentation is acknowledged as best-suited to data warehouses, because it takes decision-support query requirements into consideration and avoids computing unnecessary join operations [START_REF] Bellatreche | An Evolutionary Approach to Schema Partitioning Selection in a Data Warehouse[END_REF]. Several approaches have also been proposed for XML data fragmentation, but they do not take multidimensional architectures (i.e., star-like schemas) into account.

In derived horizontal fragmentation, dimensions' primary horizontal fragmentation is crucial. In the relational context, two major algorithms address this issue: the predicate construction [START_REF] Noaman | A Horizontal Fragmentation Algorithm for the Fact Relation in a Distributed Data Warehouse[END_REF] and the affinity-based [START_REF] Navathe | A Mixed Fragmentation Methodology for Initial Distributed Database Design[END_REF] strategies. However, both are automatic and the number of fragments is not known in advance, while it is crucial to master it, especially since distributing M fragments over N nodes with M > N can become an issue in itself. Hence, we propose in this paper the use of a k-means-based fragmentation approach that allows to control the number of fragments through its k parameter. Our idea, which adapts a proposal from the object-oriented domain [START_REF] Darabant | Semi-supervised learning techniques: k-means clustering in OODB Fragmentation[END_REF] to XML warehouses, is to cluster workload query predicates to produce primary horizontal dimension fragments, with one fragment corresponding to one cluster of predicates. Primary fragmentation is then derived on facts. Queries including given predicates are executed over the corresponding fragments only, instead of the whole warehouse, and thus run faster.

The remainder of this paper is organized as follows. We first discuss existing research related to relational data warehouse, XML data and data mining-based fragmentation in Section 2. Then, we present our k-means-based XML data warehouse fragmentation approach in Section 3. We experimentally compare its efficiency to classical derived horizontal fragmentation algorithms adapted to XML data warehouses and show its superiority in Section 4. Finally, we conclude this paper and present future research directions in Section 5.

RELATED WORK

Fragmentation Definition

There are three fragmentation types in the relational context [START_REF] Koreichi | On data fragmentation and allocation in distributed object oriented databases[END_REF]: vertical fragmentation, horizontal fragmentation and hybrid fragmentation.

Vertical fragmentation splits a relation R into subrelations that are projections of R with respect to a subset of attributes. It consists in grouping together attributes that are frequently accessed by queries. Vertical fragments are built by projection. The original relation is reconstructed by joining the fragments.

Horizontal fragmentation divides a relation into subsets of tuples using query predicates. It reduces query processing costs by minimizing the number of irrelevant accessed instances. Horizontal fragments are built by selection. The original relation is reconstructed by fragment union. A variant, derived horizontal fragmentation, consists in partitioning a relation with respect to predicates defined on another relation.

Finally, hybrid fragmentation consists of either horizontal fragments that are subsequently vertically fragmented, or vertical fragments that are subsequently horizontally fragmented.

Data Warehouse Fragmentation

Many research studies address the issue of fragmenting relational data warehouses either to efficiently process analytical queries or to distribute the warehouse.

To improve ad-hoc query performance, Datta et al. exploit a vertical fragmentation of facts to build the Cuio index [START_REF] Datta | Curio: A Novel Solution for Efficient Storage and Indexing in Data Warehouses[END_REF], while Golfarelli et al. apply the same fragmentation on warehouse views [START_REF] Golfarelli | Vertical fragmentation of views in relational data warehouses[END_REF]. Munneke et al. propose a fragmentation methodology for a multidimensional database [START_REF] Munneke | Fragmentation of multidimensional databases[END_REF]. Fragmentation consists in deriving a global data cube into fragments containing a subset of data. This process is defined by the slice and dice operation. The authors also define another fragmentation strategy, server, that removes one or several dimensions from a hypercube to produce fragments with fewer dimensions than the original data cube. Bellatreche and Boukhalfa apply horizontal fragmentation to a star-schema [START_REF] Bellatreche | An Evolutionary Approach to Schema Partitioning Selection in a Data Warehouse[END_REF]. Their fragmentation strategy is based on a query workload and exploits a genetic algorithm to select a partitioning schema. This algorithm aims at choosing an optimal fragmentation schema that minimizes query cost. Finally, Wu and Buchmaan recommend to combine horizontal and vertical fragmentation for query optimization [START_REF] Wu | Research Issues in Data Warehousing[END_REF]. A fact table can be horizontally partitioned with respect to one or more dimensions. It can also be vertically partitioned according to its dimensions, i.e., all the foreign keys to the dimension tables are partitioned as separate tables.

To distribute a data warehouse, Noaman et al. exploit a top-down strategy that uses horizontal fragmentation [START_REF] Noaman | A Horizontal Fragmentation Algorithm for the Fact Relation in a Distributed Data Warehouse[END_REF]. The authors propose an algorithm for deriving horizontal fragments from the fact table based on queries that are defined on all dimension tables. Finally, Wehrle et al. propose to distribute and query a warehouse on a computing grid [START_REF] Wehrle | A Model for Distributing and Querying a Data Warehouse on a Computing Grid[END_REF]. They use derived horizontal fragmentation to split the data warehouse and build a so-called block of chunks, a data set defining a fragment.

In summary, these proposals generally exploit static derived horizontal fragmentation to reduce irrelevant data access rate and efficiently process join operations across mul-tiple relations [START_REF] Bellatreche | An Evolutionary Approach to Schema Partitioning Selection in a Data Warehouse[END_REF][START_REF] Noaman | A Horizontal Fragmentation Algorithm for the Fact Relation in a Distributed Data Warehouse[END_REF][START_REF] Wehrle | A Model for Distributing and Querying a Data Warehouse on a Computing Grid[END_REF]. In the literature, the prevalent methods used for derived horizontal fragmentation are the following [START_REF] Koreichi | On data fragmentation and allocation in distributed object oriented databases[END_REF].

• Predicate construction. This method fragments a relation by using a complete and minimal set of predicates [START_REF] Noaman | A Horizontal Fragmentation Algorithm for the Fact Relation in a Distributed Data Warehouse[END_REF]. Completeness means that two relation instances belonging to the same fragment have the same probability of being accessed by any query. Minimality garantees that there is no redundancy in predicates.

• Affinity-based fragmentation. This method is an adaptation of vertical fragmentation methods to horizontal fragmentation [START_REF] Navathe | A Mixed Fragmentation Methodology for Initial Distributed Database Design[END_REF]. It is based on the predicate affinity concept [START_REF] Zhang | On fragmentation approaches for distributed database design[END_REF], where affinity defines query frequency. Specific matrices (predicate usage and affinity matrices) are exploited to cluster selection predicates.

A cluster is defined as a selection predicate cycle and forms a dimension graph fragment.

XML Database Fragmentation

Recently, several fragmentation techniques for XML data have been proposed. They split an XML document into a new set of XML documents. Their main objective is either to improve XML query performance [START_REF] Bonifati | Efficient Fragmentation of Large XML Documents[END_REF][START_REF] Gertz | Distributed XML Repositories: Top-down Design and Transparent Query Processing[END_REF][START_REF] Ma | Distribution Design for XML Documents[END_REF] or to distribute or exchange XML data over a network [START_REF] Bonifati | XPath lookup queries in P2P networks[END_REF][START_REF] Bose | XFrag: A query Processing Framework for Fragmented XML Data[END_REF].

To fragment XML documents, Ma et al. define a new fragmentation type: split [START_REF] Ma | Fragmentation of XML Documents[END_REF][START_REF] Ma | Distribution Design for XML Documents[END_REF], which is inspired from the oriented-object domain. This fragmentation splits XML document elements and assigns a reference to each subelement. The references are then added to the Document Type Definition (DTD) defining the XML document. The authors extend the DTD and XML-QL languages. Bonifati et al. also propose a fragmentation strategy for XML documents that is driven by structural constraints [START_REF] Bonifati | Efficient Fragmentation of Large XML Documents[END_REF][START_REF] Bonifati | Fragmenting XML Documents via Structural Constraints[END_REF]. This strategy uses both heuristics and statistics. Andrade et al. propose to apply fragmentation to an homogeneous XML collection [START_REF] Andrade | Efficiently Processing XML Queries over Fragmented Repositories with PartiX[END_REF]. They adapt traditional fragmentation techniques to an XML document collection and base their proposal on the Tree Logical Class (TLC) algebra [START_REF] Paparizos | Tree Logical Classes for Efficient Evaluation of XQuery[END_REF]. The authors also evaluate these techniques and show that horizontal fragmentation provides the best performance.

Gertz and Bremer introduce a distribution approach for an XML repository [START_REF] Gertz | Distributed XML Repositories: Top-down Design and Transparent Query Processing[END_REF]. They propose a fragmentation method and outline an allocation model for distributed XML fragments in a centralized archirecture. Gertz and Bremer also define horizontal and vertical fragmentation for an XML document. A fragment is defined with a path expression language, called XF, which is derived from XPath. This fragment is obtained by applying an XF expression on a graph RG representing XML data. Moreover, the authors define exclusion expressions that ensure fragment coherence and disjunction.

Bose and Fegaras use XML fragments for data exchange in a peer-to-peer network (P2P), called XP2P [START_REF] Bose | XFrag: A query Processing Framework for Fragmented XML Data[END_REF]. XML fragments are interrelated and each is uniquely identified by an ID. The authors propose a fragmentation schema, called Tag Structure, to define the structure of data and fragmentation information. Bonifati et al. also define XML fragments for a P2P framework [START_REF] Bonifati | XPath lookup queries in P2P networks[END_REF]. An XML fragment is obtained and identified by a single path expression, a root-to-node path expression XP, and managed on a specific peer. In addition, the authors associate to each fragment two path expressions: super fragment and child fragment. These paths ensure the identification of fragments and relationships.

In summary, these proposals adapt classical static fragmentation methods to split XML data. An XML fragment is defined and identified by a path expression [START_REF] Bonifati | XPath lookup queries in P2P networks[END_REF] or an XML algebra operator [START_REF] Andrade | Efficiently Processing XML Queries over Fragmented Repositories with PartiX[END_REF]. Fragmentation is performed on a single XML document [START_REF] Ma | Fragmentation of XML Documents[END_REF][START_REF] Ma | Distribution Design for XML Documents[END_REF] or on an homogeneous XML collection [START_REF] Andrade | Efficiently Processing XML Queries over Fragmented Repositories with PartiX[END_REF]. Note that XML data warehouse fragmentation has not been addressed yet, to the best of our knowledge.

Data Mining-based Fragmentation

Although data mining has proved useful for selecting physical data structures that enhance performance, such as indexes or materialized views [START_REF] Aouiche | Clustering-based materialized view selection in data warehouses[END_REF][START_REF] Azefack | Dynamic index selection in data warehouses[END_REF], few approaches exploit data mining for fragmentation.

Gorla and Betty exploit association rules (by adapting the Apriori algorithm [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF]) for vertical fragmentation approach in relational databases [START_REF] Gorla | Vertical Fragmentation in Databases Using Data-Mining Technique[END_REF].

Darabant and Campan propose the horizontal fragmentation method for object-oriented distributed databases based on k-means clustering we inspire from [START_REF] Darabant | Semi-supervised learning techniques: k-means clustering in OODB Fragmentation[END_REF]. This method clusters object instances into fragments by taking all complex relationships between classes into account (aggregation, associations and links induced by complex methods).

Finally, Fiolet and Toursel propose a parallel, progressive clustering algorithm to fragment a database and distribute it over a grid [START_REF] Fiolet | Progressive clustering for database distribution on a grid[END_REF]. It is inspired by the CLIQUE sequential clustering algorithm that consists in clustering data by projection.

Though in limited number, these studies clearly demonstrate how data mining can be used for vertical and horizontal fragmentation, through association rule mining and clustering, respectively. They are also static, though.

K-MEANS-BASED FRAGMENTATION

Although XML data warehouse architectures from the literature share a lot of concepts (mostly originating from classical data warehousing), they are nonetheless all different. Hence, we proposed a unified, reference XML data warehouse model that synthesizes and enhances existing models [START_REF] Mahboubi | XML Warehousing and OLAP. Encyclopedia of Data Warehousing and Mining[END_REF], and on which we base our fragmentation work. We first recall this model before detailing our fragmentation approach.

XML Warehouse Reference Model

XML warehousing approaches assume that the warehouse is composed of XML documents that represent both facts and dimensions. All these studies mostly differ in the way dimensions are handled and the number of XML documents that are used to store facts and dimensions. A performance evaluation study of these different representations showed that representing facts in one single XML document and each dimension in one XML document allowed the best performance [START_REF] Boukraa | Proposition d'un Modèle physique pour les entrepôts XML[END_REF]. Moreover, this representation also allows to model constellation schemas without duplicating dimension information. Several fact documents can indeed share the same dimensions. Hence, we adopt this architecture model. More precisely, our reference data warehouse is composed of the following XML documents:

• dw-model.xml that represents warehouse metadata;

• a set of f acts f .xml documents that each store information related to set of facts f ;

• a set of dimension d .xml documents that each store a given dimension d's member values.

The dw-model.xml document (Figure 1) defines the multidimensional structure of the warehouse. Its root node, DW-model, is composed of two types of nodes: dimension and FactDoc. A dimension node defines one dimension, its possible hierarchical levels (Level elements) and attributes (including their types), as well as the path to the corresponding dimension d .xml document. A FactDoc element defines a fact, i.e., its measures, references to the corresponding dimensions, and the path to the corresponding f acts f .xml document.

@id DW-model dimension FactDoc dimension measure @id @type @idref @path @id @path Level @id attribute @name @type attribute dimension dimension @value @value-id @id @dim-id @id @Roll-up FactDoc fact measure @mes-id @dim-id

(2) (1)
Level instance @id (3)
@Drill-Down

Fragmentation Approach

Principle

Since the aim of fragmentation is to optimize query response time, the prevalent fragmentation strategies are workload driven [START_REF] Bellatreche | An Evolutionary Approach to Schema Partitioning Selection in a Data Warehouse[END_REF][START_REF] Bonifati | Efficient Fragmentation of Large XML Documents[END_REF][START_REF] Gertz | Distributed XML Repositories: Top-down Design and Transparent Query Processing[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]. More precisely, they exploit selection predicates found in workload queries to derive suitable fragments. Our approach also belongs to this family. Its general principle is summarized in Figure 3. It outputs both a fragmentation schema (metadata) and the fragmented XML warehouse. It is subdivided into three steps that are detailed in the following sections:

1. selection predicate extraction from the query workload;

2. predicate clustering with the k-means method;

3. fragment construction with respect to predicate clusters.

Selection Predicate Extraction

Selection predicate set P is simply parsed from workload W . For example, let WS be the sample XQuery workload provided in Figure 4 and PS the corresponding predicate set. PS = {p1, p2, p3, p4, ...}, where: p1 = $y/attribute[@id = "c nation key"]/@value>"15", p2 = $y/attribute[@id = "c nation key"]/@value = "13", p3 = $y/attribute[@id = "p type"]/@value = "P BC" and p4 = $y/attribute[@id = "d date name"]/@value = "Sat.". For example, p2 and p3 are selection predicates obtained from query q2 ∈ WS.

Parsed predicates are then coded in a query-predicate matrix QP whose general term QPij equals to 1 if predicate pj ∈ P appears in query qi ∈ W , and to 0 otherwise. For example, the QPS matrix corresponding to WS and PS is featured in Table 1.

Predicate Clustering

Our objective is to derive fragments that optimize data access for a given set of queries. Since horizontal fragments are built from predicates, clustering predicates with respect to queries achieves our goal. Intuitively, we ideally seek to build rectangles (clusters) of 1s in matrix QP . We chose the widely-used k-means algorithm [START_REF] Macqueen | Some Methods for classification and Analysis of Multivariate Observations[END_REF] for clustering. This algorithm inputs vectors of object attributes (columns of QP q1 for $x in //FactDoc/Fact, $y in //dimension[@dim-id="Customer"]/Level/instance where $y/attribute[@id="c nation key"]/@value>"15" and $x/dimension[@dim-id="Customer"]/@value-id=$y/@id return $x q2 for $x in //FactDoc/Fact, $y in //dimension[@dim-id="Customer"]/Level/instance, $z in //dimension[@dim-id="Part"]/Level/instance where $y/attribute[@id="c nation key"]/@value="13" and $y/attribute[@id="p type"]/@value="PBC" and $x/dimension[@dim-id="Customer"]/@value-id=$y/@id and $x/dimension[@dim-id="Part"]/@value-id=$z/@id return $x . . . q10

for $x in //FactDoc/Fact, $y in //dimension[@dim-id="Customer"]/Level/instance, $z in //dimension[@dim-id="Date"]/Level/instance where $y/attribute[@id="c nation key"]/@value="13" and $y/attribute[@id="d date name"]/@value="Sat." and $x/dimension[@dim-id="Customer"]/@value-id=$y/@id and $x/dimension[@dim-id="Part"]/@value-id=$z/@id return $x

q 1 1 0 0 0 q 2 0 1 1 0 ... q 10 0 0 1 1
Table 1: Sample query-predicate matrix QPS in our case). It attempts to find the centers of natural clusters in source data by minimizing total intra-cluster variance k i=1

x j ∈C i (xj -µi) 2 , where Ci, i = 1, ..., k are the k output clusters and µi is the centroid (mean point) of points xj ∈ Ci. Let C be the set of all clusters Ci.

Usually, having k as an input parameter is viewed as a drawback in clustering. In our case, this turns out to be an advantage, since we want to limit the number of clusters/fragments, typically to the number of nodes the XML data warehouse will be distributed on.

In practice, we used the Weka [START_REF] Holmes | Weka: A machine learning workbench[END_REF] SimpleKMeans implementation of k-means. SimpleKMeans uses the Euclidean distance to compute distances between points and clusters. It directly inputs matrix QP (acually, the pj vectors) and k, and outputs set of predicate clusters C. For example, on matrix QPS with k = 2, SimpleKMeans outputs: CS = {{p1}, {p2, p3, p4}}.

Fragment Construction

The fragmentation construction step is itself subdivided into two substeps (Figure 5). First, predicate cluster set C is joined to warehouse schema (document dw-model.xml ) to produce an XML document named frag-schema.xml that represents the fragmentation schema (Figure 6). Its root node, Schema, is composed of fragment elements. Each fragment is identified by an @id attribute and contains dimension elements. A dimension element is identified by a @name attribute and contains predicate elements that store the predicates used for fragmentation. For example, the fragmentation schema frag-schemaS .xml corresponding to cluster set CS is provided in Figure 7.

In this process, we also output a set of XQueries (the fragments.xq script) that, applied to the XML data warehouse (i.e., the whole set of f acts f .xml and dimension d .xml documents), produces the actual fragments, which we store in a set of f acts f i .xml and dimension d i .xml documents, i = 1, ..., k + 1. As fragments, these documents indeed bear the same schema than the original warehouse. The (k + 1) th fragment is based on an additional predicate, denoted ELSE, which is the negation of the conjunction of all predicates in P and is necessary to ensure fragmentation completeness (Section 2.2). In our running example, ELSE = ¬(p1 ∧ p2 ∧ p3 ∧ p4).

Figure 8 provides an excerpt from the fragmentsS .xq script that helps build fragment f 2 from Figure 7. Dimension fragments are generated first, one by one, through selections exploiting the predicate(s) associated to the current dimension (three first queries from Figure 8). Then, fragmentation is derived on facts by joining the original fact document to the newly-created dimension fragments (last query).

EXPERIMENTS

Since derived horizontal fragmentation is a NP-hard problem [START_REF] Boukhalfa | Fragmentations Primaire et Dérivée : Etude de Complexité, Algorithmes de Sélection et Validation sous Oracle 10g[END_REF] solved by heuristics, we choose to validate our proposal experimentally.

Experimental conditions

We use XWeB (XML Data Warehouse Benchmark) [START_REF] Mahboubi | Benchmarking XML data warehouses[END_REF] as a test platform. XWeB is based on the reference model defined in Section 3.1, and proposes a test XML data warehouse and its associated XQuery decision-support workload. <Schema> <fragment id="f1"> <dimension name="Customer"> <predicate name="p1" /> </dimension> </fragment> <fragment id="f2"> <dimension name="Customer"> <predicate name="p2" /> </dimension> <dimension name="Part"> <predicate name="p3" /> </dimension> <dimension name="Date"> <predicate name="p4" /> </dimension> </fragment> </Schema> element dimension{ attribute dim-id{Customer}, element Level{ attribute id {Customers}, for $x in document("dimensionCustomer.xml")//Level where $x//attribute[@id="c nation key"]/@value="13"] return $x } } element dimension{ attribute dim-id{Part}, element Level{ attribute id {Part}, for $x in document("dimensionPart.xml")//Level where $x//attribute[@id="p type"]/@value="PBC"] return $x } } element dimension{ attribute dim-id{Date}, element Level{ attribute id {Date}, for $x in document("dimensionDate.xml")//Level where $x//attribute[@id="d date name"]/@value="Sat."] return $x } } element FactDoc { for $x in //FactDoc/Fact, $y in document("dimensionCustomer f 2 .xml")//instance, $z in document("dimensionPart f 2 .xml")//instance, $t in document("dimensionDate f 2 .xml")//instance where $x/dimension[@dim-id="Customer"]/@value-id=$y/@id and $x/dimension[@dim-id="Part"]/@value-id=$z/@id and $x/dimension[@dim-id="Date"]/@value-id=$t/@id return $x } 2.

XWeB's workload is composed of queries that exploit the warehouse through join and selection operations. We extend this workload by adding queries and selection predicates in order to obtain a significant fragmentation. Due to space constraints, our workload is only available on-line 1 .

We ran our tests on a Pentium 2 GHz PC with 1 GB of main memory and an IDE hard drive under Windows XP. We use the X-Hive XML native DBMS2 to store and query the warehouse. Our code is written in Java and connects

Fragmentation Strategy Comparison

In this first series of experiments, we aim at comparing our k-means-based horizontal fragmentation approach (denoted KM) to the classical derived horizontal fragmentation techniques, namely by predicate construction (PC) and affinitybased (AB) primary fragmentation (Section 2.2), which we adapted to XML data warehouses [START_REF] Mahboubi | Enhancing XML Data Warehouse Performance by Fragmentation[END_REF]. We also record performance when no fragmentation is applied (NF), for reference.

Query Response Time

This experiment measures workload execution time with the three fragmentation strategies we adopted. For KM, we arbitrarily fixed k = 8, which could correspond to a computer cluster's size. The fragments we achieve are stored in distinct collections to simulate data distribution. Each collection can indeed be considered to be stored on a distinct node and can be identified, targeted and queried separately. To measure query execution time over a fragmented warehouse, we first identify the required fragments with the fragschema.xml document. Then, we execute the query over each fragment and save execution time. To simulate parallel execution, we only consider maximum execution time.

Figure 9 plots workload response time with respect to data warehouse size (expressed in number of facts). It clearly shows that fragmentation significantly improves response time, and that KM fragmentation performs better than PC and AB fragmentation when the warehouse scales up. Workload execution time is indeed, on an average, 86.5% faster with KM fragmentation than with NF, and 36.7% faster with KM than with than AB. We believe our approach performs better than classical derived horizontal fragmentation techniques because these latter produce many more fragments (159 with PC and 119 with AB vs. 9 with KM). Hence, at workload execution time, queries must access many fragments (up to 50 from our observations), which multiplies query distribution and result reconstruction costs. The number of accessed fragments is much lower with KM (typically 2 fragments in our experiments).

Fragmentation Overhead

We also compare the PC, AB and KM (k = 8) fragmentation strategies in terms of overhead (i.e., fragmentation algorithm execution time). When assessing performance, it is indeed necessary to find a fair trade-off between gain and overhead. Table 3

Influence of Number of Clusters

In this experiment, we fixed data warehouse size (to 4,000 and 5,000 facts, respectively) and varied KM parameter k to observe its influence on workload response time. Figure 10 confirms that performance improves quickly when fragmentation is applied, but tends to degrade when the number of fragments increases, as we explained in Section 4.2.1. Furthermore, it hints that an optimal number of clusters for our test data warehouse and workload lies between 4 and 6, making us conclude that over-fragmentation must be detected and avoided. Note that, on Figure 10, k = 1 corresponds to the NF experiment (this one fragment is the original warehouse).

CONCLUSION

In this paper, we have introduced an approach for fragmenting XML data warehouses that is based on data mining, and more precisely clustering and the k-means algorithm. Classical derived horizontal fragmentation strategies run automatically and output an unpredictable number of fragments, which is nonetheless crucial to keep under control. By contrast, our approach allows to fully master the To validate our proposal, we have compared our fragmentation strategy to XML adaptations of the two prevalent fragmentation methods for relational data warehouses. Our experimental results show that our approach, by producing a lower number of fragments, outperforms both the others in terms of performance gain and overhead. Now that we have efficiently fragmented an XML data warehouse, our more direct perspective is to distribute it on a data grid. This raises several issues that include processing a global query into subqueries to be sent to the right nodes in the grid, and reconstructing a global result from subquery results. Properly indexing the distributed warehouse to guarantee good performance shall also be very important.

Finally, in a continuous effort to minimize the data warehouse administration function and aim at autoadministrative systems [START_REF] Aouiche | Clustering-based materialized view selection in data warehouses[END_REF][START_REF] Azefack | Dynamic index selection in data warehouses[END_REF], we plan to make our data mining basedfragmentation strategy dynamic. The idea is to perform incremental fragmentation when the warehouse is refreshed. This could be achieved with the help of an incremental variant of the k-means algorithm [START_REF] Pham | An Incremental K-means algorithm[END_REF].

Figure 1 :

 1 Figure 1: dw-model.xml graph structure

Figure 2 :

 2 Figure 2: f acts f .xml (a) and dimension d .xml (b) graph structures

Figure 3 :

 3 Figure 3: K-means-based fragmentation principle

Figure 4 :

 4 Figure 4: XQuery workload snapshot WS p 1 p 2 p 3 p 4 ... q 1 1 0 0 0

Figure 5 :

 5 Figure 5: Fragment construction substeps Schema

Figure 6 :

 6 Figure 6: frag-schema.xml graph structure

Figure 7 :

 7 Figure 7: Sample frag-schemaS.xml document

Figure 8 :

 8 Figure 8: Excerpt from sample fragmentsS.xq script

Figure 9 :

 9 Figure 9: Fragmentation efficiency comparison

Figure 10 :

 10 Figure 10: Influence of number of clusters

Table 2 :

 2 XWeB warehouse characteristicsto X-Hive and Weka through their respective Application Programming Interfaces (APIs). It is available on demand.

	Facts	Maximum number of cells
	Sale facts	7000
	Dimensions	Number of instances
	Customer	1000
	Supplier	1000
	Date	500
	Part	1000
	Documents	Size (MB)
	f acts sales .xml	2.14
	dimensionCustomer.xml 0.431
	dimension Supplier .xml	0.485
	dimensionDate.xml	0.104
	dimensionP art.xml	0.388

  summarizes the results we obtain for an arbitrarily fixed data warehouse size of 3,000 facts. It shows that KM clearly outperforms AB and PC, which is in line with these algorithms' complexities : O(|P |), O(|P | 2 ) and O(2 |P | ), respectively. While AB and PC would have to run off-line, KM could on the other hand be envisaged to run on-line.

	PC AB KM
	Execution time (h) 16.8 11.9 0.25

Table 3 :

 3 Fragmentation overhead comparison

http://eric.univ-lyon2.fr/∼hmahboubi/Workload/workload.xq

http://www.x-hive.com/products/db/

ACKNOWLEDGMENTS

The authors would like to thank Houssem Aissa, Anouar Benzakour, Kevin du Repaire and Hamza El Kartite, who participated in coding our approach in Java.