EUVIMEDEUVIMED entdecken
Crossref

Output-Optimal Evaluation of Conjunctive Queries

Xiao Hu, Shaleen Deep, Paraschos Koutris, Austen Z. Fan, Hangdong Zhao

ACM SIGMOD Record · 23.04.2026 · 55 (1) · 31-39

DOI: 10.1145/3810900.3810906 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM SIGMOD Record, online erschienen am 23.04.2026. Verfasst von Xiao Hu und 4 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

One of the most celebrated results for evaluating conjunctive queries (CQs) is the Yannakakis algorithm [24] proposed in 1981. It is known that free-connex CQs can be evaluated in O(N + OUT) time, where N is the input size of the database and OUT is the output size of the query result. This is already output-optimal. However, only an upper bound O(N ·OUT) on the runtime is known for the remaining acyclic but non-freeconnex CQs. Alternatively, one can convert a non-freeconnex CQ into a free-connex one using tree decomposition techniques, and then run the Yannakakis algorithm. However, none of them is known to be output-optimal.

Zitieren

APA

Hu, X., Deep, S., Koutris, P., Fan, A. Z., & Zhao, H. (2026). Output-Optimal Evaluation of Conjunctive Queries. ACM SIGMOD Record, 55(1), 31-39. https://doi.org/10.1145/3810900.3810906

Vancouver

Hu X, Deep S, Koutris P, Fan AZ, Zhao H. Output-Optimal Evaluation of Conjunctive Queries. ACM SIGMOD Record. 2026;55(1):31-39. doi:10.1145/3810900.3810906

BibTeX
@article{Hu2026,
  author = {Hu, Xiao and Deep, Shaleen and Koutris, Paraschos and Fan, Austen Z. and Zhao, Hangdong},
  title = {Output-Optimal Evaluation of Conjunctive Queries},
  journal = {ACM SIGMOD Record},
  year = {2026},
  volume = {55},
  number = {1},
  pages = {31--39},
  doi = {10.1145/3810900.3810906}
}
Kostenlos starten →