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 #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. &...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Association for Computing Machinery
2024
|
| _version_ | 1826314398714560512 |
|---|---|
| author | Focke, J Goldberg, LA Roth, M Živný, S |
| author_facet | Focke, J Goldberg, LA Roth, M Živný, S |
| author_sort | Focke, J |
| collection | OXFORD |
| description | 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.
<br>
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 Ψ.
<br>
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.
<br>
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. |
| first_indexed | 2024-03-07T08:29:13Z |
| format | Conference item |
| id | oxford-uuid:796d39b4-1c92-4f9b-aa74-313b47f7c710 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:31:57Z |
| publishDate | 2024 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:796d39b4-1c92-4f9b-aa74-313b47f7c7102024-09-03T15:37:51ZCounting answers to unions of conjunctive queries: natural tractability criteria and meta-complexityConference itemhttp://purl.org/coar/resource_type/c_5794uuid:796d39b4-1c92-4f9b-aa74-313b47f7c710EnglishSymplectic ElementsAssociation for Computing Machinery2024Focke, JGoldberg, LARoth, MŽivný, SWe 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. <br> 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 Ψ. <br> 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. <br> 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. |
| spellingShingle | Focke, J Goldberg, LA Roth, M Živný, S Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity |
| title | Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity |
| title_full | Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity |
| title_fullStr | Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity |
| title_full_unstemmed | Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity |
| title_short | Counting answers to unions of conjunctive queries: natural tractability criteria and meta-complexity |
| title_sort | counting answers to unions of conjunctive queries natural tractability criteria and meta complexity |
| work_keys_str_mv | AT fockej countinganswerstounionsofconjunctivequeriesnaturaltractabilitycriteriaandmetacomplexity AT goldbergla countinganswerstounionsofconjunctivequeriesnaturaltractabilitycriteriaandmetacomplexity AT rothm countinganswerstounionsofconjunctivequeriesnaturaltractabilitycriteriaandmetacomplexity AT zivnys countinganswerstounionsofconjunctivequeriesnaturaltractabilitycriteriaandmetacomplexity |