MICHAËL MIGNARD Ajinkya Kulkarni

Peter Schauenburg

A TOPOLOGICAL INVARIANT FOR MODULAR FUSION CATEGORIES

Keywords:

The modular data of a modular category C, consisting of the S-matrix and the T -matrix, is known to be an incomplete invariant of C. More generally, the invariants of framed links and knots defined by a modular category as part of a topological quantum field theory can be viewed as numerical invariants of the category. Among these invariants, we study the invariant defined by the Borromean link colored by three objects. Thus we obtain a tensor that we call B. We derive a formula for the Borromean tensor for the twisted Drinfeld doubles of finite groups. Along with T , it distinguishes the p non-equivalent modular categories of the form Z(Vec ω G ) for G the non-abelian group Z/qZ Z/pZ, which are not distinguished by the modular data.

Introduction

The modular data of a modular category C comprises the S-and T -matrices, two square matrices indexed by the isomorphism classes of simples; they define a projective representation of the modular group. On the one hand one could say that these two matrices are just particular instances of the topological invariants defined by a modular category in the framework of a topological quantum field theory: the S-matrix is the invariant defined for a Hopf link colored by two simples of the category, and the T -matrix contains the components of a kink. On the other hand, one may feel that the modular data is somewhat privileged among the topological invariants associated to the category: Invertibility of the S-matrix already features in the definition; invariance properties with respect to the modular group are key for the appearance of modular categories in conformal field theory; last but not least properties of the modular data are important for the purely algebraic study of modular categories. The importance of the modular data has led to the question being seriously considered (and stated as not quite a conjecture in [START_REF] Bruillard | Rank-finiteness for modular categories[END_REF]) as to whether a modular category (and hence the TQFT associated to it) is already determined fully by the modular data. This was refuted in [START_REF] Mignard | Modular categories are not determined by their modular data[END_REF] by a family of examples that are taken among the particularly accessible class of group-theoretical modular categories, more specifically the Drinfeld centers of pointed fusion categories, which were already considered, in the guise of representation categories of twisted Drinfeld doubles of finite groups, in [START_REF] Dijkgraaf | Quasi Hopf algebras, group cohomology and orbifold models[END_REF]. It turns out in fact that arbitrarily many inequivalent modular categories can give rise to the same modular data; the examples are defined by the same noncommutative group, endowed with different three-cocycles; the smallest example in [START_REF] Mignard | Modular categories are not determined by their modular data[END_REF] concerns the nonabelian group of order 55, although it is not known whether smaller examples exist.

This result naturally gives rise to the following question: Can one find other invariants that distinguish the modular categories in these families? Note that this was not how the categories were found to be distinct in [START_REF] Mignard | Modular categories are not determined by their modular data[END_REF], where rather the inexistence of suitable equivalences was proved through the characterization of such equivalences via Morita equivalence of pointed fusion categories. Recent general results on the correspondence between modular categories and topological quantum field theories [START_REF] Bartlett | Modular categories as representations of the 3-dimensional bordism 2category[END_REF] imply that the entire extended TQFT defined by the category can be viewed as a complete invariant. This does not, of course, solve the concrete problem of finding invariants that one can compute for specific categories and use to distinguish them -the entire TQFT is a rather formidable collection of data.

The simple idea of the present paper is to consider the invariant of a certain framed link defined by the modular categories in question and view it as an invariant of the category, much like the invariant of the Hopf link giving the S-matrix. The particular link we will use is known as the borromean rings. This is partly an obvious candidate for naive reasons: It is the closure of a three-strand braid, which is the next more complicated thing over the two-strand braid whose closure is the Hopf link; having three strands might allow the associativity constraint of the category (which, after all, is encoded in the three-cocycle that makes the basic difference in the aforementioned examples) to have a greater influence on the invariant. Since the invariant obtained from a full twist on three strands (like the Hopf link comes from a full twist on two strands) is easily seen to be determined by the modular data, making inverse braidings appear seems necessary, and the braid whose closure gives the borromean rings does this in a somewhat symmetric fashion. It may also be a good candidate for a slightly less naive reason: The borromean rings are three circles that are pairwise not linked, yet form a nontrivial link. This is a somewhat subtle topological phenomenon which one may hope gives rise to an invariant whose properties are not covered by those of the S-matrix, which records precisely what happens if two rings are linked. (In fact, the rings seem to have appeared in 15th century Italy as a heraldic symbol for this very reason: They are supposed to symbolize the political (and marital) alliances between the Borromeo, Sforza, and Visconti families, which was such that removing any one of them would have broken the alliance of the three.) Whether the motivations are justified by the success is perhaps doubtful: The borromean tensor does not at all distinguish the categories described above. In fact it does not seem to "see" the three-cocycle at all that makes the difference between the categories. It is only the T -matrix taken together with the B-tensor that makes it impossible to find a bijection between the simples of the different categories that would map these data to each other.

The same general idea of using link invariants to distinguish modular categories not distinguished by modular data was also pursued in [BDG + 18], where the authors show that the invariant of the Whitehead link, along with the T -matrix, does distinguish the five inequivalent modular categories defined from the nonabelian group of order 55. We are grateful to the authors for letting us see an advance copy of their preprint. At the time we knew by computer experiments that the invariant of the borromean rings, taken together with the modular data, also distinguishes the categories in this particular example, and we knew which components of the "borromean tensor" (given by the invariants of the borromean link with its three components colored by three simples of the category) are responsible for this success. We had not finished writing our findings, and we had not completed the results in section 6 showing that the T -matrix together with the borromean tensor is sufficient to distinguish the modular categories associated to the nonabelian groups of order pq (for all primes p, q for which such a group exists).

The paper is organized as follows: After introducing conventions and notations, we first revisit the modular data of twisted Drinfeld doubles to give a slightly improved formula for the S-matrix, but mostly to introduce the methods to be used later. We formally define the Borromean tensor in section 4 and record some symmetry properties it enjoys. In section 5 we give an explicit formula for the Borromean tensor for twisted Drinfeld doubles, with some useful specializations that we then use in section 6 to explicitly distinguish the inequivalent modular categories found in [START_REF] Mignard | Modular categories are not determined by their modular data[END_REF] by the new numerical invariant that is the T -matrix together with the B-tensor. An appendix gives some GAP codes for computing the B-tensor (and the S-matrix). Experimenting with computer calculation was an important step in our work, although computer help is not needed to prove the main result; some calculations were performed using HPC resources from PSIUN CCUB (Centre de Calcul de l'Université de Bourgogne).

Preliminaries

Throughout the paper we will consider modular categories, that is, braided spherical C-linear fusion categories C such that the square matrix S whose coefficients are the traces of the square of the braiding on pairs of simple objects is invertible. We refer to [BK01, ENO05a, EGNO15] for background. We will denote by (X i ) i∈I a set of representatives of the isomorphism classes of simple objects of C, and write i * ∈ I for the element such that X i * = X * i is the dual object. We will denote the pivotal trace in the category C of an endomoprhism f by ptr(f ).

One raison d'être of modular categories is that they allow the definition of a topological quantum field theory. In particular they define invariants in C of framed knots and links. We will freely use graphical notation for morphisms in a modular category C. The framed link invariant defined by a modular category can be viewed as follows: The link is the closure of a braid. The braid in question, colored by objects in C, defines an endomorphism of a tensor product of objects in C, and taking the closure of the braid corresponds to taking the (pivotal) trace of the endomorphism. To fix notations regarding this procedure, there is a representation of the braid group on n strands

R : B n → Aut C (. . . (V ⊗ V ) ⊗ V ) ⊗ V ) . . . ⊗ V )
on the tensor product of n copies of any object V ∈ C. In the case of a non-strict category (as indicated by the parentheses) this involves both instances of the braiding σ, and instances of the associator isomorphism Φ. We will also need to consider analogous morphisms defined on tensor products of distinct objects; informally we will write

R(β) : (. . . ((V 1 ⊗ V 2 ) ⊗ V 3 ) . . . ⊗ V n ) → (. . . ((V β -1 (1) ⊗ V β -1 (2) ) ⊗ V β -1 (3) ) . . . ⊗ V β -1 (n) )
for β ∈ B n and V 1 , . . . , V n ∈ C, where β also denotes the underlying permutation of β. We note that R(ββ ) = R(β)R(β ) in the obvious sense for two braids β, β .

The modular categories in which we will do extensive calculations are the Drinfeld centers of pointed fusion categories; an alternative description of these is as module categories of twisted Drinfeld doubles of finite groups [START_REF] Dijkgraaf | Quasi Hopf algebras, group cohomology and orbifold models[END_REF], although these quasi-Hopf algebras will play no explicit role in this paper. We need to fix notations and collect a few useful identities.

We will write g h = ghg -1 for the action of a group on itself by conjugation, C G (g) for the centralizer of g in G, and g G or g for the conjugacy class of g ∈ G. Any pointed fusion category is of the form Vec ω G , the category of finite-dimensional G-graded vector spaces with associativity constraint given by

Φ : (U ⊗ V ) ⊗ W -→ U ⊗ (V ⊗ W ) (u ⊗ v) ⊗ w -→ ω(|u|, |v|, |w|)u ⊗ (v ⊗ w) for U, V, W ∈ Vec ω
G and homogeneous elements u ∈ U, v ∈ V, w ∈ W , where |u| is our notation for the degree of the homogeneous element u, and ω : G 3 → C × is a three-cocycle. In the sequel, we will always tacitly assume that elements of graded vector spaces are homogeneous in writing such formulas.

The category Vec ω G , and by extension its Drinfeld center below, is spherical with respect to the canonical pivotal structure characterized by the property that pivotal dimensions coincide with the usual vector space dimensions. We will not explicitly need the pivotal structure, but only the fact that pivotal traces of endomorphisms are simply the usual traces of the underlying linear maps.

