  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.
