Proposition n° 12

Titre : Types de données et RDFS: concilier complétude des inférences et l'efficacité des algorithmes

Responsable(s) : Jean-François Baget (Email : jean-francois.baget@inrialpes.fr), Jérôme Euzenat (Email : jerome.euzenat@inrialpes.fr)

Spécialité(s) :
  III - Intelligence, Interaction, Information

Laboratoire(s) :
  INRIA

Description du Sujet :

RDFS est un langage de représentation de connaissances dédié à la représentation de ressources dans le web sémantique. Plusieurs degrés d'expressivité sont disponibles dans ce langage, suivant le type d'interprétations utilisé pour les graphes RDF. Mais alors que les mécanismes de subsomption pour les trois premiers types d'interprétation (simple, rdf et rdfs) sont bien connus, l'interprétation des types de données soulève de nombreux problèmes: - leur spécification ne permet pas de décider en temps fini si l'intersection de deux types de données est vide - même si l'on change ces spécifications, l'utilisation des types de données fait monter la complexité du problème de subsomption dans la hiérarchie polynomiale (de NP-complet, il devient au moins Pi2-P-complet) - de plus, l'aspect langage de requêtes disparait: il n'est plus possible de répondre à une requête par un appariement des variables d'une requête avec des termes de la base de faits Le but de ce stage est de proposer des modifications du langage (contraintes supplémentaires pour les spécifications des types de données; appauvrissement de la sémantique; restriction syntaxiques...) et d'étudier l'impact de ces modifications sur la décidabilité, la complexité et l'expressivité des langages ainsi obtenus.