Dependency Theory

Does anyone know of a good website, book or any other resources that would explain dependency theory well? I am stuck on a similar question to the one shown bel开发者_JAVA百科ow:

Given

R   < A = {P,Q,R,S,T,U,Y },


gamma = {Y->S   …(1)
       Q->ST….(2)  

U-> Y……(3)
       S->R  …...(4)

RS->T…….(5) }>.  

RTP U->T  holds

Answer is:

U -> Y -> S -> RS -> T
aug (4) by S  S->R

---

I think you'll need to search for functional dependency instead of dependency theory. Wikipedia has an introductory article on functional dependency. The expression "Y->S" means

• Y determines S, or
• if you know one value for 'Y', you know one value for 'S' (instead of two or three or seven values for 'S'), or
• if two tuples have the same value for 'Y', they'll also have the same value for 'S'

I'm not familiar with all the notation you posted. But I think you're asked to begin with a relation R and a set of functional dependencies gamma numbered 1 to 4 for reference.

Relation R = {P,Q,R,S,T,U,Y }

FD gamma = {Y->S   (1)
            Q->ST  (2)  
            U-> Y  (3)
            S->R   (4) }

This appears to be the "setup" for several problems. You're then asked to assume this additional functional dependency.

RS->T  (5)

Based on the setup and on that additional FD, you're supposed to prove that the functional dependency U->T holds. The lecturer's answer is "U -> Y -> S -> RS -> T", which I think is the chain of inferences the lecturer wants you to follow. You're given U->Y and Y->S to start with, so here's how that specific chain of inference goes.

1. U->Y and Y->S, therefore U->S. (transitivity, Lecturer's U->Y->S)

2. S->R, therefore S->RS. (augmentation, an intermediate step)

3. U->S and S->RS, therefore U->RS. (transitivity, Lecturer's U->Y->S->RS)

4. U->RS and RS->T, therefore U->T. (transitivity, Lecturer's U->Y->S->RS->T)