Modélisation de requêtes n-aires pour le
web sémantique
Sujet 2008/09 proposé dans : M2R Informatique, Projet ---
Magistere, M2
Responsables :
Mots-clés : web, langage de requêtes, analyse,
logique
Durée du projet : durée adaptable,
possibilité de continuer en thèse
Description
Les équipes WAM et EXMO partagent un axe de recherche qui
s'intéresse aux langages de requêtes permettant de
rechercher et d'extraire de l'information de données
structurées. Nous cherchons à élaborer les
outils et les algorithmes qui permettent de concevoir et
d'implanter efficacement la prochaine génération de
langages du web de demain [1].
A cette fin, l'équipe WAM a développé une
approche logique à base de mu-calcul. Le mu-calcul est une
logique modale qui peut être interprétée sur
des graphes finis, modélisant les données
manipulées dans le cadre du web sémantique. Une telle
logique permet de capturer les requêtes monadiques (autrement
dit unaires: c'est-à-dire dont le résultat est un
ensemble de noeuds du graphe). Le fait de traduire ces
requêtes en mu-calcul permet de résoudre des
problèmes comme l'équivalence de requêtes, ou
encore le test de requête vide, à l'aide d'un
algorithme connu pour tester la satisfaisabilité d'une
formule de mu-calcul. Cette méthode permet notamment
d'obtenir des bornes supérieures de complexité et des
algorithmes efficaces en pratique. En outre, un des avantages de
cette méthode est qu'il devient possible de résoudre
toute une classe de problèmes faisant intervenir ces
requêtes à l'aide du même algorithme, sans qu'il
ne soit nécessaire de concevoir un nouvel algorithme pour
chaque variante du problème. Nous avons appliqué avec
succès cette méthode dans le cadre du langage de
requêtes XPath sur les documents XML [2].
Cette méthode se révèle également
très prometteuse dans le cadre du web sémantique.
Cependant, il existe une différence majeure entre les
langages de requêtes à la XPath et les langages de
requêtes utilisés dans le contexte du web
sémantique (ex: SPARQL). Les requêtes employées
pour le web sémantique sont en effet polyadiques
("n-aires"): leur résultat est non plus forcément un
ensemble de noeuds, mais un ensemble de n-uplets de noeuds.
L'objectif de ce stage est d'étudier comment de telles
requêtes pourraient être modélisées dans
une logique modale éventuellement adaptée.
Les résultats attendus sont une technique de traduction de
requêtes polyadiques ("n-aires") dans une logique
inspirée du mu-calcul, ainsi que des techniques pouvant
être utilisées pour raisonner sur ces
requêtes.
Selon le degré d'avancement du stage, le compilateur pourra
être implanté en JAVA (nous disposons
déjà d'une implantation d'un solveur de
satisfaisabilité de mu-calcul, ainsi que du
nécessaire pour implanter des compilateurs dans cette
logique).
Ce stage offre l'opportunité de se familiariser avec les
langages du web sémantique, ainsi que de découvrir
des concepts généraux d'informatique
théorique. Il offre un excellent positionnement pour une
poursuite en thèse.
Références
[1] Static Analysis of XML Programs, Pierre Genevès and
Nabil Layaïda, (invited article) in ERCIM news number 72: "The
Future Web", 2008,
http://ercim-news.ercim.org/content/view/326/536/
[2] A System for the Static Analysis of XPath, Pierre
Genevès and Nabil Layaïda, ACM Transactions on
Information Systems (TOIS), Volume 24, Number 4, October 2006
[3] Extending SPARQL with Regular Expression Patterns (for Querying
RDF), Faisal Alkhateeb, Jean-François Baget,
Jérôme Euzenat, Journal of web semantics (à
paraître)
[4] The Complexity of Enriched µ-Calculi, Piero Bonatti,
Carsten Lutz, Aniello Murano, Moshe Vardi, Proc. ICALP,
pp540-551, 2006