Expressive Languages for Querying the Semantic Web

Marcelo Arenas, Georg Gottlob, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The problem of querying RDF data is a central issue for the development of the Semantic Web. The query language SPARQL has become the standard language for querying RDF, since its standardization in 2008. However, the 2008 version of this language missed some important functionalities: reasoning capabilities to deal with RDFS and OWL vocabularies, navigational capabilities to exploit the graph structure of RDF data, and a general form of recursion much needed to express some natural queries. To overcome these limitations, a new version of SPARQL, called SPARQL 1.1, was recently released, which includes entailment regimes for RDFS and OWL vocabularies, and a mechanism to express navigation patterns through regular expressions. Unfortunately, there are still some useful navigation patterns that cannot be expressed in SPARQL 1.1, and the language lacks of a general mechanism to express recursive queries.

To the best of our knowledge, there is no RDF query language that combines the above functionalities, and which can also be evaluated efficiently. It is the aim of this work to fill this gap. Towards this direction, we focus on the OWL 2 QL profile of OWL 2, and we show that every SPARQL query enriched with the above features can be naturally translated into a query expressed in a language which is based on an extension of Datalog which allows for value invention and stratified negation. However, the query evaluation problem for this language is highly intractable, which is not surprising since it is expressive enough to encode some inherently hard queries. We identify a natural fragment of it, and we show it to be tractable and powerful enough to define SPARQL queries enhanced with the desired functionalities.
Original languageEnglish
Title of host publicationProceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
Place of PublicationNew York, NY, USA
Number of pages13
ISBN (Print)978-1-4503-2375-8
Publication statusPublished - 2014

Publication series

NamePODS '14


Dive into the research topics of 'Expressive Languages for Querying the Semantic Web'. Together they form a unique fingerprint.

Cite this