2:Inference Test Use the given FD's to infer that these tuples must also agree in certain other attributes. If B is one of these attributes,then Y->B is true. Otherwise,the two tuples,with any forced equalities,form a two-tuple relation that proves y- B does not follow from the given FD's. 16
16 2: Inference Test z Use the given FD’s to infer that these tuples must also agree in certain other attributes. – If B is one of these attributes, then Y -> B is true. – Otherwise, the two tuples, with any forced equalities, form a two-tuple relation that proves Y - > B does not follow from the given FD’s
2:Inference Test example ●R(A,B,C)with FD's: A→B,B→C Inference steps: ●To prove A→C? 1)Assume two tuples that agree on A A B C 2)Because A→B, b1 b1=b2 a c1 3)Because B→C a b2 c2 C1=C2 17
17 2: Inference Test : example z R(A,B,C) with FD’s: AÆB, BÆC z To prove AÆC? ABC a b1 c1 a b2 c2 Inference steps: 1) Assume two tuples that agree on A 2) Because AÆB, b1=b2 3) Because BÆC c1=c2
Inference rules ●Reflexivity: If [B B2...Bm)s[A1,A2....An}then A1,A2.An→B1B2Bm called trivial FD's ●Augmentation: If A1A2....An>B B2...Bm then, A1,A2.An C1 C2.Ck>B B2..Bm C1,C2.CK Transitivity: IfA1,A2,.An→BB2Bm,andB,B2Bm→C1,C2Ck then,A1,A2,...An>C1.C2..Ck 18
18 Inference rules z Reflexivity: If {B1B2…Bm} ⊆ {A1,A2,…An} then A1,A2,…An Æ B1B2…Bm called trivial FD’s z Augmentation: If A1,A2,…An Æ B1B2…Bm then, A1,A2,…An C1,C2..Ck Æ B1B2…Bm C1,C2..Ck z Transitivity: If A1,A2,…An Æ B1B2…Bm,and B1B2…Bm Æ C1,C2..Ck then, A1,A2,…An Æ C1,C2..Ck
3:Closure Test An easier way to test is to compute the closure of Y,denoted Y+. ●Basis:Y+=Y. Induction:Look for an FD's left side X that is a subset of the current Y+.If the FD is X-> A.add A to Y+. Y+ End:when Y+can not be changed. X- A new Yt 19
19 3: Closure Test z An easier way to test is to compute the closure of Y, denoted Y +. z Basis: Y + = Y. z Induction: Look for an FD’s left side X that is a subset of the current Y +. If the FD is X -> A, add A to Y +. z End: when Y+ can not be changed. Y+ new Y+ X A
3:Closure Test:example R(A,B,C)with FD's:A→B,B→C ● To prove A→C? Closure and Keys: if the closure of X ● Calculating steps for A+: is all attributes of a relation,then X is 1.A+=A a key /superkey. 2.A+=A,B 3.A+=A,B,C A>C 20
20 3: Closure Test: example z R(A,B,C) with FD’s: AÆB, BÆC z To prove AÆC? z Calculating steps for A+ : 1. A+ = A 2. A+ = A, B 3. A+ = A, B, C AÆC Closure and Keys: if the closure of X is all attributes of a relation, then X is a key /superkey