Effektiv anslutningsbehandling är en av de mest grundläggande och välstuderade uppgifterna inom databasforskning. I detta arbete undersöker vi algoritmer för naturliga gå frågor över många relationer och beskriver en ny algoritm för att behandla dessa frågor optimalt i termer av värsta fall data komplexitet. Vårt resultat bygger på den senaste tidens arbete av Atserias, Grohe och Marx, som gav gränser för storleken på en naturlig föreningsfråga när det gäller storleken på de enskilda relationerna i frågans helhet. Dessa gränser är dock inte konstruktiva: de förlitar sig på Shearers entropiskillnader, som är informationsteoretiska. Således, de tidigare resultaten lämnar öppen frågan om det finns algoritmer vars drifttider uppnå dessa optimala gränser. Ett svar på denna fråga kan vara intressant att databas praxis, som vi visar i denna artikel att alla projekt-join stil planer, såsom de som vanligtvis används i en relationell databas ledningssystem, är asymptotiskt långsammare än den optimala för vissa frågor. Vi presenterar en algoritm vars runtime är värsta fall optimal för alla naturliga gå frågor. Vårt resultat kan vara av oberoende intresse, eftersom vår algoritm också ger ett konstruktivt bevis på den allmänna bråkdelstäcke som är bunden av Atserias, Grohe och Marx utan att använda Shearers ojämlikhet. Denna gräns innebär två berömda ojämlikheter i geometri: Loomis-Whitney ojämlikhet och dess generalisering, Bollobás-Thomason ojämlikhet. Därför bevisar våra resultat algoritmiskt dessa ojämlikheter också. Slutligen diskuterar vi hur vår algoritm kan användas för att utvärdera fullständiga konjunktiva frågor optimalt, för att beräkna en avslappnad uppfattning om anslutningar och för att optimalt (i värsta fall) räkna alla inducerade kopior av en fast subgraf inuti en given stor graf. Ytterligare nyckelord och fraser: Gå med i algoritmer, bråktäcke bundna, Loomis-Whitney ojämlikhet, Bollobás-Thomason ojämlikhet En preliminär version av denna artikel presenterades på PODS'12 som referens [62]. Vi tackar Georg Gottlob för att ha skickat oss en fullständig version av hans arbete [30]. Vi tackar XuanLong Nguyen för att ha introducerat oss till Loomis-Whitney ojämlikhet. Vi tackar Dung Nguyen för att ha fångat några fel i det tidigare uttalandet av vår algoritm. Vi tackar de anonyma PODS'12 och JACM domare för många användbara kommentarer som har avsevärt förbättrat presentationen av artikeln. Fråga storlek, en sådan instans-optimal resultat i termer av data-komplexitet är fortfarande ouppnåelig om inte W[1] = RFPT. (Se avsnitt 7.2 för närmare upplysningar.) Följaktligen formulerar och löser vi ett enklare problem: Optimalt värsta fall Gå med i utvärderingsproblem (optimalt Gå med problem). Eftersom en fast databas schemaR = {R j ( på j )} j [m] och en m-tuple av heltalN = (N 1,. ..,....,.......................................................... Låt q vara den naturliga gå fråga som ansluter förbindelserna inR och låt I (N ) vara den uppsättning av alla instanser sådan att  tillR I j  till = N j för j = 1,....,m. Sedan, det värsta fallet optimal gå utvärderingsproblem är att utvärdera q i tid Eftersom alla algoritmer för att producera q(I ) kräver tid minst  tillq(I ), en algoritm som löser ovanstående problem skulle ha en optimal värsta fall data-komplexitet. Implicit, varianter av optimal anslutning problem har studerats i över tre decennier: ett modernt relationell databashanteringssystem (RDBMS) använder årtionden av högstämda algoritmer för att effektivt producera frågeresultat. Men, som vi skall visa i denna artikel, är befintliga system för bedömning av sammanfogning-träd-baserade frågor asymptotiskt suboptimala även i det enkla exemplet Equation (1). Huvudresultatet av denna artikel är en lösning på ovanstående problem med f (m, n) = n 2 och (m, n) = mn. Här är termen f (m, n) · j  till [m] N j förbehandlingstiden, och  på (m, n) · sup I (N )  påq(I ) är den värsta frågeutvärderingstiden. I en RDBMS, en beräknar information, t.ex. index, offline som kan undanröja behovet av att läsa hela indatarelationer för att producera utdata. I en liknande anda, kan vi förlänga våra resultat för att utvärdera alla frågor q i tid O (.(m, n) · sup I (N )  påq(I )), ta bort förbearbetningstiden genom att förhandsberäkna vissa index. Den första frågan vi måste svara på för att lösa det optimala gå problemet är att beräkna exakt den bundna sup I I (N ) Lyckligtvis gav Grohe och Marx [36] och Atserias, Grohe och Marx [9] (AGM:s resultat hädanefter) upphov till snäva gränser för antalet utgående tupler i en (naturlig) fråga när det gäller storleken på inputrelationerna. Uppskattning av utdatastorlek är också av grundläggande betydelse för effektiv frågebehandling; dessa resultat har genererat en hel del spänning och direkt banat väg för våra resultat. För att förstå andan i årsstämman resultat, överväga triangeln fråga exempel Ekvation (1) och låt q(I ) betecknar den uppsättning tuples som är utdata från att tillämpa frågan till en databas instans I. Hädanefter kommer vi att släppa superskriptet I om indata databas instansen är tydlig från sammanhang. Definitionsmässigt är q(I ) den uppsättning tripletter av konstanter (a, b, c) sådan att R(ab), S (bc), och T (ac) är i I. Vårt mål är att binda antalet tuples returneras av q på I, betecknad som "q(I )", i termer av "Redigera", "S" och "T". För enkelhetens skull, låt oss överväga fallet när... =... =... =... =... = N. En okomplicerad gräns är... Man kan få en bättre bunden genom att märka att någon parvis gå (säg R S) kommer att innehålla q(I ) i det som R och S tillsammans innehåller alla attribut (eller de "täcker" alla attribut). Detta leder till den bundna (I) till ≤ N 2. Årsstämman visade att man kan få en bättre övre gräns för  skaq(I ) och ≤ N 3/2 genom att generalisera begreppet omslag till ett s.k. "fraktionstäcke" (se avsnitt 3). Dessutom, denna uppskattning är snäv i den meningen att för oändligt många värden av N, Man kan hitta en databas instans I att för vilken  tillq(I ) till = N 3/2. Dessa icke-triviala uppskattningar är spännande för databasforskare eftersom de erbjuder tidigare okända, icke-triviala metoder för att uppskatta kardinaliteten av en frågeresultat-ett grundläggande problem
I motsats till värsta fall optimal gå algoritmer REF, våra garantier är probabilistiska och hänvisar till optimal genomförandetid (inte värsta-fall resultatstorlekar).
Worst-case Optimal Join Algorithms
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}