Databases Reference
In-Depth Information
The following remarks are in order.
•
Corresponding to a deductive database
where
nistheGodel number of B in the effective enumeration of all databases
and F is the privacy function, which corresponds to R.
B, R
there is a pair
n, F
•
There is no loss of generality in regarding a deductive database
B, R
as
where F is the privacy function which corresponds
to R and n is the Godel number of B in the effective enumeration of all
databases.
B, F
or
n, F
Figure 1 illustrates a partial graphical representation of the privacy function,
which corresponds to the deductive database considered in this example. A
rule R is applied to a data set to obtain a new data set.
Multilevel Database:
A multilevel database is a triple
where B is a
database, T is a recursive set of privacy constraints and A is an algorithm (i.e.
an effective procedure) which assigns privacy levels to the data based on T.
(Note that since T is recursive, one can effectively decide whether a privacy
constraint belongs to T.)
For example consider the database B =
B, T, A
{
m1, m2, .... mn
}
. If a subset
{
of the database is given as input to A, A terminates with the
privacy level of the subset of the output. The privacy level is computed based
on the privacy constraints in T. In this example, the privacy level is the
maximum privacy level of the sets
m1, m4, m5
}
{
m1
}
,
{
m4
}
,
{
m5
}
,
{
m1, m4
}
,
{
m1, m5
}
,
{m1, m2, ……mn}
{m1, m2, ……mn,e}
{m1, m2, ……mn,f}
{m1, m2, ……mn,e,p}
Fig. 1.
Graphical representation of a privacy function
