Automating the multidimensional design of data warehouses

Automating the Multidimensional Design of Data Warehouses PhD. Thesis PhD. Student: Oscar Romero Moral Advisor: Alberto Abell´ o Gamazo Programa de Doctorat en Software Departament de Llenguatges i Sistemes Inform` atics Universitat Polit` ecnica de Catalunya Barcelona December 18, 2009 A thesis presented by Oscar Romero Moral in partial fulfillment of the requirements for the degree of Doctor en Inform` atica per la Universitat Polit` ecnica de Catalunya To those always there. This work is, somehow, also yours. Acknowledgements “Every thesis begins with a single keystroke.” PhD Comics, 2009 My foremost thank goes to Alberto Abell´ o. Without him, this dissertation would have not been possible. I thank him for his endless patience and encouragement, for his exigency and rigor, and for his insights and suggestions that helped to shape my research skills. Likewise, I really appreciate that he always had time for me, despite it was not easy with two little children around. Thanks Alberto! I would also like to thank Ernest Teniente and my colleagues in the Grup Facing On towards Logic database Rule Enforcement, and people in the Secci´ o de Sistemes d’Informaci´ o, for their support. Thanks to Dr. Diego Calvanese, for the opportunity to stay in his group for five months, and people in the KRDB Centre for Knowledge and Data, who made me feel like at home. I also thank Joan Marc Montes´ o, for implementing the AMDO tool, and Antonio Montero, for encapsulating the MDBE implementation in a web service. Also thanks to Josep Berbegal, Anna Queralt, Leonor Fr´ ıas, Gemma Grau and Jordi Conesa for their help on various details of this thesis. I thank my thesis committee members: Dr. Antoni Oliv´ e, Dr. Ernest Teniente, Dr. Diego Calvanese, Dr. Alkis Simitsis, and Dr. Juan Trujillo. It is a pleasure for me that they accepted to be part of this committee. I am greatly indebted to my friends, for all the good moments they provided but, specially, for listening to me when I needed to talk, and for making me laugh when I most needed it... such good memories I cannot capture in words! Last but not least, I owe my deepest gratitude to my mother, who always encouraged me to work hard and always believed in me, and also to my father and brothers, for always being there when I needed them most, and for supporting me through all these years. This work has been partly supported by the Ministerio de Educaci´ on y Ciencia and FEDER, under projects TIN 2005-05406 and TIN2008-03863. vii Abstract Previous experiences in the data warehouse field have shown that the data warehouse multidimensional conceptual schema must be derived from a hybrid approach: i.e., by considering both the end-user requirements and the data sources, as first-class citizens. Like in any other system, requirements guarantee that the system devised meets the end-user necessities. In addition, since the data warehouse design task is a reengineering process, it must consider the underlying data sources of the organization: (i) to guarantee that the data warehouse must be populated from data available within the organization, and (ii) to allow the end-user discover unknown additional analysis capabilities. Currently, several methods for supporting the data warehouse modeling task have been provided. However, they suffer from some significant drawbacks. In short, requirement-driven approaches assume that requirements are exhaustive (and therefore, do not consider the data sources to contain alternative interesting evidences of analysis), whereas data-driven approaches (i.e., those leading the design task from a thorough analysis of the data sources) rely on discovering as much multidimensional knowledge as possible from the data sources. As a consequence, data-driven approaches generate too many results, which misleads the user. Furthermore, the design task automation is essential in this scenario, as it removes the dependency on an expert’s ability to properly apply the method chosen, and the need to analyze the data sources, which is a tedious and time-consuming task (which can be unfeasible when working with large databases). In this sense, current automatable methods follow a data-driven approach, whereas current requirement-driven approaches overlook the process automation, since they tend to work with requirements at a high level of abstraction. Indeed, this scenario is repeated regarding datadriven and requirement-driven stages within current hybrid approaches, which suffer from the same drawbacks than pure data-driven or requirement-driven approaches. In this thesis we introduce two different approaches for automating the multidimensional design of the data warehouse: MDBE (Multidimensional Design Based on Examples) and AMDO (Automating the Multidimensional Design from Ontologies). Both approaches were devised to overcome the current limitations previously discussed. On the one hand, we rely on the end-user requirements, but we do not decline that the data sources may also contain hidden analysis capabilities that, eventually, may be of interest. Nevertheless, in any case, we do not generate endless chunks of results from the sources. On the contrary, we aim at filtering by means of objective evidences the results obtained by analyzing the sources. Importantly, our approaches consider opposite initial assumptions, but both consider the end-user requirements and the data sources as first-class citizens. Furthermore, we also focus on the automation of the process, to facilitate the ix 4.9 AMDO: the FD-tree computed for the EndDurationPrice concept . . . . . 146 4.10 AMDO: the searching space for the endDurationPrice concept, and a piece ofitsFD-tree ....................................151 4.11 AMDO: an algorithm for discovering bases . . . . . . . . . . . . . . . . . . . . 152 4.12 AMDO: an algorithm to compute SS-descendants . . . . . . . . . . . . . . . . . 153 4.13 AMDO: an algorithm for generating (i+1)-sized combinations . . . . . . . . . . 154 4.14 AMDO: an exemplification of of a directed graph . . . . . . . . . . . . . . . . . 164 4.15 The AMDO App. integrated in Prot´ eg´ e ......................169 B.1 EU-Car Rentals class diagram: brand . . . . . . . . . . . . . . . . . . . . . . . . 184 B.2 EU-Car Rentals class diagram: rental agreement . . . . . . . . . . . . . . . . . . 185 B.3 EU-Car Rentals class diagram: rental agreement subclasses . . . . . . . . . . . . 186 B.4 EU-Car Rentals class diagram: cars, discounts and enumerations . . . . . . . . . 187 xvi List of Tables 2.1 Summary of the multidimensional design methods comparison (I) . . . . . . . . 40 2.2 Summary of the multidimensional design methods comparison (II) . . . . . . . . 41 2.3 Comparison table between the relational and the multidimensional algebras. . . . 46 2.4 Summary of the comparison between multidimensional algebras. . . . . . . . . . 51 3.1 Summary of the modifications brought in a cube-query by each multidimensional operator....................................... 65 3.2 Summary of cube-query conflicts . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.3 Summary of rules used to infer the relationship multiplicities from relational sources ....................................... 81 3.4 Valid multidimensional relationships in a relational schema . . . . . . . . . . . . 82 3.5 MDBE: graph labelings generated after the first stage of MDBE . . . . . . . . . 90 3.6 MDBE statistics for the TPC-H case study . . . . . . . . . . . . . . . . . . . . . 102 4.1 AMDO: ranked facts proposed for the EU-Car Rental case study . . . . . . . . . 123 4.2 AMDO: ranked facts proposed for the TPC-H case study . . . . . . . . . . . . . 162 xvii xviii Chapter 1 Introduction “ ’Input! Input!’, Need input!’ ” Number 5, “Short Circuit”, 1986 Nowadays, the free market economy is the basis of capitalism (the current global economic system) in which the production and distribution of goods are decided by market businesses and consumers; giving rise to the supply and demand concept. In this scenario, being more competitive than the rest of organizations becomes essential, and decision making raises as a key factor for the organization success. Decision making is based on information. The more accurate information I get, the better decisions I can make to get competitive advantages. That is the main reason why information (understood as the result of processing, manipulating and organizing data in a way that adds new knowledge to the person or organization receiving it) has become a key piece in any organization. In the past, managers’ ability for foreseeing upcoming trends was crucial, but this largely subjective scenario changed when the world became digital. Actually, any event can be recorded and stored for later analysis, which provides new and objective business perspectives to help managers in the decision making process. Hence, (digital) information is a valuable asset to organizations, and it has given rise to many well-known concepts such as Information Society, Information Technologies and Information Systems among others. For this reason, today, decision making is a research hot topic. In the literature, those applications and technologies for gathering, providing access to, and analyzing data for the purpose of helping organization managers make better business decisions are globally known as Business Intelligence. This term implies having a comprehensive knowledge of any of the factors that affect an organization business with one main objective: the better decisions you make, the more competitive you are. Under this concept we embrace many different disciplines such as Marketing,Geographic Information Systems (GIS), Knowledge Discovery or Data Warehousing. 1 1.1 Data Warehousing Systems Data warehousing systems are aimed at exploiting the organization data, previously integrated in a huge repository of data (the data warehouse), to extract relevant knowledge of the organization. A formal definition can be found in [GR09]: Data Warehousing is a collection of methods, techniques and tools used to support knowledge workers -senior managers, directors, managers and analysts- to conduct data analyses that help with performing decision-making processes and improving information resources. This definition gives a clear idea of these systems final aim: give support to decision making without regard of technical questions like data heterogeneity or data sources implementation. This is a key factor in data warehousing. Nowadays, any event can be recorded within organizations. However, the way each event is stored differs in every organization, and it depends on several factors such as relevant attributes for the organization (i.e., their daily needs), technology used (i.e., implementation), analysis task performed (i.e., data relevant for decision making), etc. Thus, these systems must gather and assemble all (relevant) business data available from various (and possibly heterogeneous) sources in order to gain a single and detailed view of the organization that later will be properly managed and exploited to give support to decision making. The role of data warehousing can be better understood with five claims introduced by Kimball [KRTR98]: •We have heaps of data, but we cannot access it. Loads of data are available. However, we need the appropriate tools to effectively exploit (in the sense of query and analyze) it. •How can people playing the same role achieve substantially different results? Any organization may have several databases available (devoted to specific business areas) but they are not conceptually integrated. Providing a single and detailed view of the business process is a must. •We want to select, group and manipulate data in every possible way. This claim underlines the relevance of providing powerful and flexible analysis methods to be carried out in real time. •Show me just what matters. Too much information may be, indeed, too much. The enduser must be able to focus on relevant information for his / her current decision making processes. •Everyone knows that some data is wrong. A sensitive amount of transactional data is not correct and it has to be properly cleaned (transformed, erased, filtered, etc.) in order to avoid misleading results. Data warehousing systems have three main components: the data warehouse, the ETL (Extraction, Transformation and Load) tools and the exploitation tools. The data warehouse is a huge repository of data; i.e., a database. It is the data warehousing system core and that is why these systems are also called data warehouse systems. However, it is not just another traditional database: it depicts a single and detailed view of the organization business. By means of the ETL 2 tools data from a variety of sources is loaded (i.e., homogenized, cleaned and filtered) into the data warehouse. Once loaded, it is ready to be exploited by means of the exploitation tools. The reader is addressed to [GR09] for further details on data warehousing systems. In next sections we will focus on the data warehouse and the exploitation tools, as they are tightly related to this thesis. 1.1.1 The Data Warehouse The data warehouse term was coined by B. Inmon in 1992 [Inm92] that he defined as: ”a subjectoriented, integrated, time-variant and non-volatile collection of data in support of management’s decision making process”. Where subject oriented means that data stored gives information about a particular subject instead of the daily operations of an organization; integrated means that data have been gathered into the data warehouse from a variety of sources and merged into a coherent whole; time-variant means that all data in the data warehouse is identified with a particular time period and finally, non-volatile means that data is stable in the data warehouse. Thus, more data is added but data is never removed. This enables management to gain a consistent picture of the business. Despite this definition was introduced almost 20 years ago, it still remains reasonably accurate. However, a single-subject data warehouse is currently referred to as a data mart (i.e., a local or departmental data warehouse), while data warehouses are more global, giving a general enterprise view. In the literature, we can find other definitions like the one presented in [KRTR98], where a data warehouse is defined as ”a copy of transaction data specifically structured for query and analysis”; this definition, despite being simpler, is not less compelling, since it underlines the relevance of querying in a data warehousing system. The data warehouse design is focused on improving queries performance instead of improving update statements (i.e., insert, update and delete) like transactional databases do. Moreover, the data warehousing system end-users are high-ranked people involved in decision making rather than those low/medium-ranked people maintaining and developing the organization information systems. Next table summarizes main differences between an operational database and a data warehouse: Criterion Operational DB Data Warehouse Objective Operational Analysis and (daily operations) decision making Process Transactional, Massive querying, repetitive and well-known specific and not-known Main Activity Update statements Querying Performance Relevance of Relevance of the massive transactions time response querying time response Users Medium/Low profile High profile Data Model Relational Multidimensional 1.1.2 Exploitation Tools The final aim of every data warehousing system is to exploit the data warehouse. The data warehouse is a huge repository of data that does not tell much by itself; like in the operational 3 databases field, we need auxiliary tools to query and analyze data stored. In this field, those tools aimed at extracting relevant information from the repository of data are known as the exploitation tools. Without the appropriate exploitation tools, we will not be able to extract valuable knowledge of the organization from the data warehouse, and the whole system will fail in its aim of providing information for giving support to decision making. Most used exploitation tools can be classified in three categories: •Query & Reporting: This category embraces the evolution and optimization of the traditional query & reporting techniques. This concept refers to an exploitation technique consisting of querying data and generating detailed pre-defined reports to be interpreted by the end-user. •Data Mining: Data mining is the exploration and analysis of large quantities of data in order to discover meaningful patterns and rules [BL04]. The data mining field is a research area per se, but as the reader may note, this kind of techniques and tools suit perfectly to the final goal of the data warehousing systems. •OLAP Tools: OLAP stands for On-Line Analytical Processing, which was accurately chosen to confront the OLTP acronym (On-Line Transactional Processing). Its main objective is to analyze business data from its dimensional or components perspective; unlike traditional operational systems such as OLTP systems. In this thesis we will focus on OLAP tools, but the reader is addressed to [GR09] for further details on accessing the data warehouse. 1.2 OLAP Tools OLAP tools are intended to ease information analysis and navigation all through the data warehouse, for extracting relevant knowledge of the organization. This term was first introduced by E.F. Codd in 1993 [CCS93], but it was more precisely defined by means of the FASMI (Fast Analysis of Shared Multidimensional Information) test [Pen08]. According to it, an OLAP tool must provide Fast query answering to not frustrate the end-user reasoning; offer Analysis tools, implement security and concurrent mechanisms to Share the business Information from a Multidimensional point of view. This last feature is the most important one since OLAP tools are conceived to exploit the data warehouse for analysis tasks based on multidimensionality. 1.2.1 Multidimensionality Multidimensionality, as it is known today, was first introduced by Kimball in [Kim96], where the author argued about the necessity of an ad hoc modeling technique for data warehouses. Multidimensional modeling optimizes the system query performance in contrast to conventional Entity-Relationship (ER) models [Che76] (widely used for modeling relational databases) that are constituted to remove redundancy in the data model and optimize OLTP performance (see discussion in section 1.1.1 for further details on data warehouses vs. OLTP databases). 4 Figure 1.1: Multidimensional view of data Specifically, the multidimensional conceptual view of data is distinguished by the fact /dimension dichotomy, and it is characterized by representing data as if placed in an n-dimensional space, allowing us to easily understand and analyze data in terms of facts (the subjects of analysis) and dimensions showing the different points of view from where a subject can be analyzed. For instance, Fig. 1.1 depicts sales (subject of analysis) of an organization from three different dimensions or perspectives of view (time,product and place). One fact and several dimensions to analyze it give rise to what is known as the data cube1 This paradigm provides a friendly, easy-to-understand and intuitive visualization of data for non-expert end-users. Importantly, most events recorded are likely to be analyzed from a multidimensional point of view. An event (a potential fact) is recorded altogether with a set of relevant attributes (potential analysis dimension). For example, consider a sales event. We may record the shop,city and country where it was purchased, the item,color,size and add-ons selected, the time (hour,minute,second and even millisecond) and date (day,month,year), payment method,price,discount applied, the customer, etc. Interestingly, every attribute opens a new perspective of analysis for the sales event. More precisely, OLAP functionality is characterized by dynamic multidimensional analysis of consolidated data supporting end-user analytical and navigational activities. Thus, OLAP users are able to navigate (i.e., query and analyze) data in real-time. The user provides a navigation path in which each node (resulting in a data cube) is derived from the previous node in the path (and thus we say that the user navigates the data). Each node is transformed into the next one in the path by applying specific multidimensional operators. Most popular multidimensional 1The data cube refers to the placement of factual data in the multidimensional space. And thus, it can be thought as a mathematical function. Nevertheless, nowadays it is rather common also refer to the multidimensional space as the data cube. However, note that, in both cases, it is a language abuse, since the multidimensional space (or the placement of data in the multidimensional space) only gives rise to a cube if three analysis dimensions are considered. We address the reader to [ASS06] for further details. 5 operators are “roll-up” (increase the aggregation level), “drill-down” (decrease the aggregation level), “screening and scoping” (select by means of a criterion evaluated against the data of a dimension), “slicing” (specify a single value for one or more members of a dimension) and “pivot” (reorient the multidimensional view). Some works, like [PJ01] and [ASS06], add “drill-across” (combine data from cubes sharing one or more dimensions) to these basic operations. As a result, multidimensionality enables analysts, managers, executives and in general those people involved in decision making, to gain insight into data through fast queries and analytical tasks, allowing them to make better decisions. 1.3 Multidimensional Design Developing a data warehousing system is never an easy job, and raises up some interesting challenges. One of these challenges focus on modeling multidimensionality. OLAP tools are conceived to exploit the data warehouse for analysis tasks based on the multidimensional paradigm and therefore, the data warehouse must be structured according to the multidimensional model. Note that we are talking about the multidimensional model and not just about a paradigm. Hence, it must properly define a data structure, a set of operations to handle data and a set of integrity constraints. Unfortunately, we still lack of a standard multidimensional model like the relational model is for operational databases. Nevertheless, lots of efforts have been devoted to multidimensional modeling, and several models and design methods have been developed and presented in the literature. Consequently, we can nowadays design a multidimensional conceptual schema, create it physically and later, exploit it through the model algebra or calculus (implemented in the exploitation tools). 1.3.1 Logical Design: ROLAP vs. MOLAP When implementing our conceptual schema, and in general the OLAP tool, there are two main trends: using the relational technology or an ad hoc one, giving rise, respectively, to what are known as ROLAP (Relational On-line Analytical Processing) and MOLAP (Multidimensional On-line Analytical Processing) architectures. ROLAP maps the multidimensional model over the relational one (a multidimensional middleware on the top of the relational database makes this fact transparent for the users), allowing them to take advantage of a well-known and established technology. As consequence, ROLAP tools deal with larger volumes of data than MOLAP tools (i.e., ad hoc multidimensional solutions), but their performance for query answering and cube browsing is not as good. Thus, new HOLAP (Hybrid On-line Analytical Processing) tools were proposed. HOLAP architecture combines both ROLAP and MOLAP ones trying to obtain the strengths of both approaches, and they usually allow to change from ROLAP to MOLAP and viceversa. Although ROLAP tools have failed to dominate the OLAP market due to its severe limitations (mainly slow query answering) [Pen05], at the beginning, they were the reference architecture. Indeed, Kimball’s reference book [KRTR98] presents how a data warehouse should be implemented over a RDBMS (Relational Database Management System) and how to retrieve data from it. To do so, he introduced two logical (i.e., relational) patterns: the star schema and the 6 snowflake schema. The star schema consists of one table for the fact and one denormalized table for every dimension, with the latter being pointed by foreign keys (FK) from the fact table, which compose its primary key (PK). The normalized version of a star schema is a snowflake schema; getting a table for each level with a FK pointing to each of its parents in the dimension hierarchy. Nevertheless, both approaches can be conceptually generalized into a more generic one consisting in partially normalizing the dimension tables according to our needs: completely normalizing each dimension we get a snowflake schema, and not normalizing them at all results in a star schema. Currently, pure ROLAP tools have lost their reference position, but the star schema had, and yet has, great impact on multidimensional conceptual modeling, as we discuss in next section. 1.4 Multidimensional Modeling Methods As discussed in section 1.2.1, multidimensional modeling was first introduced by Kimball in [Kim96]. Kimball’s approach was well received by the industry and a deeper and advanced view of multidimensional modeling was presented in [KRTR98]. In these books Kimball also introduced the first method to derive the data warehouse logical schema. Similar to traditional information systems modeling, Kimball’s method is requirement-driven: it starts eliciting business requirements of an organization and through a step-by-step guide we are able to derive the multidimensional schema. Only at the end of the process data sources are considered to map data from sources to target. In short, Kimball’s approach follows a traditional modeling approach (i.e., from requirements), but it set down the principles of multidimensional modeling. Multidimensional modeling is radically opposite to OLTP systems modeling: the data warehouse conceptual schema is directly derived from the organization operational sources and provides a single, detailed, integrated and homogenized view of the business domain. Consequently, the data warehouse can be thought as a strategic view of the organization data and for this reason, and unlike most information systems that are designed from scratch, the organization data sources must be considered as first-class citizens in the data warehouse design process. This major additional requirement has such interesting consequences so much so that it gave rise to a new research topic and up to now, several multidimensional modeling methods have been introduced in the literature. With the perspective of time, we may now highlight those features that drew the attention of the community. The evolution of the modeling methods introduced in the literature focuses on two main aspects: (i) the dichotomy requirements versus data sources (and how to deal with it) and (ii) the level of abstraction of the method’s output. 1.4.1 A Piece of History In this section we introduce the background of multidimensional modeling. Our objective here is to provide an insightful view of how this area evolved with time. Note, however, that this dissertation comes up from the discussion of the state of the art carried out in Section 2.1. Shortly after Kimball introduced his ad hoc modeling method for data warehouses, some other methods were presented in the literature. Like Kimball’s method, these methods are step- 7 Figure 1.3: A comprehensive framework for introducing current multidimensional design methods (I) them, this thesis main contributions. As earlier introduced in this chapter and discussed in depth in Chapter 2, the data warehouse design task must consider (i) the end-user requirements and (ii) the data sources. Furthermore, we also aim to analyze the (iii) automation degree achieved and (iv) the quality of the output produced. In the following, we rate the most relevant methods introduced in the literature with regard to these four criteria. Note that, in this way, we are able to identify, at first sight, the assumptions made by each approach and moreover, analyze the goodness of the process proposed: i.e., the automation degree achieved and the quality of the outputs produced. Consider Figures 1.3 and 1.4. Axes xand yrepresent the assumptions of each method; i.e., the use of the requirements and the data sources in each approach. The xaxis measures how important requirements are in the approach, and if the method proposes to formalize them somehow, to facilitate their analysis. The yaxis assesses how important the analysis of the data sources is for the approach, and if detailed patterns are provided to exploit them. Finally, axes zmeasure either the automation degree achieved (see Figure 1.3) and the quality of the output produced (see Figure 1.4) regarding the assumptions made by the method (i.e., axes xand y). In the 3D-space formed, every approach is identified as a rhombus labeled with the bibliographical item in the reference list of this thesis. Furthermore, for the sake of understandability, we provide the projection of each rhombus in the three planes (green points for the XZ plane projections; 14 Figure 1.4: A comprehensive framework for introducing current multidimensional design methods (II) blue points for the XY plane and red points for the XZ plane). The methods depicted in both figures are the MDBE (see Chapter 3) and AMDO (see Chapter 4) approaches proposed in this thesis, and the most relevant multidimensional design methods introduced in the literature. Each approach is placed in the 3D-space according to the conclusions extracted from Section 2.1.4. On the one hand, the first figure shows that the automation degree achieved, in the general case, is medium or low. Only 6 approaches automate the design task up to a fair degree. Importantly, this figure shows our first main contribution: both the MDBE and AMDO approaches automate the design task as much as possible. However, note that they follow two different paradigms. Despite considering both, requirements and the data sources as first-class citizens, MDBE leads the process by exploiting the knowledge of the requirements, whereas AMDO leads the process from a thorough analysis of the data sources (and thus, they are placed in opposite vertexes). On the other hand, the quality of the output produced by most approaches is medium / high, but MDBE and AMDO produce yet semantically richer outputs. In other words, they are able to extract more valuable knowledge from the requirements / data sources. All these assertions will be properly justified in this document, but our approaches provide detailed algorithms for discovering multidimensional concepts traditionally overlooked such as factless facts, bases,aggregate measures and semantic relationships between the multidimensional concepts 15 identified. As said, both methods are complementary, as each one starts from a different set of assumptions. In this thesis, our objective is to provide the best method for each potential real-world scenario we may find. In this sense, MDBE follows a classical approach. It assumes that the data warehouse designer has been able to gather the organization multidimensional requirements (it means, then, that the end-user has been able to clearly state which are his / her informational needs). By analyzing the data sources and requirements, MDBE generates schemas fulfilling the requirements and conciliating them with the data sources. In contrast with MDBE, AMDO focuses on those scenarios in which the multidimensional requirements are not clear, and a thorough analysis of the organization data is required. Nowadays, many organizations are not aware of their own data and therefore, of their own potential analysis perspectives. In these cases, it is interesting to use AMDO to discover them and help the end-users to decide what kind of analysis could be of their interest. However, different from traditional supply-driven approaches, AMDO filters results obtained in each stage (by means of quality evidences) and performs the upcoming stages with knowledge known to be of interest to the user. 1.7.2 Integrating Requirements in a Largely Automated Design Approach Our first relevant contribution is a largely automated approach for supporting multidimensional design based principally on Multidimensional Design By Examples (MDBE); an automated method following an interleaved hybrid approach. Unlike other hybrid approaches, MDBE does not carry out two well-differentiated phases (i.e., data-driven and requirement-driven) that need to be conciliated a posteriori but instead performs both phases simultaneously. Consequently, each paradigm benefits from feedback obtained by the other, and eventually MDBE is able to derive more valuable information than approaches in which the two phases are carried out sequentially. To our knowledge, this is the first interleaved hybrid method introduced in the literature. In our approach we derive MD conceptual schemas from relational sources according to enduser requirements. There are two steps: requirement formalization and the MDBE method. As in previous requirement-driven methods (or requirement-driven stages within hybrid methods), a prior requirements elicitation step is required. However, our approach is not based on a step-by- step manual process in which the requirements and data sources that will eventually derive the MD schema are analyzed in details, but rather on a largely automatable approach. Requirements are typically expressed at a high level of abstraction and need to be formalized prior to automation of the analysis step. In our framework, requirements are expressed as SQL queries over the relational data sources (i.e., at the logical level over the data sources). SQL queries provide a clearly defined structure that will facilitate full automation of the MDBE method (the second step in our approach). Although requirement formalization must be performed manually, translating requirements into SQL queries requires considerably less effort than carrying out any of the step-by-step requirement-driven approaches in current use. In our approach, we have reduced the amount of manual operations as much as possible (i.e., removing ambiguous semantics by formalizing the requirements) and delegated most of the design workload to the MDBE method, which will use the semantics captured in the requirements and the data sources to automate the rest of the process. The inputs of the MDBE method are the end-user information requirements (expressed as 16 SQL queries) and the integrated logical model of the data sources. The output is a constellation schema (i.e., a star schema for each fact identified) derived from the data sources and capable of retrieving data requested in the input requirements. Briefly, MDBE validates whether each input SQL query represents a valid cube-query (i.e., if the query retrieves data that can be analyzed from a multidimensional perspective). Note that we translate requirements into regular SQL queries over the transactional data sources and do not require a specific translation that would make multidimensional sense. MDBE analyzes each input SQL query to validate whether it represents a multidimensional requirement and notifies if it is able to derive at least one multidimensional schema that can retrieve data requested in the SQL query. Conciliation of the schemas proposed for each query produces the output constellation schema. 1.7.2.1 Correspondence Between SQL and the Multidimensional Algebra The validation step of the MDBE method gives rise to another relevant contribution. The MDBE method generates sound and meaningful multidimensional schemas by validating if each input SQL query represents a valid multidimensional query. In other words, if the input SQL query represents a valid set of multidimensional operators. Unfortunately, we do not dispose of a standard set of multidimensional operators (see section 1.3). To overcome this major drawback we carried out a thorough study to identify a set of multidimensional operators subsuming all the operators introduced in the literature. Then, we analyzed how these operators should be translated into SQL queries (i.e., when mapping from the multidimensional to the relational model, like a ROLAP tool would internally do). As consequence, we were able to identify the subset of SQL corresponding to the multidimensional algebra and viceversa; as well as three problematic scenarios that must be considered (and fixed if needed) during the translation process to avoid changing the semantics of the multidimensional query performed. This study conforms the foundations of the MDBE validation process. An input SQL query is said to represent a valid set of multidimensional operators if we are able to find a correct mapping from the SQL query to the multidimensional algebra. If so, we will be able to find a multidimensional schema meeting the requirements stated in the query. Note that, beyond our purpose, this work can be reused for validating the multidimensional queries generated in a ROLAP tools. Importantly, the criteria identified in this study correspond to the integrity constraints of the multidimensional model considering multidimensionality as the data structure, and the whole set of multidimensional operators surveyed as the set of operators allowed to handle data. 1.7.3 Automatic Multidimensional Design from Ontologies AMDO assumes a scenario in which the data sources available are semantically richer and therefore, it does not ask for the multidimensional requirements beforehand. Oppositely to MDBE, it is a sequential hybrid approach (a fully supply-driven followed by a demand-driven stage) aimed at discovering relevant knowledge for analysis purposes. Furthermore, it does not work over relational sources but from a conceptual view of the organization business. Indeed, we start from a conceptual formalization of the domain to avoid being tied to logical design decisions that 17 would directly impact on the quality of the output schemas. The role of a conceptual layer on top of information systems has been discussed in depth in the literature. In case of reengineering processes like the data warehouse conceptual design, the benefits are clear: the conceptual layer provides more and better knowledge about the domain to carry out this task. Note that MDBE overcomes the limitations of the logical schemas by means of the multidimensional requirements. In our approach we choose Description Logics (DL) ([BCM+03]) ontologies as our method input. Thus, we benefit from the reasoning services provided by ontology languages, that will facilitate the automation of our task. Although other works already proposed to work at the conceptual level, AMDO is the first method presented in the literature automating the whole design task: i.e., identifying facts, measures and dimension hierarchies. As a novel contribution, AMDO also identifies potential bases (see section 1.5) of interest for each fact discovered. AMDO considers all the multidimensional concepts in depth by analyzing their semantics and how they should be identified from the sources. As result we propose new and original design patterns. Previous (conceptual) approaches mainly rely on their requirement elicitation (i.e., demand-driven) stages to discover the multidimensional concepts rather than on an accurate analysis of the data sources. In this sense, AMDO follows a completely different framework based on a thorough and fully automatic analysis of the sources and then, carrying out a guided requirement elicitation stage a posteriori. Therefore, unlike previous approaches, the automatic analysis of the sources leads the process and we allow the designer to restrict and control the process by stating his / her requirements on the fly. Importantly, AMDO does not generate endless amounts of multidimensional results, but, prior to show them to the user, filters them according to quality indicators. To our knowledge, our approach is the first one considering the data warehouse design from ontologies. Hence, we do believe that this work opens new interesting perspectives. For example, we can extend the data warehouse and OLAP concepts to other areas like the Semantic Web, where ontologies play a key role providing a common vocabulary. One consequence would be that despite the data warehouse design has been typically guided by data available within the organization, we would be able to integrate external data from the web into our data warehouse to provide additional up-to-date information about our business domain (this novel concept of data warehousing is known in the literature as Web-Warehousing [RALT06]). 1.8 Organization of the Thesis This thesis has been organized in five chapters (including this one). A brief overview of each one is shown below. 1.8.1 Second Chapter: Related Work This chapter presents the state of the art of two different topics: multidimensional design methods and multidimensional algebras. While the first one aims to contextualize the work carried out in this thesis, the second one is needed to identify the multidimensional model constraints, which must be enforced when automating the multidimensional design task. All in all, we present a detailed picture of the current state of both fields, as well as a comprehensive comparison between current methods / algebras presented in the literature. 18 1.8.2 Third Chapter: Integrating Requirements in a Largely Automated Design Approach This chapter presents the first of the two multidimensional design methods introduced in this thesis: a largely automated approach based on MDBE. We start this chapter explaining the overall idea behind this approach. This method takes a classical approach. We assume that the end-user knows his / her informational needs and therefore, the system designer will be able to gather the multidimensional requirements. After a detailed explanation of how MDBE works, we discuss its set of contributions regarding the related work. As discussed in this chapter, MDBE is the first method formalizing the end-user requirements (as SQL queries over the OLTP systems), and automating their use at the same time as analyzing the data sources. This approach gives rise to a new and original framework that we call interleaved hybrid approach. Next, we discuss how we are able to derive correct multidimensional schemas from SQL queries representing the multidimensional requirements. Our work focuses on a deep analysis of the multidimensional semantics regarding SQL. In short, we identify the mapping between the multidimensional algebra and SQL, which relevantly, it is the same that a ROLAP tool would exploit. If the SQL query represents a correct multidimensional navigation path (i.e., a set of multidimensional operators), we map it onto the data sources and accordingly, we identify which multidimensional role each relational concept must play. Eventually, this mapping will produce a multidimensional schema. Once the foundations of the MDBE method have been set, we introduce a detailed step-by- step view of our method. Furthermore, we also introduce a practical case of study (the TPCH-H) to show the feasibility of the method and the quality of results obtained. Prior to present our conclusions, we also introduce the MDBE tool that implements our method. 1.8.3 Fourth Chapter: Multidimensional Design from Ontologies This chapter presents our second approach for automating the multidimensional design task: the AMDO method. This chapter emulates as much as possible the structure of the previous one. First, we introduce the main idea behind our approach. Although classical approaches for information systems design start with a requirement elicitation stage, sometimes, it may be difficult to gather them. The data warehousing system design is a reengineering task and therefore, it must consider the underlying operational sources of the organization. This approach, despite considering the end-user requirements as first-class citizens, it starts by thoroughly analyzing the data sources, as any supply-driven approach would do. However, we provide a novel framework by completely automating the process from the conceptual point of view. After discussing the general idea and the main contributions of AMDO, we present our method and we set and formalize its working context. First, we introduce the multidimensional patterns it applies to analyze the data sources. Then, we discuss how to efficiently compute them. Relevantly, AMDO relies on a novel algorithm conceived to discover bases (i.e., multidimensional keys), which have been traditionally overlooked in the design process. In this chapter, we provide two different case studies upon which we show AMDO’s feasibility: the EU-Car Rental and the TPC-H. Finally, we conclude by introducing the the AMDO tool, 19 which implements our approach. 1.8.4 Fifth Chapter: Conclusions and Further Work Conclusions about the work presented in this thesis and future work to be carried out are discussed in this section. 20 Chapter 2 Related Work “ In the middle of difficulty lies opportunity. ” Albert Einstein The related work discussed in this chapter refers to two different topics: multidimensional design methods and multidimensional algebras. The necessity of the first study is clear. This thesis introduces two novel multidimensional design methods and therefore, it is a must to clearly depict the current situation of the area. On the contrary, the reason why a study about multidimensional algebras is relevant to this thesis is, at first sight, subtler. As discussed in Section 1.7, one of this thesis main objectives is to automate, as much as possible, our design approaches and consequently, automatically produce correct multidimensional schemas. Automating the design task, however, entails that outputs produced must have been validated during the process. A multidimensional schema is correct if (i) it is aligned with the multidimensional data structure and (ii) preserves the multidimensional integrity constraints (see Section 1.3). Only then, we can guarantee that data manipulation (by means of the multidimensional operators) will always be correct. Despite we do not yet benefit from a standard multidimensional model, there is a general consensus on the model data structure (indeed, the multidimensionality introduced by Kimball -see Section 1.2.1- is assumed to be a de facto data structure standard), but this is not the case of the model integrity constraints and set of operators. For this reason, we surveyed all the multidimensional algebras that, to our knowledge, were introduced in the literature. After this analysis, we were able to find an implicit agreement on how multidimensional data should be manipulated and eventually, identify the multidimensional integrity constraints preserving a correct data manipulation. Thus, the schemas produced by our approaches guarantee the multidimensional constraints identified in our study and consequently, they fully make multidimensional sense. For both topics, we first present a detailed state of the art and later, a comprehensive framework that will facilitate the comparison and further discussion of the methods / algebras we may 21 find in the literature. 2.1 Multidimensional Design Methods 2.1.1 Terminology For the sake of understandability, in this document we take advantage of the method classification introduced by Winter & Strauch [WS03]. For this reason, we first introduce the notation proposed. According to it, multidimensional modeling methods may be classified within a demand-driven, a supply-driven or a hybrid framework. They properly define each framework as follows: •Supply-driven approaches: Also known as data-driven, start from a detailed analysis of the data sources to determine the multidimensional concepts in a reengineering process. •Demand-driven approaches: Also known as requirement-driven or goal-driven, focus on determining the user multidimensional requirements (as typically performed in other information systems) to later map them onto data sources. •Hybrid approaches: Propose to combine both paradigms in order to design the data warehouse from the data sources but bearing in mind the end-user requirements. In this document, we distinguish as well between interleaved hybrid approaches and sequential hybrid approaches. The main difference is that sequential approaches perform the demand-driven and supply-driven stages independently and later on conciliate results got in a final step, whereas interleaved approaches perform both stages simultaneously benefiting from feedback retrieved by each stage all over the whole process and obtaining better results at the end. 2.1.2 A Comprehensive Survey This section presents an insight into current multidimensional design methods. These methods were selected according to three factors: reference papers with a high number of citations (according to Google Scholar [Goo] and Publish or Perish [Har]), papers with novelty contributions and in case of papers of the same authors, we have included the latest version of their works. As general rule, each method is described and classified according to the terminology presented in Section 1.5. Finally, we follow a chronological order when introducing the design methods surveyed. Thus, we provide a comprehensive framework of the evolution of multidimensional design methods (note that Section 1.4.1 sketches this survey): Kimball et al. [KRTR98] introduced multidimensional modeling as known today. In addition, they also introduced the first method to derive the multidimensional schema. Being the first approach, it does not introduce a formal design procedure, but a detailed guide of tips to identify the multidimensional concepts and then, give rise to the multidimensional schema. The presentation is quite informal and it relies on examples rather than on formal 22 rules. Kimball’s approach follows a demand-driven framework to derive a data warehouse relational schema (i.e., logical). First, the designer must identify all the data marts we could possibly build. Data marts are essentially defined as pragmatic collections of related facts. Although data sources are not considered, they already suggested to take a look to the data sources to find which data marts may be of our interest. Next step aims to list all conceivable dimensions for each data mart. At this point it is suggested to build an ad hoc matrix to capture our multidimensional requirements. Rows represent the data marts, whereas columns represent the dimensions. A given cell is marked whether that dimension must be considered for a data mart. This matrix is also used to show the associations between data marts by looking at dimensions shared. This process is supposed to be incremental. First, it is suggested to focus on single-source data marts, since it will facilitate our work and later, in a second iteration, look for multiple-sources data marts combining the single-source designs. The method’s third step designs the fact tables of each data mart: •First, we must declare the grain of detail (i.e., the data granularity of interest). It is suggested to be declared by the design team at the beginning, although it can be reconsidered during the process. Normally, it must be determined by primary dimensions. •Next, we choose the analysis dimensions for each fact table. Dimensions selected must be tested against the grain selected. This must be a creative step. We need to look for the dimension pieces (i.e. levels and descriptors) in different (and potentially heterogeneous) models and through different documents which, in the end, results in a time-consuming task. At this point, it is also suggested to choose a large number of descriptors to populate dimensions. •Finally, the last stage adds as many measures as possible within the context of the declared grain. Cabibbo and Torlone [CT98a] present one of the most cited multidimensional design methods. This approach generates a logical schema from Entity-Relationship [Che76] (ER) diagrams, and it may produce multidimensional schemas in terms of relational databases or multidimensional arrays. At first sight, this method may be thought to follow a supplydriven paradigm, as it performs an in-depth analysis of the data sources. However, no formal rules to identify the multidimensional concepts from the data sources are given. In fact, multidimensional concepts must be manually identified by the user (i.e., from requirements). For this reason, we consider it to follow a hybrid framework. In general, like Kimball’s approach, this approach is rather informal but they set up the foundations that were later used by the rest of methods. This method consists of four steps. First and second steps aim to identify facts and dimensions and restructure the ER diagram. Both steps may be performed simultaneously and benefit from the feedback retrieved by each step. Indeed the authors suggest to perform them in an iterative way to refine results obtained. However, no clue about how to identify 23 introduced by Kimball like the rest of methods do, and they present a high-level step-by- step guideline. In short, they identify the best practices that a data warehouse design project must consider, according to their analysis task. The design process must be iterative and it is divided into four stages: •First step embraces the analysis of the information supply (i.e., from the sources) and the analysis of the information needed. •Next, we must match requirements demanded with current information supply and order requirements accordingly. •In a third step, information supply and information demand must be synchronized on a full level of detail (i.e., considering data granularity selected). •Finally, we must develop the multidimensional schema. This schema must be evaluated and if needed, reformulate the process from the first step to develop the multidimensional schema in an iterative way. Despite this approach gives relevance to the data sources and demands to synchronize data demanded with the sources, we consider it to be a demand-driven approach since no clue about how to analyze the data sources is given. Vrdoljak et al. [VBR03] present a semi-automatic supply-driven approach to derive logical schemas from XML schemas. This approach considers XML schemas as data sources. Therefore, the authors propose to integrate XML data in the data warehouse, as XML is now a de facto standard for the exchange of semi-structured data. Their approach works as follows: •Preprocessing the XML schema: The schema is simplified to avoid complex and redundant specifications of relationships. •Creating and transforming the schema graph: Every XML schema can be represented as a graph. Two transformations are carried out at this point; functional dependencies are explicitly stated (by means of key attributes) and nodes not storing any value are discarded. •Choosing facts: Facts must be chosen among all vertexes (i.e., nodes) and arcs (i.e., edges) of the graph. An arc can be chosen only if it represents a many-to-many relationship. •Building the dependency graph: For each fact, a dependency graph is built. The graphical representation of the XML schema facilitates finding the functional dependencies. The graph must be examined in the direction expressed by arcs and according to cardinalities included in the dependency graph. It may happen that no cardinality is provided. In this case, XML documents are queried by means of XQueries to look for to-one relationships. The authors also consider many-to-many relationships to be of interest in some cases. However, these cases must be manually identified by the user. Finally, the dependency graph will give rise to aggregation hierarchies. 30 •Creating the logical schema: Facts and measures are directly depicted from vertexes and arcs chosen whereas dimensions are derived from the aggregation hierarchies identified. Jensen et al. [JHP04] present a supply-driven method from relational databases. They present data-mining techniques to be applied over the intensional data to discover functional and inclusion dependencies and, eventually, derive snowflake schemas. Their method starts collecting metadata such as table and attribute names, cardinality of attributes, frequency, etc. Later, data is divided into three groups according to its potential multidimensional role: measure, keys and descriptive data. Next, integrity constraints such as functional and inclusion dependencies are identified between attributes and finally, the snowflake schema is produced. First two steps are performed consulting the database catalog. The role of each attribute is derived with a bayesian network that takes as input metadata collected for each attribute. Third step discovers the database structure by identifying functional and inclusion dependencies that represent many-to-one relationships that will give rise to dimensions. Candidate keys and foreign keys are identified assuming that there are no composite keys in the database. Furthermore, inclusion dependencies among foreign keys and candidate keys are identified in this step. These dependencies will be mainly used to identify dimensions. This step is critical, since all permutations of candidate keys and foreign keys are constructed with the consequent computational cost. To pair two keys, both must have the same attribute type and the candidate key must have, at least, as many distinct values for the attribute as the table containing the foreign key. If these constraints hold, a SQL statement is issued to check if the join of both tables (by means of these attributes) has the same cardinality as the table containing the candidate foreign key. If so, an inclusion dependency is identified between both keys. Next, they propose an algorithm to derive snowflake schema from this metadata: •Fact tables are identified in a semi-automatic process involving the user. First, facts are proposed by means of the table cardinality and the number of measures identified by the bayesian network. Then, the user chooses those of his / her interest. •Inclusion dependencies discovered form different connected graphs. A connected graph is considered to be a dimension if exists a inclusion dependency between a fact table and a graph node. In this case, that node will play the atomic level role of the dimension. The authors propose an algorithm to break potential cycles and give rise to the aggregation hierarchy from the graph. When shaping the aggregation hierarchy, two consecutive levels are analyzed to avoid aggregation problems (i.e., duplicated or lost values). Giorgini et al. [GRG05] present a hybrid approach to derive the conceptual multidimensional schema. They propose to gather multidimensional requirements and later map them onto the data sources in a conciliation process. However, they also suggest that their approach could be considered a pure demand-driven if the user do not want to consider the data sources. 31 The authors introduce an agent-oriented method based on the i* framework [Yu97]. They argue that it is important to model the organization setting in which the data warehouse will operate (organization modeling) and capture the functional and non-functional requirements of the data warehouse (what authors call the decisional modeling). If we consider their hybrid approach, the next step is to match requirements with the schema of the operational sources. In this approach both ER diagrams and relational schemas are allowed as inputs describing the data sources. This matching stage consists of three steps: •Requirement mapping: Facts, dimensions and measures identified during the requirement analysis are now mapped over the data sources. According to the kind of data sources considered, the authors introduce a set of hints to map each concept. For example, facts are mapped onto entities or n-ary associations in ER diagrams and onto relations in relational schemas. •Hierarchy construction: For each fact identified, the data sources are analyzed looking for functional dependencies based on the algorithm already discussed in [GMR98]. •Refinement: This step aims to rearrange the fact schema in order to better fit the user’s needs. In this process, we may distinguish among concepts available (mapped from requirements), unavailable (demanded in the requirements but not mappable to the data sources) and what is available and not needed. The authors propose to use this information to reorder dimensions (grafting and pruning the aggregation hierarchies) and / or try to find new directions of analysis. Prat et al. [PACW06] present a method to derive the conceptual, logical and physical schema of the data warehouses according to the three abstraction levels recommended by ANSI / X3 / SPARC. Starting from end-user requirements, the conceptual phase leads to a UML [Grob] model. To this end, UML is enriched with concepts relevant to multidimensionality that will facilitate the generation of the logical schema. The logical phase maps the enriched UML model into a multidimensional schema and finally, the physical phase maps the multidimensional schema into a physical database schema depending on the target implementation tool (in this case Oracle MOLAP). At each phase, they introduce a metamodel and a set of transformations to perform the mapping between metamodels. In this study, we will focus on the method to produce the conceptual and logical schemas and we will avoid to discuss the transformations to be performed to derive the physical schema. •Conceptual phase: In this first step, the authors embrace requirements elicitation and the conceptual representation of requirements. First, requirements should be captured by means of a UML-compliant system analysis method. Requirements engineering techniques used in transactional design processes may be considered, and for example, they mention interviews, joint sessions, study of existing reports and prototyping of future reports as potential techniques to be used. Next, requirements are represented in a UML class diagram that needs to be enriched to capture multidimensional semantics. To do so, they present an extension of the UML metamodel. 32 –Classes which are not association classes are denoted as ordinary classes. Similarly, associations which are not association classes are denoted as ordinary associations. –Each attribute of an ordinary class must be identified as an attribute or not. According to authors, it must be decided by the end-user and designers jointly. –Each attribute belonging to one-to-one or many-to-one relationships is transferred to the to-many side. –Generalizations are transformed to facilitate their mapping to the logical level. Each specialization is mapped to a new class that is related to the superclass by means of an aggregation relationship. •Logical phase: Creating the logical schema from the enriched conceptual model produced in the first phase is immediate and a set of transformations expressed in Object Contraint Language (OCL) [Groa] are presented. They also introduce an ad hoc multidimensional metamodel to represent the logical schema as follows: –Every many-to-many association of the conceptual model is identified as a fact of interest and their attributes (if any) are mapped into measures of the fact. This fact would be dimensioned by mapping the ordinary classes directly or indirectly involved in the association. Similarly, every ordinary class containing numerical values of interest is also identified as a fact. In this case, the fact is dimensioned by one dimension level defined by mapping the class (similar to the approach presented in [PD02]). –Next, following many-to-one relationships between ordinary classes we give rise to aggregation hierarchies for each dimension level identified in the previous step. –Descriptors are defined from those non-identifier attributes from the classes involved in the dimension hierarchy that have not been chosen as measures of interest. –Finally, for each measure and for each dimension related to the fact where the measure is defined, it is compulsory to define which aggregation functions preserve a meaningful aggregation. Maz´ on et al. [MTL07] present a semi-automatic hybrid approach that obtains the conceptual schema from user requirements and then, verifies and enforces its correctness against the data sources by means of Query / View / Transformation (QVT) relations. Their approach work over relational sources and requirements expressed in the i* framework. The modus operandi of this approach shares many common points with [BCC+01], but in this case, they also provide mechanisms for validating the output schema. This approach starts with a requirement analysis phase. They introduce a detailed demanddriven stage in which the user should state his / her requirements at high level by means of business goals. Then, the information requirements are derived from the information business goals. Both, goals and information requirements must be modeled by an adaptation of the i* framework and eventually, the multidimensional conceptual schema must be 33 derived from this formalization. Finally, the authors propose to express the resulting multidimensional schema by using an ad hoc UML extension (i.e., their own data structure) provided in the paper. Next, they propose a final step to check the conceptual multidimensional model correctness. The objective of this step is twofold: they present a set of QVT relations based on the multidimensional normal forms (MNF) to align the conceptual schema derived from requirements with the relational schema of the data sources. Thus, output schemas will capture the analysis potential of the sources and at the same time, they will be validated according to the MNF. The MNF used in this paper are an evolution of those used in [HLV00], and they share the same objective. By means of five QVT relations that may be semi-automated, this paper describes how the conceptual multidimensional schema should be aligned to the underlying relational schema: •1MNF (a): A functional dependency in the conceptual schema must have a corresponding functional dependency in the relational schema. •1MNF (b): Functional dependencies among dimension levels contained in the source databases must be represented as aggregation relationships in the conceptual schema. Therefore, they complement the conceptual schema with additional aggregation hierarchies contained in the sources. •1MNF (c): Summarized measures that can be derived from regular measures must be identified in the conceptual schema. Therefore, they support derived measures. •1MNF (d): Measures must be assigned to facts in such a way that the atomic levels of the fact form a key. In other words, they demand to place the measure in a fact with the correct base (and thus, preserve the proper data granularity). •2MNF and 3MNF: These constraints demand to use specializations of concepts when structural NULLs in the data sources do not guarantee completeness. Song et al. [SKD07] present an automatic supply-driven method that derives logical schemas from ER models. This novel approach automatically identifies facts from ER diagrams by means of the connection topology value (CTV). The main idea underlying this approach is that facts and dimensions are usually related by means of many-to-one relationships. Concepts at the many-side are fact candidates and concepts in the one-side are dimension candidates. Moreover, it distinguishes between direct and transitive many-to-one relationships: •First, the authors demand a preprocess to transform ER diagrams into binary (i.e., without ternary nor many-to-many relationships) ER diagrams. •The CTV value of an entity is a composite function of the topology value of direct and indirect many-to-one relationships. In this formula, direct relationships have a higher weighting factor with regard to transitive ones. Thus, all those entities with a CTV value higher than a threshold are proposed as facts. Note that facts are identified by their CTV and therefore, it would be possible to consider factless facts. 34 •For each fact entity, its analysis dimensions are identified by means of many-to-one relationships. Moreover, the authors propose to use Wordnet and annotated dimensions (that represent commonly used dimensions in business processes) to enrich aggregation hierarchies depicted. This approach does not introduce any clue to identify measures, levels and descriptors. However, working over ER diagrams, it would be rather easy to assume that measures are identified by means of numerical attributes once a concept has been identified as a fact, whereas descriptors can be identified from those entities identified as dimensions. Furthermore, no clue about how to identify levels is given and indeed, in the examplification provided in the paper, every dimension identified contains just one level (i.e., they do not identify aggregation hierarchies). 2.1.3 Comparison Criteria In order to provide a comprehensive framework of the multidimensional design methods, we aim to provide a detailed comparison of the methods discussed in the previous section. Setting a basis for discussion will facilitate the mapping of the surveyed methods to a common framework from which compare each approach, detect trends such as features in common or analyze the evolution of assumptions made by the modeling methods. For this reason, this section presents the criteria used in the comparison presented in Section 2.1.4. These criteria were defined in an incremental analysis of the methods surveyed. For each method we captured its main features that were mapped onto different criteria. If a method introduced a new criterion, the rest of works were analyzed to know their assumptions with regard to this criterion. Therefore, criteria presented below were defined in an iterative process during the analysis of the multidimensional design methods. We have summarized these criteria in three main categories: general aspects, dimensional data and factual data. A graphical representation of these features is found in Figure 2.1. Next to each criterion, the values it may take are provided (in brackets, the acronyms). For example, the values that we assign for the paradigm criterion are demand-driven (DD), supply-driven (SD), interleaved hybrid (IH) or sequential hybrid (SH). General aspects refer to those criteria regarding general assumptions made in the method, whereas dimensional and factual data criteria refer to how dimensional data and factual data are identified and mapped onto multidimensional concepts. General Aspects: The general criteria are summarized into nine different items: •Paradigm: According to our terminology introduced in Section 2.1.1, multidimensional modeling methods may be classified as supply-driven, demand-driven or hybrid approaches. The reader may found a slightly different classification in [LBMS02]. •Application: Most methods are semi-automatic. Thus, some stages of these methods must be performed manually by an expert (normally those stages aimed to identify factual data) and some others may be performed automatically (normally those aimed to identify dimensional data). In general, only a few methods fully automate the whole process. On 35 Figure 2.1: Graphical view of the criteria used for comparing the multidimensional design methods the contrary, most methods present a detailed step-by-step guide that is assumed to be manually carried out by an expert. •Pre-process: Some methods demand to adapt input data into a specific format that facilitates their work. For instance, these processes may ask to enrich a conceptual model with additional semantics or perform data mining over data instances to discover hidden relationships. •Input abstraction level: Most methods (mainly those automatable) work with inputs expressed at a logical level (e.g., relational schemas) whereas some others work with inputs at a conceptual level (e.g., from conceptual formalizations such as ER diagrams or from requirements in natural language). •Output abstraction level: Several methods choose to directly generate a star or snowflake schema, whereas some others produce multidimensional conceptual schemas. Although many approaches argue that the data warehouse method should span the three abstraction 36 levels, only a few of them produce the conceptual, logical and physical schema of the data warehouse. •Data sources: There are three items summarizing main features about how data sources are considered in the method. –Type of data sources: The input abstraction item informs about the abstraction level of the input, whereas this item specifies the kind of technology of the data sources supported by the method. For example, if the method works at the conceptual level it may work from UML, ER conceptual schemas or OWL ontologies, and if it works at the logical level it may work from relational schemas or XML schemas. –Data sources analysis: Most methods perform a fully supply-driven analysis of the data sources. However, some of them also perform a requirement-driven analysis of the data sources. Clearly, this item is tightly related to the paradigm item. Nevertheless, note that a method may follow a hybrid approach but do not consider at all requirements when analyzing the data sources. –Pattern formalization: Supply-driven stages usually define design patterns to identify the potential multidimensional role that concepts depicted in the data sources may play. Some methods present these patterns in an informal way, but most of them use some kind of structured language. For example, ad hoc algorithms are the most common representation but some other methods use description logic formulas or QVT Transformations. •Requirements representation: If requirements are considered, this item summarizes how requirements are represented. For example, most methods use ad hoc representations (like forms, sheets, tables or matrixes), whereas some others use UML diagrams or the i* framework. Finally, some of them lower the level of abstraction of requirements to a logical level by means of SQL queries or MDX queries [Mic]. •Validation: Some methods integrate a validation process to derive meaningful multidimensional schemas. For example, restricting summarization of data to those dimensions and functions that preserve data semantics or forming multidimensional spaces by means of orthogonal dimensions. •Implementation: Some methods have been implemented in CASE tools or prototypes. Factual Data: These criteria summarize how a given method identifies and handles factual data (i.e., facts and measures). First, criteria used to identify measures are summarized as follows: •Data sources: Up to now, looking for numerical concepts is the only heuristic introduced to identify measures from the data sources. •Requirements: Most approaches consider requirements to identify measures. We distinguish if the method only considers explicit measures or also implicit ones. Implicit measures are those explicitly stated in the requirements but implicit in the data sources (i.e., 37 there is not a concept in the data sources that would correspond to it, but they can be derived from an already existing concept(s) in the data sources). For example, derived measures. Therefore, some kind of reasoning over the data sources is needed. Next, we introduce criteria used to identify facts. These criteria refer to how facts are identified from the data sources or from requirements, and how they may be semantically related in the resulting schema: •Factless facts: This kind of facts were introduced by Kimball [KRTR98]. They are also known as empty facts and they are very useful to describe events and coverage and a lot of interesting questions may be asked from them. •Data sources: Most of the methods demand to explicitly identify facts by means of the requirements, but some others use heuristics to identify them from the data sources. For example, in case of relational sources, most use heuristics such as table cardinalities and the number of numerical attributes that a table contains. Furthermore, some works also look for concepts with high to-one connectivity (i.e., with many potential dimensional concepts). •Requirements: Similar to measures, if requirements are considered, we distinguish among explicit and implicit facts. However, implicit facts have a slightly different meaning. We denote by implicit facts those that have not been explicitly stated in the requirements but can be identified from a requirement-driven analysis of the sources. •Semantic relationships: In case of producing a conceptual schema, some methods are able to identify semantic relationships between facts. We distinguish among associations, aggregations (also called roll-up / drill-down relationships) and generalizations. In the multidimensional model, it means that we may perform multidimensional operators such as drill-across or drill-down over them. Dimensional Data: These criteria analyze how the method identifies and handles dimensional data (i.e., dimensions, levels and descriptors). We have two main groups of items. Those referring to how dimensional data is identified (either from the data sources or from requirements), and how they are semantically related in the resulting schema. The process to identify dimensions, levels and descriptors must be understood as a whole and unlike criteria used to identify factual data we do not distinguish among criteria to look for different dimensional concepts. Roughly speaking, most approaches start looking for concepts representing interesting perspectives of analysis and from these concepts they look for aggregation hierarchies (i.e., levels). The whole hierarchy is then identified as a dimension and level attributes are considered to play a descriptor role: •Fact-centered: Most methods look for dimensional data once they have identified facts. From each fact, dimensional concepts are identified using a wide variety of techniques according to the method inputs, but always looking for functional dependencies from the fact. 38 •Data sources: There are several techniques to identify dimensional concepts from data sources. We classify these techniques in three main groups: discovering functional dependencies, discovering bases and others. At the conceptual level, functional dependencies are modeled as to-one relationships, and at the logical level it depends on the technology. For example, in the relational model, dimensional concepts are identified by means of foreign keys and candidate keys. Bases (see Section 1.5 for further information) are used to identify dimensional concepts as well. In this case, the method looks for candidate multidimensional bases in order to identify interesting perspectives of analysis (i.e., levels). •Requirements: Dimensional concepts are mostly identified from the data sources once facts and measures have been identified. However, demand-driven approaches rely on requirements to identify dimensional concepts and some hybrid approaches also enrich their supply-driven stages with requirements. Like facts, we distinguish between explicit dimensional concepts and implicit ones. •Intra-dimensional: Most of the methods distinguish between descriptors and levels, but some others do not. •Inter-dimensional: Some approaches are able to identify semantic relationships between dimensions. In this case, we consider associations and generalizations as potential relationships. 2.1.4 Methods Comparison In this section we present a detailed summarization of the main features of each method regarding the criteria introduced in previous section, which provides a common framework to compare and discuss methods surveyed. Results are shown in Tables 2.1 and 2.22, in which MDBE (see Chapter 3) and AMDO (see Chapter 4) are also considered. Methods surveyed are distributed in these tables according to the chronological order. There, rows correspond to criteria introduced in Section 2.1.3 and columns correspond to each method studied. A given cell contains information for a method for a certain criterion (we address the reader to Figure 2.1 to remind the meaning of each acronym). Most of the criteria are evaluated as yes / no, but some other have alternatives. Acronyms used to represent these alternatives may be found in Figure 2.1. Two general values can be found for any criterion: -means that this criterion does not make sense for the method (for example, if it does not consider the data sources then, any of the criteria related to them cannot be evaluated for this method), whereas none means that, despite this criterion could be considered for this method, none of the alternatives are considered (i.e., it is overlooked). Therefore, none is the equivalent to the no value but for criteria having several values. Analyzing these tables we can find some interesting trends as well as assumptions that have been considered in most of the methods surveyed. First approaches tried to contextualize the multidimensional modeling task by providing tips and informal rules about how to proceed. In other words, they presented the first guidelines to support multidimensional design. Later, when 2Note that these tables were used to produce Figures 1.3 and 1.4 in pages 14 and 15. 39 the translation of a multidimensional operator combines more than one relational operator, the subscript +is added. Next, we clearly define the relational algebra proper subset mappable from / to the multidimensional algebra (multidimensional concepts are bolded, whereas relational concepts are “quoted”): •The multidimensional selection operator is equivalent to a restricted relational “selection”. It can only be applied over descriptors and then, it is equivalent to restrict the relational “selection” just over level data. According to our notation, we express the multidimensional selection in terms of the relational algebra as σDescriptors. •Similarly, the multidimensional projection operator is equivalent to the relational one restricted to measures; that is, specific Cell data. In terms of the relational algebra we could express it as πMeasures. •OLAP tools emphasize on flexible data grouping and efficient aggregation evaluation over groups, and it is the multidimensional roll-up operator the one aimed to provide us with powerful grouping and aggregation of data. In order to support it, we need to extend the relational algebra to provide grouping and aggregation mechanisms. This topic has been studied and previous works like [LW96], [Klu82] and [Lar99] have already presented extensions of the relational algebra to what is called the grouping algebra. All of them introduce two new operators; one to group data and apply a simple addition, counting or maximization of a collection of domain values and the other one to compute the aggregation of a given attribute over a given nested relation. Following the [Lar99] grouping algebra, we will refer to them as the “group by” and the “aggregation” operators. In terms of this grouping algebra, a roll-up operator consists of a proper “group by” operation along with an “aggregation” of data. •Drill-across typically consists of a “join” between two multidimensional tables sharing the same multidimensional space. Notice that to “join” both tables it must be performed over their common level identifiers that must univocally identify each cell in the multidimensional space (i.e., over the data cube base). Moreover, once “joined”, we must “project” out the columns in the multidimensional table drill-acrossed to, except for its measures. Formally, let Aand Bbe the multidimensional tables implementing, respectively, the origin and the destination Cells involved. In the relational algebra it can be expressed as: Reference Operator “Selection” “Projection” “Join” “Union”/“Diff.” “Group by” “Aggregation” Selection XDescs Projection XMeasures Roll-up XDescsid+XMeasures+ Drill-across XDescsid+XDescsid+ Add Dim. XDescsid changeBase Remove Dim. XDescsid Alt. Base XDescsid+XDescsid+ Union/Difference X Table 2.3: Comparison table between the relational and the multidimensional algebras. 46 πDescriptorsA,MeasuresA,MeasuresB(A./ B) •ChangeBase allows us to rearrange our current multidimensional space either by changing to an alternative base (adding / removing a dimension, replacing dimensions) or reordering the space (i.e., “pivoting” as presented in [FBSV00]). When changing to an alternative base we must assure it does not affect the functional dependency of data with regard to the data cube base. Hence: –When adding dimensions we must preserve the multidimensional space. Thus, it means that the added dimension must be represented as a fixed point in the multidimensional space (i.e., it would not introduce a new axis in the multidimensional space). It can be achieved either by introducing the new dimension at the All level (note that the All level represents the whole dimension as one instance) or by fixing an instance, at any level of detail, by means of a selection. Therefore, in the relational algebra, adding a dimension is achieved through a “cartesian product” between the multidimensional table and the dimension table (that would contain a unique instance). Specifically, if Cis the initial multidimensional table and Dthe relation implementing the added dimension, it can be expressed as: C × D, where |D| = 1 –On the contrary, to remove a dimension we need to get rid of the proper level identifier projecting it out in the multidimensional table. –To change the set of dimensions identifying each cell, i.e., choosing an alternative base in which to place the data, we must perform a “join” between both bases and project out the replaced level descriptors in the multidimensional table. In this case, the “join” must be performed through the identifier descriptors of levels replaced and levels introduced. Formally, let Abe the multidimensional table,Bthe table showing the correspondence between both bases and d1, ..., dnthe identifier descriptors of those dimensions introduced. In the relational algebra, it is equivalent to: πDescriptorsB(d1,...,dn),MeasuresA(A./ B) –Finally, pivoting just asks to reorder the levels identifiers using the SQL “order by” operator, not mappable to the relational algebra. For this reason, it is not included in Table 2.3. •The multidimensional union (difference) unites (differences) two data cubes defined over the same multidimensional space. In terms of the relational algebra, it is equivalent to “union” (“difference”) two multidimensional tables. 2.2.3 A Comprehensive Survey For the sake of comprehension, the reference operators presented in Section 2.2.1 will be bolded in this section, whereas the multidimensional operators introduced in each algebra appear “in quotes”: 47 Li and Wang [LW96] introduce a multidimensional algebra as well as its translation to SQL. To do so, they introduce an ad hoc grouping algebra extending the relational one (i.e., with grouping and aggregation operators). This algebra was one of the first multidimensional algebras introduced, and the authors main aim was to construct data cubes from local operational databases. More precisely, it defines five multidimensional operators representing mappings between either data cubes or relations and data cubes. The “add dimension” and “transfer” operators are aimed to rearrange the multidimensional space similar to a changeBase: while “Add dimension” adds a new analysis dimension to the current data cube, “transfer” transfers a dimension attribute (i.e., a descriptor) from one dimension to another via a cartesian product. Since multidimensional concepts are directly derived from non-multidimensional relations, dimensions may be vaguely defined, justifying the transfer operator; the “cube aggregation” operator performs grouping and aggregation over data, being equivalent to roll-up and finally, the “rc-join” operator, that allows us to join a relational table with a dimension of the data cube, selects those dimension values also present in the table. This low level operator is tightly related to the multidimensional model presented, and it is introduced to relate non-multidimensional relations with relations modeling data cubes. Agrawal et al. [AGS97] present an algebra composed by six operators rather relevant, since they inspired many following algebras. First, “push” and “pull” transform a measure into a dimension and viceversa, as in their model measures and dimensions are handled uniformly. In our framework they would be equivalent to define semantic relationships between the proper dimensions and cells and then, drill-across and changeBase respectively; “destroy dimension” drops a cube dimension rearranging the multidimensional space and hence, being equivalent to changeBase, whereas the “restriction” operator is equivalent to selection; “merge” to roll-up and “join” to an unrestricted drill-across. Consequently, the latter can even be performed without common dimensions between two data cubes, giving rise to a cartesian product. However, a cartesian product does not make any multidimensional sense if it is not restricted, since it would not preserve disjointness when aggregating data ([RA05]). Finally, note that we can project data by means of “pull”ing the measure into a dimension and performing a “destroy dimension” over it. Gyssens and Lakshmanan [GL97] present an algebra based on the classical relational algebra operations. Therefore, it includes “selection”, “projection”, “union” /“intersection” / “difference” and the “cartesian product”; all of them being equivalent to their analogous operators in our reference algebra, except for the latter which is mappable to an unrestricted drill-across as discussed in the previous algebra. The “fold” and “unfold” operators add / remove a dimension, like in a changeBase; whereas roll-up is decomposed in two operators: “classification of tables” (i.e., grouping of data) and “summarization of tables” (aggregation of data). Hence, this algebra proposes to differentiate grouping (i.e., the conceptual navigation between levels through a part-whole relationship or in other words, the result of mapping data into groups) from aggregation (i.e., aggregating data according to an aggregation function). Thomas and Datta [TD97] and [TD01] present an algebra with eight operators based on 48 [AGS97]. Therefore, the “restriction” operator is equivalent to selection; the “metric projection” to projection; the “aggregation” to roll-up and the “union” /“difference” operators to those with the same name in our reference algebra. Moreover, similar to [AGS97], measures can be transformed into dimensions and viceversa. Hence, the “force” and “extract” operators are equivalent to the “push” and “pull” ones. Finally, they rename the “join” operator in [AGS97] as “cubic product”, and denote by “join” an specific “cubic product” over two data cubes with common dimensions (i.e., preserving disjointness if joined through their shared dimensions) since, in general, a cartesian product does not make multidimensional sense. Lehner [Leh98] present an algebra composed by five operators. “Roll-up” and “drill-down” and the “split” and “merge” operators are equivalent to roll-up and drill-down. According to its model data structure that differentiates two analysis phases of data, these four operations are needed because “roll-up” and “drill-down” find and interesting context in a first phase, whereas “split” and “merge” modify the data granularity dynamically by the dimensional attributes (i.e., descriptors) defined in the “classification hierarchies” nodes of the data structure. It also introduces two operators to aggregate data: the “implicit” and the “explicit” aggregation. The first one is implicitly used when navigating by means of “roll-up”s, whereas the second one can be explicitly stated by the end-user. Since they are equivalent, these operators are just differentiated because of the conceptual presentation followed in the paper. Finally, “slicing” operator reduces the multidimensional space in the same sense as selection, whereas the “cell-oriented operator” derives new data preserving the same multidimensional space by means of “unary operators” (-,abs and sign) or “binary operators” (*,+,-,/,min and max). “Binary operators” ask for two multidimensional objects aligned (i.e., over the same multidimensional space). In our framework it is obtained defining derived measures in design time. Cabibbo and Torlone [CT98b], [CT97] and [CT98a] present an algebra with nine operators where, similar to [GL97], roll-up is decomposed into “roll-up” (i.e., grouping) and “aggregation”. “Level description” is equivalent to changeBase: it changes a level by another one related through a one-to-one relation to it. In our framework we should define a semantic relationship among levels involved and perform a changeBase; “simple projection” projects out selected measures and reduces the multidimensional space by dropping dimensions: it can just drop measures (equivalent to projection), dimensions (to changeBase) or combine both. Finally, “abstraction” is equivalent to the “pull” operator in [AGS97] and “selection”, “cartesian product” and “natural join” to those discussed along this section. Hacid and Sattler [HS98] present an algebra based on description logics (DL) and developed from [AGS97]. Therefore, it also introduces “restrict”, “destroy” (equivalent to “destroy Dimension”) and “aggr” (equivalent to “merge”). Furthermore, the “join” and “Join” operators can be considered an extension of the “join” operator in [AGS97]: both operators restrict the original “join” to make multidimensional sense and consequently, being equivalent to drill-across; although the second one also allows to group and aggregate data before showing it (i.e., being equivalent to drill-across and roll-up). 49 Pedersen [Ped00] presents an algebra where “selection”, “projection”, “union” / “difference” and roll-up and drill-down are equivalent to those with the same name presented in our framework, whereas the “value-based join” is equivalent to drill-across and the “identitybased join” to “cartesian product”. Moreover, it also differentiates the “aggregate operation” (i.e., grouping) from the “roll-up”; the “duplicate removal” operator is aimed to remove cells characterized by the same combination of dimensional values. In our framework it can never happen because of the base definition introduced. Finally, it presents a set of non-atomic operators; the “star-join” operator combines a selection with a roll-up, by the same aggregation function, over a set of dimensions, and the “SQL-like aggregation” applies the “aggregate operation” to a certain dimensions and projects out the rest (that is, performs a changeBase). Vassiliadis [Vas00] presents an algebra with three operators. “Navigation” allows us to rollup, and according to [Vas98], it is performed by means of “level-climbing” (reducing the granularity of data), “packing” (grouping data) and “function application” (aggregating by an aggregation function). Finally, “split a measure” is equivalent to projection and “selection” to the reference selection. Yin and Pedersen [YP04] present an algebra over an XML and OLAP federation: “selection cube” allows us to select data; “decoration” adds new dimensions to the data cube (i.e., mappable to a changeBase) and “federation generalized projection” (FGP) roll-ups the data cube and removes unspecified dimensions (changeBase) and measures (projection). Note that although Roll-up is mandatory, FGP can combine it with a projection or/and changeBase. Franconi and Kamble [FK04] present an algebra with four operations. “Slice” and “multislice” select a single or a range of dimensional values; “union” /“intersection” /“difference” combine two aligned data cubes, whereas “join” is rather close to drill-across but in a more restrictive way, forcing both data cubes to share the same multidimensional space. “Derived measures” derives new measures from already existent. In our framework, as already said, derived measures should be defined in design time. Finally, notice that roll-up is not included in their set of operators, since it is considered in their model data structure. Finally, to conclude our survey, we would like to remark that some of these approaches have also presented an equivalent calculus besides the algebra introduced above (like [GL97] and [CT98b]). Moreover, [GMR98] presents a query language to define the expected workload for the data warehouse. We have not included the latter in Table 2.4 because it can not be smoothly compared to the algebraic operators. Anyway, analyzing it, we can deduce that many of our reference operators are also supported by their model like selection,projection,roll-up,union and even a partial drill-across, as they allow to overlap fact schemes. 2.2.4 Algebras Comparison This section presents a comparison between the multidimensional algebras surveyed in the previous section. To the best of our knowledge, it is the first comparison of multidimensional algebras 50 Union Algebra Operator Selection Projection Roll-up changeBase Drill-across Difference Remarks Drill-down Intersection “Add Dimension” Xp “Transfer” ∼ [LW96] “Cube Aggr.” X “Rc-join” X “Union” X “Push” XpSemantic Rels. “Pull” DXpSemantic [AGS97] Rels. “Destroy Dimension” DXp “Restriction” X “Join” X “Merge” X “Selection” X “Projection” X “Cartesian Product” ∼ [GL97] “Union/Diff./Inters.” X “Fold/Unfold” Xp “Classification” D “Summarization” D “Restriction” X “Metric Projection” X “Aggregation” X “Cartesian Product” ∼ [TD97] “Join” X “Union/Diff.” X “Extract” XpSemantic Rels. “Force” XpSemantic Rels. “Slicing” X “Roll-up/Drill-down” X [Leh98] “Split/Merge” ∼ “Implicit/Explicit Aggr.” Xp “Cell Operators” Derived Measures “Cartesian Product” ∼ “Natural Join” X “Roll-up” D “Aggregation” D [CT98b] “Level Description” XpSemantic Rels. “Scalar Function App.” Derived Measures “Selection” X “Simple Projection” X Xp “Abstraction” X+Xp+ “Restrict” X “Destroy” Xp [HS98] “join” X “Join” X+X+ “Aggr” X “Selection” X “Projection” X “Union/Diff.” X “Identity-based Join” ∼ “Aggregate Formation” Xp [Ped00] “Value-based Join” X “Duplicate Removal” Base definition “SQL-like Aggr.” Xp “Star-join” X+X+ “Roll-up/Drill-down” X “Navigate” X [Vas00] “Selection” X “Split Measure” X “Derived Measures” Derived Measures [FK04] “Join” Xp “Slice/Multislice” X “Union/Diff./Inters.” X “Selection Cube” X [YP04] “Decoration” Xp “Fed. Gen. Projection” X+X+X+ Table 2.4: Summary of the comparison between multidimensional algebras. 51 carried out. In [VS99], a survey describing the multidimensional algebras in the literature is presented. Regarding this previous work, in this study, we include up-to-date references and provide a detailed comparison of the algebras. Results presented along this section are summarized in Table 2.4. There, rows, representing an algebraic operator, are grouped according to which algebra they belong to (also ordered chronologically), whereas columns represent multidimensional algebraic operators in our framework (note that roll-up and drill-down are considered together since one is the inverse of the other). The notation used is the following: a Xcell means that those operations represent the same conceptual operator; a ∼stands for operations with similar purpose but different proceeding making them slightly different; a Xpmeans that the operation partially performs the same data manipulation as the reference algebra operator despite the latter also embraces other functionalities, and a X+means that this operation is equal to combine the marked operators of our reference algebra, meaning it is not an atomic operator. Analogously, there are some reference operators that can be mapped to another algebra combining more than one of its operators. This case is showed in the table with a D(from derived). Note that this last mark must be read vertically unlike the rest of marks. For example, in [AGS97], we can project data by means of the “pull” and “destroy dimension” operators. Finally, note that we have only considered those operations manipulating data and therefore, those aimed to manipulate the data structure are not include. A detailed analysis of Table 2.4 draws interesting conclusions. In short, we are able to identify the multidimensional backbone shared by all the algebras. Firstly, selection,roll-up and drill-down operators are considered in every algebra. It is quite reasonable since roll-up is the main multidimensional operator and selection is a basic one, allowing to select a subset of multidimensional points of interest out of the whole n-dimensional space. Projection,drill-across and set operations are included in most of the algebras. In fact, along the time, just two of the first algebras presented did not include projection and drill-across. We may include set operations in our algebra depending on the transformations that the model allows to perform over data and indeed, it is a personal decision to make. However, we do believe that to unite, intersect or difference two data cubes is a kind of navigation desirable. Finally, changeBase is also partially considered in most of the algebras. Specifically, they agree on the necessity of modifying the n-multidimensional space by adding / removing dimensions, and they include it as a first-class operator. Moreover, our framework provides additional alternatives to rearrange the multidimensional space (i.e., to change the multidimensional space base by “pivoting”). In general, we can always rearrange the multidimensional space in any way, if we preserve the functional dependencies of the cells with regard to the levels conforming the multidimensional space base; i.e., if the replaced dimension(s) and the new one(s) are related through a one-to-one relationship. Importantly, according to this study, all the algebras surveyed are subsumed by our reference framework. Finally, the algebra comparison presented in this section has revealed many implicit agreements about how multidimensional data should be handled. Although this is not the aim of this thesis, we strongly believe that a reference set of operators such as the multidimensional backbone identified in our study could be used to develop design methods oriented to improve querying, develop better and more accurate indexing techniques and facilitate query optimization (i.e., provide us with all the benefits of a reference framework). Experiences in the field of 52 databases have proved that a common framework to work with is crucial for the evolution of the area, and issues such as query optimization or better indexing techniques are even more critical than in an operational database, due to the huge amount of data stored in the data warehouse. 53 54 Chapter 3 Integrating Requirements in a Largely Automated Design Approach “ Research is the act of going up alleys to see if they are blind. ” Plutarch Data warehousing systems were designed to support decision-making within organizations. These systems homogenize and integrate data in a huge repository (i.e., the data warehouse) to create a single, detailed representation of the organization from which relevant knowledge can be extracted and applied in the organization’s decision-making processes. It is widely accepted that the conceptual schema of a data warehouse must be structured according to the multidimensional model. The multidimensional conceptual view of data is distinguished by the fact / dimension dichotomy and represents data as if placed in an n-dimensional space, which facilitates the interpretation and analysis of data in terms of facts (the subjects of analysis) and dimensions showing the different perspectives from which a subject can be analyzed. Since a data warehouse is the result of homogenizing and integrating relevant data in a single, detailed view, it is assumed that the multidimensional conceptual schema of the data warehouse must be derived from the organization’s data source schemas. Traditionally, this process has been performed manually, but automation is essential as it removes the dependency on an expert’s ability to properly apply the method chosen and the need to analyze the data sources, which is a tedious and time-consuming task (which can be unfeasible when working with large databases). In recent years, several approaches have been proposed for automating this process, most of which follow a data-driven model in which data sources are analyzed thoroughly to derive the data warehouse schema in a reengineering process that overlooks the end-user mul- 55 (like a supply-driven approach would do if the proper primary key - foreign key relationship were defined). Another example would be a denormalized database. In this case, if the query performs data grouping (i.e., it contains a GROUP BY clause) or contains comparison clauses in the WHERE clause, the attributes involved in these clauses are identified as dimensional data. In other words, the SQL queries may provide additional relevant knowledge to that captured in the sources. Nevertheless, we also harness the knowledge contained in the data sources (as in supply-driven approaches), such as foreign key and candidate key constraints, if present. In addition, (iii) MDBE works at the attribute level (SQL queries handle attributes), whereas other automatable methods work at the table level. Consequently, relational attributes can be labeled as dimensional or factual data and, in turn, relational tables are identified as dimensional data, factual data or tables containing factual data and dimensional data [KRTR98]. We can therefore identify the role played by each attribute in each relation and split it into different concepts in the resulting multidimensional schema. Thanks to these contributions, (iv) MDBE is able to handle denormalized relational schemas to some extent. The analysis of requirements at the attribute level allows MDBE to identify dimensional or factual attributes that previous approaches would overlook. However, regarding dimensional data identified from denormalized relations, MDBE cannot automatically generate the dimension hierarchies as the domain FDs needed to shape hierarchies are missing in the source schema. In other words, each requirement (i.e., SQL query) will identify attributes representing interesting analysis perspectives, but the relationships between these attributes (i.e., the dimension hierarchies) cannot be extracted from denormalized data sources. In these cases, the designer will be responsible for restructuring this kind of dimensional data. MDBE also provides the advantage of carrying out the demand-driven and supply-driven stages simultaneously in many aspects. This means that we are able to produce more and betterquality outputs than methods in which the two stages are performed sequentially. For example, (v) MDBE can derive implicit knowledge according to the input query and the data sources. Some attributes in the query may not play a relevant role in the output produced, in which case they could be overlooked. However, we analyze all of the potential alternatives, as well as metadata in the logical schema, and consider how these alternatives would affect the output schema, in some cases deriving interesting alternatives overlooked by the user. This contribution is important because it is often assumed in data warehouse modeling that the user may not recognize the analytical potential of all the data sources and, therefore, may overlook potentially useful analytical alternatives. However, analyzing all of the data sources can be expensive and produce too much noise in the final result [WS03]. We present an intermediate solution, in which concepts are analyzed to determine their analytical potential if they are implicitly related to concepts already stated in the end-user requirements (see step 6 in section 3.4.1 for further details). In addition, (vi) MDBE can derive new concepts that are not stated in the logical schemas. Since we handle requirements automatically, we can analyze them in depth and identify information such as concept specializations or newly derived measures (see Section 3.3.1.1 for further details). (vii) MDBE also keeps track of relevant metadata extracted from the requirements, which will be relevant in the implementation stage: specifically, interesting data granularity within a fact (see Step 2 in Section 3.4.1) and data summarizability properties (see Steps 1 and 3 in Section 3.4.1). 62 3.2 Validating SQL Queries as Cube-Queries As discussed in Chapter 2 there is no agreement on the multidimensional model integrity constraints nor in the set of multidimensional operators. However, if we aim to automate the data warehouse design task, we must guarantee that the conceptual schemas produced are aligned with the multidimensional model. Section 2.2 surveyed and compared current multidimensional algebras in the literature. By a detailed analysis of this comparison, we shown that there is an implicit agreement on how to manipulate multidimensional data. As presented in Section 2.2.4, this backbone is strictly subsumed by the reference algebra introduced in Section 2.2.1. This chapter introduction sketches the idea behind our approach. The end-user requirements must be expressed as SQL queries over the relational sources. Then, MDBE validates whether each input SQL query represents a valid multidimensional query (i.e., if the query retrieves data that can be analyzed from a multidimensional perspective) and eventually, derives multidimensional schemas from the relational sources that meet the multidimensional requirements. At this point, the question is immediate; how do we know if a SQL does really make multidimensional sense? [KRTR98] introduced the template query (also known as cube-query), to retrieve a Cell of data from the relational database management system (according to the SQL’92 standard): SELECT l1.ID, ..., ln.ID, [ F( ]c.Measure1[ ) ], ... FROM Cell c, Level1l1, ..., Levelnln WHERE c.key1=l1.ID AND ... AND c.keyn=ln.ID [ AND li.attr Op. K] [ GROUP BY l1.ID, ..., ln.ID ] [ ORDER BY l1.ID, ..., ln.ID ] The FROM clause contains the “Cell table” and the “level tables”. These tables are properly linked in the WHERE clause. Additionally, the WHERE clause can also contain logic clauses restricting an specific level attribute (i.e., a descriptor) to a constant Kby means of a comparison operator (i.e., equality, inequality, major, minor, etc.). The GROUP BY clause shows the identifiers of the levels used to aggregate data. Those columns in the grouping must also be selected in the SELECT clause in order to identify the result (i.e., we must select the multidimensional base to give rise to the multidimensional space). Finally, the ORDER BY clause sorts the output of the query by these identifiers. Note, however, that navigating and analyzing the data warehouse goes far beyond than just retrieving a Cell of data. In a navigation path, Cells may be combined and, in general, manipulated, by the multidimensional algebra. Thus, how this template would look like when capturing a whole navigation path? and importantly, will it always be correct? To answer these questions, we carried out the following studies: •Section 2.2.4 shows that our reference algebra subsumes all the multidimensional operators surveyed. From this starting point, we studied how each of the multidimensional operators in the reference framework should be translated into SQL (see Section 3.2.1). •Next, we analyze the potential problems we must deal with when combining two or more multidimensional operators in the same cube-query (see Section 3.2.2). 63 By the analysis of the results got in these two studies, we identify the constraints that a SQL query must guarantee to be aligned with the multidimensional model and make multidimensional sense. 3.2.1 Translating the Multidimensional Operators into SQL Queries MDBE requires to express the end-user requirements as SQL queries over the relational sources. Thus, in our study, we need to analyze how the multidimensional algebra must be translated into SQL. Importantly, note that this translation is also implicitly performed by ROLAP tools (see Section 1.3.1 for further details about ROLAP tools). As discussed in Section 1.2.1, OLAP users are able to navigate (i.e., query and analyze) data in real-time. The user provides a navigation path in which each node (resulting in a data cube) is derived from the previous node in the path (and thus we say that the user navigates the data). Each node is transformed into the next one in the path by applying specific multidimensional operators. In a relational implementation of the OLAP tool (i.e., in a ROLAP tool), the navigation path is eventually translated (in a transparent way to the user) into SQL. Interestingly, to know if a SQL query makes multidimensional sense we need to analyze how a ROLAP tool translates the multidimensional operators into SQL and identify which constraints must satisfy a SQL query to be a cube-query (i.e., to make multidimensional sense). In this section, we first analyze how each multidimensional operator in our reference multidimensional algebra (see Section 2.2.1) is expressed as a cube-query. First, for the sake of understandability, we present a practical scenario to be used as example in this section. Consider a snowflake implementation of the conceptual schema depicted in Figure 1.2 (see page 9). The cube-query that would retrieve the sales Cell depicted in the figure is: SELECT d.day, p.id, c.name, s.price, s.discount FROM sales s, day d, product p, city c WHERE s.product id = p.id AND s.day = d.day AND s.city name = c.name Note that no grouping is needed as we are just retrieving an atomic Cell. Accordingly, we use atomic cube-query to denote a cube-query retrieving a materialized Cell from the relational database management system. Next, we show how this cube-query would be modified by each multidimensional operator2(a summarization of the results obtained is shown in Table 3.1): •Selection: In SQL, it means to and the corresponding comparison clause to the WHERE clause. For example, consider the atomic cube-query presented as example. If we want to analyze the sales data regarding to the city of Barcelona, we must perform a selection over the city dimension (see Figure 3.4). •Roll-up: In SQL, it entails to replace the identifiers of the level from where we roll-up with those of the level that we roll-up to. Thus, the SELECT, GROUP BY and ORDER BY clauses must be modified accordingly. Measures in the SELECT clause must also 2For a detailed discussion on this issue, we address the reader to [ASS03]. 64 Clause Selection Roll-up ChangeBase Drill-across Projection Union SELECT Replace Replace Add Remove (LevelID) (LevelID) (Measure) (Measure) FROM Add Add Union (Levels) (Cell) (Cells and Levels) WHERE AND Add Add Union OR (conditions) (links) (links) (links) (conditions) GROUP BY Replace Replace (LevelID) (LevelID) ORDER BY Replace Replace (LevelID) (LevelID) Table 3.1: Summary of the modifications brought in a cube-query by each multidimensional operator be summarized using an aggregation function. In our example (see Figure 3.4), we perform two different roll-ups: on the one hand, we roll-up from product id to the All level. On the other hand, we roll-up from city to country. Note that the country table is added to the FROM clause, and we replace the city identifier with that of the countrylevel in the SELECT, GROUP BY and ORDER BY clauses. Finally, we add the proper links in the WHERE clause. About rolling-up from product to the All level, note that it is equivalent to remove both the product identifiers and its links. •ChangeBase: In SQL it can be performed in two different ways. If we reorder the base (i.e., when “pivoting”), we just need to reorder the identifiers in the ORDER BY and SELECT clauses. But if changing the base, we need to add the new level tables to the FROM and the corresponding links to the WHERE clause. Moreover, identifiers in the SELECT, ORDER BY and GROUP BY clauses must be replaced appropriately. Following with the same example shown in Figure 3.4, we can change from {day ×country ×All} to {day ×country}. Note that both bases are conceptually related by means of a one- to-one relationship. Specifically, this case typically applies when dropping a dimension (i.e., rolling-up to its All level and then changing the base). We roll-up to the All for representing the whole dimensions instances as a single one and therefore, producing the following base: {day ×country ×1}. Now, we can changeBase to {day ×country} without introducing aggregation problems (since we changeBase through a one-to-one relationship). •Drill-across: In SQL, we must add a new Cell table to the FROM clause, its measures to the SELECT, and the corresponding links to the WHERE clause. In general, if we are not using any semantic relationship, a new Cell table can always be added to the FROM clause if both Cells share the same base. In our example, suppose that we have a stock Cell sharing the same dimensions as the sales Cell. Then, we could drill-across to the stock Cell and show both the stock and sales measures (see Figure 3.4). •Projection: In SQL it entails to remove measures from the SELECT clause. Following our example, we can remove the discount measure by projecting the stock and price measures. 65 Figure 3.4: Exemplification of an OLAP navigation path translation into SQL queries •Union: In SQL, we unite the FROM and WHERE clauses of both SQL queries and finally, we or the selection conditions in the WHERE clauses. Importantly, note that we can only union queries over the same Cell table. Intuitively, it means that, in the multidimensional model, the union is used to undo selections. We can unite our example query to one identical but querying for data concerning Lleida instead of Barcelona. As previously stated in section 2.2.1, these considerations can be easily extended to difference and intersection. 3.2.2 Potential Translation Conflicts As discussed in previous section, OLAP users navigate the multidimensional data by providing a navigation path in which each node (resulting in a data cube) is derived from the previous node in the path by means of the multidimensional operators. For example, consider Figure 3.4, where a whole navigation path is depicted. At a given point, a node may combine a finite set of multidimensional operators. For instance, in the fifth node, this cube-query combines a selection, a changeBase, a drill-across, a projection and two roll-ups. The mapping to SQL of a single multidimensional operation does not represent a problem, but when combining the modifications brought about by a set of operations in a single SQL query, some conflicts could appear. Therefore, if these problems are not detected and treated appropriately, the automatic translation can retrieve unexpected results. In this section, we define and classify conflicts raised when automatically translating a navigation path to SQL. Suppose an arbitrary navigation path. The user chooses a source data cube from where starting to operate and automatically, the ROLAP tool will conform a cube-query to retrieve the demanded data cube. Note that this data cube is our starting point so that it has not been yet manipulated by any operation. Consequently, it is placing a Cell of data on the n-dimensional space formed by its analysis dimensions. In a relational implementation, this Cell could have 66 been materialized. If it was, the ROLAP tool will retrieve the materialized data. Otherwise, it will look for an appropriate Cell, in a lower aggregation level, from where to obtain the needed Cell by means of roll-ups. For example, according to Figure 1.2 (see page 9), we could start our analysis from the materialized Cell (i.e., the daily sales per product and city) or from a non-materialized one; e.g., annual sales per product and city. As the latter is not materialized, we need to perform an implicit roll-up over the atomic Cell, from month to year, to get the needed data. As presented in Table 3.2, certain operations may pop up a conflict when combined with an specific source cube-query. We denote source cube-query to an atomic cube-query modified by a sequence (note that we talk about sequence, because, in the multidimensional model, order matters) of operations. If no operation has been performed over the atomic cube-query we consider the empty sequence (∅). Hence, a cell is crossed (×) when the sequence of operations in the source cube-query contains a specific operation that may cause a conflict with the next one to be performed. For example, it may happen if our source cube-query includes a selection and next operation to be carried out is a roll-up. Note that all the conflicts shown in Table 3.2 are caused by data aggregation anomalies. As introduced in [LS97], operations performed must satisfy the disjointness, completeness and compatibility of the summarization (i.e., the compatibility of the dimension, the aggregation function and the kind of measure involved in the summarization) to guarantee its correct summarization. Otherwise, two operations that, as a whole, do not preserve the three conditions will raise up a conflict. Therefore, as presented in Section 3.2.1, roll-up is the only operator performing data aggregation and consequently, it is the only one that may directly raise up conflicts when combined with other operators in the same cube-query. Importantly, roll-up is the most relevant multidimensional operator, as it allows to modify the data granularity. Specifically, according to Table 3.2, all conflicts are related to roll-up and drill-across. The rest of operations except for selection, propagate conflicts if already present in the cube-query, but do not introduce new ones. Consequently, projection,union and changeBase never raise a conflict. Intuitively, projection removes measures from the SELECT clause and dropping a measure just means to discard one column of the Cell table; union ores conditions of two data cubes with the same n-dimensional space not removing / adding any point; and changeBase always asks for a one-to-one relationship, avoiding conflicts due to its own nature. Operation/Source ∅Selection Roll-up Projection Drill-across ChangeBase Union Selection Roll-up X X X X Projection Drill-across X X X ChangeBase Union Table 3.2: Summary of cube-query conflicts Oppositely, drill-across and selection may introduce conflicts in the translation to SQL of the navigation path. Drill-across asks for a one-to-one relationship but sometimes, a one-to-many 67 relationship is enough. In these cases, due to not materialized Cells, we need to perform implicit roll-ups to get the necessary one-to-one relationship and consequently, potentially raising up the same conflicts caused by a roll-up. Similarly, it may happen with non-materialized atomic cube-queries that would need to perform implicit roll-ups. A selection may cause an specific conflict along with a roll-up if we select a subset of points of the data cube and later roll-up, which would prevent the ROLAP tool of using the pre-aggregated data (as done in the general case). Consequently, note that it is enough to analyze the potential conflicts between each pair of operators, since all of them are caused by conciliating multiple aggregations of data in just one cube-query and therefore, the order performed between the operators, at the cube-query level, does not matter. Since all conflicts are due to data aggregation anomalies, we have classified them in three groups according to the three necessary conditions needed to guarantee a correct data summarizability: those performing multiple aggregation functions in a query (not preserving compatibility of data), those raising hidden many-to-many relationships (not preserving disjointness) and finally, those related to the selection granularity (not preserving completeness). 3.2.2.1 The Multiple Aggregation Problem The first conflict is related to the functions used to aggregate data when combining more than two roll-ups in the same cube-query. To analyze this problem, we consider two scenarios: (i) if the roll-ups are performed over the same dimension or (ii) over different ones. In the first case, we can always solve the problem disregarding the first roll-up and just performing the second one. This assumption holds because, in a given time, multidimensional data can only be showed at a certain aggregation level for each dimension. Thus, in the worst scenario, we can solve this conflict by rolling-up from the atomic level. Oppositely, when performed over different dimensions, we must aggregate data for each of the dimensions. SQL does not allow to aggregate data by means of two different functions in the same query, and this conflict can not be solved in a single cube-query. For example, in the first case, if we roll-up the sales Cell showed in Figure 1.2 (see page 9) from day to month, and later we roll-up from month to year, the whole sequence of roll-ups can be directly expressed as: SELECT y.year, p.id, c.name, SUM(s.price), AVG(s.discount) FROM sales s, product p, city c, day d, month m, year y WHERE s.product id = p.id AND s.day = d.day AND s.city name = c.name AND d.month id = m.month AND m.year id = y.year GROUP BY y.year, p.id, c.name ORDER BY y.year, p.id, c.name On the contrary, if we first roll-up from day to month, and later from city to country, nested queries are compulsory: 68 SELECT p.id, co.name, m.month, AVG(s.price), AVG(s.discount) FROM (SELECT p.id, c.name, m.month, AVG(s.price), AVG(s.discount) FROM sales s, product p, city c, day d, month m WHERE s.product id = p.id AND s.day = d.day AND s.city name = c.name AND d.month id = m.month GROUP BY p.id, c.name, m.month ORDER BY p.id, c.name, m.month), country co WHERE s.product id = p.id AND s.day = d.day AND AND s.city name = c.name AND c.country name = co.name GROUP BY p.id, co.name, m.month ORDER BY p.id, co.name, m.month) Even if SQL allowed to perform more than one aggregation function in the same query, we would face another problem: the order between the aggregation functions. For example, note that, in the above query, the price measure is aggregated by means of the average function over the time dimension, and by means of the sum function over the place dimension. Thus, it is important to realize that our own multidimensional conceptual design fixes the order of the aggregation functions when exploring the Cell hierarchy. Thus, order does really matter since sum of averages is different from an average of sums. The above conflict could be avoided if SQL allowed to perform more than one aggregation function per query, and set up an order between them. For example, as showed below, an SQL extension stating explicitly two GROUP BY’s (very similar to SQL’99 GROUPING SETS modus operandi), would avoid using nested queries when combining more than one conflictive roll-up. First GROUP BY would be related to the first aggregation function and analogously to second one: SELECT p.id, co.name, m.month, SUM(s.price), AVG(s.discount) FFROM sales s, product p, city c, day d, month m, country co WHERE s.product id = p.id AND s.day = d.day AND AND s.city name = c.name AND d.month id = m.month AND c.country name = co.name GROUP BY p.id, c.name, m.month GROUP BY p.id, co.name, m.month ORDER BY p.id, co.name, m.month Although this problem has been presented as a roll-up plus roll-up problem, it goes far beyond, as it may happen when obtaining non materialized Cells from materialized ones. For example, if we start our navigation path from the monthly sales per city Cell that has not been materialized, ROLAP tools will need to perform a roll-up from day to month to obtain the needed data. So that, we have already performed an implicit roll-up that could arise conflicts if we next perform an explicit one from city to country. Similarly, as presented in Section 3.2.2.2, implicit roll-ups may also occur when performing a drill-across from a non materialized Cell (indeed, implicit roll-ups can also appear when changingBase, but in this case, the implicit and explicit roll-ups are performed over the same dimension -see the (i) case above- and thus, avoiding conflicts). 3.2.2.2 The Fan-Shaped Problem In this section we introduce a family of problems that occur when disjointness of data aggregation is not preserved. It typically appears related to drill-across, either through semantic rela- 69 tionships or shared dimensions. Drill-across asks for a one-to-one relationship, but sometimes a one-to-many relationship is enough. For example, consider Figure 3.4. There, we have shown how to drill-across from the daily sales per country to the daily stock per country. Clearly, these two Cells are related by means of a one-to-one relationship. However, if they are not materialized, they give rise to a hidden many-to-many relationship. Note that, prior to performing this drill-across, we have dropped the product dimension and this is why this query that, at first sight seems correct, gives rise to a many-to-many relationship. As enounced in [LS97], the aggregation of data must be disjoint, and in this case, it is not. In fact, what should be a one-to-one relationship turns into a many-to-many one calling up a fan-shaped matching. Thus, we should use a nested query performing first one roll-up and later, the other one, being the “join” last performed. This problem could be solved if SQL allowed to state a priority between “joins” and GROUP BY’s. Finally, also note that when carrying out a drill-across to a non materialized Cell, a ROLAP tool will need to perform internal roll-ups to obtain the appropriate aggregation level from where drill-across. Internal roll-ups followed by an explicit roll-up may cause the conflict stated in Section 3.2.2.1. 3.2.2.3 The Selection Granularity Problem This problem is closely tied to selection and raises when completeness is not guaranteed. Selection allows to reduce the current multidimensional space by means of a logic clause over a certain descriptor. For example, selecting those cells of monthly sales per city related to Barcelona. Now, if we decide to materialize this Cell in the data warehouse, we cannot take advantage of it in those navigation paths not considering this selection. In the general case, ROLAP tools use materialized Cells to speed up the query processing, but note that a navigation path not preserving the Cell data granularity would not benefit from it, as data completeness is not guaranteed. For example, if we roll-up from daily sales per city to monthly sales per city we cannot take advantage of the monthly sales in Barcelona to answer this query. Simply, we do not dispose of data for the rest of cities in this materialized Cell (i.e., completeness is not preserved). In this case, using the appropriate data granularity (in the worst case, the atomic Cell) and performing internal roll-ups is mandatory. In short, this conflict invalidates pre-aggregated data (i.e., materialized Cells) not containing the same (or a finer) data granularity level with regard to the current navigation path. 3.2.3 Discussion: The Multidimensional Integrity Constraints In this section we have analyzed how the multidimensional algebra must be translated into SQL. As result, we have been able to identify the constraints a SQL query must satisfy to make multidimensional sense: it must follow the cube-query pattern (i.e., it must retrieve a data cube) and it must be free of summarizability problems. Formally, we say that a SQL query is a correct cube-query if it retrieves data that can be analyzed from a multidimensional perspective. I.e.,: •Factual data is arranged in a multidimensional space (i.e., it forms a data cube). Thus, each 70 instance of factual data is identified (i.e., placed in the multidimensional space) by a point in each of its analysis dimensions. –As consequence, we must be able to identify a minimal set of levels identifying the cells placed in the multidimensional space. According to our terminology, we denote by base to this minimal set of levels determining the factual data. •Data summarization must be correct, which is ensured by guaranteeing three necessary conditions (which, intuitively, are also sufficient) [LS97]: (1) Disjointness (the sets of objects to be aggregated must be disjoint); (2) Completeness (the union of subsets must constitute the entire set); and (3) Compatibility of the dimension, the type of measure being aggregated and the aggregation function. 3.3 Problem Context The main aim of our approach is to support the data warehouse design process. It consists of two steps: requirement formalization and the MDBE method (as shown in Figure 3.1). Furthermore, as in any classical design process, a requirement elicitation pre-process is needed. Although this pre-process falls outside the scope of this work, some relevant features should be noted here. Data warehousing systems differ in various aspects from conventional operational systems (since they are designed to support decision-making) and need specialized requirement elicitation processes [MTL07, WS03]. However, this issue has been studied in depth, and there are several methods that can be used in preliminary step (for example, [GRG05, MTL07, PSG04, SLB02, WS03]). Nevertheless, note that we gather information requirements in this step. Information requirements [WS03] are designed to meet end-user information necessities, which is the objective of a data warehouse [MTL07]. Unlike in other systems, end-users can easily determine their information necessities because they consist of business queries posed in their daily decision-making processes. Consequently, information requirements can be stated in the end-users’ own words and closely reflect their reality. For example, ”examine stocks provided by suppliers” or ”analyze customer purchases with regard to region, product and time” would be typical information requirements. The next step in our approach formalizes the requirements gathered. As discussed previously, we aim to automate the manipulation of requirements (i.e., integrate them in a fully-automated method), so they must be translated into a computer understandable language. In our approach, end-user requirements are expressed as SQL queries over the relational data sources (i.e., at the logical level over the data sources). This step must be carried out by a database expert capable of lower the level of abstraction of the input requirements to the logical level (see Section 3.1.1 for a detailed discussion of the advantages and disadvantages of this step). As shown in Figure 3.1, the next step in our approach is to apply the MDBE method, which has two inputs: the end-user information requirements (expressed as SQL queries) and the logical model of the data sources. As output, MDBE presents a multidimensional schema derived from the data sources, which allows the user to retrieve data demanded in the input requirements. In this step, MDBE determines whether each input SQL query represents a valid multidimensional query, i.e., if the query retrieves data that can be analyzed from a multidimensional perspective; 71 Figure 3.5: MDBE: decision diagram for labeling nodes representing factual data the multidimensional space in which to place the data. There are three possible cases: the Cell directly contains (i) the multidimensional base, (ii) a candidate base (i.e., a set of attributes preserving a one-to-one relationship with the multidimensional base) or (iii) a set of attributes fully determining the multidimensional base. To preserve [C3], in the (i) and (ii) cases, it means that either the multidimensional base (candidate base) corresponds to a table CK (also represented in the node) or, if performing data aggregation in the query, the GROUP BY clause is compound of attributes of the node. For the (iii) case, consider the TPC-H business query #5 previously introduced, and the TPC-H relational schema shown in Figure 3.2. In this query, the name attribute (from the nation node) forms the multidimensional base and lineitem plays a Cell role. To preserve [C3], lineitem is properly linked to name in such a way that every instance of factual data is related to just one nation name value. In other words, lineitem functionally determines the nation of the supplier (indeed, this dependency is properly captured in the relational schema by means of FKs). We use link attributes to denote the dimensional concepts contained in a Cell placing factual data in the multidimensional space (i.e., the (i), (ii) or (iii) cases discussed). –Cell (C): These nodes represent ”factless facts” [KRTR98]. This definition is equivalent to the previous one, but this type of Cell does not contain measures. These facts are very useful for describing events and coverage and can be used to formulate many interesting questions [KRTR98]. To determine the factual label of a node, we follow the decision diagram shown in Figure 3.5, which generates questions about the query and the table metadata. These questions derive directly from constraints introduced in Section 3.3.1, and we distinguish between two possible scenarios: one in which the current input query performs data grouping (i.e., it contains a GROUP BY clause) and another in which it does not. In the first case, and according to [C1], if the SELECT clause contains an aggregated attribute (i.e., summarized by an aggregation function), that attribute will play a measure role. Consequently, the node is labeled as CM. Otherwise, if no aggregated attribute is selected, it is labeled as a factless fact C(i.e., the Cell does not contain measures). Similarly, if no data grouping is performed in the query but we are able to produce a multidimensional space (i.e., a table CK is selected), the node will be labeled as a Cell:CM if attributes 78 other than the key are selected (i.e., if it contains measures); otherwise, C. According to [C6], any other alternative would not make multidimensional sense as a Cell (depicted in the figure by the Xmark). When checking if any measure other than a table key is selected, we do not only consider numerical attributes. Traditionally, numerical attributes produce measures because they are perfectly additive but, as discussed in [KRTR98], semi-additive or non-additive values could be of interest to the end-user. Moreover, there are some areas in which non-numerical values are additive. For example, the spatial databases area contains algorithms for the aggregation of text values representing geographical information (see [CMTV00]). Note the multidimensional semantics involving each alternative in the decision diagram discussed above. Cells identified without grouping will represent ”atomic factual data” [ASS06] (i.e., the finest granularity of data in the data warehouse), whereas those Cells identified by data aggregation will represent ”aggregated factual data” (i.e., coarser data granularities of interest). Similarly, to determine the dimensional role of a node we follow the decision diagram shown in Figure 3.6. Again, it generates questions about the query and the table metadata. First, we check if the input query performs data grouping, and according to [C3], attributes in the GROUP BY (i.e., contains attributes being part of the multidimensional base) will play a level role. Consequently, the nodes containing these attributes are labeled as L. If no data grouping is performed or none of the node attributes are used to group data, we check the WHERE clause. We distinguish between two possible scenarios: if any of the node attributes are involved in a comparison clause or in a join. In the first case, according to [C7], selections are performed over dimensional data and thus, that attribute will be identified as dimensional data. In the second case, according to [C1], joins in the WHERE clause represent conceptual associations. Thus, if a node contains an attribute joined to a dimensional attribute (i.e., an attribute already identified as dimensional data) then, both attributes represent dimensional data. Any other scenario would not make sense as dimensional data and the node is not labeled (see the the Xmark in the figure). Supporting Denormalization: As discussed in Section 3.1, our method can handle denormalized input schemas, which means that a given node may play a factual and dimensional role simultaneously. This scenario occurs when a graph node is labeled as factual data by the decision diagram shown in Figure 3.5, and as dimensional data by the decision diagram shown in Figure 3.6: MDBE: decision diagram for labeling nodes representing dimensional data 79 Figure 3.7: MDBE: state diagram showing the transition between node labels Figure 3.6. In this case, we introduce two new labels to identify hybrid nodes containing factual and dimensional data. Note, however, that a factual node (i.e., those labeled as CM or C) always contains dimensional data forming the multidimensional space (i.e., the link attributes). However, hybrid nodes contain additional dimensional data: either attributes playing a degenerated dimension [KRTR98] role and / or attributes playing the role of denormalized dimensional data (i.e., partial or whole denormalized dimension hierarchies): •Cell With Measures and Additional Dimensional Data (CDM): This label is equivalent to the CM label (this node therefore contains the link attributes as well as measures) with additional dimensional data. The additional dimensional data represent other analytical levels and descriptors that form other analytical perspectives. •Cell with Additional Dimensional Data (CD): Similarly, nodes representing factless facts with additional dimensional data are labeled as CD. For example, consider the TPC-H business query Q5 previously introduced. If this query contained an additional comparison clause such as l shipdate = ’12-02-2009’ in the WHERE clause, MDBE would identify lineitem as a hybrid node: according to the decision diagram shown in Figure 3.5, lineitem is labeled as CM (because the query contains grouping and lineitem contains two aggregated attributes -i.e., l extendedprice and l discountin the SELECT clause) and, according to the decision diagram shown in Figure 3.6, it will also identify lineitem as dimensional data (because lineitem does not contain any attribute in the GROUP BY clause, but it contains l shipdate, which is involved in a comparison clause in the WHERE). As result, MDBE labels this node as a hybrid node (CDM) since it contains measures, the link attributes and also an additional dimensional attribute. Once we know how to label attributes (by means of the 7 criteria introduced in section 3.3.1) and nodes (by means of the decision diagrams previously introduced in this section), the node labeling state diagram can be produced, as shown in Figure 3.7. The transitions between possible labels are shown. Every node is unlabeled in its initial state (i.e., at the beginning of the labeling 80 CKn1CKn2F Kn1F Kn2NNn1NNn2Relationship Multiplicity × × × × ? ? Attr. →Attr. N −M X× × X X X CK →F K +NN 1 -o N X× × ?X?CK →Attr. 1 o-o N ×X X ×X X F K +NN →CK N o- 1 ×X?×?XAttr. →CK N o-o 1 X X X X X X CK +F K →F K +CK 1−1 X X X ×X X CK +F K →CK 1 o- 1 X X ×X X X CK →CK +F K 1 -o 1 X X × × X X CK →CK 1 o-o 1 Table 3.3: Summary of rules used to infer the relationship multiplicities from relational sources process) and the label is then updated according to the explicit knowledge extracted from the query. For example, from the initial state, we can label each node as either CM (if one of its attributes is identified as a measure) or L(if one of its attributes is identified as a dimensional concept). From the CM state, we can keep the same label if any other measure is identified or update it to CDM if an attribute playing a dimensional role and not part of the link attributes is identified (i.e., if this node contains factual and dimensional data). Some transitions shown in the state diagram are labeled with the NKD (New Knowledge Discovery) tag. In MDBE, a state transition can take place due to either the explicit knowledge extracted from the query or the implicit knowledge derived both from the input query and the data source metadata. The latter case represents a scenario in which either the query does not explicitly establish a node role (thus, the node is not yet labeled) or the implicit knowledge available suggests an alternative labeling. In these cases we analyze every labeling alternative for the node in question. As discussed in Section 3.1 and presented in detail in Section 3.4.1 (see Step 6), this process is used to derive new multidimensional knowledge that is not stated in the requirements. 3.3.2.3 Edge Labeling Edges relate nodes and keep track of joins in the WHERE clause of the query. They provide information about how relational concepts are related in the relational schema fragment captured in the query. For our purpose, a given edge is labeled according to the multidimensional conceptual relationship it may represent (i.e., the multidimensional interpretation we may infer). We consider four potential labels: Cell - Cell, Cell - Level, Level - Cell and Level - Level. For example, a Cell - Level edge label would mean that the relationship could relate factual data (i.e., a node playing a Cell role) to dimensional data (i.e., a level). Note that edge labels only depict the conceptual role that each node may play relative to a given edge. Therefore, these labels show how factual and dimensional data may be related but, as previously discussed, MDBE has different labels to identify factual and dimensional nodes. Specifically, a node playing a factual role may be labeled as CM,C,CDM or CD whereas a node playing a dimensional role can only be labeled as L. In other words, regarding edges, hybrid nodes can only play a Cell role, as justified later in this section. 81 Next, we introduce the edge labeling process: •First, for each join between tables in the WHERE clause, we first infer the relationship multiplicity with regard to the schema constraints of the join attributes (i.e., FKs, CKs or not NULL values). In the relational model, the multiplicity of a relationship depends on how attributes involved are defined in the schema: Whether they (as a whole, since we consider multi-attribute joins) play the role of a relation CK and / or if they are defined as a FK to the other attribute(s) and / or if they allow NULL values. Joining to a CK guarantees to match at most one instance of the relation3. Otherwise it may match many of them. Similarly, an attribute not allowing NULL values and being defined as FK will surely match one and just one instance. Otherwise, it may introduce zeros. Table 3.3 summarizes all those relationship multiplicities that we may find in the relational model with regard to the attributes metadata. There, each row represents an specific relationship between nodes (i.e., a kind of join). Notation used is the following: first six columns represent all possible combinations with regard to the constraints of join attributes (the subscripts n1 and n2 refer to each one of the attribute sets joined): As CK, as a FK pointing to the other attribute(s) or as NN (not NULL) attribute(s). If an specific cell is ticked (i.e., X), it means that that attribute is constrained according to that column. Otherwise, it is marked with a ×mark. Notice that not all the combinations are allowed and some columns determine the following ones. For instance, CK attribute(s) can not accept NULL values. Moreover, a cell is marked with a ?mark if previous columns already determine a certain multiplicity, meaning that this constraint does not affect the obtained multiplicity. Finally, last two columns inform about the specific join depicted as well as the multiplicity inferred. There, an Attr. represents unconstrained attribute(s); that is, not defined neither CK nor FK and allowing NULL values. •Next, according to the semantics of the multiplicity inferred, we label each edge with those multidimensional relationships it could represent (i.e., the multidimensional concepts it could relate). Potential edge labels are shown in Table 3.4, and those combinations making 3We assume, as all systems do, that a FK can only point to a CK set of attributes. Multiplicity Level -Level Cell -Cell Level -Cell Cell -Level 1 - 1 X X X X 1 o- 1 X X XcX 1 o-o 1 X X XcXc N- 1 X X ×X No- 1 X X ×X No-o 1 X X ×Xc N-o 1 X X ×Xc N-M×Xd× × N-o M×Xdc × × No- M×Xdc × × No-o M×Xdc × × Table 3.4: Valid multidimensional relationships in a relational schema 82 multidimensional sense (according to [C2], [C5] and [C6]) are marked with a X. For example, a many-to-one relationship, depending on zeros, could represent a Cell - Level, Cell - Cell or a Level - Level relationship but not a Level - Cell relationship, since it would not satisfy [C2]. However, completeness could eventually be relaxed to identify concept specializations, as explained in Section 3.3.1.1. These cases, in which completeness would be relaxed a posteriori, are shown in Table 3.4 as Xc. It can also be seen that many-to-many relationships would not generally produce valid labeling. According to the constraints presented in Section 3.3.1, a many-to-many relationship is meaningless in the multidimensional model. Nevertheless, there is one case in which we may consider many-to-many relationships, since we could eventually relax disjointness to identify derived measures, as explained in Section 3.3.1.1; this exception, in which disjointness would be relaxed a posteriori, is shown in Table 3.4 as Xd. Finally, and as previously stated, we would like to remark that a node required to play a dimensional role by an edge label, can only be labeled as Land not as CDM or CD. Although these two labels represent hybrid nodes (and thus, they also contain dimensional data), their semantics are different from those of the Llabel. Importantly, edges relate nodes, and they determine the role that the related nodes may play according to the join conditions. Consider again Table 3.4. A node may play a level role whether: (i) it is placed in the to-one end of a relationship (see second, fourth and fifth column) or (ii) it is placed in the to-many end of a Level - Level one-to-many relationship (see second column). By definition, the cardinality of factual data within a hybrid node is greater than (or in a degenerate case, equal to) that of the dimensional data it contains. Thus, in the (i) case, when an edge relates a node nto a hybrid node hby means of a to-one relationship, the link relates nto the factual data in h. Otherwise, if the link were relating nto the dimensional data in h, it would not raise the to-one multiplicity. For this reason, hybrid labels cannot be used in this case. In the (ii) case the reason is subtler. According to Table 3.4, the node in the to-many end may represent a level (see second column) or a Cell (see third and fifth column). However, labeling it as a hybrid node entails that this node contains factual and dimensional data and, by the same reasoning as in the previous case, we are relating the factual data in h(i.e., the hybrid node) to the data in n(i.e., its counterpart node) by means of a many-to-one relationship. For this reason, the semantics of this edge would capture a Cell - Level or a Cell - Cell relationship (depending on the role of n), but never a Level - Level relationship. Indeed, a Level - Level relationship can only be obtained by considering hto play a strict dimensional role (i.e., labeling it as L). Summing up, from the perspective of the edge labeling process and concerning hybrid nodes, factual data is of more relevance than dimensional data. Note that this is sound with the hybrid node definition: they contain factual data (and thus, like any other Cell, the link attributes) and additional dimensional data (that in the general case will introduce redundancy). 3.4 MDBE: Multidimensional Design Based on Examples The MDBE method has two inputs: the end-user information requirements (expressed as SQL queries) and the logical model of the data sources. As output, our method produces a constel- 83 Figure 3.8: Summary of the MDBE process lation schema from the data sources, which allows the user to retrieve the data requested in the input requirements. In this scenario, each query is analyzed to derive a multidimensional schema that meets the information requirements. This automatic process is depicted in Figure 3.8 and can be divided into four different stages: •For each input query, the first stage (see Section 3.4.1) extracts the multidimensional knowledge contained in the query (i.e., the multidimensional role played by each concept in the query and the conceptual relationships between concepts), which is properly stored in the multidimensional graph. For this purpose, we apply the labeling methods discussed in Section 3.3.2. In this stage, the role played by the data sources will be crucial in inferring the conceptual relationships between concepts. •The second stage (see Section 3.4.2) validates the multidimensional graph created in the first stage according to the constraints introduced in Section 3.3.1. The aim is to check whether the concepts and relationships stated in the graph collectively produce a data cube. From the graph building perspective, the first stage of the MDBE method is designed to derive a multidimensional labeling (i.e., label attributes, nodes and edges) to be validated in the second stage (i.e., checking the overall soundness of the graph). Therefore, this stage determines whether we would be able to use a set of multidimensional operators to retrieve data requested in the input query from the multidimensional schema represented by the multidimensional graph. If the validation process fails our method ends, since the required data cannot be analyzed from a multidimensional perspective (i.e., we are not be able to retrieve the requested data simply by using multidimensional operators). Otherwise, the resulting multidimensional schema is directly derived from the multidimensional graph. •The third stage (see Section 3.4.3) finds the most representative results among those obtained. The step in which new multidimensional concepts are discovered may introduce new results (i.e., labelings) of potential interest, and we introduce a rule for determining which results should be presented to the user. •Finally, the fourth stage (see Section 3.4.4) conciliates the multidimensional schemas obtained for each query. The result is a minimal constellation schema subsuming each of the schemas obtained for the input queries. 84 Importantly, MDBE establishes a framework that can be used incrementally: by launching queries we can see the impact on the final conceptual schema. This feature facilitates the maintenance of the multidimensional conceptual schema. 3.4.1 First Stage: Concept Labeling The first stage is designed to build the multidimensional graph in 6 steps by applying the labeling standards introduced in Section 3.3.2. In this section, we introduce a detailed algorithm in pseudo-code (the MDBE algorithm) for implementing the first MDBE stage. This algorithm is followed by a brief explanation and an example of the execution of each step (based on the TPC-H schema). For the purposes of the study, the comprehensibility of the pseudo-code took priority over its performance (nevertheless, some optimizations have already been applied for its implementation in the MDBE tool): declare MDBE ALGORITHM as 1. For each table in the FROM clause do (a) Create a node and Initialize node properties; 2. For each attribute in the GROUP BY clause do (a) Label attribute as Level; (b) node =get node(attribute); Label node as Level; (c) For each attr2 in follow conceptual relationships(attribute, WHERE clause) do i. Label attr2 as Level; ii. node =get node(attr2); Label node as Level; 3. For each attribute in the SELECT clause not in the GROUP BY clause do (a) Label attribute as Measure; (b) node =get node(attribute); Label node as Cell with Measures selected; 4. For each comparison in the WHERE clause do (a) attribute = extract attribute(comparison); (b) if !(attribute labeled as Level)then i. Label attribute as Descriptor; ii. node =get node(attribute); Label node as Level; (c) For each attr2 in follow conceptual relationships(attribute, WHERE clause) do i. if !(attribute labeled as Level)then A. Label attribute as Descriptor; B. node =get node(attribute); Label node as Level; 5. For each join in the WHERE clause do (a) /* Notice a conceptual relationship between tables may be modeled by several equality clauses in the WHERE */ (b) set of joins =look for related joins(join); (c) multiplicity =get multiplicity(set of joins); relationships fitting ={}; (d) For each relationship in get allowed relationships(multiplicity)do i. if !(contradiction with graph(relationship)) then 85 A. relationships fitting =relationships fitting + {relationship}; (e) if !(sizeof(relationshipsfitting)) then return notify fail(”Node relationship not allowed”); (f) Create an edge(get join attributes(set of joins)); Label edge to relationships fitting; (g) if (unequivocal knowledge inferred(relationships fitting))then propagate knowledge; 6. for each gin New Knowledge Discovery(graph) do (a) output += validation process(g); //A detailed pseudo-code of this function can be found in section 3.4.2 return output; The algorithm analyzes each query clause according to Def. 1: Step 1: Each table in the FROM clause is represented as a node in the multidimensional graph. As presented in Section 3.3.2, MDBE will try to label every node, attribute and edge depicted in the query. Each node will keep track of relevant metadata inferred during the process. Specifically, we retain relevant metadata related to the query and referring to the data cube retrieved (if it makes multidimensional sense): the data cube base and compatibility information. Example: Consider the TPC-H business question #5 (Q5) that ”lists the revenue volume done through local suppliers”. We will present, a detailed view of each step for Q5. In this first step, the graph initially has six nodes: customer,orders,lineitem, supplier,nation and region. Step 2: This step is designed to find explicit dimensional data used to arrange the multidimensional space. According to [C3], the GROUP BY clause (see [C1]) must fully functionally determine data. Thus, fields in this clause represent interesting perspectives from which to base data analyses. In addition, fields joined to these attributes in the WHERE clause will also be labeled as dimensional data (since joins represent conceptual associations stated in the end-user requirements [C1]). Current methods has thus far relief on foreign keys to identify dimensional data, so results depend on the degree of normalization of the data sources (see Section 3.1 for further information). In our approach we are not tied to design decisions affecting the data source logical schemas and can identify them from the requirements. For example, that the user state relationships not depicted in the logical schemas of the data sources (for instance, data grouping). Consequently, every attribute identified in this step is labeled in the multidimensional graph as an interesting level of analysis. In these steps, each time an attribute is labeled, the label of the node to which it belongs will be properly updated according to the decision diagram shown in Figure 3.7. Finally, we add the identified data cube base to the graph metadata. Example: Attribute n name from node nation is labeled as a level and accordingly (see Figure 3.7), nation is labeled as a node containing dimensional data (i.e., L). Furthermore, to propagate that knowledge, we verify any concept association in the WHERE clause in which n name is involved. However, there is no join involving that attribute. If c nationkey had been used in the GROUP BY clause instead of n name,s nationkey 86 and n nationkey would have been identified as dimensional concepts as well since there are two joins in the WHERE clause relating all of the attributes (i.e., c nationkey = s nationkey and s nationkey = n nationkey). Finally, we store the n name as the data cube base in the graph metadata. Step 3: This step is designed to find explicit factual data. Aggregated attributes in the SELECT clause (see [C1]) play a measure role. However, if the input query does not contain a GROUP BY clause we do not have to aggregate measures in the SELECT clause, and this step cannot identify them (these types of Cells and those not containing measures will be identified in Step 6). If the query does not perform a GROUP BY, we store the primary key used as the data cube base in the graph metadata (see Figure 3.5 for further details). Finally, we also track the compatibility information identified in the node metadata. Example: In this step, l extendedprice and l discount are identified as measures, and accordingly, table lineitem is labeled as a Cell with measures (CM). We also add to the graph metadata the compatibility information stated in the query: the (l extendedprice * (1 - l discount)) can be summarized by using sum function for all the dimensions in the data cube base (i.e., n name; see previous step). Step 4: This step is designed to find explicit dimensional data used to restrict the multidimensional space. Since a selection (i.e., a comparison between an attribute and a constant value) must be carried out over dimensional data (see [C1] and [C7]), this step labels attributes as dimensional concepts looking for comparisons in the WHERE clause, following the concept association criteria presented in step 2. Attributes identified in this step are labeled as descriptors unless they have been used to arrange the multidimensional space (in this case they would have been labeled as levels in Step 2). Example: The SQL query #5 contains three comparison clauses between attributes and constants in the WHERE clause (r name =’[REGION]’,o orderdate >=’[DATE]’ and o orderdate <’[DATE]’ + ’1’ year). Consequently, r name and o orderdate are labeled as descriptors. Accordingly, orders and region are labeled as dimensional data (L). In this step, we again verify joins in the WHERE clause involving any of these attributes to propagate the multidimensional knowledge through concept associations. However, none of the attributes, in our example, are involved in a join. Step 5: The previous steps are aimed at creating and labeling nodes and their attributes whereas this step creates and labels edges (i.e., concept associations). Conceptual relationships are depicted in an SQL query by joins in the WHERE clause (see [C1]). In the multidimensional graph joins are represented as edges, and this step is designed to label them following the process described in section 3.3.2.3. A list of potential edge labels is inferred according to the multiplicity inferred for a conceptual association in the WHERE clause (see Table 3.4). These alternatives are checked prior to labeling the edge, and a label is overlooked if it contradicts current knowledge depicted in the graph. For example, this may occur if a node has already been labeled and the edge label requires it to be relabeled in an incompatible way. An incompatible labeling 87 in the conciliation process (see next section). Consequently, more than one multidimensional schema can be produced for a given query. However, an alternative graph could make multidimensional sense but not represent a new and potentially interesting analytical perspective. Indeed, dimensional data could always be considered as an alternative factless fact, although in most cases it will not be relevant to the end-user. Therefore, this step is designed to determine the representativeness of new alternatives produced by Step 6, according to the following rule: R2: If, for a given query, we obtain two sibling graphs that suggest analyzing a given dimensional node as a factless fact, we disregard the potential factual role of that node. Two sibling graphs differ only in the labeling of one node. Therefore, they have exactly the same labels except for one node, which is considered to play a factless fact role in one graph and a strict dimensional role in the other. As an example, consider the following table, which depicts the alternative graphs obtained after the validation step for a given query: Id Node ANode BNode CNode D 1 CM CD C L 2 CM L C L 3 CM L C CD According to the previous definition, alternative Graphs 1 and 2 (which only differ in the label of B), and Graphs 2 and 3 (differing in the label of D) are siblings. In this case, and according to R2, for the first sibling relationship we disregard the first graph and choose Graph 2 as the most representative; for the second pair we disregard Graph 3 and choose Graph 2 again. Eventually, this query will produce a single multidimensional schema. In short, sibling graphs do not provide new interesting analytical perspectives. MDBE uses them to analyze the potential factual data that a dimension may contain. However, in most cases, the end-user would not be interested in this type of analysis. Knowledge inferred from Step 6 is therefore disregarded when it produces sibling graphs and is only considered and presented to the user in one of the following two cases: (i) Firstly, if we identify a dimensional node that may also play a factual role with measures. This scenario can only arise in a query without data grouping, in which case Step 6 would identify an atomic Cell with measures (see Section 3.3.2.2 for further details). Note that this type of node is relabeled in Step 6 as CDM and, as such, does not fit the sibling definition (since the alternative sibling graph labeling that node as Lwill be missing) and will not be pruned in this step. (ii) In the second possible case, we have a factless fact that cannot play a dimensional role (i.e., there is no sibling graph for this labeling). Example: The latter case (ii) occurs in the Q5 validation process. Consider Table 3.5. The two valid labels are shown in rows 6 and 7; since they do not have sibling graphs, none will be pruned in this step. Essentially, MDBE highlights that Q5 will make multidimensional sense if either supplier or orders plays a factless fact role (the query semantics can be checked to confirm that this is consistent with the query definition). 3.4.4 Fourth Stage: Conciliation MDBE validates each input requirement and obtains a potential set of multidimensional schemas for each query (see the three previous stages presented above). In this section we present an 94 algorithm that conciliates the results for the input queries into a minimal set of schemas covering all of the queries. Before proceeding to the conciliation, a pre-process must be carried out to normalize the multidimensional graphs; each hybrid node in every multidimensional graph is normalized. This means that any node labeled as CDM or CD will produce two different nodes: according to the discussion introduced at the end of Section 3.3.2.3, hybrid nodes contain factual data (and thus, like any other Cell, the link attributes) and additional dimensional data (that in the general case will introduce redundancy of data). In fact, hybrid nodes could be represented as factual data (i.e., a node labeled as CM or C) related by a many-to-one (or in a degenerate case, a one-to-one) relationship to dimensional data (i.e., a node labeled as L); in other words, we could normalize them. We then apply the following algorithm (for clarity, the comprehensibility of the algorithm took priority over its performance): •(1) MDBE looks for all the facts identified in the multidimensional graphs, and creates a new factual class4for each one (every class will eventually produce a multidimensional schema at the end of the conciliation process). Two other tasks are performed in this step: i) we enrich each class by adding the measures identified in the graphs as attributes of the factual class; and ii) we draw the conceptual relationships between facts depicted in the graphs by semantic relationships between classes. Example: Consider a simplified scenario of the TPC-H case study in which we only need to conciliate the multidimensional graphs created for Q5 and Q9 (see Figure 3.9). First, we create four factual classes (lineitem,orders,supplier and partsupp) for each node labeled as either CM or C. Then, we add the measures identified in these graphs to each class. Consequently, l extendedprice,l discount (from Q5 and Q9) and l quantity (from Q9) are added to the lineitem class and ps supplycost (from Q9) is added to partsupp. The remaining classes will not contain measures as they were identified as factless facts (see Q5). In addition, since partsupp is related to lineitem in Q9, we keep track of this conceptual relationship by drawing a semantic relationship between the two classes. The same is done with lineitem and order, and lineitem and supplier (Q5). •(2) Next, we conciliate the dimension hierarchies identified by the input queries. We first look for compatible hierarchies. Two hierarchies are compatible if they share their atomic level5. Every set of compatible hierarchies must be conciliated (i.e., produce a single dimension subsuming all of them). This process is carried out by checking the hierarchies graphs. From the perspective of the multidimensional graph, a hierarchy is represented by the subgraph containing the nodes that form the dimension. For example, the customer →nation →region hierarchy identified in Q5 (see Figure 3.9 and Table 3.5) is directly derived from the subgraph formed by these three nodes. Therefore, a hierarchy h subsumes a hierarchy h’ if the subgraph representing h’ is contained (except for the descriptors) in the subgraph representing h. At this point, it should 4In this step we are devising the multidimensional conceptual schema. We therefore talk about classes and attributes in this section, but we could use the notation from any conceptual multidimensional model. For example, [ASS06]. 5An atomic level is the finest granularity level within a dimension hierarchy and is directly related to the fact [ASS06]. 95 be noted that a one-to-one relationship is contained in a one-to-many or a many-to-one relationship. Having said that, we conciliate a set of compatible dimensions by applying the following properties iteratively: –(2.1) If a given hierarchy hsubsumes a hierarchy h’ and h’ also subsumes h, both hierarchies are equivalent and we only need to keep one of them aligning all of the descriptors of both dimensions. The other hierarchy must be removed from the set of compatible hierarchies. –(2.2) Alternatively, if hsubsumes h’ and h’ does not subsume h, the descriptors of h’ are mapped to h, and h’ is removed from the set. –(2.3) Finally, if hdoes not subsume h’ and h’ does not subsume h, they are conciliated as follows: i) first, we conciliate (by keeping the common structure and aligning their descriptors) the overlapping part shared by the hierarchies (note that, by definition, they will share at least their atomic levels; -see the compatible hierarchies definition above-); second, ii) we draw two alternative branches in the resulting hierarchy, one branch for each disjoint part of the subgraphs. Example: In our example, Q5 and Q9 provide two sets of compatible dimensions (i.e., the first set is a compound of the supplier →nation →region from Q5 and supplier →nation from Q9, and the second set is compound of orders dim from Q9 and Q5, and orders dim →customer →nation →region from Q5). In this scenario, conciliation of the two sets corresponds to the second case presented above: one hierarchy is contained in the other but the reverse is not true. Therefore, we keep the richest hierarchy and enrich it with the descriptors of the discarded one. The conciliated dimension hierarchies and those that are not compatible with any other are depicted in the multidimensional schema. For example, consider the orders dim →customer →nation →region dimension; its atomic level was related to lineitem and orders. Consequently, we relate this new conciliated dimension to these two factual classes. By carrying out this process, we will obtain a star schema for each factual class identified. Note that conciliated dimensions enrich the conceptual schema: they provide other factual classes with new analytical perspectives considered in other star schemas. For example, orders only considered the orders dim level, whereas it now has a detailed conciliated hierarchy. •(3) Finally, a pruning step is carried out. MDBE identifies those star schemas that are semantically poor. We can also introduce a non-representative requirement, which would produce an unneeded star, for example: every star schema composed of just one dimension is proposed to be disregarded (note that we could use any other criterion introduced in the literature [SKD07, RA07a], if desired). However, the final decision is taken by the user, since the star schema is derived from the end-user requirements and he/she must decide if it really makes sense or it was an error. Example: In the TPC-H case study, this would be the case of supplier and customer. Both have been identified as factless facts during the process, but their star schemas are rather simple (one dimension each). After considering the requirements from which they 96 were derived, we may decide to eliminate them (as was the case in the final schema shown in Figure 3.3). Two main points should be made about this process. First, it does not introduce a summarizability problem, because we are only merging compatible labels (i.e., factual data and only fully compatible dimensional data). It is also very important to note the relevance of semantics in the conciliation process. In a data warehousing design task, semantic relationships must be carefully considered. For example, two different relationships between the same concepts Aand Bmust produce two different perspectives. The reason is clear: each relationship relates a different set of instances from the two classes and, therefore, produces two different analytical perspectives. This explains why two dimension hierarchies such as A→r1B(where r1identifies the relationship between Aand B) and A→r2C→r3Bcannot be conciliated as A→r2C→r3B. Had we proceeded like this, we would have lost semantics. It should be considered that we are working with relational sources, so if we travel from Ato Balong two different paths there must necessarily be two different conceptual paths between them. As explained in Step 2.3 of the conciliation process, the hierarchies should be conciliated as: B←r1A→r2C→r3B; i.e., with two alternative branches starting from A(the common part). The second point is that the orthogonality of the multidimensional spaces that may be produced is not lost, since we keep track of the metadata inferred from each query at the constellation level (see section 3.4.1; steps 2 and 3). Note that each input query represents a data cube of interest. Consequently, our output schema retains the metadata about these datacubes: the multidimensional space depicted (i.e., the cube base) and the information about the compatibility of the data summarization performed (i.e., which function may be used for their measures and in which dimensions). This type of information will be relevant for the OLAP tool once it has been implemented. Finally, this stage, like the three previous stages, is fully automatic and we therefore obtain a star schema for each fact identified; this, as a whole, produces a constellation schema (see Figure 3.3). Note that this figure only shows facts,measures and dimension hierarchies identified in the process, whereas descriptors have been overlooked to avoid disrupting the final result. Nevertheless, it should be stressed that MDBE works at the attribute level and keeps track of the role assigned to each attribute when deriving partial schemas from each query. Consequently, we are able to split some tables (for example, orders produced two different concepts in the multidimensional schema, since the dimensional attributes contained in the relational orders table are represented explicitly in orders dim). 3.5 A Practical Case: The TPC-H In this section we discuss several issues about the overall TPC-H case study. MDBE was carried out for the 22 TPC-H queries that together produced the constellation schema shown in Table 3.3. Below, we focus on five interesting aspects of this case study: the specificity of requirements needed, the expressiveness and quality required in the sources, the degree of automation achieved, the computational complexity of the algorithm and the quality of results obtained (i.e., the output correctness and the extra knowledge obtained in the output thanks to the novel contributions of MDBE). Note that our study is exhaustive regarding the four axis discussed in Section 97 1.7, and we also provide a study of the performance (and thus, feasibility, of our proposal). Later, we will also use this case study to provide a comprehensive framework in which compare the MDBE and AMDO methods. 3.5.1 Requirements Specificity MDBE requires to gather the end-user informational requirements and formalize them into SQL queries. Thus, one interesting aspect deserving further study is the number of queries needed to produce the resulting conceptual schema. In the output schema we identify 3 factual classes (containing 9 measures) and 9 dimension hierarchies (containing a total of 18 level classes and 39 descriptors): •In the worst case, we would need 11 queries to identify all of the factual classes and dimension hierarchies in the multidimensional model. In other words, some queries are redundant and are not relevant to the final result. Had we executed them in the worst possible order, we would have identified all the multidimensional classes and most of the attributes even with 11 queries (8 out of 9 measures and 17 out of 39 descriptors). •In contrast, in the best case, we would have been able to identify all of the factual classes and dimension hierarchies with just 4 queries (and 6 out of 9 measures and 10 out of 39 descriptors -it would also be possible to give more relevance to descriptors and then identify 16 out of 39 descriptors but 5 out of 9 measures, also with 4 queries-). For example, Q5 is a key requirement as it identifies 4 dimension hierarchies and 2 factual classes. Indeed, Q5 and Q9 identify all three factual classes and 4 measures of the resulting multidimensional schema. If we considered a random order of input queries (i.e., without any consideration other than choosing the order of the query execution at random) we would need an average of 8 queries (i.e., the average of the worst case -i.e., 11 queries- and the best case -i.e., 4) to identify the main structure of the schema (i.e., facts, measures and dimension hierarchies). This result is sound as it is relatively easy to identify the multidimensional classes with only a small number of queries. Indeed, the multidimensional design task proposed in this chapter is incremental, and it is up to the user to decide when to stop adding new queries. Once most of the structure has been defined, it can be customized as in traditional approaches. For example, consider a case in which we are satisfied with the number of facts, measures and dimension hierarchies identified by MDBE. Suppose that we have identified the 3 factual classes, the whole dimension hierarchies and the 9 measures. In an average case, these concepts can be defined with 8 queries and we would have approximately 14-19 descriptors (depending on the input queries used). To proceed further, it would be easier to identify the rest of the descriptors among the dimensional data table attributes than by launching new queries. Note that MDBE can easily support this last step: we can browse the attributes of each level identified and let users add those that are of interest to them. To continue with our example, at this point the region level class would contain r regionkey and r name but the r comment attribute in the relational table would not have been selected 98 yet. However, it would be easier to browse the region attributes and add r comment to the output schema than to launch a new query specifically for the purpose. 3.5.2 Data Source Expressiveness The TPC-H relational schema is well-formed and captures a fair picture of the business domain. For example, foreign keys are used to identify semantic relationships between attributes in different tables, and the schema is in 3NF. Importantly, note that MDBE is an interleaved hybrid approach, which analyzes the end-user and the data sources simultaneously, but the requirement analysis leads the process. Consequently, the quality of the sources required in our approach is considerably lower than in previous approaches working from relational sources. Indeed, as discussed in Section 2.1, current approaches demand that the source relational schemas capture the functional dependencies (i.e., to-one relationships) existing in the domain. This kind of relationships, typically represented at the logical level by means of foreign and candidate key constraints, are crucial to identify the multidimensional concepts and specially, the dimensional concepts. For this reason, the quality of the output obtained by current approaches decreases drastically for relational sources between a denormalized schema and a logical schema in 3NF. On the contrary, MDBE is able to produce high-quality results, even from denormalized sources, by means of two key features: •MDBE exploits the candidate - foreign key knowledge captured in the data sources. Nevertheless, if this information is missing, we are able to extract it from the requirements (in case it is relevant for the final result). For example, consider the TPC-H relational schema introduced in Figure 3.2, and the TCP-H #5 query used as example all over the chapter. In Q5, the c custkey = o custkey logic clause involves two concepts related by means of a primary - foreign key relationship and thus, it can be exploited by most of the current methods. However, if we discard the candidate - foreign key relationships in the schema, none of these approaches would be able to exploit it anymore. Relevantly, this does not affect MDBE, since we consider requirements. Indeed, SQL query joins represent concept associations explicitly stated by the user and thus, we are able to exploit them even if the attributes joined are not explicitly related in the sources. Consequently, the multidimensional knowledge inferred for attribute involved in joins in the WHERE clause is automatically propagated to its counterpart (see Section 3.1.2 for further details). Specifically, the orders node is initially labeled as a level in Step 4 (see Section 3.4.1) and therefore, its attributes involved in the query are identified as dimensional concepts (i.e., o orderdate, o custkey and o orderkey). Thus, by means of the c custkey = o custkey join, we propagate the knowledge inferred for o custkey to c custkey: i.e., it is also identified as a dimensional concept. Interestingly, later, Step 6 proposed orders to play a Cell role as well. This alternative is not prune in the third stage of the algorithm (see Section 3.4.3) and eventually, MDBE produces two results for the Q5 query (see Section 3.4.2). However, even in this case, o custkey and c custkey will still play a dimensional role: in this scenario, o custkey would have not been identified as a dimensional concept, but customer is labeled as level and accordingly, c custkey as dimensional concept. Consequently, o custkey is identified 99 as a dimensional concept by means of the association in the WHERE clause. This is sound, since MDBE is identifying o custkey as orders link attribute (see Section 3.3.2) and thus, it is part of the dimensional concepts forming the multidimensional space. •Furthermore, MDBE smooths the impact of denormalization on the output produced. Consider now a unique relation capturing the whole TPC-H relational schema (i.e., the TPC-H universal relation); i.e.: TPC-H(lineitem attrs, orders attrs, partsupp attrs, part attrs, supplier attrs, customer attrs, nation attrs, region attrs) where lineitem attrs refers to the whole set of attributes in the lineitem relation, and similarly for the rest. Functional dependencies would not be extracted from such a relation, and current approaches (i) would not be able to identify any dimensional concept or (ii) they would produce loads of meaningless results. On the contrary, MDBE is able to identify dimensional concepts from such a relation by means of the end-user requirements (see Section 3.1.2 for further details). For example, consider the TPC-H Q5 business query over the universal relation introduced above: Select nation name, sum(lineitem extendedprice *(1 - lineitem discount) as revenue FROM TPC-H WHERE region name = ’[REGION]’ and orders orderdate >=’[DATE]’ and orders orderdate <’[DATE]’ + ’1’ year GROUP BY nation name ORDER BY revenue desc; In this case, the multidimensional graph would be compound of just one node (i.e., TPC-H), which would be labeled as CDM, since nation name, region name and ordersorderdate would be identified as dimensional concepts (see Steps 2 and 4 in Section 3.4.1), and lineitem extendedprice and lineitem discount as measures (see Step 3 in Section 3.4.2). However, regarding dimensional data identified from this kind of relations, MDBE cannot automatically generate the dimension hierarchies, since requirements provide additional knowledge about the role played by each attribute but, under no circumstances, knowledge about the missing to-one relationships (i.e., functional dependencies) is provided. For example, considering just the dimensional concepts identified for Q5, and according to the requirements stated in the TPC-H benchmark, we should manually form the place dimension (in which nation name can be aggregated into region name) and the order date dimension. We can only overcome this drawback by mining the instances, but mining the instances is computationally expensive (see [JHP04], which already proposes to mine the instances to identify functional dependencies) and can be unfeasible for large databases. Finally, note that, although MDBE does not generate the dimension hierarchies from denormalized sources, it does identify the dimensional concepts and therefore, they do not have to be derived from scratch, but from the set of dimensional concepts identified for the fact (i.e., we do not shape dimensions by exploiting all the to-one relationships in the schema, but only those between concepts identified as dimensional concepts). 100 3.5.3 Automation The automation degree obtained in our approach is, in the worst case, as good as in equivalent approaches. Importantly, the whole process is automated once the requirements are expressed into SQL queries (the reader will note that there is no approach automating the end-user requirement elicitation process and thus, no automated counterpart can be used for this pre-process), and the user is only needed in the following cases: •According to rule R1, introduced in Section 3.3.1.1, if, for a given query, MDBE cannot produce any output, our approach tries to identify relevant derived measures or concept specializations by relaxing [C5] and [C6] respectively. In this case, if any result is generated, the user must validate the derived measures or concept specializations generated. In the TPC-H case study, only two queries (TPC-H #9 and #12 queries) required to relax these criteria and thus, the user is only asked to validate two queries out of the 22 used as input. •If [C7] is relaxed, we may allow selections by means of joins. In an OLAP tool, this scenario can only be considered if the selection done through the join paths are equivalent. Otherwise, the selection would not make multidimensional sense (see Section 3.3.1.1 for further details). Thus, if [C7] is relaxed, the user is responsible for validating the join paths stated in the query as equivalent. For example, following the example introduced in Section 3.3.1.1, MDBE would ask the user to validate if the lineitem -orders -customer - nation join path is equivalent to the lineitem -partsupp -supplier -nation one. If the end-user guarantees that they are equivalent (for example, if a business constraint guarantee that customers are only supplied with supplier from their own country) then, MDBE automatically rewrites the query to make multidimensional sense (by using two different alias for the nation table). Otherwise, it is discarded. •In case of dealing with denormalized data sources, the user is asked to shape the dimension hierarchies, by arranging the dimensional concepts identified. In the TPC-H case study this does not hold, and dimension hierarchies are automatically derived. Regarding the universal relation example introduced in previous section, it would embrace shaping the place and order date dimensions manually. In the first case, note that MDBE relaxes [C5] and [C6] regarding the data sources, and proposes derived measures or concept specializations, which guarantee the completeness and disjointness of the result proposed. However, since these new measures or specializations are not explicitly captured in the sources, only the user can validate them, and his / her participation is compulsory. Similarly, the second case can only be guaranteed by the user, since the semantics of each path are not captured in the data sources. Finally, in the latter case, there is no alternative to infer this knowledge from the logical schema. Indeed, this is inherent to relational schemas that, in the general case, are semantically poorer than conceptual schemas and therefore, relevant knowledge about the domain may be missing. Consequently, all the approaches working at the logical level suffer from this drawback. 101 Id Implicit Edges Alternative Validation Siblings #Results Factless New Dim. Nodes Contradict. Graphs Process Facts Attrs. Q1 0 0 1 0 0 1 0 3 Q2 5(3) 23(4) 9(4) 1(1) 7(2) 1(1) 0 0(1) Q3 2 1 3 0 2 1 0 (1) Q4 1(1) 0 2(2) 1(1) 0 1(1) 0 2(1) Q5 5 24 8 6 0 2 2 0 Q6 0 0 1 0 0 1 0 3 Q7 5(6) 20(51) 12(13) 0(1) 11(11) 1(1) 0 1(1) Q8 7(8) 98(225) 30(31) 0(1) 29(29) 1(1) 0 0 Q9 4(4) 4(4) 12(12) 0 11(11) 1(1) †1(1) 0 Q10 3 4 4 0 3 1 0 1 Q11 2(2) 1(1) 3(3) 0 2(2) 1(1) 0 2(0) Q12 2(2) 1(1) 3(3) 1(1) 1(1) 1(1) †5(5) 0 Q13 2 1 3 1 1 1 1 0 Q14 1(2) 0(1) 2(3) 0(1) 1(1) 1(1) 0(1) 1(0) Q15 1(2) 0(1) 2(3) 0(1) 1(1) 1(1) 0(1) 1(0) Q16 2(1) 1(0) 3(2) 2(1) 0 1(1) 1(1) 0 Q17 1(1) 0 2(2) 0 1(0) 1(1) 0 1(1) Q18 2(1) 1(0) 3(2) 0(1) 2(0) 1(1) 0 0(1) Q19 1(1)(1) 0 2(2)(2) 0 1(1)(1) 1(1)(1) 0 3(3)(3) Q20 2(1)(0) 1(0)(0) 3(2)(1) (1)(1)(0) 1(0)(0) 1(1)(1) 1(1)(0) 0(0)(3) Q21 4(1)(1) 9(0)(0) 7(2)(2) 1(1)(1) 5(0)(0) 1(1)(1) 0(1)(1) 0 Q22 0(0)(1) 0 0(0)(2) 0(0)(1) 0 1(1)(1) 0(0)(1) 2(2)(0) Table 3.6: MDBE statistics for the TPC-H case study 3.5.4 Computational Complexity & Performance Finally, we discuss our approach feasibility by presenting an in in-depth analysis of the 22 business queries in the TPC-H benchmark, and use the findings as the basis for discussing the complexity and performance of the MDBE algorithm. Table 3.6 summarizes some of the relevant statistics for each query. Statistics for their subqueries, if any, are shown in brackets (briefly, subqueries must be validated by their own, as they can be considered a materialized factual table and must therefore make multidimensional sense as well). The first column represents the query id and the other columns should be read as follows: the second column shows the number of implicit nodes we have for the query (i.e., nodes that remain unlabeled up to Step 6 or which are relabeled at that point). According to the number of implicit nodes, we can produce 2#implicit nodes label combinations (note that Step 6 only tries two label alternatives for unlabeled nodes). However, as discussed previously, many of these combinations are not even generated, since they raise contradictions with knowledge already depicted in the graph and, therefore, do not satisfy the multidimensional constraints. Ungenerated combinations are shown in the third column, and the fourth column shows the number of many alternative graphs (to be validated) generated for each query. The fifth column shows the number of multidimensional graphs that are discarded in the MDBE validation stage, and the sixth column shows the number of graphs that are are collapsed, according to the sibling rule introduced in Section 3.4.3. 102 The MDBE tool execution time for the TPC-H benchmark is negligible (∼1 second6). Our approach only has a potential combinatorial explosion in Step 6 (note that the conciliation process carried out - see Section 3.4.4- is linear regarding the number of schemas obtained and, therefore, it does not raise the computational complexity of the MDBE process). However, most combinations of labels generated by Step 6 are discarded on the basis of edge semantics (see the third column), which produces a tractable algorithm. In all queries, the final set of graphs to be validated is considerably smaller than 2#implicit nodes (see the fourth column). This statement is based on the empirical results provided, but we can intuitively identify why Step 6 will never generate an exponential number of combinations: the whole multidimensional graph must be semantically valid, which means that several nodes and edge labelings will not be allowed. For example, Table 3.4 shows 25 forbidden combinations (we count those allowed by relaxing [C5] and [C6], as they will only be considered if no result is generated. Thus, if considered, we obtain just one result at most). Consequently, many combinations of labels will fail to make multidimensional sense. Furthermore, the first five steps of the MDBE process always label most of the nodes/edges for multidimensional requirements. Only implicit nodes (see the discussion prior to Step 6 in Section 3.4.1 for further details) can produce unlabeled nodes. Consequently, the exponent value in the 2#implicit nodes expression will be typically a small number. For example, in the statistics shown, only two queries (Q7 and Q8) have more than 6 implicit nodes. However, Q7 invalidates 51 of 64 alternative graphs (and is computed in ∼0,1 s) according to edge semantics, and 225 of 256 in Q8 (computed in ∼0,12 s). Let us consider a query with a large number of implicit nodes. In this case, we will only generate all possible combinations of labels (i.e. exponential computational complexity) if these tables are related by one-to-one relationships with a double FK pointing between each pair (see Tables 3.3 and 3.4). However, this would be an unlikely real-world scenario and, in any case, an SQL query is unlikely to have a large number of tables in its FROM clause. The MDBE validation process takes an average of 0.007 s, so in the worst-case scenario discussed above a query with 10 unlabeled tables in the FROM clause would generate 1024 label combinations, which would be processed in 7.168 secs. 3.5.5 Output Quality In this section we measure the quality of the output produced by MDBE. We do so by means of the result correctness (by comparing the output obtained with the multidimensional schema proposed in the Star Schema Benchmark), and the additional output inferred regarding both, the Star Schema Benchmark and previous approaches. 3.5.5.1 Output Correctness The Star Schema Benchmark (or SSB) [P. 09] presents a multidimensional logical schema that is derived manually from the TPC-H schema. This schema was devised to improve the querying performance of the data warehouse by denormalization. Data denormalization, achieved by implementing a logical star schema [KRTR98], is fairly common in data warehouse systems and is used to speed up certain queries [KRTR98]. Unlike SSB, the MDBE method produces a conceptual schema, but the SSB logical schema can be obtained by applying the same design decision 6The computer used in these test was equipped with an Intel Core 2 Duo 2.16 GHz processor, 3 GB of RAM. 103 Figure 4.1: A fully denormalized relational schema of a car rental agreement There, a single relation (namely, rental agreement) models data related to a car rental agreement in a relational database management system (RDBMS). Each row represents an attribute of the relation (in italics its data type). The relation primary key is identified by the PK label and the capital letters in brackets next to each attribute represent the multidimensional role that attribute should play according to its semantics (Mstands for measure; i.e., interesting business measures of our fact of study, and DC for dimensional concept; i.e., interesting perspectives of view of our fact -a detailed definition of the multidimensional concepts may be found in Section 1.5-). Only those concepts that would play a meaningful role in the multidimensional schema are shown in the figure, but additional attributes could be found in the relation (depicted by the ellipsis at the end). In this case, current methods would either i) overlook all the dimensional concepts (since they are not involved in any CK or FK), or ii) identify all the nonnumerical attributes as dimensional concepts (i.e., even those not making multidimensional sense and not shown in the figure). Furthermore, even if they were able to identify any dimensional concept they would not be able to identify potential aggregation paths (or roll-up relationships) that would give rise to dimension hierarchies. Thus, they are not able to answer the following questions: is each dimensional concept conforming a dimension by itself? which of them would form the same dimension hierarchy (i.e., which are levels and which descriptors within the same dimension)? which belong to the same dimension and which to dimensions semantically related? In this sense, note that MDBE (see Chapter 3) partially overcomes this major drawback by considering end-user requirements as first-class citizens. Indeed, the analysis of requirements allows MDBE to identify dimensional or factual attributes that the other approaches would overlook. However, regarding dimensional data identified from denormalized relations, MDBE cannot automatically generate the dimension hierarchies as the domain FDs needed to shape hierarchies are missing in the source schema (see Section 3.1.2). In short, requirements provide additional relevant knowledge, but the relationships between these attributes cannot be extracted from denormalized data sources. Dimension hierarchies are crucial in the multidimensional model which is based on two main features: (i) placement of data in the multidimensional space and (ii) summarizability of data (see Section 3.2.3 for further details). A bad design of the dimension hierarchies would directly impact on the aggregation paths we may have. Modify data granularity when showing data to the user is a key feature of OLAP tools (performed through the roll-up and drill-down operators; see Section 2.2.1). Thus, overlooking aggregation paths in the design task would impact on the 110 success of the whole system. Indeed, any intermediate situation between a denormalized schema and a logical schema in 3NF would affect the output quality of current multidimensional design methods. This scenario can be avoided by modeling the data warehouse from a conceptual formalization of the domain. The role of a conceptual layer on top of information systems has been discussed in depth in the literature (see, for example, [Oli04]). In case of reengineering processes, like the data warehouse conceptual design, the benefits are clear: the conceptual layer provides more and better knowledge about the domain to carry out this task. For example, consider now the ontology represented in Figure 4.21. This ontology plays a conceptual role regarding the logical implementation depicted in Figure 4.1. The piece of ontology depicted in the figure (that will be used as example in this chapter) refers to a car rental agreement between abranch and a costumer. For a given rental agreement (which can still be ongoing -i.e., an opened rental- or already closed -i.e., a closed rental- and / or be booked by reservation with or without guaranteed canceled), a car is assigned. Several information about the branch is captured, such as pendant car models to be assigned to rental agreements, the demand for a given kind of car group or the service depot associated to a branch. Moreover, a car belongs to a branch and it is assigned to aservice depot when maintenance needed. There, each relevant concept of the domain is clearly stated as well as its relationships with the other concepts, and for example we will be able to propose a car to be summarizable into two different aggregation paths (into car model and car group but also through the branch path up to the country,branch type or service depot it belongs to), that would form, as a whole, the car dimension. In this chapter we introduce AMDO (Automating Multidimensional Design from Ontologies), our approach for automatically deriving the multidimensional schema from a domain ontology. Our goals are mainly two: i) we want to improve the quality of the output got (by working over a conceptual formalization of the domain instead of a logical one) and ii) we want to automate the process. This second goal is the main reason for choosing ontologies instead of other conceptual formalizations, as ontology languages provide reasoning services that will facilitate the automation of our task. Our work, however, is not tight to a specific ontology language. In general, we assume OWL DL [W3C], a W3C recommendation, as our input ontology language, but we show later that any Description Logics (DL) language providing the necessary expressiveness can be considered in our framework (indeed, less expressible DL are enough, as discussed in Section 4.4.2.5). Nowadays ontology languages are widely used in different areas like data integration [Len02] and the Semantic Web [BLHL01], but in other areas, like software engineering, UML [Grob] and Entity-Relationship (ER) [Che76] are the most common choices. In these cases, our approach requires a pre-process to generate a DL ontology from the UML or ER diagram. This process can be automated nowadays [ACK+07, BCG05, CCDGL02, GDD07] and the expressivity needed in DL to capture UML / ER diagrams has already been addressed in the literature [ACK+07, BCG05, CCDGL02]. At this point it is important to note that when a conceptual formalization of the domain is not available then, by means of reverse engineering we may extract the ontology from the logical schema. However, the output obtained by AMDO in this case 1This schema captures a piece of the EU-Car Rental introduced in Appendix B. 111 Figure 4.2: Diagrammatic representation (based on UML notation) of a piece of a car renting ontology would be equivalent to results obtained by those approaches automating the design from logical schemas. The reason is that the ontology derived would reflect the logical design decisions made and thus, its potential lack of semantics would entail the problems described previously. 4.1 Contributions Our proposal is a reengineering process to derive the multidimensional schema from a conceptual formalization of the domain. Working from conceptual formalizations improves the quality of the output, as earlier discussed. Although other approaches already proposed to work at the conceptual level, AMDO is the first method presented in the literature automating the whole process: i.e., identifying facts, measures and dimension hierarchies. Relevantly, AMDO also introduces a fully automated method to identify bases of interest by using and exploiting the ontological knowledge. Previous approaches working at the conceptual level mainly rely on their requirement elicitation stages to discover the multidimensional concepts rather on an accurate analysis of the data sources (see, for example, [BvE99, BCC+01, CT98a, GRG05, GR09, HLV00, MK00, PACW06, MTL07, WS03], which are discussed in detail in Section 2.1.2). AMDO follows a completely different framework based on a thorough and fully automatic analysis of the sources and then, carrying out a guided requirement elicitation stage a posteriori, as discussed in Section 4.3. Therefore, unlike previous approaches, the automatic analysis of the sources leads the process. 112 AMDO considers all the multidimensional concepts in depth by analyzing their semantics and how they should be identified from the sources. As result we propose new and original design patterns. For example, a more accurate heuristic to discover facts, based on the ontology topology (see Section 4.3 for further details), is provided; we handle measures and dimensional concepts uniformly in an automatic way (see Section 4.3.1); we are able to identify aggregate measures (see Section 4.3.2), which have been completely overlooked in the literature and we introduce formal rules to distinguish between descriptors and levels in a dimension hierarchy as well as identify semantic relationships between dimensions (see Section 4.3.5). A possible reason why previous approaches that work at the conceptual level have overlooked the automation of the process could be that ER (or UML) are conceptual formalizations thought to graphically represent the domain, and unlike ontologies, not thought for querying and reasoning. To our knowledge, our approach is the first one considering the data warehouse design from ontologies. Hence, we do believe that this work opens new interesting perspectives. For example, we can extend the data warehouse and OLAP concepts to other areas like the Semantic Web, where ontologies play a key role providing a common vocabulary. One consequence would be that despite the data warehouse design has been typically guided by data available within the organization, we would be able to integrate external data from the web into our data warehouse to provide additional up-to-date information about our business domain (this novel concept of data warehousing is known in the literature as Web-Warehousing [RALT06]). As an additional and relevant contribution, we also propose a novel approach for discovering bases of interest by exploiting the ontological knowledge. Bases are, indeed, the multidimensional keys. Currently, we may find several works for computing functional dependencies (note that the traditional key concept is a specific case of functional dependencies; see, for example [AHV95]) and / or keys (e.g., [DT95, DKM08, FS99, Lim97, M. 92, SBHR06] among others), but they work either at the logical or data level, and they share some inherent constraints. Similar to the discussion earlier presented in this chapter, approaches working over the logical schema are tied to the design decisions made when devising the system (for example, denormalization of data) and these decisions have a big impact on the data semantics captured in the schema. Therefore, to avoid missing some important data dependencies, these approaches make some unrealistic assumptions such as completeness of the data structures (i.e., all the constraints of the domain of interest are captured at the logical level). For this reason, most automated approaches for identifying keys require to address this task at the instance level. However, these methods have various drawbacks: they tend to overlook composite keys (essential when dealing with bases), propose solutions that are computationally expensive, and register drops in performance when a large number of attributes or instances are processed. Importantly, in our approach, we guide the process at the conceptual level and we introduce a set of pruning rules for improving the performance by reducing the number of key (i.e., bases) hypotheses generated, and to be verified with data. Our algorithm is relevant because, despite the importance of object identification, most DL do not provide identification mechanisms, and only very expressive DL (that are not suitable for real world applications due to their computational complexity) incorporate them [CDGL+08]. 113 4.2 Method Foundations Our goal is to generate multidimensional schemas in an automated way and this section aims to concisely define the criteria our proposal will be based on; i.e., criteria allowing us to identify ontology concepts making multidimensional sense. Similar to the MDBE foundations introduced in Section 3.3.1, these criteria derive from the study introduced in Section 2.2.4 and discussed and formalized in Section 3.2.3. However, unlike MDBE, we do not need to consider how these criteria apply for SQL queries. Concisely, multidimensionality pays attention to two main aspects; placement of data in a multidimensional space and correct summarizability of data: •[Notation]: AMDO produces conceptual schemas structured according to the multidimensional model. Nowadays, it is widely accepted that data warehouses must be exploited by OLAP tools and thus, structured according to multidimensionality. As detailed in Section 1.5, multidimensionality is based on the fact / dimension dichotomy (see bolded terms). Dimensional concepts give rise to the multidimensional space where the fact is placed. By dimensional concepts we refer to any concept likely to be used as a new perspective of analysis. Traditionally, they have been classified as dimensions,levels and descriptors. Thus, we consider a dimension to contain a hierarchy of levels representing different granularities (or levels of detail) to study data, and a level to contain descriptors (i.e., level attributes). On the other hand, a fact contains measures of analysis, and one fact and several dimensions to analyze it give rise to a multidimensional schema. •[C1] The multidimensional space arrangement constraint:Dimensions arrange the multidimensional space where the fact of study is depicted. Each instance of data is identified (i.e., placed in the multidimensional space) by a point in each of its analysis dimensions. Conceptually, it entails that a fact must be related to each analysis dimension (and by extension, to dimensional concepts) by a many-to-one conceptual relationship. That is, every instance of the fact is related to, at least and at most, one instance of an analysis dimension, and every dimension instance may be related to many instances of the fact. Importantly, note that this is a specific case of functional dependency. The fact determines the dimension; but unlike traditional functional dependency theory, we enforce that the fact is related to the dimensional concept by means of a mandatory relationship (in terms of mathematical relations, it would entail that the relation is complete). For the sake of understandability, from here on we force the notation and denote this kind of relationships by complete functional dependencies, or simply, complete fds. •[C2] The base integrity constraint: We denote by base aminimal set of dimensions functionally determining a fact. Thus, two different instances of data cannot be placed in the same point of the multidimensional space. In other words, given a point in each of the analysis dimensions forming the base, it only determines one, and just one, instance of data. Dimensions giving rise to a base must be orthogonal (i.e., functionally independent) [ASS06]. Otherwise, we would use more dimensions than strictly needed to represent data, and it would generate empty meaningless zones in the space. According to our current framework, note that the base is the multidimensional object identifier. 114 Figure 4.3: AMDO: method overview •[C3] The summarization integrity constraint: Data summarization performed must be correct, and we warrant this by means of the three necessary conditions (intuitively also sufficient) [LS97]: (1) disjointness (the sets of objects to be aggregated must be disjoint), (2) completeness (the union of subsets must constitute the entire set), and (3) compatibility of the dimension, kind of measure being aggregated and the aggregation function. Compatibility must be satisfied since certain functions are incompatible with some dimensions and kind of measures. For example, we cannot aggregate stock over the time dimension by means of sum, as some repeated values would be counted. However, compatibility will not be automatically checked in our method unless additional metadata was provided (for example, a list of compatibilities could be asked to the user for each measure identified). 4.3 AMDO: Automatic Multidimensional Design from Ontologies This section presents a detailed view of AMDO and how it applies the criteria exposed in Section 4.2. Figure 4.3 depicts a schematic overview of AMDO. There are three well-differentiated tasks: •The first task looks for potential subjects of analysis (i.e., facts). In the literature we can find different approaches to discover facts but most of them are hardly automatable. Identifying facts automatically is a difficult task [PD02], and most methods rely on heuristics such as table cardinalities or numerical attributes that may easily identify false facts or overlook real ones. The rest of approaches demand to identify facts manually. According to the multidimensional paradigm, the analysis of data must facilitate the decision making within organizations and in this sense, the better knowledge you have, the better decisions you make. We say, thus, that an ontology concept is likely to play a fact role if it has as many measures as possible and it can be analyzed from as many different perspectives as 115 possible. Eventually, this fact may not be of interest for the user (this will be considered later in our approach), but objectively, it will provide many different measures to analyze from many different perspectives. This task, therefore, is divided in two main subtasks; (1) discover potential dimensional concepts and (2) point out potential measures. Note that we do not talk about dimensions but about dimensional concepts. This step will find potential points of view to analyze the subject of analysis but, at this point, we are not able to distinguish their dimensional role (i.e., a dimension, a level or even a descriptor). This job is carried out in the third task of the algorithm, where dimension hierarchies will be shaped. Now, for each ontology concept we can estimate its likeliness of being a fact. In general, concepts with the most potential dimensional concepts and measures are good candidates, but we may weight each input according to our preferences. In our approach we define f as a function that, given the number of dimensional concepts and measures of a concept c, it evaluates cas a promising fact. The quality function will prune those concepts below a given threshold. This threshold will depend on the quality function provided (AMDO is not tied to a specific function). In fact, we can use any function we would like to, like the “Connection Topology Value” (CTV) [SKD07] introduced in the literature that only gives weight to dimensional concepts found, or develop our ad hoc formula. For example, it would also be possible to rate facts according to the relevance of a concept in the application domain. Finally, potential facts not pruned are ranked according to its f value, and presented to the user. From each fact selected by the user, the second and third tasks are launched once, and eventually producing a multidimensional schema for each fact. Thus, as a whole, our approach produces constellation schema [KRTR98]. •The second task discovers sets of concepts likely to be used as a base (see [C2]) for each fact identified. Bases are compound of concepts identified as dimensional concepts in previous step. In short, we look for concepts being able to univocally identify objects of analysis (i.e., factual data) and produce interesting data cubes. Bases identified are pruned according to the sparsity of the multidimensional space generated. Similar to the previous step, too sparse data cubes are filtered and not presented to the user. Eventually, the user will choose, among the bases proposed, those of his /her interest. •Finally, the third task gives rise to dimension hierarchies. Previous step filters the dimensional concepts of interest: among the whole set of dimensional concepts identified in the first step, the end-user selects those cubes of his / her interest. However, the user selects data cubes of interest (i.e., a specific data granularity level), but we need to propose interesting aggregation paths to navigate and analyze the cubes. Thus, for each dimensional concept in a base selected, we produce its own dimension hierarchy. Consequently, we aim to identify relevant aggregation paths looking for typical part-whole relationships for each interesting dimensional concept. In this step, AMDO builds graphs giving shape to each dimension hierarchy that the user may tune up to his / her necessities. AMDO carries out an exhaustive search of potential facts among all the concepts of the domain, like supply-driven methods do. This paradigm has a main benefit with regard to those 116 approaches which derive the schema from requirements and later, map them onto the data sources (i.e., demand-driven approaches): in many real scenarios, the user may not be aware of all the potential analysis contained in the data sources and, therefore, overlook relevant knowledge. Demand-driven stages do not consider this fact, and assume that requirements are exhaustive. Thus, knowledge derived from the sources not depicted in the requirements is not considered and disregarded. In our approach, we claim to derive all the multidimensional knowledge contained in the ontology, filter results according to quality evidences and eventually, let the user select results of his / her interest (i.e., according to the end-user requirements) among those produced by AMDO. On the one hand, we are conciliating requirements with data available as hybrid approaches do. On the other hand, we believe that, in many scenarios, it is easier to carry out the requirement elicitation process from knowledge proposed by AMDO than carrying out it from scratch. As counterpart, supply driven approaches tend to generate too many results and mislead the user. In this sense, our approach overcomes this problem by minimizing the amount of data shown to the user (i.e., by means of the concepts of quality function, threshold and the base concept). Specifically, after computing the likeliness of each concept as a fact, AMDO presents a ranked list of potential facts to the user (according to the quality function and threshold selected). For each concept, a value estimating its likeliness is provided. Moreover, if the user would like to, AMDO can show the list of potential measures and dimensional concepts computed for this fact. In the end, the user must select those relevant facts for his / her decision making. Similarly, among dimensional concepts identified for a fact of interest, we filter them according to the base concept. We propose to the user sets of concepts producing data cubes at different data granularity levels. Then, the user selects those cubes that better fulfill his / her necessities and accordingly, we filter the dimensional concepts. Finally, for each fact, AMDO provides (i) a list of (filtered) measures, (ii) a list of (filtered) dimensions (with their corresponding dimension hierarchies shown as a directed graph), and (iii) a list of relevant bases (i.e., potential data cubes of interest derivable from the set of dimensional concepts shown). For further details, an example over a realistic case is discussed while presenting our approach. 4.3.1 Discovering Dimensional Concepts This section introduces the multidimensional pattern to identify dimensional concepts from DL ontologies. Note that, in this chapter, we propose two different algorithms to compute this pattern (i.e., an ad hoc reasoning algorithm, and another using generic DL reasoners). Both are properly described in Section 4.4. According to [C1], a dimensional concept is related to a fact by a one-to-many relationship (i.e., a complete fd); that is, every instance of factual data is related to one, and just one, of its instances. Hence, we can express our pattern to look for dimensional concepts as follows: Fv= 1r.D, where r ≡(r1◦. . . ◦rn) Note that this pattern is expressed in Description Logic (DL) [BCM+03], where rand Dare variables, and Fthe ontology concept we are trying to identify as a potential fact. As discussed in the introduction, in the general case, we assume OWL DL (a W3C recommendation) as our 117 input ontology language. Accordingly, we use OWL notation and thus, we consider a class to be a unary predicate (i.e., Dand F), and a property (i.e., r) as a binary predicate expressing a relationship between two classes . Briefly, the vsymbol stands for subsumption, the basic inference in DL. Subsumption is the problem of checking if the subsumer (in our assertion, F) is considered more general than the subsumee (= 1r.D). That is, if the subsumee can always be considered a subset of the subsumer. ≡stands for a logic equivalence and can be defined as a specific kind of subsumption, that is: subsumer vsubsumee and subsumee vsubsumer.◦ stands for property composition (i.e., {a, c} ∈ r◦siff ∃bsuch that {a, b} ∈ rand {b, c} ∈ s). Finally, = 1 stands for a specific number restriction where, in our case, the number of individuals belonging to class Drelated to a given individual of the class F, through the property r, must be exactly one. Thus, we are looking for classes (D) such that every instance of a given fact (F) is related, directly or by property composition (r), to, at least and at most, one of its instances. For each ontology class Fwe look for classes that may play the dimensional concept role by evaluating the pattern presented above; where the dimensional concept is defined by the class D (from here on, the ending concept) and a composite property r(from here on, the property path or simply, the path). For example, consider the conceptual schema in Figure 4.2. Branch is a dimensional concept of rental agreement, as every instance of rental agreement is related, to at least and at most, one instance of branch. Thus, rental agreement would play the F role; branch the Drole and dropOffBranch the rrole. Note, however, that rcan be a composite property and thus, country is a dimensional concept of rental agreement as well, because every instance of rental agreement is related, at least and at most, to one instance of country by means of dropOffBranch ◦locatedAt. In our approach, we not only consider classes to play a dimensional concept role (i.e., the role of D), but also datatypes. Hence, a datatype may play a measure role (as it would seem more natural to think and we will discuss later), but also the role of an analysis dimensional concept. Handling facts and dimensions uniformly is not new. In fact, it was introduced by Agrawal et al. [AGS97] and since then, it has also been considered in many other design methods. Consequently, in our example, basicPrice and bestPrice will be considered potential dimensional concepts of rental agreement. Importantly, note that a dimensional concept and a measure derived from the same datatype must be semantically related in the output multidimensional schema (for example, by the “equivalence” construct in OWL or by an “association” relationship in UML). Definition 1. A dimensional concept is defined by an ending concept and a path of properties (i.e., a composite property). From a multidimensional point of view, the path must be considered because it adds relevant semantics. Two classes related by means of ndifferent to-one paths (i.e., a complete fd) must give rise to ndifferent perspectives of analysis, as all these paths will potentially identify different sets of instances in the ending concept. For example, consider Figure 4.2. There, rental agreement has two to-one relationships to branch (i.e., pickUpBranch and dropOffBranch). Thus, {branch,pickUpBranch} and {branch,dropOffBranch}must be considered as two different points of view from where analyze a rental agreement, and the semantics of each dimensional concept identified is provided by the combined semantics of the path and the ending concept. 118 4.3.1.1 Practical Consideration Several current design methods consider a dimensional concept to be a functional dependency (see, for example, [GR09, BvE99, HLV00, MK00, JHP04, GRG05]). Thus, they do not require the dimensional concept to be a complete functional dependency. From our point of view, we strongly recommend to enforce the theoretical pattern presented as much as possible. Relaxing them, indeed, may entail the identification of meaningless dimensions or give rise to sparser multidimensional spaces, which may mislead the user. Nevertheless, we could consider this practical consideration (i.e., fact instances not related to any instance of a dimensional concept) and, like current approaches do, automatically create a dummy instance (for example, named others) related to fact instances not related to the dimensional concept. Then, our pattern to look for dimensional concepts would look like as follows: Fv ≤ 1r.D, where r ≡(r1◦. . . ◦rn) This multidimensional pattern, however, cannot be used over arbitrary OWL DL ontologies. Indeed, the mandatory participation is needed in arbitrary ontologies to avoid discovering meaningless functional dependencies. Importantly, in an ontology, properties are not necessarily typed, i.e., they do not necessarily have a specified class as domain and a specified class as range. Therefore, we cannot establish, in the general case, that a property relates one class to another class. As a consequence, considering the pattern introduced in this section, every functional untyped property would potentially allow to infer that two arbitrary classes are functionally dependent on each other, provided that the property relates one instance to, at most, a single other instance (i.e., that it is functional). Note, however, that this general assumption does not hold for conceptual schemas. Consider Figure 4.2. In a UML conceptual schema, every property is strictly typed. Therefore, OWL DL ontologies derived from conceptual schemas are also strictly typed. Thus, when working from OWL DL ontologies assuming strict property-typing (for example, ontologies derived from conceptual schemas) we may relax and successfully compute the alternative pattern presented in this section. In the AMDO tool we introduced a check-box to allow the user enforce this restriction, or relax it, according to the designer own considerations. 4.3.2 Discovering Measures We now introduce the multidimensional patterns to identify measures from DL ontologies, and in Section 4.4.2.3 we describe how to compute them. In this step we look for measures (i.e., factual data). Typically, measures are numerical attributes allowing data aggregation. AMDO considers any summarizable datatype (i.e., those allowing data aggregation by its own nature) to be a measure of a given fact Fif, according to [C3], it preserves a correct data aggregation from F; i.e., if they are conceptually related by a one-to-one relationship or according to our notation, by a complete fd whose inverse property is also a complete fd). (1) The to-one multiplicity in the measure end enforces that each fact instance is related to just one measure value, and by the mandatory participation we preserve 119 Figure 4.5: AMDO: multidimensional schema proposed for the rental agreement fact hierarchies shown in Figure 4.5. There, each arrow starting from rental agreement depicts a dimension hierarchy. Concepts identified as levels by AMDO are depicted as a class, whereas concepts identified as descriptors are depicted in italics in the level they belong to. In total we generate nine maximal directed graphs (from customer,lastModification, assigment,dropOffBranch,pickUpBranch,rentalDuration,car,bestPrice and basicPrice). Next, the user must tune up dimension hierarchies obtained up to his necessities. For example, by considering some descriptors as interesting aggregation levels (it is the case of minimumDuration and maximumDuration that were identified as descriptors but we have considered to be interesting levels of aggregation in Figure 4.5) or by dropping dimensions of no interest (in our example, we have disregarded the (single-node) graphs produced for bestPrice and basicPrice). It is important to remark that levels derived from the same class but placed in different graphs would be related by semantic relationships. For example, country or branch type, which appear in different hierarchies. 4.4 Computing Functional Dependencies After presenting the patterns used by AMDO to identify the multidimensional concepts from a domain ontology, we know discuss how to compute them. Importantly, note that patterns presented to discover dimensional concepts, measures and dimension hierarchies are based on discovering complete fds. For example, dimensional concepts (see Section 4.3.1) and dimension hierarchies (see Section 4.3.5) patterns directly ask for complete fds between classes. About the patterns for discovering measures, Pattern 1 (see Section 4.3.2) looks for complete fds between classes and datatype. Pattern 2 looks for a bridge-concept Bfulfilling Pattern 1 such that, the fact is a dimensional concept of Band viceversa (i.e., Bis a complete fd of Fby means of a path p, whose inverse, namely p−, also depicts a complete fd between Fand B). Consequently, in this section we propose two different algorithms to compute complete fds. First, according to our general assumption, we consider the input ontology to be expressed in OWL DL. As discussed 126 in Section 4.4.2, this algorithm only benefits partially from generic reasoning algorithms. For this reason, and to take advantage of the well-known reasoning services provided by DL languages, we propose a second algorithm fully computable by a generic DL reasoner. To do so, we restrict the expressivity of the input DL, as discussed in Section 4.4.3. As an exception, note that measure patterns (namely, Pattern 1 and Pattern 2) can be relaxed and just ask for a mandatory (i.e., complete relation) in the bridge-class / datatype end. However, we will discuss later how to compute them. 4.4.1 Computing Functional Dependencies Over DL Ontologies In this section, we discuss how the functional dependency concept maps onto ontologies. Specifically, we discuss how to discover functional dependencies by relying on the assertions in a DL ontology. First, we recall some basic definitions regarding functional dependencies in the standard relational model (see, e.g., [AHV95]). Consider a relation schema R, i.e., a relation symbol with an associated set of attributes, each denoting one component of R. A functional dependency (fd) over Rhas the form R:X→Y, where Xand Yare sets of attributes of R. We say that a relation rfor Rsatisfies such a dependency if for each pair t1,t2of tuples in rsuch that πX(t1) = πX(t2), we have πY(t1) = πY(t2)(where, as usual, πX(t)denotes the projection of tuple ton the attributes in X). It is well known (for example, see [AHV95]) that the following set of inference rules is sound and complete for implication of fds over a relation schema R(below, X,Y, and Zare sets of attributes of R, and juxtaposition of two sets stands for their union): •If Y⊆X, then R:X→Y(reflexivity). •If R:X→Y, then R:XZ →Y Z (augmentation). •If R:X→Yand R:Y→Z, then R:X→Z(transitivity). In other words, all fds derived from a set Fof fds over R, i.e., the F-closure, can be computed by starting from Fand exhaustively applying the above inference rules. We would like now to carry over the conceptual level the standard notion of fd defined at the logical level. To this aim, we introduce the formal notion of fd over an ontology. We observe that previous work has already considered fds in the context of ontologies, see e.g., [CDGL01, TW05, TW08]. In these works, mimicking the notion in the relational model, a fd ensures that, if two objects that are instances of some concept share the same values for a set of attributes (or of attribute chains), then they share also the value of an additional attribute (or attribute chain), namely the attribute (chain) that functionally depends on the former attributes (chains). Instead, for our purposes, a fd should capture the intuition that the instances of one concept functionally depend on the instances of another concept. In other words, given two concepts C1and C2, we are interested in establishing whether each instance of C1allows one to determine a unique instance of C2. We will denote this by C1→C2. Several observations are in order: (i) The dependency between the two concepts C1and C2needs to be established explicitly, and this can be done by means of some role that relates C1to C22. 2Note that in the relational model, attributes that functionally depend on other attributes are implicitly related through the relation schema to which the attributes belong. 127 (ii) Since each instance of C1should determine a unique instance of C2, and such a dependency is established through a role, we need to require such a role to be functional. (iii) If we want to ensure a property analogous to transitivity (i.e., if C1→C2and C2→C3, then also C1→C3), we need to allow the dependency to be established not only by atomic roles, but also by composite roles (i.e., role chains). (iv) In an ontology, roles are not necessarily typed, i.e., they do not necessarily have a specified concept as domain and a specified concept as range. Therefore, one cannot establish in general that a role relates one concept to another concept. As a consequence, every untyped role would potentially allow one to establish that two arbitrary concepts are functionally dependent on each other, provided that the role relates one object to a single other object, i.e., that it is functional. This is clearly unsatisfactory, and therefore we need to enforce some stricter condition for a functional dependency C1→C2to hold. Specifically, we will require not only that the role is functional, but also that the instances of C1mandatorily participate to the role, and that the role necessarily relates them to an instance of C2. Importantly, note that the fd notion over DL ontologies is equivalent to that of complete functional dependency introduced in Section 4.2. 4.4.2 Using Specific Reasoning Algorithms In this section we consider that AMDO’s input ontology is expressed in OWL DL. Unfortunately, we may not take advantage of generic DL reasoning algorithms for directly computing patterns introduced at once, as most common reasoning services are not decidable when considering composite properties [BCM+03]. Indeed, composite properties are not even expressible in OWL DL. For this reason, in this section we discuss each pattern separately. We start discussing how to compute the pattern to discover dimensional concepts (see Section 4.3.2): •First, for a given class F, we look for its direct dimensional concepts. •Next, we compute the transitive closure of dimensional concepts according to the following transitive rule: Definition 3. If {A,r}(being Aa class and ra property) is a dimensional concept of B, and {C,r1}is a dimensional concept of A, then {C,r◦r1}is a dimensional concept of B as well. The first step can be completely computed using generic algorithms provided by DL reasoners and the second step requires an ad hoc algorithm that will also partially benefit from these algorithms. 4.4.2.1 Computing Direct Dimensional Concepts Computing direct dimensional concepts (i.e, complete fds) is equivalent to consider ras a single property instead of a composite property in the pattern introduced in previous section: Fv= 1r.D, 128 Where ris a single property. This pattern can be computed by basic reasoning (see Section 4.4.2.5 for further details about basic reasoning in DL) and for each class Fwe keep track of pairs {D,{r1, ..., rn}} (where every riis a property between Fand D), which define its potential dimensional concepts. According to Def. 1, every riidentified between Fand Dwill give rise to a different multidimensional concept. Using generic reasoning means that any assertion stated in the ontology (by using OWL DL constructs) is automatically considered. For example, subsumption of classes, subsumption of properties, cardinality restrictions, functional (or inverse functional) properties, etc. Finally, note that if the practical consideration introduced in Section 4.3.1.1 must be considered then, the pattern to look for in this step would be: Fv ≤ 1r.D, Where ris a single property, which can be also computed by basic reasoning. 4.4.2.2 Computing the Transitivity Closure of Dimensional Concepts In this section we present an ad hoc algorithm to compute the transitive closure of dimensional concepts. Despite this algorithm cannot be fully computed by using generic reasoning services, we can take advantage of subsumption to propagate this knowledge through class taxonomies, as we will show later. Our algorithm aims to compute the transitive closure of the asserted complete fds. With this aim, we build a matrix Mof N×Nelements (where Nis the number of classes in the ontology) such that each row depicts a class and its potential dimensional concepts: ∀{D, {r, ..., rn}} ∈ M < F >:   Fv= 1r.D, · · · Fv= 1rn.D Where Mis the N×Nmatrix, Fand Dare classes, r, ..., rnare composite properties. M < F > is an operator over Mthat retrieves a list of classes related to Fby, at least, a complete fd (i.e., its list of dimensional concepts). Each class in this list is represented as {D, {r, ..., rn}} where Dis the class (or datatype) itself and each riis a to-one path (i.e., a complete fds) depicted as a composite property. Therefore, we may derive as many dimensional concepts from Das different paths it has. Roughly speaking, each cell C(F,D)of Mcontains a list of composite properties ({r, ..., rn}) such that each instance of Fis related at least and at most to one instance of D. In this section we aim to build the final state of this matrix, and we achieve it by means of the next algorithm: Since Mis a sparse matrix, the function create matrix implements it as a vector of lists (see Figure 4.6, step 1). Thus, every position in the vector represents a class and its list of potential dimensional concepts (see the to−one rels typedef declaration). Lists are created and initialized to the empty list in step 2. Step 3 finds and breaks trivial deadlocks. The need of this step will be justified later in this section. Step 4 corresponds to the pattern presented in Section 4.4.2.1. Each potential dimensional concept identified is added to the proper list in the vector. Figure 4.7.1 (which represents ma- 129 typedef list <properties>path typedef tuple <concept, list<path> > paths to concept typedef tuple <concept, list<paths to concept> > to-one rels functioncreate matrix returns Matrix 1. vector<list<to-one rels> > M; 2. initialize(M); 3. compute trivial deadlocks(M, ontology); 4. first iteration(M, ontology); 5. propagate path(M, converge); 6. return M; Figure 4.6: AMDO: an algorithm to compute matrix M Figure 4.7: AMDO: exemplification of to-one paths propagation by transitivity trix M) shows results obtained after step 4 for some of the concepts in Figure 4.2. For example, the maintenance scheduled class has a to-one relationship to date (through the dateScheduled,acquisitionDate and lastMaintenanceDate properties), service depot (through the In property), branch (through the isAvailable and isResponsibleFor properties), car model (through the isOf property), boolean (through the available property) and double (through the currentMilleage and milleageFromLastService properties). Note that, according to Def. 1, those classes (or datatypes) related to maintenance schedule by several different paths (e.g., date) will generate as many dimensional concepts as different paths between both classes. For example, date will produce three different dimensional concepts: {date,dateScheduled},{date,acquisitionDate}and {date, lastMaintenanceDate}. Step 5 propagates the dimensional concepts identified in the previous step according to the 130 transitive rule (see Def. 3). We use the propagate path function (see Figure 4.8) for this purpose. void propagate path (Matrix lM) 7. list <paths to concept>ending concepts; 8. foreach Cin Mdo (a) if Mc< C > =∅then i. C.closed := true; 9. do { 10. bool conceptsClosed := false; 11. foreach Cnot closed in Mdo (a) reachable concepts := Mc< C >; (b) foreach Din reachable concepts such that !(M < C, D >).treated do i. if D.closed then A. foreach rin Mp< C, D > do B. listEls := listEls ∪(r◦M < D >); C. M < C > := M < C > ∪listEls; D. M < C, D >.treated := true; (c) if all closed(reachable concepts) then i. list <concept>parents := compute direct superconcepts(C,M); ii. if all closed(parents) then A. foreach Pin parents do B. M < C > := M < C > ∪M < P >; C. C.closed := true; D. conceptsClosed := true; 12. if(!conceptsClosed) (a) break deadlocks(M); 13. }while concepts not closed(M)>0 Figure 4.8: AMDO: an algorithm to compute the transitive closure of dimensional concepts This function implements a smart algorithm to compute the transitive closure of the asserted complete fds (i.e., the final state of M). Essentially, the list of dimensional concepts of each class is propagated only once during this process, when we know that it cannot vary. To do so, dimensional concepts are propagated from the end of the complete fd paths (from here on, leaf classes) to the beginning, according to the definition of closed class: Definition 4. We say a class C is closed or that a given class C closes in the ith iteration of our algorithm Closed(C,i), if all its dimensional concepts have been computed in ior a previous iteration. In other words, if a class Ccloses in a certain iteration i, no other dimensional concept will be identified for Cin any iteration jsuch that i<j. In our notation, we define Closed(C,i) as a recursive function: Closed(C,i) := ∀{D, {r, ..., rn}} ∈ M < C >:Closed(D, j)∧j < i, 131 Our algorithm only propagates closed classes (see the closed method in the algorithm). If a given class Ccloses in the ith iteration of the algorithm, we propagate its dimensional concepts in the i+1th iteration. Once propagated, it is never considered again thanks to the treated method. Note that this method does not hold at a class level but at dimensional concept level (i.e., regarding C:M < C, D >.treated). Thus, our algorithm aims to identify closed classes and propagate them just once. Propagating knowledge is done in two different ways: •Let Cand Dbe two classes such that Dis in the dimensional concepts list of C(see step 11b). Then, the dimensional concepts list of Dis propagated to Cby transitivity according to Def. 3 (see step 11(b)iA): ∀D∈Mc< C >, ∀Di∈Mc< D >:{Di,{Mp< C, D > ◦Mp< D, Di>}} ∈ Mp< C, Di>, Where Mc< C > and Mp< C, D > are two operators over matrix M. The first one retrieves the list of classes in the dimensional concept list of a given class C(i.e., it is equivalent to the operator M < C > but overlooking the path lists), and the second one retrieves the list of paths between two classes Cand Dsuch that Dis in the dimensional concept list of C(i.e., it retrieves the path information between Cand Din M < C >). Diare the set of classes in the dimensional concepts list of a concept D(i.e., ∀Di, Di∈ Mc< D >) and {M < C, D > ◦M < D, Di>}represents the concatenation of each path in M < C, D > with each path in M < D, Di>(for the sake of readability, this formalization is depicted with an slight abuse of notation in step 11(b)iB of the algorithm). Roughly speaking, we are concatenating each to-one path from Cto D, with each to-one path from Dto Di(see step 11(b)i). •Let Pbe a class such that Pis a parent (i.e., a direct superclass) of C. Then, all the dimensional concepts of Pmust be inherited by C(i.e., M < C > := M < C > ∪M < P >, see step 11(c)iiB). In our algorithm, this kind of propagation is done when all the dimensional concepts of Chave closed (see step 11c). Then, we can take advantage of DL basic reasoning (see Section 4.4.2.5 for further details) to compute the list of superclasses to propagate. Moreover, we do not propagate them until they have closed to avoid propagating more than once (see step 11(c)ii). Finally, closed classes are detected as follows: •First iteration: Leaf classes and datatypes (as discussed in Section 4.4.2.1, our algorithm considers the datatypes as potential dimensional concepts and in this sense, they can be considered leaf classes) close in this iteration (see step 8). •Second iteration: Classes that were closed in the previous iteration are now propagated. In this case, propagating them is immediate, as their lists of dimensional concepts are empty. Now, according to our definition of closed class, any class whose dimensional concepts have closed (and therefore, already propagated), closes in this step. •Nth Iteration: A given class Cwill close in this iteration if the last class to close in its list of dimensional concepts has already closed in the (n-1)th iteration (see step 11c). Therefore, all the dimensional concepts of Chave already been computed and we can now propagate Cin the next iteration (see step 11(c)iiC). 132 Following our example, Figure 4.7.1 shows direct dimensional concepts identified for each ontology class and Figure 4.7.2 depicts how we propagate them by transitivity. For example, rental agreement is related by two to-one relationships to branch (bolded in the figure), and branch is related by to-one relationships to country,string,branch type and service depot. Hence, the latter are also considered dimensional concepts of rental agreement according to the transitivity rule (see the arrow in Figure 4.7.2). Moreover, note that the path list of these newly identified dimensional concepts have been properly updated when adding them to the list of rental agreement. For example, we can get from rental agreement to branch by two different paths (i.e., pickUpBranch and dropOffBranch) and from branch to country by the locatedAt property. Therefore, from rental agreement we can get to country through the composition of pickUpBranch and locatedAt, and dropOffBranch and locatedAt. Analogously for the rest of dimensional concepts. At a given iteration, when detecting closed classes, it is important to detect potential deadlocks due to complete fd cycles between classes. When a cycle is detected (in our algorithm, when no class closes in the current iteration; see step 12) it is broken propagating just once among them (and therefore, sharing all their potential dimensional concepts). Moreover, this situation will be notified to the user to let him / her know that each recurrent propagation within the cycle may add new interesting semantics (i.e., new analysis dimensional concepts) that could be considered. The most common and also easiest case to detect are one-to-one and reflexive relationships. To facilitate the process, AMDO treats these two basic cases immediately after being identified (see step 3 of Figure 4.6). Detecting trivial deadlocks can be computed by generic reasoning (see Section 4.4.2.5 for further details) and we may use any of the current algorithms presented in the graph theory to detect general cycles. For example, a depth-first-search (DFS) remembering previous visited nodes would fit properly. For example, customer and driving license through the one-to-one has property is computed in the first iteration. At this point, we are able to compute its list of dimensional concepts breaking up the deadlock (i.e., do not apply the transitive rule over it) and notifying to the user that, in case s/he would be interested, it is possible to derive new dimensional concepts just following the cycle semantics. Complexity of the Algorithm The computational cost of this algorithm has Θ(N×cl)as an upper bound; where Nis the number of classes in the ontology; cthe maximum to-one connectivity (i.e., direct to-one relationships from a class) and lthe maximum chain of to-one properties. However, this upper bound is theoretical and hardly achievable in practice since real ontologies neither have all classes with maximum to-one connectivity nor all to-one paths are of maximum length. Moreover, along the process, classes computed in previous iterations are not considered in the forthcoming ones. In practice, the computational complexity raised by AMDO is polynomial for most ontologies. For example, consider the EU-Car Rental ontology (see Figure 4.2). The whole EU-Car Rental ontology has 65 classes and 170 properties (or relationships) of which 94 properties are between classes (30 of them are subsumption assertions) and 76 are properties among classes and datatypes. The maximum to-one connectivity (i.e., c) is 21 (raised by LateReturn). In the worst case (i.e., assuming the practical consideration introduced in Section 4.4.3.4), the longest to-one path has length 5. Consequently, the theoretical upper bound for this simulation would be 133 Θ(65 ×215). However, using the AMDO tool, the execution of the algorithm was immediate (less than one second in a regular desktop computer). The algorithm converges in just 5 iterations: closing 2 classes before starting (i.e., besides datatypes, there are two classes with empty list of dimensional concepts), 12 classes in the first iteration, 13 in the second one, 19 in the third one, 15 in the fourth one and 4 in the last one. In each iteration, only some classes are propagated and those previously propagated are not computed again, so, a better estimation of the answer time would be: l X i=1 Ni×ci Where Niis the number of classes not yet closed (i.e., that still have to be considered) in that iteration, cithe maximum functional connectivity in that iteration and lthe number of iterations (i.e., the size of the bigger to-one path in the ontology). In our example, it would raise: 5 X i=1 Ni×ci= (63 ×21) + (51 ×24) + (38 ×54) + (19 ×87) + (4 ×109) Result got, drastically smaller than the theoretical upper bound, is still an upper bound of the answer time of AMDO. Notice that we are considering the maximum connectivity for each class in each iteration, something completely false. However, we want to underline some important things depicted in this formula: on the one hand, we may appreciate that the value of Niis strictly decreasing and, on the other hand, the value of ciis never exponential. In fact, in the last iteration, its value is 109, far away from 215. All in all, despite the EU-Car Rental ontology size, AMDO behaves well and the answer time is good enough to develop an interactive tool. Soundness and Completeness of the Algorithm Our algorithm is clearly sound, since it computes direct to-one relationships and propagates them according to the transitivity rule presented in Section 4.4.2.2. Our algorithm is complete if we can assure that it converges; that is, if it would fully explore each to-one path (starting from the end, by identifying leaf classes, and going through the paths up to the beginning). We can say so if we can assure that if in a given iteration the vector Mis not updated then, in any of the following iterations it will not be updated either. It can be guaranteed because: •We detect and break deadlocks and, •in the worst case, if Pis the maximum number of to-one properties chained in the ontology, in each iteration the propagate path function (see step 5 of Figure 4.6) will propagate, at least, one property. Indeed, the invariant of the main loop of the algorithm (see step 9 of Figure 4.8) guarantees that the length of each to-one path explored up to current iteration is strictly increasing and at most, in Piterations we would have explored (and propagated) all chained to-one properties in the ontology. Thus, step 5 will not be able to propagate any other property in next iterations. 134 –Note, however, that we need to show that, in OWL DL, a to-one path (i.e., a composite property) is compound of to-one properties. In other words, that a path compound of, at least, a to-many property cannot be asserted to raise a to-one relationship as a whole. This holds because of the DL tree model property [Var96], which most DL languages, such as SHOIQ(D)upon which OWL DL is based, guarantee. 4.4.2.3 Computing Measures In Section 4.3.2 we introduced 2 different patterns with two variants. Pattern 1 and Pattern 1.a, can be computed by generic reasoning (see Section 4.4.2.5 for further details). Similar to the idea introduced in Section 4.4.2.1, for each class Fwe keep track of pairs {dt,{r1, ..., rn}} (where every riis a property between Fand dt). According to Def. 2, every riidentified will give rise to a different measure. Pattern 2 can be directly computed by matrix M(see Section 4.4.2.2): Measure(F,{dt, r1, ..., rn}):= ∃B, ∃r1, ..., rn| ∀ri,1≤i≤n, B v ∃ri.dt ∧(F∈Mc< B > ∧B∈Mc< F >) Note that it is expressed using matrix Mnotation, and it means that, by transitivity, we have been able to identify Bas a dimensional concept of F(i.e., as a complete fd) and viceversa. Finally, note that Pattern 2.a does not look for complete fds, and therefore, it is not computable from matrix M. Thus, to compute Pattern 2.a, we need to introduce a new matrix, namely matrix M1(of N×Nelements), where Nis the number of classes in the ontology. This matrix represents, for each class F, the list of classes we may get to by means of mandatory paths. Thus, analogously to the definition of matrix M, each row of M1can be defined as follows: ∀{D, {r, ..., rn}} ∈ M1< F >:   Fv ∃r.D, ··· Fv ∃rn.D Where M1is the N×Nmatrix, Fand Dare classes, rand rnare composite properties and M1< F > an operator over M1that retrieves a list of classes related to Fby, at least, a mandatory (i.e., 1..N) path. Like in the definition of matrix M, each class in this list is represented as {D, {r, ..., rn}} where Dis the class (or datatype) itself and each riis a mandatory path depicted as a composite property. Now, we can compute this pattern as follows: Measure(F,{dt, r1, ..., rn}):= ∃B, ∃r1, ..., rn| ∀ri,1≤i≤n, B v ∃ri.dt ∧(F∈Mc< B > ∧B∈M1c< F >) Where M1c< B > is the equivalent operator to Mc< B > of M1. Matrix M1can be computed with an algorithm analogous to the one presented in Section 4.4.2.2 (see Figure 4.6) to compute M, but instead of looking for direct to-one relationships in step 4, we will look for direct mandatory relationships: Fv ∃r.D, Where ris a single property. The rest of the algorithm (i.e., propagating this knowledge) remains the same. The addition of matrix M1do not modify the overall computation complexity. Indeed, 135