pith. sign in

arxiv: 2301.08178 · v4 · pith:4JPIUOZOnew · submitted 2023-01-19 · 💻 cs.DB · cs.LO

Work-Efficient Query Evaluation in Constant Time with PRAMs

Jens Keppeler , Thomas Schwentick , Christopher Spinrath This is my paper

Pith reviewed 2026-05-24 10:28 UTC · model grok-4.3

classification 💻 cs.DB cs.LO
keywords query evaluationCRCW PRAMconstant timework-efficient algorithmsrelational algebraacyclic queriessemijoin algebraworst-case optimal joins
0
0 comments X

The pith

Relational algebra queries can be evaluated in constant time on CRCW PRAMs with work O(T^{1+ε}) for any ε>0 relative to optimal sequential time T, under assumptions that data values have polynomial bit length or relations are sorted.

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

The paper establishes constant-time parallel algorithms for evaluating relational queries that keep total work within any superlinear polynomial factor of the best sequential running time. It develops these bounds specifically for acyclic queries, queries in the semijoin algebra, and join queries handled by worst-case optimal algorithms. The methods first handle individual relational operators and then compose them while using parallel primitives to avoid the polynomial processor blow-up and scattered memory layout of naive approaches. A reader would care because the results show how constant parallel time can be achieved without paying an arbitrarily large work penalty, provided the input satisfies the stated size or ordering conditions.

Core claim

Under the assumptions that data values are numbers of polynomial size in the size of the database or that the relations are suitably sorted, constant-time CRCW PRAM algorithms exist that evaluate the queries with work O(T^{1+ε}) for every ε>0, where T is the running time of an optimal sequential algorithm. The algorithms cover the evaluation of relational operators in general and are instantiated for acyclic queries, semijoin algebra queries, and worst-case optimal join queries. They rely on approximate prefix sums and compaction to control work and memory layout.

What carries the argument

Approximate prefix sums and compaction algorithms that reorganize data and compute partial sums in constant time with controlled work, enabling efficient composition of relational operators on the CRCW PRAM.

If this is right

  • Acyclic queries admit constant-time PRAM evaluation whose work is O(T^{1+ε}) for any ε>0.
  • Semijoin algebra queries can be evaluated under the same constant-time and work bounds.
  • Worst-case optimal join algorithms extend to constant-time PRAM versions with the stated work guarantee.
  • Result sets produced by the algorithms occupy contiguous or easily compactible memory locations rather than being arbitrarily scattered.
  • All relational algebra queries remain evaluable in constant time, but the work bound holds only inside the three identified settings.

Where Pith is reading between the lines

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

  • The same primitives could be reused to obtain work-efficient constant-time algorithms for other data-processing tasks whose sequential versions already run in near-linear time.
  • If hardware implementations of approximate prefix sums become available, the approach would directly translate to low-latency parallel query engines on shared-memory multiprocessors.
  • Relaxing the polynomial-size assumption on data values would require new compaction techniques that still run in constant time.

Load-bearing premise

Data values are numbers whose bit length is polynomial in the database size, or the input relations are already sorted in a suitable order.

What would settle it

An explicit database instance obeying the polynomial-size or sorted-relation assumption, together with a query from one of the three covered classes, for which every constant-time CRCW PRAM algorithm requires work larger than T^{1+ε} for some fixed ε>0.

read the original abstract

The article studies query evaluation in parallel constant time in the CRCW PRAM model. While it is well-known that all relational algebra queries can be evaluated in constant time on an appropriate CRCW PRAM model, this article is interested in the efficiency of evaluation algorithms, that is, in the number of processors or, asymptotically equivalent, in the work. Naive evaluation in the parallel setting results in huge (polynomial) bounds on the work of such algorithms and in presentations of the result sets that can be extremely scattered in memory. The article discusses some obstacles for constant-time PRAM query evaluation. It presents algorithms for relational operators and explores three settings, in which efficient sequential query evaluation algorithms exist: acyclic queries, semijoin algebra queries, and join queries -- the latter in the worst-case optimal framework. Under mild assumptions -- that data values are numbers of polynomial size in the size of the database or that the relations of the database are suitably sorted -- constant-time algorithms are presented that are weakly work-efficient in the sense that work $\mathcal{O}(T^{1+\varepsilon})$ can be achieved, for every $\varepsilon>0$, compared to the time $T$ of an optimal sequential algorithm. Important tools are the algorithms for approximate prefix sums and compaction from Goldberg and Zwick (1995).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper claims that, in the CRCW PRAM model and under the mild assumptions that data values have polynomial bit length or that input relations are suitably sorted, constant-time algorithms exist for evaluating acyclic queries, semijoin-algebra queries, and worst-case-optimal join queries. These algorithms are weakly work-efficient, achieving work O(T^{1+ε}) for every ε>0 relative to the running time T of an optimal sequential algorithm, by building on the approximate-prefix-sum and compaction primitives of Goldberg and Zwick (1995).

