Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.110
URN: urn:nbn:de:0030-drops-49804
URL: https://drops.dagstuhl.de/opus/volltexte/2015/4980/
Chen, Hubie ; Mengel, Stefan
A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
| pdf-format: |
|
Abstract
Conjunctive queries are basic and heavily studied database queries; in relational algebra, they are the select-project-join queries. In this article, we study the fundamental problem of counting, given a conjunctive query and a relational database, the number of answers to the query on the database. In particular, we study the complexity of this problem relative to sets of conjunctive queries. We present a trichotomy theorem, which shows essentially that this problem on a set of conjunctive queries is either tractable, equivalent to the parameterized CLIQUE problem, or as hard as the parameterized counting CLIQUE problem; the criteria describing which of these situations occurs is simply stated, in terms of graph-theoretic conditions.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs:2015:4980,
author = {Hubie Chen and Stefan Mengel},
title = {{A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries}},
booktitle = {18th International Conference on Database Theory (ICDT 2015)},
pages = {110--126},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-79-8},
ISSN = {1868-8969},
year = {2015},
volume = {31},
editor = {Marcelo Arenas and Mart{\'i}n Ugarte},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4980},
URN = {urn:nbn:de:0030-drops-49804},
doi = {10.4230/LIPIcs.ICDT.2015.110},
annote = {Keywords: database theory, query answering, conjunctive queries, counting complexity}
}
| Keywords: | database theory, query answering, conjunctive queries, counting complexity | |
| Seminar: | 18th International Conference on Database Theory (ICDT 2015) | |
| Issue date: | 2015 | |
| Date of publication: | 19.03.2015 |
