The parameterized complexity of database queries
Martin Grohe · 2001
This paper gives a short introduction into parameterized complexity theory, aimed towards database theorists interested in this area. The main results presented here classify the evaluation of first-order queries and conjunctive queries as hard parameterized problems.