EUVIMEDEUVIMED entdecken
Crossref

Technical Perspective: Output-Optimal Evaluation ofConjunctive Queries

Dan Suciu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →