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

Query evaluation over probabilistic databases is a notoriously intractableproblem -- not only in combined complexity, but for many natural queries indata complexity as well. This motivates the study of probabilistic queryevaluation through the lens of approximation algorithms, and particularly ofcombined FPRASes, whose runtime is polynomial in both the query and instancesize. In this paper, we focus on tuple-independent probabilistic databases overbinary signatures, which can be equivalently viewed as probabilistic graphs. Westudy in which cases we can devise combined FPRASes for probabilistic queryevaluation in this setting.  We settle the complexity of this problem for a variety of query and instanceclasses, by proving both approximability and (conditional) inapproximabilityresults. This allows us to deduce many corollaries of possible independentinterest. For example, we show how the results of Arenas et al. on countingfixed-length strings accepted by an NFA imply the existence of an FPRAS for thetwo-terminal network reliability problem on directed acyclic graphs: this wasan open problem until now. We also show that one cannot extend the recentresult of van Bremen and Meel that gives a combined FPRAS for self-join-freeconjunctive queries of bounded hypertree width on probabilistic databases:neither the bounded-hypertree-width condition nor the self-join-freenesshypothesis can be relaxed. Finally, we complement all our inapproximabilityresults with unconditional lower bounds, showing that DNNF provenance circuitsmust have at least moderately exponential size in combined complexity.

Conjunctive Queries on Probabilistic Graphs: The Limits of Approximability