Significance. If the constructions are correct, the work supplies the first constant-time, nearly work-optimal PRAM algorithms for the three standard settings in which sequential query evaluation is known to be efficient. It thereby closes a gap between the well-known constant-time PRAM upper bound for arbitrary relational algebra and the desire for work bounds that remain close to the sequential optimum.

minor comments (2)
  1. [§1] The abstract and introduction state the polynomial-size or sorted-relation assumptions but do not indicate whether these assumptions are used only for the constant-time bound or also for the work bound; a short clarifying sentence in §1 would help.
  2. Notation for the work measure W(n) versus the sequential time T is introduced without an explicit comparison table; adding one would make the weakly-work-efficient claim easier to verify at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, the positive summary, and the recommendation to accept the paper. No major comments were raised that require a point-by-point response.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central results consist of algorithms for constant-time PRAM evaluation of relational queries (acyclic, semijoin, worst-case optimal joins) that achieve weakly work-efficient bounds O(T^{1+ε}) relative to sequential time T. These rest on external, non-self-cited primitives for approximate prefix sums and compaction from Goldberg and Zwick (1995), together with explicitly stated mild assumptions on data values or sorting. No derivation step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the claims are independent of the paper's own outputs and rely on standard CRCW PRAM techniques.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard CRCW PRAM model and one external algorithmic primitive; no free parameters or invented entities are introduced.

axioms (2)
  • standard math CRCW PRAM model permits concurrent reads and writes with appropriate conflict resolution
    Invoked as the computational model throughout the abstract.
  • domain assumption Approximate prefix sums and compaction algorithms of Goldberg and Zwick (1995) run in constant time with the stated work bounds
    Explicitly cited as the key tool enabling the constant-time property.

pith-pipeline@v0.9.0 · 5763 in / 1212 out tokens · 27314 ms · 2026-05-24T10:28:58.769455+00:00 · methodology

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

