Data Complexity of SPARQL
Channel: Knowledge-Based Systems, TU Dresden
Date: 2020-12-08

SPARQL query answering is quite tractable when looking only at data complexity (NL-complete), explaining to some extent why SPARQL works on large knowledge graphs in spite of the intractable (PSpace-hard) overall complexity we observed earlier. We conclude by sketching naive algorithms that could show that our complexity results are tight, i.e., can really be achieved by algorithms.

► Lecture slides for download: https://iccl.inf.tu-dresden.de/web/KG2020/en (Lecture 7)
► Related problem sheet to test your knowledge: Exercise 6
► Current and previous versions of the lecture:  https://iccl.inf.tu-dresden.de/web/Knowledge_Graphs
► Lecture notes on complexity theory for background reading: https://iccl.inf.tu-dresden.de/web/Complexity_Theory_(WS2019/20)