The complexity of weighted counting for acyclic conjunctive queries

This paper is a study of weighted counting of the solutions of acyclic conjunctive queries (ACQ). The unweighted quantifier free version of this problem is known to be tractable (for combined complexity), but it is also known that introducing even a single quantified variable makes it #P-hard. We fi...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2014-02, Vol.80 (1), p.277-296
Main Authors: Durand, Arnaud, Mengel, Stefan
Format: Article
Language:English
Subjects:
Complexity
Conjunctive queries
Counting complexity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper is a study of weighted counting of the solutions of acyclic conjunctive queries (ACQ). The unweighted quantifier free version of this problem is known to be tractable (for combined complexity), but it is also known that introducing even a single quantified variable makes it #P-hard. We first show that weighted counting for quantifier free ACQ is still tractable and that even minimalistic extensions of the problem lead to hard cases. We then introduce a new parameter for quantified queries that permits to isolate a large island of tractability. We show that, up to a standard assumption from parameterized complexity, this parameter fully characterizes tractable subclasses for counting weighted solutions for ACQs. Thus we completely determine the tractability frontier for weighted counting for ACQ. •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.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2013.08.001