Problem 1. Consider the following table describing objects {x1,x2,…,x7} by attributes {k1,k2,k3,k4,k5}.

k1 / k2 / k3 / k4 / k5
x1 / 11 / 1 / 13 / 10 / 11
x2 / 2 / 21 / 4 / 54 / 1
x3 / 36 / 3 / 39 / 11 / 0
x4 / 1 / 11 / 3 / 2 / 14
x5 / 15 / 45 / 15 / 16 / 2
x6 / 13 / 3 / 26 / 31 / 1
x7 / 0 / 27 / 3 / 1 / 29

Construct binary TV-tree with threshold 4 for an attributes to be active. When building the tree, you can not split the table in a way that one of the subtables contains only one object. Show how to use the tree to find the closest document to the one represented by [0, 15, 10, 15, 10].

Solution: k1: 0 1 2 11 13 15 36 L=2 (active)

P1 p2

P1

k1 k2 k3 k4 k5 k1 k2 k3 k4 k5

X2 2 21 4 54 1 x1 11 1 13 10 11

X4 1 11 3 2 14 x3 36 3 39 11 0

X7 0 27 3 1 29 x5 15 45 15 16 2

x6 13 3 26 31 0

k2: 1 3 11 21 27 45

p3 p4 p5 p6

k3: 3 4 13 15 26 39

p7 p8 p9

Problem 2.

Let us assume that the following fields in Table 1 have to be hidden: c(x2), c(x6), a(x3).

Apply SCIKD algorithm to find secure masking for Table below.

a b c d

x1 / 1 / 1 / 2 / 1
x2 / 1 / 2 / 2 / 2
x3 / 1 / 2 / 1 / 1
x4 / 2 / 1 / 1 / 2
x5 / 1 / 1 / 2 / 2
x6 / 2 / 2 / 2 / 2
x7 / 2 / 2 / 1 / 2

Solution:

a – decision attribute

a1*={1,2,3,5}, a2*={4,6,7}

b1*={1,4,5}, b2*={2,3,6,7}, c1*={3,4,7}, c2*={1,2,5,6},

d1*={1,3}< a1*, d2*={2,4,5,6,7},

b1.c1*={4}<a2*, b1.c2*={1,5}<a1* ,

b1.d2*={4,5}, b2.c1*={3,7}, b2.c2*={2,6}, b2.d2*={2,6,7}, c1.d2*={4,7}<a2*,

c2.d2*={2,5,6},

b1.d2.c1*={4}<a2* , b1.d2.c2*={5}<a1*

b2.c1.d2*={7}<a2* , b2.c2.d2*=b2.c2*.

d1->a1, b1.c1->a2, b1.c2->a1, c1.d2->a2, b1.d2.c1->a2, b1.d2.c2->a1, b2.c1.d2->a2

b – decision attribute

b1*={1,4,5}, b2*={2,3,6,7}

a1*={1,2,3,5}, a2*={4,6,7}, c1*={3,4,7}, c2*={1,2,5,6},

d1*={1,3}, d2*={2,4,5,6,7},

a1.c1*={3}<b2* , a1.c2*={1,2,5}, a1.d1*=d1* , a1.d2*={2,5}, a2.c1*={4,7},

a2.c2*={6}<b2*, a2.d1*=0, a2.d2*=a2*,

c1.d1*={3}<b2*, c1.d2*={4,7} c2.d1*={1}<b1* c2.d2*={2,5,6}

a1.c2.d1* ={1}<b1* a1.c2.d2* ={2,5}, a1.d2.c1*=0, a2.c1.d1*=0 a2.c1.d2*=a2.c1*,

c1.d2.a1*=0 c1.d2.a2*=c1.d2* c2.d2.a2*={6}<b2*

a1.c1->b2, a2.c2->b2, c1.d1->b2, c2.d1->b1, a1.c2.d1->b1, c2.d2.a2->b2

c – decision attribute

c1*={3,4,7}, c2*={1,2,5,6}

a1*={1,2,3,5}, a2*={4,6,7}, b1*={1,4,5}, b2*={2,3,6,7}

d1*={1,3}, d2*={2,4,5,6,7}

a1.b1*={1,5}<c2* a1.b2*={2,3} a1.d1*=d1* a1.d2*={2,5}<c2*

a2.b1*={4}<c1* a2.b2*={6,7} a2.d1*=0 a2.d2*=a2*

b1.d1*={1}<c2* b1.d2*={4,5} b2.d1*={3}<c1* b2.d2*={2,6,7}

a1.b2.d1*={3}<c1* a1.b2.d2*={2}<c2*, a2.b2.d1*=0 a2.b2.d2*=a2.b2*

b1.d2.a1*={5}<c1* b1.d2.a2*={4}<c1*

a1.b1->c2, a1.d2->c2 , a2.b1->c1, b1.d1->c2, b2.d1->c1, a1.b2.d1->c1,

a1.b2.d2->c2, b1.d2.a1->c1, b1.d2.a2 -> c1

d – decision attribute

d1*={1,3}, d2*={2,4,5,6,7}

c1*={3,4,7}, c2*={1,2,5,6}

a1*={1,2,3,5}, a2*={4,6,7}<d2*, b1*={1,4,5}, b2*={2,3,6,7}

c1.a1*={3}<d1*, c1.b1*={4}<d2*, c1.b2*={3,7}, c2.a1*={1,2,5},

c2.b1*={1,5}, c2.b2*={2,6}<d2*, a1.b1*={1,5}, a1.b2*={2,3},

c1.b2.a1*={3}<d1*, c2.a1.b1*={1,5}, c2.a1.b2*={2}<d2*, a1.b1.c1*=0

a2->d2, c1.a1->d1, c1.b1->d2, c2.b2->d2, c1.b2.a1->d1, c2.a1.b2->d2

The set of all rules extracted from Table 1:

{d1->a1, b1.c1->a2, b1.c2->a1, c1.d2->a2, b1.d2.c1->a2, b1.d2.c2->a1, b2.c1.d2->a2

a1.c1->b2, a2.c2->b2, c1.d1->b2, c2.d1->b1, a1.c2.d1->b1, c2.d2.a2->b2

a1.b1->c2, a1.d2->c2 , a2.b1->c1, b1.d1->c2, b2.d1->c1, a1.b2.d1->c1,

a1.b2.d2->c2, b1.d2.a1->c1, b1.d2.a2 -> c1, a2->d2, c1.a1->d1, c1.b1->d2, c2.b2->d2,

c1.b2.a1->d1, c2.a1.b2->d2}

a b c d

x6 / 2 / 2 / 2

a2*={a2,d2}

b2*={b2}

d2*={d2}

a2.b2*={a2,b2}, a2.d2*={a2,d2}, b2.d2*={b2,d2}

a2.b2.d2*={a2,b2,d2}

a b c d

x3 / 2 / 1

b2*=b2*, c1*=c*, d1*={d1,a1}

b2,c1*={b2,c1}

1.  Apply SCIKD to x2: (c=2)

a b c d

x2 / 1 / 2

a1*={a1}, a1.b2*={a1,b1}

b2*={b2}, a1.d2*= {a1,d2,c2}

d2*={d2}, b2.d2*={b2,d2}

x6: (c=2)

a b c d

x6 / 2 / 2 / 2

a2*={a2,d2}

b2*={b2}

d2*={d2}

a2.b2*={a2,b2.d2}

a2.d2*=a2*

b2.d2*={b2,d2}

b2.d2.a2*=a2.b2*

2.  x3: (a=1)

a b c d

x3 / 2 / 1

b2*={b2}, b2.c1*={b2,c1}

c1*={c1}

d1*={d1,a1}