In a multidimensional (MD) database, dimensions may be subject to semantic conditions that are not enforced by MD DBMSs or data warehouse applications. Strictness and homogeneity are possibly two of them; and are crucial for the efficiency and correctness of answering MD aggregate queries and updating materialized aggregate views. Dimensions may become inconsistent, i.e. non-strict or heterogeneous, as the result of update operations. As a methodology to restore consistency, we propose and investigate changes to the dimension schema, as an alternative to changes on the dimension instance. We introduce the notion of minimal structural repair, and establish that under certain conditions, a structural repair reduces the cost wrt changing the dimension instance. We also show that it allows for a correct rewriting of queries posed to the original MD model into queries in terms of the new schema. Finally, we show how query-scoped calculated members in MDX can be used to create virtual repairs that simulate structural repairs.
straints on dimension instances. In a strict dimension, every element of a category rolls up to at most one element in a same ancestor category.
In a homogeneous dimension, all elements in a category have the same structure. More precisely, if a category C has C as an ancestor category, then all elements of C must roll up to some element in C . The dimension instance in Figure 1 is not homogeneous, i.e. heterogeneous, because the element London does not roll up to any element in categories State or Province. It is also non-strict, because London rolls up to the two different elements, England and UK, in the Country category.
Dimension instances that do not satisfy strictness or homogeneity (or both) are said
to be inconsistent. Hence, the dimension in Figure 1 is inconsistent. Dimensions may
become inconsistent for several reasons, in particular, as the result of a poor design or a
series of update operations. Inconsistent dimensions reduce soundness and efficiency of
OLAP systems. In them it is not possible to assume that the summarizability property
holds [
To restore consistency, changes have to be made to the dimension schema and/or the
dimension instance. In accordance with the area of consistent query answering (CQA)
in relational databases [
As indicated above, inconsistency may be caused by a problematic dimension
schema. Therefore, changing the dimension instance may be only a temporary solution.
Future update operations will probably produce new inconsistencies. So, exploring and
considering structural changes, i.e. changes in the schema, is a natural way to go. This
is an idea that has been suggested in [
Structural repairs restrict changes to dimension instances by allowing changes that affect only the category lattice and the distribution of the data elements in different categories. In particular, there are no “data changes” (as in data repairs), in the sense that the data elements and also the edges between them remain. In the case of a ROLAP data warehouse (with relational schemas, like star or snow flake) fewer data changes on a dimension instance directly results in fewer changes on records in the underlying database.
We establish that any minimal structural repair enables query rewriting: Given a
query, Q, posed to the original, inconsistent MDDB D and any of its minimal repairs,
D , Q can be translated into a query Q to be posed to D , obtaining the same results
in terms of selected data elements and their respective aggregate values. In particular,
if in D some summarizability properties applied or “local” homogeneity and strictness
held (which, e.g. can be enforced by local semantic constraints [
Structural repairs can be used to solve both non-strictness and heterogeneity, and have major advantages wrt to other approaches, specially when dealing with heterogeneity. On the other hand, when fixing non-strictness, structural repairs have good properties wrt the number of changes when the parent elements in a same category involved in a violation of strictness (i.e. they have a descendant in common) do not have descendants in many different categories. In such undesirable cases, changing the parent category may have to be propagated to categories belonging to its lower subgraph, causing several additional changes (cf. Section 6). Thus, a data repair or a combination of data and structural repair may result in fewer overall changes.
Structural repairs may be virtually implemented through appropriate view
definitions, an idea we develop in this work. As a view definition language, we consider
MDX, the language commonly used to query MDDBs [
This paper is organized as follows: Section 2 presents the MD data model. Section 3 formalizes the notion of (minimal) structural repair. Section 4 discusses properties of an ideal repair and shows that, by satisfying certain conditions, a minimal structural repair will have those properties. Section 5 shows how virtual structural repairs can be created in MDX. Section 6 provides a discussion of previous work, a comparison between data repairs and structural repairs, directions for future work, and some concluding remarks. Proofs of results, additional examples, and a brief introduction to MDX can be found in an extended version.2
In this work we adopt as a basis the Hurtado-Mendelzon model of MDDBs [
CU = {City, State, Province, Country, All}. 3. EU ⊆ UE is a finite, non-empty set of “active” data elements. In the example,
EU = {LA, ..., all}. 4. LUC is the child/parent relationship between categories, i.e. edges between categories in the dimension schema. In the example, L UC ={(City, State), (State, Country), . . . , (Country, All)}. 1 Actually, all these claims still hold under slightly softer conditions than those imposed by the notion of minimal repair. 2 http://people.scs.carleton.ca/∼bertossi/papers/strucRep18Ext.pdf From a dimension S as above we can define its dimension schema structure: K(S) := UC , CU , LUC . We can also define its dimension instance: M (S) := U, E U , LUE, ECU . Loosely speaking, we can say that “M (S) is the instance for schema K(S)”.
For a structure S to represent a valid MDM, it has to satisfy the following basic MD conditions (BMDCs): (below ei and ci represent members of the universe and R ∗ denotes the transitive closure of a binary relation R): 1. CU ∩ EU = ∅. 2. LUC ⊆ CU × CU. 3. LUE ⊆ EU × EU. 4. EC U ⊆ EU × CU. 5. For all e1, e2, c1, c2: If (e1, e2) ∈ LUE and (e1, c1) ∈ ECU and (e2, c2) ∈ ECU, then (c1, c2) ∈ LUC. 6. For all c1: If c1 ∈ CU, then (c1, c1) ∈/ (LUC )∗. 7. For all e1: If e1 ∈ EU, then there exists c1 with (e1, c1) ∈ ECU. 8. For all c1, c2: If there is e with (e, c1) ∈ EC U and (e, c2) ∈ EC U , then c1 = c2. 9. For all c1, c2: c1 = c2 iff, for all e ∈ EU, it holds: (e, c1) ∈ ECU iff (e, c2) ∈ ECU .
Notice that from these conditions it follows that 2. an 3. are proper inclusions. Definition 1. Dimension S = U, C U , EU , LUC , LUE , ECU is: (a) Strict if, for all e1, e2, e3, c : If (e1, e2) ∈ (LUE)∗, (e1, e3) ∈ (LUE)∗, (e2, c) ∈ ECU , (e3, c) ∈ ECU , then e2 = e3. (b) Homogeneous if, for all e1, c1, c2 : If (e1, c1) ∈ ECU , (c1, c2) ∈ LUC , then there is e2, with (e2, c2) ∈ ECU and (e1, e2) ∈ LUE . (c) Consistent if it satisfies the two previous conditions; and inconsistent otherwise. 3
Structural Repairs Definition 2. A data repair for an inconsistent dimension S = U, C U , EU , LUC , LUE , U EC U is a structure S = U, CU , EU , LUC , LUE, EC that satisfies the dimension conditions and the BMDCs,4 and is strict and homogeneous.
Notice that S and S have the same universe, the same categories, and the same category links (but other relations may differ). We can see that, in order to obtain a data repair, one can only add or remove data elements, change links between elements or move elements between different categories. The following notion of structural repair (SR) is given in terms of a new MD structure, possibly with a new schema, and a mapping that establishes the correspondence between the original dimension and the new structure. Definition 3. A structural repair for an inconsistent dimension S = LUC , LUE , ECU is a pair S , g , with S a structure U, CU , EU , LUC , LUE , EC , with the following properties: (a) S is strict and homogeneous. (b) Elements cannot move U, C U , EU ,
U 3 We assume that in MDM all dimensions have this top category All with the single element all, to which all the other elements roll up. 4 In the following this will be implicity assumed. ⊆-incomparable with {e | (e, c ) ∈ EC
and c ∈ g(c)}). between categories that exist both in S and S : For all e, c1, c2, if (e, c1) ∈ ECU , (e, c2) ∈ ECU , c1 = c2, then {c1, c2} (CU ∩ CU ). (c) Any new category in S must have at least one data element. (d) g : C U → 2CU , the schema mapping, is a total function that maps each category of S to a set of categories in CU (which is finite in S ). (e) If c ∈ g(c), then c and c share at least one data element.
The role of g is to establish a relationship between the schemas of S and S . Notice that, for each category c, the set of its “elements”, i.e. {e | (e, c) ∈ EC U }, may be
U
This proposition can be proved by using a simple structural repair that essentially creates a new one-element category for each element in the dimension instance, and also links between the newly created categories whenever their single elements are connected in the original instance. Figure 4 illustrates this kind of structural repair as a third repair for the instance in Figure 1. 5 Isomorphic structural repairs, i.e. that differ only in the names of active categories, will treated as being the same repair.
Example 1. The following mapping is a schema mapping between the dimension of Figure 1 and the structural repair of Figure 2: g : City → {City1, City2}, State → {StateProv}, Province → {StateProv}, Country → {Country1, Country2}, All → {All}. Now we define minimal structural repairs (MSRs), as preferred repairs among the structural repairs. This requires comparing structural repairs. The data movement set, defined next, has useful properties for enabling this comparison (cf. Section 4).
Definition 4. Let S , g be an SR for dimension S, and c a category of S. (a) The data movement set of category c is defined by:
DMSet g(c) = {e | (e, c) ∈ ECU } c ∈g(c){e | (e, c ) ∈ EC }, where denotes the symmetric difference of two sets. (b) The overall data movement set between S and S is DMSetg(S, S ) := c∈CU DMSetg(c).
U Example 2. (example 1 cont.) For the schema mapping in the example: DMSet g(City) = ∅, DMSetg(State) = {BC, ON}, DMSet g(Province) = {California}, DMSetg(Country) = ∅, DMSet g(All) = ∅.
Intuitively, an MSR is a new dimension that is obtained by applying a minimal set of
changes to the schema of an inconsistent dimension. Inspired by the notion of
prioritized minimization [
S1, g1 ≤S S2, g2 iff DMSet g1 (S, S1) ⊆ DMSetg2 (S, S2) and
DMSet g1 (S, S1) = DMSetg2 (S, S2) ⇒ (CS CS1) ⊆ (CS CS2).
Here, CS , CS1 and CS2 denote the finite sets (C U ) of active categories for structures S, S1 and S2, respectively.
Definition 6. S1, g1 is a minimal structural repair (MSR) of dimension S iff it is an SR of S and there is no other SR S2, g2 for S, such that S2, g2 <S S1, g1 . (Here, as expected, u <S v means u ≤S v, but not v ≤S u.) Example 3. It can be shown that the structural repair of Figure 3 is an MSR for the inconsistent dimension of Figure 1, with the following schema mapping: g1 : City → {City1, City2, City3}, State → {State}, Province → {Province},
Country → {Country1, Country2}, All → {All}.
On the other hand, the structural repair of Figure 2 is not an MSR for any possible schema mapping. This is because for categories State and Province in the original dimension, there is no category (or set of categories) in this repair that contains exactly the data elements that belong to those two categories. Therefore, for any mapping g2, DMSet g2 (State) = ∅ and DMSet g2 (Province) = ∅. As a result, DMSet g2 (State) DMSet g1 (State). According to the definition of MSR, g 2 cannot be minimal.
Proposition 2. An inconsistent dimension always has a minimal structural repair. The following example shows that an inconsistent dimension may have multiple MSRs. Example 4. The structural repair of Figure 5, that is obtained by swapping the data elements England and UK in the structural repair of Figure 3, shows another minimal structural repair for the inconsistent dimension of Figure 1. These two minimal repairs are not isomorphic. If the notion of MSR is applied to a consistent dimension S, then S, id is one of its MSRs, with id : c → {c}, but not necessarily the only one. This is because we can have categories with no members in a consistent dimension, and changing the links that are attached to them results in different minimal repairs. To ensure that a consistent dimension is its only MSR, we have to add an extra condition in the definition of minimal repair, to restrict changes on the set of category links, i.e. on L UC .
Our next result states two properties of MSRs that will be useful in Section 4. Theorem 1. (a) If S , g is an MSR of dimension S, then for every category c in S, DMSet g(c) = ∅. (b) In an MSR, if g(c) = {c1, . . . , cn}, then, for all e with U (e, c) ∈ EC U , there is a ci, such that (e, ci) ∈ EC .
Notice that the inverse of the implication in (a) does not necessarily hold. The example in Figure 4 shows an SR with an empty data movement set that is not minimal. 4
Properties of Structural Repairs
An OLAP system is usually modeled by a three level architecture consisting of a data
warehouse server, a query client and a data cube engine [
And the new queries should return similar outputs in terms of selected data elements and their respective aggregate values (cf. Section 4.1). 3. If the original structure allows summarizations over existing cube views, to compute new cube views, similar summarizations should also be possible in the repaired dimension (cf. Section 4.2).
By definition, structural repairs restrict changes to data so that elements and links in
the dimension instance do not change at all. Therefore, the first requirement is strictly
satisfied by the use of structural repairs. In Sections 4.1 and 4.2 we will focus on how
structural repairs perform wrt the two other requirements.
4.1 Rewritability of cube views
The most common aggregate queries in DWHs are those that perform grouping by the
values of a set of attributes (i.e. categories), and return a single aggregate value per
group. These aggregate queries are also known as cube views [
Now, a cube view (query) at granularity G = c 1, ..., cn (a list of active categories) is denoted by CVG, and is expressed as:
SWFEHRLEOERMCETT,cocRnjbcd,jji.,ti..o..n.csRnbc,nnf(a) luHepverereel,lcacatijtoe,.gn.os.rRycbcunjjn,ad.r.ee.racRttibcr)nin,bTu(wtieshset(hrceeatefeaagccohtrtibaeibs)liesoatfhtbahotetatrsoosmlol--ciates numerical values (measures) to elements in b i,
GROUP BY cj , . . . cn and f is one of min, max, count, sum, avg, applied to fact measure a. The result of this cube view, denoted result (CV G), is the set of tuples {t1, ..., tr} with tk = ejk, ..., enk, ak . The non-aggregate portion e jk, . . . , enk of tuple tk contains the values for the attributes in the SELECT clause (which are the same as in the GROUP BY). Here, eik is a data element that belongs to category c i, and ak is the value of aggregate function f for this tuple.
Definition 7. A cube view CVG on categories of dimension S is rewritable on an SR S , if there exists a cube view CVG on categories of S , such that result (CVG) = result (CVG ). CVG is called a rewriting of CVG in S .
Theorem 2. A cube view CV G at granularity G = c1, ..., cn on dimension S is rewritable over a structural repair S , g if the data movement set for categories c 1, . . . , cn is empty. In particular, cube views are always rewritable over MSRs. Notice that in the theorem the inverse implication may not hold: Even for repairs with non-empty data movement set, some queries may be rewritable.
Example 5. Consider the dimension of Figure 1 and a cube view (a) below for this dimension. Assume that Facts is the fact table, and Sales is a fact measure. This cube view is not rewritable on the structural repair of Figure 2, because DMSet g (Province) = ∅. On the other hand, for the structural repair of Figure 3 (that has empty data movement set for all categories), the cube view in (b) below is a rewriting. It is obtained by replacing RCity Province.
Province by RCity2 (a) SELECT Province, SUM(Sales)(b) SELECT Province, SUM(Sales) FROM Facts, RCPirtoyvince FROM Facts, RPCriotvyi2nce
GROUP BY Province GROUP BY Province A common technique for speeding up OLAP query processing is to pre-compute some cube views and use them for the derivation (or answering) of other cube views. This approach to query answering is correct under the so-called summarizability property (cf. Example 6). It is globally guaranteed by the consistency conditions on the dimension schema. However, in the case of inconsistency, there could still be localized summarizability. Either way, ideally these summarizability properties should be preserved under structural repairs.
Example 6. Consider the dimension of Figure 1 and a pre-computed cube view CV Country in (a) below for category Country. Also, consider cube view (b) below that uses CVCountry to derive aggregate values for category All: (a) SELECT Country, SUM(Sales) AS S (b) SELECT All, SUM(S) FROM Facts, RCCoiutnytry FROM CVCountry, RACloluntry GROUP BY Country GROUP BY All This derivation will produce correct results, only if category All is summarizable from category Country. In the dimension of Figure 1, this summarizability property does not hold. This is because in the instance of this dimension, element London will be considered twice as a descendant of all (via England and UK).
Cube view CVG1 at granularity G1 = c1, ..., cj depends on cube view CV G2 at
granularity G2 = ck, ..., cn iff CVG1 can be answered using the result of CV G2 [
Definition 8. An SR S , g for dimension S preserves summarizability of category c over categories {c1, ..., cn} (all in S) iff every c ∈ g(c) is summarizable from n k=1 g(ck) in S .
Theorem 3. An SR S , g for dimension S preserves summarizability of category c over categories {c1, ..., cn} if DMSet g(c) = DMSet g(c1) = · · · = DMSet g(cn) = ∅. In particular, minimal structural repairs preserve all the summarizability properties. Example 7. For the inconsistent dimension of Figure 1, consider the structural repair of Figure 3, with the schema mapping g : City → {City1, City2, City3}, State → {State}, Province → {Province},
Country → {Country1, Country2}, All → {All}.
Since g has an empty data movement set for every category, we expect it to preserve summarizability properties that hold in the original dimension. For example, Province is summarizable from City in the dimension in Figure 1. In the MSR in Figure 3, Province is summarizable from {City1,City2,City3}. Notice in the previous example that, in addition to the preservation of existing summarizability properties, the structural repair is also adding extra summarizibility properties. For instance, category All was not summarizable from City through category Country in the original dimension, but it is now summarizable from {City1,City2, City3} through category Country1. This is achieved through the newly imposed strictness and homogeneity conditions. 5
Virtual Repairs in MDX An important problem that needs to be addressed is how to implement structural repairs in a way that is transparent to users of MDDBs. As discussed in previous sections, one advantage of using structural repairs instead of data repairs is that the former remove inconsistencies without having to change the underlying database.
One of the interesting features of the MDX query language is the ability to define query-scoped calculated members. A query-scoped calculated member is a virtual object defined in terms of other existing objects by means of a query. For example, a new category (or data element) in terms of other existing categories (data elements, resp.), etc. They are generated using the WITH construct in MDX: WITH {MEMBER|SET} MemberIdentifier AS ’member-formula’ SELECT ...
This template creates a new calculated member (or set of members) that is defined by the MDX expression ’member-formula’. {MEMBER|SET} indicates if the newly created object is an element or a category, resp.
Using this feature, structural repairs can be virtually created, without any need for materializing new data or accessing the database in order to generate database views. This is specially useful if the structural repair of choice is going to be materialized at some point, after some exploratory analysis.
Example 8. The following MDX query creates a query-scoped calculated category StateProv, as the union of categories State and Province. It then selects the summarized value of measure Sales for the members in this new category. Here, SalesCube is the base cube (or fact table):
WITH SET [StateProv] AS
’[State].MEMBERS + [Province].MEMBERS’ SELECT [Measures].[Sales] ON AXIS(0),
[StateProv] ON AXIS(1)
FROM [SalesCube] Structural repairs (or portions of them) can be generated using this form of view definitions, as virtual repairs. In them, new categories are defined as calculated members. Virtual repairs can be used to test how structural changes will affect existing queries before making the transition to the new MD model.
Example 9. (example 8 cont.) Consider the structural repair of Figure 2. The given MDX query defines StateProv, the new category in the structural repair of Figure 2. It contains the elements in the union of categories State and Province.
Research on repairing inconsistent dimensions has focused mainly on modifying data elements. Here we introduced and investigated the notion of structural repair, as an alternative to data repair. Structural repairs restrict changes to the dimension instance by only allowing changes that affect the dimension schema and the organization of elements in different categories. We defined the notion of minimal structural repair and proved that, by having a minimal data movement set, it enables the rewriting of queries posed to the original multidimensional model as queries to be posed to a repair. The rewritten query the same results in terms of selected data elements and their respective aggregate values.
The notion of (data) repair was introduced in [
In [
In [
An important drawback of data repairs is that they manipulate the dimension instance, i.e. the data. In case the MDDB is implemented on a relational DB, this results in changes in records, which users may find undesirable. In contrast, structural repairs can be implemented without the need to change the underlying database, through view definitions.
Another problem with data repairs is that resolving heterogeneity may require introducing redundant NULL data values in the dimension instance. Those values have to be proliferated along the path of ancestor categories. The alternative approach for removing heterogeneity that is based on insertions of new links has the problem of possibly introducing new sources of non-strictness, which have to be resolved. This may introduce multiple changes in the dimension instance.
Fixing non-strictness via structural repairs has good properties in terms of the number of changes when the parent elements in a same category involved in a violation of strictness (i.e. they have a descendant in common) do not have descendants in many different categories. In the opposite case, changing the parent category may have to be propagated to categories belonging to its lower subgraph, causing several additional changes, as shown in the next example.
(a) A non-strict dimension (b) SR causing multiple changes
Fig. 6: Structural repairs and non-strictness Example 10. Consider the non-strict dimension of Figure 6a, where element e2 rolls up to two different elements, e7 and e8, in category C4. Here, e7 and e8 have descendants from three different categories in their subgraph. As shown in Figure 6b, a structural repair forces many changes in the dimension schema. Using a data repair or a combination of a data and a structural repair may result in fewer overall changes. Inconsistencies can be resolved by combining (the ideas behind) structural and data repairs. In some cases, that still have to be properly characterized, taking advantage of both approaches for resolving different local inconsistencies may produce better results in terms of number of changes. This is illustrated in the next example. (a) An inconsistent dimension (b) A repair that changes the schema and instance
Fig. 7: Combining structural repairs and data repairs Example 11. Figure 7a shows an inconsistent dimension. Restriction to pure data repairs will require applying multiple data and link changes. One way is to add at least five new and different NULL elements and ten new links, to resolve heterogeneity; and also remove the link between e3 and e10, to resolve non-strictness. On the other hand, using a pure structural repair requires introducing at least four new categories. As can be seen in Figure 7b, a combination of structural and data changes provides a solution that involves fewer changes (adding two categories in the dimension schema and removing a single link in the dimension instance).
There are still many issues to be investigate around structural repairs, and also around their non-trivial combination with data repairs. They are the subject of ongoing research. In this work we have not developed a notion of consistent answers to queries. This is left for future research.
Our notion of a minimal structural repair can be extended with priorities imposed
on certain categories (or different levels in the lattice) in the dimension schema. Higher
priorities can be assigned to categories that are queried more often or contain data
elements that are more sensitive to change. Multidimensional integrity constraints on the
schema [
In this work we have also showed how query-scoped calculated members in MDX can be used to create virtual structural repairs. This can be seen as a way of implementing view-based (structural) repairs. We have experimented with this approach on top of the IBM Cognos 8 Business Intelligence system, which is also being used for testing the performance of structural repairs. Reporting the results is part of the future work.