Chase (algorithm): Difference between revisions

Revision as of 16:11, 18 June 2019

Latest revision as of 17:34, 26 September 2021

(6 intermediate revisions by 5 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₁, ..., 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.

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_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 S_''i''. Then, ''t_i'' will agree with ''t'' if it is in S_''i'' 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==

Line 25:

|}

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’sFDs in ''F'' to equate symbols in the tableau. FinalA 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''.

<br />

To perform the chase test, first decompose all FD’sFDs in ''F'' so each FD has a single attribute on the right hand side of the "arrow". (In this example, ''F'' remains unchanged because all of its FD'sFDs already hashave 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, ifIf both have their own subscript, change either to be the other. However, to avoid confusion, all of the occurrences should be changed.

<br>

First, apply ''A''→''B'' to the tableau.