Constrained regular expressions for answering RDF-path queries modulo RDFS

Abstract

Purpose

The paper aims to discuss extensions of SPARQL that use regular expressions to navigate RDF graphs and may be used to answer queries considering RDFS semantics (in particular, nSPARQL and our proposal CPSPARQL).

Design/methodology/approach

The paper is based upon a theoretical comparison of the expressiveness and complexity of both nSPARQL and the corresponding fragment of CPSPARQL, that we call cpSPARQL.

Findings

The paper shows that nSPARQL and cpSPARQL (the fragment of CPSPARQL) have the same complexity through cpSPARQL, being a proper extension of SPARQL graph patterns, is more expressive than nSPARQL.

Research limitations/implications

It has not been possible to the authors to compare the performance of our CPSPARQL implementation with other proposals. However, the experimentation has allowed to make interesting observations.

Practical implications

The paper includes implications for implementing the SPARQL RDFS entailment regime.

Originality/value

The paper demonstrates the usefulness of cpSPARQL language. In particular, cpSPARQL, which is sufficient for capturing RDFS semantics, admits an efficient evaluation algorithm, while the whole CPSPARQL language is in theory as efficient as SPARQL is. Moreover, using such a path language within the SPARQL structure allows for properly extending SPARQL.

Citation

Alkhateeb, F. and Euzenat, J. (2014), "Constrained regular expressions for answering RDF-path queries modulo RDFS", International Journal of Web Information Systems, Vol. 10 No. 1, pp. 24-50. https://doi.org/10.1108/IJWIS-05-2013-0013