Article ID Journal Published Year Pages File Type
430081 Journal of Computer and System Sciences 2013 18 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,