The Chase Test for Lossless Join - eg.bucknell.edu

Lecture 19aTheChase Test for Lossless Join
Lossless Decomposition
We say if a decomposition islosslessif the original relation can be recovered completely by natural joining the decomposed relations.Three important facts to remember:The natural join is associative. That is, the order of the relation join does not mater.AnytupletinRis surely in the joined decomposed relations.If we can prove anytuplet in joined relationR1u R2u … uRkis also inR, we have a 1-1 mapping betweenRand re-joined relation, thus alosslessdecomposition.
ChaseTest
Thechasetest is an organized way to see whether atupletin joined relationR1u R2u … uRkcan be proved using FDs also to be atupleinR.We will show through an example how the process works.
Notations
AssumeRhas attributesA, B, …We usea, b,… for the components oft.Forti, we use the same letter as in the components that are inSi, but we subscript the letter withiif the component is not ini.The example in next slide will clarify the notation.
Example
Suppose we have relationR(A,B,C,D)and FD’sAB, BC, CDA. Assumewehave decomposedRintorelations with sets of attributesS1={A,D},S2={A,C}, andS3={B,C,D}. Then the tableau (re-joined) for this decomposition looks as follows.
Note: 1. Attribute letters with subscript mean that they are arbitrary values.2. Attributes with subscripts are “free” values that eventually will be proved not.
Chasing0
Our goal is to prove those rows with subscripted attributes are really in originalR.We “chase” the tableau by applyingFDs repeatedly until the relation becomesR.In the next a few slides, we will see how the tableau evolves whenFDs are applied
Chase1
Because the first two rows agree on attribute A, they must also agree on attribute B by the FD {AB}, so the tableau evolves into
The red colored subscript indicates the change, in this case from b2 to b1.
Chase2
Because the first two rows now agree on attribute B, they must also agree on attribute C by the FD {BC}, thus c and c1 must be the same. So the tableau evolves into
The red colored subscript indicates the change, in this case c1 to c.
Chase3
We know {CDA}, checking row 1 and row 3, a and a3 must agree. So the tableau evolves into
The red colored subscript indicates the change, in this case a3 to a.
At this point, we see that last row becomes (a,b,c,d) which isthe original R. Other rows must agree as well.
10
Let’s revisit some early examples
{SSN}{Name,City}
This FD isbadbecause it isnotasuperkey, {SSN} can’t determine {PhoneNumber}
11
R is decomposed into R1 and R2
{SSN}{Name,City}
Now in BCNF!
This FD is nowgoodbecause it is the key
R can be recoveredby joining R1 and R2!