Chase (algorithm): Difference between revisions

Revision as of 22:29, 3 March 2011

Revision as of 02:40, 31 March 2011

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 (relational algebra) | 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 (database) | relation]] and ''F'' is a set of [[functional dependency | functional dependencies]] (FD). If tuples in ''R'' are represented as ''t₁, ..., t_k'', the join of the projections of each ''t_i'' should agree with ''t'' on <math>\pi_{S_i}(R)</math> where ''i'' = 1, 2, ..., ''k''. If ''t_i'' 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 [[attribute (computing) | attributes]] ''A, B, ...'' and components of ''t'' are ''a, b, ...''. For ''t_i'' use the same letter as ''t'' in the components that are in S_''i'' but subscript the letter with ''i'' if the component is not in ''i''. Then, ''t_i'' will agree with ''t'' if it is in S_''i'' and will have a unique value otherwise.

==Example==

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 on the right hand side of the "arrow". ''F'' remains unchanged because all of it'sits FD's already has a single attribute on the right hand side. ''F'' = {''A''→''B'', ''B''→''C'', ''CD''→''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 63:

<references/>

* [[Serge Abiteboul]], [[Richard B. Hull]], [[Victor Vianu]]: Foundations of Databases. Addison-Wesley, 1995.

* [[Alfred Aho | A. V. Aho]], C. Beeri, and [[Jeffrey Ullman | J. D. Ullman]]: ''The Theory of Joins in Relational Databases''. ACM Transactions on Database Systems 4(3): 297-314, 1979.

* [[Jeffrey Ullman | J. D. Ullman]]: ''Principles of Database and Knowledge-Base Systems, Volume I''. Computer Science Press, New York, 1988.

* [[Jeffrey Ullman | J. D. Ullman]], [[Jennifer Widom | J. Widom]]: ''A First Course in Database Systems'' (3rd ed.). pp.96-99&nbsp;96–99. Pearson Prentice Hall, 2008.

{{database-stub}}

{{DEFAULTSORT:Chase (Algorithm)}}

[[Category:Database theory]]

[[Category:Database algorithms]]