Since the Resource Description Framework (RDF) has emerged as the basic format of choice for representing Semantic Web data, query languages for RDF such as SPARQL, RQL, and Versa have been developed. Although blank nodes are a prominent feature of RDF, these query languages have, until now, largely ignored the need for sophisticated blank node support.

In this article we analyze the limitations of existing RDF query languages with respect to blank nodes by studying a formal, rule-based query language called RDFLog. We define the operational semantics of RDFLog by a LOGSPACE transformation of RDFLog programs to logic programs and back to RDF graphs, using Skolemization and a novel form of un-Skolemization. This yields a generic and closed operational semantics. Moreover, a declarative semantics is provided, and the operational semantics is shown to be sound and complete with respect to the declarative semantics. For several fragments of RDFLog, we study complexity and expressiveness. In addition, we provide complexity results for SPARQL and show how to increase SPARQLs expressiveness without affecting its complexity.

Comparison of RDFLog with leading SPARQL Implementations:

In both figures, smaller is better. The first figure shows performance in presence of blank nodes in the head (scoped by all universal variables as SPARQL allows only that form of blank nodes). The second figure shows that even in absence of blank nodes, RDFLog (implemented on top of XSB by using a (< 100 lines) pre- and postprocessing) outperforms both Jena’s ARQ and Sesames in-memory SPARQL implementation significantly.