Pith. sign in

REVIEW 3 major objections 5 minor 26 references

For FD-constrained join queries, lexicographic direct access with linear preprocessing is achievable exactly when every bag of the reordered disruption-free decomposition is determined by a single atom together with the dependencies.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 03:27 UTC pith:ARUFA32O

load-bearing objection Solid conditional frontier result for direct access under FDs; the lower-bound proof has a real π/π′ gap that needs fixing before the dichotomy is fully established. the 3 major comments →

arxiv 2607.13875 v1 pith:ARUFA32O submitted 2026-07-15 cs.DB

Lexicographic Direct Access with Functional Dependencies

Florent Capelli , Nofar Carmeli , Stefan Mengel This is my paper
classification cs.DB MSC 68P1568Q25
keywords join querieslexicographic direct accessfunctional dependenciesdisruption-free decompositionpolymatroid boundcolor numberZero-Clique Conjecturefine-grained complexity
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Lexicographic direct access asks a database system to answer, after a preprocessing phase, "what is the j-th answer to a query in a chosen order?" in logarithmic time. This paper asks how functional dependencies (FDs) change the minimum preprocessing needed, and gives a nearly complete answer. For unary FDs the optimal preprocessing exponent is now known exactly: it is the incompatibility number of the query after incorporating the FDs, tight up to sub-polynomial factors. For general FDs the paper proves a dichotomy: linear preprocessing suffices if and only if every bag of a certain decomposition, built after reordering variables to respect the FDs, is guarded by a single atom, meaning the atom's variables plus the FDs determine all bag variables. The negative direction is conditional on the Zero-Clique Conjecture, and the dichotomy covers all self-join-free join queries.

Core claim

The paper's central result is a complete dichotomy for lexicographic direct access to self-join-free join queries under functional dependencies, assuming the Zero-Clique Conjecture (Theorem 6.1). After reordering the variable order to respect the FDs (a Δ-reordering), one builds the disruption-free decomposition of the query; preprocessing time O(|D|) with O(log |D|) access time is possible if and only if every bag of that decomposition is Δ-guarded — that is, some atom of the query together with the functional dependencies determines all variables of the bag. The positive direction is an algorithm that materializes each bag using the paper's information-theoretic evaluation algorithm, PANDA

What carries the argument

The argument rests on three objects. (1) The Δ-reordering of the variable order places each FD-implied variable directly after the variables that determine it; it never changes the output order and never increases either width measure. (2) The disruption-free decomposition is a hypergraph whose bags record, for each variable, which earlier variables it interacts with through the query; the maximum polymatroid bound P_{Q,Δ}(B_i) over the bags bounds the preprocessing time of the algorithm, while the maximum color number C_{Q,Δ}(B_i) (the FD-aware incompatibility number) supplies the lower bound. (3) The dichotomy pivots on a lemma that C_{Q,Δ}(S)=1 exactly when S is Δ-guarded, i.e., when a si

Load-bearing premise

All lower bounds rest on the Zero-Clique Conjecture (that finding a zero-weight k-clique in an n-node graph requires near n^k time), and the dichotomy is proved only for queries without self-joins.

What would settle it

