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

Recent years have seen exciting developments in join algorithms. In 2008,Atserias, Grohe and Marx (henceforth AGM) proved a tight bound on the maximumresult size of a full conjunctive query, given constraints on the inputrelation sizes. In 2012, Ngo, Porat, R{\'e} and Rudra (henceforth NPRR) deviseda join algorithm with worst-case running time proportional to the AGM bound.Our commercial Datalog system LogicBlox employs a novel join algorithm,\emph{leapfrog triejoin}, which compared conspicuously well to the NPRRalgorithm in preliminary benchmarks. This spurred us to analyze the complexityof leapfrog triejoin. In this paper we establish that leapfrog triejoin is alsoworst-case optimal, up to a log factor, in the sense of NPRR. We improve on theresults of NPRR by proving that leapfrog triejoin achieves worst-caseoptimality for finer-grained classes of database instances, such as thosedefined by constraints on projection cardinalities. We show that NPRR is\emph{not} worst-case optimal for such classes, giving a counterexample whereleapfrog triejoin runs in $O(n \log n)$ time, compared to $\Theta(n^{1.375})$time for NPRR. On a practical note, leapfrog triejoin can be implemented usingconventional data structures such as B-trees, and extends naturally to$\exists_1$ queries. We believe our algorithm offers a useful addition to theexisting toolbox of join algorithms, being easy to absorb, simple to implement,and having a concise optimality proof.

Leapfrog Triejoin: a worst-case optimal join algorithm