Approximately counting answers to conjunctive queries with disequalities and negations
<p>We study the complexity of approximating the number of answers to a small query 𝜑 in a large database D. We establish an exhaustive classification into tractable and intractable cases if 𝜑 is a conjunctive query possibly including disequalities and negations:</p> <br> <p>•...
| Autores principales: | , , , |
|---|---|
| Formato: | Journal article |
| Lenguaje: | English |
| Publicado: |
Association for Computing Machinery
2024
|
| _version_ | 1826314956519243776 |
|---|---|
| author | Focke, J Goldberg, L Roth, M Zivny, S |
| author_facet | Focke, J Goldberg, L Roth, M Zivny, S |
| author_sort | Focke, J |
| collection | OXFORD |
| description | <p>We study the complexity of approximating the number of answers to a small query 𝜑 in a large database D. We establish an exhaustive
classification into tractable and intractable cases if 𝜑 is a conjunctive query possibly including disequalities and negations:</p>
<br>
<p>• If there is a constant bound on the arity of 𝜑, and if the randomised Exponential Time Hypothesis (rETH) holds, then the
problem has a fixed-parameter tractable approximation scheme (FPTRAS) if and only if the treewidth of 𝜑 is bounded.</p>
<p>• If the arity is unbounded and 𝜑 does not have negations, then the problem has an FPTRAS if and only if the adaptive width of
𝜑 (a width measure strictly more general than treewidth) is bounded; the lower bound relies on the rETH as well.</p>
<br>
<p>Additionally we show that our results cannot be strengthened to achieve a fully polynomial randomised approximation scheme
(FPRAS): We observe that, unless NP = RP, there is no FPRAS even if the treewidth (and the adaptive width) is 1.</p>
<p>However, if there are neither disequalities nor negations, we prove the existence of an FPRAS for queries of bounded fractional
hypertreewidth, strictly generalising the recently established FPRAS for conjunctive queries with bounded hypertreewidth due to
Arenas, Croquevielle, Jayaram and Riveros (STOC 2021).</p> |
| first_indexed | 2024-09-25T04:24:07Z |
| format | Journal article |
| id | oxford-uuid:c88750ff-7dda-4c05-9a55-5701b18e8edf |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:15:07Z |
| publishDate | 2024 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:c88750ff-7dda-4c05-9a55-5701b18e8edf2024-10-18T08:47:32ZApproximately counting answers to conjunctive queries with disequalities and negationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:c88750ff-7dda-4c05-9a55-5701b18e8edfEnglishSymplectic ElementsAssociation for Computing Machinery2024Focke, JGoldberg, LRoth, MZivny, S<p>We study the complexity of approximating the number of answers to a small query 𝜑 in a large database D. We establish an exhaustive classification into tractable and intractable cases if 𝜑 is a conjunctive query possibly including disequalities and negations:</p> <br> <p>• If there is a constant bound on the arity of 𝜑, and if the randomised Exponential Time Hypothesis (rETH) holds, then the problem has a fixed-parameter tractable approximation scheme (FPTRAS) if and only if the treewidth of 𝜑 is bounded.</p> <p>• If the arity is unbounded and 𝜑 does not have negations, then the problem has an FPTRAS if and only if the adaptive width of 𝜑 (a width measure strictly more general than treewidth) is bounded; the lower bound relies on the rETH as well.</p> <br> <p>Additionally we show that our results cannot be strengthened to achieve a fully polynomial randomised approximation scheme (FPRAS): We observe that, unless NP = RP, there is no FPRAS even if the treewidth (and the adaptive width) is 1.</p> <p>However, if there are neither disequalities nor negations, we prove the existence of an FPRAS for queries of bounded fractional hypertreewidth, strictly generalising the recently established FPRAS for conjunctive queries with bounded hypertreewidth due to Arenas, Croquevielle, Jayaram and Riveros (STOC 2021).</p> |
| spellingShingle | Focke, J Goldberg, L Roth, M Zivny, S Approximately counting answers to conjunctive queries with disequalities and negations |
| title | Approximately counting answers to conjunctive queries with disequalities and negations |
| title_full | Approximately counting answers to conjunctive queries with disequalities and negations |
| title_fullStr | Approximately counting answers to conjunctive queries with disequalities and negations |
| title_full_unstemmed | Approximately counting answers to conjunctive queries with disequalities and negations |
| title_short | Approximately counting answers to conjunctive queries with disequalities and negations |
| title_sort | approximately counting answers to conjunctive queries with disequalities and negations |
| work_keys_str_mv | AT fockej approximatelycountinganswerstoconjunctivequerieswithdisequalitiesandnegations AT goldbergl approximatelycountinganswerstoconjunctivequerieswithdisequalitiesandnegations AT rothm approximatelycountinganswerstoconjunctivequerieswithdisequalitiesandnegations AT zivnys approximatelycountinganswerstoconjunctivequerieswithdisequalitiesandnegations |