One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries
- Submitting institution
-
Birkbeck College
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 147
- Type
- D - Journal article
- DOI
-
10.1145/3143805
- Title of journal
- ACM Transactions on Computational Logic
- Article number
- 29
- First page
- -
- Volume
- 18
- Issue
- 4
- ISSN
- 1529-3785
- Open access status
- Technical exception
- Month of publication
- December
- Year of publication
- 2017
- URL
-
http://eprints.bbk.ac.uk/id/eprint/21940/
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
3 - Knowledge Representation and Data Management
- Citation count
- 4
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper presents a fine-grained complexity classification of conjunctive queries, a heavily studied class of queries in the database literature, using and extending tools from parameterised complexity theory and graph minor theory. One of the fruits of this article is a readily comprehensible and succinct proof of the main theorem of Martin Grohe's 2007 Journal of the ACM article "The complexity of homomorphism and constraint satisfaction problems seen from the other side”.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -