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

Quantifying the contribution of database facts to query answers has beenstudied as means of explanation. The Banzhaf value, originally developed inGame Theory, is a natural measure of fact contribution, yet its efficientcomputation for select-project-join-union queries is challenging. In thispaper, we introduce three algorithms to compute the Banzhaf value of databasefacts: an exact algorithm, an anytime deterministic approximation algorithmwith relative error guarantees, and an algorithm for ranking and top-$k$. Theyhave three key building blocks: compilation of query lineage into an equivalentfunction that allows efficient Banzhaf value computation; dynamic programmingcomputation of the Banzhaf values of variables in a Boolean function using theBanzhaf values for constituent functions; and a mechanism to computeefficiently lower and upper bounds on Banzhaf values for any positive DNFfunction.  We complement the algorithms with a dichotomy for the Banzhaf-based rankingproblem: given two facts, deciding whether the Banzhaf value of one is greaterthan of the other is tractable for hierarchical queries and intractable fornon-hierarchical queries.  We show experimentally that our algorithms significantly outperform exact andapproximate algorithms from prior work, most times up to two orders ofmagnitude. Our algorithms can also cover challenging problem instances that arebeyond reach for prior work.

Banzhaf Values for Facts in Query Answering