Databases Reference
In-Depth Information
{
. If a privacy constraint does not explicitly classify
a piece of data then its privacy level is assumed to be system-low which we
assume to be the lowest privacy level (e.g., public) supported by the system.
This is usually the level Public. Since T is recursive, one can determine the
privacy level of any piece of data.
Multilevel deductive database:
A multilevel deductive database is a quadruple
m4, m5
}
and
{
m1, m4, m5
}
where B is a database, F is a privacy function, T is a recursive
set of privacy constraints and A is an algorithm that assigns privacy levels to
the data in the database as well as to the derived data.
For example, in the graph of Fig. 1, algorithm A assigns privacy levels
to each node based on the recursive set of privacy constraints. We assume
that there is a unique algorithm, which assigns privacy levels to all the data.
Therefore we do not include the algorithm A in the discussion. Some directions
toward algorithm A are given in [THUR05c].
Privacy problem:
The privacy problem with respect to privacy level L is the
set of all triples
B, F, T, A
such that there is some x belongs to CnF(B)
and the privacy level of x dominates L. Note that we assume that the set of
privacy levels form a lattice (see also [THUR03c]). Formally stated the privacy
problem at level L is the set:
B, F, T
PP[L] =
{
B, F, T
>
|
Level (B)
≤
Land
∃
x(x
∈
CnF(B) and Level(x)
L)
}
where
∃
is the “there exists” symbol.
If the set
PP
[L] is decidable then given a database B, a privacy function F
and a set of privacy constraints T, the privacy controller can decide whether B
is privacy enhanced with respect to the privacy level L under the constraints
T and the inference rules F.
2.3 Properties of the Privacy Problem
As stated earlier if the privacy problem is solvable, then there is no problem.
That is, given a database B, a set of inference rules R and a set of privacy
constraints T, one can effectively decide whether the database is privacy en-
hanced with respect to a privacy level. Unfortunately, as we will see, the
privacy problem in general is not solvable. In this section we will state and
prove unsolvability results of the privacy problem. Once it is determined that
the problem is unsolvable. The next question that needs to be answered is: to
what extent is the privacy problem unsolvable? Is the problem creative? If so,
then it is of the highest degree of unsolvability. Our approach to showing that
an unsolvable problem is creative is to first show that it is nonsimple. This
is because no creative set can be simple. The next step is to show that the
nonsimple problem is a cylinder. This is because all creative sets are cylinders.
Finally we show that the cylindrical problem is creative.
In the discussion given in this section we assume that the privacy functions
as well as the privacy constraints are classified at the level Public (which is
