Skip to Main content Skip to Navigation

Combined complexity of probabilistic query evaluation

Abstract : Query evaluation over probabilistic databases (probabilistic queryevaluation, or PQE) is known to be intractable inmany cases, even in data complexity, i.e., when the query is fixed. Althoughsome restrictions of the queries and instances have been proposed tolower the complexity, these known tractable cases usually do not apply tocombined complexity, i.e., when the query is not fixed. My thesis investigates thequestion of which queries and instances ensure the tractability ofPQE in combined complexity.My first contribution is to study PQE of conjunctive queries on binary signatures, which we rephraseas 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, I 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 : ABES STAR :  Contact
Submitted on : Monday, January 14, 2019 - 1:25:10 PM
Last modification on : Friday, July 31, 2020 - 10:44:09 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01980366, version 1


Mikaël Monet. Combined complexity of probabilistic query evaluation. Databases [cs.DB]. Université Paris-Saclay, 2018. English. ⟨NNT : 2018SACLT003⟩. ⟨tel-01980366⟩



Record views


Files downloads