Databases Reference
In-Depth Information
the empty set. At the public level the privacy problem could be nonempty. We
show that there are situations in which the privacy problem at the public level
is (i) nonrecusive, (ii) not creative if the privacy functions are deterministic,
and (iii) neither recursive nor a cylinder.
Theorem 2.
(i) There is a situation where PP[Public] is not recursive.
(ii) Assuming that the privacy functions are deterministic, there is a situation
where PP[Public] is not creative.
(iii) There is a situation where PP[Public] is neither recursive nor a cylinder.
Proof of Theorem 2(i).
We first show that given a recursively enumerable set
W, there is a situation S such that
W
≡
m
PP
[Public]. Note that
≡
m is the many-one equivalence relation-
ship. The result is then immediate from the following reasoning.
* It has been shown that there is set K which is creative. K is the set
{
x: the xth partial recursive function halts on input x
}
* The situation S that is constructed from the recursively enumerbale set
K will guarantee that
PP
[Public] is creative. This is because if the two
sets A and B are many one equivalent and A is creative, then so is B.
Therefore, if
PP
[Public] is creative then it cannot be recursive.
Given a recursively enumerable set W, we create a situation S by defining
a set of privacy constraints and a privacy function. Let the set of privacy
constraints be
. That is, the only element that is assigned the private
level is the pair (0,0). We consider pairs of natural numbers. This does not
cause any problem due to the existence of the pairing function from N
{
(0,0)
}
N
onto N where N is the set of all natural numbers. The set of privacy constraints
is recursive (note that in this case it is also finite) and does not depend on W.
We define a privacy function, which depends on W as follows. We assume
that e is the index of W. The privacy function f for a pair (u, v) is defined as
follows:
×
{
(u
,
v+1)
}
if u
= 0 AND NOT T(e
,
u
,
v)
{
(0
,
u + v) if u
= 0 AND T(e
,
u
,
v)
f(u
,
v) =
{
(u
,
v
−
1) if u = 0 AND v
=0
φ
(the empty set) if u = 0 AND v = 0
Note that T is the Kleene
s T Predicate
The graphical representation of f is shown in Fig. 2. Note that defining f on
pairs of natural numbers does not cause any problem. This is because one can
define a privacy function g on N such that g(x) =
{
y: x = j(u,v) and y = j(p,q)
for some x,y,p,q and (p,q)
}
where j is the pairing function from NxN to N.
∈
f(u,v)
