12 avril 2022, 10:30-11:30.
ENS, S16
The Semiring-Based Provenance Framework for Graph Databases
L’augmentation du volume de données collectées par des capteurs et générées par des interactions humaines a mené à l’utilisation des bases de données orientées graphes en tant que modèle de représentation efficace pour les données complexes.
Les techniques permettant de tracer les calculs qui ont été appliqués aux données au sein d’une base de données relationnelle classique sont sur le devant de la scène, notamment grâce à leur utilité pour
faire respecter les régulations sur les données privées telles que le RGPD en Union Européenne.
Notre travail de recherche croise ces deux problématiques en s’intéressant à un modèle de provenance à base de semi-anneaux pour les requêtes navigationnelles.
En première partie, nous étudions le modèle en lui-même et introduisons un ensemble cohérent d’algorithmes permettant d’effectuer des calculs de provenance et adaptés aux propriétés des semi-anneaux utilisés.
Nous introduisons notablement une nouvelle méthode basée sur la théorie des treillis permettant de calculer la provenance pour des requêtes complexes.
Nous proposons une implémentation open-source de ces algorithmes et faisons une étude expérimentale sur de larges réseaux de transport issus de la vie réelle pour attester de l’efficacité pratique de notre approche.
La richesse de la littérature sur le domaine nous a notamment permis d’obtenir une borne inférieure sur la complexité de notre modèle.
On s’intéresse finalement au positionnement de ce cadre de travail par rapport à d’autres modèles de provenance à base de semi-anneaux. Nous nous intéressons à Datalog en particulier.
Nous démontrons que les méthodes que nous avons développées pour les bases de données orientées graphes peuvent se généraliser sur des requêtes Datalog.
Nous montrons de plus qu’elles peuvent être vues comme des généralisations de la méthode semi-naïve.
En se basant sur ce fait-là, nous étendons les capacités de \textsc{Soufflé}, un évaluateur Datalog appartenant à l’état de l’art, afin d’effectuer des calculs de provenance pour des requêtes Datalog.
Les études expérimentales basées sur cette implémentation open-source confirment que cette approche reste compétitive avec les solutions spécifiques pour les graphes, mais tout en étant plus générale.
Nous terminons par une discussion sur les améliorations possibles du modèle et énonçons les questions ouvertes qui ont été soulevées au cours de ce travail.
