The parameterized complexity of database queries
- 1 May 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
Abstract
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.Keywords
This publication has 18 references indexed in Scilit:
- Datalog LITEACM Transactions on Computational Logic, 2002
- Fixed-Parameter Tractability, Definability, and Model-CheckingSIAM Journal on Computing, 2001
- Parameterized circuit complexity and the W hierarchyTheoretical Computer Science, 1998
- Fixed-Parameter Tractability and Completeness I: Basic ResultsSIAM Journal on Computing, 1995
- Fixed-parameter tractability and completeness II: On completeness for W[1]Theoretical Computer Science, 1995
- Monadic second-order evaluations on tree-decomposable graphsTheoretical Computer Science, 1993
- Easy problems for tree-decomposable graphsJournal of Algorithms, 1991
- Nonconstructive tools for proving polynomial-time decidabilityJournal of the ACM, 1988
- The complexity of relational query languages (Extended Abstract)Published by Association for Computing Machinery (ACM) ,1982
- Optimal implementation of conjunctive queries in relational data basesPublished by Association for Computing Machinery (ACM) ,1977