Chase (algorithm): Difference between revisions

Revision as of 18:30, 17 February 2011

Revision as of 22:29, 3 March 2011

Line 24:

The first row represents S₁. The components for attributes ''A'' and ''D'' are unsubscripted and those for attributes ''B'' and ''C'' are subscripted with ''i'' = 1. The second and third rows are filled in the same manner with S₂ and S₃ respectively.

The goal for this test is to use the given ''F'' to prove that ''t'' = (''a'', ''b'', ''c'', ''d'') is really in ''R''. To do so, the tableau can be chased by applying the FD’s in ''F'' to equate symbols in the tableau. Final tableau with a row that is the same as ''t'' implies that any tuple ''t'' in the join of the projections is actually a tuple of ''R''.

To perform the chase test, first decompose all FD’s in ''F'' so each FD has a single attribute. Then,on the right hand side of the "arrow". ''F'' =remains {unchanged because all of it's FD'As already has a single attribute on the right hand side. ''→''BF'', = {''BA''→''CB'', ''CB''→''AC'', ''DCD''→''A''}.

When equating two symbols, if one of them is unsubscripted, make the other be the same so that the final tableau can have a row that is exactly the same as ''t'' = (''a'', ''b'', ''c'', ''d''). Also, if both have their own subscript, change either to be the other. However, to avoid confusion, all of the occurrences should be changed.

First, apply ''A''→''B'' to the tableau. The first row is (''a'', ''b₁'', ''c₁'', ''d'') where ''a'' is unsubscripted and ''b₁'' is subscripted with 1. Comparing the first row with the second one, change ''b₂'' to ''b₁''. Since the third row has ''a₃'', ''b'' in the third row stays the same. The resulting tableau is:

Line 48:

|}

Now consider ''CCD''→''A''. The first row has an unsubscripted ''c'' withand an unsubscripted ''ad'', which is the same as in third row. This means that the A value for row one and three must be the same as well. Hence, change ''a₃'' in the third row to ''a''. The resulting tableau is:

{| border="1" cellspacing="0" cellpadding="5" align="center"

! ''A'' !! ''B'' !! ''C'' !! ''D''