Skip to Main content Skip to Navigation

Combined Complexity of Probabilistic Query Evaluation

Mikaël Monet 1, 2
1 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
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. My thesis investigates the question of which queries and instances ensure the tractability of PQE in combined complexity. My first contribution is to study PQE of conjunctive queries on binary signatures, which we rephrase 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. While the restrictions imposed in this setting are quite severe, my second contribution shows that, if we are ready to increase the complexity in the query, then we can evaluate a much more expressive language on more general instances. Specifically, we show that PQE for a particular class of Datalog queries on instances of bounded treewidth can be solved with linear complexity in the instance and doubly exponential complexity in the query. To prove this result, we use techniques from tree automata and knowledge compilation. The third contribution is to show the limits of some of these techniques by proving general lower bounds on knowledge compilation and tree automata formalisms.
Document type :
Complete list of metadata

Cited literature [146 references]  Display  Hide  Download
Contributor : Pierre Senellart Connect in order to contact the contributor
Submitted on : Friday, December 21, 2018 - 1:37:55 PM
Last modification on : Wednesday, November 17, 2021 - 12:33:15 PM
Long-term archiving on: : Friday, March 22, 2019 - 3:46:50 PM


Files produced by the author(s)


  • HAL Id : tel-01963559, version 1


Mikaël Monet. Combined Complexity of Probabilistic Query Evaluation. Databases [cs.DB]. Université Paris-Saclay, 2018. English. ⟨tel-01963559⟩



Record views


Files downloads