Constrained Regular Expressions in SPARQL

Faisal Alkhateeb 1 Jean-François Baget 2, 3 Jérôme Euzenat 1
1 EXMO - Computer mediated exchange of structured knowledge
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : RDF is a knowledge representation language dedicated to the annotation of resources within the Semantic Web. Though RDF itself can be used as a query language for an RDF knowledge base (using RDF consequence), the need for added expressivity in queries has led to the definition of the SPARQL query language. SPARQL queries are defined on top of graph patterns that are basically RDF (and more precisely GRDF) graphs. To be able to characterize paths of arbitrary length in a query (e.g., "does there exist a trip from town A to town B using only trains and buses?"), we have already proposed the PRDF (for Path RDF) language, effectively mixing RDF reasonings with database-inspired regular paths. However, these queries do not allow expressing constraints on the internal nodes (e.g., "Moreover, one of the stops must provide a wireless connection."). To express these constraints, we present here an extension of RDF, called CRDF (for Constrained paths RDF). For this extension of RDF, we provide an abstract syntax and an extension of RDF semantics. We characterize query answering (the query is a CRDF graph, the knowledge base is an RDF graph) as a particular case of CRDF entailment that can be computed using some kind of graph homomorphism. Finally, we use CRDF graphs to generalize SPARQL graph patterns, defining the CSPARQL extension of that query language, and prove that the problem of query answering using only CRDF graphs is an NP-hard problem.
Type de document :
[Research Report] RR-6360, INRIA. 2007, pp.23
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger
Contributeur : Faisal Alkhateeb <>
Soumis le : dimanche 16 décembre 2007 - 18:53:55
Dernière modification le : samedi 15 décembre 2018 - 01:49:37
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 16:57:00


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00188287, version 3


Faisal Alkhateeb, Jean-François Baget, Jérôme Euzenat. Constrained Regular Expressions in SPARQL. [Research Report] RR-6360, INRIA. 2007, pp.23. 〈inria-00188287v3〉



Consultations de la notice


Téléchargements de fichiers