Dans les différents modèles de base de connaissance définis dans la famille SG, le problème étudié est celui de la déduction d'un graphe d'un ensemble de graphes (éventuellement accompagné de règles, contraintes...). Les requêtes dans ce cadre sont limitées à des questions "oui/non" portant sur l'existence d'une connaissance dans la base. Etant donné un SG Q représentant une requête et un SG G (non forcément connexe) représentant une base de connaissances, il s'agit de vérifier si G ≤ Q.
Nous souhaiterions traiter les requêtes comme des questions de type "retrouver dans G les Q ". Il s'agit alors d'extraire de la base des connaissances les BG (sous-BG de G) répondant à la question. Ce nouveau cadre nécessite de définir l'ensemble des réponses à une requête Q sur une base G.
A la manière du SQL des SGBD, on souhaiterait finalement exprimer des questions du type "quels sont les QH tels que QB ?" qui pourraient être représentées par un couple de lambda graphes (ou un graphe bicoloré) (QH, QB) et même pouvoir présenter un ensemble de réponses comme un graphe particulier (~ notion de vue).
L'objectif de ce stage est donc de définir un langage de requêtes sur une base de graphes et de proposer des mécanismes "à base de graphes" pour traiter ces requêtes. Quelques exemples de ce que pourrait être un tel langage sont proposés dans le rapport de recherche "On querying Simple Conceptual Graphs with Negation".
On s'intéressera au calcul des réponses à une requête et au problème de l'inclusion de requêtes (i.e. étant donnée deux requêtes Q1 et Q2, a-t-on pour toute base G, l'ensemble des réponses à Q1 dans G est-il inclus dans l'ensemble des réponses à Q2 dans G ?).
On s'inspirera des propositions faites dans le cadre du web sémantique : en particulier le langage SPARQL proposé pour les graphes RDF. Un article intéressant sur le sujet : Foundations of semantic web databases