Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity

Journal article

We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem #UCQ(C) provides as input a UCQ Ψ ∈ C and a database D and the problem is to compute the number of answers of Ψ in D. Chen and Mengel [PODS’16] have shown that for any recursively enumerable class C, the problem #UCQ(C) is either fixed-parameter tractable or hard for one of the parameterised complexity classes W[1] or #W[1]. However, their tractability criterion is unwieldy in the sense that, given any concrete class C of UCQs, it is not easy to determine how hard it is to count answers to queries in C. Moreover, given a single specific UCQ Ψ, it is not easy to determine how hard it is to count answers to Ψ. In this work, we address the question of finding a natural tractability criterion: The combined conjunctive query of a UCQ Ψ = φ1 ∨ · · · ∨φℓ is the conjunctive query ∧ (Ψ) = φ1∧· · ·∧φℓ. We show that under natural closure properties of C, the problem #UCQ(C) is fixed-parameter tractable if and only if the combined conjunctive queries of UCQs in C, and their contracts, have bounded treewidth. A contract of a conjunctive query is an augmented structure, taking into account how the quantified variables are connected to the free variables — if all variables are free, then a conjunctive query is equal to its contract; in this special case the criterion for fixed-parameter tractability of #UCQ(C) thus simplifies to the combined queries having bounded treewidth. Finally, we give evidence that a closure property on C is necessary for obtaining a natural tractability criterion: We show that even for a single UCQ Ψ, the meta problem of deciding whether #UCQ({Ψ}) can be solved in time O(|D|d ) is NP-hard for any fixed d ≥ 1. Moreover, we prove that a known exponential-time algorithm for solving the meta problem is optimal under assumptions from fine-grained complexity theory. As a corollary of our reduction, we also establish that approximating the Weisfeiler-Leman-Dimension of a UCQ is NP-hard.

Authors: Focke, J; Goldberg, L; Roth, M; Živný, S

• Publication status: Accepted
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: ACM Transactions on Computational Logic
• Volume: 27
• Issue: 1
• Article number: 7
• Publication date: 2026-01-16
• Acceptance date: 2025-10-01
• DOI: 10.1145/3771726
• EISSN: 1557-945X
• ISSN: 1529-3785
• Language: English