OLAP dimension constraints

ABSTRACT

In multidimensional data models intended for online analytic processing (OLAP), data are viewed as points in a multidimensional space. Each dimension has structure, described by a directed graph of categories, a set of members for each category, and a child/parent relation between members. An important application of this structure is to use it to infer summarizability, that is, whether an aggregate view defined for some category can be correctly derived from a set of precomputed views defined for other categories. A dimension is called heterogeneous if two members in a given category are allowed to have ancestors in different categories. In previous work, we studied the problem of inferring summarizability in a particular class of heterogeneous dimensions. In this paper, we propose a class of integrity constraints and schemas that allow us to reason about summarizability in general heterogeneous dimensions. We introduce the notion of frozen dimensions, which are minimal homogeneous dimension instances representing the different structures that are implicitly combined in a heterogeneous dimension. Frozen dimensions provide the basis for efficiently testing implication of dimension constraints, and are useful aid to understanding heterogeneous dimensions. We give a sound and complete algorithm for solving the implication of dimension constraints, that uses heuristics based on the structure of the dimension and the constraints to speed up its execution. We study the intrinsic complexity of the implication problem, and the running time of our algorithm.

REFERENCES

• 1: Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.122-133, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263676]
• 2: Peter Buneman , Wenfei Fan , Scott Weinstein, Path constraints on semistructured and structured data, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.129-138, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275502]
• 3: Luca Cabibbo , Riccardo Torlone, Querying Multidimensional Databases, Proceedings of the 6th International Workshop on Database Programming Languages, p.319-335, August 18-20, 1997
• 4: B. A. Goldstein. Constraints on null values in relational databases. In Proceedings of the 7th International Conference on Very Large Data Bases, Cannes, France, 1981.
• 5: C. Hurtado and A. Mendelzon. OLAP dimension constraints (extended version). In ftp.db.toronto.edu/pub/papers/fullpods02.ps.gz.
• 6: Carlos A. Hurtado , Alberto O. Mendelzon, Reasoning about Summarizability in Heterogeneous Multidimensional Schemas, Proceedings of the 8th International Conference on Database Theory, p.375-389, January 04-06, 2001
• 7: B. Huseman, J. Lechtenborger, and G. Vossen. Conceptual data warehouse design. In Proceedings of the International Workshop on Design and Management of Data Warehouses (DMDW), Stockholm, Sweden, 2000.
• 8: H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava, What can Hierarchies do for Data Warehouses?, Proceedings of the 25th International Conference on Very Large Data Bases, p.530-541, September 07-10, 1999
• 9: R. Kimball. The aggregate navigator. DBMS and Internet Systems Magazine, http://www.dbmsmag.com, November 1995.
• 10: R. Kimball. The Data Warehouse Toolkit. J. Wiley and Sons, Inc, 1996.
• 11: W. Lehner, H. Albrecht, and H. Wedekind. Multidimensional normal forms. In Proceedings of the 10th Statistical and Scientific Database Management Conference, Capri, Italy., 1998.
• 12: Hans-Joachim Lenz , Arie Shoshani, Summarizability in OLAP and Statistical Data Bases, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.132-143, August 11-13, 1997 [doi>10.1109/SSDM.1997.621175]
• 13: Multidimensional Data Modeling for Complex Data, Proceedings of the 15th International Conference on Data Engineering, p.336, March 23-26, 1999
• 14: Torben Bach Pedersen , Christian S. Jensen , Curtis E. Dyreson, Extending Practical Pre-Aggregation in On-Line Analytical Processing, Proceedings of the 25th International Conference on Very Large Data Bases, p.663-674, September 07-10, 1999

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Design, Languages, Theory