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

Cited literature [40 references]  Display  Hide  Download

https://hal.inria.fr/tel-01963559
Contributor : Pierre Senellart <>
Submitted on : Friday, December 21, 2018 - 1:37:55 PM
Last modification on : Friday, June 7, 2019 - 11:18:40 AM
Long-term archiving on : Friday, March 22, 2019 - 3:46:50 PM

File

thesis.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01963559, version 1

Citation

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

Share

Metrics

Record views

202

Files downloads

93