Counting solutions to conjunctive queries: Structural and hybrid tractability

Counting the number of answers to conjunctive queries is an intractable problem (#P-hard), even over classes of acyclic queries. Therefore, classical structural decompositions based on suitable gener-alizations of acyclicity are not helpful here, and novel approaches have to be designed. The paper faces this issue by defining the novel concept of #-generalized hypertree decomposition, and by showing that answers can be efficiently counted on those classes of queries that have bounded #-generalized hypertree width. Variants of #-generalized hypertree de- compositions are also discussed leading, in particular, to hybrid methods identifying islands of tractability based not only on the structure of the query, but also on the database given at hand.