Chase (algoritm)

Jakten är en enkel fastpunktsalgoritm som testar och upprätthåller implikationen av databeroende i databassystem . Det spelar viktiga roller i databasteorin såväl som i praktiken. Det används, direkt eller indirekt, dagligen av personer som designar databaser, och det används i kommersiella system för att resonera kring konsistensen och riktigheten i en datadesign. Nya tillämpningar av jakten inom metadatahantering och datautbyte upptäcks fortfarande.

Jakten har sitt ursprung i två framstående tidningar från 1979, en av Alfred V. Aho , Catriel Beeri och Jeffrey D. Ullman och den andra av David Maier , Alberto O. Mendelzon och Yehoshua Sagiv .

I sin enklaste tillämpning används chase för att testa om projektionen av ett relationsschema begränsat av vissa funktionella beroenden på en given nedbrytning kan återställas genom att återförena projektionerna . Låt t vara en tuppel i $\pi _{S_{1}}(R)\bowtie \pi _{S_{2}}(R)\bowtie ...\bowtie \pi _{S_{k }}(R)$ där R är en relation och F är en uppsättning funktionella beroenden (FD). Om tupler i R representeras som t ₁ , ..., t _k , bör sammanfogningen av projektionerna för varje t _i överensstämma med t på $\pi _{S_{i}}( R)$ där i = 1, 2, ..., k . Om t _i inte är på ${\displaystyle \pi _{S_{i}}(R)} ,$ är värdet okänt.

Jakten kan göras genom att rita en tablå (vilket är samma formalism som används i tablåfrågan). Antag att R har attributen A, B, ... och komponenter i t är a, b, ... . För t _i använd samma bokstav som t i komponenterna som finns i S _i men skriv bokstaven med i om komponenten inte är i S _i . Då t _i att hålla med t om det är i S _i och kommer att ha ett unikt värde annars.

Jaktprocessen är sammanflytande . Det finns implementeringar av chase-algoritmen, några av dem är också öppen källkod.

Exempel

Låt R ( A , B , C , D ) vara ett relationsschema känt för att lyda uppsättningen funktionella beroenden F = { A → B , B → C , CD→A }. Antag att R är uppdelad i tre relationsscheman S ₁ = { A , D }, S ₂ = { A , C } och S ₃ = { B , C , D }. Att avgöra om denna nedbrytning är förlustfri kan göras genom att utföra en jakt som visas nedan.

Den första tablån för denna nedbrytning är:

A	B	C	D
a	b 1	c 1	d
a	b 2	c	d 2
en 3	b	c	d

Den första raden representerar _S1 . Komponenterna för attribut A och D är otecknade och de för attribut B och C är tecknade med i = 1. Den andra och tredje raden fylls på samma sätt med S ₂ respektive S ₃ .

Målet för detta test är att använda det givna F för att bevisa att t = ( a , b , c , d ) verkligen är i R. För att göra det kan tablån jagas genom att använda FD:erna i F för att likställa symboler i tablån. En sista tablå med en rad som är samma som t antyder att varje tuppel t i sammanfogningen av projektionerna faktiskt är en tupel av R . För att utföra jakttestet, först dekomponera alla FD:er i F så att varje FD har ett enda attribut på höger sida av "pilen". (I det här exemplet F oförändrat eftersom alla dess FD redan har ett enda attribut på höger sida: F = { A → B , B → C , CD → A }.)

ha en rad som är exakt samma som t = ( a , b , c , d ) . Om båda har sin egen prenumeration, ändra endera till att vara den andra. För att undvika förvirring bör dock alla händelser ändras. Applicera först A → B på tablåen. Den första raden är ( a , b ₁ , c ₁ , d ) där a är avregistrerad och b ₁ är prenumererad med 1. Jämför den första raden med den andra, ändra b ₂ till b ₁ . Eftersom den tredje raden har en 3 _{: a förblir} b i den tredje raden densamma. Den resulterande tablån är:

A	B	C	D
a	b 1	c 1	d
a	b 1	c	d 2
en 3	b	c	d

Tänk sedan på B → C . Både första och andra raden har b ₁ och lägg märke till att den andra raden har ett avregistrerat c . Därför ändras den första raden till ( a , b ₁ , c , d ). Då är den resulterande tablån:

A	B	C	D
a	b 1	c	d
a	b 1	c	d 2
en 3	b	c	d

Tänk nu på CD → A . Den första raden har ett otecknat c och ett ej prenumererat d , vilket är samma som i tredje raden. Det betyder att A-värdet för rad ett och tre måste vara detsamma också. Ändra därför en _3: a i den tredje raden till en . Den resulterande tablån är:

A	B	C	D
a	b 1	c	d
a	b 1	c	d 2
a	b	c	d

Lägg nu märke till att den tredje raden är ( a , b , c , d ) vilket är samma som t . Därför är detta den sista tablån för jakttestet med givna R och F . Följaktligen, närhelst R projiceras på Si , _S2 och S3 _{och återförenas ,} är resultatet i R. Speciellt är den resulterande tupeln densamma som tupeln av R som projiceras på { B , C , D }.

• Serge Abiteboul , Richard B. Hull, Victor Vianu : Foundations of Databases. Addison-Wesley, 1995.
• AV Aho , C. Beeri och JD Ullman : Theory of Joins in Relational Databases . ACM Transactions on Database Systems 4(3): 297-314, 1979.
• JD Ullman : Principer för databas- och kunskapsbassystem, volym I. Computer Science Press, New York, 1988.
• JD Ullman , J. Widom : En första kurs i databassystem (3:e upplagan). s. 96–99. Pearson Prentice Hall, 2008.
• Michael Benedikt, George Konstantinidis, Giansalvatore Mecca, Boris Motik, Paolo Papotti, Donatello Santoro, Efthymia Tsamoura: Benchmarking the Chase . I Proc. av PODS, 2017.

Vidare läsning

•   Sergio Greco; Francesca Spezzano; Cristian Molinaro (2012). Ofullständiga data och databeroenden i relationsdatabaser . Morgan & Claypool Publishers. ISBN 978-1-60845-926-1 .