The (right) Drinfeld center Z(V ec ω G ) is a modular category. The structure of an object (W, σ •,W ) in the center, with σ V,W : V ⊗ W → W ⊗ V the half-braiding for V ∈ Vec ω G can be described in terms of an action (not quite a group action) of G on W [START_REF] Majid | Quantum double for quasi-Hopf algebras[END_REF]. More precisely, giving a half-braiding is equivalent to giving a map : G ⊗ W → W subject to the conditions

|g w| = g |w| (2.1) e w = w (2.2) g h w = α |w| (g, h)gh w (2.3)
for g, h ∈ G and w ∈ W , the equivalence being described by the formula

V ⊗ W v ⊗ w → |v| w ⊗ v ∈ W ⊗ V. Let V ∈ Z(Vec ω G ).
Since acting by an element g ∈ G is a vector space automorphism of V ∈ Vec ω G which conjugates degrees, any object decomposes as the direct sum of objects where the degrees of nonzero homogeneous components form a conjugacy class. Assume that the degrees of the nonzero components of V form a conjugacy class. Then G permutes those homogeneous components transitively, and elements in the centralizer C G (g) map the homogeneous component V g to itself.

In particular, V g is an α g -projective representation of C G (g) where (2.4) α g (x, y) = ω(x, y, g)ω -1 (x, y g, y)ω(xy g, x, y)

and the structure of V is determined by this projective representation for any one g in the conjugacy class. In particular, simple objects of Z(Vec ω G ) are parametrized by pairs (g, χ) where g runs through a system of representatives for the conjugacy classes of G, and χ is an irreducible α g -projective character of C G (g).

It is convenient to note how to obtain the C G (x)-projective character χ describing the action of C G (x) on V x when x belongs to the same conjugacy class, say x = f g. So let c ∈ C G (x) and v ∈ V g . We have

c (f v) = α g (c, f )cf v (2.5) f ((f -1 c) v) = α g (f, f -1 c)cf v (2.6) and therefore c f v = α g (c, f )α -1 g (f, f -1 c)f (f -1 c) v. This means that the diagram V g f / / (f -1 c) V x c V g f / / V x commutes up to the scalar factor α g (c, f )α -1 g (f, f -1 c).
By cyclicity of the trace, the projective character of the projective C G (x)-representation V x is therefore χ x , given by (2.7)

χ x := (f χ)(c) := α g (c, f )α -1 g (f, f -1 c)χ(f -1 c).
In particular this expression does define a projective character, and does not depend on the choice of f ∈ G with f g = x.

The inverse of the braiding in

Z(Vec ω G ) is given by σ -1 (w ⊗ v) = v ⊗ |v| -1 w, where : CG ⊗ V → V is such that g g -1 v = g -1 g v = v. From f -1 (f v) = α |v| (f -1 , f )v, f f -1 v = α |v| (f, f -1 )v one reads off f -1 v = α -1 |v| (f, f -1 )f -1 v, (2.8) f -1 v = α -1 f |v| (f -1 , f )f -1 v, (2.9)
respectively.

The modular data of Z(Vec ω

G ) It is of course well-known how to compute the modular data of the twisted Drinfeld double of a finite group [START_REF] Coste | Finite group modular data[END_REF]. In particular the T -matrix is given by

(3.1) T (g,χ) = Θ(g, χ) = χ(g) χ(1) .
We will rederive a formula for the S-matrix with only a slight advantage: The formula from [CGR00] involves a double sum, over two conjugacy classes, or twice over the group. Our formula has only one sum. The S-matrix is the trace of a braid on two strands (whence the two sums, related to the two objects coloring the strands); generally, the invariant obtained from taking the trace of a braid on n strands would involve n summations, over the conjugacy classes associated to the objects, but one can get away with only n -1 summations by a simple trick based on a well-known fact.

In the graphical calculus, taking the trace of the image of a braid in a pivotal monoidal category amounts to closing the braid. Obviously, one can choose to close all strands but one, which leaves us with an endomorphism with the object labelling the remaining strand, and then take the trace of that endomorphism. More formally:

Remark 3.1. Let V, W ∈ C and f : V ⊗ W → V ⊗ W . Then ptr(f ) = ptr(ptr V (f )), where (3.2) ptr V (f ) = W ¨f © W is a partial (pivotal) trace. If W is simple, then ptr V (f ) = λ • id W is a scalar, and ptr(f ) = λ dim(W ).
Working in the category Z(Vec ω G ), where formulas for the traces of braids involve sums over all the combinations of G-degrees of each object (subject to some condition), this will allow us to get away with one less sum (or, when coding the formulas, one less nested loop):

Remark 3.2. Let V, W ∈ Z(Vec ω G )
with W the simple object corresponding to (g, χ), and let f :

V ⊗ W → V ⊗ W . Then tr V (f ) = λ id; the scalar λ is determined by the component tr V (f )| Wg : W g → W g of tr V (f ) by λ dim W g = tr(tr V (f )| Wg ), and thus tr(f ) = |g| tr(tr V (f )| Wg )
As an illustration and warm-up for the calculations in section 5 we will consider the S-matrix for two simple objects V, W ∈ Z(Vec ω G ), corresponding to the pairs (g, χ 1 ) and (h, χ 2 ). We need to compute

S (g,χ 1 ),(h,χ 2 ) = tr(σ W V σ V W ) = tr(σ 2 ) = tr(R(σ 2 )),
where (no parentheses being necessary on two objects) there is no difference between the representation R of the braid group B 2 on one generator σ and simply instances of the braiding of the category Z(Vec ω G ).

If we write V = ⊕ x∈g V x and W = ⊕ x∈h W y , then for v ∈ V x and w ∈ W y we have σ 2 (v ⊗ w) = σ(x w ⊗ v) = |x w| v ⊗ x w = (x y) v ⊗ x w.
We can endow V ⊗W with a G×G-grading composed of the G-gradings of V and W . Then

deg G×G σ 2 (v ⊗ w) = ((x y) x, x y) for x = |v|, y = |w|.
For a finite group Γ, a Γ-graded vector space E, and an endomorphism f of E let f 0 be trivial component of f with respect to the Γ-grading of End(E). Then tr(f ) = tr(f 0 ).

In our example, considering the G × G-grading of V ⊗ W , we see that σ 2 (v ⊗ w) has the same degree as v ⊗ w if and only if x and y commute.

(3.3) (σ 2 ) 0 (v ⊗ w) = x v ⊗ y w [x, y] = 1 0 [x, y] = 1
In particular

S V,W = tr(σ 2 ) = tr((σ 2 ) 0 ) = x∈g y∈h [x,y]=e χ x 1 (y)χ y 2 (x)
Using remark 3.2 we can replace the double sum by a single sum; also, we can use (eq. (2.7)):

S (g,χ 1 ),(h,χ 2 ) = |h| [x,h]=1 x∈g χ x 1 (h)χ 2 (x) = |h| [x,h]=1 x∈g α g (c, p)α -1 g (p, p -1 c)χ 1 (p -1 c)χ 2 (x)
where p stands for any group element satisfying p g = x. Alternatively, we can use the bijection G/C G (g) → g G given by aC G (g) → a g to rewrite

S (g,χ 1 ),(h,χ 2 ) = |h| |C G (g)| [p g,h]=1 p∈G α g (h, p)α -1 g (p, p -1 b)χ 1 (p -1 b)χ 2 (p g) = |h| [p g,h]=1 p∈G/C G (g) α g (h, p)α -1 g (p, p -1 b)χ 1 (p -1 b)χ 2 (p g)
As mentioned, this formula is (up to conventions) quite like the formula in [START_REF] Coste | Finite group modular data[END_REF], except for two details: We have a single sum over one conjugacy class instead of a double sum, and we have half the cocycle ("α") terms due to the fact that we need to use (eq. (2.7)) on only one of the two objects.

The Borromean tensor

A modular category (in fact any spherical braided fusion category) defines a numerical invariant of framed knots and links which can be written as the pivotal trace of the image in the category of a braid whose closure is the link, with its components colored by simple objects of the category. Read differently, each fixed framed link defines a numerical invariant of modular categories in this fashion. More precisely, the invariant is then indexed by as many simple objects as the link has components.

Among this infinite supply of numerical invariants (among which the S-matrix and, up to a dimension factor, the T -matrix can also be found) we pick one example, for the heuristic (and art historical) reasons cited in the introduction: Definition 4.1. The borromean tensor (or B-tensor) of a modular category with simples (X i ) i∈I is the family (4.1)

