On the Hardness of Counting the Solutions of SPARQL Queries
Counting, i.e. deriving the number of answers to a query, is a central feature of every query formalism-take for example the existence of a count() aggregate function in basically every major query language. For SPARQL, the W3C recommendation for a dedicated query language for RDF (Resource Description Framework) data, aggregate functions have been introduced recently. However, despite the ever growing importance of SPARQL, with few exceptions, the counting problem for SPARQL queries has remained unexplored so far. This paper is to initiate a systematic analysis of the complexity of counting the solutions of SPARQL queries.