Vi anser att uppgiften att räkna upp och räkna svar på k-ary konjunktiva frågor mot relationella databaser som kan uppdateras genom att infoga eller ta bort tuples. Vi uppvisar en ny uppfattning om q-hierarkiska konjunktiva frågor och visar att dessa kan upprätthållas effektivt i följande mening. Under en linjär förbehandlingsfas kan vi bygga en datastruktur som möjliggör konstant fördröjningsräkning av frågeresultaten; och när databasen uppdateras kan vi uppdatera datastrukturen och starta om uppräkningsfasen inom konstant tid. För det speciella fallet av själv-join fria konjunktiva frågor vi få en dikotomi: om en fråga är inte q-hierarkiska, då fråga uppräkning med sublinjär * fördröjning och sublinjär uppdateringstid (och godtycklig förbehandlingstid) är omöjligt. För att svara Booleska konjunktiva frågor och för det mer allmänna problemet med att räkna antalet lösningar av k-ary frågor får vi kompletta dikotomier: om frågans homomorfiska kärna är q-hierarkisk, då storleken på frågeresultatet kan beräknas i linjär tid och upprätthållas med konstant uppdateringstid. Annars, storleken på frågeresultatet kan inte upprätthållas med sublinjär uppdateringstid. Alla våra lägre gränser förlitar sig på OMV-conjecture, en gissning på hårdheten av online matris-vektor multiplikation som nyligen har uppstått inom området finkornig komplexitet för att karakterisera hårdheten av dynamiska problem. Den lägre gränsen för räkneproblemet bygger dessutom på ortogonala vektorer gissningar, vilket i sin tur är underförstått av den starka exponentiella tidshypotesen. * ) Med sublinjära menar vi O(n 1−ε ) för vissa ε > 0, där n är storleken på den aktiva domänen i den aktuella databasen. •Teori för beräkning → Komplexitetsteori och logik; Datastrukturer och algoritmer för datahantering; Databasförfrågan bearbetning och optimering (teori); Problem, minskningar och fullständighet; Datastrukturer design och analys; Logik och databaser;
De så kallade q-hierarkiska gå frågor (såsom bostadsfrågan i våra experiment) är exakt de själv-join-fria konjunktiva frågor som medger konstant tidsuppdatering REF.
Answering Conjunctive Queries under Updates
{'venue': "PODS '17", 'journal': None, 'mag_field_of_study': ['Computer Science']}