Databases Reference
In-Depth Information
This Ends the Program
Set D =
∪{
Dm: m
∈
N
}
where
Di
∪
Dj = Di if i
>
j
=Djif i
≤
j
Clearly for any point x of Dm, all lines incident with X in D are lines of
Dm + 1.
Define f(x) =
}
=
{
y: (x
,
y) is a line of Dx + 1
}
f
−
1(x) =
{
y: (y
,
x) is a line of D
}
=
{
y: (x
,
y) is a point of D
{
y: (y
,
x) is a point of Dx + 1
}
Clearly f belongs to
PF
. That is, f is a privacy function and
PP
[
Public
]=
{
x
:
x is public and x
→
0(
D
)
}
This ends Part I of the proof.
We now state and prove three lemmas which constitute the second part of
the proof of Theorem 2(iii). We first need the following definition.
Definition
A label P is fixed at stage numbed H if either P remains assigned to the same
point at all stages numbered n
≥
H or P remains unassigned at all stages
numbered n
≥
H.
Lemma 1.
For each e, there exists a stage H(e) at which all labels Pi where
i
≤
earefixed.
Proof of Lemma 1.
There are four ways in which a label Pe can be moved.
(M1) Introduction at stage e (step 1)
(M2) Deletion at stage e (step 3a)
(M3) Reintroduction via an attack on i where e depends on i (step 3b)
(M4) Reintroduction via an attack on i under step 3c, case 3.2 (i)
The proof of the lemma is by induction on e.
Basis e = 0: P0 is introduced at stage 0 (M1). As 0 does not depend
number and there is no i such that i
<
0, P0 cannot be moved by M3 or M4.
Therefore, if 0 is never attacked then P0 is fixed at stage 0. If 0 is attacked at
stage m, then P0 is fixed and unassigned at stage m, i.e., H(0) = m.
Inductive step: As inductive hypothesis, assume that all labels Pi
<
eare
fixed at stage H(e-1). Pe is introduced at stage e (M1). It cannot stage e (M1).
It cannot be moved by M3 or M4 at a stage m
≥
H=MAX
{
H(e-1),e
}
.For,
