Constrained Regular Expressions in SPARQL

The authors have proposed an extension of SPARQL, called PSPARQL, to characterize paths of variable lengths in an RDF knowledge base (e.g. "Does there exist a trip from town A to town B?"). However, PSPARQL queries do not allow expressing constraints on internal nodes (e.g. "Moreover, one of the stops must provide a wireless access."). This paper proposes an extension of PSPARQL, called CPSPARQL that allows expressing constraints on paths. For this extension, the authors provide an abstract syntax, semantics as well as a sound and complete inference mechanism for answering CPSPARQL queries.