Certain Query Answering in First-Order Languages

Les bases de données actuelles contiennent bien souvent des informations incertaines, inconsistantes ou incomplètes. Le terme certain query answering (CQA) qualifie les méthodes utilisées pour calculer les réponses fiables à des requêtes sur ces bases de données. Cette thèse se concentre sur les cas où un tel calcul est exprimable en logique du premier ordre (et donc, dans la classe de faible complexité AC0).

La première partie de la thèse traite du CQA dans des bases de données relationnelles qui peuvent ne pas satisfaire des contraintes de clés primaires. Ces bases de données sont également appelées 'incertaines'. Une réparation d'une telle base de données incertaine est obtenue en sélectionnant un nombre maximum de tuples sans jamais sélectionner deux tuples distincts d'une même relation, et qui partagent une même valeur de clé primaire. Une requête booléenne q est dite 'certaine' dans une base de données incertaine db si q s'évalue à vrai sur chaque réparation de db. Étant donnée une requête booléenne q, CERTAINTY(q) est défini comme l'ensemble des bases de données incertaines dans lesquelles q est certaine.
La littérature fait déjà mention de requêtes conjonctives q pour lesquelles CERTAINTY(q) est coNP-dur. Cette thèse se focalise sur les cas où CERTAINTY(q) est définissable en logique du premier ordre, c'est-à-dire qu'il existe une phrase en logique du premier ordre qui détermine si q est certaine. Une telle phrase est également appelée une ré-écriture certaine de q en logique du premier ordre. Si q est une requête booléenne, acyclique, conjonctive et sans self-join, le problème de savoir si CERTAINTY(q) est définissable en logique du premier ordre est décidable.
Nous proposons des algorithmes qui construisent des ré-écritures certaines pour de telles requêtes, à la fois en logique du premier ordre et en SQL. Nous étudions ensuite les effets qu'ont plusieurs simplifications syntaxiques sur les temps d'exécution des ré-écritures certaines en SQL sur de larges bases de données.

Dans la seconde partie de la thèse, poussés par une problématique dans les bases de données temporelles, nous considérons les incertitudes dans le cadre de la logique du premier ordre sur les mots. Dans ce contexte, l'incertitude est retranscrite au sein du concept de multimot. Un multimot est une séquence finie d'ensembles (non-vides) de symboles possibles. Chaque mot pouvant être obtenu en choisissant un symbole dans chaque ensemble de symboles possibles est un mot possible. Si w est un mot, alors CERTAIN(w) est défini comme l'ensemble des multimots tels que w est facteur de chaque mot possible du multimot.
Nous apportons des preuves solides qui soutiennent la conjecture que CERTAIN(w) est définissable en logique du premier ordre, quelque soit le mot w. Nous étudions également les automates déterministes finis reconnaissant CERTAIN(w).