Databases Reference
In-Depth Information
Intuitively, a redundant cell in
S
can be ignored, because it can be com-
puted from other cells in
S
. This implies that we only consider
distribu-
tive
aggregation functions [15], such as SUM, MAX, MIN, COUNT, or non-
distributive functions that can be converted to distributive ones, such as
AVERAGE to a pair (SUM,COUNT). By ignoring non-comparable cells,
we shall only consider the inference caused by descendants. This assump-
tion may not hold if outbound knowledge can correlate cells that do not
depend on each other. To simplify our discussion, we first consider a spe-
cial case where the set
S
in any
Object
(
L, S
) is a complete cuboid. The
object
Object
(
L, S
) is thus simply (the union of) the cuboids in
Below
(
L
).
For example, in Figure 3 the lower curve in solid line depicts such an object
Below
(
a
1
,b
1
,c
2
,d
2
a
1
,b
2
,c
1
,d
2
) in a four-dimensional data cube. Let
T
be the object and
S
be its complement to the data cube. To remove inferences
from
S
to
T
, we first find a subset of
S
that is free of m-d inferences to
T
and
at the same time is maximal for this purpose. We then remove 1-d inferences
from this subset.
{
,
}
… …
<a
3
, b
2
, c
2
, d
2
>
<a
1
, b
2
, c
2
, d
3
>
… …
… …
<a
3
, b
2
, c
2
, d
1
>
<a
2
, b
2
, c
2
, d
2
>
… …
<a
1
, b
2
, c
2
, d
2
>
<a
2
, b
1
, c
2
, d
2
>
2
, b
2
, c
1
, d
2
>
<a
2
, b
2
, c
2
, d
1
>
2
, b
1
, c
1
, d
2
> <a
2
, b
1
, c
2
, d
1
><a
2
, b
2
, c
1
, d
1
>
<a
1
, b
1
, c
2
, d
2
>
<a
1
, b
2
, c
1
, d
2
>
<a
1
, b
2
, c
2
, d
1
>
<a
1
, b
1
, c
1
, d
2
>
<a
1
, b
1
, c
2
, d
1
>
<a
1
, b
2
, c
1
, d
1
>
<a
2
, b
1
, c
1
, d
1
>
<a
1
, b
1
, c
1
, d
1
>
Fig. 3.
An Example of Preventing m-d Inferences
The definition of reducible inferences can help to find a maximal subset of
S
that is free of m-d inferences to
T
. Roughly speaking, with respect to each
cuboid in
T
, we can remove all the redundant and non-comparable cuboids
from
S
such that only a set of
minimal descendants
need to be considered.
For example, in Figure 3, only the two minimal descendants
a
2
,b
1
,c
1
,d
1
and
a
1
,b
2
,c
2
,d
1
need to be examined for inferences. However, checking whether
the set of minimal descendants cause m-d inferences may still incur high com-
plexity, and we want to avoid such checking. We take a more aggressive ap-
proach by only allowing accesses to one minimal descendant. For example, we
can choose to allow
a
2
,b
1
,c
1
,d
1
a
1
,b
2
,c
2
,d
1
and remove
from
S
. We also
