Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity

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 \(\#\text{UCQ} (C)\) provides as input a UCQ \(\Psi\in C\) and a database \(\mathcal{D}\) and the problem is to compute the number of answers of \(\Psi\) in \(\mathcal{D}\) . Chen and Mengel [PODS ’16] have shown that for any recursively enumerable class \( C \) , the problem \(\#\text{UCQ} (C)\) is either fixed-parameter tractable or hard for one of the parameterised complexity classes \(\mathrm{W}[1]\) or \(\#\mathrm{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 \(\Psi\) , it is not easy to determine how hard it is to count answers to \(\Psi\) . In this work, we address the question of finding a natural tractability criterion: The combined conjunctive query of a UCQ \(\Psi=\varphi_{1}\vee\dots\vee\varphi_{\ell}\) is the conjunctive query \(\boldsymbol{\wedge}\left(\Psi\right)=\varphi_{1}\wedge\dots\wedge\varphi_{\ell}\) . We show that under natural closure properties of \( C \) , the problem \(\#\text{UCQ} (C)\) is FPT 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 \(\#\text{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 \(\Psi\) , the meta problem of deciding whether \(\#\text{UCQ} (\{\Psi\})\) can be solved in time \(O(|\mathcal{D}|^{d})\) is \(\mathrm{NP}\) -hard for any fixed \(d\geq 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 \(\mathrm{NP}\) -hard.