Content deleted Content added
No edit summary |
m WP:CHECKWIKI error fixes using AWB (11708) |
||
Line 1:
'''The Chase''' is a simple [[fixed-point iteration|fixed-point algorithm]] testing and enforcing implication of data dependencies in [[database|database systems]]. It plays important roles in [[database theory]] as well as in practice.
It is used, directly or indirectly, on an everyday basis by people who design databases, and it is used in commercial systems to reason about the consistency and correctness of a data design.{{
The Chase has its origins in two seminal papers, one by [[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> and the other by [[David Maier]], [[Alberto O. Mendelzon]], and [[Yehoshua Sagiv]].<ref>
[[David Maier]], [[Alberto O. Mendelzon]], and [[Yehoshua Sagiv]]: "Testing Implications of Data Dependencies". ACM Trans. Datab. Syst. 4(4):455-469, 1979.</ref>
In its simplest application the chase is used for testing whether the [[projection (relational algebra)|projection]] of a [[relation schema]] constrained by some [[functional dependency|functional dependencies]] onto a given decomposition can be [[join dependency|recovered by rejoining the projections]]. 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 dependencies (FD). If tuples in ''R'' are 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.
Line 37:
|-
| ''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 ''c''. Therefore, the first row changes to (''a'', ''b<sub>1</sub>'', ''c'', ''d''). Then the resulting tableau is:
Line 48:
|-
| ''a<sub>3</sub>'' || ''b'' || ''c'' || ''d''
|}
Now consider ''CD''→''A''. The first row has an unsubscripted ''c'' and an unsubscripted ''d'', 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<sub>3</sub>'' in the third row to ''a''. The resulting tableau is:
| |||