I detta dokument undersöks problemet med att tillnärma konjunktiva frågor utan självhjälp på probabilistiska databaser med lägre och övre gränser som kan beräknas mer effektivt. Vi studerar detta problem via en indirektion: Med en propositionell formel 0, hitta formler på ett mer begränsat språk som är störst lägre bundna respektive minst övre bundna, respektive 0. Vi studerar gränser i de språk av läs-en gång formler, där varje variabel förekommer som mest en gång, och av läs-en gång formler i disjunktiv normal form. Vi visar ekvivalenser av syntaktiska och modellteoretiska karakteriseringar av optimala gränser för unika formler, och presenterar algoritmer som kan räkna upp dem med polynomisk fördröjning. Sådana gränser kan beräknas genom frågor som uttrycks med hjälp av första ordningen frågor utökad med transitiv stängning och ett särskilt val konstruktion. Förutom probabilistiska databaser, dessa resultat kan också gynna problemet med ungefärlig frågebedömning i relationsdatabaser, eftersom gränserna uttryckta av frågor kan beräknas i polynom kombinerad komplexitet.
En approximationsteknik för konjunktiva frågor om probabilistiska databaser har undersökts i REF.
On the optimal approximation of queries using tractable propositional languages
{'venue': "ICDT '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}