8494 articles  [english version]

inria-00598819, version 2

PSPARQL Query Containment

Melisachew Wudage Chekol () a, 1, Jérôme Euzenat () a, 1, Pierre Genevès () b, 2, Nabil Layaïda () a, 2

(2011)

Résumé : Querying the semantic web is mainly done through SPARQL. This language has been studied from different perspectives such as optimization and extension. One of its extensions, PSPARQL (Path SPARQL) provides queries with paths of arbitrary length. We study the static analysis of queries written in this language, in particular, containment of queries: determining whether, for any graph, the answers to a query are contained in those of another query. Our approach consists in encoding RDF graphs as transition systems and queries as $\mu$-calculus formulas and then reducing the containment problem to testing satisfiability in the logic. We establish complexity bounds and report experimental results

  • a –  INRIA
  • b –  CNRS
  • 1 :  EXMO (INRIA Grenoble Rhône-Alpes / LIG Laboratoire d'Informatique de Grenoble)
  • INRIA – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – CNRS : UMR5217 – Institut polytechnique de Grenoble (Grenoble INP)
  • 2 :  WAM (INRIA Grenoble Rhône-Alpes / LIG Laboratoire d'Informatique de Grenoble)
  • INRIA – Institut polytechnique de Grenoble (Grenoble INP) – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – CNRS : UMR5217
  • Domaine : Informatique/Intelligence artificielle
  • Mots-clés : Query Containment – PSPARQL – Semantic Web – RDF – Regular path queries
  • Versions disponibles :  v1 (07-06-2011) v2 (08-06-2011)
 
  • inria-00598819, version 2
  • http://hal.inria.fr/inria-00598819
  • oai:hal.inria.fr:inria-00598819
  • Contributeur : Melisachew Wudagae Chekol <>
  • Soumis le : Mercredi 8 Juin 2011, 15:54:09
  • Dernière modification le : Jeudi 16 Juin 2011, 12:15:56