Tractable counting of the answers to conjunctive queries

Conjunctive queries (CQs) are one of the most fundamental forms of database queries. In general, the evaluation of CQs is NPNP-complete. Consequently, there has been an intensive search for tractable fragments. In this paper, we want to initiate a systematic search for tractable fragments of the counting problem of CQs, i.e., the problem of counting the answers to a CQ. We prove several new tractability and intractability results by starting with acyclic conjunctive queries and generalising these results to CQs of bounded hypertree-width. We also extend our study to the counting problem of unions of CQs.

► This work initiates the systematic search for tractable cases of the problem of counting answers to conjunctive queries. ► We prove several new tractability and intractability results for acyclic conjunctive queries. ► These results are easily generalised to conjunctive queries of bounded hypertree-width.