On the Complexity of the Privacy Problem in Databases - Data Mining: Foundations and Practice - page 357

r(0)

0

x

y

(a)

t(x)

r(0)

x

y*

(b) 0

y

t(y*)

r(0)

y

(c)

x*

0

x

t(x*)

r(0)

(d)

x

0

y

t(x)

r(0)

0

x

y

(e)

t(x)

Fig. 4. Construction of a program

Program

Stage 0: D0 consist of the points 0 and 1 with 1 labeled P0.
Stage m (m ≥ n1):

Step 1: Introduce the label Pm to Dm-1 and extend the resulting graph
to Dm*.

Step 2: Find the smallest number e ≤ m such that there exist numbers

x, y, z all m satisfying the condition R(x, y, z, e, m) where R is the

conjunction of the following conditions R1, R2 and R3.

≤

R1 ≡ T(e , x , z) and M(z) = y

R2 ≡ NOT (x = y)

∗
Note that T is the Kleene's T predicate and R1 implies that e(x) = y.
For a discussion of the functions T and M we refer to [MEND79].

R3 ≡ x is labeled Pe in Dm