Databases Reference
In-Depth Information
empty cells falls between the given bounds, we can no longer tell whether
inferences are possible by only looking at the number of empty cells.
The above results can be used to compute inference-free aggregations based
on the three-tier architecture. The data tier corresponds to the core cuboid;
the aggregation tier corresponds to a collection of cells in aggregation cuboids
that are free of inferences; the query tier includes any query that can be rewrit-
ten using the cells in the aggregation tier. To compute the aggregation tier,
we first partition the core cuboid based on dimension hierarchies. We then
apply the above sucient conditions to find blocks that are free of inferences.
The union of those blocks then forms the aggregation tier. It is straightfor-
ward that the aggregation tier satisfies the three properties of the three-tier
architecture. Computing the aggregation tier has a linear time complexity in
nature since it only requires counting the number of empty cells in each block.
This is an improvement over previously known methods, such as transforming
a matrix to its RREF [8].
Parity-Based Method
The second method is based on a simple fact that even number is closed under
the operation of addition and subtraction. The nature of an m-d inference is to
keep adding or subtracting (strictly speaking, set union and set difference) sets
of cells until the result yields a single cell. Suppose now all the sets have even
number of cells, then how to add and subtract those sets to obtain
one
cell
would be significantly more dicult, although still possible as we shall show
shortly. We consider the
multi-dimensional range
(or MDR for short) query,
which can be regarded as an axis-parallel box. We use the notation
q
∗
(
u, v
)to
denote an MDR query, where
u
and
v
are any two given cells. Table 4 gives
examples of MDR queries and their answers. By restricting MDR queries
to only include even number of cells, it may seem that inferences are hard
to obtain. However, if we add up the answers to the last four queries and
subtract from it the answer to the first query, then dividing the result by two
gives us Bob's commission in
Q
2
,thatis
x
2
= 500.
Table 4.
Examples of Multi-dimensional Range Queries
The Core Cuboid
MDR Queries
MDR Query
Answer
q
∗
(
Q
1
,Bob
,
Q
4
,Alice
)
6500
Q
1
Q
2
Q
3
Q
4
q
∗
(
Q
1
,Bob
,
Q
2
,Bob
)
1500
Bob
x
1
x
2
x
3
q
∗
(
) 2000
q
∗
(
Q
3
,Alice, Q
4
,Alice
) 1500
q
∗
(
Q
3
,Bob, Q
3
,Alice
)
Q
2
,Alice
,
Q
3
,Alice
Alice
x
4
x
5
x
6
2500
The model of inferences in SUM-only data cube needs to be enhanced
with the new concept of
derivability
and
equivalence
between sets of queries.
