Hierarchies are an important means to categorize data stored in OLAP systems. OLAP queries follow the drill/slice/dice-paradigm and therefore exhibit navigation patterns that follow the hierarchy of a dimension. In real-world applications, hierarchies are often unbalanced and share levels, resulting in complex hierarchy structures. So far, encoding methods for simple structured hierarchies have been introduced to handle hierarchies efficiently for query processing. In this paper we propose the HINTA algorithm to compute the clustering order for complex hierarchies by linearization. The physical clustering of OLAP data computed by HINTA significantly improves the performance of OLAP queries. HINTA enables clustering of complex hierarchies that can share hierarchy levels in several classifications over one dimension.
A data warehouse (DW) is a physical database with an integrated view onto arbitrary data. A multidimensional (MD) view enables complex interactive, explorative data analysis (OLAP, i.e. OnLine Analytical Processing). Conceptually, the data of a DW is stored in data cubes. A data cube consists of a set of dimensions and a set of measures. Dimensions provide categorical (qualitative) data (e.g., products, customers, time), which determine the context of the measures (e.g., items sold, cost, turnover). The set of base values forming a dimension generally is classified according to a set of hierarchies. For instance, the time dimension may have a hierarchy all-year-monthday or all-year-week-day. In this paper we will discuss and further detail how the set of hierarchies can be represented and efficiently utilized for query processing. Multidimensional clustering indexes (e.g., UB-Tree, RTree) handle multiple dimensions for multidimensional range queries ([Mar99]). Encoding methods prepare hierarchical classification for the use of clustering B-Trees for one hierarchy ([ZSL98], [MRB99]). This encoding, however, is only useful for a special case of hierarchies, i.e., hierarchy trees or simple hierarchies. In reality, hierarchies are more complex, e.g., hierarchies are unbalanced, have alternative paths and shared levels. To solve this severe problem and make encoding techniques useful for real world scenarios, we propose HINTA, an algorithm that transforms an instantiation of a complex hierarchy to a hierarchy tree. In combination with the above mentioned encoding schemes, the resulting hierarchy can be used for clustering.
In this paper, we present a formal hierarchy model, that is based on graph algorithms and is introduced by the instantiation of the hierarchies.
The rest of the paper is organized as follows. Section 2 lists related work. Section 3 gives a motivating example how to use hierarchy encoding and to make use of HINTA. In Section 4, we present the hierarchy model. Section 5 describes HINTA, a transformation algorithm of complex hierarchies to simple hierarchies. Section 6 summarizes this paper and gives an outlook to future work. 0 Germany 0 North
1 South 0 AldiN
1 SaturnN 0A1 1A2 0000 0001 with classify-relationships. In [LW96], a MD model is discussed, based on relational elements.
Many publications propose first to establish the conceptual model and then to do the actual implementation ([WB97], [CT98], [GMR98]). [HLV00] show how to systematically derive a conceptual warehouse schema from a generalized multidimensional normal form. [FS99] introduce a conceptual data model, that allows complex descriptions of the structure of aggregated entities and multiply hierarchically organized dimensions. [VS99] presents an overview of the understanding of commercial and scientific concepts of DW modeling. For single hierarchies, [ZSL98] discusses the linearization and presents the physical representation within DBMS. [MRB99] extend the linearization to multiple dimensions and hierarchies and discuss query processing of hierarchically organized multidimensional data.
In this paper, we further present a linearization method for complex hierarchies by transforming complex hierarchies to simple hierarchies and using the linearization method already published in [MRB99]. [PJD99] discuss a transformation algorithm to achieve summarizability on unbalanced hierarchies.
1 Austria 0 East
1 West 0 HoferE 1SaturnE
0 HoferW 1 SaturnW 1000 In a star schema ([Kim96]), dimension tables are connected to a large fact table via dimension attributes (join attributes). The dimension table usually contains the hierarchies of the dimension, where for every path through the hierarchy an artificial unique id (dimID) is used as join attribute. This dimID can be a computed number with respect to the encoding of the hierarchy for hierarchical clustering: dimID=surr(vm, vm-1, …, vleaf). The function surr computes a surrogate id for the path of the dimension tuple. The schema of a dimension table usually includes the hierarchy attributes of all simple hierarchies. Conventional approaches to process queries in DW schemata in relational DBMS are star join algorithms, where restrictions on the dimension tables result in a number of dimension values that are joined with the fact table. Queries that restrict dimensions, have predicates on hierarchy levels. These predicates usually are point or interval restrictions ([Sar97]) and result in large point sets on base granularity (i.e., the leaf level of the hierarchy). Such point sets can be replaced by a smaller set of interval restrictions depending on the predicate. The predicate “Germany” of the hierarchy in Figure 3-1 would result in the leaf members {“A1”, “A2”, “S1”, “S2”, “A3”}, and
Segment
TG23 A3 every such member is a join predicate to the fact table. Figure 3-1 shows a hierarchy schema (on the left) and one hierarchy instance (on the right). The hierarchy is a complex hierarchy with the paths Dimension-Country-RegionMicroMarket-Outlet (solid arrows) or alternatively Dimension-Country-TurnoverClass-Outlet (dashed arrows). 3.1
The identifier of the paths must be unique. Thus, a number can be used to represent the corresponding path in the hierarchy. We establish an encoding schema on the hierarchy, that numbers (surrogate number) the children of every level. The resulting identifier, called compound surrogate, are the concatenated surrogates of the path, one for each level. It is shown in Figure 3-1 in the rectangles. With this encoding ([ZSL98], [MRB99]), hierarchical point sets can be replaced by intervals. The predicate “Germany”, is mapped to the interval [000; 0100]. This new interval predicate speeds up query execution on the fact table, when using corresponding clustering indexes (because a local interval predicate can be performed on the fact table instead of a join). Such an encoding is known for simple hierarchies. But predicates on a complex hierarchy often result in point restrictions on the leaf members. The predicate “TG2” specifies the leaf members {“A2”, “S2”, “A3”}, that cannot be expressed by an interval when encoding the hierarchy with respect to the previous case.
A solution to speed up queries for DW applications with complex hierarchies is to transform the complex hierarchy into a simple hierarchy while leaving hierarchical dependencies. With this transformation and the mentioned encoding, a predicate on the dimension hierarchy can be mapped to a relatively small number of intervals on the fact table. Thus, a query with a number of intervals on the fact table is performed instead of a complex join operation between dimension and fact table.
HINTA changes the hierarchy from a complex to a simple hierarchy, where alternative paths are concatenated by preserving hierarchical dependencies. Figure 3-2 shows, the result of HINTA for the complex hierarchy of Figure 3-1 (the detailed transformation algorithm is discussed in Section 5). 3.2
The advantage of using HINTA in combination with hierarchy encoding is, that the dimension is left unchanged for the members of the hierarchy. Only the artificial key has to be recomputed. A dimension table D for Figure 3-1 may have the schema D(country, region, micromarket, turnoverclass, outlet, dimID). For the geographical hierarchy, dimID=surrgeo(country, region, micromarket, outlet), for the transformed hierarchy, dimID=surrgeotc(country, region, micromarket, turnoverclass, outlet), where surr is a function that computes the encoding for the corresponding hierarchy path.
These physical properties do not affect the schema. If the optimizer is able to handle hierarchy encoding, another hierarchy schema and therefore encoding even is transparent to the SQL statements (i.e., the optimizer recognizes, that a predicate on the dimension table with a corresponding join to the fact table can be replaced by a number of local interval predicates on the fact table). In such a case, the generated operator tree avoids expensive join operations. However, for the so called residual join, i.e., the join for the result set of the fact table to the dimension table in order to perform grouping, sorting, feature evaluation, postfiltering etc., the join cannot be prevented. Compared to the first pass of query evaluation, this residual join will be performed on a relatively small number of tuples and thus usually will not be critical for query execution. 4
Graphs represent relationships between vertices. Members in hierarchies are classified by relationships (usually 1:n relationships), which we in the following call hierarchical relationships. These hierarchical relationships can be represented in a directed graph. A hierarchy instance is the actual instantiation of the hierarchical relationship. A special case of a hierarchy instance is a hierarchy tree. In this paper, we extend the simple structure of a hierarchy tree to a more complex hierarchy graph. We use equivalence classes defined on the graph to describe hierarchy instances.
In the first part of this section, we work out properties of directed acyclic graphs (DAG) as model to describe hierarchies. The second part introduces hierarchy instances and schemata. We define some special hierarchies and describe typical hierarchies of data warehouses. Basically, a hierarchy instance H corresponds to a graph G = (V, E) with vertices vi ∈ V and typed edges ej ∈ E. V is a finite set and E is a subset of V×V×N: et ∈ E = (v1, v2,)t, where v1, v2 ∈ V and t ∈ N is a type determinator (type) specifying the type of the edge. We define a function T: V×V×N!N that returns the type of an edge e: T(e) = T((v1, v2)t) = t. 4.1
We concentrate on DAGs ([CLR90]) with typed edges, abbreviated by tDAG. In a DAG, a vertex v is adjacent to u, if u ! v or (u, v) ∈E.
Figure 4-1 illustrates a sample graph. This graph is a tDAG (the direction of the edges is denoted by arrows, the type of the edges is denoted by the edge style, a solid arrow denotes type 1, a dashed arrow denotes type 2). The vertices vi are { Germany, Austria, North, South, East, West, …, S6 }, the edges are: E={A1!AldiN, AldiN! North, North!Germany, …, West!Austria} or equivalently a set of pairs E={(A1, AldiN)1, (AldiN, North)1, …, (TG2, Germany) 2, …, (West, Austria)1}.
A path φ from u to v is a sequence of adjacent vertices (v1, v2, …, vn), where vi ! vi+1, i = 1, …, n-1 and v1 = u and vn = v. We say, v is reachable from u via φ: u Φ→ v . We say, φ contains the vertices v1, v2, …, vn.
A typed path φt is a path with a type t, the function T: (E× .. ×E)! N returns the type:
t if ∀vi,vi+1 ∈Φ:T((vi ,vi+1))=t (i =1,...,n−1) T(Φ) =
⊥ otherwise Two paths φ1 = (v11, v12, …, v1n) and φ2 = (v21, v22, …, v2n) have the same type t, if the types of all edges of φ1 and φ2 are the same: T(φ1) = T(φ2) = t.
The pathlength is the number of edges in path φ.
The out-degree of a vertex u (outdegree(u)) is the number of edges leaving u, outdegreet(u) is the number of edges with type t, leaving u.
The in-degree of u (indegree(u)) is the number of edges entering u, indegreet(u) is the number of edges with type t entering u, correspondingly.
The degree of u is the sum of indegree(u) and outdegree(u).
A rooted tDAG has a number of vertices vi with indegree(vi) = 0. These vertices are called leaf vertices vleaf (or leaves). In the graph of Figure 4-1, the leaf vertices are {A1, A2, S1, S2, A3, H1, H2, S4, H3, H4, S5, S6}. A root Segment
Germany North
South
A1
A2
S1
S2
AldiS A3
TG1 TG2 TG5 TA1 TA2
Austria East West
pathlength(φ) = pathlength(path(u, v)), if φ = u Φ→ v and path(u,v) is the path φ from u to v. The type of a path is only defined, if all edges in the path have the same type.
We use Figure 4-1 as example graph. There are two paths from “A1” to “Segment” φ1=(“A1”, “AldiN”, “North”, “Germany”, “Segment”) and φ2=(“A1”, “TG1”, “Germany”, “Segment”). pathlength(φ1) = 4 and pathlength(φ2) = 3, where T(φ1)=1 and T(φ2) = 2.
A rooted tDAG is a tDAG that has one vertex r that is reachable from all vertices vi ∈ V \{r}. Thus, there is a path from all vi∈V to r, vi≠r. Vertex r is called root vertex (or root).
If the union of two tDAGs G1=(V1, E1) and G2=(V2, E2) is not rooted (i.e., G=G1∪G2=(V1∪V2, E1∪E2) is not a rooted tDAG), but G1 and G2 are rooted tDAGs, we can construct a rooted tDAG G of G1∪G2 by adding a new vertex r and two edges e1 = (rG1, r) and e2 = (rG2, r), where rG1 is root of G1 and rG2 is root of G2: G=( V1 ∪ V2 ∪ r, E1 ∪ E2 ∪ (rG1, r) ∪ (rG1, r)). vertex (root) r has an out-degree of 0.
We further consider graphs, where every leaf vertex has at least one typed path to the root. We additionally require, that for every vertex v outdegreet(v)=1.
In Figure 4-1, the vertex SaturnN has the following degrees: indegree(SaturnN) = indegree1(SaturnN) = 2, outdegree(SaturnN)=1, degree(SaturnN)=3.
A subgraph G’ of graph G=(V,E) is a graph, whose vertices V’ and edges E’ are subsets of vertices V and edges E of G: G’=(V’, E’), V’⊆V, E’⊆E.
A simple tDAG (stDAG) Ts=(Vs, Es) is a subgraph of G with edges of one type t. The vertices of Ts are the vertices contained in all paths φtk from leaves of G to the root, and pathlength(φti)= pathlength(φtj), i.e., all paths from leaves to root with same type and length.
A simple tDAG TS is a balanced tree.
An equivalence class is a set of vertices with the following properties: Two vertices u, v of a simple tDAG TS=(VS, ES), u, v ∈ Vs are elements of equivalence class c, if pathlength(path(u, root)) = pathlength(path(v, root)), i.e., if the path length of the path from the vertices of c to the root is identical (same distance). 4.2
With the definitions of graphs, we now can define hierarchies. We draw a parallel from the concepts of rooted 1 A tree is a finite set T of one or more vertices such that there is one specially designated node called the root of the tree, root(T), and the remaining nodes (excluding the root) are partitioned into m≥0 disjoint sets T1, …, Tm and each of these sets in turn is a tree. The trees T1, …, Tm are called the subtrees of the root. tDAGs to hierarchies. This section describes hierarchies and their properties.
A hierarchy instance H is a rooted tDAG H=(V, E) with members mi∈V and directed, typed edges ej∈E. The edges are called hierarchical relationships. We call a member mi hierarchically dependent on mj, if mj!mi (or equivalently (mj, mi) ∈ E). We call a member mi indirect hierarchically dependent on mj, if mi is reachable from mj via a path φ: m j Φ→ mi , also denoted by m j *→ mi . We additionally define sub-hierarchies, called simple hierarchies HS=(VS,ES) that correspond to simple graphs. All simple hierarchies HiS of a hierarchy instance H are partitions of H. The union of the simple hierarchies is the hierarchy instance H: U H iS = H . This follows from i the definition of simple graphs.
A hierarchy level or level is an equivalence class of a simple hierarchy containing members with the same distance from the root. We call the level, consisting of leaves, leaf level and the level, consisting of the root, root level. A simple hierarchy is a balanced hierarchy tree with a depth equal to the pathlength of the path from the leaves to the root.
A level hj is hierarchically dependent on hi, if all members mjk∈hj are hierarchically dependent on members mih∈hi, i.e., ∀mjk∈hj ∃mih∈hi: (mih, mjk) ∈E. The function HD: (V, V×V)!(V×V) computes the hierarchical relationships {(hi, hj)} of the levels of a hierarchy instance H=(V, E), where hi, hj are levels of H and hi is hierarchically dependent on hj.
A level hj is indirect hierarchically dependent on hi, if all members mjk∈ hj are indirect hierarchically dependent on members mih∈ hi.
The order of dependencies often intuitively is misunderstood. A simple example illustrates the correct hierarchical dependencies: In a geographic hierarchy with levels country, state and town, the level state is hierarchically dependent on town, because state is determined by the towns. The level country also is hierarchically dependent on town, however indirect (via level state).
HD(H1) returns the following hierarchical dependencies: HD(H1) = {(A1, AldiN), (A2, AldiN), (S1, SaturnN), (S2, SaturnN), (A3, AldiS), …, (Germany, Segment), (Austria, Segment)}, i.e., all edges of the graph representing H1.
Two levels h1={mk1} and h2={mj2} are shared levels, if the intersection of h1 and h2 is not empty. Otherwise the levels h1 and h2 are not shared. We call such levels h1 and h2 disjoint levels.
The distinct operator L!L returns a subset of levels L’={hk} of a set of levels L={hi}: distinct(L)={hk}=L’, where ∀hk, hh ∈ L’: hk ≠ hh. There are no equal levels in L’.
If there are several paths from a member to the root (usually true for shared levels), we call these paths alternative paths.
According to Example 4-5, shared levels are: h11=h12, 4 =h32, h51=h42. h 1 For the hierarchy instance H = H1∪H2, the distinct operator returns the following levels: distinct(H) ={ h11, h21, h31, h41, h51, h22}.
The distinct operator generally is not deterministic. However, the members of the levels specified by the distinct operator, are deterministic (e.g., the members of h11 and h12 are the same).
A balanced hierarchy is a hierarchy, whose leaf members are contained in one (shared) level hl. Simple hierarchies are always balanced hierarchies, because they have only one leaf level (balanced tree).
The hierarchy schema HS is a rooted tDAG specified by HS=(LS, ES), where L is a set of levels hi, and ES is a set of hierarchical relationships ES=(hi, hj) between the levels, i.e., hj is hierarchically dependent on hi.
A hierarchy schema HS=(LS, ES) conforms to a hierarchy instance H=(VH, EH), if the number of levels of HS and H is equal, and the hierarchical dependencies of these levels are equal: ∀ (hiS, hjS) ∈ ES: ∃( hiH, hjH) ∈ HD(H) ∧ ∀( hiH, hjH) ∈ HD(H): ∃(hiS, hjS) ∈ ES
On the left side of Figure 3-1, a hierarchy schema is illustrated: HS=(L, ES), where L={Outlet, MicroMarket, Region, TurnoverClass, Country, Dimension} and ES={(Outlet, MicroMarket), (MicroMarket, Region), (Region, Country), (Outlet, TurnoverClass), (TurnoverClass, Country), (Country, Dimension)}. As hierarchy instance H, we use Example 4-5. H = H1∪H2 = (V, EH), where the levels are LH={h11, h21, h31, h41, h51, h12, h22, h32, h42}. The distinct levels are distinct(LH) = {h11, h21, h31, h41, h51, h22} and the hierarchical dependencies are HD(H) = {(h11, h21), (h21, h31), (h31, h41), (h41, h51), (h11, h22), (h22, h41)}. If we map Outlet to h11, MicroMarket to h21, Region to h31, Country to h41, Dimension to h51 and TurnoverClass to h22, the hierarchy schema HS conforms to hierarchy instance H of Figure 4-1. 4.3
Hierarchies are used to classify the dimensions of a DW. DW model complex business contexts. Additional attributes are used to provide additional classification information, e.g., the screen size of TV sets. For this reason, the members can be augmented by classification features. Therefore, a member v in a hierarchy graph is a pair v=(id, {fi}), where id is a unique identifier of the vertex, called member label (or label), and {fi} is a set of additional attributes, called feature attributes. We call such a graph an attributed tDAG.
Feature attributes are assigned to hierarchy members. Generally, a member can have an arbitrary number of features. In many DW hierarchies, however, the hierarchy members of one hierarchy level have the same number of feature attributes2. In this case, features are assigned to hierarchy levels.
In a DW, hierarchies are assigned to dimensions. One dimension can contain several hierarchies. We combine all hierarchies of one dimension to one hierarchy instance corresponding to a rooted tDAG, where the root is the “All” level. Such a hierarchy instance is called DWhierarchy. Usually, facts have a base granularity with respect to every dimension. This base granularity corresponds to one leaf level of the DW hierarchy. Thus, a DW-hierarchy only has one (shared) leaf level.
If facts are classified with respect to different granularities3 (leaf hierarchy levels), new aggregation and grouping semantics have to be introduced ([Leh98a]). The hierarchy model, however, supports such degenerated hierarchies. 5
First, we discuss some algorithms, that are used by HINTA. Then we discuss HINTA in detail and show a complete example of HINTA for the hierarchy instance of Figure 3-1. 5.1
We use the term primitive hierarchy instance, phi, for hierarchy instances, that consist of two simple hierarchies with one shared leaf level - the remaining levels are disjoint. Such a phi can be transformed to one simple hierarchy instance. A phi is some kind of sub-hierarchy of a 2 Hierarchy members of one hierarchy level usually categorize the same information, e.g., the level “country“ may have feature attributes like number of inhabitants, gross national product, etc. for every country stored in the hierarchy. 3 unbalanced hierarchies conventional hierarchy instance consisting of two simple hierarchies.
A phi H consists of a number of hierarchically dependent disjoint levels and one shared leaf level. Figure 5-1 illustrates all possible hierarchy schemata of phi (phi1, phi2, phi3). phi1 only contains one shared level, i.e., the leaf level of H. Such a phi can be constructed, if a hierarchy has several hierarchically dependent shared levels. This sequence of levels is split into phi’s of type phi1 for every level. Usually, edges of both simple hierarchies “leave” phi1 (illustrated by dotted arrows). Thus, the original hierarchy has a level hierarchically dependent on hi, if hi is not the root level. phi2 is the general case for a phi. Two simple hierarchies H1 and H2 have one shared leaf level hi and a number of hierarchically dependent levels hk, …, hh for H1 and hj, …, hl for H2. Usually, a level hx (shared level) is hierarchically dependent on hh and hl. The dotted arrows denote these hierarchical relationships. phi3 is a special case of phi2, where H1 only consists of the shared leaf level hi, and H2 consists of additional hierarchically dependent levels hj, …, hl.
In Figure 5-1, a splitting of a hierarchy schema of hierarchy H with the two simple hierarchies HS1 and HS2 into phi’s is illustrated. HS1 consists of the levels {A, B, D, E, G, J}, HS2 consists of the levels {A, B, E, F, G, I, J}. Shared hierarchy paths (levels A and B) are from type phi1, the alternative paths for levels G!D!C and G!F!E are from type phi2, and the alternative paths J and J!I are from type phi3.
No other phi are possible for two simple hierarchies, because by concatenating phi’s, all hierarchy instances for A
B C D hh ... hk G hi
E F I hl ... hj phi1 phi1 phi2 hi hl ... hj hi phi1
phi2 phi3 phi3 Figure 5-1: Hierarchy Schema for Primitive
HJierarchy Instances
Figure 5-2: Example of phi’s two simple hierarchies can be constructed.
A phi of a hierarchy instance H=H1∪H2 formally is defined in the following way:
The primitive hierarchy instance (phi) of a hierarchy instance H consisting of two simple hierarchies HS1=(VS1, ES1) and HS2=(VS2, ES2) is a hierarchy instance Hphi=(Vphi, Ephi): Vphi = {h1m, h1m-1, …, h1k, h2n, h2n-1, …, h2h}, where h1m resp. h2n are root levels of HS1 resp. HS2 and h1k and h2h are shared levels and ∀h1j, k<j≤m: ∀h2i, h<i≤n: h1j, h2i are disjoint levels.
Ephi = {ei}, where ei = (vi, vj) ∈ (ES1∪ES2): vi, vj ∈ {(Vphi ∪ vx)}, vk!vx, vk∈Vphi.
Ephi contains all original edges between the members of Vphi and the “leaving” edges.
This example shows the phi’s of the sample hierarchy instance H of Figure 4-1. H consists of three phi’s: Hp1, Hp2 and Hp3.
Hp1 is of type phi1. Vp1 = {Segment}, Ep1 = ∅ , because the root does not have leaving edges.
Hp2 is of type phi1 again and consists of the members Vp2 = {Germany, Austria} and the edges Ep2 = {(Germany, Segment)1, (Austria, Segment)1, (Germany, Segment)2, (Austria, Segment)2} The edges are of type 1 and 2 (see Figure 4-1).
Hp3 is of type phi2 and consists of two alternative paths with shared leaf level Outlet (see Figure ) Vp3 = {A1, A2, S1, S2, A3, H1, H2, S4, H3, H4, S5, S6, AldiN, SaturnN, AldiS, HoferE, SaturnE, HoferW, SaturnW, TG1, TG2, TG5, TA1, TA2, North, South, East, West} Ephi3 = {(A1, AldiN), (A2, AldiN), (S1, SaturnN), (S2, SaturnN), (A3, AldiS), …, (South, Germany), (East, Austria), (West, Austria)} 5.2
A phi can be transformed to a simple hierarchy. In this section, members are denoted by v. If v is in level hi, i.e., v ∈ hi, we write vi, if v ∈ hj, we write vj etc. We write vx and vy for members not within the hierarchies. An edge (vh, vx) hh ... hk hl ...
hj hi
Figure 5-4: Transformation of a phi2 is a leaving edge of vh. Depending on the type of the phi, the hierarchy is transformed by deleting and adding special members and edges. A phi consists of two simple hierarchies. For the transformation, one hierarchy is preferred, i.e., the levels of the preferred hierarchy usually are more significant for the encoding than the levels of the other hierarchy (predicate isPreferred). The isPreferred: any more (see Figure 5-4). The operation insertpath(path) inserts members and edges of path. This is necessary, because a member vj ∈ hj can be adjacent to several members vi ∈ hi, that do not correspond to an equal number of members vk ∈ hk. Thus, we have to duplicate the path to preserve hierarchical dependencies. Instead of the discussed transformation algorithm, that concatenates two simple hierarchies, a hierarchy level interleaving also is possible. This interleaving corresponds to a topological sorting of the hierarchies. Further research is necessary to work out the advantages of the transformation methods. The Hierarchy INstance Transformation Algorithm, HINTA, transforms a hierarchy instance H=(V, E), represented by a rooted tDAG (e.g., a DW-hierarchy) into simple hierarchy HS = HINTA(H) = (VS, ES). The input of HINTA is a hierarchy instance that consists of an arbitrary number n of simple hierarchies HSk. We transform two simple hierarchies HS1 and HS2 to one simple hierarchy by splitting them into phi’s and transforming each phi with Segment
Austria East
West HoferE
SaturnE
HoferW
SaturnW H1 H2
S4
H3 H4 S5
S6
Germany North
South AldiN
SaturnN A1
A2
S1
S2
AldiS A3 TurnoverClass
TG1 TG2 TG5 TA1 TA2 TransformPhiToSimpleHierarchy into a primitive simple hierarchy. The primitive simple hierarchies are merged to the resulting simple hierarchy HS12. We now transform HS12 and the next simple hierarchy HS3 to HS123 according to the previous described steps etc. Thus, at the end of HINTA, we get one simple hierarchy HS123..n. In the following, we describe the process in a more formal manner: The input hierarchy H is split into simple hierarchies HSi: H = U H S
i , where HSi is preferred to HSi+1.
i HINTA: HS = HINTA(H) According to the informal description of HINTA above, we transform a pair of simple hierarchies into one simple hierarchy, starting with the first two simple hierarchies in preference order.
H12 = Transform(HS1 ∪ HS2) The resulting simple hierarchy H12 and the next preferred simple hierarchy HS3 are transformed: 11-8 Transform is a recursive function, that transforms the first phi of H into a simple hierarchy HS and concatenates HS with the rest of the transformed phi’s by calling Transform again. It terminates, when H is already a phi, i.e., if the last phi of the original hierarchy instance is the input parameter.
The “∪” operator means, that for H1∪H2 the hierarchies H1 and H2 are concatenated via the existing edges of members of H1 and H2.
The “\” operator is a splitting of the hierarchies H1 and H2, To illustrate HINTA, we use the hierarchy instance H=(VH, EH) of Figure 4-1, where H contains two simple hierarchies H1S and H2S (see Example 4-5). We assume, that H1S is preferred to H2S. The resulting simple hierarchy HS is computed by: 11-9 HS= HINTA(H) The pair of simple hierarchies H1 and H2 is transformed by Transform(H1∪H2), where H1∪H2 is not a phi. (H1∪H2) consists of three phi, i.e., Hphi1, Hphi2 and Hphi3. Hp1 (of type phi1) is the root level without edges, because the root level does not have leaving edges.
Hp2 (of type phi1) consists of the members {Germany, Austria} and the corresponding edges to the root (see Figure 5-3 and Example 5-1).
Hp3 =(V, E) (of type phi2) consists of two alternative paths with shared leaf level Outlet (see Figure 5-3 and Example 5-1).
Now we transform Hp1, Hp2 and Hp3 to simple hierarchies: HS1=TransformPhiToSimpleHierarchy(Hp1) HS2=TransformPhiToSimpleHierarchy(Hp2) HS2=TransformPhiToSimpleHierarchy(Hp3) HS1 = ({Segment}, ∅}, i.e. the root without edges.
S H 2 = ({Germany, Austria}, {(Germany, Segment), (Austria, Segment)}, because Hp2 is a phi of type phi1, the edges of type 2 are deleted.
HS3 = (V, E): Hp3 is of type phi2 and we delete the edges {(A1, AldiN), (A2, AldiN), (S1, SaturnN), (S2, SaturnN), (A3, AldiS), (H1, HoferE), (H2, HoferE), (S4, SaturnE), (H3, HoferW), (H4, HoferW), (S5, SaturnW), (S6, SaturnW)} and the edges {(TG1, Germany), (TG2, Germany), (TG5, Germany), (TA1, Austria), (TA2, Austria)} (edges between leafs and the preferred hierarchy are deleted, because now the members of the non preferred hierarchy are directly dependent on the leafs). Figure 5-5 illustrates, which edges are deleted.
We delete members {TG1, TG2, TG5, TA1, TA2} and insert new members {TA11, TG21, TG51, TG22, TG23, TA21, TA11, TA12, TA13, TA13, TA22, TA14} and get the set of members: V = { A1, A2, S1, S2, A3, H1, H2, S4, H3, H4, S5, S6, AldiN, SaturnN, AldiS, HoferE, SaturnE, HoferW, SaturnW, North, South, East, West, TA11, TG21, TG51, TG22, TG23, TA21, TA11, TA12, TA13, TA13, TA22, TA14} We insert new edges of level TurnoverClass to Micromarket preserving hierarchical dependencies: {(A1, TG11), (TG11, AldiN), (A2, TG21), (TG21, AldiN), (S1, TG51), L
M
S
C1 (TG51, SaturnN), (S2, TG22), (TG22, SaturnN), (A3,TG23), …, (TA14, SaturnW)} After deleting and inserting, the edges are: E = {(A1, TG11), (A2, TG21), (S1, TG51), (S2, TG22), (A3, TG23), (H1, TA21), (H2, TA11), (S4, TA12), (H3, TA13), …, (North, Germany), (South, Germany), (East, Austria), (West, Austria)} The resulting simple hierarchy of HINTA is the union of HS1, HS2 and HS3, as illustrated in Figure 5-6. This section illustrates the benefit of HINTA in an example. Usually, the benefit of HINTA is as better as larger the hierarchies are. Due to graphical illustrations, however, only small hierarchies can be drawn. In Figure 5-7 we show a complex hierarchy with the levels H1=CountryState-Town and H2=Country-Category-Town, where Category characterizes the size of the towns (large, middle, small). Hierarchy Encoding is applied to H1, i.e., a predicate “Category=L” would include the leaves {T11, T13, T21, T23, T31, T34} or equivalently the dimIDs {00, 02, 10, 12, 20, 23}, i.e., 6 intervals include one single value. With a transformed hierarchy (as in Figure 5-8), we get three intervals [000, 001], [100, 101] and [200,201]. With these intervals, the query will be processed faster on the fact table. This section gives a short impact to the quality of HINTA. We consider a hierarchy such as in Figure 3-1, where one is the preferred hierarchy, the other is the non-preferred hierarchy. We use an encoding of the preferred hierarchy (EPH), an encoding of the non-preferred hierarchy (ENPH) and an encoding of the transformed hierarchy with HINTA (ETH).
Day
Figure 6-1: Time Hierarchy In general, no perfect linearization is possible for all simple hierarchies. However, due to the transformation algorithm, the preferred hierarchy still is encoded perfectly, i.e., a predicate (point restriction) on EPH resulting in one interval also will result in one interval for ETH, because the affected leaves are the leaves of a complete sub-tree. This is due to the higher priority of the preferred hierarchy (the levels of the preferred hierarchy usually are higher levels than the levels of the non-preferred hierarchy). Thus, no disadvantages in query execution will result from HINTA for such predicates.
The clustering of ETH compared to ENPH, however, is not optimal, and a predicate on a level of ENPH might result in a number of intervals instead of one interval. This number highly depends on the correlation of the two simple hierarchies: If the hierarchies are correlated in a large extent (e.g., for the time hierarchy in Figure 6-1 with the preferred hierarchy year – month – day), most restrictions such as year = 1999 and week = 33 will result in an interval on dimID for the transformed hierarchy year – month – week – day. 6
In this paper, we present a concept, how to represent hierarchies by directed acyclic typed graphs. We concentrate on complex hierarchies and describe HINTA, a method to linearize complex hierarchies by transforming them to simple hierarchies and thus allow hierarchical clustering on such hierarchies.
The quality of clustering depends on the correlation of the simple hierarchies. For query processing, predicates on hierarchy levels are mapped to intervals by an encoding that preserves hierarchical clustering.
Currently, in the EDITH project ([Edi01]), we are integrating encoding algorithms into the kernel of the relational DBMS TransBase ([Tra01]) and are investigating query processing algorithms and optimizer strategies to efficiently support these methods. Application partners will test the DBMS implementation. We are going to analyze HINTA by transforming complex real world hierarchies and compare clustering properties.
We thank Martin Zirkel and Robert Fenk for fruitful discussions for reading and correcting this paper. 7