English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the complexity of various fundamental counting problems that arisein the context of incomplete databases, i.e., relational databases that cancontain unknown values in the form of labeled nulls. Specifically, we assumethat the domains of these unknown values are finite and, for a Boolean query$q$, we consider the following two problems: given as input an incompletedatabase $D$, (a) return the number of completions of $D$ that satisfy $q$; or(b) return the number of valuations of the nulls of $D$ yielding a completionthat satisfies $q$. We obtain dichotomies between \#P-hardness andpolynomial-time computability for these problems when $q$ is a self-join-freeconjunctive query, and study the impact on the complexity of the following tworestrictions: (1) every null occurs at most once in $D$ (what is called Coddtables); and (2) the domain of each null is the same. Roughly speaking, we showthat counting completions is much harder than counting valuations: forinstance, while the latter is always in \#P, we prove that the former is not in\#P under some widely believed theoretical complexity assumption. Moreover, wefind that both (1) and (2) can reduce the complexity of our problems. We alsostudy the approximability of these problems and show that, while countingvaluations always has a fully polynomial-time randomized approximation scheme(FPRAS), in most cases counting completions does not. Finally, we consider moreexpressive query languages and situate our problems with respect to knowncomplexity classes.

The Complexity of Counting Problems over Incomplete Databases