Databases Reference
In-Depth Information
Q
p
Equivalent To The Even MDR Queries in Table 5
Table 6.
A Collection of Pairs
In
Q
∗
{Q
1
,Bob, Q
2
,Bob} {Q
2
,Bob, Q
3
,Bob}
{Q
2
,Bob, Q
2
,Alice} {Q
2
,Alice, Q
3
,Alice}
{Q
3
,Alice, Q
4
,Alice} {Q
3
,Bob, Q
3
,Alice}
Not In
Q
∗
{Q
3
,Bob, Q
4
,Alice}
p
, we only need to decide if the lat-
ter causes any inference. We first denote
Q
∗
is equivalent to
Knowing that
Q
Q
p
as an undirected simple graph
G
(
C
c
,
Q
p
). That is, the core cuboid is the vertex set and the collection of pairs
Q
p
is the edge set. We then apply Chin's result that a collection of pairs is
free of inferences iff the corresponding graph is a bipartite graph (that is, a
graph with no cycle composed of odd number of edges) [37]. The existence
of odd cycles can easily be decided with a breadth-first search, taking time
O
(
p
given in
Table 6 will have an odd cycle of three edges, corresponding to the inference
described earlier.
The parity-based method can be enforced based on the three-tier inference
control architecture described earlier. A partition of the core cuboid based on
dimension hierarchies composes the data tier. We then apply the parity-based
method to each block in the partition to compute the aggregation tier. The
query tier includes any query that is derivable from the aggregation tier.
The relation
R
AD
and
R
QA
between the three tiers are simply the derivable
relation. The first property of the aggregation tier is satisfied because the
number of pairs in
p
|
C
c
|
+
|Q
|
). As an example, the graph corresponding to the
Q
p
must be
O
(
n
2
), where
n
is the size of the core cuboid.
The last two conditions are satisfied in a straightforward way.
Q
5.2 Generic Data Cubes
The two methods we just described can only deal with SUM-only data cubes,
which is a limitation inherited from statistical databases. Chin has shown that
even to detect inferences caused by queries involving both MAXs and SUMs is
intractable [6]. This section describes a method that does not directly detect
inferences, but instead first prevents m-d inferences and then removes 1-d
inferences. This approach enables the method to deal with data cubes with
generic aggregation types, and it also significantly reduces the complexity
because 1-d inferences are generally easy to detect by examining each query
separately. In contrast, m-d inferences are hard to detect because they are
caused by combinations of queries instead of each individual query.
Access Control
Limiting access control to the core cuboid is not always appropriate. Values
in aggregation cuboids may also carry sensitive information. For example, in
Figure 1 a user may need to be prohibited from accessing any employee's yearly