Exhibit a self-join-free join query, an FD set, and a variable order such that some bag of the Δ-reordered disruption-free decomposition is not Δ-guarded, yet lexicographic direct access still runs in linear preprocessing time and logarithmic access time — that would refute the dichotomy's only-if direction, independent of the conjecture.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • The linear-preprocessing frontier is fully mapped: any query, order, and FD set whose bags are not all Δ-guarded needs superlinear preprocessing (assuming the Zero-Clique Conjecture), so no cleverer algorithm can cross that boundary.
  • For unary FDs the optimal preprocessing exponent is exactly the incompatibility number of the reordered extension, an integer computable by linear programming, so the hardness of a concrete instance can be read off mechanically.
  • The information-theoretic algorithm is never worse than the extension-based reduction and sometimes strictly better, so the recommended pipeline is always: Δ-reorder, build the decomposition, materialize the bags.
  • FDs can substantially shrink the polymatroid width — from k−1 down to 1 in the paper's star-query example — meaning declared constraints can turn a high-polynomial preprocessing problem into a near-linear one.
  • Because direct access supports quantiles, histograms, and sampling without repetition, the dichotomy identifies exactly which FD-constrained databases admit these operations with near-linear preprocessing.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The Δ-guarded condition reads like a query-language criterion — a bag is cheap when one atom, closed under FDs, determines it. A similar guardedness criterion may characterize other FD-constrained tasks such as constant-delay enumeration or counting, where the extension approach was previously believed sufficient.
  • The gap between the polymatroid width (upper bound) and the color-number width (lower bound) is left open and can be arbitrarily large; closing it would require knowing when the polymatroid bound coincides with the entropic bound, so tighter results for general FDs would likely need new information-theoretic inequalities, not just faster join algorithms.
  • A testable extension: the same machinery is expected to transfer to degree constraints and other cardinality constraints supported by the underlying evaluation algorithm; if so, the guarded-bag dichotomy may generalize to a broader class of integrity constraints.
  • The reordering observation — that FDs let dependent variables move earlier in the lexicographic order at no cost — is a property database optimizers could exploit beyond direct access, since it preserves answer order for any downstream task.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies lexicographic direct access to join query answers over databases satisfying functional dependencies (FDs). It proposes two approaches: (i) a reordered-extension reduction, for which it shows tight bounds for unary FDs but failure for general FDs; and (ii) an information-theoretic/PANDA-based algorithm whose preprocessing is governed by a new disruption-free polymatroid width, with matching lower bounds (up to gaps) expressed through an FD-aware incompatibility/color number. The main result, Theorem 6.1, is a dichotomy characterizing, under the Zero-Clique Conjecture, the self-join-free join queries with FDs that admit lexicographic direct access with linear preprocessing and logarithmic access time: the condition is that every bag of the disruption-free decomposition of a Δ-reordering is Δ-guarded. The paper is careful in stating its limitations: the general width bounds are not tight, and all lower bounds rely on the Zero-Clique Conjecture and exclude self-joins.

Significance. If the central claims are correct, the paper gives the first complete linear-preprocessing characterization for lexicographic direct access under general FDs, a substantial advance over prior unary-FD results. The unary-FD result (Corollary 3.7) is tight up to subpolynomial factors and generalizes earlier work cleanly. The use of the color number and polymatroid bound in the context of disruption-free decompositions is a natural and promising technical contribution, as is the modularization-lemma comparison of the two approaches. The paper is also honest about the fact that its upper and lower bounds are generally not tight, and that this is tied to the lack of worst-case optimal join algorithms for FDs. If the proof gaps identified below are repaired, the paper would be a strong fit for a top database theory venue.

