Yuzhao Yang
email: yuzhao.yang@irit.fr

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

Franck Ravat
email: franck.ravat@irit.fr

Olivier Teste
email: olivier.teste@irit.fr

An Automatic Schema-Instance Approach for Merging Multidimensional Data Warehouses

Keywords: Information systems → Data warehouses Multidimensional data warehouse, schema-instance merging, automatic integration

Using data warehouses to analyse multidimensional data is a significant task in company decision-making. The need for analyzing data stored in different data warehouses generates the requirement of merging them into one integrated data warehouse. The data warehouse merging process is composed of two steps: matching multidimensional components and then merging them. Current approaches do not take all the particularities of multidimensional data warehouses into account, e.g., only merging schemata, but not instances; or not exploiting hierarchies nor fact tables. Thus, in this paper, we propose an automatic merging approach for star schema-modeled data warehouses that works at both the schema and instance levels. We also provide algorithms for merging hierarchies, dimensions and facts. Eventually, we implement our merging algorithms and validate them with the use of both synthetic and benchmark datasets.

decision support systems [START_REF] March | Integrated decision support systems: A data warehousing perspective[END_REF]. Data in DWs are usually modeled in a multidimensional way, which allows users to consult and analyze the aggregated data through multiple analysis axes with On-Line Analysis Processing (OLAP) [START_REF] Romero | A Survey of Multidimensional Modeling Methodologies[END_REF]. In a company, various independent DWs containing some common elements and data may be built for different geographical regions or functional departments. There may also exist common elements and data between the DWs of different companies. The ability to accurately merge diverse DWs into one integrated DW is therefore considered as a major issue [START_REF] Kwakye | Merging Multidimensional Data Models: A Practical Approach for Schema and Data Instances[END_REF]. DW merging constitutes a promising solution to provide more opportunities of analysing the consistent data coming from different sources.

A DW organizes data according to analysis subjects (facts) associated with analysis axes (dimensions). Each fact is composed of indicators (measures). Finally, each dimension may contain one or several analysis viewpoints (hierarchies). Hierarchies allow users to aggregate the attributes of a dimension at different levels to facilitate analysis. Hierarchies are identified by attributes called parameters.

Merging two DWs is a complex task that implies solving several problems. The first issue is identifying the common basic components (attributes, measures) and defining semantic relationships between these components. The second issue is merging schemata that bear common components. Merging two multidimensional DWs is difficult because two dimensions can (1) be completely identical in terms of schema, but not necessarily in terms of instances;

(2) have common hierarchies or have sub-parts of hierarchies in common without necessarily sharing common instances. Likewise, two schemata can deal with the same fact or different facts, and even if they deal with the same facts, they may or may not have measures in common, without necessarily sharing common data.

Moreover, a merged DW should respect the constraints of the input multidimensional elements, especially the hierarchical relationships between attributes. When we merge two dimensions having matched attributes of two DWs, the final DW should preserve all the partial orders of the input hierarchies (i.e., the binary aggregation relationships between parameters) of the two dimensions. It is also necessary to integrate all the instances of the input DWs, which may cause the generation of empty values in the merged DW. Thus, the merging process should also include a proper analysis of empty values.

In sum, the DW merging process concerns matching and merging tasks. The matching task consists in generating correspondences between similar schema elements (dimension attributes and fact measures) [START_REF] Bernstein | Generic Schema Matching, Ten Years Later[END_REF] to link two DWs. The merging task is more complex and must be carried out at two levels: the schema level and the instance level. Schema merging is the process of integrating several schemata into a common, unified schema [START_REF] Quix | Generic Schema Merging[END_REF]. Thus, DW schema merging aims at generating a merged unified multidimensional schema. The instance level merging deals with the integration and management of the instances. In the remainder of this paper, the term "matching" designates schema matching without considering instances, while the term "merging" refers to the complete merging of schemata and corresponding instances.

To address these issues, we define an automatic approach to merge two DWs modeled as star schemata (i.e., schemata containing only one fact table), which [START_REF] Ariyan | Structural Repairs of Multidimensional Databases[END_REF] generates an integrated DW conforming to the multidimensional structures of the input DWs, (2) integrates the input DW instances into the integrated DW and copes with empty values generated during the merging process.

The remainder of this paper is organized as follows. In Section 2, we review the related work about matching and merging DWs. In Section 3, we specify an automatic approach to merge different DWs and provide DW merging algorithms at the schema and instance levels. In Section 4, we experimentally validate our approach. Finally, in Section 5, we conclude this paper and discuss future research.

RELATED WORK

DW merging actually concerns the matching and the merging of multidimensional elements. We classify the existing approaches into four levels: matching multidimensional components, matching multidimensional schemata, merging multidimensional schemata and merging DWs.

A multidimensional component matching approach for matching aggregation levels is based on the fact that the cardinality ratio of two aggregation levels from the same hierarchy is nearly always the same, no matter the dimension they belong to [START_REF] Bergamaschi | Semi-automatic Discovery of Mappings Between Heterogeneous Data Warehouse Dimensions[END_REF]. Thus, by creating and manipulating the cardinality matrix for different dimensions, it is possible to discover the matched attributes.

The matching of multidimensional schemata directs at discovering the matching of every multidimensional components between two multidimensional schemata. A process to automatically match two multidimensional schemata is achieved by evaluating the semantic similarity of multidimensional component names [START_REF] Banek | Automating the Schema Matching Process for Heterogeneous Data Warehouses[END_REF]. Attribute and measure data types are also compared in this way. The selection metric of bipartite graph helps determine the mapping choice and define rules aiming at preserving the partial orders of the hierarchies at mapping time. Another approach matches a set of star schemata generated from both business requirements and data sources [START_REF] Elamin | A Semantic Resource Based Approach for Star Schemas Matching[END_REF]. Semantic similarity helps find the matched facts and dimension names. Yet, the DW designer must intervene to manually identify some elements.

A two-phase approach for automatic multidimensional schema merging is achieved by transforming the multidimensional schema into a UML class diagram [START_REF] Feki | A Two-Phase Approach for Multidimensional Schemes Integration[END_REF]. Then, class names are compared and the number of common attributes relative to the minimal number of attributes of the two classes is computed to decide whether two classes can be merged.

DW merging must operate at both schema and instance levels. Two DW merging approaches are the intersection and union of the matched dimensions. Instance merging is realized by a d-chase procedure [START_REF] Torlone | Two approaches to the integration of heterogeneous data warehouses[END_REF]. The second merging strategy exploits similar dimensions based on the equivalent levels in schema merging [START_REF] Olaru | A Dimension Integration Method for a Heterogeneous Data Warehouse Environment[END_REF]. It also uses the d-chase algorithm for instance merging. However, the two approaches above do not consider the fact table. Another DW merging approach is based on the lexical similarity of schema string names and instances, and by considering schema data types and constraints [START_REF] Kwakye | Merging Multidimensional Data Models: A Practical Approach for Schema and Data Instances[END_REF]. Having the mapping correspondences, the merging algorithm takes the preservation requirements of the multidimensional elements into account, and is formulated to build the final consolidated DW. However, merging details are not precise enough and hierarchies are not considered.

To summarize, none of the existing merging methods can satisfy our DW merging requirements. Some multidimensional components are ignored in these approaches, and the merging details of each specific multidimensional components is not explicit enough, which motivates us to propose a complete DW merging approach.

PRELIMINARIES

We introduce in this section the basic concepts of multidimensional DW design [START_REF] Ravat | Algebraic and Graphic Languages for OLAP Manipulations[END_REF]. The multidimensional DW can be modelled by a star or a constellation schema. In the star schema, there is a single fact connected with different dimensions, while the constellation schema consists of more than one fact which share one or several common dimensions. Definition 3.1. A constellation denoted 𝐶 is defined as (𝑁 𝐶 , 𝐹 𝐶 , 𝐷 𝐶 , 𝑆𝑡𝑎𝑟 𝐶 ) where 𝑁 𝐶 is a constellation name, 𝐹 𝐶 = {𝐹 𝐶 1 , ..., 𝐹 𝐶 𝑚 } is a set of facts, 𝐷 𝐶 = {𝐷 𝐶 1 , ..., 𝐷 𝐶 𝑛 } is a set of dimensions, 𝑆𝑡𝑎𝑟 𝐶 : 𝐹 𝐶 → 2 𝐷 𝐶 associates each fact to its linked dimensions. A star is a constellation where 𝐹 𝐶 contains a single fact; i.e. 𝑚 = 1.

A dimension models an analysis axis and is composed of attributes (dimension properties). Definition 3.2. A dimension, denoted 𝐷 ∈ 𝐷 𝐶 is defined as (𝑁 𝐷 , 𝐴 𝐷 , 𝐻 𝐷 , 𝐼 𝐷 ) where 𝑁 𝐷 is a dimension name, 𝐴 𝐷 = {𝑎 𝐷 1 , ..., 𝑎 𝐷 𝑢 } ∪{𝑖𝑑 𝐷 } is a set of attributes, where 𝑖𝑑 𝐷 represents the dimension identifier, which is also the parameter of the lowest level and called the root parameter. 𝑗 . A sub-hierarchy is a continuous sub-part of a hierarchy which we call the parent hierarchy of the sub-hierarchy. This concept will be used in our algorithms, but it is not really meaningful. So a subhierarchy has the same elements than a hierarchy, but its lowest level is not considered as "𝑖𝑑". All parameters of a sub-hierarchy are contained in its parent hierarchy and have the same partial orders than those in the parent hierarchy. "Continuous" means that in the parameter set of the parent hierarchy of a sub-hierarchy, between the lowest and highest level parameters of the sub-hierarchy, there is no parameter which is in the parent hierarchy but not in the sub-hierarchy. Definition 3.4. A sub-hierarchy 𝑆𝐻 of 𝐻 ∈ 𝐻 𝐷 is defined as (𝑁 𝑆𝐻 , 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 ) where 𝑁 𝑆𝐻 is a sub-hierarchy name, 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 = < 𝑝 𝑆𝐻 1 , ..., 𝑝 𝑆𝐻 𝑣 > is an ordered set of parameters, called parameters, ∀𝑘 ∈ [1...𝑣], 𝑝 𝐻 𝑘 ∈ 𝑃𝑎𝑟𝑎𝑚 𝐻 . According to the relationship between a sub-hierarchy and its parent hierarchy, we have: (1)

