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

Resilience is one of the key algorithmic problems underlying various forms ofreverse data management (such as view maintenance, deletion propagation, andvarious interventions for fairness): What is the minimal number of tuples todelete from a database in order to remove all answers from a query? A long-openquestion is determining those conjunctive queries (CQs) for which this problemcan be solved in guaranteed PTIME. We shed new light on this and the relatedproblem of causal responsibility by proposing a unified Integer LinearProgramming (ILP) formulation. It is unified in that it can solve both priorstudied restrictions (e.g., self-join-free CQs under set semantics that allow aPTIME solution) and new cases (e.g., all CQs under set or bag semantics It isalso unified in that all queries and all instances are treated with the sameapproach, and the algorithm is guaranteed to terminate in PTIME for the easycases. We prove that, for all easy self-join-free CQs, the Linear Programming(LP) relaxation of our encoding is identical to the ILP solution and thusstandard ILP solvers are guaranteed to return the solution in PTIME. Ourapproach opens up the door to new variants and new fine-grained analysis: 1) Italso works under bag semantics and we give the first dichotomy result for bagssemantics in the problem space. 2) We give a more fine-grained analysis of thecomplexity of causal responsibility. 3) We recover easy instances for generallyhard queries, such as instances with read-once provenance and instances thatbecome easy because of Functional Dependencies in the data. 4) We solve an openconjecture from PODS 2020. 5) Experiments confirm that our results indeedpredict the asymptotic running times, and that our universal ILP encoding is attimes even faster to solve for the PTIME cases than a prior proposed dedicatedflow algorithm.

A Unified Approach for Resilience and Causal Responsibility with Integer Linear Programming (ILP) and LP Relaxations