major comments (3)
  1. [Lemma 5.6, §5.2] The proof of Lemma 5.6 mixes the original order π and the Δ-reordering π′ in a way that is not justified by the statement. The lemma assumes only that π′ is a Δ-reordering of π; π itself need not be consistent with Δ. Yet the proof says 'Let vt be the last variable in π that introduces a color', defines Bt as 'the bag in which vt is the last variable with respect to π', uses the decomposition for π in Claim C.3, and in Claim C.2 asserts 'As π is consistent with the FDs'. The coloring from Lemma C.1 is obtained from 'some bag B of the disruption-free decomposition' without specifying whether the decomposition is for π or π′. Since C_{Q,Δ}-width(Q,π′) is defined using π′, the bag B must be a bag of the π′-decomposition. Unless π=π′, the chain of bags B_{i1},...,B_{iℓ} in Claim C.3 is not a valid chain in that decomposition, so the proof does not establish the stated coloring. Because Lemma
  2. [Lemma 5.5, §5.2] The proof of Lemma 5.5 is only a sketch, and the construction omits an important case. For an atom R(v1,...,vn) of Q, the construction joins the star relations corresponding to the colors of [k] appearing in L(v1)∪...∪L(vn). If this set is empty, the text says to compute the join of zero relations, which does not produce values for x_{k+1}; the construction would silently add a single fact with all coordinates set to ⊥. Such atoms can occur in the coloring produced by Lemma 5.6: after adding the fresh color k+1 to all variables of S_t, an atom entirely inside S_t may carry no colors from [k]. It would then fail to encode the different x_{k+1}-values of D⋆, breaking the claimed bijection. The sentence 'It can be shown that the construction encodes...' is not a substitute for handling this case. Since Lemma 5.5 is the reduction step for all lower bounds in Section 5 and for the 'only if' d
  3. [Theorem 6.1, §6] The 'only if' direction of Theorem 6.1 is stated as a proof sketch that relies directly on Lemma 6.3 and Theorem 5.7. Given the issues in Lemmas 5.5 and 5.6, the dichotomy's negative direction is not fully established in the submitted text. This is not a challenge to the upper bound, which follows from Lemma 6.2 and the decomposition argument, but it means the central 'if and only if' is currently conditional on repaired lower-bound proofs.
minor comments (5)
  1. [Lemma 5.5/5.6, §5.2] Labeling these results as 'Proof sketch' is risky for results that carry the main lower-bound weight. The final version should include full proofs in the appendix, not sketches in the main text.
  2. [Section 7] There is a typo: 'Deonte byQ+' should be 'Denote by Q+'.
  3. [Section 3.1, Corollary 3.7] The lower bound in Corollary 3.7 states the optimality claim only for preprocessing O(|D|^{ι-ε}) and access O(|D|^δ). This is correct but could be stated more explicitly as 'up to subpolynomial factors' to match the informal discussion.
  4. [Author list] The second author affiliation line contains a typesetting artifact ('Carmeli/envel⌢pe'); this should be corrected.
  5. [Lemma 6.4] The notation σ_{R_i(X_i)} as both a variable name and subscript is slightly confusing; consider using σ_i.

Circularity Check

0 steps flagged

No significant circularity; the lower and upper bounds are genuine reductions to independent prior theorems, with at most non-load-bearing self-citations.

full rationale

Every main result is derived by constructing either an exact reduction or a width measure rather than by renaming an input. Corollary 3.7 is based on exact reductions in both directions (Thm 3.4/3.6) between (Q,pi,Delta) and the FD-free reordered extension; hardness flows from the k-star lower bound (Thm 2.1) under the Zero-Clique Conjecture, not from any FD-specific assumption. Theorem 4.3 materializes disruption-free bags using PANDA; the runtime exponent P_{Q,Delta}-width is defined from an LP, not fitted. Theorem 5.7's lower bound uses the color-number width, and Prop 5.9 shows that this width is at most the algorithm's width, so the lower bound is not the algorithm restated. Theorem 6.1 reduces to Lemma 6.3 (guardedness iff color number 1), proved by LP duality; this is a combinatorial lemma independent of the direct-access result. The paper itself notes in Section 8 that the bounds are not tight in general and that lower bounds rely on the Zero-Clique Conjecture; that is a limitation and a conditional-hardness caveat, not circularity. The only author-overlap citations are [11], [13], and [14], used as published black-box theorems (e.g., the exact reductions of Carmeli-Kroell and the direct-access machinery of Bringmann et al.); these do not assume the target theorem, so they do not make the derivation circular. The abbreviated proof sketches of Lemmas 5.5 and 5.6 might leave correctness gaps, but that is a proof-completeness issue, not a self-referential reduction. No fitted constants appear, no quantity is both fit and predicted, and no known result is merely renamed as a new contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No data-fitting or hand-tuned constants appear; all widths and bounds are functions of the query, order, FD set, and database size. The main external assumptions are the Zero-Clique Conjecture, the self-join-free restriction for lower bounds, and prior published theorems taken as background.

