Content deleted Content added
No edit summary |
Minibear898 (talk | contribs) No edit summary |
||
Line 6:
[[Alfred V. Aho]], [[Catriel Beeri]], and [[Jeffrey D. Ullman]]<ref>[[Alfred V. Aho]], [[Catriel Beeri]], and [[Jeffrey D. Ullman]]: "The Theory of Joins in Relational Databases", ACM Trans. Datab. Syst. 4(3):297-314, 1979.</ref>.
'''Chase test''' is for testing whether the projection of a relation onto any decomposition can be recovered by rejoining.
Let ''t'' be a tuple in <math>\pi_{S_1}(R) \bowtie \pi_{S_2}(R) \bowtie ... \bowtie \pi_{S_k}(R)</math> where ''R'' is a relation and ''F'' is a set of [[functional dependency | functional dependencies]] (FD). If tuples in ''R'' is represented as ''t<sub>1</sub>, ..., t<sub>k</sub>'', the join of the projections of each ''t<sub>i</sub>'' should agree with ''t'' on <math>\pi_{S_i}(R)</math> where ''i'' = 1, 2, ..., ''k''. If ''t<sub>i</sub>'' is not on <math>\pi_{S_i}(R)</math>, the value is unknown.
Chase test can be done by drawing a tableau. Suppose ''R'' has attributes ''A, B, ...'' and components of ''t'' are ''a, b, ...''. For ''t<sub>i</sub>'' use the same letter as ''t'' in the components that are in S<sub>''i''</sub> but subscript the letter with ''i'' if the component is not in ''i''. Then, ''t<sub>i</sub>'' will agree with ''t'' if it is in S<sub>''i''</sub> and will have a unique value otherwise.
==Example==
Suppose ''R''(''A'', ''B'', ''C'', ''D'') which are decomposed into relations with attributes S<sub>1</sub> = {''A'', ''D''}, S<sub>2</sub> = {''A'', ''C''} and S<sub>3</sub> = {''B'', ''C'', ''D''} and ''F'' = {''A''→''B'', ''B''→''C'', ''CD→A''} is given. The initial tableau for this decomposition is:
{| border="1" cellspacing="0" cellpadding="5" align="center"
! ''A'' !! ''B'' !! ''C'' !! ''D''
|-
| ''a'' || ''b<sub>1</sub>'' || ''c<sub>1</sub>'' || ''d''
|-
| ''a'' || ''b<sub>2</sub>'' || ''c'' || ''d<sub>2</sub>''
|-
| ''a<sub>3</sub>'' || ''b'' || ''c'' || ''d''
|}
The first row represents S<sub>1</sub>. 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<sub>2</sub> and S<sub>3</sub> 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, ''F'' = {''A''→''B'', ''B''→''C'', ''C''→''A'', ''D''→''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<sub>1</sub>'', ''c<sub>1</sub>'', ''d'') where ''a'' is unsubscripted and ''b<sub>1</sub>'' is subscripted with 1. Comparing the first row with the second one, change ''b<sub>2</sub>'' to ''b<sub>1</sub>''. Since the third row has ''a<sub>3</sub>'', ''b'' in the third row stays the same. The resulting tableau is:
{| border="1" cellspacing="0" cellpadding="5" align="center"
! ''A'' !! ''B'' !! ''C'' !! ''D''
|-
| ''a'' || ''b<sub>1</sub>'' || ''c<sub>1</sub>'' || ''d''
|-
| ''a'' || ''b<sub>1</sub>'' || ''c'' || ''d<sub>2</sub>''
|-
| ''a<sub>3</sub>'' || ''b'' || ''c'' || ''d''
|}
Then consider ''B''→''C''. Both first and second rows have ''b<sub>1</sub>'' and notice that the second row has an unsubscripted ''b''. Therefore, the first row changes to (''a'', ''b<sub>1</sub>'', ''c'', ''d''). Then the resulting tableau is:
{| border="1" cellspacing="0" cellpadding="5" align="center"
! ''A'' !! ''B'' !! ''C'' !! ''D''
|-
| ''a'' || ''b<sub>1</sub>'' || ''c'' || ''d''
|-
| ''a'' || ''b<sub>1</sub>'' || ''c'' || ''d<sub>2</sub>''
|-
| ''a<sub>3</sub>'' || ''b'' || ''c'' || ''d''
|}
Now consider ''C''→''A''. The first row has an unsubscripted ''c'' with an unsubscripted ''a''. Hence, change ''a<sub>3</sub>'' in the third row to ''a''. The resulting tableau is:
{| border="1" cellspacing="0" cellpadding="5" align="center"
! ''A'' !! ''B'' !! ''C'' !! ''D''
|-
| ''a'' || ''b<sub>1</sub>'' || ''c'' || ''d''
|-
| ''a'' || ''b<sub>1</sub>'' || ''c'' || ''d<sub>2</sub>''
|-
| ''a'' || ''b'' || ''c'' || ''d''
|}
At this point, notice that the third row is (''a'', ''b'', ''c'', ''d'') which is the same as ''t''. Therefore, this is the final tableau for the chase test with given ''R'' and ''F''. Hence, whenever ''R'' is projected onto S<sub>1</sub>, S<sub>2</sub> and S<sub>3</sub> and rejoined, the result is in R. Particularly, the resulting tuple is the same as the tuple of ''R'' that is projected onto {''B'', ''C'', ''D''}.
== References ==
<references/>
* [[Serge Abiteboul]], [[Richard B. Hull]], [[Victor Vianu]]: Foundations of Databases. Addison-Wesley, 1995.
* A. V. Aho, C. Beeri, and J. D. Ullman: ''The theory of joins in relational databases''. ACM Transactions on Database Systems 4(3): 297-314, 1979.
* J. D. Ullman: ''Principles of Database and Knowledge-Base Systems, Volume I''. Computer Science Press, New York, 1988.
* J. D. Ullman; J. Widom: ''A First Course in Database Systems'' (3rd ed.). pp.96-99. Pearson Prentice Hall, 2008.
{{database-stub}}
| |||