# A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries

arXiv: https://arxiv.org/abs/1408.0890 · HTML: https://mlsanity.com/paper/1408.0890/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2014.

## Built on by (most cited first, 3 of 3)

- [Solving Projected Model Counting by Utilizing Treewidth and its Limits](https://mlsanity.com/paper/2305.19212/) (2023)
- [Characterising Fixed Parameter Tractability of Query Evaluation over Guarded TGDs](https://mlsanity.com/paper/2101.11727/) (2021)
- [Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability](https://mlsanity.com/paper/2311.14579/) (2023)

## Abstract (arXiv)

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.