axioms (5)
  • domain assumption Zero-Clique Conjecture: for every k≥3, Zero-k-Clique has no randomized algorithm running in O(n^{k-ε}) time for any ε>0.
    Used in Theorem 2.1 and all negative results (Corollary 3.7, Theorem 5.7, Theorem 6.1); if false, the conditional lower bounds fail.
  • domain assumption All lower bounds and the main dichotomy are restricted to self-join-free queries.
    The abstract and Section 1 restrict hardness results to queries without self-joins; the simplified color number and Lemma 5.5 rely on this.
  • standard math Prior published theorems are used as black boxes: direct access without FDs (Theorem 2.3, [11]), PANDA algorithm (Theorem 2.4, [4,5]), exact reductions of Carmeli-Kröll [13], and direct access for acyclic decompositions [11,14].
    These are established results with proofs; the paper's contribution is built on them and does not re-derive them.
  • domain assumption FDs are assumed normalized to single-head form R_i:A→b and expressed using query variables.
    Section 2 follows [14, Section 8]; all definitions and proofs assume this normal form.
  • domain assumption Word-RAM computation model with O(log n)-bit words and unit-cost operations.
    Section 2 fixes the model for direct-access algorithms and lower-bound reductions.

pith-pipeline@v1.3.0-alltime-deepseek · 30976 in / 18595 out tokens · 185738 ms · 2026-08-02T03:27:20.411886+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Lexicographic Direct Access with Functional Dependencies." pith.science (2026). https://pith.science/paper/ARUFA32O

