Evènement pour le groupe Séminaire Méthodes Formelles


Date 2020-05-19  14:00-15:00
TitreQuery evaluation on probabilistic data: a story of dichotomies 
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. 
LieuVirtual 
OrateurAntoine Amarilli 
Emailhttps://a3nm.net/ 
UrlTélécom Paris 



Aucun document lié à cet événement.

Retour
Retour à l'index