Combined complexity of probabilistic query evaluation
Complexité combinée de l'évaluation de requêtes sur des données probabilistes
Résumé
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.
L'évaluation de requêtes sur des données probabilistes(probabilistic query evaluation, ou PQE) est généralement très coûteuse enressources 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 diminuerla 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 montreque 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éeset doublement exponentiel en la requête. Ce résultat est prouvé en utilisant des techniques d'automatesd'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 desbornes 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.
Origine : Version validée par le jury (STAR)
Loading...