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 analyse 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 Skolemisation and a novel form of un-Skolemisation. 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.