Content deleted Content added
No edit summary |
rm sig |
||
| (9 intermediate revisions by 8 users not shown) | |||
Line 7:
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.
The chase can be done by drawing a tableau (which is the same formalism used in [[tableau query]]). Suppose ''R'' has [[attribute (computing)|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 S<sub>''i''</sub>. Then, ''t<sub>i</sub>'' will agree with ''t'' if it is in S<sub>''i''</sub> and will have a unique value otherwise.
The chase process is [[confluence (rewriting system)|confluent]]. There exist implementations of the chase algorithm,<ref>[[Michael Benedikt (computer scientist)|Michael Benedikt]], [[George Konstantinidis]], [[Giansalvatore Mecca]], [[Boris Motik]], [[Paolo Papotti]], [[Donatello Santoro]], [[Efthymia Tsamoura]]: ''Benchmarking the Chase''. In Proc. of PODS, 2017.</ref> some of them are also open-source.<ref>{{cite web |url=https://github.com/donatellosantoro/Llunatic |title=The Llunatic Mapping and Cleaning Chase Engine|date=6 April 2021}}</ref>
==Example==
Let ''R''(''A'', ''B'', ''C'', ''D'') be a relation schema known to obey the set of functional dependencies ''F'' = {''A''→''B'', ''B''→''C'', ''CD→A''}. Suppose ''R'' is decomposed into three relation schemas S<sub>1</sub> = {''A'', ''D''}, S<sub>2</sub> = {''A'', ''C''} and S<sub>3</sub> = {''B'', ''C'', ''D''}. Determining whether this decomposition is lossless can be done by performing a chase as
The initial tableau for this decomposition is:
Line 25:
|}
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
<br />
To perform the chase test, first decompose all
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'').
<br>
First, apply ''A''→''B'' to the tableau.
Line 71 ⟶ 73:
* [[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. Pearson Prentice Hall, 2008.
* [[Michael Benedikt (computer scientist)|Michael Benedikt]], [[George Konstantinidis]], [[Giansalvatore Mecca]], [[Boris Motik]], [[Paolo Papotti]], [[Donatello Santoro]], [[Efthymia Tsamoura]]: ''Benchmarking the Chase''. In Proc. of PODS, 2017.
== Further reading ==
| |||