Vi studerar utvärderingen av positiva konjunktiva frågor med booleska aggregattester (liknar HAVING i SQL) på probabilistiska databaser. Mer exakt studerar vi konjunktiva frågor med predikataggregat på probabilistiska databaser där aggregeringsfunktionen är en av MIN, MAX, EXISTS, COUNT, SUM, AVG, eller COUNT (DISTINCT) och jämförelsefunktionen är en av =, =, ≥, >, ≤ eller <. Komplexiteten i att utvärdera en HANDEL fråga beror på aggregeringsfunktionen, α, och jämförelsefunktionen,. I detta dokument fastställer vi en uppsättning trikotomi resultat för konjunktiva frågor med HAVING predikat parametrized av (α,  ska ). För sådana frågor (utan självhjälp) är en av följande tre påståenden sanna: (1) det exakta utvärderingsproblemet har P-tidsdata komplexitet. I det här fallet kallar vi frågan säker. (2) Det exakta utvärderingsproblemet är P-hård, men det ungefärliga utvärderingsproblemet har (randomiserat) P-tidsdata komplexitet. Mer exakt, det finns en fptras för frågan. I det här fallet kallar vi frågan apx-säker. (3) Det exakta utvärderingsproblemet är P-hard, och det ungefärliga utvärderingsproblemet är också svårt. Vi kallar dessa frågor farliga. Den exakta definitionen av varje klass beror på det aggregat som beaktas och jämförelsefunktionen. Vi har därför frågor som är (MAX, ≥)-säkra, (COUNT, ≤)-apx-säkra, (SUM, =)-farligt, etc. Vårt trikotomi resultat är en betydande förlängning av en tidigare dikotomi resultat för Booleska konjunktiva frågor till säker och inte säker. av de tre klasser vi presenterar nya tekniker. För säkra frågor beskriver vi en utvärderingsalgoritm som använder slumpmässiga variabler över halvringar. För apx-säkra frågor beskriver vi en fptras som bygger på en ny algoritm för att generera en slumpmässig möjlig värld som uppfyller ett givet tillstånd. Slutligen, för farliga frågor vi ger nya bevis på hårdhet approximation. Resultaten för säkra frågor tillkännagavs tidigare (i Ré, C., Suciu, D. Effektiv utvärdering av. I: DBPL, s. 186-200, 2007), men alla andra resultat är nya.
I arbetet med REF studeras problemet med att HAVA aggregerade frågor med predikat.
The trichotomy of HAVING queries on a probabilistic database
{'venue': 'The VLDB Journal', 'journal': 'The VLDB Journal', 'mag_field_of_study': ['Computer Science']}