000 frozen dimensions, that is, for schemas
of much more complexity than the ones found in practical scenarios.
Inference
In the framework of dimension constraints the hierarchy schema is augmented with
constraints yielding the notion of dimension schema. A dimension schema is a pair
2 Hurtado & Gutierrez
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
D = (H, ??‘) , where H is a hierarchy schema, and ??‘ is a set of dimension constraints.
A dimension schema specifies a set of possible dimensions, that is, the dimensions
that have the hierarchy schema H and satisfy the set of constraints ??‘. Those dimensions
are the possible instances of the schema.
A dimension schema D logically implies a dimension constraint a, if every dimension
d over the schema D satisfies a. The implication problem for dimension constraints
is the problem of determining, given a dimension schema D and a dimension
constraint ?±, whether D implies ?±. Although the implication problem for dimension
constraints is CoNP-complete in the size of the schema, due to the sizes of schemas
occurring in practice, it is treatable. The problem reduces to computing the frozen
dimensions of the schema. An algorithm to test implication based on the computation
of frozen dimensions, called Dimsat, is presented in Hurtado et al.
Pages:
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126