53 extracted references · 53 canonical work pages

  1. [1]

    An optimal O(log log N) -time parallel algorithm for detecting all squares in a string

    Alberto Apostolico and Dany Breslauer. An optimal O(log log N) -time parallel algorithm for detecting all squares in a string. SIAM Journal on Computing , 25(6):1318--1331, 1996. https://doi.org/10.1137/S0097539793260404 doi:10.1137/S0097539793260404

    work page doi:10.1137/s0097539793260404 1996

  2. [2]

    Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve

    Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin K \" u nnemann. Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 192--203. IEEE, 2017. https://doi.org/10.1109/FOCS.2017.26 doi:10.1109/FOCS.2017.26

    work page doi:10.1109/focs.2017.26 2017

  3. [3]

    Database Theory

    Marcelo Arenas, Pablo Barcel\'o, Leonid Libkin, Wim Martens, and Andreas Pieris. Database Theory . Open source at https://github.com/pdm-book/community, 2021. Preliminary Version, August 19, 2022

    work page 2021

  4. [4]

    If the current clique algorithms are optimal, so is Valiant's parser

    Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is Valiant's parser. In IEEE 56th Annual Symposium on Foundations of Computer Science , pages 98--117. IEEE, 2015. https://doi.org/10.1109/FOCS.2015.16 doi:10.1109/FOCS.2015.16

    work page doi:10.1109/focs.2015.16 2015

  5. [5]

    Size bounds and query plans for relational joins

    Albert Atserias, Martin Grohe, and D \' a niel Marx. Size bounds and query plans for relational joins. SIAM Journal on Computing , 42(4):1737--1767, 2013. https://doi.org/10.1137/110859440 doi:10.1137/110859440

    work page doi:10.1137/110859440 2013

  6. [6]

    Foundations of Databases

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

    work page 1995

  7. [7]

    Approximate counting with uniform constant-depth circuits

    Mikl \' o s Ajtai. Approximate counting with uniform constant-depth circuits. In Jin - Yi Cai, editor, Advances In Computational Complexity Theory, Proceedings of a DIMACS Workshop, New Jersey, USA, December 3-7, 1990 , volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science , pages 1--20. American Mathematical Society, 1993. h...

    work page doi:10.1090/dimacs/013/01 1990

  8. [8]

    On parallel constant-time string algorithms

    Daniel Albert. On parallel constant-time string algorithms. Master's thesis, 2024

    work page 2024

  9. [9]

    Tight comparison bounds on the complexity of parallel sorting

    Yossi Azar and Uzi Vishkin. Tight comparison bounds on the complexity of parallel sorting. SIAM Journal on Computing , 16(3):458--464, 1987. https://doi.org/10.1137/0216032 doi:10.1137/0216032

    work page doi:10.1137/0216032 1987

  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 . Theses, Universit \'e de Caen , April 2013. URL: https://hal.archives-ouvertes.fr/tel-01081392

    work page 2013

  11. [11]

    On acyclic conjunctive queries and constant delay enumeration

    Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings , volume 4646 of Lecture Note...

    work page doi:10.1007/978-3-540-74915-8_18 2007

  12. [12]

    Bernstein and Nathan Goodman

    Philip A. Bernstein and Nathan Goodman. Power of natural semijoins. SIAM Journal on Computing , 10(4):751--771, 1981. https://doi.org/10.1137/0210059 doi:10.1137/0210059

    work page doi:10.1137/0210059 1981

  13. [13]

    Mix Barrington, Neil Immerman, and Howard Straubing

    David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC \( ^1 \) . Journal of Computer and System Sciences , 41(3):274--306, 1990. https://doi.org/10.1016/0022-0000(90)90022-D doi:10.1016/0022-0000(90)90022-D

    work page doi:10.1016/0022-0000(90)90022-d 1990

  14. [14]

    Communication steps for parallel query processing

    Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. Journal of the ACM , 64(6):40:1--40:58, 2017. https://doi.org/10.1145/3125644 doi:10.1145/3125644

    work page doi:10.1145/3125644 2017

  15. [15]

    Efficient String Algorithmics

    Dany Breslauer. Efficient String Algorithmics . PhD thesis, Columbia University , 1992

    work page 1992

  16. [16]

    Chlebus, Krzysztof Diks, Torben Hagerup, and Tomasz Radzik

    Bogdan S. Chlebus, Krzysztof Diks, Torben Hagerup, and Tomasz Radzik. Efficient simulations between concurrent-read concurrent-write PRAM models. In Michal Chytil, Ladislav Janiga, and V \' a clav Koubek, editors, Mathematical Foundations of Computer Science 1988, MFCS'88, Carlsbad, Czechoslovakia, August 29 - September 2, 1988, Proceedings , volume 324 o...

    work page doi:10.1007/bfb0017146 1988

  17. [17]

    Cook, Cynthia Dwork, and R \" u diger Reischuk

    Stephen A. Cook, Cynthia Dwork, and R \" u diger Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM Journal on Computing , 15(1):87--97, 1986. https://doi.org/10.1137/0215006 doi:10.1137/0215006

    work page doi:10.1137/0215006 1986

  18. [18]

    Query optimization in compressed database systems

    Zhiyuan Chen, Johannes Gehrke, and Flip Korn. Query optimization in compressed database systems. In Sharad Mehrotra and Timos K. Sellis, editors, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, Santa Barbara, CA, USA, May 21-24, 2001 , SIGMOD/PODS01, pages 271--282. ACM , 2001. https://doi.org/10.1145/375663.375692 doi:1...

    work page doi:10.1145/375663.375692 2001

  19. [19]

    Sensitive functions and approximate problems

    Shiva Chaudhuri. Sensitive functions and approximate problems. Information and Computation , 126(2):161--168, 1996. https://doi.org/10.1006/inco.1996.0043 doi:10.1006/inco.1996.0043

    work page doi:10.1006/inco.1996.0043 1996

  20. [20]

    E. F. Codd. Relational completeness of data base sublanguages. In R. Rustin, editor, Database Systems , pages 33--64. Prentice-Hall, 1972

    work page 1972

  21. [21]

    Ka Wong Chong and Edgar A. Ramos. Improved deterministic parallel padded sorting. In Gianfranco Bilardi, Giuseppe F. Italiano, Andrea Pietracaprina, and Geppino Pucci, editors, Algorithms - ESA '98, 6th Annual European Symposium, Venice, Italy, August 24-26, 1998, Proceedings , volume 1461 of Lecture Notes in Computer Science , pages 405--416. Springer, 1...

    work page doi:10.1007/3-540-68530-8_34 1998

  22. [22]

    Incremental and decremental evaluation of transitive closure by first-order queries

    Guozhu Dong and Jianwen Su. Incremental and decremental evaluation of transitive closure by first-order queries. Information and Computation , 120(1):101--106, July 1995. https://doi.org/10.1006/inco.1995.1102 doi:10.1006/inco.1995.1102

    work page doi:10.1006/inco.1995.1102 1995

  23. [23]

    The power of methods with parallel semantics

    Karl Denninghoff and Victor Vianu. The power of methods with parallel semantics. In Guy M. Lohman, Am \' lcar Sernadas, and Rafael Camps, editors, 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings , pages 221--232. Morgan Kaufmann, 1991. URL: http://www.vldb.org/conf/1991/P221.PDF

    work page 1991

  24. [24]

    Fich, Prabhakar Ragde, and Avi Wigderson

    Faith E. Fich, Prabhakar Ragde, and Avi Wigderson. Relations between concurrent-write models of parallel computation. SIAM J. Comput. , 17(3):606--627, 1988. https://doi.org/10.1137/0217037 doi:10.1137/0217037

    work page doi:10.1137/0217037 1988

  25. [25]

    Hypertree decompositions: Questions and answers

    Georg Gottlob, Gianluigi Greco, Nicola Leone, and Francesco Scarcello. Hypertree decompositions: Questions and answers. In Tova Milo and Wang - Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016 , SIGMOD/PODS'16, pages 57--74. ACM , 201...

    work page doi:10.1145/2902251.2902309 2016

  26. [26]

    Hypertree decompositions and tractable queries

    Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences , 64(3):579--627, 2002. https://doi.org/10.1006/jcss.2001.1809 doi:10.1006/jcss.2001.1809

    work page doi:10.1006/jcss.2001.1809 2002

  27. [27]

    Goodrich, Yossi Matias, and Uzi Vishkin

    Michael T. Goodrich, Yossi Matias, and Uzi Vishkin. Approximate parallel prefix computation and its applications. In The Seventh International Parallel Processing Symposium, Proceedings, Newport Beach, California, USA, April 13-16, 1993 , pages 318--325. IEEE Computer Society Press, 1993. https://doi.org/10.1109/IPPS.1993.262899 doi:10.1109/IPPS.1993.262899

    work page doi:10.1109/ipps.1993.262899 1993

  28. [28]

    Goodrich, Yossi Matias, and Uzi Vishkin

    Michael T. Goodrich, Yossi Matias, and Uzi Vishkin. Optimal parallel approximation for prefix sums and integer sorting. In Daniel Dominic Sleator, editor, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA , pages 241--250. ACM/SIAM , 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314499

    work page arXiv 1994

  29. [29]

    Optimal deterministic approximate parallel prefix sums and their applications

    Tal Goldberg and Uri Zwick. Optimal deterministic approximate parallel prefix sums and their applications. In Third Israel Symposium on Theory of Computing and Systems, ISTCS 1995, Tel Aviv, Israel, January 4-6, 1995, Proceedings , ISTCS-95, pages 220--228. IEEE Computer Society Press, 1995. https://doi.org/10.1109/ISTCS.1995.377028 doi:10.1109/ISTCS.1995.377028

    work page doi:10.1109/istcs.1995.377028 1995

  30. [30]

    The log-star revolution

    Torben Hagerup. The log-star revolution. In Alain Finkel and Matthias Jantzen, editors, STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13-15, 1992, Proceedings , volume 577 of Lecture Notes in Computer Science , pages 259--278. Springer, 1992. https://doi.org/10.1007/3-540-55210-3_189 doi:10.1007/3-540-...

    work page doi:10.1007/3-540-55210-3_189 1992

  31. [31]

    On a compaction theorem of Ragde

    Torben Hagerup. On a compaction theorem of Ragde . Information Processing Letters , 43(6):335--340, 1992. https://doi.org/10.1016/0020-0190(92)90121-B doi:10.1016/0020-0190(92)90121-B

    work page doi:10.1016/0020-0190(92)90121-b 1992

  32. [32]

    Fast deterministic approximate and exact parallel sorting

    Torben Hagerup and Rajeev Raman. Fast deterministic approximate and exact parallel sorting. In Lawrence Snyder, editor, Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '93, Velen, Germany, June 30 - July 2, 1993 , SPAA '93, pages 346--355. ACM Press, 1993. https://doi.org/10.1145/165231.157380 doi:10.1145/165231.157380

    work page doi:10.1145/165231.157380 1993

  33. [33]

    Instance and output optimal parallel algorithms for acyclic joins

    Xiao Hu and Ke Yi. Instance and output optimal parallel algorithms for acyclic joins. In Dan Suciu, Sebastian Skritek, and Christoph Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019 , pages 450--463. ACM , 2019. https://doi.org/10.1145/...

    work page doi:10.1145/3294052.3319698 2019

  34. [34]

    Massively parallel join algorithms

    Xiao Hu and Ke Yi. Massively parallel join algorithms. ACM SIGMOD Record , 49(3):6--17, 2020. https://doi.org/10.1145/3444831.3444833 doi:10.1145/3444831.3444833

    work page doi:10.1145/3444831.3444833 2020

  35. [35]

    Expressibility and parallel complexity

    Neil Immerman. Expressibility and parallel complexity. SIAM Journal on Computing , 18(3):625--638, 1989. https://doi.org/10.1137/0218043 doi:10.1137/0218043

    work page doi:10.1137/0218043 1989

  36. [36]

    Descriptive Complexity

    Neil Immerman. Descriptive Complexity . Graduate texts in computer science. Springer, 1999. https://doi.org/10.1007/978-1-4612-0539-5 doi:10.1007/978-1-4612-0539-5

    work page doi:10.1007/978-1-4612-0539-5 1999

  37. [37]

    J \' a J \' a

    Joseph F. J \' a J \' a . An Introduction to Parallel Algorithms . Addison-Wesley, 1992

    work page 1992

  38. [38]

    Worst-case optimal algorithms for parallel query processing

    Paraschos Koutris, Paul Beame, and Dan Suciu. Worst-case optimal algorithms for parallel query processing. In International Conference on Database Theory, ICDT 2016 , pages 8:1--8:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany, 2016. https://doi.org/10.4230/LIPIcs.ICDT.2016.8 doi:10.4230/LIPIcs.ICDT.2016.8

    work page doi:10.4230/lipics.icdt.2016.8 2016

  39. [39]

    Algorithmic aspects of parallel data processing

    Paraschos Koutris, Semih Salihoglu, and Dan Suciu. Algorithmic aspects of parallel data processing. Foundations and Trends in Databases , 8(4):239--370, 2018. https://doi.org/10.1561/1900000055 doi:10.1561/1900000055

    work page doi:10.1561/1900000055 2018

  40. [40]

    Work-efficient query evaluation with PRAM s

    Jens Keppeler, Thomas Schwentick, and Christopher Spinrath. Work-efficient query evaluation with PRAM s. In Floris Geerts and Brecht Vandevoort, editors, 26th International Conference on Database Theory, ICDT 2023, March 28-31, 2023, Ioannina, Greece , volume 255 of LIPIcs , pages 16:1--16:20. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023. ...

    work page doi:10.4230/lipics.icdt.2023.16 2023

  41. [41]

    The semijoin algebra and the guarded fragment

    Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz, and Jan Van den Bussche. The semijoin algebra and the guarded fragment. Journal of Logic, Language and Information , 14(3):331--343, 2005. https://doi.org/10.1007/s10849-005-5789-8 doi:10.1007/s10849-005-5789-8

    work page doi:10.1007/s10849-005-5789-8 2005

  42. [42]

    On the complexity of division and set joins in the relational algebra

    Dirk Leinders and Jan Van den Bussche . On the complexity of division and set joins in the relational algebra. Journal of Computer and System Sciences , 73(4):538--549, 2007. https://doi.org/10.1016/j.jcss.2006.10.011 doi:10.1016/j.jcss.2006.10.011

    work page doi:10.1016/j.jcss.2006.10.011 2007

  43. [43]

    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. Journal of the ACM , 65(3):16:1--16:40, 2018. https://doi.org/10.1145/3180143 doi:10.1145/3180143

    work page doi:10.1145/3180143 2018

  44. [44]

    Dyn-FO : A parallel, dynamic complexity class

    Sushant Patnaik and Neil Immerman. Dyn-FO : A parallel, dynamic complexity class. Journal of Computer and System Sciences , 55(2):199--209, 1997. https://doi.org/10.1006/jcss.1997.1520 doi:10.1006/jcss.1997.1520

    work page doi:10.1006/jcss.1997.1520 1997

  45. [45]

    Paris and A

    J. Paris and A. Wilkie. Counting _0 sets. Fundamenta Mathematicae , 127(1):67--76, 1987. URL: http://eudml.org/doc/211630

    work page 1987

  46. [46]

    On the constant-depth complexity of k-clique

    Benjamin Rossman. On the constant-depth complexity of k-clique. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008 , STOC '08, pages 721--730. ACM , 2008. https://doi.org/10.1145/1374376.1374480 doi:10.1145/1374376.1374480

    work page doi:10.1145/1374376.1374480 2008

  47. [47]

    Query Evaluation Revised: Parallel, Distributed, via Rewritings

    Christopher Spinrath. Query Evaluation Revised: Parallel, Distributed, via Rewritings . PhD thesis, TU Dortmund University , 2024. https://doi.org/10.17877/DE290R-24219 doi:10.17877/DE290R-24219

    work page doi:10.17877/de290r-24219 2024

  48. [48]

    Work-sensitive dynamic complexity of formal languages

    Jonas Schmidt, Thomas Schwentick, Till Tantau, Nils Vortmeier, and Thomas Zeume. Work-sensitive dynamic complexity of formal languages. In Stefan Kiefer and Christine Tasson, editors, Foundations of Software Science and Computation Structures - 24th International Conference, FOSSACS 2021 , volume 12650 of Lecture Notes in Computer Science , pages 490--509...

    work page doi:10.1007/978-3-030-71995-1_25 2021

  49. [49]

    Machine models and simulation

    Peter van Emde Boas. Machine models and simulation. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity , pages 1--66. Elsevier and MIT Press, 1990

    work page 1990

  50. [50]

    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. https://doi.org/10.5441/002/icdt.2014.13 doi:10.5441/002/icdt.2014.13

    work page doi:10.5441/002/icdt.2014.13 2014

  51. [51]

    Introduction to Circuit Complexity - A Uniform Approach

    Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach . Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. https://doi.org/10.1007/978-3-662-03927-4 doi:10.1007/978-3-662-03927-4

    work page doi:10.1007/978-3-662-03927-4 1999

  52. [52]

    Query evaluation by circuits

    Yilei Wang and Ke Yi. Query evaluation by circuits. In Leonid Libkin and Pablo Barcel \' o , editors, PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022 , SIGMOD/PODS '22, pages 67--78. ACM , 2022. https://doi.org/10.1145/3517804.3524142 doi:10.1145/3517804.3524142

    work page doi:10.1145/3517804.3524142 2022

  53. [53]

    Algorithms for acyclic database schemes

    Mihalis Yannakakis. Algorithms for acyclic database schemes. In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings , pages 82--94. IEEE Computer Society, 1981

    work page 1981