Chase (algorithm): Difference between revisions

Revision as of 16:50, 6 March 2020

Latest revision as of 17:34, 26 September 2021

(4 intermediate revisions by 4 users not shown)

Line 9:

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 FDs already have 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.