Output-Optimal Evaluation of Conjunctive Queries
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.
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}
}
EUVIMED