Seminars

Title: Combined Complexity of Probabilistic Query Evaluation

Abstract:
Query evaluation over probabilistic databases (probabilistic query evaluation, or PQE) is known to be intractable in many cases, even in data complexity, i.e., when the query is fixed. Although some restrictions of the queries and instances have been proposed to lower the complexity, these known tractable cases usually do not apply to combined complexity, i.e., when the query is not fixed. This talk gives an overview of my PhD research, which investigates which queries and instances ensure the tractability of PQE in combined complexity.

I will first present our work on PQE of conjunctive queries on binary signatures, which can be rephrased as a probabilistic graph homomorphism problem. We restrict the query and instance graphs to be trees and show the impact on the combined complexity of diverse features such as edge labels, branching, or connectedness. This is joint work with Antoine Amarilli and Pierre Senellart and was presented at PODS'2017.

Second, we will explore the combined complexity of evaluating queries on treelike databases, i.e., databases whose treewidth is bounded by a constant. We introduce a class of queries (named 'CFG-Datalog') which generalizes many known query languages that are tractable in this context. Specifically, we show that the (non-probabilistic) evaluation of CFG-Datalog on treelike databases can be solved with complexity linear in the product of the instance size and of the query size. In the process, we introduce a new representation of the provenance of a query on a database, based on cyclic Boolean circuits. This is joint work with Antoine Amarilli, Pierre Bourhis, and Pierre Senellart, and was presented at ICDT'2017.

Last, we will move to the field of knowledge compilation and present our work that connects various notions of width for Boolean circuits. We show that circuits of bounded treewidth can be efficiently compiled into structured deterministic decomposable normal forms (d-SDNNFs), which in particular allows efficient probability computation. We show the implications of this result for PQE of CFG-Datalog on treelike databases. We also prove general lower bounds on knowledge compilation formalisms, which imply lower bounds for provenance computation. This is joint work with Antoine Amarilli and Pierre Senellart and was presented at ICDT'2018.