[Back]

R. Pichler, S. Skritek:
"On the Hardness of Counting the Solutions of SPARQL Queries";
Talk: 8th Alberto Mendelzon Workshop on Foundations of Data Management, Cartagena de Indias; 06-04-2014 - 06-06-2014; in: "Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management", G. Gottlob, J. Perez (ed.); CEUR-WS, Vol-1189 (2014), 6 pages.

Counting is a central feature of every query formalism. With SPARQL 1.1, aggregate functions (including count()) have been also introduced in SPARQL. We initiate a systematic study of the influence of the OPTIONAL operator on the complexity of counting for SPARQL queries. The OPTIONAL operator is a central language feature of SPARQL, since it enables a SPARQL query to return partial answers. In this paper, we thus study counting for well-designed SPARQL graph patterns, possibly extended by projection. We show that for these settings, counting is intractable (even beyond #P) in general. In a second step, we therefore investigate possible tractable fragments, starting with the recently identified fragments for conjunctive queries (CQs). Our results show that for these fragments, tractability does not carry over from CQs to well-designed graph patterns. We thus consider even stronger restriction (e.g., graph patterns containing only the OPTIONAL operator), and show that while the complexity decreases, counting becomes only tractable for well-designed graph patterns without union and projection, and remains still #P-complete if either union or projection is added.

SPARQL, counting, well-designed graph patterns, counting complexity

http://ceur-ws.org/Vol-1189/paper_14.pdf

Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions