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 consider the problem of finding the minimal-size factorization of theprovenance of self-join-free conjunctive queries, i.e., we want to find aformula that \emph{minimizes the number of variable repetitions}. This problemis equivalent to solving the fundamental Boolean formula factorization problemfor the restricted setting of the provenance formulas of self-join freequeries. While general Boolean formula minimization is $\Sigma^p_2$-complete,we show that the problem is NP-C in our case. Additionally, we identify a largecategory of queries that can be solved in PTIME, expanding beyond thepreviously known tractable cases of read-once formulas and hierarchicalqueries.  We describe connections between factorizations, variable elimination ordersand minimal query plans. We leverage these insights to create an Integer LinearProgram (ILP) that can solve the minimal factorization problem exactly. We alsopropose a Max-Flow Min-Cut (MFMC) based algorithm that gives an efficientapproximate solution. Importantly, we show that both the Linear Programming(LP) relaxation of our proposed ILP, and our MFMC based algorithm are\emph{always correct for all known PTIME cases}. Thus, we present two unifiedalgorithms that can recover all known PTIME cases in PTIME, yet also solve NP-Ccases exactly or approximately as desired.

Towards a Dichotomy for Minimally Factorizing the Provenance of Self-Join Free Conjunctive Queries