This paper presents a proposal for a Data Warehouse Conceptual Data (CDWDM) Model which allows for the description of both the relevant aggregated entities of the domain-together with their properties and their relationships with other relevant entities-and the relevant dimensions involved in building the aggregated entities. The proposed CDWDM is able to capture the database schemata expressed in an extended version of the Entity-Relationship Data Model; it is able to introduce complex descriptions of the structure of aggregated entities and multiply hierarchically organised dimensions; it is based on Description Logics, a class of formalisms for which it is possible to study the expressivity in relation with decidability of reasoning problems and completeness of algorithms.
(S. Gatziu, M. Jeusfeld, M. Staudt, Y. Vassiliou, eds.) http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-19/ the fact that (1) experiences in the field of databases have proved that conceptual modelling is crucial for the design, evolution, and optimisation of a database, (2) a great variety of data warehouse system are on the market, most of them providing some implementation of multidimensional aggregation, and (3) query optimisation with aggregated queries [Nutt et al., 1998; Cohen et al., 1999] is even more crucial for data warehouses than it is for databases— which makes semantic query optimisation using a conceptual model even more important. As a consequence of the absence of a such an extended modelling formalism, a comparison of different systems or language extensions for query optimisation is difficult: a common framework in which to translate and compare these extensions is missing, new query optimisation techniques developed for extended schema and/or query languages cannot be compared appropriately.
In order to address these questions, a formal framework must be developed that encompasses the abstract principles of the data warehouse related extensions of traditional representation formalisms. In this paper, we present some preliminary outcome from the research done within the “Foundations of Data Warehouse Quality” (DWQ) long term research project, funded by the European Commission (n. 22469) under the ESPRIT Programme. With respect to the global picture, the role of our research within DWQ is to study a formal framework at the conceptual level (see Figure 1). The conceptual data model we are investigating should be able to abstract and describe the entities and relations which are relevant both in the whole enterprise, and in the user analysis of such information. In the following, we will refer to this formalism as the Data Warehouse Conceptual Data Model (DWCDM). 1.1
A DWCDM must provide means for the representation of a multidimensional conceptual view of data. More precisely, a DWCDM provides the language for defining multidimen
sional information within a conceptual model in the data warehouse global information base. As stated above, the model is of support for the conceptual design of a data warehouse, for query and view management, and for update propagation: it serves as a reference meta-model for deriving the inter-relations among entities, relations, aggregations, and for providing the integrity constraints necessary to reduce the design and maintenance costs of a data warehouse. Hence a DWCDM must be expressive enough to describe both the abstract business domain concerned with the specific application (Enterprise model)—just like a conceptual schema in the traditional database world—and the possible views of the enterprise information a specific user may want to analyse (Client model)—with particular emphasis on the aggregated views, which are peculiar to a data warehouse architecture (see Figure 1). A multidimensional modelling object in the logical perspective—e.g., a materialised view, a query, or a cube—should always be related with some (possibly aggregated) entity in the conceptual schema.
In the following, we will briefly introduce the ideas
behind a multidimensional data model
Relational database tables contain records (or rows). Each record consists of fields (or columns). In a normal relational database, a number of fields in each record (keys) may uniquely identify each record. In contrast, a multidimensional database contains n-dimensional arrays (sometimes called hypercubes or cubes), where each dimension has an associated hierarchy of levels of consolidated data.
Juice 10 Cola 13 Soap
JanFeb
MONTH
For instance, a spatial dimension might have a hierarchy with levels such as country, region, city, office.
Measures (which are also known as variables or metrics)—like Sales in the example, or budget, revenue, inventory, etc.—in a multidimensional array correspond to columns in a relational database table whose values functionally depend on the values of other columns. Values within a table column correspond to values for that measure in a multidimensional array: measures associate values with points in the multi-dimensional world. For example, the measure of the sales of the product Cola, in the northern region, in January, is 13,000. Thus, a dimension acts as an index for identifying values within a multidimensional array. If one member of the dimension is selected, then the remaining dimensions in which a range of members (or all members) are selected defines a sub-cube. If all but two dimensions have a single member selected, the remaining two dimensions define a spreadsheet (or a slice or a page). If all dimensions have a single member selected, then a single cell is defined. Dimensions offer a very concise, intuitive way of organising and selecting data for retrieval, exploration and analysis. Usual pre-defined or user-defined dimension levels (or Roll-Ups ) for aggregating data in DW are: temporal (e.g., year vs. month), geographical/spatial (e.g., Rome vs. Italy), organisational (meaning the hierarchical breakdowns of your organisation, e.g., Institute vs. Department), and physical (e.g., Car vs. Engine).
A value in a single cell may represent an aggregated measure computed from more specific data at some lower level of the same dimensions. Aggregation involves computing aggregation functions—according to the attribute hierarchy within dimensions or to crossdimensional formulas—for one or more dimensions. For example, the value 13,000 for the sales in January, may have been consolidated as the sum of the disaggregated val13-2 ) e p y E1 Calls (av. duration)
Mon
Tue
Date (Week Day) Wed Thu Fri
Sat
Sun ) e p y T r e m rce tso ouS (uC
Consumer
Business E2 ues of the weekly (or day-by-day) sales. Another example introducing an aggregation grounded on a different dimension is the cost of a product—e.g., a car—as being the sum of the costs of all of its components.
In order to provide an adequate conceptualisation of multidimensional information, a DWCDM should provide the possibility of explicitly modelling the relevant aggregations and dimensions. According to a conservative point of view, a desirable DWCDM should extend some standard modelling formalism (such as Entity-Relationship) to allow for the description of both aggregated entities of the domain—together with their properties and their relationships with other relevant entities—and the dimensions involved. This document is about a proposal for a Data Warehouse Conceptual Data Model based on the EntityRelationship model where aggregations and dimensions are first class citizens. The data model it is based on Description Logics (DL), which have been proved useful for a logical reconstruction of the most popular conceptual data modelling formalisms, including the (enhanced) ER model. Advantages of using Description Logics are their high expressivity combined with desirable computational properties—such as decidability, soundness and completeness of deduction procedures. The devised logic has a decidable reasoning problem, thus allowing for automated reasoning over the whole conceptual representation. The presented framework extends the ideas pursued in [Calvanese et al., 1998b] regarding conceptual modelling using Description Logics as a data model, and the Information Integration framework presented in [Calvanese et al., 1998a; 1998c] based on an extended Description Logics data model for both the conceptual and the logical levels; our proposal is compatible with the DWCDM presented in [Calvanese et al., 1998c].
The paper is organised as follows. Section 2 informally introduces an extended ER formalism which allows for the description of the explicit structure of multidimensional aggregations; the section briefly describes the semantics of the conceptual data model in terms of a logical representation of multidimensional databases, as proposed by [Cabibbo and Torlone, 1998]. Section 3 will propose a basic modelling language—based on Description Logics—which is expressive enough to capture the EntityRelationship Data Model. The core part of the paper (Section 4) shows how it is possible to translate a schema expressed in the extended ER with aggregations in a suitable Description Logics theory, allowing for reasoning services such as satisfiability of a schema or the computation of a logically implied statement, such as an implicit taxonomic link between entities. 2
Modelling the Structure of Aggregation We introduce in this section an extension of the EntityRelationship Conceptual Data Model for representing the structure of aggregations. Thus, a conceptual schema will be able to describe abstract properties of multidimensional cubes, their interrelationships, and, most notably, their components. A Data Warehouse Conceptual Schema may contain detailed descriptions of the structure of aggregates, but it may not explicitly include aggregation functions.
Aggregations are first class citizens of the representation 13-3 1,1 Source
Point
X code type language: it is possible to describe the components of aggregations, and the relationships that the properties of the components may have with the properties of the aggregation itself; it is possible to build aggregations out of other aggregations, i.e., it is possible for an aggregation to be explicitly composed by other aggregations. This approach closely resembles the one pursued by [Catarci et al., 1995; De Giacomo and Naggar, 1996], in the sense of proposing a conceptual data model in which aggregations are first-class entities intensionally described by means of their components.
As we have pointed out, the description of an aggregation is not going to include a specification of how values of its attributes are computed from attribute values of its components using aggregation functions such as min, average, or sum. While including such constructs in the conceptual model is obviously important, if we restrict our attention to data models which are computable (in a general sense), then we should be very conservative. The reason for this comes from an important result of the research within the DWQ project which identifies the borders for the possible extensions of a Data Warehouse Conceptual Data Model towards the explicit inclusion of aggregation functions [Baader and Sattler, 1998]. It has turned out that the explicit presence of aggregation functions, when viewed as a means to define new attribute values for aggregated entities, and built-in predicates in a concrete domain increases the expressive power of the basic conceptual model in such a way that all interesting inference problems may easily become undecidable. Moreover, this result is very tightly bounded: extending a very weak Conceptual Data Model allowing only basic constructs with a weak form of aggregation already leads to the undecidability of reasoning – i.e., no terminating procedure solving the reasoning problem may ever exist. On the other hand, recent research has shown that appropriate restrictions of the allowed aggregation functions yield decidability of these problems. These results concern (1) the use of aggregation functions in nested concepts, and (2) concrete domains like the integers, the non-negative integers, the rationals, and the reals. 2.1
As stated in [Agrawal et al., 1995], a “good” data warehouse system should support user-definable multiple hierarchies along arbitrary dimensions. In Section 1.1 we have briefly defined a dimension as an index for identifying measures within a multidimensional data model. In the conceptual data model, “dimension” is a synonym for a domain of an attribute (or of attributes) that is structured by a hierarchy and/or an order. In order to support multiple hierarchies, the data model must provide means for defining and structuring these hierarchies, and for arbitrary aggregation along the hierarchies.
A conceptual data model where both multidimensional
aggregations and multiply hierarchically organised
dimensions can be abstracted and described can be used in query
languages and for semantic optimization in
multidimensional data bases. In fact, in the few attempts where a cube
algebra introduces the notion of multiple dimensions and
of levels within dimensions
Let us now consider a concrete example related to the analysis of the average duration of telephone calls according to their dates and source types. The base data involved in the analysis is represented at the conceptual level in Figure 4. In order to perform the analysis, the two tables of Figure 3 are materialised by the OLAP tool. Each cell in the bi-dimensional cube on top denotes the aggregation composed by all the telephone calls issued at some date (expressed as a day of the year) and originated by a particular source (expressed as the type of the calling telephone); the date and the source are the dimensions of the cube, while the calls are the target. In particular, cell E1 is the aggregation composed by all those calls issued on 3/1/99 and 13-4 1,1 Source code type
MD the multidimensional logical data model introduced The semantics of an ER schema is given in terms of legal multidimensional database states, i.e. multidimensional databases which conform to the constraints imposed by the schema. We consider as a starting point the ER semantics introduced in [Calvanese et al., 1998b], recasted to cope with multidimensional information. For we have chosen points)—more conceptual entities come into play. Figure 6 presents the extensions required to the original schema.
Cell E2 is the aggregation composed by all calls issued on Friday from a consumer type phone. Similar to E1, E2 may have the property average(duration) which computes the average duration of all those calls.
Thus, we need to add both a new aggregated entity and the definitions of the newly introduced levels for the dimensions date and source. The new aggregated entity, Ag-2, aggregates calls according to the level Week day and the level Customer Type of the dimensions date and source respectively. Then E2 is one of the aggregations denoted by Ag-2. The level Week Day is obtained by aggregating days from the partitioning of the Day entity into seven sub-entities, namely the seven days of the week. The level Customer Type is obtained by aggregating phone points from the partitioning of the Point entity into the two sub-entities Consumer and Business. Customer Type is called simple aggregation, since there is no dimension involved in its definitions.
Customer Type and Week Day are levels in the multiply hierarchically organised source and date dimensions.
We do not formally define in this paper the syntax of the extended ER model. originating from a land line phone point. It is clear that E1 may include more than one call, and it may itself have some properties which depend on all of its components. For example, E1 may have the property average(duration) which denotes the average duration of all the calls issued on 3/1/99 and originating from a land line phone point. Of course, this property may be computed by an appropriate aggregation function from the property duration of the components.
An adequate basic conceptual schema for this simple multidimensional information base should include the base entities such as Call, Day, and Phone Point and relations such as date and source. Moreover, the schema should also include an additional aggregated entity, say Ag-1, namely the class denoting the aggregations of calls by date and source; such an aggregated entity can also have attributes such as average(duration). We can also say that Ag-1 aggregates telephone calls according to the (basic) level Day and the level Point Type of the dimensions date and source, respectively. The entity Point Type is itself an aggregation, aggregating all the specific telephone points according to their four basic types. It is clear that E1 is one of the aggregations denoted by Ag-1.
Figure 5 presents the schema in a variant of the EntityRelationship data model. The particular way of representing aggregated entities in the figure is inspired by [Catarci et al., 1995; De Giacomo and Naggar, 1996].
If we also consider as part of the multidimensional information base the aggregated view represented by the second cube of Figure 3—denoting the aggregation composed by the telephone calls issued at some day of the week and originated from some source type of a different level as before (aggregated now according to consumer and business type 2.2
Wed
Thu
Fri 1,1 Source
Point
X code type MD tidimensional database state is thus an instance of a MD abstracts notions such as dimension hierarchies MD by [Cabibbo and Torlone, 1998]. is independent of MD tions. The central element of a schema is the f-table, MD tidimensional databases described as instances which MD it is shown how a logical schema can be translated any specific implementation of multidimensional databases (ROLAP or proprietary MOLAP), thus providing an abstract and general framework for the logical representation of multidimensional data. In [Cabibbo and Torlone, 1998] into a ROLAP logical representation in the form of a “star” schema, and into a general MOLAP logical representation in the form of sparse multidimensional arrays. and levels, fact tables, cubes, and measures. As expected, dimensions are organised into hierarchies of levels, corresponding to the various granularity of the basic data.
Within a dimension, levels are related through roll-up funcrepresenting factual data. An f-table is the abstract logical representation of a multidimensional cube, and it is a function associating symbolic coordinates (one per involved dimension) to measures. According to the authors, a mullogical schema: it is the description of the specific f-tables involved, in the form, for example, of tables describing the mapping from coordinates to measures.
Thus, a particular ER diagram denotes a set of multidimensional database states, i.e., the set of all possible mulconform to the diagram itself – i.e., they are legal states. If a diagram is inconsistent, then no multidimensional database may conform to it.
ALC 1999], extending with features (i.e., functional roles), ALCF I sider the Description Logic [Horrocks and Sattler, Smolka, 1991] whose extensions have been summarised in [Donini et al., 1996; Calvanese et al., 1999].
The basic types of a concept language are concepts, roles, and features. A concept is a description gathering the common properties among a collection of individuals; from a logical point of view it is a unary predicate. Interrelationships between these individuals are represented either by means of roles (which are interpreted as binary relations) or by means of features (which are interpreted as partial functions). Both roles and features can be used to individuals to certain properties. In the following, we will coninverse roles, role composition, and role restrictions. average(duration)
Ag-2 In this section we give a brief introduction to a basic Description Logic, which will serve as the basic representation language for our DWCDM proposal. With respect to the formal apparatus, we will strictly follow the concept language formalism introduced by [Schmidt-Schauß and (C u = D)I = (9R. C)I (f = ")I = (:C)I = ?I = >I (C t = D)I = (8R. C)I (f : = C)I 4 Encoding ER schemas with Aggregations
1ER-roles are the names given to the arguments of relationships; we assume that a unique name is given within a relationship to each ER-role, representing a specific participation of an entity in the relationship.
ALCF I ER diagram and an knowledge base. ALCF I expressed in an knowledge base—whose models It is shown how a schema expressed in the conceptual data model informally introduced in the previous section can be correspond with legal multidimensional database states of the ER diagram—allowing for reasoning services such as satisfiability of a schema or the computation of a logically implied statement.
In the following, we describe the translation between an D An ER schema is translated into a corresponding knowl
edge base where for each domain, entity, aggregation, or relationship symbol a concept name is introduced, and for each attribute or ER-role symbol1 symbol a feature name is introduced. The terminology is defined to contain the following axioms: n and corresponding levels Li (each one being either D T n For each aggregation Ag in involving a target , dimensions Di (each one being a relationship in D) an entity Ei or a simple aggregation Agi in D), contains: D legal multidimensional databases of and models of .
Extending the results of [Calvanese et al., 1994] to the case of multidimensional databases, it can be proved that the translation is correct, in the sense that whenever a reasoning problem has a specific solution in the ER model, then the corresponding reasoning problem in the DL has a corresponding solution, and vice-versa. This is grounded on the fact that there is a precise correspondence between
Thus, it is possible to exploit DL reasoning procedures for v i 6= j Fi :Fj for all E v t : : : t F1 Fn v E i Fi for all : : : F1 Fn in D, E For each PARTITION of an entity into sub entities
contains: : : : : : : E1 En by means of the ER-roles PER1 PERn , R D n For each relationship in relating entities
contains: D mappings from legal multidimensional database states of D ing the corresponding f-table in exists, and vice-versa. solving reasoning problems in the ER model. The reasoning problems we are mostly interested in are consistency of a ER schema—which is mapped to a satisfiability problem in the corresponding DL knowledge base—and logical implication within a ER schema—which is mapped to a logical implication problem in the corresponding DL knowledge base.
The proof is based by establishing the existence of two to models of and vice-versa. Informally speaking, the existence of the mappings ensures that, whenever an aggregation is satisfiable in , then a non-empty mapping describThe same applies for level orderings and roll-up functions in D. A more detailed sketch of the proof will be given in the full paper.
As a final remark, it should be noted that the high expressivity of DL constructs can capture an extended version of the basic ER model, which includes not only taxonomic relationships, but also arbitrary boolean constructs to represent so called generalized hierarchies with disjoint unions; entity definitions by means of either necessary or sufficient conditions or both, and integrity constraints expressed by means of generalised axioms [Calvanese et al., 1998b].
Let us now consider the example introduced in Section 2. We start to (partially) formalise the schema of Figure 4, i.e., the base data. Please recall that every role name which appears in the translation of an ER schema in a Description Logic knowledge base—with the exception of the aggregation roles—is a functional role name. The partitioning of days into the seven day of the week is translated in a similar way.
The aggregated entity Customer Type is the simple aggregation of telephone points into two categories: The Week Day simple aggregation is obtained in a similar way.
The aggregated entity Ag-2 is defined as being an aggregation composed by those calls issued in some day of the week and originated by either a consumer telephone point or a business telephone point:
Mobile Call
Dest Recall that Ag-2 is the class of all aggregations such that each one of them aggregates calls issued at the same day of the week and originated from the same telephone point.
Each aggregation of calls belonging to the class denoted by Ag-2 includes either only consumer originated calls or only business originated calls. In a similar way, each aggregation of Ag-2 includes either only calls issued on Monday, or only calls issued on Tuesday, etc. Thus, aggregations denoted by Ag-2 may be of fourteen possible types: Monday consumer, Monday business, Tuesday consumer, Tuesday business, etc.
As an example of reasoning, let us see a case with an inconsistent aggregation. If we introduce the entity Mobile Call as in Figure 9, it turns out that the aggregated entity having Mobile Call as target (instead of its super entity Call) and Business as level for the dimension Source is inconsistent, i.e., the materialised cube is necessarily empty.
In fact, the translated theory in Description Logics turns out to be unsatisfiable, since mobile calls are originated only from cell points, which are disjoint from any kind of business phone point. 5
Conclusions We have introduced a Data Warehouse Conceptual Data Model, extending the most interesting traditional Semantic Data Models and Object-Oriented Data Models, which allows the representation of a multidimensional conceptual view of data. We have seen how the proposed conceptual data model is able to introduce complex descriptions of the structure of aggregated entities and multiply hierarchically organised dimensions. In order to support multiple hierarchies, the data model provides means for defining and structuring these hierarchies, and for arbitrary aggregation along the hierarchies. Our future work will be devoted to a further development of the data model in order to explicitly consider temporal and spatial dimensions, and a study of the expressivity in relation with decidability and complexity of the refinement reasoning task.
.
Source
Cell