Probabilistiska databaser har löfte om att vara ett livskraftigt medel för storskalig osäkerhetshantering, som i allt högre grad behövs på ett antal områden i den verkliga världen. Men frågeutvärdering i probabilistiska databaser är fortfarande en utmaning för beräkningen. Tidigare arbete med effektiv exakt frågeutvärdering i probabilistiska databaser har till stor del koncentrerats på frågecentriska formuleringar (t.ex. säkra planer, hierarkiska frågor), i det att de endast beaktar egenskaperna hos frågan och inte uppgifterna i databasen. Det är lätt att konstruera exempel där en förment svår fråga körs på en lämplig databas ger upphov till ett dragbart frågebedömningsproblem. I detta dokument utvecklar vi effektiva frågevärderingstekniker som utnyttjar egenskaperna hos både förfrågan och data i databasen. Vi fokuserar på tuple-oberoende databaser där frågeutvärderingsproblemet är likvärdigt med att beräkna marginell sannolikhet för Booleska formler i samband med resultatet tuples. Denna senare uppgift är lätt om Booleska formler kan faktoriseras till en form som har varje variabel visas som mest en gång (kallas read-once). Men en naiv metod som direkt använder tidigare utvecklade Booleska formel factorization algoritmer är ineffektiv, eftersom dessa algoritmer kräver inmatning formler för att vara i disjunktiv normal form (DNF). Vi utvecklar istället nya, mer effektiva faktoriseringsalgoritmer som direkt konstruerar det read-once uttrycket för ett resultat tuple boolean formel (om man finns), för en stor underklass av frågor (specifikt, konjunktiva frågor utan själv-joins). Vi demonstrerar empiriskt att (1) våra föreslagna tekniker är storleksordningar snabbare än generiska inferensalgoritmer för frågor där resultatet Booleska formler kan faktoriseras till läs-en gång uttryck, och (2) för specialfallet av hierarkiska frågor, de konkurrerar effektiviteten av tidigare tekniker särskilt utformade för att hantera sådana frågor.
Precis som vi ser REF ut att bestämma effektivt när det extensionella tillvägagångssättet är tillämpligt med tanke på en konjunktiv fråga utan själv-joins och en tuple-oberoende databas.
Read-Once Functions and Query Evaluation in Probabilistic Databases
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}