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

Conference item

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 ∨ ... ∨ φl is the conjunctive query ^ Ψ = φ_1 ∧ ... ∧ φl. 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, LA; Roth, M; Živný, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: Proceedings of the ACM on Management of Data
• Volume: 2
• Issue: 2
• Article number: 113
• Publication date: 2024-05-14
• Acceptance date: 2024-03-04
• Event title: 2024 ACM International Conference on Management of Data (SIGMOD/PODS 2024)
• Event location: Santiago, Chile
• Event website: https://2024.sigmod.org/
• Event start date: 2024-06-09
• Event end date: 2024-06-14
• DOI: 10.1145/3651614
• EISSN: 2836-6573
• Language: English