B ijk := ptr(B((σ -1 2 σ 1 ) 3 ) where B((σ -1 2 σ 1 ) 3 ) ∈ Aut C ((X i ⊗ X j ) ⊗ X k ). Graphically B ijk = ptr          i j k i j k          = i ¨j k ©
(In the graphical representation, we let i stand for X i .)

Lemma 4.2. The following equalities hold:

(1)

B ijk = B jki = B kij (2) B ijk = B jik * (3) B ijk = B kji if C statisfies the F-property (see [NR11]).
Proof. Clearly cyclicity of the trace implies that the B-tensor is invariant with respect to cyclic permutations of its three indices. We need to show the other symmetry properties:

Conjugating with shows that

(4.2) tr          i j k i j k          = tr          k j i k j i         
Furthermore, we have

j i k i j © = j i k © i j = ¨j i k © i j and thus tr          i j k i j k          = tr          i j k i j ©          = tr          i j k © i j          = tr          k * i j k * i j         
Combining with (4.2) we see that B ijk = B jik * . Together with the cyclic permutation invariance, this yields that B is invariant under any permutation of its indices combined with dualizing an even or odd number of its indices according to the parity of the permutation. If the borromean braid has finite order in the category in question (as is the case for group-theoretical modular categories, see [reference]), then B ijk is also the complex conjugate of the trace of the inverse Borromean braid. But the right hand side of (4.2) is that trace, so B ijk = B kji . So in this case B is invariant under permutation and dualization of its indices, up to conjugation if the number of dualized indices has the opposite parity of the permutation.

For larger rank categories, these symmetry properties could serve to speed up the computation of the borromean tensor, although, truth be told, we have so far only used them to debug our code.

The borromean tensor of a twisted double

In this section we will derive an explicit formula for the borromean tensor in the Drinfeld center of a pointed fusion category, in terms of the group, the cohomological data, and the projective characters parametrizing the simple objects. It should be noted that in principle it is known how to obtain such formulas for the topological invariants defined by braided monoidal categories. Nevertheless it is a rather tedious undertaking to provide them in complete detail.

Consider three simple objects U, V, W ∈ Z(V ec ω G ), parametrized by couples (g, χ 1 ), (h, χ 2 ) and (k,

χ 3 ). Take u ∈ U x , v ∈ V y , w ∈ W z , where x ∈ g, y ∈ h, z ∈ k.
Looking at the G 3 -degree of tensors in (U ⊗ V ) ⊗ W (which is not affected by associativity isomorphisms), we see that for

u ∈ U x , v ∈ V y , w ∈ W z we have deg G 3 (R(σ -1 2 σ 1 ))(u ⊗ v ⊗ w) = P (x,
y, z) if we define P : G 3 → G 3 by P (x, y, z) = (x y, z, z -1 x). Note P -1 (x, y, z) = (y z, y z -1 x, y). Now in order that ((σ -1 2 σ 1 ) 3 ) 0 (u⊗v⊗w) = 0, we need to have P 3 (x, y, z) = (x, y, z), or equivalently P 2 (x, y, z) = P -1 (x, y, z).

Comparing

P 2 (x, y, z) = P (x y, z, z -1 x) = ((x y) z, z -1 x, (z -1 x -1 ) x y) = ((x y) z, z -1 x, [z -1 , x -1 ] y) P -1 (x, y, z) = (y z, y z -1 x, y) we see that:

((σ -1 2 σ 1 ) 3 ) 0 | Ux⊗Vy⊗Wz = 0 ⇔      (x y) z = y z z -1 x = y z -1 x [z -1 , x -1 ] y = y ⇔      [[y -1 , x], z] = 1 [[z, y], x] = 1 [[z -1 , x -1 ], y] = 1 (5.1)
We evaluate the morphism R((σ -1 2 σ 1 ) 3 ) in three steps.

R(σ -1 2 σ 1 )((u ⊗ v) ⊗ w) : = Φ(V ⊗ σ -1 )Φ -1 (σ ⊗ W )((u ⊗ v) ⊗ w) = Φ(V ⊗ σ -1 )Φ -1 ((x v ⊗ u) ⊗ w) = Φ(V ⊗ σ -1 )(ω(x y, x, z)(x v ⊗ (u ⊗ w)) = Φ(ω(x y, x, z)(x v ⊗ (w ⊗ z -1 u) = ω -1 (x y, z, z -1 x)ω(x y, x, z)(x v ⊗ w) ⊗ z -1 u = ψ(x, z -1 x, x y, z)Ψ((u ⊗ v) ⊗ w) with ψ(x, x , y, z) = ω -1 (y, z, x )ω(y, x, z)α -1 x (z, z -1 ) = ω -1 (y, z, x )ω(y, x, z)α -1 x (z -1 , z) Ψ(u ⊗ v ⊗ w) = (|u| v ⊗ w) ⊗ |w| -1 u Further R(σ -1 2 σ 1 )((x v ⊗ w) ⊗ z -1 u) = ψ(x y, (z -1 x) -1 (x y), (x y) z, z -1 x)Ψ((x v ⊗ w) ⊗ z -1 u) = ψ(x y, y, y z, z -1 x)Ψ((x v ⊗ w) ⊗ z -1 u) where Ψ((x v ⊗ w) ⊗ z -1 u) = α((z -1 x) -1 , x)((x y) w ⊗ z -1 u) ⊗ [z -1 , x -1 ] v ∈ W (x y) z ⊗ U z -1 x ⊗ V [z -1 ,x -1 ] y = W y z ⊗ U z -1 x ⊗ V y .
Further,

R(σ -1 2 σ 1 )(((x y) w ⊗ z -1 u) ⊗ [z -1 , x -1 ] v) = ψ(y z, y -1 (y z), (y z) (z -1 x), y)Ψ((x y) w⊗z -1 u⊗[z -1 , x -1 ] v) = ψ(y z, z, x, y)Ψ((x y) w ⊗ z -1 z ⊗ [z -1 , x -1 ] v) Ψ((x y) w ⊗ z -1 z ⊗ [z -1 , x -1 ] v) = α x (y z, z -1 )α z (y, x y)ψ(y z, z, x, y)([y, z] u⊗[z -1 , x -1 ] v⊗[y, x] w. Thus R((σ -1 2 σ 1 ) 3 ((u ⊗ v) ⊗ w) = Ω(x, y, z)[y, z] u ⊗ [z -1 , x -1 ] v ⊗ [y, x] w

with

(5.2) Ω(x, y, z) = ψ(x, z -1 x, x y, z)ψ(x y, y, y z, z -1 x)ψ(y z, z, x, y)

= ω(x y, z, z -1 x)ω -1 (x y, x, z)α -1 x (z, z -1 ) ω(y z, z -1 x, y)ω -1 (y z, x y, z -1 x)α -1 y (z -1 x -1 , z -1 x) ω(x, y, z)ω -1 (x, y z, y)α z (y -1 , y)
We conclude that

B (g,χ 1 ),(h,χ 2 ),(k,χ 3 ) = tr(R((σ -1 2 σ 1 ) 3 )) = tr(R((σ -1 2 σ 1 ) 3 ) 0 ) = x∈g,y∈h,z∈k (eq. (5.1)) Ω(x, y, z)χ x 1 ([y, z])χ y 2 ([z -1 , x -1 ])χ z 3 ([y, x]).
Using remark 3.2, we can reduce the three summations in the preceding formula to two.

B (g,χ 1 ),(h,χ 2 ),(k,χ 3 ) = |k| x∈g,y∈h (eq. (5.3)) Ω(x, y, k)χ x 1 ([y, k])χ y 2 ([k -1 , x -1 ])χ 3 ([y, x]) = |k| x∈g,y∈h (eq. (5.3)) Ω(x, y, k)α g ([y, k], p)α -1 g (p, p -1 [y, k]) α h ([k -1 , x -1 ], q)α -1 h (q, q -1 [k -1 , x -1 ]) χ x 1 ([y, k])χ y 2 ([k -1 , x -1 ])χ 3 ([y, x]). with (5.3) [[k, y], x] = 1 [[y -1 , x], k] = 1
Finally, we can express the characters χ x 1 , χ y 2 in terms of χ 1 , χ 2 using (eq. (2.7)):

B (g,χ 1 ),(h,χ 2 ),(k,χ 3 ) = |k| p∈G/C G (g) q∈G/C G (g) (eq. (5.6))
Ω(p g, q h, k)(p χ 1 )([q h, k])

(q χ 2 )([k -1 , p g -1 ])χ 3 ([q h, p g]) (5.4) = |g||h||k| |G| 2 p∈G q∈G (eq. (5.6)) Ω(p g, q h, k)(p χ 1 )([q h, k]) (q χ 2 )([k -1 , p g -1 ])χ 3 ([q h, p g]) (5.5) with (5.6) [[k, q h], p g] = 1 [[(q h) -1 , p x], k] = 1.
Besides the ω and α terms already hiding in Ω, the conjugated characters in the last formulae are hiding further α terms from (eq. (2.7)):

(p χ 1 )([q h, k]) = α g ([q h, k], p)α -1 g (p, p -1 [q h, k]) •χ 1 (p -1 [q h, k]) (q χ 2 )([k -1 , p g -1 ]) = α h ([k -1 , p g -1 ], q)α -1 h (q, q -1 [k -1 , p g -1 ]) •χ 2 (q -1 [k -1 , p g -1 ])
We have implemented the general formula for the B-tensor above in GAP; the codes are in appendix A. For explicit calculations by humans, the abundance of cocycle terms (six ω terms and three α terms gathered in Ω plus four α terms hiding in conjugated projective characters) and the tedious commutation conditions on group elements certainly make the formulas somewhat unwieldy. We will now describe particular circumstances where these problems do not occur and the formula simplifies drastically. The special cases will be very useful for the key example we will treat in the following section.

Proposition 5.1. Suppose there is an abelian normal subgroup A G such that ω is inflated from the quotient G/A , and g, h ∈ A. Then

(5.7) B (g,χ 1 ),(h,χ 2 ),(k,χ 3 ) = |k| • x∈g y∈h χ 1 (p -1 [y, k])χ 2 (q -1 [k -1 , x -1 ]).
where p g = x, q h = y in the sum. Note also that χ 1 , χ 2 are ordinary characters in this case.

Proof. The conditions are tailored to ensure that Ω(x, y, z) = 1 in 5.2, since all values of ω where one argument is conjugate to g or h are trivial. The same holds for the α terms used in (eq. (2.7)), since commutators with one element from A also lie in A. Also, [[k, q h], p g] = 1 for all q, p since q h ∈ A, hence [k, q h] ∈ A, and p g ∈ A.

Finally [q h -1 , p g] = 1 since q h, p g ∈ A which is abelian, and in particular

[[q h -1 , p g], k] = 1.
Corollary 5.2. Assume the hypotheses of the preceding corollary, and in addition that there is a subgroup Q ⊂ C G (k) such that g Q = g and h Q = h. This applies for example when G = A Q is a semidirect product of abelian groups. Then (5.8)

B (g,χ 1 ),(h,χ 2 ),(k,χ 3 ) = |k||A| |C Q (g)||C Q (h)| • q∈Q χ 2 (q [h, k])χ 1 (q -1 [k -1 , g -1 ]).
Proof. We have bijections Q/C Q (g) p → p g ∈ g and Q/C Q (h) q → q h ∈ h, and therefore, abbreviating

N = |C Q (g)||C Q (h)|, B (g,χ 1 ),(h,χ 2 ),(k,χ 3 ) = |k| N • p,q∈Q χ 1 (p -1 [q h, k])χ 2 (q -1 [k -1 , p g -1 ]) = |k| N • p,q∈Q χ 1 (p -1 q [h, q -1 k])χ 2 (q -1 p [p -1 k -1 , g -1 ]) = |k| N • p,q∈Q χ 1 (p -1 q [h, k])χ 2 (q -1 p [k -1 , g -1 ])
which gives the desired result after reparametrization.

Twisted doubles of nonabelian groups of order pq

Let p, q be odd primes with p|q -1. There is a unique nonabelian group of order pq, and there are exactly p inequivalent twisted doubles of that group; see [START_REF] Mignard | Modular categories are not determined by their modular data[END_REF] and below. However, these p inequivalent modular categories only afford three different sets of modular data. In this section we will show that the T -matrix and the borromean tensor do distinguish the p modular categories. We first tested this for the case p = 5 and q = 11 using our GAP-implementation of (eq. (5.5)). That is, we computed the values of T -matrix, S-matrix, and B-tensor in this case, and verified that no bijection between the simples of two distinct categories maps all three data to each other. Closer inspection of the experimental data also helped us pick out the particular simples to use in our borromean tensor calculations below. Thus, although no computer help is necessary in the end to prove our results, machine calculations were instrumental in our finding them. Note that the Smatrix turns out not to be necessary in our example in the end; the T -matrix and B-tensor suffice.

The nonabelian group of order pq where p and q are odd primes such that p|q -1 has the following presentation:

Z/qZ Z/pZ ∼ = a, b|a q = b p = 1, bab -1 = a n
The integer n ∈ Z/qZ must be chosen such that n ≡ 1 mod q and n p ≡ 1 mod q, but the group does not depend on that choice. We note

b k a l b -k = a n k l [a l , b k ] = a l(1-n k ) [b k , a l ] = a l(n k -1) (6.1)
The canonical surjection Z/qZ Z/pZ → b ∼ = Z/pZ induces an isomorphism between the cohomology groups H 3 ( b , C × ) → H 3 (Z/qZ Z/pZ, C × ), where H 3 ( b , C × ) ∼ = Z/pZ is generated by the following cocycle ω:

ω(b i , b j , b k ) := exp 2iπ p 2 ([i]([j] + [k] -[j + k])
where

[i] ∈ {0, . . . , p -1} is such that [i] ≡ i mod p.
The following is a complete list of representatives for the isomorphism classes of simples of Z(Vec ω u G ): (1) (1, χ) where χ is an irreducible character of G, (2) (a l , χ s q ) where l ∈ (Z/qZ) × / n , s ∈ Z/qZ, and χ q is the generator of a ∼ = Z/qZ given by That is χ r p = χ r p µ u b k where α u b k = dµ u b k . In the sequel, we will write the simple as (b k , χ r p ) instead of (b k , χ r p ). For simplicity, we will refer to these as simples of type one, type two or type three.

χ q (a) = exp 2iπ q , (3)
Lemma 6.1. The T -matrix of Z(Vec ω u G ) is given by the following: Proof. For simples in Z(Vec ω u G ) of the first type, it is obvious that the corresponding twist Θ(1, χ) = χ(1) χ(1) = 1. For simples of the second type (a l , χ s q ), one has α u a l = 1, and then the irreducible projective characters of the centralizer a ∼ = Z/qZ of a l are the usual irreducible characters.

(1) Θ(1, χ) = 1 (2) Θ(a l , χ s q ) = exp 2iπ q sl (3) Θ(b k , χ r p ) = exp 2iπ p 2 (pkr + k 2 u) ,
The twist is therefore given by Θ(a l , χ r q ) = χ s q (a l ) χ s q (1) = exp 2iπ q sl

Finally, for simples of the last type (b k , χ r p ), one has

α u b k = dµ u b k where µ u b k (x) = exp 2iπu p 2 k[Π(x)]
and α u b k -projective characters of the centralizer b ∼ = Z/qZ of b k are usual irreducible characters twisted by µ u b k . Therefore:

Θ(b k , χ r p ) = χ r q (b k )µ u b k (b k ) χ r q (1)µ u b k (1) = exp 2iπ p 2 (pkr + k 2 u)
Lemma 6.2. The B-tensor of the category Z(Vec ω u Z/qZ Z/pZ ) with p and q odd primes such that q|p -1 and u ∈ {0, . . . p -1} satisfies

(6.2) B (a l ,χ s q ),(a l ,χ s q ),(b k ,χ r p ) = pq p-1 m=0 e ( 2iπsl q (n -t -n t )(n m -n -m )) ; 2t ≡ k(p)
Proof. We apply corollary 5.2 with Q = b and A = a . By eq. (5.8) and eq. (6.1) we have

B (a l ,χ s q ),(a l ,χ s q ),(b k ,χ r p ) = pq p-1 m=0 χ s q (b m [a l , b k ])χ s q (b -m [b -k , a -l ]) = pq p-1 m=0 χ s q (a l•n m (1-n k ) )χ s q (a -l•n -m (n -k -1) ) = pq p-1 m=0 e ( 2iπsl q (n m (1-n k )+n -m (1-n -k )) .
For 2t ≡ k(p) we get

n m (1 -n k ) + n -m (1 -n -k ) ≡ n m (1 -n 2t ) + n -m (1 -n -2t ) = (n m+t -n -(m+t) )(n -t -n t )
so reparametrization gives the desired expression.

In [START_REF] Mignard | Modular categories are not determined by their modular data[END_REF] it was shown that the p non-equivalent modular tensor categories Z(Vec ω u Z/qZ Z/pZ ) for u = 0, .., p -1, are not distinguished by their modular data. In fact there are only three different modular data between these categories. As we will see shortly, this is changed when we add the B-tensor to the data.

Table 1. p = 5, q = 11, n = 4 k t β ls (k) 1 3 1 + ζ 4 + ζ 6 + ζ 5 + ζ 7 2 1 1 + ζ + ζ 7 + ζ 4 + ζ 10 Table 2. p = 5, q = 31, n = 2 k t β ls (k) 1 3 1 + ζ 6 + ζ 15 + ζ 16 + ζ 25 2 1 1 + ζ 10 + ζ 25 + ζ 6 + ζ 21 Table 3. p = 7, q = 29, n = 7 k t β ls (k) 1 3 1 + ζ 4 + ζ 11 + ζ + ζ 28 + ζ 25 + ζ 18 2 1 1 + ζ 24 + ζ 14 + ζ 18 + ζ 11 + ζ 15 + ζ 5 3 4 1 + ζ 15 + ζ 4 + ζ 16 + ζ 25 + ζ 14 + ζ 13
The fact that the B-tensor should help may seem surprising given that the expression (6.2) does not depend on u at all. At least in the case p = 5, q = 11 this is not only true for the particular coefficients of the B-tensor that we calculated above. If we label simple objects by χ, resp. (l, s), resp. (k, r) as above, then the entire B-tensor is independent of u, as we found by computer calculation. However, in this labelling, the T -matrices do depend on u, and for different u we cannot relabel so that both B and T agree. We will inspect this closer for some low order examples.

In Tables 1, 2 and 3, we have listed, in the cases (p, q, n) = (5, 11, 4), (5, 31, 2), (7, 29, 7), the rescaled B-tensor values

β ls (k) := 1 pq B (a l ,χ s q ),(a l ,χ s q ),(b k ,χ r p )
for a fixed value of the product ls (they do not depend on r, and only half are listed since β ls (p -k) = β ls (k)). We have set ζ = exp 2πisl q , which is a primitive q-th root of unity if ls ≡ 0 mod q.

We see that in the examples (and, it will turn out below, in general) the value of k 2 is determined by the entry of the B-tensor. A bijection between simples of categories for different values of u that preserves the T -matrix would have to fix ls, and it would need to nontrivially permute the values of k to compensate the difference in u, a contradiction. Details are in the proof of the following Theorem 6.3. The T -matrix and B-tensor form a complete set of invariants for the p non-equivalent modular categories Z(Vec ω u Z/qZ Z/pZ ) where p and q are odd primes such that p|q -1. More precisely, if there is a map κ from the simple objects of Z(Vec ω u Z/qZ Z/pZ ) to the simple objects of Z(Vec ω u Z/qZ Z/pZ ) satisfying T κ(V ) = T V and B κ(U ),κ(V ),κ(W ) = B U V W for all simples U, V, W of the former, then u = u .

Proof. Let κ be such a map. We will use the notations (g, χ) u and (g, χ) u to denote simple objects of the two categories under consideration. The category corresponding to the trivial cocycle is easily distinguished from the others by the T -matrix alone, so we can assume u, u = 0. Let ls ≡ 0 mod q. Then it is obvious from lemma 6.1 that κ((a l , χ s q ) u ) = (a l , χ s q ) u with sl ≡ s l mod q. Also, part (4) of 6.1 implies that κ((b k , χ r p ) u ) = (b k , χ r p ) u for some k and r with k 2 u ≡ k 2 u mod p.

Next,

B (a l ,χ s q )u,(a l ,χ s q )u,(b k ,χ r p )u = B κ((a l ,χ s q )u),κ((a l ,χ s q )u),κ((b k ,χ r p ))
= B (a l ,χ s q ) u ,(a l ,χ s q ) u ,(b k ,χ r p ) u So, with lemma 6.2 and 2t ≡ k mod p, 2t ≡ k mod p, we get (6.3)

p-1 m=0 e 2iπsl q (n t -n -t )(n m -n -m ) = p-1 m=0 e 2iπs l q (n t -n -t )(n m -n -m )
.

Since this is a Q-linear relation between fewer than q powers of the same primitive q-th root of unity e 2iπsl q = e 2iπs l q

, we conclude that the set

M t := {(n t -n -t )(n m -n -m )|m = 0, . . . , p -1} ⊂ Z/qZ
is equal to the analogous set M t . We note that the p elements n m -n -m are distinct: Indeed, assume n m -n -m = n j -n -j for 0 ≤ m, j ≤ p -1. Then

0 = n m -n j + n -j -n -m = (n -j-m + 1)(n m -n j ).
Now n -j-m + 1 = 0 since n has odd order, and so n m = n j which implies m = j. In particular

x∈Mt x 2 = p-1 m=0 (n t -n -t ) 2 (n 2m + n -2m -2) = (n t -n -t ) 2 p-1 m=0 n 2m + p-1 m=0 n -2m -2p = -2p(n t -n -t ) 2 ,
since n 2 and n -2 are primitive p-th roots of unity in Z/qZ and so the sum over all their powers gives zero. By the same reasoning

x∈Mt x 2 = x∈M t x 2 = -2p(n t -n -t ) 2
Thus (n t -n -t ) 2 = (n t -n -t ) 2 , which implies n t -n -t = n t -n -t or n t -n -t = n -t -n t . As we have seen, this implies t ≡ t or t ≡ -t in Z/pZ. Therefore k 2 = k 2 and we can conclude that u = u . Remark 6.4. There is an action of the absolute Galois group of abelian extensions of the rationals Γ := Gal(Q ab /Q) on the set of simples of any integral modular category; see [START_REF] Etingof | On fusion categories[END_REF]Appendix]. In the case of Z(Vec ω G ) it satisfies S γ(i),γ(j) = γ 2 (B i,j ) for any γ ∈ Γ, and also T γ(i),γ(i) = γ 2 (T ii ) as shown in [START_REF] Dong | Congruence property in conformal field theory[END_REF]. If we analyze the proof in [START_REF] Mignard | Modular categories are not determined by their modular data[END_REF] that the twisted doubles of nonabelian groups of order pq share only three different sets of modular data, we can conclude from our result that the analogous property B γ(i),γ(j),γ(k) = γ 2 (B ijk ) is not satisfied.

Appendix A. GAP codes

We give in this appendix the codes that we used to compute the Smatrix and the Borromean tensor for the categories Z(Vec ω G ). Preliminary codes that compute complex valued group cohomology, projective characters of finite groups, etc., as well as the code that computes the T -matrix, are the ones of [START_REF] Mignard | Morita equivalence of pointed fusion categories of small rank[END_REF]. The function ZwG_S computes the S-matrix and the function ZwG_B computes the Borromean tensor; both those functions are taking as arguments a finite group G, a 3-cocycle ω ∈∈ H 3 (G, C × ), the simple objects of Z(Vec ω G ) and a non-negative integer e. More precisely, ω is given as its list of values in Z/eZ, where e is the exponent of H 3 (G, C × ) and the simple objects are couples (g, χ) where g ∈ G and χ is a projective character given by its list of values

  (b k , χ r p ) where k ∈ (Z/pZ) × , r ∈ Z/pZ, and χ r p is the α u b kprojective character of C G (b k ) = b associated to χ r p , χ p being the generator of b ∼ = Z/pZ given by χ p (b) = exp 2iπ p .

  and in particular (4) Θ(b k , χ r p ) p = ζ k 2 u p for ζ p = exp( 2iπ p ).

  bp_inv := posG ( listG [ bp ]^-1); c_inv := posG ( listG [ c ]^-1); cinv_hit_ap := posG ( Conjugation ( listG [ c_inv ] , listG [ ap ])); ap_hit_bp := posG ( Conjugation ( listG [ ap ] , listG [ bp ])); bp_hit_c := posG ( Conjugation ( listG [ bp ] , listG [ c ])); cinv_hit_apinv := posG ( Conjugation ( listG [ c_inv ] , listG [ ap_inv ])); commm_cinv_apinv := posG ( Commm ( listG [ c_inv ] , listG [ ap_inv ])); hinv_hit_commca := posG ( Conjugation ( listG [ h ]^-1 , listG [ commm_cinv_apinv ])); commm_bp_c := posG ( Commm ( listG [ bp ] , listG [ c ])); ginv_hit_commmbc := posG ( Conjugation ( listG [ g ]^-1 , listG [ commm_bp_c ])); commm_bpinv_ap := posG ( Commm ( listG [ bp_inv ] , listG [ ap ])); if not ( Commm ( Commm ( listG [ bp_inv ] , listG [ ap ]) , listG [ c ]) = One ( G ) and Commm ( Commm ( listG [ bp ] , listG [ c ]) , listG [ ap ]) = One ( G ) ) then continue ; else sum := sum + E ( e ) ^( cocyclevalues [ ap_hit_bp ][ ap ][ c ] -cocyclevalues [ ap_hit_bp ][ c ][ cinv_hit_ap ] + cocyclevalues [ bp_hit_c ][ ap_hit_bp ] [ cinv_hit_ap ] -cocyclevalues [ bp_hit_c ][ cinv_hit_ap ][ bp ] + cocyclevalues [ ap ][ bp_hit_c ][ bp ] -cocyclevalues [ ap ][ bp ][ c ]-alphag ( ap ) ( c , c_inv ) + alphag ( ap ) ( bp_hit_c , c_inv ) -alphag ( ap_hit_bp ) ( cinv_hit_ap , cinv_hit_apinv )Email address: mignard@math.cnrs.frEmail address: peter.schauenburg@u-bourgogne.fr Institut de Mathématiques de Bourgogne, UMR 5584 CNRS, Université Bourgogne Franche-Comté, F-21000 Dijon, France

(in C) on the centralizer C G (g). Finally, checking whether one or more matrices or "tensors" indexed by a power of the same index set are identical up to a permutation of the index set (i. e. simultaneous permutations of the matrix or tensor indices) is in itself a tricky task. We include a function that does this for T , S and B (based on an analogous function that we wrote for the modular data) using some heuristic tricks to speed up the procedure.

then return true ; fi ; od ; od ; return false ; end ; presorted := function (S ,T , B ) local labels , labelset , perm ,n , blocks , TS , SS , BS ; n := Size ( T );


Kamel Aouiche
email: kaouiche@eric.univ-lyon2.fr

Pierre-Emmanuel Jouve
email: pjouve@eric.univ-lyon2.fr

Jérôme Darmont
email: jdarmont@eric.univ-lyon2.fr

Clustering-Based Materialized View Selection in Data Warehouses

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Among the techniques adopted in relational implementations of data warehouses to improve query performance, view materialization and indexing are presumably the most effective ones [START_REF] Rizzi | View materialization vs. indexing: Balancing space constraints in data warehouse design[END_REF]. Materialized views are physical structures that improve data access time by precomputing intermediary results. Then, user queries can be efficiently processed by using data stored within views and do not need to access the original data. Nevertheless, the use of materialized views requires additional storage space and entails maintenance overhead when refreshing the data warehouse.

One of the most important issues in data warehouse physical design is to select an appropriate set of materialized views, called a configuration of views, which minimizes total query response time and the cost of maintaining the selected views, given a limited storage space. To achieve this, views that are closely related to the workload queries are materialized.

The view selection problem has received significant attention. Researches about materialized view selection differ in several points: [START_REF] Agrawal | Automated selection of materialized views and indexes in SQL databases[END_REF] the way of determining candidate views; [START_REF] Baralis | Materialized views selection in a multidimensional database[END_REF] the frameworks used to capture relationships between candidate views; (3) the use of mathematical cost models vs. calls to the query optimizer; (4) view selection in the relational or multidimensional context; [START_REF] Chan | Design and selection of materialized views in a data warehousing environment: a case study[END_REF] multiple or simple query optimization; and (6) theoretical or technical solutions.

The classical papers in materialized view selection introduce a lattice framework that models and captures dependency (ancestor or descendent) among aggregate views in a multidimensional context [START_REF] Baralis | Materialized views selection in a multidimensional database[END_REF][START_REF] Harinarayan | Implementing data cubes efficiently[END_REF][START_REF] Kotidis | DynaMat: A dynamic view management system for data warehouses[END_REF][START_REF] Uchiyama | A progressive view materialization algorithm[END_REF]. This lattice is greedily browsed with the help of cost models to select the best views to materialize. This problem has been firstly treated in one data cube and then extended to multiple cubes [START_REF] Shukla | Materialized view selection for multi-cube data models[END_REF]. Another theoretical framework called AND-OR view graph may also be used to capture the relationships between views [START_REF] Chan | Design and selection of materialized views in a data warehousing environment: a case study[END_REF][START_REF] Gupta | Selection of views to materialize in a data warehouse[END_REF][START_REF] Nadeau | Achieving scalability in OLAP materialized view selection[END_REF][START_REF] Valluri | View relevance driven materialized view selection in data warehousing environment[END_REF]. The majority of these solutions are theoretical and are not truly scalable. In opposition to these studies, we exploit a query clustering involving similarity and dissimilarity measures defined on the workload queries, in order to capture the relationships existing between the candidate views derived from this workload. This approach is scalable thanks to the low complexity of our clustering (log linear regarding the number of queries and linear regarding the number of attributes).

A wavelet framework for adaptively representing multidimensional data cubes has also been used [START_REF] Smith | A wavelet framework for adapting data cube views for OLAP[END_REF]. This method decomposes data cubes into an indexed hierarchy of wavelet view elements that correspond to partial and residual aggregations of data cubes. An algorithm greedily selects a non-expensive set of wavelet view elements that minimizes the average processing cost of the queries defined on the data cubes. In the same spirit, Kotidis et al. proposed the Dwarf structure, which compresses data cubes [START_REF] Sismanis | Dwarf: shrinking the petacube[END_REF]. Dwarf identifies prefix and suffix redundancies within cube cells and factors them out by coalescing their storage. Suppressing redundancy improves the maintenance and interrogation costs of data cubes. These approaches are very interesting, but they are mainly focused on computing efficient data cubes by changing their physical design. In opposition, we aim optimizing performance in relational warehouses without changing their design.

Other approaches detect common sub-expressions within workload queries in relational context [START_REF] Baril | Selection of materialized views: a cost-based approach[END_REF][START_REF] Goldstein | Optimizing queries using materialized views: a practical, scalable solution[END_REF][START_REF] Rizzi | View materialization vs. indexing: Balancing space constraints in data warehouse design[END_REF]. The problem of view selection consists in finding common subexpressions corresponding to intermediary results that are suitable to materialize. However, browsing is very costly and these methods are not truly scalable with respect to the number of queries.

Finally, the most recent approaches are workload-driven. They syntactically analyze the workload to enumerate relevant candidate views [START_REF] Agrawal | Automated selection of materialized views and indexes in SQL databases[END_REF]. By calling the query optimizer, they greedily build a configuration of the most pertinent views. A workload is indeed a good starting point to predict future queries because these queries are probably within or syntactically close to a previous query workload. In addition, extracting candidate views from the workload ensures that future materialized views will probably be used when processing queries.

Our approach is also workload-driven. Its originality lies in exploiting knowledge about how views can be used to resolve a set of queries to cluster these queries together. For this purpose, we define the notion of query similarity and dissimilarity in order to capture closely related queries. These queries are grouped in the same cluster and are used to build a set of candidate views. Furthermore, these candidate views are merged to resolve multiple queries. This merging process can be seen as iteratively building a lattice of views. The merging process time can be expensive when the number of candidate views is high. However, we apply merging over candidate views present in each cluster instead of the whole set of candidate views as in [START_REF] Agrawal | Automated selection of materialized views and indexes in SQL databases[END_REF]. This reduces the complexity of the merging process, since the number of candidate views per cluster is significantly lower.

The remainder of this paper is organized as follows. We first present in Section 2 our materialized view selection strategy. Then, we show in Section 3 how we build a candidate view configuration through our merging process. Next, we detail in Section 4 the cost models used for building the final configuration of views to materialize. To validate our approach, we also present some experiments in Section 7. We finally conclude and provide research perspectives in Section 8

Strategy for materialized view selection

The architecture of our materialized view selection strategy is depicted in Figure 1. We assume that we have a workload composed of representative queries for which we want to select a configuration of materialized views in order to reduce their execution time. The first step is to build, from the workload, a context for clustering. This context is modelled as a matrix having as many lines as the extracted queries and as many columns as the extracted attributes from each query. We define similarity and dissimilarity measures that help clustering together relatively similar queries. On each query cluster, we apply a merging process to build a configuration of candidate views. Then, the final view configuration is created with a greedy algorithm. This step exploits cost models that evaluate the cost of accessing data using views and the cost of their storage.

Query workload analysis

The workloads we consider are sets of GPSJ (Generalized Projection-Selection-Join) queries. A GPSJ query q is composed of joins, selection predicates and aggregations. As such, it may be expressed in relational algebra over a star schema as follows: q = π G,M σ S (F ⊲⊳ D 1 ⊲⊳ D 2 ⊲⊳ . . . ⊲⊳ D d ), where S is a conjunction of simple range predicates on dimension table attributes, G is a set of attributes from dimension tables D i (grouping set), and M is a set of aggregated measures each defined by applying aggregation operator to a measure in fact table F . For example, query q 1 in Figure 2 may be expressed as follows: q 1 = π sales.time id,sum(quantity sold) σ f iscal day=2 (sales ⊲⊳ times).

The first step consists in extracting from the workload the attributes that are representative of each query. We mean by representative attributes those that are present in Where (join and selection predicate attributes) and Group by clauses. We also save for each query their aggregation operators and joined tables. A query q i is then seen as a line in a matrix composed of cells that The general term qa ij of this matrix is set to 1 if the extracted attribute is present in the query and to 0 otherwise. This matrix represents our clustering context. Moreover, we store in an appendix matrix the existing associations between the join attributes and queries, in the same manner. We illustrate this step by an example: from the workload shown in Figure 2, we build the clustering context depicted in Figure 3.

Building the candidate view set

In practice, it is hard to search all the views that are syntactically relevant (candidate views) from the workload queries, because the search space is very large [START_REF] Agrawal | Automated selection of materialized views and indexes in SQL databases[END_REF]. To reduce the size of this space, we propose to cluster the queries. Indeed, we group in a same cluster all the queries that are closely similar. Closely similar queries are queries having a close binary representation in the queryattribute matrix. Two closely similar queries can be resolved by using only one materialized view. Used within a clustering process, the similarity and dissimilarity measures defined in the next section ensures that queries within a same cluster are strongly related to each others whereas queries from different clusters are significantly distant to each others.

Similarity measure. Let QA be a query-attribute matrix that has a set of queries Q = {q i , i = 1..n} as rows and a set of attributes A = {a j , j = 1..p} as columns. The value qa ij is equal to 1 if attribute a j is extracted from query q i . Otherwise, qa ij is equal to 0. We describe query q i by a vector of p values (q1) select sales.time id, sum(quantity sold) from sales, times where sales.time id = times.time id and times.day year = 2 group by sales.time id; (q2) select sales.prod id, sum(amount sold) from sales, products, promotions where sales.prod id = products.prod id and sales.promo id = promotions.promo id and promotions.promo category = 'newspaper' group by sales.prod id; (q3) select sales.cust id, sum(amount sold) from sales, customers, products, times where sales.cust id = customers.cust id and sales.prod id = products.prod id and sales.time id = times.time id and times.fiscal day = 3 and customers.cust marital status ='single' and products.prod category ='Women' group by sales.cust id; . . .

Fig. 2. Example of workload

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a1 times.time id a2 times.fiscal day q1 1 1 1 0 0 0 0 0 0 0 0 0 a3 sales.time id a4 products.prod id q2 0 0 0 1 0 1 1 1 1 0 0 0 a5 products.prod category a6 sales.promo id q3 0 0 0 1 0 1 1 1 1 1 1 1 a7 promotions.promo id a8 sales.prod id .. a9 promotions.promo category a10 sales.cust id .. a11 customers.cust marital status a12 customers.cust id Fig. 3. Example of clustering context

q i = [q i1 , ..., q ip ]
. These p values describe respectively the presence (q ij = 1) or absence (q ij = 0) of attribute a j . This description model helps comparing two queries. Then, for example, we can consider queries q 1 and q 2 as closely similar if vectors [q 11 , ..., q 1p ] and [q 21 , ..., q 2p ] have the majority of their cells equal. This introduces the notion similarity and dissimilarity between queries.

Similarity and dissimilarity between queries. We define the notion of similarity and dissimilarity between queries by two functions δ sim (q kj , q lj ) and δ dissim (q kj , q lj ) that measure the similarity between two queries q kj and q lj with respect to attribute a j .

δ sim (q kj , q lj ) = 1 if q kj = q lj = 1 0 otherwise This first function defines the notion of similarity between q k and q l following attribute a j : two queries q k and q l are considered similar regarding attribute a j if and only if q kj = q lj = 1, i.e., attribute a j is extracted from both queries.

δ dissim (q kj , q lj ) = 0 if q kj = q lj 1 if q kj = q lj
This second function defines the notion of dissimilarity between queries q k and q l according to attribute a j : two queries q k and q l are considered dissimilar according to attribute a j if only and if q kj = q lj , i.e., if one of the queries does not contain a j . Note that there is not a complete symmetry between the notion of similarity and dissimilarity: non similar queries according to an attribute are not necessarily dissimilar according to this attribute. Let q 1 and q 2 be queries such that q 1j = 0 and q 2j = 0, respectively. Then we have δ sim (q 1j , q 2j ) = 0 (q 1 and q 2 are not considered similar) and δ dissim (q 1j , q 2j ) = 0 (q 1 and q 2 are not considered dissimilar). This absence of full symmetry underlines the fact that the absence of the same attribute in two queries does not give an element of similarity or dissimilarity between these queries.

These measures can be extended to an attribute set A such that we get the degree of global similarity and dissimilarity between two queries: sim(q k , q l ) = p j=1 δ sim (q kj , q lj ) and dissim(q k , q l ) = p j=1 δ dissim (q kj , q lj ), where 0 ≤ sim(q k , q l ) ≤ p and 0 ≤ dissim(q k , q l ) ≤ p. Hence, the closer sim(q a , q b ) (resp. dissim(q a , q b )) is to p the more q a and q b can be considered globally similar (resp. dissimilar).

Similarity and dissimilarity between query sets. As we do for two queries, we introduce two functions that take into account the degree of similarity and dissimilarity between two query sets. A set of queries (subset of Q) is denoted C a . In order to translate the level of similarity (resp. dissimilarity) between query sets, we use function Sim(C a , C b ) (resp.

Dissim(C i , C j )) that determines the number of similarity (resp. dissimilarity) between two different sets of queries Similarity and dissimilarity within a query set. The notion of similarity (resp. dissimilarity) within a query set corresponds to the number of similarities (resp. dissimilarities) between queries of a same set C a . It consists of an extension of the similarity and dissimilarity functions defined between query sets: Sim(C a ) = q k ∈Ca,q l ∈Ca,k<l sim(q k , q l ) and Dissim(C a ) = q k ∈Ca,q l ∈Ca,k<l dissim(q k , q l ), where 0 ≤ Sim(C a ) ≤ card(Ca)×(card(Ca)-1)×p 2 and 0 ≤ Dissim(C a ) ≤ card(Ca)×(card(Ca)-1)×p

C a and C b (C a = C b ): Sim(C a , C b ) = q k ∈Ca,q l ∈C b sim(q k , q l ) Dissim(C a , C b ) = q k ∈Ca,q l ∈C b dissim(q k , q l ) where 0 ≤ Sim(C a , C b ) ≤ card(C a ) × card(C b ) × p and 0 ≤ Dissim(C a , C b ) ≤ card(C a ) × card(C b ) × p.

2

. Hence, the close Sim(C a ) (resp. Dissim(C a )) is to card(Ca)×(card(Ca)-1)×p 2 the more C a contains queries that are globally similar (resp. dissimilar).

Query clustering. Clustering consists in determining a so-called natural partition P nat composed of objects (here, queries) that reflects the internal structure of data. This partition must be such as its clusters are composed of objects with high similarity and objects from different clusters present a high dissimilarity.

Based on the previously defined functions, a clustering quality measure Q(P h ) can be built as follows.

Q(P h ) = a=1..z, b=1..z,a < b Sim(Ca, C b ) + z a=1 Dissim(Ca) 0 ≤ Q(P h ) ≤ i=1..z,j=1..z,i<j card(Ci) × card(Cj) × p + z i=1 card(C i )×(card(C i )-1)×p 2
This measure permits to capture the natural aspect of a partition. Hence, Q(P h ) measures simultaneously similarities between queries within the same cluster of partition P h and dissimilarities between queries within different clusters. Thus, we can define Q(P h ) as an homogeneity function for the same class and an heterogeneity function for different classes. Therefore, the partitions presenting a high intra-cluster homogeneity and a high inter-cluster disparity have a weak value of Q(P h ) and thereby appear as the most natural.

Jouve and Nicoloyannis proposed such a solution in the Kerouac clustering algorithm and its associated clustering quality measure [START_REF] Jouve | KEROUAC: an algorithm for clustering categorical data sets with practical advantages[END_REF]. We have chosen this algorithm because it has several interesting properties: (1) its computational complexity is relatively low (log linear regarding the number of queries and linear regarding the number of attributes) ; (2) it can deal with a high number of objects (queries) ; (3) it can deal with distributed data [START_REF] Jouve | A new method for combining partitions, applications for distributed clustering[END_REF].

View merging process

If we materialize all the different views derived from the query clusters obtained in the previous step, we can obtain a high number of materialized views, especially if the number of queries within the workload is high. A view configuration obtained this way would not be very relevant if the storage space allotted by the data warehouse administrator was limited. Instead of materializing each view, it is better to only materialize views that can be used to resolve multiple queries.

To solve this problem, we must enumerate the space of views that can be merged, determine how to guide the merging process, and finally build the set of merged views. View merging is relevant if the queries are strongly similar. As we cluster together closely similar queries, it is logical to apply the merging process on the set of queries present in each cluster. This significantly reduces the number of possible combinations when merging views. We detail in the following sections how we merge two views and then generalize this process to many views.

Merging of view couples. The merging of two views must ensure these conditions: (1) all queries resolved by each view must also be resolved by the merged view, and (2) the cost of using the couple of views must not be significatively greater than the cost obtained when using the merged view. Let v 1 and v 2 be a couple of views of the same cluster and s 11 , . . . , s 1m the selection predicates that are in v 1 and not in v 2 . In a dual way, let s 21 , . . . , s 1n be the selection conditions present in v 2 and not in v 1 . Merged view v 12 is obtained by applying Algorithm 1.

1: M = V1 2: for (k = 2; V k-1 = ∅; k + +) do 3: C k = View Gen(V k-1 ) 4: M ← M ∪ C k 5: for all (view v ∈ M) do 6:
Remove the parents of v from M 7: end for 8: end for 9: return M

The merging of two views v 1 and v 2 is effective if cost(v 12 ) ≥ ((cost(v 1 ) + cost(v 2 )) * x). Cost computation is detailed in Section 4. The value of x is fixed empirically by the administrator. If it is small (resp. high), we privilege (resp. disadvantage) view merging.

Merged view generation algorithm. The algorithm of view generation by merging is similar to algorithms searching for frequent itemsets. A frequent itemset lattice looks like a lattice of views within a given cluster. The lattice nodes represent the space of views obtained by merging.

Algorithm 3 Function View Gen(V k-1 ) 1: C k = ∅ 2: for all (view v ∈ V k-1 ) do 3: for all (view u ∈ V k-1 ) do 4: if (v[1] = u[1] ∧ . . . ∧ v[k -2] = u[k - 2] ∧ v[k -1] < u[k -1]) then 5: c = Merge View Pair (v,u) 6: if (cost(c) ≥ ((cost(v)+cost(u)) * x)) then 7: C k = C k ∪
S ← S ∪ {vmax} 13: end if 14: until (F /S (vmax) ≤ 0 or V -S = ∅)
The algorithm of view generation by merging (Algorithm 3) uses an iterative approach by level to generate a new view. It explores the view lattice in breadth first. The input of the algorithm is V 1 , a set of candidate views extracted from a given cluster. This algorithm outputs a set of candidate views obtained by merging. In the k th iteration, view set V k-1 obtained by merging the k -1 th level's views from the lattice (computed in the last step) is used to generate the set C k of k-candidate views. This set is added to set M (line 4). The parents of each view obtained by merging are then removed from set M (lines 5 to 7).

The function for view generation by merging View Gen(V k-1 ), called on line 3, takes as argument V k-1 and returns C k . Two views v and u within V k-1 form a k-view c if and only if they have (k -2) views in common. This is expressed using a lexicographic order in the condition of line 3. We denote by v

[1] . . . v[k-2]v[k-1]
the merged views in the k th iteration that are used to derive v. Function Merge View Pair(v,u) (Algorithm 1) called on line 5 of View Gen generates a new view c. The condition of line 6 ensures, after generating a k-view from two k -1-views, that the candidate view does not have a cost greater than the cost of its parents.

Cost models

The number of candidate views is generally as high as the input workload is large. Thus, it is not feasible to materialize all the proposed views because of storage space constraints. To circumvent these limitations, we use cost models allowing to conserve only the most pertinent views. In most data warehouse cost models [START_REF] Golfarelli | A methodological framework for data warehouse design[END_REF], the cost of a query q is assumed to be proportional to the number of tuples in the view on which q is executed. In the following section, we detail the cost model that estimates the size of a given view.

Let ms(F ) be the maximum size of fact table F , |F | be the number of tuples in F , D i ID be a primary key of dimension D i , |D i ID| be the cardinality of the attribute(s) that form the primary key, and N be the number of dimension tables. Then, ms(F ) = N i=1 |D i ID|.

Let ms(V ) be the maximum size of a given view v that has attributes a 1 , a 2 , . . . , a k in its group by clause, where k is the number of attributes in v and |a i | is the cardinality of attribute a i . Then, ms(v) = k i=1 |a i |. Golfarelli et al. [START_REF] Golfarelli | A methodological framework for data warehouse design[END_REF] proposed to estimate the number of tuples in a given view v by using Yao's formula [START_REF] Yao | Approximating block accesses in database organizations[END_REF] as follows:

|v| = ms(v) × 1 -|F | i=1 ms(F )×d-i+1 ms(F )-i+1
, where d = 1 -1 ms(v) . If ms(F ) ms(v) is sufficiently large, then Cardenas' formula [START_REF] Cardenas | Analysis and performance of inverted data base structures[END_REF] approximation gives:

|v| = ms(v) × 1 -1 -1 ms(v) |F |
, where d = 1 -1 ms(v) . Cardenas' and Yao's formulaes are based on the assumption that data is uniformly distributed. Any skew in the data tends to reduce the number of tuples in the aggregate view. Hence, the uniform assumption tends to overestimate the size of the views and give a crude estimation. However, they have the advantage to be simple to implement and fast to compute. In addition, because of the modularity of our approach, it is easy to replace the cost model module by another more accurate one.

From the number of tuples in v, we estimate its size, in bytes, as follows: size(v) = |v|× c i=1 size(c i ), where size(c i ) denotes the size, in bytes, of column c i of v, and c is the number of columns in v.

Objective functions

In this section, we describe three objective functions to evaluate the variation of query execution cost, in number of tuples to read, induced by adding a new view. The query execution cost is assimilated to the number of tuples in the fact table when no view is used or to the number of tuples in view(s) otherwise. The workload execution cost is obtained by adding all execution costs for each query within this workload.

The first objective function advantages the views providing more profit while executing queries, the second one advantages the views providing more benefit and occupying the smallest storage space, and the third one combines the first two in order to select at first all the views providing more profit and then keep only those occupying the smallest storage space when this resource becomes critical. The first function is useful when storage space is not limited, the second one is useful when storage space is small and the third one is interesting when storage space is larger.

Profit objective function

Let V = {v 1 , ..., v m } be a candidate view set, Q = {q 1 , ..., q n } a query set (a workload) and S a final view set to build. The profit objective function, noted P , is defined as follows:

P /S (v j ) = C /S (Q) -C /S∪{vj } (Q) -β C maintenance ({v j }) ,
table |F |. When a view v j is added to S, C /S∪{vj } (Q) = |Q| k=0 C(q k , {v j })
denotes the query execution cost for the views that are in S ∪ {v j }. If query q k exploits v j , the cost C(q k , {v j }) is then equal to C vj (number of tuples in v j ). Otherwise, C(q k , {v j }) is equal to the minimum value between |F | and values of C(q k , {v}) (executing cost of q k exploiting v ∈ S with v = v j ).

-Coefficient β = |Q| p(v j ) estimates the number of updates for view v j . The update probability p(v j ) is equal to 1 number of views %update %query , where %update %query represents the proportion of updating vs. querying the data warehouse.

-C maintenance ({v j }) represents the maintenance cost for view v j .

Profit/space ratio objective function

If view selection is achieved under a space constraint, the profit/space objective function R /S (v j ) = P /S (vj ) size(vj ) is used. This function computes the profit provided by v j in regard to the storage space size(v j ) that it occupies.

Hybrid objective function

The constraint on the storage space may be relaxed if this space is relatively large. The hybrid objective function H does not penalize space-"greedy" views if the ratio remaining space storage space is lower or equal than a given threshold α (0 < α ≤ 1), where remaining space and storage space are respectively the remaining space after adding v j and the allotted space needed for storing all the views. This function is computed by combining the two functions P and R as follows:

H /S (v j ) = P /S (v j ) if remaining space storage space > α, R /S (v j ) otherwise.

View selection algorithm

The view selection algorithm (Algorithm 4) is based on a greedy search within the candidate view set V . Objective function F must be one of the functions P or R described previously. If R is used, we add to the algorithm's input the space storage M allotted for views.

In the first algorithm iteration, the values of the objective function are computed for each view within V . The view v max that maximizes F , if it exists (F /S (v max ) > 0), is then added to S. If R is used, the whole space storage M is decreased by the amount of space occupied by v max .

The function values of F are then recomputed for each remaining view in V -S since they depend on the selected views present in S. This helps taking into account the interactions that probably exist between the views.

We repeat these iterations until there is no improvement (F /S (v) ≤ 0) or until all views have been selected (V -S = ∅). If function R is used, the algorithm also stops when storage space is full.

In order to validate our approach for materialized view selection, we have run tests on a 1 GB data warehouse implemented within Oracle 9i, on a Pentium 2.4 GHz PC with a 512 MB main memory and a 120 GB IDE disk. This data warehouse is composed of the fact table Sales and five dimensions Customers, Products, Times, Promotions and Channels. We executed on our data warehouse a workload composed of sixty-one decision-support queries involving aggregation operations and several joins between the fact table and dimension tables. Due to space constraints, the data warehouse schema and the detail of each workload query are available at http://eric.univ-lyon2.fr/~kaouiche/ adbis.pdf. Our experiments are based on an ad-hoc benchmark because, as far as we know, there is no standard benchmark for data warehouses. TPC-R [START_REF]TPC Benchmark R Standard Specification[END_REF] has no multidimensional schema and does not qualify, for instance.

We first applied our selection strategy with the profit function. This function gives us the maximal number of materialized views (twelve views) because it does not specify any storage space constraint. This point gives us the upper boundary of the storage space occupation. Then, we applied the profit/space ratio and hybrid functions under a storage space constraint. We have measured query execution time with respect to the percentage of storage space allotted for materialized views. This percentage is computed from the upper boundary computed when applying the profit function. This helps varying storage space within a wider interval. Ratio profit/space function experiment. We plotted in Figure 4 the variation of workload execution time with respect to the storage space allotted for materialized views. This figure shows that the selected views improve query execution time. Moreover, execution time decreases when storage space occupation increases. This is predictable because we create more materialized views when storage space is large and thereby better improve execution time. We also observe that the maximal gain is equal to 94.86%. It is reached for a space occupation of 100% (no constraint on storage space). This case is also reached when using the profit function, because it corresponds to the upper boundary.

Hybrid function experiment. We repeated the previous experiment with the hybrid objective function. We varied the value of parameter α between 0.1 and 1 by 0.1 steps. The obtained results with α ∈ [0.1, 0.7] and α ∈ [0.8, 1] are respectively equal to those obtained with α = 0.1 and α = 0.8. Thus, we plotted in Figure 5 only the results obtained with α = 0.1 and α = 0.7. This figure shows that for percentage values of space storage under 18.6%, the hybrid function with α = 0.1 and α = 0.8 behaves as the ratio function. When the storage space becomes critical, the hybrid function behaves as the ratio profit/space function.

On the other hand, for the percentage values of storage space greater than 18.6%, the results obtained with α = 0.8 are slightly better than those obtained with α = 0.1. This is explained by the fact that for the high values of α, the hybrid function chooses the views providing the most profit and thereby improving the best the execution time. The maximal gain in execution time observed for the values 0.1 and 0.8 of α is equal to 96%.

Fig. 6. Query covering rate by the selected materialized views

Selected view pertinence experiment. In order to show if our strategy provides pertinent views for a given workload, we measured the covering rate of the workload query results by the selected views. We mean by covering rate the ratio between the number of queries resolved from the materialized views and the total number of queries within the workload. Thus, the highest the rate value, the most pertinent the selected views. In this experiment, the percentage of storage space is also computed from the upper boundary. We plotted in Figure 6 the covering rate according to storage space occupation. This figure shows that the covering rate increases with storage space. When storage space gets larger, we materialize more views and thereby we recover more query results from these views. When materializing all the views (100% storage space occupation), all the data corresponding to query results are recovered from the materialized views. This shows that, without storage space constraint, the selected views are pertinent. For example, for 0.05% storage space occupation, 22.95% of the query results are recovered from the selected views. This shows that, even for a limited storage space, our strategy helps building views that cover a maximum number of queries. This experiment shows that materialized view selection based on workload syntactical analysis is efficient to guarantee the exploitation of the selected views by the workload queries.

Conclusion

In this paper, we presented an automatic strategy for materialized view selection in data warehouses. This strategy exploits the results of clustering applied on a given workload to build a set of syntactically relevant candidate views. Our experimental results show that our strategy guarantees a substantial gain in performance. It also shows that the idea of using data mining techniques for data warehouse auto-administration is a promising approach. This work opens several future research axes. First, we are still currently experimenting in order to better evaluate system overhead in terms of materialized view building and maintenance. The maintenance cost is currently derived from the query frequencies (Section 4). We are envisaging a cost model more accurate to estimate update costs. We also plan to compare our approach to other materialized view selection methods. Furthermore, it could be interesting to design methods that select both indexes and materialized views, since these data structures are often used together. More precisely, we are currently developing methods to efficiently share the available storage space between indexes and views. Finally, our strategy is applied on a workload that is extracted from the system during a given period of time. We are thus performing static optimization. It would be interesting to make our strategy dynamic and incremental, as proposed in [START_REF] Kotidis | DynaMat: A dynamic view management system for data warehouses[END_REF]. Studies dealing with dynamic or incremental clustering may be exploited. Entropy-based session detection could also be beneficial to determine the best moment to run view reselection.

Fig. 1 .

 1 Fig. 1. Strategy of materialized view selection

  Hence, the closer Sim(C a , C b ) (resp. Dissim(C a , C b )) is to card(C a ) × card(C b ) × p the more C a and C b can be considered similar (resp. dissimilar).

Algorithm 1 2 :Algorithm 2

 122 Merge View Pair(v1, v2) 1: put v1 and v2 aggregation operations in v12 operation aggregations put the union of projection and group by attributes v1 and v2 in projection and group by clause of v12 3: put all attributes s11, . . . , s1m and s21, . . . , s1n in the group by clause of v12 4: put the selection predicates shared between v1 and v2 in the selection predicate clause of v12 Mergin View Generation

  where v j / ∈ S. -C /S (Q) denotes the query execution cost when all views in S are used. If this set is empty, C /∅ (Q) = |Q| × |F | because all the queries are resolved by accessing fact

Fig. 4 .

 4 Fig. 4. Profit/space ratio function Fig. 5. Hybrid function

Property 1 The view obtained by merging views v 1 and v 2 is the smallest view that resolves the query resolved by both v 1 and v 2 .

Proof. To show that the view obtained by merging views v1 and v2 is the smallest view, we have to show that there is no view v ′ 12 such as the data within v ′ 12 are also included within v12. We denote respectively views v1, v2 and v12 πG 1 ,M 1 σS 1 (F ⊲⊳ . . .), πG 2 ,M 2 σS 2 (F ⊲⊳ . . .) and πG 12 ,M 12 σS 12 (F ⊲⊳ . . .), respectively, where: -G1, G2 are respectively the attribute set of the group by clause of views v1 and v2; -S1, S2 are respectively the attribute set of the selection predicates of v1 and v2;

∈ G1 and x / ∈ G2, then x is not in any clause of v2. This means that x / ∈ G ′ 12 , which contradicts condition x ∈ G ′ 12 . From the second condition, there is at least one attribute y such that y ∈ S12 and y / ∈ S ′ 12 . As we have y ∈ S12, then y ∈ S1 and y ∈ S2 because S12 = S1 ∪ S2. As y ∈ S1 and y ∈ S2, then y must be in all the predicates of the views obtained by merging v1 and v2. This means that y ∈ S ′ 12 , which contradicts condition y / ∈ S ′ 12 .