Abstrakt. Vi presenterar en algoritm för att bygga ett träd för att tillfredsställa en uppsättning av härstamning begränsningar på vanliga förfäder. Vi tillämpar sedan denna algoritm för att syntetisera en relationell algebra uttryck från en enkel tablå, ett problem som uppstår i teorin om relationella databaser. Nyckelord, trädalgoritmer, lägsta vanliga förfäder, relationsdatabaser, relationell algebra, tablåer, frågeoptimering, gå med i minimization 1. Ett problem med att upptäcka träd. I ett rotat träd, den lägsta gemensamma förfadern till två noder x och y, betecknad (x, y), är noden en som är en förfader till både x och y sådan att ingen riktig ättling till en är också en förfader till både x och y. Antag att vi får höra ett träd T har blad numrerade 1, 2,.., n, och vi ges en uppsättning begränsningar på de lägsta gemensamma förfäderna av vissa par av blad. I synnerhet, anta att begränsningarna är av formen (i, /) < (k, l) där /" och k 1, vilket innebär att den lägsta gemensamma förfadern till och j är en riktig ättling till den lägsta gemensamma förfadern till k och l. Observera att ordningen av och j i (i, j) och av k och i (k, l) är irrelevant. Kan vi från en uppsättning begränsningar i denna form rekonstruera T, eller avgöra att det inte finns något sådant träd? Exempel 1. Antag att vi får begränsningarna (1.1) (1, 2) < (1, 3), (3, 4) < (1, 5), (3, 5) < (2, 4). Ett möjligt träd T-konsonant med dessa begränsningar visas i bild. 1................................................................ Men om vi lägger till begränsningen (4, 5) < (1, 2), då kan det visas att inget träd kan samtidigt uppfylla alla dessa begränsningar. I detta dokument ger vi en effektiv algoritm för att lösa detta problem. Vi presenterar sedan en tillämpning av denna algoritm på problemet med att syntetisera en relationell algebra uttryck från en enkel tablå. 2. Utgångspunkten är följande: Hitta trädet. Den centrala tanken bakom lösningen är att bestämma för ett potentiellt träd T de uppsättningar blad som är ättlingar till varje barn av roten av T. Kalla dessa uppsättningar $ 1, $ 2,'", St. Vi kan anta r=> 2, eftersom om ett träd uppfyller en uppsättning * Mottagna av redaktörerna 10 juli 1979, och Det finns två villkor som dessa uppsättningar måste uppfylla för varje begränsning (i, ]) < (k, t). (1) och ] måste vara i samma uppsättning. Annars (i,/') är roten av T, och roten kan inte vara en riktig avkomling av (k, l). (2) Antingen k och är i olika uppsättningar, eller i,/', k och är alla tillsammans i en uppsättning. Annars (i, ]) kan inte vara en riktig ättling till (k, l). Vi skall också visa att villkoren 1 och 2 är tillräckliga. Således, om vi kan dela upp noderna i två eller flera uppsättningar tillfredsställande (1) och (2), och om vi kan rekursivt bygga träd för varje uppsättning, då ett träd existerar; annars, man gör inte. Med tanke på en uppsättning begränsningar C, definierar vi en partition rrc på bladen 1, 2,..., n använder följande regler" (2) används. Om vi lägger till (1.1) begränsningen (4, 5) < (1, 2), för att få uppsättningen (1, 2) < (1, 3), (3, 4) < (1, 5), (3, 5) < (2, 4), (4, 5) < (1, 2), sedan genom regel (2) de två blocken måste slås samman, vilket ger en trivial partition. Eftersom ett nödvändigt villkor för ett träds existens är att rrc har mer än ett block, kan vi omedelbart dra slutsatsen att denna nya uppsättning begränsningar inte uppfylls av något träd. På bild. 2 vi presenterar en rekursiv algoritm för att bygga ett träd T uppfyller en uppsättning begränsningar C på en nontomy uppsättning noder S. Det returnerar nullträdet om inget träd finns. Grundidén är att beräkna partitionen rrc, kontrollera att den har minst två block $1, $2, ', &, r -> 2, och konstruera uppsättningarna av begränsningar C,,, 1 _- < rn _ <-r, sådan att C, är C begränsad till de begränsningar som endast involverar medlemmar av S. THEOREM 1. Om BUILD (S, C) returnerar en icke-null träd T, då T uppfyller begränsningen uppsättning C. Bevis. Vi fortsätter genom induktion på storleken av S. Grunden, en nod, är trivial. Antag då att teorem är sant för alla uppsättningar mindre än S. Eftersom varje rekursiv anspelning av BUILD tillämpas på en uppsättning av strikt mindre storlek än S, kan vi anta att alla rekursiva anrop av BUILD lyda den induktiva hypotesen. Vi måste visa att alla begränsningar i C är uppfyllda av T. Följaktligen, låt (1) tillämpas på en begränsning (i, f) < (k, l) orsakar blocken innehåller och j, säger B1 och B2, att slås samman. Genom induktion, alla noder i B1 och B2 är inneslutna, respektive i underträden rotade vid n och nz, två barn av roten. Om n n2, då (i, j) är roten till T. Men då ingen begränsning av formen (i, ) < (k, l) kan tillfredsställas av T, bryter mot vårt antagande att T nöjda C. Vi måste därför ha rtx n: och alla noder i B tO Bz är ättlingar till samma barn av roten. har bara ett block, eller BUILD (S, C,) returnerar nullträdet för några m. I det första fallet följer av Lemma 1 att roten av T bara har ett barn. Men sedan T', som är T med roten borttagen, ger ett mindre motexempel till teorem. I det andra fallet, där BUILD (S, C,) returnerar nullträdet, låt S, inneslutas i underträdet rotat på barn n av roten av T. Definiera T' att vara underträdet av T med rot n, efter att ha tagit bort alla blad inte i $, och alla inre noder ingen av vars ättling blad är i $,. Då T' uppfyller C,, är T' mindre än T, men BUILD (S, C,) inte konstruerar ett nonnull träd. Således T tillsammans med C var inte det minsta motexempel till teorem, som man trodde. Eftersom en enda nod inte kan vara ett motexempel på teorem, drar vi slutsatsen att teorem inte har något minsta motexempel. Eftersom ett motexempel, om man existerar, är ändligt, kan det inte finnas något motexempel alls, från vilket vi avslutar teoremet. Exempel 3. Antag att vi får begränsningarna (1,3) <(2,5) (1, 4) < (3, 7) (2, 6) < (4, 8) (3, 4) < (2, 6) (4, 5) < (1, 9) (7, 8) < (2, 10) (7, 8) < (7, 10) (8,10) < (5, 9). Regel (1) funktion n, antalet begränsningar, och f, en funktion som anger den tid som krävs för att partitionera en uppsättning begränsningar. Vi ska se att användningen av den naiva partitioneringsalgoritmen leder till en O(n3) implementering av BUILD. Genom att använda en mer sofistikerad partitioneringsalgoritm kan den totala körtiden minskas till O(n 2 log n). Dessutom, genom att införa begränsningen att alla begränsningar är av formen (i, ]) < (i, k), kan vi ytterligare minska körtiden till O(n2). I avsnitt 4 i detta dokument presenteras en databasapplikation där problem med denna begränsade form uppstår på ett naturligt sätt. LEMMA 2 ).............................................................................................................. Låt f(n) vara den tid som behövs för att partitionera en uppsättning n begränsningar som omfattas av reglerna (1) och (2) i föregående avsnitt. Iff är monotont nondecreasing, då den tid som förbrukas av BUILD när den tillämpas på en uppsättning n begränsningar är O(nf(n)). Bevis. Den värsta drifttiden inträffar när algoritmen lyckas syntetisera ett icke-nullträd, så vi ska begränsa vår uppmärksamhet till att analysera detta fall. Vi kommer att fortsätta genom att tilldela varje knutpunkt i trädet en kostnad och sammanfatta kostnaderna. Eftersom den högsta nivån anrop på BUILD innebär n begränsningar, som var och en kan införa som mest 4n blad i trädet, har det syntetiserade trädet högst 4n blad. (Lämnar som inte nämns i någon begränsning kan göras barn av roten av det slutliga trädet.) Eftersom grenningsfaktorn vid varje intern nod är minst 2, kan antalet interna noder inte överstiga 4n 1. Vid varje intern nod, BUILD partitioner någon delmängd av de ursprungliga begränsningarna och sedan spenderar en konstant mängd tid (exklusivt rekursiva samtal) bearbetning varje block av partitionen. Eftersom f är monoton, f(n) är säkert en övre gräns på kostnaden för att utföra varje partition. Dessutom, eftersom f måste växa åtminstone linjärt med sitt argument, kan vi bortse från kostnaden för att fördela begränsningarna över blocken i partitionen jämfört med f(n) och ladda varje intern nod O (f(n)) enheter av tiden. Således den tid som debiteras alla interna noder är O((4n 1)f(n)) O(nf(n)). Eftersom BUILD tillbringar en konstant mängd tid vid varje blad, bidraget från bladen till körtiden är O(n) för totalt över alla noder av O(nf(n)). 71 Problemet med att producera en snabb implementering av BUILD minskar därmed till en av att producera en snabb partitionering algoritm. Låt oss först ta itu med detta problem i det speciella fall som nämndes tidigare. Bevis. Genom Lemma 2 räcker det att visa hur man partitionerar en uppsättning n begränsningar i O(n) tid. När alla begränsningar är av formen (i, ]) < (i, k), behöver regel (2) i partitionen som konstruerar algoritm av 2 aldrig tillämpas explicit. För att se detta, anta att och k är i samma block. Enligt regel (1) och ] måste också vara i samma block, och därmed genom transitivitet, i, ], och k är alla i samma block. Det räcker därför med att tillämpa regeln (1) på egen hand. Om vi tar varje blad som visas i en eller flera begränsningar att vara en nod, och varje begränsning (i, ]) < (i, k) Bevis. Genom Lemma 2 räcker det att visa hur man partitionerar en uppsättning n begränsningar i O(n log n) tid. Block av partitionen kommer att underhållas med hjälp av en uppsättning sammanslagningsalgoritm som stöder följande operationer" (1) Eftersom ett element i, hitta den uppsättning som för närvarande tillhör. (2) Med tanke på två uppsättningar, slå ihop dem och tilldela dem ett gemensamt namn. Bilda. 4........................................... Innan du fortsätter, observera att varje begränsning ger upphov till ett kommando, som omedelbart placeras på O i steg (2), och två kopior av en implikation, säger p q =), r s, som placeras på olika listor. På de flesta av dessa kopior kommer så småningom kommandot r s att placeras på Q, och detta kommer att hända när en sammanslagningsoperation först orsakar p och q att bli element i samma block. Det totala antalet kommandon är alltså högst 2n (n i steg (2) och n i steg (3)). Den tid som tillbringas i steg (1) och (2) är helt klart O(n). Den tid som används av det inre för steg (3) är O(n log n) eftersom varje kopia av en implikation endast beaktas i denna slinga när den flyttas från en kortare till en längre lista. Eftersom inte mer än n-1 sammanslagningar kan utföras, kan ingen implikation flyttas mer än logg: n-1 gånger. Det arbete som utförs i den inre för öglan är alltså O(n log n). Den tid som tillbringas i resten av steg (3), exklusive den inre för loop, används för att ta bort högst 2n kommandon från Q, gör som mest O(n) fynd och jämförelser, och utför som mest n 1 fusionerar. Detta kräver helt klart O(n log n) tid, och så den totala tid som används av algoritmen i O(n log n). 71 Utökningar. Den trädsyntesalgoritm av 2 och 3 kan utökas för att hantera en mer allmän uppsättning begränsningar än de som hittills ansetts. Mer specifikt kan vi hantera varje samling av begränsningar av följande typer" (1) (i, j) < (k, l), (2) (i,/') _- < (k, l), (3) (i, j)= (k, l) (4) (i, j) är jämförbar med (k, l), (5) (i, j) är ojämförbar med (k, l). I ovanstående begränsningar, två noder av ett träd sägs vara jämförbara om den ena är förfader till den andra, och ojämförligt annars. Liksom tidigare finns det en uppsättning regler för att dela upp trädens blad i separata uppsättningar så att bladen i varje uppsättning är ättlingar till ett annat barn av roten. Den lämpliga uppsättningen regler är" (1) Om (i, ]) < (k, l) är en begränsning, då och/" är i samma block av rc. (6) Om (i, ]) är ojämförligt med (k, l) är en begränsning, då är i samma block som ], och k är i samma block som I. (7) Det finns inga två blad i samma block av 7rc om de inte följer från (1) till (6). Dessa regler kan visa sig vara både nödvändiga och tillräckliga villkor för att bygga ett träd som följer en uppsättning begränsningar (om sådana finns) enligt förfarandet BUILD. Varje regel innebär att lägga ett fall till var och en av Theorem 1 och Lemma 1. En enkel ändring av partitioneringsalgoritmen i 3 gör att vi kan hantera denna bredare klass av begränsningar utan att öka den körtid som påstås i Theorem 3. För ytterligare generalisering av detta problem, se [6]. I [3] visades att värdet av en SPJ-uttryck kan representeras i form av en tvådimensionell matris som kallas tablå. En förening-minimering förfarande för SPJ-uttryck beskrevs i vilken en tablå konstrueras från en given SPJexpression E. Tablån omvandlas sedan till en likvärdig minsta rad tablå. Från denna minsta rad tabell kan vi sedan konstruera en SPJ-uttryck som har de minsta sammanfogningar av alla relationsuttryck som motsvarar det ursprungliga uttrycket E. Tyvärr relation är bara "nuvarande värde" av ett relationsschema. Förhållandet sägs vara definierat på uppsättningen attribut i relationssystemet. Operatörerna väljer, projekterar och går med definieras på följande sätt. (1) Välj. Låt r vara en relation på en uppsättning attribut X, A ett attribut i X, och c ett värde från domänen A. Därefter är markeringen A c applicerad på r, skriftlig O'A= (r), den delmängd av r som har värde c för egenskap A. (2) Projekt. Låt r vara en relation på en uppsättning attribut X. Låt Y vara en delmängd av X. Vi definierar y(r), projektionen av r på Y, att vara det förhållande som erhålls genom att ta bort alla komponenter i tuples av r som inte tillhör Y och ta bort dubbla tuples. Representation oI SPJ-uttryck av tablåer. Med tanke på ett SPJ-uttryck E, kan vi konstruera en tablå T för att representera uttrycket på följande sätt. Konstruktionen fortsätter induktivt på formen av E. (1) Om E är en enda relation system R, då tablå T för E har en rad och en sammanfattning sådan att i) Om A är ett attribut i R, sedan i kolumnen för A tablå T har samma
Särskilt Aho et al. REF presenterade en algoritm som, med tanke på en uppsättning ordinala begränsningar i förväg, finner ett träd som överensstämmer med begränsningarna (eller bestämmer att ingen finns).
Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}