Let X , Y , S, R be sets of attributes such that S ? R and X ? Y = R. Let r be a relation over R that satis?es the nontrivial MVD R = X  Y (i.e., neither set X or Y is a subset of the other).

Question

a. Prove that if X ? Y ? S , then the relation ?S(r) satis?es the MVD S =(S ? X) (S ? Y ).
b. Suppose X , Y , S ,andR satisfy all the above conditions, except that X ? Y ? S. Give an example of r that satis?es R = X  Y but does not satisfy S =(S ? X ) (S ? Y ).

Answer 1

a. If t is a tuple over S such that tX= ?S ?X(t ) ? ?S ?X(r) and tY= ?S ?Y(t) ? ?S ?X(r) then tX and tY match over the attributes in X ? Y . We can extend these tuples to t'X? ?X(r) and t'Y? ?Y(r). Being extensions of tX and tY, these tuples also match on X ? Y. Since the MVD R = X  Y holds, t'X and t'Y join over X ? Y into a tuple t'? r. Since t = ?S(t'), it follows that t ? ?S(r). This proves that ?S(r)=?S ?X(r)  ?S ?Y(r).
b. Let A ? (X ? Y ) ? S.
Let r consist of just two tuples, t and s, such that:
1. t has the value 1 over the attributes in X ? Y and Y ? X , the value 2 over the attributes in (X ? Y ) ? A, and the value 3 over the attribute A
2. s has the value 4 over the attributes in X ? Y and Y ? X , the value 2 over the attributes in (X ? Y ) ? A, and the value 5 over the attribute A
It is easy to see that projecting this relation on X and Y and then joining back yields the original relation. However, if we project r on S, then the attribute A is projected out and thus the tuples s and t match on X ? Y ? S .Therefore,

?S ?X(r)  ?S ?Y(r)

contains the extraneous tuples of the form 111222444 and 444222111,which are not in ?S(r).