𝐻 𝐷 = {𝐻 𝐷 1 , ..., 𝐻 𝐷 𝑣 } is a set of hierarchies, 𝐼 𝐷 = {𝑖 𝐷 1 , ..., 𝑖
∀𝑝 𝑆𝐻 1 , 𝑝 𝑆𝐻 2 ∈ 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 , 𝑝 𝑆𝐻 1 ⪯ 𝑆𝐻 𝑝 𝑆𝐻 2 ⇒ 𝑝 𝑆𝐻 1 , 𝑝 𝑆𝐻 2 ∈ 𝑃𝑎𝑟𝑎𝑚 𝐻 ∧ 𝑝 𝑆𝐻 1 ⪯ 𝐻 𝑝 𝑆𝐻 2 , (2) ∀𝑝 𝐻 1 , 𝑝 𝐻 2 , 𝑝 𝐻 3 ∈ 𝑃𝑎𝑟𝑎𝑚 𝐻 , 𝑝 𝐻 1 ⪯ 𝐻 𝑝 𝐻 2 ∧ 𝑝 𝐻 2 ⪯ 𝐻 𝑝 𝐻 3 ∧ 𝑝 𝐻 1 , 𝑝 𝐻 3 ∈ 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 ⇒ 𝑝 𝐻 2 ∈ 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 .
A fact reflects information that has to be analysed according to dimensions and is modelled through one or several indicators called measures. 𝐼𝑆𝑡𝑎𝑟 𝐹 associates fact instances to their linked dimension instances.

We complete these definitions by a function 𝑒𝑥𝑡𝑒𝑛𝑑 (𝐻 1 , 𝐻 2 ) allowing to extend the parameters of the first (sub)hierarchy 𝐻 1 by the other one (𝐻 2 ).

AN AUTOMATIC APPROACH FOR DW MERGING

Like illustrated in Figure 1, merging two DWs implies matching steps and steps dedicated to the merging of dimensions and facts. The matching of parameters and measures are based on syntactic and semantic similarities [10][6] for the attribute or measure names. Since the matching is intensively studied in the literature, we focus in this paper only on the merging steps of our process (green rectangle in Figure 1). In regard to the merging, we firstly define an algorithm for the merging of hierarchies by decomposing two hierarchies into sub-hierarchy pairs and merging them to get the final hierarchy set. Then, we define an algorithm of dimension merging concerning both instance and schema levels and which completes some empty values. Finally, we define an algorithm of the star merging based on the dimension merging algorithm which merges the dimensions and the facts at the schema and instance levels and corrects the hierarchies after the merging. In this section, we define the schema merging process of two hierarchies coming from two different dimensions. The first challenge is that we should preserve the partial orders of the parameters. The second one is how to decide the partial orders of the parameters coming from different original hierarchies. These challenges are solved in the algorithm proposed below which is achieved by 4 steps: record of the matched parameters, generation of the subhierarchy pairs, merging of the sub-hierarchy pairs and generation of the final hierarchy set.

Algorithm 1 𝑀𝑒𝑟𝑔𝑒𝐻𝑖𝑒𝑟𝑎𝑟𝑐ℎ𝑖𝑒𝑠 (𝐻 1 , 𝐻 2 )
Output: A set of merged hierarchies 𝐻 ′ or two sets of merged hierarchies 𝐻 1 ′ and 𝐻 2 ′ 1: 𝑀, 𝑆𝐻 ′ , 𝐻 ′ ← ∅; //𝑀 is an ordered set of the couples of matched parameters with possibly the couple of the last parameters, for the 𝑛th

parameter couple 𝑀 [𝑛 -1], 𝑀 [𝑛 -1] [0] represents the parameter of 𝐻 1 in 𝑀 [𝑛 -1], while 𝑀 [𝑛 -1] [1] represents the one of 𝐻 2 . 2: 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 1 , 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 1 ′ , 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 2 , 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 2 ′ ← ∅; 3: for each 𝑝 𝐻 1 𝑖 ∈ 𝑃𝑎𝑟𝑎𝑚 𝐻 1 do 4: for each 𝑝 𝐻 2 𝑗 ∈ 𝑃𝑎𝑟𝑎𝑚 𝐻 1 do 5: if 𝑝 𝐻 1 𝑖 ≃ 𝑝 𝐻 2 𝑗 then 6: 𝑀 ← 𝑀+ < 𝑝 𝐻 1 𝑖 , 𝑝 𝐻 2 𝑗 >; 7: end if 8:
end for 9: end for 10: if 𝑀 = ∅ then 11:

𝐻 1 ′ ← {𝐻 1 }; 𝐻 2 ′ ← {𝐻 2 }; 12: return 𝐻 1 ′ , 𝐻 2 ′ 13: else 14: 𝑚 𝑙 ←< 𝑃𝑎𝑟𝑎𝑚 𝐻 1 [ |𝑃𝑎𝑟𝑎𝑚 𝐻 1 | -1], 𝑃𝑎𝑟𝑎𝑚 𝐻 2 [ |𝑃𝑎𝑟𝑎𝑚 𝐻 2 | -1] >; //
for 𝑖 = 0 to |𝑀 | -2 do 19: 𝑝 𝑆𝐻 1 1 ← 𝑀 [𝑖 ] [0]; //first parameter of 𝑆𝐻 1 20: 𝑝 𝑆𝐻 1 𝑣 1 ← 𝑀 [𝑖 + 1] [0]; //last parameter of 𝑆𝐻 1 21: 𝑝 𝑆𝐻 2 1 ← 𝑀 [𝑖 ] [1]; //first parameter of 𝑆𝐻 2 22: 𝑝 𝑆𝐻 2 𝑣 2 ← 𝑀 [𝑖 + 1] [1]; //last parameter of 𝑆𝐻 2 23: if 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 1 ⊆ 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 2 then 24: 𝑆𝐻 ′ ← {𝑆𝐻 2 }; 25: else if 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 2 ⊆ 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 1 then 26: 𝑆𝐻 ′ ← {𝑆𝐻 1 }; 27: else if 𝐹 𝐷 𝑆𝐻 1 _𝑆𝐻 2 ≠ ∅ then 28: for each 𝑃𝑎𝑟𝑎𝑚 ′ ∈ 𝑀𝑒𝑟𝑔𝑒𝑃𝑎𝑟𝑎𝑚𝑒𝑡𝑒𝑟𝑠 (𝐹 𝐷 𝑆𝐻 1 _𝑆𝐻 2 ) do 29: 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻𝑎 ← 𝑃𝑎𝑟𝑎𝑚 ′ ; 𝑆𝐻 ′ ← 𝑆𝐻 ′ +
𝑆𝐻 ′ ← {𝑆𝐻 1 , 𝑆𝐻 2 }; 33: end if 34: 𝐻 ′ ← {𝐻 ′ 𝑎 .𝑒𝑥𝑡𝑒𝑛𝑑 (𝑆𝐻 ′ 𝑏 ) | (𝐻 ′ 𝑎 ∈ 𝐻 ′ ) ∧ (𝑆𝐻 ′ 𝑏 ∈ 𝑆𝐻 ′ ) }; 35:
end for 36: end if

37: if 𝑖𝑑 𝐷 1 ≃ 𝑖𝑑 𝐷 2 then 38: 𝐻 ′ ← 𝐻 ′ ∪ {𝐻 1 , 𝐻 2 }; 39: return 𝐻 ′ 40: else 41: 𝑝 𝑆𝐻 1 ′ 1 ← 𝑝 𝐻 1 1 ; //first parameter of 𝑆𝐻 1 ′ 42: 𝑝 𝑆𝐻 1 ′ 𝑣 ′ 1 ← 𝑀 [0] [0]; //last parameter of 𝑆𝐻 1 ′ 43: 𝑝 𝑆𝐻 2 ′ 1 ← 𝑝 𝐻 2 1 ; //first parameter of 𝑆𝐻 2 ′ 44: 𝑝 𝑆𝐻 2 ′ 𝑣 ′ 2 ← 𝑀 [0] [1]; //last parameter of 𝑆𝐻 2 ′ 45: for each 𝐻 ′ 𝑐 ∈ 𝐻 ′ do 46: 𝐻 1 ′ ← 𝑆𝐻 1 ′ .𝑒𝑥𝑡𝑒𝑛𝑑 (𝐻 ′ 𝑐 ); 𝐻 2 ′ ← 𝑆𝐻 2 ′ .𝑒𝑥𝑡𝑒𝑛𝑑 (𝐻 ′ 𝑐 ); 47:
end for 48:

𝐻 1 ′ ← 𝐻 1 ′ ∪ {𝐻 1 }; 𝐻 1 ′ ← 𝐻 2 ′ ∪ {𝐻 2 }; 49: return 𝐻 1 ′ , 𝐻 2 ′ 50: end if 4.1.
1 Record of the matched parameters. The first step of the algorithm consists in matching the parameters of the two hierarchies and record the matched parameter pairs(𝐿 1 -𝐿 9 ). If there is no matched parameter between the two hierarchies, the merging process stops (𝐿 11 -𝐿 12 ). 4.1.2 Generation of the sub-hierarchy pairs. Then the algorithm generates pairs containing 2 sub-hierarchies (𝑆𝐻 1 and 𝑆𝐻 2 ) of the original hierarchies whose lowest and highest level parameters are adjacent in the list of matched parameter pairs that we created in the previous step (𝐿 18 -𝐿 22 ). To make sure that the last parameters of the two hierarchies are included in the sub-hierarchies, we also add the pair of the last parameters into the matched parameter pair (𝐿 14 -𝐿 17 ).

Example 4.1. In Figure 2, for (a), we have 𝐻 1.𝐶𝑜𝑑𝑒 ≃ 𝐻 2.𝐶𝑜𝑑𝑒, 𝐻 1.𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 ≃ 𝐻 2.𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝐻 1.𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 ≃ 𝐻 2.𝐶𝑜𝑛𝑡𝑖-𝑛𝑒𝑛𝑡. So for the first sub-hierarchy pair, the first parameter of 𝑆𝐻 1 and 𝑆𝐻 2 is 𝐶𝑜𝑑𝑒 and their last parameter is 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, so we have:

𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 1 =< 𝐶𝑜𝑑𝑒, 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 >, 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 2 =< 𝐶𝑜𝑑𝑒, 𝐶𝑖𝑡𝑦, 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 >.
In the second sub-hierarchy pair, we get the subhierarchy of 𝐻 1 from 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 to 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 : 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 1 =< 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝑅𝑒𝑔𝑖𝑜𝑛, 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 >, and the sub-hierarchy of 𝐻 2 from 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 to 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 : 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 2 =< 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝐶𝑜𝑢𝑛-𝑡𝑟𝑦, 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 >. If the last parameters of the two original hierarchies do not match, like 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 of 𝐻 1 and 𝐶𝑜𝑢𝑛𝑡𝑟𝑦 of 𝐻 3 in (b), < 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡, 𝐶𝑜𝑢𝑛𝑡𝑟𝑦 > is added into the matched parameter pair 𝑀 of the algorithm so that the last sub-hierarchies of 𝐻 1 and 𝐻 3 are 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 1 =< 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝑅𝑒𝑔𝑖𝑜𝑛, 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 > and 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 3 =< 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝐶𝑜𝑢𝑛𝑡𝑟𝑦 >.

Merging of the sub-hierarchies.

We then merge each subhierarchy pair to get a set of merged sub-hierarchies (𝑆𝐻 ′ ) and The matched parameters will be merged into one parameter, so it's the unmatched parameters that we should deal with. We have 2 cases in terms of the unmatched parameters.

If one of the sub-hierarchies has no unmatched parameter, we obtain a sub-hierarchy set containing one sub-hierarchy whose parameter set is the same as the other sub-hierarchy (𝐿 23 -𝐿 26 ).

Example 4.2. For the first parameter pair 𝑆𝐻 1 =< 𝐶𝑜𝑑𝑒, 𝐷𝑒𝑝𝑎𝑟𝑡-𝑚𝑒𝑛𝑡 > and 𝑆𝐻 2 =< 𝐶𝑜𝑑𝑒, 𝐶𝑖𝑡𝑦, 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 > of 𝐻 1 and 𝐻 2 in Figure 4. We see that 𝑆𝐻 1 does not have any unmatched parameter, so the obtained sub-hierarchy set contains one sub-hierarchy whose parameter set is the same as 𝑆𝐻 2 which is 𝑃𝑎𝑟𝑎𝑚 𝑆𝐻 ′ =<< 𝐶𝑜𝑑𝑒, 𝐶𝑖𝑡𝑦, 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 >>.

The second case is that both two sub-hierarchies have unmatched parameters (𝐿 27 -𝐿 30 ). We then see if these unmatched parameters can be merged into one or several hierarchies and discover their partial orders. Our solution is based on the functional dependencies (FDs) of these parameters. To be able to detect the FDs of the parameters of the two sub-hierarchies, we should make sure that there are intersections between the instances of these two sub-hierarchies which means that they should have same values on the root parameter of the sub-hierarchies. We keep only the FDs which have a single parameter in both hands and which can not be inferred by transitivity. These FDs are represented in the form of ordered set (𝐹 𝐷 𝑆𝐻 1 _𝑆𝐻 2 ) are then treated by algorithm 2 𝑀𝑒𝑟𝑔𝑒𝑃𝑎𝑟𝑎𝑚𝑒𝑡𝑒𝑟𝑠 to get the parameter sets of the merged sub-hierarchies. If it's not possible to discover the FDs, the two sub-hierarchies are impossible to be merged (𝐿 31 -𝐿 32 ).

Algorithm 2 𝑀𝑒𝑟𝑔𝑒𝑃𝑎𝑟𝑎𝑚𝑒𝑡𝑒𝑟𝑠 constructs recursively the parameter sets from the FDs in the form of ordered sets. In each recursion loop, for each one of these sets, we search for the other ones whose non-last (or non-first) elements have the same values and order as its non-first (or non-last) elements and then merge them (𝐿 6 -𝐿 21 ). The recursion is finished until there are no more two sets being able to be merged (𝐿 22 -𝐿 31 ).

Example 4.3. If we have 𝐹 𝐷 =<< 𝐴, 𝐵 >, < 𝐵, 𝐶 >, < 𝐵, 𝐹 > , < 𝐶, 𝐸 >, < 𝐷, 𝐵 >>. Like illustrated in Figure 3, in the first recursion, by merging the ordered set, we get 𝑃𝑎𝑟𝑎𝑚 =<< 𝐴, 𝐵, 𝐶 > , < 𝐴, 𝐵, 𝐹 >, < 𝐵, 𝐶, 𝐸 >, < 𝐷, 𝐵, 𝐶 >, < 𝐷, 𝐵, 𝐹 >>, all the ordered sets in 𝐹 𝐷 are merged, so there are only merged ordered set in 𝑃𝑎𝑟𝑎𝑚. 𝑃𝑎𝑟𝑎𝑚 is then inputted to the second recursion, we then get the next 𝑃𝑎𝑟𝑎𝑚 =<< 𝐴, 𝐵, 𝐶, 𝐸 >, < 𝐷, 𝐵, 𝐶, 𝐸 >> after the merging of the ordered sets, since < 𝐴, 𝐵, 𝐹 > and < 𝐷, 𝐵, 𝐹 > are not merged, they are also added into 𝑃𝑎𝑟𝑎𝑚, and we get 𝑃𝑎𝑟𝑎𝑚 =<< 𝐴, 𝐵, 𝐶, 𝐸 >, < 𝐷, 𝐵, 𝐶, 𝐸 >, < 𝐴, 𝐵, 𝐹 >, < 𝐷, 𝐵, 𝐹 >>. In the final recursion, it's no more possible to merge any two ordered sets, so the parameter set of the final result of the hierarchy set is << 𝐴, 𝐵, 𝐶, 𝐸 >, < 𝐷, 𝐵, 𝐶, 𝐸 >, < 𝐴, 𝐵, 𝐹 >, < 𝐷, 𝐵, 𝐹 >>. for 𝑗 ← 𝑖 + 1 to 𝑙 do 4.1.4 Generation of the final hierarchy set. 𝐿 37 -𝐿 49 concerns the generation of the final hierarchy set. The two original hierarchies may have different instances, so there may be empty values in the instances of the merged hierarchies. Some empty values can be completed, which is introduced in the next section of dimension merging. But not all empty values can be completed. The empty values generate the incomplete hierarchies and make the analysis difficult. Inspired by the concept of the structural repair [START_REF] Ariyan | Structural Repairs of Multidimensional Databases[END_REF], we also add the two original hierarchies into the final hierarchy set. Then for a parameter which appears in different hierarchies, it can be divided into different parameters in different hierarchies of the hierarchy set so that each hierarchy is complete. Thus, for the multidimensional schema that we get, we provide an analysis form like shown in Figure 4. In the analysis form, one parameter can be marked with different numbers if it is in different hierarchies.

For the generation of the final hierarchy set, we discuss 2 cases where the 2 hierarchies have the matched root parameters which means their dimensions are the same analysis axis and the opposite case which will lead to 2 kinds of output results (one or two sets of merged hierarchies).

If the root parameters of the two original hierarchies match, we simply add the two original hierarchies into the merged hierarchy set obtained in the previous step to get one final merged hierarchy set. (𝐿 37 -𝐿 39 ).

Example 4.4. For the hierarchies 𝐻 1 and 𝐻 2 in Figure 4, we combine the merged hierarchy obtained in 𝐸𝑥𝑎𝑚𝑝𝑙𝑒 4.4 with the result gained in 𝐸𝑥𝑎𝑚𝑝𝑙𝑒 4.2 to get the merged hierarchy 𝐻 𝑚 : < 𝐶𝑜𝑑𝑒, 𝐶𝑖𝑡𝑦, 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝑅𝑒𝑔𝑖𝑜𝑛, 𝐶𝑜𝑢𝑛𝑡𝑟𝑦, 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 >. We add 𝐻 𝑚 into the hierarchy set 𝐻 ′ and then also add the original hierarchies 𝐻 1 and 𝐻 2 . Thus 𝐻 ′ is the final merged hierarchy set. If the root parameters of the two original hierarchies do not match, we will get two merged hierarchy sets instead of one. For each original hierarchy, the final merged hierarchy set will be the extension of the sub-hierarchy containing all the parameters which are not included in any one of the sub-hierarchies created before (𝑆𝐻 1 ′ and 𝑆𝐻 2 ′ ) with the merged hierarchy set that we get plus this original hierarchy itself (𝐿 41 -𝐿 49 ).

Example 4.5. In Figure 5, between 𝐻 1 and 𝐻 3 , we have 𝐻 1 .𝐷𝑒𝑝𝑎𝑟𝑡-𝑚𝑒𝑛𝑡 ≃ 𝐻 3 .𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 and 𝐻 1 .𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 ≃ 𝐻 3 .𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡. We can then get one sub-hierarchy pair in which there are 2 subhierarchies containing parameter sets < 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝑅𝑒𝑔𝑖𝑜𝑛, 𝐶𝑜𝑛-𝑡𝑖𝑛𝑒𝑛𝑡 > and < 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝐶𝑜𝑢𝑛𝑡𝑟𝑦, 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 >. By merging the sub-hierarchy pairs, we get the merged hierarchy whose parameter set is < 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝑅𝑒𝑔𝑖𝑜𝑛, 𝐶𝑜𝑢𝑛𝑡𝑟𝑦, 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 >. For 𝐻 1 , the remaining part < 𝐶𝑜𝑑𝑒 > is associated to it to get the merged hierarchy 𝐻 1 13 . We then get the merged hierarchy set of 𝐻 1 containing 𝐻 1 and 𝐻 1 13 . We do the same thing for 𝐻 3 and get the merged hierarchy set containing 𝐻 3 and 𝐻 2 13 .

Dimension merging

This section concerns the merging of two dimensions having matched attributes which is realized by algorithm 3 𝑀𝑒𝑟𝑔𝑒𝐷𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛𝑠. We consider both the schema and instance levels for the merging of dimensions. The schema merging is based on the merging of hierarchies. Concerning the instances, we have 2 tasks: merging the instances and completing the empty values.

Algorithm 3 𝑀𝑒𝑟𝑔𝑒𝐷𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛𝑠 (𝐷 1 , 𝐷 2 )

Output: One merged dimension 𝐷 ′ or two merged dimensions 𝐷 1 ′ and 𝐷 2 ′

1: if 𝑖𝑑 𝐷 1 ≃ 𝑖𝑑 𝐷 2 then 2:
𝐻 𝐷 ′ ← ∅;

3:

for each 𝐻

𝐷 1 𝑖 ∈ 𝐻 𝐷 1 do 4:
for each 𝐻

𝐷 2 𝑗
∈ 𝐻 𝐷 2 do 5: end for 8:

𝐻 𝐷 ′ ← 𝐻 𝐷 ′ ∪ 𝑀𝑒𝑟𝑔𝑒𝐻𝑖𝑒𝑟𝑎𝑟𝑐ℎ𝑖𝑒𝑠 (𝐻 𝐷 1 𝑖 , 𝐻
𝐴 𝐷 ′ ← 𝐴 𝐷 1 ∪ 𝐴 𝐷 2 ; 𝐻 𝑚 ← 𝐻 𝐷 ′ \ (𝐻 𝐷 1 ∪ 𝐻 𝐷 2 ); 9:
𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝐸𝑚𝑝𝑡 𝑦 (𝐷 ′ , 𝐷 ′ , 𝐻 𝑚 );

10:

return 𝐷 ′ 11: else 12:

𝐻 𝐷 1 ′ , 𝐻 𝐷 2 ′ , 𝐴 𝐷 1 ′ , 𝐴 𝐷 2 ′ ← ∅; 13:
for each 𝐻

𝐷 1 𝑖 ∈ 𝐻 𝐷 1 do 14:
for each 𝐻

𝐷 2 𝑗 ∈ 𝐻 𝐷 2 do 15: 𝐻 1 ′ , 𝐻 2 ′ ← 𝑀𝑒𝑟𝑔𝑒𝐻𝑖𝑒𝑟𝑎𝑟𝑐ℎ𝑖𝑒𝑠(𝐻 𝐷 1 𝑖 , 𝐻 𝐷 2 𝑗 ); 16: 𝐻 𝐷 1 ′ ← 𝐻 𝐷 1 ′ ∪ 𝐻 1 ′ ; 𝐻 𝐷 2 ′ ← 𝐻 𝐷 2 ′ ∪ 𝐻 2 ′ ; 17:
end for 18:

end for 19: return 𝐷 1 ′ , 𝐷 2 ′ 29: end if 4.2.1 Schema merging. If the root parameters of the two dimensions match, the algorithm generates a merged dimension (𝐿 1 -𝐿 8 ). The hierarchy set of the merged dimension is the union of the hierarchy sets generated by merging every 2 hierarchies of the original dimensions (𝐿 3 -𝐿 7 ). We also get a hierarchy set containing only the merged hierarchies but no original hierarchies (𝐻 𝑚 ) which is to be used for the complement of the empty values (𝐿 8 ). The attribute set of the merged dimension is the union of the attribute sets of the original dimensions (𝐿 8 ).

for each 𝐻 𝐷 1 ′ 𝑢 ∈ 𝐻 𝐷 1 ′ do 20: 𝐴 𝐷 1 ′ ← 𝐴 𝐷 1 ′ ∪ 𝑃𝑎𝑟𝑎𝑚 𝐻 𝐷
Example 4.6. Given 2 original dimensions 𝐷 1 and 𝐷 2 in Figure 8 and their instances in Figure 6, we can get the merged dimension schema 𝐷 ′ in Figure 8. In 𝐷 ′ , 𝐻 1 and 𝐻 2 are the original hierarchies of 𝐷 1 , 𝐻 3 and 𝐻 4 are those of 𝐷 2 , 𝐻 13 is a merged hierarchy of 𝐻 1 and 𝐻 3 , and 𝐻 24 is a merged hierarchy of 𝐻 2 and 𝐻 4 . We can thus get 𝐻 𝐷 ′ = {𝐻 1 , 𝐻 2 , 𝐻 3 , 𝐻 4 , 𝐻 13 , 𝐻 24 }, 𝐻 𝑚 = {𝐻 13 , 𝐻 24 }, 𝐴 𝐷 ′ = {𝐶𝑜𝑑𝑒, 𝐶𝑖𝑡𝑦, 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝑅𝑒𝑔𝑖𝑜𝑛, 𝐶𝑜𝑢𝑛𝑡𝑟𝑦, 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡, 𝑃𝑟𝑜 𝑓 𝑒𝑠𝑠𝑖𝑜𝑛, 𝑆𝑢𝑏𝑐𝑎𝑡𝑒𝑔𝑜𝑟𝑦, 𝐶𝑎𝑡𝑒𝑔𝑜𝑟𝑦} When the root parameters of the two dimensions don't match, we will get a merged dimension for each original dimension, which is realized by 𝐿 13 -𝐿 25 . For each original dimension, the hierarchy set of its corresponding merged dimension is the union of all hierarchy sets generated by merging every 2 hierarchies of the original dimensions (𝐿 13 -𝐿 18 ), the attribute set is the union of the attributes of each hierarchy in the merged dimension (𝐿 19 -𝐿 24 ). Similar to the first case, we get a hierarchy set containing only the merged hierarchies for each original dimension (𝐻 𝑚 1 and 𝐻 𝑚 2 ) (𝐿 26 -𝐿 27 ).

Example 4.7. Given 2 original dimensions 𝐷 1 and 𝐷 2 in Figure 5 and their instances in Figure 7, after the execution of algorithm 3 𝑀𝑒𝑟𝑔𝑒𝐷𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛𝑠, we can get the merged dimension schema 𝐷 1 ′ and 𝐷 2 ′ in Figure 5. In 𝐷 1 ′ , 𝐻 1 and 𝐻 2 are the original hierarchies of 𝐷 1 , 𝐻 1 13 is the merged hierarchy of 𝐻 1 and 𝐻 3 . In 𝐷 2 ′ , 𝐻 3 is the original hierarchy of 𝐷 2 , 𝐻 2 13 is the merged hierarchy of 𝐻 1 and 𝐻 3 . So for 𝐷 1 , we have

𝐻 𝐷 1 ′ = {𝐻 1 , 𝐻 2 , 𝐻 1 13 }, 𝐻 𝑚1 = {𝐻 1 13 }, 𝐴 𝐷 1 ′ = {𝐶𝑜𝑑𝑒, 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝑅𝑒𝑔𝑖𝑜𝑛, 𝐶𝑜𝑢𝑛𝑡𝑟𝑦, 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡, 𝑃𝑟𝑜 𝑓 𝑒𝑠𝑠𝑖𝑜𝑛, 𝐶𝑎𝑡𝑒- 𝑔𝑜𝑟𝑦}, while for 𝐷 2 , we get 𝐻 𝐷 2 ′ = {𝐻 3 , 𝐻 2 13 }, 𝐻 𝑚2 = {𝐻 2 13 }, 𝐴 𝐷 2 ′
= {𝐶𝑖𝑡𝑦, 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡, 𝑅𝑒𝑔𝑖𝑜𝑛, 𝐶𝑜𝑢𝑛𝑡𝑟𝑦, 𝐶𝑜𝑛𝑡𝑖𝑛𝑒𝑛𝑡 } 4.2.2 Instance merging and complement. When the root parameters of the two dimensions match, the instance of the merged dimension is obtained by the union of the two original dimension instances which means that we insert the data of the two original dimension tables into the merged dimension table and merge the lines which have the same root parameter instance (𝐿 9 ).

Example 4.8. The instance merging result of Example 4.2.1 is presented in Figure 6. All the data in the original dimension tables 𝐷 1 , 𝐷 2 are integrated into the merged dimension table 𝐷 ′ . The original tables of the instances are marked on the left of the merged table 𝐷 ′ with different colors. There are instances coming from both 𝐷 1 and 𝐷 2 , which means that they have the same root parameter in 𝐷 1 and 𝐷 2 , and are therefore merged together.

The attribute set of the merged dimension contains all the attributes of two original dimensions, while the original dimensions may contain their unique attributes. So there may be empty values in the merged dimension table on the instances coming from only one of the original dimension tables and we should complete the empty values on the basis of the existing data (𝐿 9 ).

The complement of the empty values is realized by Algorithm 𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝐸𝑚𝑝𝑡𝑦 where the input 𝐷 𝐼 𝑛 ← ∅;

3:

𝐼 𝑛 ← 𝐼 𝑛 ∪ {𝑖 𝐷 1 ′ 𝑘 ∈ 𝐼 𝐷 1 ′ | (𝑖 𝐷
𝑃 𝑟 ← {𝑝 𝐻 𝑚 𝑎 𝑣 ∈ 𝑃𝑎𝑟𝑎𝑚 𝐻 𝑚 𝑎 | (𝑖 𝑛 𝑏 .𝑝 𝐻 𝑚 𝑎 𝑣 is not null) ∧(∀𝑝 𝑛 𝑠 ∈ 𝑃 𝑛 , 𝑝 𝐻 𝑚 𝑎 𝑣 ⪯ 𝐻 𝑝 𝑛 𝑠 ) }; 7: if ∃𝑖 𝐷 2 ′ 𝑢 ∈ 𝐼 𝐷 2 ′ ∃𝑝 𝑟 𝑤 ∈ 𝑃 𝑟 , (𝑖 𝐷 2 ′ 𝑢 .𝑝 𝑟 𝑤 = 𝑖 𝑛 𝑏 .𝑝 𝑟 𝑤 ) ∧ (∀𝑝 𝑛 𝑞 ∈ 𝑃 𝑛 , 𝑖 𝐷 2 ′ 𝑢 .𝑝 𝑛 𝑞 is not null) then 8:
for each 𝑝 𝑛 𝑐 ∈ 𝑃 𝑛 do end for 13: end for For an empty value, we search for an instance which has the same value as the instance of this empty value on one of the parameters rolling up to the parameter of the empty value and whose value of the parameter of the empty value is not empty, we can then fill the empty by this non-empty value. The complement of the empty values is also possibly a change of hierarchies. Nevertheless, after completing the empty values of an instance, there may be some completed parameters which are not included in the hierarchies of the instance, so the complement of such values does not make sense in this case. The possible change of the hierarchy is from the hierarchies containing less parameters to those containing more parameters. We know that the merged hierarchies contain more parameters than their corresponding original hierarchies. Hence, before the complement of an instance, we will first look at the merged hierarchies to decide which parameter values can be completed.

In algorithm 4 𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝐸𝑚𝑝𝑡𝑦 which aims to complete the empty values, for each hierarchy in the merged hierarchy set we see, if (a) there exists instances in the merged dimension table which contains empty values on the parameters of this hierarchy (𝐿 3 ) and (b) where the value of the second lowest parameter is not empty (𝐿 3 ). The condition a is basic because we need empty values to be completed. Since we will complete the empty values by the other lines of the merged dimension table, we can only complete the empty values based on the non-id parameters since the id is unique, so if the second lowest parameter is empty, it can never be completed so that the hierarchy can never be completed. That's why we have the condition b. For each one of the instances satisfying these conditions (𝐼 𝑛 ), we search for the parameters (𝑃 𝑛 ) having empty values (𝐿 5 ) and to make sure that each one of them can be completed, we search also for the parameters (𝑃 𝑟 ) which roll up to the lowest of them and to which we refer to complete the empty values (𝐿 6 ). We can then complete the empty values like discussed in the previous paragraph (𝐿 7 -𝐿 11 ).

Example 4.9. After the merging in 𝐸𝑥𝑎𝑚𝑝𝑙𝑒 4.9, we get the empty values of 𝐷 ′ which are in red in Figure 6. The merged hierarchies are 𝐻 13 and 𝐻 24 as illustrated in Figure 5. For 𝐻 13 , the instances of code 𝐶3 and 𝐶5 have empty values on the second root parameter 𝐶𝑖𝑡𝑦, which do not satisfy the condition b. As we can see, for the instance of 𝐶3, although the value of 𝐶𝑜𝑢𝑛𝑡𝑟𝑦 can be retrieved through the value of 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 which is the same as the instance of 𝐶1, the value of 𝐶𝑖𝑡𝑦 can not be completed and thus we should give up this complement. For the instance of 𝐶9, the value of 𝑅𝑒𝑔𝑖𝑜𝑛 is completed by 𝐶7 which has the same value of 𝐷𝑒𝑝𝑎𝑟𝑡𝑚𝑒𝑛𝑡 and whose value of 𝑅𝑒𝑔𝑖𝑜𝑛 is not empty. When it's the turn of 𝐻 24 , values of 𝐶𝑎𝑡𝑒𝑔𝑜𝑟𝑦 of 𝐶8 and 𝐶9 are completed in the same way.

When the root parameters of the two dimensions don't match, the instance merging and complement are done by 𝐿 26 -𝐿 27 . The values of the attributes of one of the dimension tables coming from the other dimension table are empty, so there is only instance complement but no merging. We also call algorithm 4 𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝐸𝑚𝑝𝑡𝑦 to complete the instances for each one of the merged dimension tables.

Example 4.10. The instance merging and complement of the example for 𝐸𝑥𝑎𝑚𝑝𝑙𝑒 4.8 is demonstrated in Figure 7. For 𝐷 1 ′ , 𝐶𝑜𝑢𝑛𝑡𝑟𝑦 comes from the dimension table 𝐷 2 , so the values of 𝐶𝑜𝑢𝑛𝑡𝑟𝑦 are completed by the values in 𝐷 2 ′ . The same operation is also done for 𝑅𝑒𝑔𝑖𝑜𝑛 of 𝐷 2 ′ .

Star merging

In this section, we discuss the merging of two stars. Having two stars, we can get a star schema or a constellation schema because the fact table of each schema may be merged into one schema or not. The star merging is related to the dimension merging and fact merging. Two stars are possible to be merged only if there are dimensions having matched root parameters between them.

Algorithm 5 𝑀𝑒𝑟𝑔𝑒𝐴𝑙𝑙𝐷𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛𝑠 (𝑆 1 , 𝑆 2 )

Output:A set of merged dimensions 𝐷 𝑆 ′ 1: for each 𝐷 𝑆 1 𝑖 ∈ 𝐷 𝑆 1 do 2:
for each 𝐷

𝑆 2 𝑗 ∈ 𝐷 𝑆 2 do 3: if 𝑖𝑑 𝐷 𝑆 1 𝑖 𝑖𝑑 𝐷 𝑆 2 𝑗 then 4: 𝐷 𝑆 1 𝑖 , 𝐷 𝑆 2 𝑗 ← 𝑀𝑒𝑟𝑔𝑒𝐷𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛𝑠 (𝐷 𝑆 1 𝑖 , 𝐷 𝑆 2
𝑗 ); end for 22: end for 23: return 𝐷 𝑆 ′ For the dimensions of the two stars, we have two cases: 1. The two stars have the same number of dimensions and for each dimension of one schema, there is a dimension having matched root parameters in the other schema. 2. There exists at least one dimension between the two stars which does not have a dimension having a matched root parameter in the other.

The dimension merging of two stars is common for the two cases which is done by algorithm 5 𝑀𝑒𝑟𝑔𝑒𝐴𝑙𝑙𝐷𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛. We first merge every two dimensions of the two stars which have unmatched root parameters because the merging of such dimensions is able to complete the original dimensions with complementary attributes (𝐿 1 -𝐿 7 ). Then the dimensions having matched root parameters are merged to generate the merged dimensions of the merged multidimensional schema (𝐿 8 -𝐿 15 ). After the merging and complement of the instances of the dimension tables, there may be some merged hierarchies to which none of the instances belong. In this case, if there will be no more update of the data, such hierarchies should be deleted. There may also be original hierarchies in the merged dimensions such that there is no instance which belongs to them but does not belong to any merged hierarchy containing all the parameters of this original hierarchy. The instances belonging to this kind of hierarchies belong also to other hierarchies which contains more parameters,so they become useless and should also be deleted (𝐿 18 -𝐿 19 ).

Example 4.11. For the merging of the dimensions of two stars 𝑆 1 and 𝑆 2 in Figure 8. The dimension 𝑃𝑟𝑜𝑑𝑢𝑐𝑡 of 𝑆 1 and the dimension 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 of 𝑆 2 are firstly merged since their root parameters don't match but they have other matched parameters. There are then attributes of dimension 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 of 𝑆 2 added into dimension 𝑃𝑟𝑜𝑑𝑢𝑐𝑡 of 𝑆 1 . The two dimensions 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 and the two dimensions 𝑝𝑟𝑜𝑑𝑢𝑐𝑡 have matched root parameters, so they are merged into the final star schema. After the merging and complement of the instance, we verify each hierarchy in the merged dimension tables. If the merging of 𝑆 1 .𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 and 𝑆 2 .𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 is as shown in Figure 5 at the schema level and in Figure 6 at the instance level. In their merged dimension table 𝐷 ′ . We can find that all the instances belonging to 𝐻 4 also belong to 𝐻 24 which is a merged hierarchy containing all the parameters of 𝐻 4 , so 𝐻 4 should be deleted.

We then discuss the merging of the other elements in the two cases which is processed by algorithm 6 𝑀𝑒𝑟𝑔𝑒𝑆𝑡𝑎𝑟 : Algorithm 6 𝑀𝑒𝑟𝑔𝑒𝑆𝑡𝑎𝑟 (𝑆 1 , 𝑆 2 ) Output:A merged multidimensional schema which may be a star schema 𝑆 ′ or a merged constellation schema 𝐶 ′

1: if ( |𝐷 𝑆 1 | = |𝐷 𝑆 1 |) ∧ (∀𝐷 𝑆 1 𝑖 ∈ 𝐷 𝑆 1 ∃𝐷 𝑆 2 𝑗 ∈ 𝐷 𝑆 2 , 𝑖𝑑 𝐷 𝑆 1 𝑖 ≃ 𝑖𝑑 𝐷 𝑆 2
𝑗 ) then 2:

𝐷 𝑆 ′ ← 𝑀𝑒𝑟𝑔𝑒𝐴𝑙𝑙𝐷𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛𝑠 (𝑆 1 , 𝑆 2 ); 3: 𝑀 𝐹 𝑆 ′ ← 𝑀 𝐹 𝑆 1 ∪ 𝑀 𝐹 𝑆 2 ; 𝐼 𝐹 𝑆 ′ ← 𝐼 𝐹 𝑆 1 ∪ 𝐼 𝐹 𝑆 2 ;
4:

𝐼𝑆𝑡𝑎𝑟 𝐹 𝑆 ′ ← 𝐼𝑆𝑡𝑎𝑟 𝐹 𝑆 1 ∪ 𝐼𝑆𝑡𝑎𝑟 𝐹 𝑆 2 ; 5:
return 𝑆 ′ 6: else 7:

𝐷 𝑆 ′ ← 𝑀𝑒𝑟𝑔𝑒𝐴𝑙𝑙𝐷𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛𝑠 (𝑆 1 , 𝑆 2 ); 𝐹 𝐶 ′ ← {𝐹 𝑆 ′ 1 , 𝐹 𝑆 ′ 2 }; 8:
return 𝐶 ′ 9: end if For the first case, we merge the two fact tables into one fact table and get a star schema. The measure set of the merged star schema is the union of the 2 original measures (𝐿 3 ). The fact instances are the union of the measure instances of the two input star schemata (𝐿 4 ). The function associating fact instances to their linked dimension instances of the merged schema is also the union of the functions of the original schemata (𝐿 4 ). Example 4.12. For the two original star schemata in Figure 8, the dimension merging is discussed above so we mainly focus on the merging of fact table instances here. The dimensions 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 , 𝑃𝑟𝑜𝑑𝑢𝑐𝑡 of 𝑆 1 have respectively matched root parameters in the dimensions 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 , 𝑃𝑟𝑜𝑑𝑢𝑐𝑡 of 𝑆 2 . They also have the same number of dimensions. Therefore we get a merged star schema 𝑆 ′ , the original fact tables are merged by merging the measures of 𝑆 1 and 𝑆 2 to get the fact table of 𝑆 ′ . At the instance level, in Figure 9, we have the instances of the fact tables, for the instances of 𝐹 𝑆 1 and 𝐹 𝑆 2 , the framed parts are the instances having the common linked dimension instances, so they are merged into the merged fact table 𝐹 𝑆 ′ , the other instances are also integrated in 𝐹 𝑆 ′ but with empty values in the merged instances, but they will not have big impacts on the analysis, so they will not be treated particularly.

EXPERIMENTAL ASSESSMENTS

To validate the effectiveness of our approach, we applied our algorithms on benchmark data. Unfortunately, we did not find a suitable benchmark for our problem. So, we adapted the datasets of the TPC-H benchmark to generate different DWs. Originally, the TPC-H benchmark serves for benchmarking decision support systems by examining the execution of queries on large volumes of data. Because of space limit, we put the test results in github 1 .

1 https://github.com/Implementation111/Multidimensional-DW-merging

Technical environment and Datasets

The algorithms were implemented by Python 3.7 and were executed on a processor of Intel(R) Core(TM) i5-8265U CPU@ 1.60GHz with a 16G RAM. The data are implemented in R-OLAP format through the Oracle 11g DBMS. The TPC-H benchmark provides a pre-defined relational schema 2 with 8 tables and a generator of massive data.

First, we generated 100M of data files, there are respectively 600572, 15000, 25, 150000, 20000, 80000, 5, 1000 tuples in the table of 𝐿𝑖𝑛𝑒𝑖𝑡𝑒𝑚, 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 , 𝑁 𝑎𝑡𝑖𝑜𝑛, 𝑂𝑟𝑑𝑒𝑟𝑠, 𝑃𝑎𝑟𝑡, 𝑃𝑎𝑟𝑡𝑠𝑢𝑝𝑝, 𝑅𝑒𝑔𝑖𝑜𝑛 and 𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 . Second, to have more deeper hierarchies, we included the data of 𝑁 𝑎𝑡𝑖𝑜𝑛 and 𝑅𝑒𝑔𝑖𝑜𝑛 into 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 and 𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 , and those of 𝑃𝑎𝑟𝑡𝑠𝑢𝑝𝑝 into 𝑃𝑎𝑟𝑡. Third, we transformed these files to generate two use cases by creating 2 DWs for each case. To make sure that there are both common and different instances in different DWs, for each dimension, instead of selecting all the corresponding data, we selected randomly 3/4 of them. For the fact table, we selected the measures related to these dimension data. Since the methods in the related work do not have exactly the same treated components or objective as the ours, we do not have comparable baseline in our experiments. The objective of this experiment is to merge two star schemata having the same 4 dimensions with the matched lowest level of granularity for each dimension.

Star schema generation

After executing our algorithms, we obtain one star schema as shown in Figure 11 which is consistent with the expectations. The parameters of the hierarchies satisfy the relationships of functional dependency. The run time is 30.70s. The 3 dimensions 𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 , 𝑃𝑎𝑟𝑡, 𝐷𝑎𝑡𝑒 of the original DWs are merged. Between the different dimensions 𝑆 1 .𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 and 𝑆 2 .𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 , there is a matched attribute 𝑁 𝑎𝑡𝑖𝑜𝑛, so they are also merged such that 𝑆 1 .𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 provides 𝑆 2 .𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 with the attribute 𝑅𝑒𝑔𝑖𝑜𝑛. Then the 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 in the merged DW also has the attribute 𝑅𝑒𝑔𝑖𝑜𝑛. We can also observe that normally, in the merged schema, there should be the original hierarchy 𝑂𝑟𝑑𝑒𝑟𝑑𝑎𝑡𝑒 → 𝑀𝑜𝑛𝑡ℎ → 𝑌𝑒𝑎𝑟 of 𝑆 2 .𝐷𝑎𝑡𝑒 but which is deleted. By looking up in the table, we find that there is no tuple which belongs to this hierarchy but not to 𝑂𝑟𝑑𝑒𝑟𝑑𝑎𝑡𝑒 → 𝑀𝑜𝑛𝑡ℎ → 𝑆𝑒𝑚𝑒𝑠𝑡𝑒𝑟 → 𝑦𝑒𝑎𝑟 , that's why it is removed.

At the instance level, the result is shown in github. Table 1 shows the number of tuples of the original DWs (𝑁 1 , 𝑁 2 ), of the merged DW (𝑁 ′ ) and the number of the common tuples (𝑁 ∩ ) (tuples having the same dimension key in the original DWs). For each dimension or fact table, 𝑁 ′ = 𝑁 1 + 𝑁 2 -𝑁 ∩ , we can thus confirm that there is no addition or loss of data. For each tuple in the original tables, we verify that the all the values are the same with the values in the merged table. We also find that there are some empty values of the attribute 𝑅𝑒𝑔𝑖𝑜𝑛 in the dimension 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 and 𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 and the attribute 𝑆𝑒𝑚𝑒𝑠𝑡𝑒𝑟 of the dimension 𝑂𝑟𝑑𝑒𝑟𝑑𝑎𝑡𝑒 which are completed. Table 2 shows the number of these attributes in the original DWs (𝑁 1 , 𝑁 2 ) and in the merged DW (𝑁 ′ ), we can then get the number of the completed values 𝑁 + for these attributes. They meet the relationship 𝑁 ′ = 𝑁 1 + 𝑁 2 + 𝑁 + .

Constellation schema generation

The objective of this experiment is to merge two star schemata having the same 2 dimensions (𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 , 𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 ) with the same lowest level of granularity for each dimension, as well as 2 different dimensions (𝑆 1 .𝑃𝑎𝑟𝑡 and 𝑆2.𝐷𝑎𝑡𝑒).

Figure 12: Constellation schema generation

At the schema level, the second test generates a constellation schema like shown in Figure 12. The run time is 32.13s. As expected, the 2 dimensions 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 , 𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 of the original DWs are merged, the other dimension and fact tables are not merged. The dimension 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 gains a new attribute 𝑅𝑒𝑔𝑖𝑜𝑛 by the merging between 𝑆 1 .𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 and 𝑆 2 .𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 . We can see that the hierarchy 𝐶𝑢𝑠𝑡𝑘𝑒𝑦 → 𝑛𝑎𝑡𝑖𝑜𝑛 of 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 which should be in the merged schema is deleted because there is no tuple which belongs to this hierarchy but not to 𝐶𝑢𝑠𝑡𝑘𝑒𝑦 → 𝑛𝑎𝑡𝑖𝑜𝑛 → 𝑅𝑒𝑔𝑖𝑜𝑛. The hierarchy 𝑆𝑢𝑝𝑝𝑘𝑒𝑦 → 𝑛𝑎𝑡𝑖𝑜𝑛 of 𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 is removed due to the same reason.

At the instance level, the data of experiment can be found in github. They also meet 𝑁 ′ = 𝑁 1 + 𝑁 2 -𝑁 ∩ . There are empty values of the attribute 𝑅𝑒𝑔𝑖𝑜𝑛 in the dimension 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 and 𝑆𝑢𝑝𝑝𝑙𝑖𝑒𝑟 which are completed which meet 𝑁 ′ = 𝑁 1 + 𝑁 2 + 𝑁 + .

We got the results conforming to our expectations in the tests, we can thus conclude that our algorithms work well for the different cases discussed at both schema and instance levels.

CONCLUSION AND FUTURE WORK

In this paper, we define an automatic approach to merge two different star schema-modeled DWs, by merging multidimensional schema elements including hierarchies, dimensions and facts at the schema and instance levels. We define the corresponding algorithms, which consider different cases. Our algorithms are implemented and illustrated by various examples.

Since we only discuss the merging of DWs modeled as star schemata in this paper, which is only one (albeit common) possible DW design, we plan to extend our approach by adding the merging of DWs modelled as constellation schemata in the future. There may also be so-called weak attributes in DW components. Thus, we will consider them in future work. Our goal is to provide a complete approach that is integrated in our previous work concerning the automatic integration of tabular data in DWs.

Figure 1 :

 1 Figure 1: Overview of the merging process

Figure 2 :

 2 Figure 2: Example of generation of the sub-hierarchy pairs

Figure 3 :

 3 Figure 3: Example of parameter merging based on FDs Algorithm 2 𝑀𝑒𝑟𝑔𝑒𝑃𝑎𝑟𝑎𝑚𝑒𝑡𝑒𝑟𝑠 (𝐹 𝐷) Output: A set of parameter sets 𝑃𝑎𝑟𝑎𝑚 1: 𝑙 ← |𝐹 𝐷 |; 2: for 𝑛 ← 0 to 𝑙 -1 do 3: 𝑓 𝑑𝑚𝑒𝑟𝑔𝑒𝑑 [𝑛] ← 𝐹𝑎𝑙𝑠𝑒; //Boolean indicating whether an element in 𝐹 𝐷 is mergerd 4: end for 5: 𝑒𝑥𝑖𝑠𝑡𝑚𝑒𝑟𝑔𝑒𝑑 ← 𝐹𝑎𝑙𝑠𝑒; //Boolean indicating whether there are elements that are merged in a recursion loop 6: for 𝑖 ← 0 to 𝑙 -1 do7:

8 :

 8 if 𝐹 𝐷 [𝑖 ] [1 : 𝑙 -1] = 𝐹 𝐷 [ 𝑗 ] [0 : 𝑙 -2] //𝐹 𝐷 [𝑎] [𝑏 : 𝑐 ] represents the ordered set having the values and order from the 𝑏th element to the 𝑐th element of 𝐹 𝐷 [𝑎] then 9: 𝑃𝑎𝑟𝑎𝑚 𝑡 ← 𝐹 𝐷 [𝑖 ] [1 : 𝑙 -1] ; 10: 𝑃𝑎𝑟𝑎𝑚 𝑡 ← 𝑃𝑎𝑟𝑎𝑚 𝑡 + 𝐹 𝐷 [ 𝑗 ] [𝑙 -1]; 11: 𝑃𝑎𝑟𝑎𝑚 ← 𝑃𝑎𝑟𝑎𝑚 + 𝑃𝑎𝑟𝑎𝑚 𝑡 ; 12: 𝑓 𝑑𝑚𝑒𝑟𝑔𝑒𝑑 [𝑖 ], 𝑓 𝑑𝑚𝑒𝑟𝑔𝑒𝑑 [ 𝑗 ], 𝑒𝑥𝑖𝑠𝑡𝑚𝑒𝑟𝑔𝑒𝑑 ← 𝑇 𝑟𝑢𝑒; if 𝐹 𝐷 [𝑖 ] [0 : 𝑙 -2] = 𝐹 𝐷 [ 𝑗 ] [1 : 𝑙 -1] then 15: 𝑃𝑎𝑟𝑎𝑚 𝑡 ← 𝐹 𝐷 [ 𝑗 ] [1 : 𝑙 -1] ; 16: 𝑃𝑎𝑟𝑎𝑚 𝑡 ← 𝑃𝑎𝑟𝑎𝑚 𝑡 + 𝐹 𝐷 [𝑖 ] [𝑙 -1]; 17: 𝑃𝑎𝑟𝑎𝑚 ← 𝑃𝑎𝑟𝑎𝑚 + 𝑃𝑎𝑟𝑎𝑚 𝑡 ; 18: 𝑓 𝑑𝑚𝑒𝑟𝑔𝑒𝑑 [𝑖 ], 𝑓 𝑑𝑚𝑒𝑟𝑔𝑒𝑑 [ 𝑗 ], 𝑒𝑥𝑖𝑠𝑡𝑚𝑒𝑟𝑔𝑒𝑑 ← 𝑇 𝑟𝑢𝑒; for 22: if 𝑒𝑥𝑖𝑠𝑡𝑚𝑒𝑟𝑔𝑒𝑑 = 𝑇 𝑟𝑢𝑒 then 23: for 𝑚 ← 0 to 𝑙 -1 do 24: if 𝑓 𝑑𝑚𝑒𝑟𝑔𝑒𝑑 [𝑚] = 𝐹𝑎𝑙𝑠𝑒 then 25: 𝑃𝑎𝑟𝑎𝑚 ← 𝑃𝑎𝑟𝑎𝑚 + 𝐹 𝐷 [𝑚]; 𝑃𝑎𝑟𝑎𝑚 ← 𝐹 𝐷; 31: end if 32: return 𝑃𝑎𝑟𝑎𝑚 After the merging of each sub-hierarchy pair, we extend the final merged hierarchy set by the new merging result (𝐿 34 ).

Figure 4 :

 4 Figure 4: Hierarchy merging example

Figure 5 :

 5 Figure 5: Dimension merging example (schema)

Figure 6 :

 6 Figure 6: Dimension merging example (instance)

Figure 7 :

 7 Figure 7: Dimension merging example (instance)

Figure 8 :

 8 Figure 8: Star merging example (schema)

Figure 9 :

 9 Figure 9: Star merging example (instance)

  For the second case, since there are unmatched dimensions, the merged schema should be a constellation schema. The facts of the original schemata have no change at both the schema and instance levels and compose the final constellation. (𝐿 8 ) Example 4.13. This example is simplified in Figure10due to the space limit. For the original star schemata 𝑆 1 and 𝑆 2 , they have dimensions 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 which have the matched root parameters. They also have their unique dimensions: 𝑇𝑖𝑚𝑒 of 𝑆 1 and 𝑃𝑟𝑜𝑑𝑢𝑐𝑡 of 𝑆 2 . So the merged schema is a constellation schema generated by merging the dimensions 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 and by keeping the other dimensions and fact tables. At the instance level, we just have a new merged dimension table of 𝐶𝑢𝑠𝑡𝑜𝑚𝑒𝑟 , the other dimension and fact tables remain unchanged.

Figure 10 :

 10 Figure 10: Star merging example (schema)

Figure 11 :

 11 Figure 11: Star schema generation

  Definition 3.3. A hierarchy of a dimension 𝐷, denoted 𝐻 ∈ 𝐻 𝐷 is defined as (𝑁 𝐻 , 𝑃𝑎𝑟𝑎𝑚 𝐻 ) where 𝑁 𝐻 is a hierarchy name, 𝑃𝑎𝑟𝑎𝑚 𝐻 =< 𝑖𝑑 𝐷 , 𝑝 𝐻 2 , ..., 𝑝 𝐻 𝑣 > is an ordered set of dimension attributes, called parameters, which represent useful graduations along the dimensions, ∀𝑘 ∈ [1...𝑣], 𝑝 𝐻 𝑘 ∈ 𝐴 𝐷 . The roll up relationship between two parameters can be denoted by 𝑝 𝐻 1 ⪯ 𝐻 𝑝 𝐻 for the case where 𝑝 𝐻 1 roll up to 𝑝 𝐻 2 in 𝐻 . For 𝑃𝑎𝑟𝑎𝑚 𝐻 , we have 𝑖𝑑 𝐷 ⪯ 𝐻 𝑝 𝐻 1 , 𝑝 𝐻 1 ⪯ 𝐻 𝑝 𝐻 2 , ..., 𝑝 𝐻 𝑣-1 ⪯ 𝐻 𝑝 𝐻 𝑣 . The matching of multidimensional schemata is based on the matching of parameters, the matching relationship between two parameters of two hierarchies 𝑝 𝐻 1 𝑖 and 𝑝 𝐻 2 𝑗 is denoted as 𝑝 𝐻 1 𝑖 ≃ 𝑝 𝐻 2

	𝐷 𝑝 } is a set of dimension instances. The value of the
	instance 𝑖 𝐷 𝑝 for an attribute 𝑎 𝐷 𝑢 is annotated as 𝑖 𝐷 𝑝 .𝑎 𝐷 𝑢 .
	Dimension attributes (also called parameters) are organised ac-
	cording to one or more hierarchies. Hierarchies represent a partic-
	ular vision (perspective) and each parameter represents one data
	granularity according to which measures could be analysed.

𝐹 is a function where D 𝐹 is the cartesian product over sets of dimension instances, which is defined as D 𝐹 = 𝐷 𝑘 ∈𝑆𝑡𝑎𝑟 𝐶 (𝐹 ) 𝐼 𝐷 𝑘 .

  Definition 3.5. A fact, noted 𝐹 ∈ 𝐹 𝐶 is defined as (𝑁 𝐹 , 𝑀 𝐹 , 𝐼 𝐹 , 𝐼𝑆𝑡𝑎𝑟 𝐹 ) where 𝑁 𝐹 is a fact name, 𝑀 𝐹 = {𝑚 𝐹

	1 , ..., 𝑚 𝐹 𝑤 } is a set of
	measures. 𝐼 𝐹 = {𝑖 𝐹 1 , ..., 𝑖 𝐹 𝑞 } is a set of fact instances. The value of a
	measure 𝑚 𝐹 𝑤 of the instance 𝑖 𝐹 𝑞 is denoted as 𝑖 𝐹 𝑞 .𝑚 𝐹 𝑤 . 𝐼𝑆𝑡𝑎𝑟 𝐹 : 𝐼 𝐹 →
	D

  pair of the last parameters

	15:	if 𝑚 𝑙 ∉ 𝑀 then
	16:	𝑀 ← 𝑀 + 𝑚 𝑙 ;
	17:	end if
	18:

  𝑆𝐻 𝑎 ;

	30:	end for
	31:	else
	32:

  𝐻 𝑚 1 ← 𝐻 𝐷 ′ \ 𝐻 𝐷 1 ; 𝐻 𝑚 2 ← 𝐻 𝐷 ′ \ 𝐻 𝐷 2 ;

				1 ′
				𝑢	;
	21: 22: 23:	end for for each 𝐻 𝐷 2 ′ 𝑣 𝐴 𝐷 2 ′ ← 𝐴 𝐷 2 ′ ∈ 𝐻 𝐷 2 ′ ∪ 𝑃𝑎𝑟𝑎𝑚 𝐻 𝐷 2 ′ do 𝑣	;
	24:	end for
	25: 26: 27:	𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝐸𝑚𝑝𝑡 𝑦 (𝐷 1 ′ 𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝐸𝑚𝑝𝑡 𝑦 (𝐷 2 ′	, 𝐷 2 ′ , 𝐷 1 ′	, 𝐻 𝑚 1 ); , 𝐻 𝑚 2 );
	28:

  1 ′ is the merged dimension table having empty values to be completed, 𝐷 2 ′ is the merged dimension table which provides the completed values and 𝐻 𝑚 is the hierarchy set of 𝐷 1 ′ containing only merged hierarchies but no original hierarchies. In this discussed case, 𝐷 ′ is inputted as both 𝐷 1 ′ and 𝐷 2 ′ in 𝐶𝑜𝑚𝑝𝑙𝑒𝑡𝑒𝐸𝑚𝑝𝑡𝑦 since we get one merged dimension including all data of two original dimensions (𝐿 11 ).

  𝐷 𝑆 ′ ← 𝐷 𝑆 ′ ∪ 𝑀𝑒𝑟𝑔𝑒𝐷𝑖𝑚𝑒𝑛𝑠𝑖𝑜𝑛𝑠 (𝐷

	5:	end if
	6:	end for
	7: end for 8: 𝐷 𝑆 ′ ← ∅;
	9: for each 𝐷 𝑢 ∈ 𝐷 𝑆 1 do 𝑆 1
	10:	for each 𝐷	𝑆 2 𝑣 ∈ 𝐷 𝑆 2 do
	11:	if 𝑖𝑑 𝐷 𝑆 1 𝑢 ≃ 𝑖𝑑 𝐷 𝑆 2 𝑣 then
	12:		𝑆 1 𝑢 , 𝐷	𝑆 2 𝑣 );
	13:	end if
	14:	end for
	15: end for 16: for each 𝐷 𝑆 ′ 𝑘 ∈ 𝐷 𝑆 ′ 17: for each 𝐻 𝐷 𝑆 ′ 𝑘 𝑚 ∈ 𝐻 𝐷 𝑆 ′ do 𝑘 do 18: if 𝑖 𝐷 𝑆 ′ 𝑘 𝑟 𝐷 𝑆 ′ ∈ 𝐼 𝐷 𝑆 ′ 𝑘 , (𝑖 𝑘 𝑟 is on 𝐻 𝑚 ) ∨ (𝑖 𝐷 𝑆 ′ 𝑘 𝐻 𝐷 𝑆 ′ 𝑘 𝑚 ∧ (𝐻 𝐷 𝑆 ′ 𝑘 𝑚 ∈ 𝐻 𝐷 𝑆 1 ∨ 𝐻 𝐷 𝑆 ′ 𝑘 𝑚 ∈ 𝐻 𝐷 𝑆 2 )) then 𝐷 𝑆 ′ 𝑘 𝑟 is only on 19: 𝐻 𝐷 𝑆 ′ 𝐷 𝑆 ′ 𝑘 ← 𝐻 𝐷 𝑆 ′ 𝑘 -𝐻 𝑘 𝑚 ;
	20:	end if
	21:

Table 1 :

 1 Number of tuples

		Customer Supplier Part Orderdate Lineorder
	𝑁 1	11250	750	15000	1804	252689
	𝑁 2	11250	750	15000	1804	252821
	𝑁 ∩	8439	556	11261	1349	105345
	𝑁 ′	14061	944	18739	2259	400165
	Customer.Region Supplier.Region Orderdate.Semester
	𝑁 1	X		X	1804
	𝑁 2	X		750	X
	𝑁 ′	9713		846	2259
	𝑁 +	9713		96	455

Table 2 :

 2 Number of attributes

ACKNOWLEDGMENTS

The research depicted in this paper is funded by the French National Research Agency (ANR), project ANR-19-CE23-0005 BI4people (Business Intelligence for the people).


published or not. The documents may come

1

Text published in Popular Music History, 6.2, Sheffield, Equinox Publishing, 2012, p. 100-115 (in anonymous letter to G. [START_REF] Guibert | Les festivals musiques actuelles en Pays de la Loire. Entre logiques d'implantations locales et reconfigurations nationales[END_REF] "Let me ask you a quick question -which by the way failed to come up at the trial which they had: What performer wants his fucking audience dead?" Bill Hicks: Relentless (1992) ii Based on the number of performers, audience and budget, Hellfest is the most important metal music festival in France. It has been held every year since 2006, for three days around June 20 th , in Clisson, a small town of 7.000 inhabitants, in the county of Loire-Atlantique in the West of France. It has not stopped growing since its birth: The first time, 62 groups played on two stages for 20.000 people, with a budget amounting to about 800.000 euros. In 2010, 114 groups played on four stages, 72.000 metalheads came, and the budget reached 3.500.000 euros.

The festival takes place in a region where metal music events have been rare.

In general, metal in France remains an underground and little-known subculture. Compared to the other festivals in the region of Les Pays de la Loire, the Hellfest's economic functioning is an exception, as it is self-financed (subsidies only account for 2% of the budget, while the average is 25% -cf. Guibert 2008, 4) and based on an individual, private initiative. Its growth is thus all the more impressive when one considers that subsidies represent on average a quarter of the budget of regional popular music festivals [START_REF] Guibert | Les festivals musiques actuelles en Pays de la Loire. Entre logiques d'implantations locales et reconfigurations nationales[END_REF]. This success also relies upon the strong number of foreigners who attend the shows (35% of the audience, a national record). Finally, the Hellfest's instigator is a "local boy": Benjamin Barbaud, now 29 years-old, who grew up, played soccer and learned his catechism in Clisson. Obviously, his personal history makes it easier to understand how it was possible to organize the festival there. He gathered a team of mainly local residents to put everything in place. A fast learner, he basically learned by doing, having first created a hardcore punk event, the Fury Fest (2002)(2003)(2004)(2005), before deciding to create one dedicated to metal, with Korn as the 2006 edition's top of the bill, and Kiss as that of 2010's. Looking back to the early years, he says:

We had fun programming GBH and the Dead Kennedys, but it didn't work out that well, which is why we turned to metal. Metalheads spend more money, while punks will have a hard time paying 100 euros for a seat. It's not their state of mind, it's tough explaining to them that we don't get subsidies like general public festivals. […] We always wanted to bring bands from the eighties, but in the beginning we just didn't have the money. […] People made unpleasant comments about Kiss, who aren't extreme, but we just thought that there should be a space for that type of bands in France. We did great with Manowar last year […] Since I've been organizing the Hellfest, I've rediscovered metal." (Chelley and Manoeuvre 2010, 9).

Barbaud is a pragmatist: he responds to an unsatisfied demand, and that is how he justifies his choices of acts, before considering aesthetic or social reasons. This explains why he invites black metal bands -which are, however, a minority in the festival's program.

Birth of Ignorance: The ambivalent 2006-2007 reactions

The establishment of the Hellfest immediately sparked off important debates.

Clisson inhabitants were nervous at the possibility of being disturbed by a rock festival (huge crowd, noise, lack of safety). Yet in 2006, the town hall, which had a right-wing majority, emphasized its economic benefits.

The outcome of the first festival in 2006 was positive. Clisson storekeepers were quite satisfied with the economic impact of the event (lodging, catering, transportation, tourism). Although some of them complained of the nuisances (traffic, noise, etc.), there weren't any incidents. The police noted that the law was universally respected. Considering the festival's size, problems of violence Collaborations with the local civil society developed during the preparations for the following editions (volunteer work, animations, set-building, cleaningup and a "green-friendly" festival).

At Hellfest 2007, the organizers encountered management problems due to the terrible weather and the unrelenting rain -they nicknamed it "Woodstock edition" for that reason. However, these climatic hazards ended up being beneficial, as many "Clissonnais" helped the festival-goers out, welcoming them into their homes or garages. Generally speaking, links between both populations grew stronger iii .

By Demons Be Driven: The 2008 turning point

While the festival was taking root in Clisson, the year 2008 was also a polemical turning point. Violently hostile reactions surfaced sporadically during the months preceding the event, followed by a growth in arguments against the festival. The growth of the internet, and in particular of lobbyist blogs, accompanied the debates.

Municipal elections took place in early 2008, and in Clisson the outgoing mayor was defeated by his left-wing Catholic opponent. The latter had an ambiguous position vis-à-vis the Hellfest, which enabled him to gather opponents into his camp without alienating his supporters. He insisted upon the festival's economic and tourist importance, and acknowledged the right for any musical expression to have a platform. But at the same time, he denounced the attacks against Christians in the lyrics of some of the groups invited. The opponents' rhetoric gained in precision, following the visit, early 2008, of father Benoît Domergue, a priest with a PhD in theology, who studied gothic and metal culture, and who offered several meetings on the topic in Clisson.

One of them was public, and was attended by about 300 people, another was organized behind closed doors for the city council. Domergue also met both of Clisson's priests.

There is something odd about Father Domergue's strategy. During the festival, he appeared as a moderate. He acknowledged the legitimacy of heavy metal as a culture, while condemning its anti-Christian excesses. He wanted a say in the festival's programming, but only in order to separate the wheat from the chaff, and set aside the bands that were too extreme (he mentioned Belphegor, Dimmu Borgir and Impaled Nazarene). Yet, one can only be surprised by the huge gap between what he would say in public and what he wrote in his book on extreme music [START_REF] Domergue | Culture barock et Gothic flamboyant. La musique extrême : un écho surgi des abîmes[END_REF]. In the latter, he proposes a description of Satanist metal, listing dozens of bands, translating the most shocking lyricswhich, undeniably, are easy to find. However, he makes a naïve interpretation of them, as he does for example with bands such as Slipknot or Slayer, one of the apparently most vehemently anti-Christian bands, whose lead singer, Tom Arraya, nonetheless sincerely adopts the Christian faith. As Deena [START_REF] Weinstein | Heavy Metal: The Music and its Culture[END_REF] or Fabien [START_REF] Hein | Rock & Religion. Dieu(x) et la musique du diable[END_REF] put it, calls for the eradication of Christianity should not be taken literally. Domergue establishes this list as if there were a systematic homogeneity between the musicians' intent and the forms taken by their music. That is to say that sound forms are always perfectly adapted and coherent with lyrics and vice-versa, that they are the smoothest, the most faithful vehicle of the explicit message that they are supposed to promote in unison. This fallacious faith in the flat coherence of the musical sign as a whole makes Domergue incapable of conceiving that musicians and audiences can play with meaning and its degrees of seriousness/literalness, that musicians can associate intentions, texts to musical forms that are radically opposed to the monolithical signification he considers the obvious one. The presence of several "Christian core" (see Moberg in this volume) bands at each edition of the festival -or, for that matter, of a great majority of non-Satanist bands playing the same type of music -could have given him some sort of clue pointing to the possibility of ambivalence or polysemy, if not voluntary "misappropriations".

The second stage of Domergue's reasoning was that formally Satanic music, produced by a Satanist intention, can only have, in an appropriate context (the "collective trance" created in metal concerts as he puts it), Satanic effects. These effects are, first, moral, as the music creates despair, depression, and morbid fascination. Second, they are proselytic: music is a technique of converting people to Satanism, based on the conjunction of the mesmerizing show -he mentions "bewitchment" -and this moral weakness. For example,

Domergue writes:

If one considers Black or Death Metal, one can easily see that there is an automatic and mechanical relationship between the tones, the rhythms and the sonorities of this type of music and those who listen to it […] which also results from magic." (Domergue, 2000, 84).

In order to seal up this harmonious chain of meaning, no matter how powerfully corruptive Satanist metal is, the listener still has to be "helpless to resist" its power (Walser 1993, 141). During his 2008 conference, Domergue said that "most young people I meet are lost lambs, but not wolves. For example, some Gothics [sic] came to see me so that I could hear their confessions. These young people swallow the words of a band like Slayer, and their latest anti-Christian album" iv Comments such as this that deny any form of agency to the metal listener who presents symptoms of psychological or moral fragility, are legion in the book and his meetings, as well as being present in the discourse of all Catholic opponents to the Hellfest. As Robert Wright puts it, while examining the controversies around Marilyn Manson in the United States: "the very act of listening becomes symptomatic of antisocial behaviour and even suicidal tendencies" (Wright 2000, 373). Listening is the location where this type of discourse finds its most fertile point of entry, where the Satanist threat can contemplate its ravages, within the intimacy of the notquite-innocent and dangerously alienable soul it lives to musically deprave.

This alleged corruption of course justifies all types of inquisitions wished for by moral authorities: assertion of norms, detection of symptoms and proposal of therapeutics (including, in this case, exorcism v ). To sum things up, there is a perfect similarity between intentions, forms and effects, which is only possible provided that the meaning is petrified, and that the two first instances (the intentions and the musical form) of the musical sign have a direct power on the third (the listener), which is deprived of any autonomous will or sensibility.

While he highlights a certain form of magic and the corrupting psychological potency within the substance of metal, Domergue's discursive strategy carries out a certain moral technique of power that, by mobilizing a whole set of eclectic rhetorical tactics, aims at producing a representation of the metal world that could hook up with vague anxieties within the French Catholic milieu, if not State authorities. The cultural and demographic context of Catholicism in France is one of decline and reaction to different real or perceived "assaults": loss of flock, influence and authority, multiple recent scandals, failure to impose the idea of a "Christian origin" of Europe in its Constitution, fear of Islam, and beyond that, the French anticlerical tradition [Schlegel 2009, 7-16].

Thus, finding/inventing heinous and dangerous enemies enables the Church to present itself as "victim" and exclusive "scapegoat" of rampant "cathophobia", and can be an efficient way to mobilize troops. Taking inspiration from Foucault (2004, 68-69), we could call this strategy a government of senses (Sklower 2008, 211): discursive techniques aimed at producing, with the cooperation of the receptive subject, representations and sensorial (in this case, listening) practices that take root in the pre-existing fears, in order to unite a community in the rejection of a subculture. Not only a peripheral "excess", but maybe a central revelator of recent evolutions within society. In this case, an ambiguous strategy, one that tries to bind a community together in a fantasmatic fear while still trying to debate with the opponents. The goal is to have some legitimacy within both worlds, a position from which negotiating censorship is possible.

Clisson's town hall wasn't insensitive to the more presentable and relatively consensual aspects of Father Domergue's discourse. As representatives of many of the town's believers, the local authorities kept in mind the idea that metal could promote an insidious and dangerous message. They found further confirmation of their suspicions in the conclusions of the Miviludes (the "Interministerial Mission of Vigilance and Fight against Sectarian Excesses", a State organism in charge of informing the authorities and the public about various sectarian dangers -for example, the 2009 annual report dealt with the influence of "New Age" movements) that released its analyses about the "growing influence" of Satanism at the same moment (Spring 2008). It is important to offer a brief description of these analyses, as they represent the authority of the State, and thus -one would hope vi -a neutral, scientific and balanced point of view on the reality of Satanism in France. These conclusions were constantly referred to by the festival's opponents, radical or not (the "Confédération Nationale des Associations de Familles Catholiques", the association "Catholiques en Campagne", the "Cercle des Trois Provinces" quoted at the beginning of this chapter, as well as many Catholic blogs).

What is interesting about this report is that one can find a familiar list of the different "symptoms" and "signs" that must "alert" parents on the risks that their children run when they listen to diabolical music, such as:

-A "radical change in the dress code, and in particular the adoption of black as the only reference", -Forms of "withdrawal" (rejecting usual activities, family, school etc.), -"a total rejection of traditional religions, combined with a growing fascination for pagan emblems, military clothing and relics", -"melancholic tendencies", -"musical tastes orientated towards the more violent forms of metal", -"the excessive consumption of scary and horror movies, as well as of roleplaying games or video games that surf on the same morbid themes", -The viewing of "Internet websites, forums and blogs" that deal with "provocation, Satanism, esotericism, pornography (and paedophilia), mind reading and political extremism -And, among many others, this poetically elliptical one: "the attraction to cultural consumer goods forbidden for any younger than age 16" (Miviludes 2006, 79-80).

A short 2004 preliminary report highlighted "the assiduous frequentation of metal concerts" as "not without risk (nearly-hypnotic atmospheres that encourage states of trance, subliminal messages calling for acting out and stimulating suicidal drives, etc.)" (Miviludes 2004, 2), as well as "incitement to hatred" and "anti-Semitic allusions to paganism and nationalism", not to mention the "sometimes proselyte, fervent Satanists" who haunt the "nebula of fans of Black Metal idols" -many elements that one also finds in Domergue's book as well as on various anti-Hellfest blogs and texts.

Adopting these signs can thus indicate a form of "subjugation" ("mise sous influence"): anything counter-cultural about these practices, anything that can bear a sense of aesthetic identification, that can create values, a sense of community, is immediately rejected as a deleterious manipulation. The Satanist sign, once again, carries a harmful scheme, the threat of dispossession of the self. As Robert Walser puts it, Tipper Gore-type critics "imagine that fans are passive, unable to resist the pernicious messages of heavy metal, and thus they themselves commit the sort of dehumanization they ascribe to popular culture.

They make fans into dupes without agency or subjectivity" (Walser 1993, 144).

Of course, the 2006 report clearly says that there is no "direct causality between listening to Satanist music and acting out", but there still are "indirect effects" that can constitute a "favourable terrain for acting out": "the connection during concerts with practicing and proselyte Satanists; acting out of what is promoted in the songs' lyrics" and "deep rupture with common family culture" (Miviludes 2006, 94).

The fact is that the Miviludes never discusses the "sectarian excesses" that can exist in legitimate religions, and that could formally reveal many affinities with the definitions it proposes of this subculture's functioning; nor would it indulge in analyzing, for example, the moral weakness, the confusion that can push some to seek refuge within the more respectable belief systems and religious communities, or the examples of charlatanism that exist within some of them.

This discourse is proposed in the name of a certain normative -if not religious -order of signs, aimed at the exposure of subcultural forms, as much, if not more, as it is in the name of cultural (freedom of religion, tolerance) and "biopolitical" (our youth's moral health -or rather, the norms that determine the appearance of moral health -, peoples' security) imperatives (Foucault 1976, 184;2004, 233-237). The insistence on "influence" and "acting out"here, obviously, in a more scientific (psychoanalytical) register than in Domergue's -reveals the anxiety concerning familial and social stability, which cannot go without cultural (moral, aesthetic) prescriptions. Once again, culture is analyzed monosemantically, the listening subject is deprived of any capacity of creating significance through autonomous practices (a subjectivation), that in fact "undo" this illusory power (De Certeau 1990, 239-242;Rancière 2008, 18-20/48-49).

Strengthened by this conjuncture, the festival's opponents decided to lead public campaigns against the Hellfest. There was for instance the "Cercle des Trois Provinces" (Circle of the Three Provinces), a Catholic association politically and ideologically rooted in the extreme-right movement vii . They mainly used posters and sent letters to the media and festival's supporters (Ben Barbaud received one, in which he was told that he would have to "answer before God for his deeds" viii …), in which they mixed religious texts, prophecies, prayers, as well as odd articles, for example on Aids in Africa and the solutions recommended by Pope John-Paul II (abstinence etc.). These tracts proposed many elements typical of the rhetoric we analyzed above in a more extreme and caricatured way: condemnation of "anti-Christian racism", of the authorities' "criminal" behaviour, in financing an evil festival in the context of a "multiplication of tomb desecrations in cemeteries", Satanist proselytism which "harnesses the weakness of certain young people who go through an identity, mental crisis, lack future perspectives, break with their family, drop out of school" thanks to "magical", "sexual" and "destructive rituals" and their attraction to anything "morbid" or "esoteric" etc.

A right-wing association of Clisson inhabitants wanted the festival to disappear, demanding the "protection of public order and of youth" (Hebdo Sèvres et Maine, May 8 th , 2008, 3). In this case, the evocation of humanist and republican or traditional principles, as well of course as the defence of teenagers, constituted a means by which these groups propounded their values within the broader ethical field of civil society and the authorities.

Quite quickly though, the church of Clisson distanced itself from such positions. The festival's third edition dispelled all doubts, as it took place under a bright sky, and without any major incidents. The exchanges between festivalgoers and local inhabitants had by then become part of the "folklore". The local library presented books on the subject, inviting the authors to present their work, the festival showed films on metal culture in Clisson's movie theatre. More and more people also provided shelter for the metal fans.

III. God Gave Rock 'n' Roll to Everyone -the 2009-2010 confrontation

The Hellfest came out strengthened by the 2008 edition, even though the most conservative Catholics kept on protesting about the Satanist factory it was supposed to be ix . The festival's organizers feared a big assault because of Marilyn Manson's top billing on June 20 th , but no such thing happened. In the Clisson parish bulletin, the priest called for serenity and opened permanent prayer services during the entire festival (Ouest France, June 10 th , 2009, 8).

But a broader attack coming from national right-wing political parties and traditionalist Catholic blogs took shape shortly before the beginning of the festival, in the form of questioning the (scarce) public subsidies granted by the General Council of the Loire Atlantique county and the Regional Council of the Pays de la Loire. A small right-wing party close to the government's UMP party (Union for a Popular Movement), the CNI (National Independents Centre) opened the assault, declaring that "the limits of the unbearable have been crossed […] Our taxes serve the diffusion of extremely violent messages" (Presse Océan, June 20 th , 2009, 2). The local representation of the UNI (the main UMP-affiliated students association) and Catholic associations pursued the same agenda x . These different organizations wanted to put pressure on the Hellfest by email and phone messages sent to the festival's public or private (Kronenbourg, Coca-Cola) sponsors and their servers and telephone switchboards were overwhelmed for several days. Coca-Cola, who supported the festival with its Monster Energy Drink, declared in early July that it would withdraw from the festival (however, it agreed to come back in 2010).

Various "interest groups" reacted to these attacks. First, those who supported the Hellfest, or more globally, metal. Specialized blogs and websites (Metallorgy, spirit-of-metal, Metal Impact…) relayed the information and criticized it. Fans created a specific website in defence of the festival (proHellfest.fr), which gathered the many initiatives, such as Facebook groups xi . Professionals of the cultural field mobilized by proposing a petition: "Appel à soutien au Hellfest: pour la diversité artistique" (Call for the support of the Hellfest: for artistic diversity) xii . As with the year before, it was only days before the festival that the polemic developed, losing force only days after. It was scarcely touched on by the media, as once again there were no incidents in 2009. Security companies even said it was their favourite event in the West of France because of its peaceful nature (Hebdo Sèvre et Maine, June 25 th , 2009, 11). Besides, the programming of bands such as Europe and Mötley Crüe broadened its appeal within the metal community.

Robert Culat, priest of the Carpentras parish and an active supporter of metal, intervened during the May 2009 debate in Clisson. His perception of the metal milieu opposes that of Father Domergue's in many ways, as well as, a fortiori, that of the more fundamentalist Catholic groups. He loves metal (Opeth being his favourite), listens to many anti-Christian bands (like Emperor), and even wrote a book on his experience and encounter with this world (Culat 2008), in which he interviewed dozens of fans about their relationship to this music. In a June 28 th , 2009 post on his myspace, "Padre Bob" delivered a digest of his thoughts on metal, in which he criticized the caricatured vision proposed by extremist Catholics. He used many biblical references, Church texts, such as the Catholic social teaching, or various encyclics, in order to dispel the accusation of Satanism and reverse it against "true Satanism", i.e. hedonistic individualism in contemporary capitalism.

Culat finds positive, and even Christian values within the metal world, such as solidarity (he mentions the grass-root fundraising that was organized to help Chuck Shuldiner xiii ). What the anti-Hellfest Catholics consider as perversion or dangerous passivity, for him, becomes the sign of a praiseworthy spiritual craving: one mustn't judge "those who seem to refuse God", because "certain oppositions can be closer to a true religious attitude than soulless conformism" and "sometimes, 'blasphemous' words uttered by Atheists can be the expression of a more or less conscious spiritual research." Thus, rather than condemning without knowing, one must follow Paul VI's precepts (the "bête noire" of Catholic fundamentalists), that is to "get closer to the profane society" and try to "evangelize the culture, the milieus and the mentalities so that the reference to God find its right place". Thus, the adoption of signs, and even of a specific liturgy by metal fans should not be considered as a threat to Christianity anymore, but as a godsend in disguise for a new evangelization.

To moral fundamentalism, he opposes a rationale of pastoral efficiency: "Is asking for censorship or banning the solution to promote the cause of the Gospel and of faith among the young people that are generally very far from Christianity?" xiv he asks. His discourse is not one of universal tolerance xv , but one of subcultural sympathy. He believes in the spiritual power of the metal community, in its capacity to recognize the true meaning of its practices. The desires that underpin the adherence to metal signs reveal virtues that are absolutely compatible with the Christian faith and way of life, specifically: love, understanding and evangelization vs. hatred, stereotypes and inquisition.

The year 2010 was one of national controversies. Adopted by the locals, the Hellfest had become a much-loved, and 72.000 fans came to hear the Deftones, Fear Factory, Infectious Grooves, Sepultura, Slayer, Carcass, Alice Cooper and Kiss, as well as the 108 other bands. Nonetheless, the polemics resumed, starting earlier than in previous years and reaching an unprecedented scale. Once again, the political context was responsible for making the argument an issue, as regional elections took place in March 2010. On March 11 th , during a meeting of the right-wing regional opposition, Catholic and xenophobic politician Philippe de Villiers stated that "our values aren't the ones that push the actual Regional Council to finance a Satanist festival!". In the heat of the electoral campaign, Christine Boutin, former minister and president of the Christian Democrat party (equally in the region's political opposition) disclosed on her website a letter sent to brewer Kronenbourg, asking the company if it was "relevant to associate [their] image to a festival that promotes and encourages a culture of death?" xvi . An idiom that carries all the ex-minister's struggles against other faces of this "culture" -abortion, homosexuality… To this literal and monosemic interpretation of the sign "death", one could oppose the testimony of death metal musician Dan Saladin, gathered by Harris Berger: "The energy of a death metal performance, and the attendant subcultural community-building that these musicians so enthusiastically participated in, is pursued as a pro-active response to the apathy, a way of overcoming hopelessness" (Berger 1999, 173), or even Marilyn Manson's answer to such accusations (Wright 2000, 375). The apparent morbidity of the metal milieu is in fact often the sign of a struggle against the threat of insensibility or spiritlessness: a conjuration of melancholy, an aspiration for energy, a research of community.

On March 30 th , socialist deputy Patrick Roy reacted by interrogating Minister of Culture Frédéric Mitterrand, during a parliamentary questions. The latter played down the controversy while emphasising that the State didn't subsidize the festival. The left won the elections, and the controversy disappeared during the month of April. Two elements must be noted here.

First, this exposure of the Hellfest proved a lucrative one for the Hellfest's organizers, as the number of tickets sold grew again in 2010. Secondly, the national media globally defended the Hellfest. Even TF1, the most popular French private television channel, although it did show in its reportage on the festival xvii a "shocking" backstage Satanist ritual whereby the members of Scandinavian band Watain covered their faces with animal blood before their performance, insisted predominantly on the "friendly atmosphere" that reigned during the whole event.

Conclusion

From this brief review of the controversies surrounding the Hellfest, one can identify two fundamental tendencies. First, on a local level, the perception of the festival -and through it, of metal -evolved from questions and incomprehension to enthusiasm and support. One could consider these debates a Habermassian public sphere [START_REF] Habermas | L'Espace public : archéologie de la publicité comme dimension constitutive de la société bourgeoise[END_REF] in the sense that practical reason and consensus prevailed. During public debates, the various parties were invited to have their say, and organizers tried to deal with some of the critics. But on the national level, it is a public sphere according to Nancy Fraser's definition [START_REF] Fraser | Rethinking the public sphere: a contribution to a critique of actually existing democracy[END_REF]): antagonistic, impassioned, and animated by subaltern counter-publics. The public dominant in previous eras (Catholics opposed to blasphemy and symbolic attacks) has progressively become a minority, as the influence of the Church has declined in French society. Rock's partisans now promote potent norms.

Any strategy of cultural and moral struggle summons a various set of discourses and rhetorical strategies. Specifically in this case, Catholic opponents to the festival proposed on the one hand a moral and aesthetic one, on the value and power of a given cultural sign, and the means by which authorities should fight against it. On the other hand, they used various cultural strategies of struggle that followed an axis going from total ideological intransigence to a set of flexible tactics of negotiation with opponents or other institutions' values. Among the extremists -in this case, Catholic fundamentalists -, there was the antagonistic and closed assertion of a conservative value and belief system, and among the more pragmatic, the search for some sort of "settlement" between the ideological systems supported by the different agents of the polemic. This meant convincing the authorities to put limits on freedom of speech in the name of tolerance (a Republican, secular value), and thus accept the censorship of violently anti-Christian bands (their political goal). These strategies reveal different perceptions of each agent's capacity to defend its values at the moment of the struggle ("should we confront or negotiate?") as well as, eventually, interpretations of the state or "origin" of the loss of influence ("what does the existence of a Satanist festival in this "Catholic" country say about the evolution of our authority?").

The question of the limit imposed on what metal bands can express cannot be judged independently from this context of broader relationships in which the targeted authorities (in this case, the Church, but also eventually others such as the State, the family, the workplace etc.) are entangled. Indeed, the argument according to which similar attacks on Judaism or Islam wouldn't be tolerated is quite right, if considered in abstracto. But the difference in this case is that the Catholic Church, despite its long-term decline in influence symbolically remains a dominant moral figure, historically and geographically rooted (especially in Western France), benefiting from traditional privileges (State-funded private schools, for example) as well as recent reactionary presidential endorsements xviii . This is where the French context is different from that of the United-States, although the comparison with the Tipper Gore/PMRC debates shows many strong similarities (Walser 1993, 138-142) notably when it comes to "preserving" youth's moral health. In France, Christianity is a weakening yet symbolically potent figure of moral order and repression. All of this makes it a purely metaphoric -thus caricatured -target of counter-cultural rebellious desires within the vast majority of metal fandom.

Just as the stereotypical depictions of the latter by certain Catholic groups serve as a pretext to galvanize opposition against its specific "victimization" as a religion, while using at the same time typically secular "multiculturalist" rhetorics (denouncing intolerance and lack of respect for freedom of religion).

The question of the limits to freedom of expression is however a problematic one for the metal world. When can one identify the objective signification of a song and its concrete dangers (Kahn-Harris 2003)? If we draw these limits, do we not risk reifying signification when we previously set ourselves up as champions of its collective construction? This same confidence in the "hijacking" of signification operated by the listener represents a chance or a threat depending on the circumstances, the intentions, the interactions, the needs of those who preside over the "choices" guiding such practices… A Western band virulently criticizing Islam offers little doubt about its xenophobia, whereas the wearing of T-shirts with the logo of explicit anti-Semitic bands by Israeli metal fans -although quite meaningful -obviously does not point to a literal identification (Kahn-Harris 2002, 126). Indeed, metal maintains a counter-cultural aura as long as it keeps sparking off such polemics -and it is a subculture that feeds on provocation and excess. From this point of view, the strategy of the Hellfest's organizers, consisting in successfully portraying metalheads as sweet and harmless boys can be problematic: could these ultra-virile and hyper-mean musical assaults only be a farce, a sort of musical translation of wrestling kitsch? Specific provocative images promoted by bands can only be considered as countercultural in context: multiple scales must be taken into consideration, as everything depends on what one considers as the dominant culture targeted by a particular genre, band or song, and the criteria chosen to define its main signification. To insist on the multiplicity of signifying practices (De Certeau 1990, 239-242), on the spectator's activity, against the types of "distribution of the sensible" (Rancière 2000, 12) that the idea of passivity contains, is to accept the frailty and ideological and political relativity of any "counter"culture. Its identity or boundaries are then to be negotiated in a power struggle involving the agents of a cultural polemic (or "war"), the values chosen to judge these forms, the authority of the methods assessing their danger and the right to freedom of speech.

KEY WORDS

France -Hellfest -festival -local scene -metal -rock culture -popular music in France -youth -counter-culture -subculture -public spherereligion -Catholicism -politics -controversies -sign -significationgovernment of senses -distribution of the sensible Cambridge University Press. Talking about Metal or techno music concerts, he says, elsewhere: "The human intelligence and will are not directly concerned by these stimuli, but a true "hypersaturation" of the senses and an exacerbated imagination are practically capable of isolating them. This conditioning and this oppression […] are such, that cases of infestations or possessions can be imagined in such circumstances" . See Le Subliminal.

Interview du Père Domergue. http://www.lesubliminal.fr/interview_du_pere_domergue_193.htm. vi The Miviludes' method and conclusions were severely criticized by one of the members of the commission working on Satanism, sociologist Olivier Bobineau (Bobineau 2008), who lead a collective counter-survey on the question, concluding there was barely any Satanist sectarian risk in France. vii They are an emanation of Jean Ousset's "Cité catholique", a "nationalcatholic", former member of Charles Maurras' "Action Française" (the inglorious royalist and anti-Semitic league created at the end of the XIX th century), and member of the "Jeune légion", an armed wing of the Vichy regime. The link to the video: http://videos.tf1.fr/sept-a-huit/la-guerre-des-mondes-5898258.html.

xviii In his December 20 th , 2007 speech at the Lateran, Mr. Sarkozy created quite a scandal back in France, for saying that "teachers will never be able to replace the priest or the pastor" in the moral education of our children. The speech can be accessed here: http://www.elysee.fr/president/les-actualites/discours/2007/allocutionde-m-le-president-de-la-republique.7012.html?search=Latran.

  the "heavy metal controversies and counterculture" special issue edited by T. Hjelm, K. Kahn-Harris and M. Levine) "Hellfest: The Thing That Should Not Be? Local Perceptions and Catholic Discourses on Metal Culture in France" by Gérôme Guibert and Jedediah Sklower "Il ne faut pas prendre les enfants du Bon Dieu pour des canards sauvages." i "Cercle des Trois Provinces"

  or offences were barely visible, and the local population, although sometimes shocked by what they perceived as, in the dress codes and the music itself, aggressiveness, was surprised by the festival-goers' polite behaviour: "20.000 festival-goers with their strange way of dressing and their 'shrieking' music: the locals expected the worst. But finally, the Hellfest got almost unanimous support. The various Cassandras got nothing for their pains. […] The attitude, the costume, the music may seem provoking. The attitude isn't. 'They are extremely polite and respectful…' This is what all those who were in contact with them -the mayor and his deputies, municipal counselors, the police, rescue workers, shopkeepers and the population -said." (Ouest France, june 27 th , 2006, p. 6). Concerns about public safety or "morality" remained lowlevel, largely because the festival's team adopted a proactive attitude, overcoming the problems of organization, improving the reception conditions for festival-goers and being open to requests from Clisson inhabitants. Local economic agents also insisted that the festival keep on going, and by the fall of 2006, the second edition (Hellfest 2007) was authorized by the city council.

i"

  You mustn't imagine The Good Lord's children just dropped out of trees" ii Bill Hicks refers to the 1990 James Vance vs. Judas Priest trial. iii As can be seen in accounts by the local press (Ouest France, Hebdo Sèvre et Maine…). iv The album Christ Illusion 2006. American Recordings. B003CSCHUS. v

  For a synthesis of conservative catholic blogs and websites about the 2009 edition, see: Christ Roi blog. Synthèse des mobilisations contre le Hellfest et ses soutiens. http://christroi.over-blog.com/article-32838939.html x Among the latter is the site e-deo.typepad.fr, which explicitly refers to the "real country" (pays réel), a concept that refers once again to the ideology of Charles Maurras, see supra, n. 4. The site's tone is constantly xenophobic and islamophobic. /www.facebook.com/group.php?gid=95531469014 "Je suis chrétien et j'écoute du metal. Et ce n'est pas contradictoire". http://frfr.facebook.com/group.php?gid=22098979270.Leader of very influential death metal band Death, who died in December 2001 of collateral damage from his cancer treatment (pneumonia). During the years 2000 and 2001, Metal bands gave charity concerts, fans sent money to pay for his first surgery. find on his myspace blog the copy of a post in favor of the Swiss "anti-minaret" November 2009 vote. See Ibid. Le Benditisme a encore frappé.

	xvi	The	letter	can	be		downloaded	here:
	http://www.partichretiendemocrate.fr/images/stories/downloads/lettre%20a%20thoma
	s%20amstutz-pdg%20des%20brasseries%20kronenbourg.pdf
	xvii
	viii	See	Kaosguards.	Ben	Barbaud,	Organisateur	du	Hellfest.
	http://www.kaosguards.com/content/view/699/35/.
	xi	Soutenons			le					Hellfest !!!
	http://www.facebook.com/group.php?gid=92490879863
		Support			group:		Hellfest!		!
	http:/xii	The	petition	can	be		accessed	here:
	www.lepole.asso.fr/fichiers/file/petition%20Hellfest(3).pdf
	xiv	See	Padre	Bob	blog.	Qui	sont	les	vrais	satanistes?
	http://www.myspace.com/agedumetal/blog.

ix xiii xv One can