Technical Perspective: Output-Optimal Evaluation ofConjunctive Queries
ACM SIGMOD Record · 23.04.2026 · 55 (1) · 30-30
DOI: 10.1145/3810900.3810905 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMOD Record, online erschienen am 23.04.2026. Verfasst von Dan Suciu.
Abstract (Originalsprache)
The best asymptotic runtime that we can hope for a query evaluation algorithm is O(N + OUT), where N is the size of the input database and OUT is the size of the query's output. Indeed, any algorithm must read the input, and must write the output, hence one cannot do better asymptotically. It is not immediately obvious how to evaluate a query in this time. The standard approach taken by all query engines is to compute one join at a time, but in that case the intermediate results may become much larger than both the input and the final output. Yannakakis' algorithm from the early 80's achieves a runtime of O(N +OUT) on all full, acyclic queries, by first removing all dangling tuples from all relations using a sequence of semijoins, then performing the joins.
Zitieren
APA
Suciu, D. (2026). Technical Perspective: Output-Optimal Evaluation ofConjunctive Queries. ACM SIGMOD Record, 55(1), 30-30. https://doi.org/10.1145/3810900.3810905
Vancouver
Suciu D. Technical Perspective: Output-Optimal Evaluation ofConjunctive Queries. ACM SIGMOD Record. 2026;55(1):30-30. doi:10.1145/3810900.3810905
BibTeX
@article{Suciu2026,
author = {Suciu, Dan},
title = {Technical Perspective: Output-Optimal Evaluation ofConjunctive Queries},
journal = {ACM SIGMOD Record},
year = {2026},
volume = {55},
number = {1},
pages = {30--30},
doi = {10.1145/3810900.3810905}
}
EUVIMED