First page Back Continue Last page Graphics

Completeness for Subset Constraints


Notes:

In the proof we may also use D4, D5 and D6 from labsession 2 of course. (Since they have been proven by using on ly D1, D2 and D3.
We're using  here because the square subset symbol doesn't exist in a font. (Sorry)
First we define the closure of X with respect to the set D of subset constraints as:
X+ = { A | A  X can be deduced from D by D1,D2,D3 }
Suppose that Y  X cannot be deduced from D. We are going to create an instance r in which Y  X does not hold but in which all the subset constraints of D hold.
Note that when Y  X cannot be deduced from D then Y  X+. (Same argument as for fd's: apply union D4 and decomposition D5 rules.)
attributes of X+ | other attributes
-----------------------------------
0 0 0 ... 0 0 0 | 0 0 0 ... 0 0 0
0 0 0 ... 0 0 0 | 1 1 1 ... 1 1 1
1. Clearly Y  X does not hold in r because value 1 occurs in Y and not in X.
2. Let W  V be a subset dependency in D.
If V  X+ then W  V holds because the values 0 and 1 occur under V.
If V  X+ then both V  X and W  X can be deduced from D by D1, D2, D3. This means that W is a subset of X+ and thus only the value 0 occurs under W, and then the instance r satisfies W  V.