ACM Transactions on Database Systems · 2005 · 93 citations · 17 references
ComputingComputer ScienceInformation SystemsData AnalyticsDatabasesKnowledge RepresentationDimensionality ReductionOnline Analytical ProcessingComplexityIntegrity ConstraintsMulti-dimensional AggregationMultidimensional ModelsViews
In OLAP, multidimensional data models use directed graphs of categories to structure dimensions, and summarizability—whether aggregates can be correctly derived from precomputed views—depends on these structures, especially when dimensions are heterogeneous. This paper introduces dimension constraints, a class of integrity constraints that enable reasoning about summarizability in heterogeneous dimensions. By defining frozen dimensions as minimal homogeneous instances, the authors present a sound and complete algorithm that efficiently tests constraint implication using structure‑based heuristics and analyze its computational complexity.
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 structurally heterogeneous if two members in a given category are allowed to have ancestors in different categories. In this article, we propose a class of integrity constraints, dimension constraints , that allow us to reason about summarizability in 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 the implication of dimension constraints and are a 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.
17
Proceedings of the 27th International Conference on Very Large Data Bases
Peter M. G. Apers, Paolo Atzeni, Stefano Ceri et al. · 2001 · 845 citations
Summarizability in OLAP and statistical data bases
H. Lenz, Arie Shoshani · 2002 · 292 citations