Security in Data Warehouses and OLAP Systems - Database Security: Applications and Trends - page 205

need to remove other cuboids that are not redundant, such as a 1 ,b 2 ,c 2 ,d 2

and a 1 ,b 2 ,c 2 ,d 3 . The result is a subset of S that includes all the descen-

a 2 ,b 1 ,c 1 ,d 1 dants of , namely, a descendant closure , as illustrated by the

upper curve in Figure 3.
The descendant closure has only one minimal descendant of the core
cuboid, and hence is free of m-d inferences to the core cuboid. The prop-
erty actually holds for any other cuboid in T .Thatis,forany c

T , only
one minimal descendant of c appears in this subset of S , and hence m-d infer-
ences to c are no longer possible. On the other hand, it is easy to observe that
the upper curve cannot be modified to include any of the cuboids between the
current two curves in Figure 3 without inducing possible m-d inferences. More
generally, as long as a cuboid c r satisfies that all its ancestors are included by
T , the descendant closure of c r will be the maximal result for preventing m-d
inferences. Moreover, the descendant closure turns out to be the only choice,
if any subset of S is to prevent the need for checking m-d inferences and at
the same time being maximal for that purpose. These results are summarized
in Theorem 3 (the proof can be found in [32]).

∈

Theorem 3. In any data cube, let L be the collection of all cuboids. Given

any L Below ( L ) can satisfy both that each cuboid not in C

has exactly one descendant in C that is not redundant, and any superset of C
must include more than one descendant of some cuboid in Below ( L ) ,iffC is
the descendant closure of some cuboid c r satisfying that c r is not in Below ( L )
but all of its ancestors are in Below ( L ) .

⊆L ,anyC ⊆L−

The results in Theorem 3 can be extended to the general case where the
object is specified by a set of cells instead of a set of cuboids. The key issue in
such an extension is that Slice ( S i )'s may overlap, and it would be prohibitive
if we need to compute a descendant closure for each of their intersections.
Fortunately, the set intersection of descendant closures is always another de-
scendant closure. This property guarantees that no m-d inferences are possible
to the cells included by multiple slices. However, obtaining the maximal re-
sult in Theorem 3 is intractable in the general case, and is no easier than the
maximum independent set problem.
After m-d inferences are prevented, we still need to remove 1-d inferences.
It may seem to be a viable solution to simply restrict any cell that causes 1-d
inferences. However, the restricted cells themselves then become targets of
inferences. Hence, we must adopt the following iterative procedure to remove
1-d inferences. First, we check each cell and add those that cause 1-d infer-
ences to the object so they will be prohibited by access control. Second, we
control m-d inferences to this new object by applying the results in Theorem 3
again. By repeating the two steps, we gradually remove all 1-d inferences. The
procedure terminates in at most m steps, where m is the number cuboids. The
final result is a set of cells that are guaranteed to be free of inferences to the
object.