Discovering dependencies in data is a well-know problem in database theory. The most common rules are Functional Dependencies (FDs), Conditional Functional Dependencies (CFDs) and Association Rules (ARs). Many tools can display those rules as lists, but those lists are often too long for inspection by users. We propose a new way to display and navigate through those rules. Display is based on On-Line Analytical Processing (OLAP), presenting a set of rules as a cube, where dimensions correspond to the premises of rules. Cubes reflect the hierarchy that exists between FDs, CFDs and ARs. Navigation is based on a lattice, where nodes are OLAP views, and edges are OLAP navigation links, and guides users from cube to cube. We present an illustrative example with the help of our prototype.
Discovering dependencies in data is a well-know problem in database theory. Using dependency rules can help to prevent redundancy, to optimize queries and to avoid update errors. There are many softwares for computing dependency rules in a table. They generally provide the rules as a list. The main problem for users is to find the relevant information in those lists. Therefore, users need tools to navigate among them, and to check them. In this paper, we present how to create views over a table, such that users are able to visualize rules. Then we present how to guide users to navigate from a view to another.
We study the discovery of the following kinds of rules. Functional
Dependencies (FDs) [
Association Rules (ARs) [
The number of rules extracted from a table is often too high. We must
therefore provide to the user synthetic views showing a subset of rules. In a number
of works, those views are defined by premises and conclusion [
The number of different cubes can be too high to vizualize them all.
Therefore, users need tools to navigate from cube to cube. We relate this work to
Logical Information Systems (LIS) [
The main motivation for this paper is to demonstrate that OLAP offers a good support to display and navigate the dependency rules. First we introduce the concepts and definitions, along with illustrative examples, that are needed in our study (Section 2). Next we present how to visualize dependency rules in a cube (Section 3). Then we present how to navigate from cube to cube (Section 4). Finally, we detail an example of navigation (Section 5), and conclude (Section 6). 2
A relation, as in databases, is comparable to a many-valued context. A relation
schema R is defined by a set of attributes Attr(R). The domain of each attribute
A ∈ Attr(R) is denoted by Dom(A). An instance of a relation schema R, a
relation r, is a set of transactions. Each transaction t maps a value to each
attribute. The notation t[X] represents the values of the transaction t, for the
Seller
J ohn
Abby
Abby
Abby
Abby
J im
Bob
J ohn
J im
Bob
attribute sequence X. Table 1 shows the example relation re, which is an instance
of Re and contains a set of sales. This relation is extracted from [
In this article, we only study dependency rules whose conclusion has a single
attribute. A Functional Dependency (FD) [
A FD X → Y , with X ⊆ Attr(R) and Y ∈ Attr(R), is valid on r if ∀t1, t2 ∈ r, (t1[X] = t2[X]) ⇒ (t1[Y ] = t2[Y ]).
A Conditional Functional Dependency (CFDs) [
An Association Rule (AR) [
Huhtala et al. [
X-complete. Applying a closure operator, it is possible to form FDs. The
Xcomplete partition lattice consists of concepts which represent the partitions,
ordered by FD and labelled to find CFD. Medina and Nourine [
Codd introduced the concept of On-Line Analytical Processing (OLAP) [
The main problem of OLAP is that the navigation space is restricted by the
starting cube. For instance, OLAP users can neither change the measure (e.g.,
set the store as measure), nor add a dimension (e.g., add a seller dimension).
A request to the database administrator is necessary to extract a new starting
cube. Some authors present an OLAP model that overcomes this limitation [
We study OLAP because of the representation of a cube. Indeed, each cell of a cube represents a transaction or a set of transactions, ordered in a cube structure. The mining of FD implies to check, for any combination of the premise values, if the conclusion value is the same. The cube structure presents all combinations of premise values. 3
In our mining of dependency rules, we introduced OLAP, because of the similarity between the form premises → conclusion of the dependency rules, and the
Date 01/09 01/16 01/23 02/06 02/13 02/20 02/27 {{J ohn}} {{Abby, Abby}} {{Abby, J im}} {{Bob}} {{J ohn}} {{J im}} {{Bob}} form dimensions → measure of the cubes. In order to extract rules from a cube, we need to project the relation into a cube. 3.1
A cube actually forms a particular view of a relation. The main difference is the distinction between dimensions and the measure, which does not exist in a relation. We use this distinction to form dependency rules. For each transaction of the relation, we place the measure value in the cell of the cube corresponding to the dimension values. The measure values of each cell are usually aggregated. In our study, we retain the measure values as a multiset, because we are interested in dependency rules. Therefore, a cube is defined by a total function c that returns for each cell a multiset of measure values. Thereafter, we consider that an attribute has the same domain in the relation schema and the cube schema. Definition 2 (Projection of a relation into a cube). Let r be a relation with attributes Attr(r). A cube c is obtained by the projection of the relation r on dimensions Dim(c) = (D1, . . . , Dp) such that Di ∈ Attr(r) for i ∈ [1, p], and on the measure M eas(c) = Dq ∈ Attr(r). The domain of the dimensions are the same as the domain of their corresponding attributes in the relation. The domain of the measure M eas(Dq) is made of multisets over Dom(Dq). The cube c is defined by (the double curly braces denote multisets): c(b0, . . . , bp) = {{bq|t ∈ r, (t[D1] = b0) ∧ . . . ∧ (t[Dp] = bp) ∧ (t[Dq] = bq)}}.
For example, Table 2 shows the projection ce of re, where the dimensions are Dim(ce) = (Date) and the measure is M eas(ce) = Seller. The result of the projection is like a traditional OLAP cube, but data are not aggregated. The advantages are that any kind of value can be studied (e.g. strings), and there is no information loss for rule visualization.
Now we show that FDs, CFDs and exact ARs can be visually found in the relation projection (cube), and that the hierarchy between those rules is respected. Indeed, a cell of the cube at coordinates D1 = d1, . . . , Dp = dp contains the multiset of values taken by the attribute Dq, in all transactions such that D1 = d1, . . . , Dp = dp. The definition of exact ARs D1 = d1 ∧ . . . ∧ Dp = dp → Dq = dq is that for any transaction such that D1 = d1 ∧ . . . ∧ Dp = dp, then Dq = dq. Then, in this cell, if there is only one value in the multiset (e.g. {{a, a}}), there is an exact AR at this coordinate. If there is more than one value (e.g. {{a, a, b}}), the AR is approximate. Therefore, the cube is a synthetic view of all the possible ARs following the dimensions and measure.
Theorem 1 (Association Rule in the cube). Let d = (D1 = b1)∧. . .∧(Dp = bp) → (Dq = bq) be an AR, and c be a cube with Dim(c) = (D1, . . . , Dp), and M eas(c) = Dq. The support of this rule is equal to the number of elements that have value bq in the cell of c at coordinates (b1, . . . , bp):
sup(d, r) = k{{b|b ∈ c(b1, . . . , bp) ∧ b = bq}}k.
The confidence is equal to the ratio of elements bq on all the elements on the cell at coordinates (b1, . . . , bp): conf (d, r) =
sup(d, r) kc(b1, . . . , bp)k .
There exists a hierarchy between FDs, CFDs and ARs [
The definition of a CFD in the cube is between the definition of an AR and
a FD. If each cell in a subset of the cube (e.g. a line or a square subset) contains
one or zero element in its multiset, then there is a valid CFD, whose pattern
tableau covers the subset of the cube. The hierarchy established by [
For example, Table 2 shows dependency rules. We note that each cell except {{Abby, J im}} has one distinct value. This implies that there are ARs at those cells (e.g. Date = 01/06 → Seller = Abby), and a CFD whose pattern covers those cells ((Date → Seller, {(01/09, , , , , ), . . .})). On the contrary, no FD can be found from this view. 3.2
A major strength of OLAP is the definition of taxonomies on the dimensions.
Indeed, the dimension values are hierarchically organized, according to several
levels of granularity. In traditional OLAP, an aggregation function can synthesize
the grouped data, using a function (e.g., sum, average, count). Han and Fu [
Definition 3 (Dimension taxonomy). Let D be a dimension. This dimension, at granularity level δ, is denoted by D ∼ δ. A dimension taxonomy on D is defined by a set of n ordered levels Δ = {1, . . . , n} (1 is the most general level), and a set of subsumption axioms bi ⊑ bj (i.e., bi is more specific than bj ), with bi ∈ Dom(D ∼ i), bj ∈ Dom(D ∼ j), and j = i − 1. The levels form a partition of the dimension domain, i.e., Dom(D) = ∪i∈nDom(D ∼ i) and ∀i, j ∈ 1 . . . n, Dom(D ∼ i) ∩ Dom(D ∼ j) = ∅. To get a more concise notation, a dimension without taxonomy keeps its old notation.
Definition 4 (Projection of a relation in a cube with taxonomies). Let r be a relation with attributes Attr(r). A cube c is the projection of the relation with taxonomies, on dimensions Dim(c) = (D1, . . . , Dp) such that Di ∈ Attr(r), and a set of levels (δ1, . . . , δp) for each dimension, and a measure M eas(c) = Dq, with Dq ∈ Attr(r) and δq a level of Dq. The domains of elements of Dim(c) are equivalent to the domains of the corresponding elements of Dom(Di ∼ δi). The domain of M eas(c) is equivalent to the multiset of Dom(Dq ∼ δq). The projected cube c is defined by:
c(b′1, . . . , b′p) = {{b′q|t ∈ r, ∀k ∈ 1 . . . p, q, (t[Dk] = bk ∧ bk ⊑ b′k)}}.
This definition allows users to create new cubes, at several granularity levels. This implies that more dependency rules can be extracted from the relation. For instance, Table 3 shows the result of the projection of re in cet, with the
Seller
J ohn Abby J im Bob dimensions Dim(cet) = (Date ∼ δmonth, Seller) and the measure M eas(cet) = N umber. We can then deduce that the CFD ϕ2 = (Date ∼ δmonth ∧ Seller → N umber, {( , J ohn, , , , ), ( , J im, , , , )}) is valid on re. 4
In the previous section we show that a projection of a relation into a cube allows to see the FDs, CFDs and ARs, following the dimensions and the measure of the cube. To give access to all dependency rules, we need to give access to cubes for all dimension combinations, granularity levels, and measures.
To navigate from cube to cube, changing granularity levels, adding or removing dimensions, we use OLAP navigation links. Traditionally, OLAP systems do not have an add navigation link, to add a dimension (because of the initial cube problem). We add this navigation link. The set of navigation links is: Roll-up (dimension / measure) Traditionnaly, a roll-up changes the granularity level of a dimension. Our choice is to consider the measure as a special dimension, then a roll-up can here be used on the measure. Formally, a roll-up on D ∼ δi will modify it into D ∼ (δi−1).
Drill-down (dimension / measure) Such as roll-up, drill-down changes the granularity level of a dimension or a measure. A drill-down on D ∼ δi will modify it into D ∼ (δi+1).
Delete Deletes a dimension. Delete a dimension is a special case of roll-up (at the top level).
Add Adds a dimension.
Those six navigation links change the number of values in the chosen dimension, and hence the visible dependency rules. A roll-up (resp. drill-down) on a dimension increases (resp. decreases) the number of values in this dimension. This means that the multisets of measure values are splitted (resp. regrouped), which promotes the appearance (resp. disappearance) of rules. Figure 2 shows the set of accessible navigation links. The effect of each navigation link is given for two starting cubes: one verifying an FD, and another not verifying an FD. We detail the two phenomena explained above.
The first phenomena is the splitting of the measure values (e.g. when the user adds a dimension or drill-down a dimension). This splitting is important in the mining of dependency rules. Indeed, we see that when values are dispatched into separate cells, they have less chance to be with different values, then there is a greater chance to have an AR or a FD. There is a similar phenomenon when mining rules directly from relations. However, one has to be careful neither to over-increase the granularity of the dimensions, nor to over-reduce the granularity of the measure. Indeed, rules have more chance to appear, but their quality and precision decrease.
The second phenomena is the regroupment of the measure values (e.g. when the user deletes a dimension or roll-up a dimension). If equal values are grouped into a same cell, this does not change the rule at this coordinate. On the contrary, if different values are grouped into a same cell, this breaks the dependency rule at this coordinate. Figure 2 shows the two cases of value regroupments. This figure helps the user to choose navigation links, to find new rules with the help of OLAP navigation links. 5
In this section, we present our prototype Abilis and we show its use with the
example re. Abilis is a web application based on Logical Information System
(LIS) [
We navigate with the example re, adding a taxonomy on each dimension. Dates are organized by day and month; stores are organized by city and region; products are organized by article and by type. We search for dependency rules between products, numbers and stores. Table 4 presents the steps of our navigation scenario. Figure 3 shows our prototype at step 8. It contains (1) the
Step Dimensions Measure Query 0 () / All 1 () N umber All 2 (P roduct) N umber All 3 (P roduct) N umber not(P roduct = “AT V ′′) 4 (P roduct) Store not(P roduct = “AT V ′′) 5 (P roduct) Store All 6 (P roduct, N umber) Store All 7 (P roduct, N umber) Store ∼ δRegion All 8 (P roduct ∼ δT ype, N umber) Store ∼ δRegion All 9 (P roduct ∼ δT ype) Store ∼ δRegion All current query (All means all the transactions), (2) the navigation tree (to add a dimension or refine the query) and (3) the view, displayed as a cube. Each cell of the cube shows the multiset of measure values as a tag cloud. For example, (4) shows that the support of the rule P roduct ∼ δT ype = Bike ∧ N umber = 3 → Store ∼ δRegion is 2. The size of an item in a cell depends on the support of the rule.
The first view presents a single cell containing the 10 transactions (0). We set N umber as the measure (1). The cube has always one cell, and displays the proportion of the seven different number values (e.g. there is two sales with N umber = 4). We add a dimension P roduct (2), to check dependencies like P roduct → N umber. The resulting cube partitions the numbers into six cells, one per product. Each case except ATVs contains one number value. We select all transactions such that the product is not ATV (3). All cells of the resulting cube contains one number value. Therefore, there is a CFD (P roduct → N umber, Tp), where Tp contains cells where the product is not ATV.
Now we want to work with the store locations. We change the measure to
Store (4) then we select all transactions (5). The resulting cube does not contain
a FD. Figure 2 shows that adding a dimension helps to have more dependencies.
We then add N umber as a new dimension (6). The resulting cube has two
dimensions and shows the CFD (P roduct, N umber → Store, Tp) with Tp containing
all the transactions except those where N umber = 3 and P roduct = BM X.
Indeed, this cell contains {{Quimper, Brest}}. Those two cities being in the same
region, we change the granularity level of the measure to Store ∼ δ Region
(7). The resulting cube shows a FD, because each cell contains zero or one
region. Figure 2 shows two possibilities of a roll-up in a dimension, with a
starting cube containing FD: either the FD is still valid, or it is made invalid. We
roll-up the P roduct dimension to P roduct ∼ δT ype (8). The FD is still valid.
Finally, we see that in each column of the current cube, there is only one
region. Then we delete the dimension N umber (9). The final cube shows a FD
P roduct ∼ δT ype → Store ∼ δRegion.
In this paper, we show that projecting a relation into a cube brings relevant
properties. First, Association Rules, Conditional Functional Dependencies and
Functional Dependencies are made visible in this synthetic view, through the
number of values in each cell. This is due to the similarity between the form
premises → conclusion of the dependency rules, and the form dimensions →
measure of the rules. Then, we show that the hierarchy established in [
A cube is a representation of a subset of all rules that can be extracted from a relation. We use the conventional OLAP navigation links to allow users to navigate from cube to cube, to add or to remove dimensions, or to change the granularity levels. This paper shows how to guide the user to choose navigation links. The navigation links show that some operators have a predictable behavior about the appearance or disappearance of rules.