CISPA
Browse

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations

Download (403.47 kB)
conference contribution
posted on 2023-11-29, 18:19 authored by Jacob FockeJacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Živný
We study the complexity of approximating the number of answers to a small query \varphi in a large database D. We establish an exhaustive classification into tractable and intractable cases if \varphi is a conjunctive query possibly including disequalities and negations: - If there is a constant bound on the arity of \varphi, 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 \varphi is bounded. - If the arity is unbounded and \varphi does not have negations, then the problem has an FPTRAS if and only if the adaptive width of \varphi (a width measure strictly more general than treewidth) is bounded; the lower bound relies on the rETH as well. 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. 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).

History

Preferred Citation

Jacob Focke, Leslie Goldberg, Marc Roth and Stanislav Živný. Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations. In: ACM SIGMOD-SIGACT-SIGART Conference on Principles of Database Systems (PODS). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM SIGMOD-SIGACT-SIGART Conference on Principles of Database Systems (PODS)

Legacy Posted Date

2022-03-24

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3591, title = "Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations", author = "Focke, Jacob and Goldberg, Leslie Ann and Roth, Marc and Živný, Stanislav", booktitle="{ACM SIGMOD-SIGACT-SIGART Conference on Principles of Database Systems (PODS)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC