Databases Reference
In-Depth Information
Intuitively, if a set of queries is derivable from another set, then the answers
to the former can be computed using the answers to the latter. By definition,
if a set of queries is derivable from another set of queries, then the former
is free of inferences if the latter is so, while the converse is not necessar-
ily true. To determine whether the collection of even MDR queries, denoted
as
Q
∗
, causes any inferences, we find another collection of queries that are
equivalent to
Q
∗
and whose inferences are easier to detect. Intuitively, the
collection of even MDR queries contains redundancy that can be removed by
decomposing the queries into the smallest even range queries, that is
pairs
of
cells. For example, in Table 4 the query
q
∗
(
Q
2
,Bob
,
Q
3
,Alice
) is deriv-
q
∗
(
)
,q
∗
(
able from
{
Q
2
,Bob
,
Q
3
,Bob
Q
2
,Alice
,
Q
3
,Alice
)
}
, and hence
is redundant in terms of causing inferences.
It is not always apparent whether we can find an appropriate collection of
pairs equivalent to
Q
∗
. First, the collection of pairs included by
Q
∗
,asshown
in Table 5, is
not enough
for this purpose. The query
q
∗
(
Q
1
,Bob
,
Q
4
,Alice
)
Q
∗
. Second, the collection of all
possible pairs is
too much
. For example, the pair
is not derivable from the pairs included by
{
Q
1
,Bob
,
Q
3
,Bob
}
is not
Q
∗
. Fortunately, Theorem 2 shows that there always exists a
set of pairs equivalent to the collection of even MDR queries (the proof can be
found in [33]). The proof of the theorem includes an algorithm that constructs
the desired set of pairs
derivable from
Q
p
for any given data cube.
Table 5.
The Collection of Even MDR Queries
Q
∗
For The Data Cube in Table 4
q
∗
(
Q
1
,Bob, Q
2
,Bob
)
q
∗
(
Q
2
,Bob, Q
3
,Bob
)
Pairs
q
∗
(
Q
2
,Bob, Q
2
,Alice
)
q
∗
(
Q
2
,Alice, Q
3
,Alice
)
q
∗
(
Q
3
,Alice, Q
4
,Alice
)
q
∗
(
Q
3
,Bob, Q
3
,Alice
)
Non-pairs
q
∗
(
Q
1
,Bob, Q
4
,Alice
)
q
∗
(
Q
2
,Bob, Q
3
,Alice
)
Theorem 2.
Given any data cube, let the core cuboid be C
c
and the collection
of even MDR queries be
Q
∗
, then a set of pairs
Q
p
{{
u, v
}|
u
∈
C
c
,v
∈
=
C
c
,u
=
v
}
can always be found in O
(
|
C
c
|·|Q
∗
|
)
time, such that
Q
∗
≡
d
Q
p
is true.
For example, in Table 5, the algorithm groups cells included by the query
into pairs. For
q
∗
(
Q
1
,Bob
,
Q
4
,Alice
), it first group cells along one dimen-
sion and have
{
Q
1
,Bob
,
Q
2
,Bob
}
and
{
Q
2
,Alice
,
Q
3
,Alice
}
. It then
groups the remaining two cells
into a third pair.
Similarly, it processes the other queries in Table 5. The final result
Q
3
,Bob
and
Q
4
,Alice
p
Q
will
include all the pairs given in Table 5 plus
{
Q
3
,Bob
,
Q
4
,Alice
}
,asshown
p
in Table 6 is indeed equivalent to the
in Table 6. It can be verified that the
Q
Q
∗
in Table 5. First, any query in
Q
∗
can be derived by adding up the corre-
p
. Second, each pair in
p
can be derived by subtracting
sponding pairs in
Q
Q
Q
∗
.
queries in