@misc{pith2026260713875,
  author       = {Pith},
  title        = {Pith review of: Lexicographic Direct Access with Functional Dependencies},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ARUFA32O}},
  note         = {Machine review of arXiv:2607.13875}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We study the complexity of lexicographic direct access to join query answers over databases that satisfy functional dependencies (FDs). More precisely, we give fine-grained lower and upper bounds on the preprocessing time required to achieve polylogarithmic access time. We start by considering the simple approach of a reordered extension, which first incorporates the FDs in the query and order, and then ignores the FDs during evaluation. We show that this simple approach gives tight bounds for unary FDs but fails for general FDs. We then consider a second approach, inspired by size bounds for query answers using information theory, that takes the FDs into account while materializing the bags of a decomposition tailored to the direct access task at hand. Interestingly, we show that the same reordering is also useful while constructing the decomposition in this second approach for reducing the complexity. While the obtained upper and lower bounds are generally not tight, we show that they yield a complete characterization of lexicographic direct access with linear preprocessing time. All lower bounds in this paper apply only to queries without self-joins and rely on the Zero-Clique Conjecture.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 6 canonical work pages

  1. [1]

    Foundations of Databases

    Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases . Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/

    1995

  2. [2]

    Fast matrix multiplication meets the submodular width

    Mahmoud Abo Khamis , Xiao Hu, and Dan Suciu. Fast matrix multiplication meets the submodular width. Proc. ACM Manag. Data , 3(2):98:1--98:26, 2025. https://doi.org/10.1145/3725235 doi:10.1145/3725235

    doi:10.1145/3725235 2025

  3. [3]

    Computing join queries with functional dependencies

    Mahmoud Abo Khamis , Hung Q Ngo, and Dan Suciu. Computing join queries with functional dependencies. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , pages 327--342, 2016

    2016

  4. [4]

    Ngo, and Dan Suciu

    Mahmoud Abo Khamis , Hung Q. Ngo, and Dan Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? CoRR , abs/1612.02503, 2016. URL: http://arxiv.org/abs/1612.02503, https://arxiv.org/abs/1612.02503 arXiv:1612.02503

    Pith/arXiv arXiv 2016

  5. [5]

    Ngo, and Dan Suciu

    Mahmoud Abo Khamis , Hung Q. Ngo, and Dan Suciu. PANDA: query evaluation in submodular width. TheoretiCS , 4, 2025. URL: https://doi.org/10.46298/theoretics.25.12, https://doi.org/10.46298/THEORETICS.25.12 doi:10.46298/THEORETICS.25.12

    doi:10.46298/theoretics.25.12 2025

  6. [6]

    Ngo, and Dan Suciu

    Mahmoud Abo Khamis , Hung Q. Ngo, and Dan Suciu. Pandaexpress: a simpler and faster PANDA algorithm. CoRR , abs/2512.10217, 2025. URL: https://doi.org/10.48550/arXiv.2512.10217, https://arxiv.org/abs/2512.10217 arXiv:2512.10217 , https://doi.org/10.48550/ARXIV.2512.10217 doi:10.48550/ARXIV.2512.10217

    Pith/arXiv arXiv doi:10.48550/arxiv.2512.10217 2025

  7. [7]

    Width functions for hypertree decompositions (Weitefunktionen f \" u r Hyperbaumzerlegungen)

    Isolde Adler. Width functions for hypertree decompositions (Weitefunktionen f \" u r Hyperbaumzerlegungen) . PhD thesis, University of Freiburg, Germany, 2006. URL: https://freidok.uni-freiburg.de/data/2468

    2006

  8. [8]

    Computing the jth solution of a first-order query

    Guillaume Bagan, Arnaud Durand, Etienne Grandjean, and Fr \' e d \' e ric Olive. Computing the jth solution of a first-order query. RAIRO Theor. Informatics Appl. , 42(1):147--164, 2008. https://doi.org/10.1051/ita:2007046 doi:10.1051/ita:2007046

    work page doi:10.1051/ita:2007046 2008

  9. [9]

    Constant delay enumeration for conjunctive queries: a tutorial

    Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt. Constant delay enumeration for conjunctive queries: a tutorial. ACM SIGLOG News , 7(1):4--33, 2020. https://doi.org/10.1145/3385634.3385636 doi:10.1145/3385634.3385636

    arXiv 2020

  10. [10]

    De la pertinence de l’ \'e num \'e ration: complexit \'e en logiques propositionnelle et du premier ordre

    Johann Brault-Baron. De la pertinence de l’ \'e num \'e ration: complexit \'e en logiques propositionnelle et du premier ordre . PhD thesis, Universit \'e de Caen, 2013

    2013

  11. [11]

    Tight fine-grained bounds for direct access on join queries

    Karl Bringmann, Nofar Carmeli, and Stefan Mengel. Tight fine-grained bounds for direct access on join queries. ACM Trans. Database Syst. , 50(1):1:1--1:44, 2025. https://doi.org/10.1145/3707448 doi:10.1145/3707448

    work page doi:10.1145/3707448 2025

  12. [12]

    A simple algorithm for worst case optimal join and sampling

    Florent Capelli, Oliver Irwin, and Sylvain Salvati. A simple algorithm for worst case optimal join and sampling. In Sudeepa Roy and Ahmet Kara, editors, 28th International Conference on Database Theory, ICDT 2025, Barcelona, Spain, March 25-28, 2025 , volume 328 of LIPIcs , pages 23:1--23:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2025. U...

    work page doi:10.4230/lipics.icdt.2025.23 2025

  13. [13]

    Enumeration complexity of conjunctive queries with functional dependencies

    Nofar Carmeli and Markus Kr \"o ll. Enumeration complexity of conjunctive queries with functional dependencies. Theory of Computing Systems , 64(5):828--860, 2020

    2020

  14. [14]

    Tractable orders for direct access to ranked answers of conjunctive queries

    Nofar Carmeli, Nikolaos Tziavelis, Wolfgang Gatterbauer, Benny Kimelfeld, and Mirek Riedewald. Tractable orders for direct access to ranked answers of conjunctive queries. ACM Transactions on Database Systems , 48(1):1--45, 2023

    2023

  15. [15]

    Answering (unions of) conjunctive queries using random access and random-order enumeration

    Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Alessio Conte, Benny Kimelfeld, and Nicole Schweikardt. Answering (unions of) conjunctive queries using random access and random-order enumeration. ACM Transactions on Database Systems (TODS) , 47(3):1--49, 2022

    2022

  16. [16]

    Partition constraints for conjunctive queries: Bounds and worst-case optimal joins

    Kyle Deeds and Timo Camillo Merkl. Partition constraints for conjunctive queries: Bounds and worst-case optimal joins. In Sudeepa Roy and Ahmet Kara, editors, 28th International Conference on Database Theory, ICDT 2025, Barcelona, Spain, March 25-28, 2025 , volume 328 of LIPIcs , pages 17:1--17:18. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2...

    work page doi:10.4230/lipics.icdt.2025.17 2025

  17. [17]

    Fast join project query evaluation using matrix multiplication

    Shaleen Deep, Xiao Hu, and Paraschos Koutris. Fast join project query evaluation using matrix multiplication. In David Maier, Rachel Pottinger, AnHai Doan, Wang - Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo, editors, Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], Ju...

    arXiv 2020

  18. [18]

    Entropy bounds for conjunctive queries with functional dependencies

    Tomasz Gogacz and Szymon Torunczyk. Entropy bounds for conjunctive queries with functional dependencies. In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory, ICDT 2017, Venice, Italy, March 21-24, 2017 , volume 68 of LIPIcs , pages 15:1--15:17. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2017. URL: h...

    work page doi:10.4230/lipics.icdt.2017.15 2017

  19. [19]

    Size and treewidth bounds for conjunctive queries

    Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant. Size and treewidth bounds for conjunctive queries. J. ACM , 59(3):16:1--16:35, 2012. https://doi.org/10.1145/2220357.2220363 doi:10.1145/2220357.2220363

    arXiv 2012

  20. [20]

    Output-optimal algorithms for join-aggregate queries

    Xiao Hu. Output-optimal algorithms for join-aggregate queries. Proc. ACM Manag. Data , 3(2):104:1--104:27, 2025. https://doi.org/10.1145/3725241 doi:10.1145/3725241

    work page doi:10.1145/3725241 2025

  21. [21]

    A simple guide to five normal forms in relational database theory

    William Kent. A simple guide to five normal forms in relational database theory. Communications of the ACM , 26(2):120--125, 1983

    1983

  22. [22]

    Lower bounds based on the exponential time hypothesis

    Daniel Lokshtanov, D \' a niel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bull. EATCS , 105:41--72, 2011. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/92

    2011

  23. [23]

    Lower bounds for conjunctive query evaluation

    Stefan Mengel. Lower bounds for conjunctive query evaluation. In Floris Geerts and Benny Kimelfeld, editors, Companion of the 44th Symposium on Principles of Database Systems, PODS 2025, Berlin, Germany, June 22-27, 2025 , page 5. ACM , 2025. https://doi.org/10.1145/3722234.3725824 doi:10.1145/3722234.3725824

    arXiv 2025

  24. [24]

    Hung Q. Ngo. Worst-case optimal join algorithms: Techniques, results, and open problems. In Jan Van den Bussche and Marcelo Arenas, editors, Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018 , pages 111--124. ACM , 2018. https://doi.org/10.1145/3196959.3196990 doi:10.1145/319695...

    arXiv 2018

  25. [25]

    Ngo, Ely Porat, Christopher R \' e , and Atri Rudra

    Hung Q. Ngo, Ely Porat, Christopher R \' e , and Atri Rudra. Worst-case optimal join algorithms. J. ACM , 65(3):16:1--16:40, 2018. https://doi.org/10.1145/3180143 doi:10.1145/3180143

    doi:10.1145/3180143 2018

  26. [26]

    Veldhuizen

    Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014 , pages 96--106. OpenProceedings.org, 2014. URL: https://doi.org/10.5441/002/icdt.2014.13, https://doi.org/10....

    doi:10.5441/002/icdt.2014.13 2014