Abstract-En avgörande utmaning i probabilistiska databaser är skalbar beräkning av förtroenden av tuples i frågeresultat. Detta dokument introducerar en effektiv sekundär-lagring operatör för exakt beräkning av frågor på tuple-oberoende probabilistiska databaser. Vi anser att konjunktiva frågor utan själv-joins som är kända för att vara dragbar på någon tuplein oberoende databas, och frågor som inte är traktat i allmänhet men blir dragbar på probabilistiska databaser begränsas av funktionella beroenden. Vår operatör är semantiskt ekvivalent med en sekvens av aggregeringar och kan naturligt integreras i befintliga relationella frågeplaner. Som ett bevis på konceptet utvecklade vi en förlängning av PostgreSQL 8.3.3 frågemotorn SPRUT. Vi studerar optimeringar som driver eller drar vår operatör eller delar därav tidigare går samman. Operatören använder statisk information, såsom frågestrukturen och funktionella beroenden, för att bestämma vilka beståndsdelar aggregeringar kan utvärderas tillsammans i en scan och hur många skanningar som behövs för den övergripande förtroende beräkning uppgift. En fallstudie på TPC-H-riktmärket visar att de flesta TPC-H-frågor som erhålls genom att ta bort aggregeringar kan utvärderas effektivt med hjälp av vår operatör. Experimentell utvärdering av probabilistiska TPC-H-data visar på betydande effektivitetsförbättringar jämfört med den senaste tekniken. I detta dokument studerar vi följande problem: Med tanke på en fråga Q och en probabilistisk databas D, beräkna de distinkta möjliga tuples i resultatet av Q on D tillsammans med deras exakta förtroenden. Konceptuellt representerar en probabilistisk databas en uppsättning möjliga världar, var och en med en relationsdatabas, och frågan utvärderas i varje värld individuellt. Förtroendet för en tuple t är summan av sannolikheterna för alla de möjliga världar där t är en del av frågeresultatet. Dalvi och Sucius arbete med utvärdering av konjunktiva frågor om tuple-oberoende probabilistiska databaser [7] visar att klassen konjunktiva frågor kan delas in i "lätta" frågor (med polynom-tidsdata komplexitet) och "hårda" (#P-fullständiga) frågor. Deras metod för att behandla de enkla frågorna utan självhjälp använder så kallade säkra planer för att beräkna både svaret tuples och deras förtroende [5]. Säkra planer är en begränsad klass av frågeplaner eftersom deras gemensamma order följer den hierarkiska strukturen av frågan och använder överdriven dubblering i tillfälliga resultat. Detta dokument visar att de begränsningar som införs genom säkra planer inte är nödvändiga och någon frågeplan kan användas för att beräkna svaret tuples. För att beräkna förtroenden definierar vi
I REF visades det att en polynom-tid utvärdering kan utföras också med frågeplaner med någon gå beställning (inte bara de beställningar som krävs av säkra planer).
SPROUT: Lazy vs. Eager Query Plans for Tuple-Independent Probabilistic Databases
{'venue': '2009 IEEE 25th International Conference on Data Engineering', 'journal': '2009 IEEE 25th International Conference on Data Engineering', 'mag_field_of_study': ['Computer Science']}