Foundations of RDF Databases

The goal of this paper is to give an overview of the basics of the theory of RDF databases. The authors provide a formal definition of RDF that includes the features that distinguish this model from other graph data models. They then move into the fundamental issue of querying RDF data. They start by considering the RDF query language SPARQL, which is a W3C Recommendation since January 2008. They provide an algebraic syntax and a compositional semantics for this language, study the complexity of the evaluation problem for different fragments of SPARQL, and consider the problem of optimizing the evaluation of SPARQL queries, showing that a natural fragment of this language has some good properties in this respect.