Soutenance de thèse
Les problèmes de l’incohérence dans les bases de données et les bases de connaissances ont été largement abordés et discutés au cours des quarante dernières années. L’incohérence est l’une des principales dimensions de la qualité des données. À notre époque, les données sont le nouvel or, mais les données sans qualité ou l’absence de mesures de qualité peuvent entraîner d’autres fardeaux qui conduisent à des résultats d’analyse erronés et peu informatifs à partir des données. Le problème de l'incohérence survient lorsqu’un ensemble de contraintes qui doivent être satisfaites par l'instance de la base de données sont violées par cette instance. Les travaux précédents qui traitent du problème de l’incohérence se sont intéressés soit de la réparation de la base de données incohérente pour obtenir une nouvelle base de données qui est cohérente (c’est-à-dire qu’il n’y a pas de violation des contraintes), soit sur la quantification de l’incohérence dans la base de données entière. Dans cette thèse, nous proposons une nouvelle approche pour gérer l’incohérence dans les bases de données relationnelles en la quantifiant au niveau des tuples, puis en classant les tuples/réponses selon leur incohérence pour permettre de choisir parmi les réponses aux requêtes celles qui sont les plus cohérentes/inconsistantes. Ainsi, nous définissons différentes nouvelles mesures de degrés de l’incohérence basées soit sur la violation des tuples. Nous considérons la classe des contraintes de déni( denial constraint en anglais) et la classe des requêtes con- jonctives. Nous tirons parti des méthodes why-provenance et polynomial provenance pour identifier les tuples incohérents et pour calculer les degrés de l’incohérence des réponses aux requêtes, respectivement. Nous convertissons chaque contrainte de déni en une requête booléenne conjonctive et évaluons cette dernière sur la base de données pour calculer le why-provenance de la réponse true. En utilisant le why-provenance, chaque ligne de la base de données est annotée avec l’ensemble des contraintes qu’elle viole et son identifiant sous une forme de monôme (dans le cas contraire, c’est-à-dire si la ligne de donées n’est impliquée dans aucune violation de contrainte, elle est alors annotée par le monôme 1), on obtient alors une base de données annotée. Étant donné une requête conjonctive Q, Q est évaluée sur la base de données annotée et chaque réponse est calculée avec une provenance polynomiale qui encode dans une formule polynomiale l’ensemble des contraintes violées par les réponses ainsi que l’ensemble des lignes de données utilisées pour calculer la réponse et impliquées dans la violation de ces contraintes. Ensuite, nous définissons douze mesures de degré de l’incohérence en utilisant la provenance polynomiale des réponses. Une fois les mesures d'incohérence définies, il est intéressant de permettre le classement des réponses aux rêquetes en fonction de leur degré d’incohérence. Nous concevons un ensemble d’algorithmes de top-k, dont TopINC sur lequel est basée l’idée des autres algorithmes, permettant de classer les réponses aux requêtes en fonction de leurs degrés d’incohérence. Nous introduisons une nouvelle classe d’algorithmes avec un nouveau modèle de coût et montrons l’optimalité de ces algorithmes de top-k dans certaines conditions spécifiques. De plus, pour chaque algorithme de top-k, nous donnons sa complexité théorique. Nous avons mené une grande experimentation pour montrer la faisabilité de notre approche en pratique et aussi pour montrer l’efficacité de nos algorithmes de top-k développés.
Membres du jury :
