Combined Complexity of Probabilistic Query Evaluation

Complexité combinée d’évaluation de requêtes sur des données probabilistes

Mikaël Monet (1, 2)

1 VALDA - Value from Data
2 LTCI - Laboratoire Traitement et Communication de l'Information

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.

L’évaluation de requêtes sur des données probabilistes (probabilistic query evaluation ou PQE) est généralement très coûteuse en ressources et ce même à requête fixée. Bien que certaines restrictions sur les requêtes et les données aient été proposées pour en diminuer la complexité, les résultats existants ne s’appliquent pas à la complexité combinée, c’est-à-dire quand la requête n’est pas fixe. Ma thèse s’intéresse à la question de déterminer pour quelles requêtes et données l’évaluation probabiliste est faisable en complexité combinée. La première contribution de cette thèse est d’étudier PQE pour des requêtes conjonctives sur des schémas d’arité 2. Nous imposons que les requêtes et les données aient la forme d’arbres et montrons l’importance de diverses caractéristiques telles que la présence d’étiquettes sur les arêtes, les bifurcations ou la connectivité. Les restrictions imposées dans ce cadre sont assez sévères, mais la deuxième contribution de cette thèse montre que si l’on est prêts à augmenter la complexité en la requête, alors il devient possible d’évaluer un langage de requête plus expressif sur des données plus générales. Plus précisément, nous montrons que l’évaluation probabiliste d’un fragment particulier de Datalog sur des données de largeur d’arbre bornée peut s’effectuer en temps linéaire en les données et doublement exponentiel en la requête. Ce résultat est prouvé en utilisant des techniques d’automates d’arbres et de compilation de connaissances. La troisième contribution de ce travail est de montrer les limites de certaines de ces techniques, en prouvant des bornes inférieures générales sur la taille de formalismes de représentation utilisés en compilation de connaissances et en théorie des automates.

Mots clés: Databases; Probabilities; Combined Complexity on the combined c

Mots clés: Bases de données; Probabilités; Complexité combinée

Domaines: Base de données [cs.DB]

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