Utilisation d'un solveur de contrainte pour répondre à des requêtes conjonctives dans une grande base de connaissances

Jean-François Baget & Rémi Coletta

baget@lirmm.fr

coletta@lirmm.fr

 

 

Contexte

Ce sujet s’inscrit dans la perspective du développement d’un logiciel permettant d’interroger une base de connaissance, à l’aide de requêtes conjonctives, en présence d’ontologies. Ce problème, parfois appelé « ontology-based data access » est aujourd’hui fortement étudié, notamment dans le cadre du web sémantique, où la grande quantité de données semi-structurées pose de nouveaux problèmes.

La particularité de l’équipe GraphIK (INRIA & LIRMM) est d’utiliser des règles existentielles pour le codage des ontologies. Le langage ainsi obtenu, aujourd’hui appelé Datalog+, permet de coder des ontologies écrites dans différents langages : par exemple dans le cadre du web sémantique, RDFS ou des fragments de OWL2.

Un problème central dans l’architecture logicielle que nous voulons aujourd’hui mettre en place est la recherche d’homomorphismes dans une base de connaissances. Il s’agit d’un problème NP-difficile, que l’on peut voir comme la recherche des réponses à une requête conjonctive dans une base de données relationnelle, mais qui pourrait se coder de façon efficace par un solveur de contraintes, tel qu’étudié au sein de l’équipe Coconut du LIRMM. Dans le cas de très grandes bases de connaissances, le codage standard de notre problème par un réseau de contraintes soulève des difficultés qui devront être résolues au cours de ce stage.

 

Objectifs

Le but de ce stage sera de brancher un solveur de contraintes sur une interface de gestion de bases de connaissances. Un sujet de thèse en cours au sein de l’ équipe GraphIK (Bruna Paiva Lima da Silva) est la réalisation d’une telle interface. Celle-ci permet de construire et d’interroger (par des opérations élémentaires) de façon unifiée des bases de connaissances en utilisant indifféremment différentes formes de stockage (graphes, bases de données relationnelles, triple stores…) Le codage de l’homomorphisme lui-même se fera en utilisant un solveur de contraintes. Le problème majeur est que la création du réseau de contraintes nécessite de coder l’ensemble de la base de connaissances dans le réseau lui-même, ce qui est impossible dans le cas de très grandes bases. Afin de remédier à ce problème, il faudra travailler à étendre le solveur afin de pouvoir créer dynamiquement le réseau au fur et à mesure de l’avancement du mécanisme de recherche (backtrack), en ne construisant que ce qui est nécessaire à un instant donné.

 

Les aspects théoriques aussi bien que la programmation sont importants pour ce stage :

·         Il faudra s’assurer que les différents algorithmes utilisés par le solveur de contraintes sont bien résistants à l’extension dynamique du réseau ;

·         Enfin, il faudra comparer le mécanisme d’interrogation obtenuavec ses équivalents dans différents formalismes, comme les requêtes conjonctives dans le SGBD Oracle ou différentes implémentations de SPARQL dans le cadre sdu web sémantique.