Skip to Main content Skip to Navigation
Theses

Combined complexity of probabilistic query evaluation

Résumé : 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.
Document type :
Theses
Complete list of metadatas

Cited literature [146 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01980366
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

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

197

Files downloads

78