Databases Reference
In-Depth Information
system-low). That is, they are visible to all users. By assuming that the privacy
functions are public, we mean that users at all privacy levels utilize the same
strategies to draw inferences.
In Theorem 1 we show that the privacy problem is recursively enumerable
with respect to all privacy levels. In addition, the privacy problem is either
recursive or nonsimple. If the privacy functions are deterministic, then we
show that the privacy problem is either recursive or a cylinder. We show that
if the privacy level L1 dominates the privacy level L2 (such as the Private
level dominates the Public level), then the privacy problem with respect to
L1 is a subset of the privacy problem with respect to L2.
Theorem 1.
(i) For each privacy level L, PP[L] is recursively enumerable.
(ii) For each privacy level L, PP[L] is either recursive or nonsimple.
(iii) If all privacy functions which model the rules in deductive databases are
deterministic, then for each privacy level L, PP[L] is either recursive or
a cylinder.
(iv) If the privacy level L1 dominates the privacy level L2, then PP[L1]
⊆
PP[L2], where
⊆
is the subset function.
Proof of Theorem 1
Proof of Theorem 1(i).
Let
, ....be an effective
enumeration of all multilevel deductive databases where B1, B2, B3 . . ....
are all visible at level L.
B1, F1, T1
,
B2, F2, T2
The set
PP
[L] is enumerated as follows:
Step 1:
Perform 1 step in the computation of CnF1(B1). If it converges, let
X be the result. Check whether the privacy constraints in T1 classify
X at a level which dominates L. If so, list
B1, F1, G1
as a member
of
PP
[L].
Step 2:
If CnF1(B1) did not converge in step 1, perform two steps in the
computation of CnF1(B1). If it converges let X be the result. Check
whether the privacy constraints in T1 classify X at a level which
dominates L. If so, list
B1, F1, T1
as a member of
PP
[L].
Perform one step in the computation of CnF1(B2), CnF2(B1),
CnF2(B2). For each computation CnF(B) do the following: if it
converges let X be the result. Let T be the privacy constraints associ-
ated with
, Check whether the privacy constraints in T classify
X at a level which dominates L. If so, list
B, F
B, F, T
as a member of
PP
[L].
Step 3:
The following computations are performed:
If CnF1(B1) did not converge in step 2, perform three steps in the
computation of CnF1(B1).
If CnF2(B1), CnF2(B2), CnF2(B2) did not converges in step 2, per-
form two steps in their computation
