The Complexity of Basic Graph Pattern Matching

We show that even the mere check whether a basic graph pattern in SPARQL has any match on a given graph is already NP-complete, i.e., difficult and not practically tractable in general. In fact, this is true for any query language that can find patterns in graphs. While students are required to bring an undergraduate level of complexity theory, the video also includes some review of the main parts of complexity theory we need, and some pointers to sources where you can brush up your knowledge. ► 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)