The complexity of weighted counting for acyclic conjunctive queries

作者：

Highlights：

• We study weighted counting of solutions of acyclic conjunctive queries.

• We chart the tractability frontier for this problem.

• A parameter, called quantified star size, that measures how projected variables are spread in the query.

• Having bounded quantified star size exactly characterizes tractability for this problem.

摘要

•We study weighted counting of solutions of acyclic conjunctive queries.•We chart the tractability frontier for this problem.•A parameter, called quantified star size, that measures how projected variables are spread in the query.•Having bounded quantified star size exactly characterizes tractability for this problem.

论文关键词：Conjunctive queries,Counting complexity

论文评审过程：Received 26 June 2012, Revised 21 July 2013, Accepted 5 August 2013, Available online 13 August 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.08.001