Soutenance mémoire
Organisation du mémoire
Dans ce document, nous nous concentrons sur les techniques de réécritures et plus spécifiquement sur les techniques de réécritures d’une requête conjonctive initiale Q en une union de requêtes conjonctives (UCQ) ? Une UCQ peut aussi être vue comme un ensemble de requêtes conjonctives, que nous appellerons réécritures de Q. Notre but est de calculer un ensemble de réécritures qui soit à la fois adéquat (si l’une des réécritures s’envoie sur les faits alors Q est impliqué par la base de connaissances) et complet (si Q est impliqué par la base de connaissances alors l’une des réécritures s’envoie sur les faits). Une autre propriété souhaitable de l’ensemble de réécritures est sa minimalité : plus l’ensemble est petit, plus son évaluation sera rapide. Étant donné que le problème n’est pas décidable avec un ensemble de règles existentielles quelconques, il n’existe pas forcément d’ensemble de réécritures fini ayant les propriétés d’adéquation et de complétude. Un ensemble de règles existentielles qui assure l’existence d’un tel ensemble de réécritures pour n’importe quelle requête est appelé ensemble à unification finie (finite unification set, fus) [Baget et al., 2011a]. Après l’introduction dans le chapitre 2, des notions de base nécessaires à la compréhension de notre travail nous proposons dans le chapitre 3 un cadre théorique permettant l’étude des techniques de réécritures. Nous définissons d’abord les propriétés souhaitables d’un ensemble de réécritures (adéquation, complétude, minimalité). Puis nous étudions un algorithme générique qui, étant donné une requête et un ensemble de règles, calcule un ensemble de réécritures. Cet algorithme est paramétré par un opérateur de réécriture, c’est-à-dire une fonction qui, étant donné une requête et un ensemble de règles existentielles, retourne les réécritures “directes” de cette requête par cet ensemble de règles. L’algorithme effectue une exploration en largeur de l’espace des réécritures. A chaque étape, l’algorithme calcule l’ensemble des réécritures directes des requêtes obtenues à l’étape précédente et conservées (toutes les requêtes n’étant pas nécessairement conservées, pour des raisons que nous détaillerons au chapitre 3). Nous définissons des propriétés d’un opérateur de réécriture qui assurent que l’ensemble de réécritures calculé par l’algorithme est adéquat, complet, et minimal si l’ensemble de règles existentielles est fus.
Marche avant
La marche avant enrichit la base de faits en appliquant toutes les règles possibles puis interroge la base enrichie avec la requête initiale. L’étape d’application des règles, appelée saturation, se fait avec une stratégie en largeur pour garantir la complétude. On part d’un fait initial F0. Chaque étape i consiste à produire un fait appelé Fi à partir du fait courant, noté Fi−1, en calculant tous les homomorphismes des hypothèses de chaque règle avec Fi−1 puis en effectuant toutes les applications de règles correspondantes. Le fait Fk obtenu à l’étape k est appelé la k-saturation de F0 avec l’ensemble de règles. La marche avant peut-être aussi retrouvée sous le nom de chase dans la littérature de base de données, néanmoins il faut noter qu’il existe différentes variantes du chase qui se différencient par leur manière de traiter la redondance (oblivious [Calì et al., 2008], skolem [Marnette, 2009], restricted [Fagin et al., 2005], core chase [Deutsch et al., 2008])
Marche arrière
Historiquement, la marche arrière a d’abord été utilisée en programmation logique, notamment avec Prolog. Un programme logique positif est un ensemble de clauses de Horn représentant des faits (atomes sans variable) et des règles, pouvant comporter des symboles fonctionnels. On prouve qu’une requête conjonctive Q est conséquence logique d’un programme logique P en montrant que P ∧¬Q est insatisfiable, à l’aide de la méthode de résolution (à noter que Prolog par exemple suit une stratégie en profondeur pour des raisons d’efficacité, et que cette stratégie n’est pas complète). Lorsque la clause vide est produite, on dit que l’on a “effacé” Q. A chaque étape, on unifie un atome de Q, appelé le but, avec un atome positif d’une clause (donc un fait ou une conclusion de règle) et on produit la réécriture correspondante. On peut découper le processus de production de la clause vide en deux parties. La première partie crée de nouvelles clauses à partir des buts et des règles (pour que ce découpage soit applicable, cela nécessite bien sûr que ce processus soit fini). La seconde partie produit la clause vide à partir d’une clause créée par la première phase et des faits. On remarque que si l’on efface Q avec des faits cela revient à trouver un homomorphisme de Q dans ces faits. Nous en venons à une autre vision de la marche arrière introduite par l’article fondateur en OBQA [Calvanese et al., 2005] pour la logique de description DL-Lite. La marche arrière y est décomposée en deux étapes :
1. on calcule un ensemble de réécritures de la requête initiale, qui est un ensemble de requêtes conjonctives vu comme une union de requêtes conjonctives.
2. on interroge la base de faits avec cette union de requêtes conjonctives ce qui est équivalent d’un point de vue logique à chercher des homomorphismes (bien que le mécanisme soit implémenté en SQL). Cette séparation des faits et de l’ontologie présente d’indéniables avantages, par exemple dans le cas où les données sont réparties dans plusieurs bases ou que l’on ne dispose pas des droits d’écritures sur les faits. Outre les problèmes d’accès aux données, la marche arrière évite les problèmes liés au grossissement d’une base de faits causé par la marche avant. Nous avons montré dans la section 2.3.3 qu’une TBox DL-Lite se traduit en règles existentielles, et donc pas directement en clauses. L’unification doit donc être adaptée pour tenir compte des variables existentielles, ou bien les règles obtenues doivent être skolémisées. Ces deux approches ont été utilisées par la suite. Les techniques de réécriture de la littérature peuvent être classées en deux catégories en fonction du type de la réécriture. La première technique consiste à réécrire la requête sous forme d’une union de requêtes conjonctives [Gottlob et al., 2011, Chortaras et al., 2011, Rodriguez-Muro et al., 2013], la seconde réécrit la requête en un programme Datalog [Pérez-Urbina et al., 2010, Gottlob and Schwentick, 2012, Eiter et al., 2012, Trivela et al., 2013]. L’existence d’une réécriture sous forme d’une union de requêtes conjonctives est assurée lorsqu’un ensemble de règles est reformulable en requête du premier ordre (« first-order rewritable »). Cette notion très commune dans la littérature concerne l’existence d’une réécriture, adéquate et complète, en requête du premier ordre (« first order query »). En pratique, ces requêtes sont équivalentes à des requêtes SQL.
Unificateur par pièce
Comme nous l’avons vu dans la première section de ce chapitre, afin de conserver l’adéquation des réécritures, il faut ajouter des contraintes supplémentaires à l’unification. Ces contraintes permettent d’assurer que toutes les occurrences des termes qui disparaissent lors de la réécriture (qui sont unifiées avec des variables existentielles) appartiennent à la partie unifiée. Ces termes particuliers sont appelés variables liantes, et un ensemble d’atomes minimal qui contient aucune ou toutes les occurrences d’une même variable liante est une pièce.
|
Table des matières
1 Introduction
2 Notions de base
2.1 Bases de la logique du premier ordre
2.2 Les faits et la requête
2.3 L’ontologie
2.3.1 Logiques de description
2.3.2 Les règles existentielles
2.3.3 Traduction d’une base de logique de description en une base avec règles existentielles
2.4 Les différentes approches
2.4.1 Marche avant
2.4.2 Marche arrière
3 Un cadre théorique pour la réécriture en UCQ
3.1 Propriétés d’un ensemble de réécritures
3.2 Algorithme de réécriture
3.2.1 Terminaison et correction de l’algorithme
3.2.2 Adéquation et complétude
4 Une famille d’opérateurs de réécriture en union de requêtes conjonctives
4.1 Unification en présence de variables existentielles
4.2 Substitution et partition
4.3 Unificateur par pièce
4.4 Unificateur mono-pièce
4.5 Unificateur mono-pièce agrégé
4.6 Perspective d’amélioration
4.7 Comparaison aux algorithmes existants
5 Compilation de règles
5.1 Prise en compte de règles hiérarchiques
5.2 Extension aux règles compilables
5.3 Prise en compte d’un pré-ordre sur les atomes pour l’homomorphisme
5.4 Prise en compte d’un pré-ordre sur les atomes pour l’unification
5.5 Introduction de l’opérateur de réécriture rew4
5.6 Évaluation d’une UCQ-pivot
6 Implémentation
6.1 Calcul des unificateurs par pièce
6.2 Mise en place de la compilation
6.2.1 Saturation
6.2.2 Codage
6.2.3 Intégration du pré-ordre sur les atomes
6.2.4 Déploiement d’une requête
6.3 Structures de données et optimisations pratiques
7 Évaluation
7.1 Présentation du benchmark
7.2 Expérimentation des différentes versions de l’algorithme de réécriture
7.2.1 Comparaison en termes de nombre de requêtes
7.2.2 Comparaison en termes de temps
7.3 Comparaison à l’existant
7.3.1 Systèmes comparés
7.3.2 Comparaison expérimentale
7.4 Impact de la décomposition en règles à conclusion atomique
8 Conclusion
Index
Bibliographie
Télécharger le rapport complet
