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 :
Theses
Complete list of metadatas

Cited literature [146 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01980366
Contributor : Abes Star <>
Submitted on : Monday, January 14, 2019 - 1:25:10 PM
Last modification on : Thursday, October 17, 2019 - 12:36:10 PM

File

74604_MONET_2018_archivage.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01980366, version 1

Citation

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

Share

Metrics

Record views

125

Files downloads

36