A data warehouse is an integrated and timevarying collection of data derived from operational data and primarily used in strategic decision making by means of online analytical processing (OLAP) techniques. Although it is generally agreed that warehouse design is a non-trivial problem and that multidimensional data models and star or snowflake schemata are relevant in this context, hardly any methods exist to date for deriving such a schema from an operational database. In this paper, we fill this gap by showing how to systematically derive a conceptual warehouse schema that is even in generalized multidimensional normal form.
A data warehouse is generally understood as an integrated and time-varying collection of data primarily used in strategic decision making by means of online analytical processing (OLAP) techniques. It is essentially a database that stores integrated, often historical, and aggregated information extracted from multiple, heterogeneous, autonomous, and distributed information sources. Although it is generally agreed that warehouse design is a non-trivial problem and that multidimensional data models and star or snowflake schemata are relevant in this context, hardly any (M. Jeusfeld, H. Shu, M. Staudt, G. Vossen, eds.) http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-28/ methods exist to date for deriving such a schema from an operational database. In this paper, we recall the notion of multidimensional normal form (MNF) [LAW98] as a means to describe “good” warehouse schemata, and we show how to systematically derive a conceptual warehouse schema in MNF from a given operational schema.
Traditional database design methods [BCN92, Vos99] structure the design process into a sequence of phases or steps. It is common to start with requirements analysis and specification, then do conceptual design, then logical design, and finally physical design; this broad description can be refined in a variety of ways. As a central issue during a design process, a conceptual schema for the database under design is established which is then transformed into the “language of a logical data model as the basis for physical implementation. For data warehouses, no corresponding methodology is yet in sight, although there is a large body of literature that discusses how to derive schemas based on intuitive principles. We remedy this situation by presenting a method for conceptual warehouse design that is in line with traditional database design, and that fits into a modeling process which follows classical approaches. An important point for our exposition is that traditional design methods have clearly defined goals and objectives, such as completeness w.r.t. a coverage of the underlying application, minimality of resulting schemata, freedom of redundancies, readability, etc. Some of these requirements can even be made formally precise. Most notably, relational dependency theory provides insight to understanding the reasons for redundancies in database relations, and formalizes normal forms and normalization as a way to avoid them; moreover, there are algorithmic approaches (such as the synthesis algorithm [Vos99]) for constructing normalized schemata.
For two reasons, the above is in remarkable contrast with what can be called warehouse design. First, current practice in data warehousing and its applications marks a radical departure from the principles of normalized schema design. Indeed, a common understanding of a “welldesigned” warehouse schema is that the schema under consideration should have the form of a “star”, i.e., it should consist of a central fact table that contains the facts of interest to an OLAP application, and that is connected to a number of dimension tables through referential integrity constraints based on the various dimension keys. Since dimensions can be composed of attribute hierarchies, it is often the case that dimension tables are unnormalized, and their normalization results in what is known as a snowflake schema. As an example, the conceptual schema shown in Figure 1 may be perceived as a conceptual snowflake schema that corresponds to the operational schema of Figure 2. Second, the research community has not been paying too much attention so far to (a) developing complete design methods for data warehouses in general or for conceptual design in particular, and (b) establishing guidelines for good schema design or integrity constraints within the context of multidimensional models. As a result, there appears to be a discrepancy between traditional database design as applied to operational databases, and the design principles that apply to data warehouses.
We remedy this situation by presenting a phase-oriented design process for data warehouses that is modeled after the traditional design process, where we use an example from the banking domain as our running example. Concretely, we will show how to obtain the warehouse schema shown in Figure 1 from the conceptual operational database schema in Figure 2. The most important phase, the phase of conceptual design, has to sort out dimensions, corresponding dimension hierarchies, and measures, and has to determine which attribute from the underlying database(s) belongs where. Our contribution here is threefold: First, we establish guidelines for answering the question of whether an attribute is a dimension level or a property attribute. Second, we propose a graphical formalism for conceptual warehouse design that captures this distinction in an appropriate way. Third, we show how generalized multidimensional normal form (GMNF), originally proposed in [LAW98], can be obtained for a warehouse schema under design.
The organization of this paper is as follows: In Section 2, we briefly recall the database design process, and we review previous approaches on warehouse design and normal forms for warehouse schemata. We then introduce necessary terminology in Section 3, before we propose and illustrate our approach to conceptual warehouse design in Section 4. Afterwards, we show in Section 5 that our design method does indeed produce schemata in GMNF. Finally, concluding remarks and plans for future research appear in Section 6. 2
Database design, i.e., the task of mapping a given realworld application to the formal data model of a given database management system, is ia well-understood process; following [BCN92], database design can roughly be seen as being done in four steps, with the result of a database schema which can be processed by a database management system. This process comprises the phases requirements analysis, conceptual schema design, logical schema design, and physical schema design.
Concerning data warehouse design, there is a general agreement that at least a conceptual or logical modeling activity should precede the actual implementation [WB97, AGS97, CT98, GMR98]. Typically, the modeling activity is based on a multidimensional model (see [BSHD98, VS99, PJ99] for comparisons of various multidimensional models), whereas the implementation is carried out either within relational or multidimensional databases [CD97].
However, most of these models were developed without an embedding into a design process and thus without guidelines on how to use them or what to do with the resulting schemata. Notable exceptions in this respect are the approaches of [CT98] and [GR98], which we summarize next.
In [CT98] a design method is presented that starts from an existing E/R schema, derives a multidimensional schema, and provides implementations in terms of relational tables as well as multidimensional arrays. The derivation of the multidimensional schema is structured into the steps (1) identification of facts and dimensions, (2) restructuring of the E/R schema, (3) derivation of a dimensional graph, and (4) translation into the multidimensional model. In the first step, facts along with their measures have to be selected, and afterwards dimensions for a fact are identified by navigating the schema. Then, in the second step, the initial E/R schema is restructured in order to express facts and dimensions explicitly, thus arriving at a schema that can be mapped to the multidimensional model. From this point on, the remaining steps provide natural translations of the E/R schema into an multidimensional schema and then into a target database schema.
The work of [GR98] presents a complete warehouse design method which resembles the traditional database design and consists of the following steps: (1) analysis of the information system, (2) requirement specification, (3) conceptual design (following the method of [GMR98]), (4) workload refinement and schema validation, (5) logical design, (6) physical design. We note here that the design of a conceptual schema is carried out by producing a so-called fact schema for each fact, which, following [GMR98], can be derived from an E/R schema using an algorithmic procedure, which starting from facts navigates through the schema along x-to-one relationships in order to determine dimensions and their hierarchies.
Concerning these two approaches, we critically remark the following. In [CT98], conceptual and logical design are mixed, and a “logical” multidimensional model is presented. We argue (in accordance with, e.g., [WB97]) that 6-2 ac countcustName custAge
orgID branch orgGroup businessec tor tim e effectiveDay month quarter
year the conceptual design should be independent of the target database system, whereas the logical design should be tailored towards the chosen target system (here: relational or multidimensional database system). As a consequence, what is called logical design in [CT98] should actually be called conceptual design instead, and the implementation activity of [CT98] should be divided into a logical and a physical design phase, as in [GR98]. Moreover, the crucial first two steps of [CT98] are presented by examples only, and remain rather vague. In contrast, [GR98] contains an algorithmic procedure to perform the corresponding activities. However, neither approach provides any formal justification for the applied method, and nor does it supply criteria according to which schema quality could be measured.
In summary, well-established design phases for multidimensional databases are still missing, and while normal forms have a long tradition in the area of relational databases as guidelines for good schema design, research on quality factors for multidimensional database schemata seems to have started only recently. Indeed, the work presented in [LS97] can be regarded as a first step in this respect. The authors argue that summarizability, i.e., guaranteed correctness of aggregation results, is of most importance for OLAP queries. Hence, any multidimensional schema should be set up in such a way that summarizability is obtained to the highest possible degree. Moreover, if summarizability is violated along certain aggregation paths then the schema should express this constraint clearly. Finally, [LS97] provides criteria that imply summarizability.
Following and extending this line of thought, [LAW98] defines the multidimensional normal form (MNF) of multidimensional schemata, which guarantees summarizability within one-dimensional contexts. However, [LAW98] illustrates by an example taken from [Leh98] that the multidimensional normal form might be too restrictive for certain application scenarios and defines the generalized multidimensional normal form (GMNF). As argued in [LAW98], a schema in GMNF ensures summarizability in a context-sensitive manner and supports an efficient physical database design. However, so far there is no design method that guarantees multidimensional normal forms. : : : ; Given an aggregation path (d1; dn), where di is a distored in measures and a qualifying context which is determined through (terminal) dimension levels. Each dimension level contains a set of instances or elements. An aggregation path is a subsequence of dimension levels, which starts in a terminal dimension level and ends in an implicit dimension level All containing a single element <all>. mension level, 1 i n, we assume that every element of di belongs to (or is associated to) at most one element of di+1, 1 i n 1; moreover, we say that di+1 is a higher (aggregation) level than di. A dimension is structured in terms of one or more aggregation paths that share the same terminal dimension level. Therefore, each dimension comprises at least one terminal dimension level and the implicit level All. For example, a dimension time might consist of the single aggregation path (day, month, year), where the element <2000/03/29> of dimension level day is associated to element <2000/03> of level month, which in turn belongs to element <2000> of level year. In slight abuse of terminology, the graph consisting of all aggregation paths for a given dimension is called dimension hierarchy (although a dimension level might have more than one parent level). We assume that sets of dimension levels of distinct dimensions are disjoint.
A property attribute describes additional information related to a dimension level (e.g., the property attribute custName for dimension level custID in Figure 1). An optional property attribute (e.g., custAge) needs not be specified for each element of the corresponding dimension level and therefore may contain <null> values. A property attribute can be used to delimit the resulting set of a multidimensional query, but does not determine its aggregation level.
A fact schema represents the dimensional context for a set of facts that share the same terminal dimension levels; we use graphical schemata such as the one shown in Figure 1 to express fact schemata. Note that we avoid the term fact table during conceptual design, as “table” suggests logical storage in (relational) tables, which concerns logical design decisions only. 3.2
3
We briefly describe a graphical notation for conceptual multidimensional data modeling next. To avoid misunderstandings resulting from the variety of terminology in multidimensional databases, we first clarify some terms and then use these throughout the rest of the paper. 3.1
Facts represent atomic information elements in a multidimensional database. A fact consists of quantifying values Dimension hierarchies are classified into two basic types. A simple hierarchy consists of exactly one linear aggregation path within a dimension (e.g., path day!month!year in dimension time of Figure 3).
A multiple dimension hierarchy contains at least two different aggregation paths in a dimension (e.g., the dimension account of Figure 3). A group of aggregation paths rooted in a common dimension level d is called alternative, if every element of d belongs to exactly one element of each higher level (e.g., the paths of Figure 3 starting in dimension level orgID). Moreover, we allow optional groups of aggregation paths. Here, we assume that some 6-4 custN ame custAge orgID time eff ec tiveD ay month branch orgGroup dimension level dl has two or more higher levels such that for every element of dl there is exactly one element in a higher level to which that element belongs. For example, in Figure 3 the group of aggregation paths starting in dimension level custID is optional, and each element of dimension level custID is related to either a profession or a branch); within an optional group of aggregation paths a dimension level such as custID is called split level whereas customerType is called join level.
In our graphical notation, simple hierarchies and alternative groups of aggregation paths are indicated by simple arrows, pointing from the lower dimension level to the higher one. Optional groups of aggregation paths are specified by double lined arrows. A mandatory property attribute is connected via a diamond to its dimension level, and an optional property attribute without.
Intuitively, aggregations along different aggregation paths in an alternative group yield the same result. However, if a group is optional then aggregations along different paths within the group represent (partial) aggregation results for mutually disjoint subsets of the elements of the terminal dimension level.
We point out that if some element of a dimension level does not belong to an element of some higher level then all data related to that element is lost at the higher aggregation level, resulting in erroneous query results. To avoid such partial mappings we propose the insertion of an element <other> into the higher dimension level. After that we allocate every nonrelated element of the lower level to the element <other> of the higher one. 4
In this section, we propose an approach to data warehouse design that resembles the traditional database design process. In Section 4.1 we briefly sketch the overall approach, then we present the conceptual design phase in detail in Section 4.2; we refer to [Hue99] for more information on the remaining phases. The operational E/R schema delivers basic information to determine the multidimensional analysis potential, where we assume that such a schema is available to the warehouse designer (if it is not, it could be obtained, for example, through techniques of reverse engineering as described in [FV95]). In this phase business domain experts select strategically relevant operational database attributes and specify the purpose to use them as dimensions and/or measures. For each attribute it is necessary to decide whether it contains optional data or not. Furthermore, additional complementary requirements in the form of complex derived measures are added. The resulting requirements specification contains a tabular listing of attributes along with their multidimensional purpose. Supplementary informal information (such as relevant business integrity constraints) can 6-5 be added in a textual appendix, which also includes typical strategic queries.
The conceptual design phase performs a transformation of the semi-formal business requirements specification into a formalized conceptual multidimensional schema. The formalization results in a graphical multidimensional diagram, which comprises fact schemata with their related measures and dimension hierarchies. For each measure of a fact scheme the summarizability constraints are formalized in an tabular appendix. In Section 4.2 we propose a phase model to derive such diagrams and appendices in a straightforward way starting from the requirements specification. 4.2
As we mentioned already, the aim of the conceptual schema design phase is to produce a graphical multidimensional schema, which for each measure expresses its multidimensional context in terms of relevant dimensions and their hierarchies.
We assume that a global operational E/R schema such as the one shown in Figure 2 exists, which describes the available source information. Moreover, we assume that requirements analysis has been carried out together with domain experts, and that the global operational E/R schema has been analyzed to determine interesting measures, dimensions, and initial OLAP queries. The output of this phase consists of (a) tables such as the extract concerning account information shown in Table 1 (which contains an informal description for each relevant attribute and indicates whether the attribute may be used as measure or dimensional attribute and whether the attribute is optional or not) and (b) standard multidimensional queries such as
The data warehouse design process ends in a physical implementation of the logical schemata with respect to the individual properties of the target database system, including physical optimization techniques such as commonly known indexing strategies, partitioning etc., as well as OLAPspecific adjustments like relational denormalization of dimension tables, pre-aggregations or special use of bitmap indexes. = : : : ; Given the set M fm1; mkg of measures defined dur! 2 countID, effectiveDay) balance FKey for ! of all FDs of the form Di mi so obtained. Thus, given an ! 2 FD Di mi FKey, the dimension levels in Di functionally ing requirements analysis and the set D of dimensional attributes, every fact can be perceived as an element of a graph of some function from dimension levels to measures.
Hence, the conceptual design phase starts by determining functional dependencies (FDs)1 from dimension levels to measures. First, we determine a (minimal) key Di D for each measure mi; then we define the set FKey as consisting determine measure mi, but are not functionally determined by any other level. Hence, they qualify as terminal dimension levels that are used as roots of dimension hierarchies.
For each terminal dimension level we define a corresponding dimension.
In our running example, we hence obtain the FD (acmeasure balance. Furthermore, all measures mi; m j with “show the average turnover by year and product group” or “how many current accounts are managed online.”
We note that Table 1 contains additional attributes that represent multidimensional requirements which are not part of the operational schema (e.g., fmonth, customerTypeg). In particular, the new dimension level customerType is introduced in order to represent the specialization hierarchy concerning different types (e.g. business and private) of customers as shown in Figure 2.
These attributes extend operational data and augment multidimensional aggregation possibilities according to multidimensional analysis needs. Further additional attributes are obtained by an examination of those attributes that are specified both as measure and dimension. In our case, we note that related to business management it may not be useful to query an aggregation level on discrete balance and turnover values. Thus, we define new dimension levels balanceClass, turnoverClass that represent analysis intervals; moreover, the corresponding original attributes fbalance, turnoverg are then rated as nondimensional.
The logical design phase converts the conceptual schema to a logical one with respect to the target logical data model (mostly relational or multidimensional). The logical schemata are generated according to transformation rules, which only refer to the developed conceptual diagrams and summarizability constraints.
A process model to conceptual data warehouse design We subdivide the process phase of conceptual data warehouse design into three sequential phases:
1Since functional dependencies are a well-known concept in relational databases, we assume the reader to be familiar with it; otherwise see, for example, [BCN92, Vos99]. time
effectiveDay month quarter year accountID balance balanceClass turnover turnoverClass creditlimit interest custID custName custAge customerType profession branch productID productType orgID orgName orgGroup orgType businessector
M no no no no no yes no yes no yes yes no no no no no no no no no no no no no
D yes yes yes yes yes no yes no yes no no yes yes yes yes yes yes yes yes yes yes yes yes yes
O no no no no no no no no no no no no no yes no yes yes no no no no no no no ac count
f ac ts balanc e turnover creditlim it interest
Ftime Graphically, we derive the simple dimension hierarchy shown in Figure 6. ! ! and di d j is a non-transitive FD, i.e., if di d j holds 6= and there is no dimension level dk (dk di; d j) such that 6= an edge from dimension level di to level d j, if di d j ! ! di dk d j holds. ! sion level dl if the FD dl dp is non-transitive. The infor
In the following, we use the dimension account (see Figure 7) as running example for the derivation of complex dimension hierarchies. In a first step, property attributes and dimension levels have to be distinguished according to analysis requirements (recall that property attributes may only be used for selections but not for aggregations). For example, orgName represents a property attribute, since aggregations according to orgName are meaningless to business analysts. Similarly, custName and custAge are identified as property attributes, whereas all remaining dimensional attributes represent dimension levels.
Next, in a second step, a rough approximation of the dimension hierarchy is obtained by building a directed graph whose nodes are dimension levels. This graph contains
The graph obtained so far is now augmented with property attributes: Property attribute dp is attached to dimenmation whether a property attribute is optional or not can be retrieved from the requirements specification.
Finally, multiple dimension hierarchies have to be checked whether they contain optional groups of aggre! branch customerType, ness customer), which implies that the aggregation paths = f ! ; : : : Faccount accountID orgID, termines the optional dimension levels dc1 dck . These ! ; : : : g accountID balanceClass, sets of fdc1 dck such that the elements of levels in each ! ! orgID orgGroup, orgID orgType, In our example, custID is the split level, and ! ! g custID custName, custID custAge from custID to profession and branch form an ! ! accountID custID, accountID turnoverClass, optional levels are now grouped by building disjoint sub! productID productType, ments of split level dl. ! ! custID profession, custID branch, of custID belongs either to profession (in case of ! profession customerType, a private customer) or to branch (in case of a busi! accountID productID, group form a complete and disjoint partitioning of the elegation paths or not. If all dimension levels are manda... time effectiveDay m onth quarter year tory according to the requirements specification then all groups of aggregation paths are alternative. If, however, Figure 6: Simple Dimension Hierarchy time. some dimension levels are optional (such as profession and branch in our example) then these levels infTohlleowdiimngenFsDiosn: levels of dimension account exhibit the troduce groups of optional aggregation paths. Assume that dl is a (mandatory) split level that functionally deooorrrgggIGTDryop!uep!o!rgbbNuuassmiienne,esssseeccttoorr,, eflpsrwofhiecshshiaovne, tborabencghroguapreedth.e oCplteiaornlayl, deimacehnseiloenmleevn-t optional group of aggregation paths. Moreover, customerType is the join level for this group as customerType is functionally dependent on profession and branch. We point out that in general, however, (a) multiple groups may arise and (b) it may be necessary to introduce new optional levels in order to ensure completeness for each group. Furthermore, we require that each group has a join level whose elements indicate for each element of the split level to which optional level of the group it belongs. For example, if customerType contains the elements <business customer> and <private customer> then each customer, i.e., each element of custID, belongs to branch if the customerType is <business customer> and to profession otherwise. Thus, customerType is a join level that satisfies our requirements. In general, it might be necessary to introduce such a join level explicitly.
As already argued in, e.g., [LS97, GMR98, PJ99], not all possible aggregations of measures within a certain application scenario make sense in general. For example, given a group of customers, summing over as well as taking averages of account balances may be perfectly reasonable; similarly, the computation of average ages may be reasonable, time ...
acc ount prof ession businessector whereas the sum of customer ages will probably be meaningless. Consequently, a conceptual model should provide means to distinguish meaningful aggregations of measures from meaningless ones, as this information helps analysts in formulating their queries. In particular, the warehouse schema should express explicitly which measure may be aggregated along what dimension hierarchy according to what aggregation function. Clearly, we could integrate this information into the graphical fact schemata by connecting each pair of measures and terminal attributes by an edge that is labeled with all meaningful (or, alternatively, by all meaningless) aggregate functions. However, for the schema shown in Figure 1 we would already have to add at least 8 edges, thereby reducing readability. Hence, we refrain from representing meaningful aggregations within graphical schemata, but propose to use summarizability appendices as described next. 2 2 n D where for all di D there is d j D fdig such that we Compared to the approaches [CT98, GMR98], our analysis of FDs corresponds to the “schema navigation” performed in those approaches. However, we start by an identification of measures and proceed algorithmically from there on, whereas [CT98, GMR98] start by a rather vague identification of facts. Moreover, our method is justified by multidimensional normal forms as we will show next.
First, we recall terminology related to multidimensional normal forms from [LAW98], suitably adapted to our framework. We point out that [LAW98] distinguishes weak FDs (which amount to partial functions) from non-weak ones (denoting total functions), whereas we (equivalently) make use of FDs in the usual sense but distinguish optional from mandatory attributes.
A dimensional schema is a set of dimensional attributes based on the allowed aggregation functions along every path is meaningful. We declare a chosen restriction on a given dimension level implicitly valid for all dependent higher dimension levels. This does not exclude the possibility to define further constraints with greater restriction level on higher dimension levels.
The results of this process are arranged within a summarizability appendix such as the one shown in Table 4, which contains the restriction levels for measures in the fact schema of Figure 1.
The measure balance is additive in the dimension level accountID, so we assign restriction level 1 to it for all aggregation paths starting in accountID. In contrast summing up balance-values in the dimension level effectiveDay is meaningless. Nevertheless the analysis of average values or other statistical characterizing quantities makes sense, so restriction level 2 is allocated for the dimension level effectiveDay.
Along the lines of [PJ99] we distinguish four degrees of increasing restriction levels for measures within the context of dimension levels as shown in Table 3. Given a pair (m; d) of a measure m and a dimension level d, we associate restriction level 1, if all aggregate functions may be applied to roll-up m from dimension level d to every functionally dependent higher level. Restriction level 2 is associated to those pairs (m; d), where all aggregate functions but the SUM-Operator are applicable (e.g., age information along the customer dimension as explained above). The restriction level 3 represents the highest limitation, where aggregation is still possible, but only in terms of counting (e.g., for constant measures). Finally, degree 4 states that no aggregation function is permissible.
Given the graphical, conceptual schemata so far, the next step is to define restriction levels for all measures along the different aggregation paths in every fact schema: For each pair of measures and dimension levels we define a restriction level such that every multidimensional query 5
turnover creditlimit interest 1. For each optional dimension level dl in dimension d there is an element of a mandatory higher level dc denoting the context of validity of dl. 2. Each dimensional schema restricted to mandatory attributes is in dimensional normal form. 3. The dimensions are orthogonal to each other. 4. All measures are full functionally determined by the set of terminal dimension levels of the dimensions. 6
In this paper, we have outlined an approach to conceptual warehouse design which incorporates new guidelines to address specific warehouse needs and which can naturally be embedded into the traditional database design process. In this respect, the generalized multidimensional normal form can be regarded as a quality factor that avoids aggregation anomalies (similar to the avoidance of update anomalies by traditional normal forms for operational databases) and is therefore of most importance to guarantee correct query results.
Previously, the method proposed in [GR98] seems to have been the only existing approach that covers a complete data warehouse design starting from source integration and requirements analysis, very much in resemblance of traditional database design. We believe that their overall approach is well-suited to data warehouse design, since the separation of design phases is essential to any design process, within the context of relational databases or otherwise. For example, it is the requirements analysis that allows to identify facts, measures, and typical queries, which are basic ingredients for the following design steps. In contrast, starting with the conceptual design the approach [CT98] indicates only that facts and dimensions have to be identified and selected but contains no hints as how to achieve this.
Concerning further details on logical schema design, the reader is referred to [Hue99], which focuses on the relational model, and develops a straightforward transformation procedure from the conceptual to the relational model, where fact schemata are mapped to fact relations and each dimension level is mapped to a separate table. Interestingly, the final schema turns out to be a fully normalized snowflake schema (if only a single fact schema occurs) or galaxy schema (if multiple fact schemata occur and share some dimensions).
Acknowledgement. The authors are grateful to Thomas Lo¨ chte of zeb/rolfes-schierenbeck/associates for a number of discussions on the subject of this paper.