Résumé | Query evaluation is the problem of checking if some input data
satisfies a fixed query, and probabilistic query evaluation (PQE) is its
extension to probabilistic data, where we must compute the probability
that the query is true. Specifically, we study this problem on
tuple-independent databases of arity 2, aka probabilistic graphs: the
graph has edges labeled with probabilities denoting how likely it is
that the edge exists, independently from other edges. The PQE problem
for a query Q, called PQE(Q) is to then take an input probabilistic
graph of this kind, and compute the exact probability that a random
possible world of this graph satisfies Q. We study this problem in data
complexity, i.e., its complexity is measured as a function of the graph,
when Q is fixed.
The talk will present several dichotomies around the PQE problem. The
first one is by Dalvi and Suciu [JACM'12] and applies to unions of
conjunctive queries. They showed that for any such query Q, either
PQE(Q) is in PTIME or it is #P-hard. I will present our recent extension
of this dichotomy with Ismail Ilkan Ceylan [ICDT'20], for the larger
query class of homomorphism-closed queries: for any such query Q, either
PQE(Q) is in PTIME or it is #P-hard. Actually, the main result is that
PQE(Q) is #P-hard for any homomorphism-closed query which is not a UCQ.
I will also present our dichotomy with Pierre Bourhis and Pierre
Senellart [ICALP'15, PODS'16] on restricting instance classes. We show
that PQE(Q) is in PTIME, for the larger class of MSO queries, when the
input probabilistic graphs are required to be trees or have
bounded-treewidth. Conversely, PQE is intractable on unbounded-treewidth
graphs under some technical assumptions. Last, I will present our
ongoing work with Benny Kimelfeld, showing that the PQE dichotomy on
self-join-free conjunctive queries also applies to unweighted PQE, i.e.,
when all probabilities of the graph are 1/2. |