Databases Reference
In-Depth Information
among all the solutions [8]. We shall adopt this notion to model inferences
in SUM-only data cubes. Notice that for the special case of 1-d inferences,
as shown in Example 1, the coecients matrix itself would have a unit row
vector (which will certainly also appear in
M
rref
). It is well-known that the
RREF of a
m
n
matrix can be obtained by a Gauss-Jordan elimination with
complexity
O
(
m
2
n
) [19].
The number of empty cells can only determine the existence of 1-d infer-
ences in two extreme cases. First, if the core cuboid has no empty cell, then
trivially it is free of 1-d inferences as long as all the attributes have more than
one value. The second straightforward result says that any data cube whose
core cuboid has fewer non-empty cells than the given upper bound 2
k−
1
×
d
max
,
where
k
is the number of dimensions and
d
max
is the greatest domain size
among all dimensions, will always have 1-d inferences. If the number of empty
cells falls between the two bounds, then the existence of 1-d inferences can no
longer be determined simply based on the number of empty cells.
Although less straightforward, there is only a connection between existence
of m-d inferences and the number of empty cells (a lengthy proof of Theorem 1
can be found in [34]). Similar to the case of 1-d inferences, any data cube with
a core cuboid having no empty cells is free of m-d inferences. To relax this
rigid result, Theorem 1 gives a tight upper bound on the number of empty
cells for a data cube to remain free of m-d inferences. The bound is tight in the
sense that we can no longer tell whether m-d inferences are present from the
number of empty cells, once this number goes beyond the bound. Notice that
the bound only guarantees the absence of m-d inferences, while 1-d inferences
may still be present as long as the core cuboid has empty cells.
·
Theorem 1 (m-d Inferences).
In any k-dimensional data cube with one-
level dimension hierarchy, let C
c
be the core cuboid and C
all
be the collection
of all aggregation cuboids. Suppose the i
th
attribute of C
c
has d
i
values, and
let d
u
and d
v
be the two smallest among the d
i
's, then C
all
does not cause
any m-d inferences to C
c
, if the number of empty cells in C
c
is less than
2(
d
u
−
4) + 2(
d
v
−
4)
−
1
and d
i
≥
4
for all
1
≤
i
≤
k; for any integer
w
1
, there always exists a data cube with w empty
cells that causes m-d inferences.
≥
2(
d
u
−
4) + 2(
d
v
−
4)
−
These connections between inferences and the number of empty cells have
following implications. First, a data cube with no empty cells being free of
inferences means that the threat of inferences is absent if the adversary does
not know any cell from outbound channels. Second, a data cube can still be
free of m-d inferences, if it has fewer empty cells than the given upper bound;
however, the data cube needs to be checked for 1-d inferences. Hence, if an
adversary knows about a few cells in the core cuboid, inferences can still be
easily controlled. Third, a data cube having more empty cells than a given
bound always has inferences. That is, a data cube cannot be protected from
an adversary who already knows most of the cells. Finally, if the number of
