DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2026.17

Algorithms for Optimizing Acyclic Queries

Authors: Zheng Luo, Wim Van den Broeck, Guy Van den Broeck, and Yisu Remy Wang

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract

Most research on query optimization has centered on binary join algorithms like hash join and sort-merge join. However, recent years have seen growing interest in theoretically optimal algorithms, notably Yannakakis' algorithm. These algorithms rely on join trees, which differ from the operator trees for binary joins and require new optimization techniques. We propose three approaches to constructing join trees for acyclic queries. First, we give an algorithm to enumerate all join trees of an α-acyclic query by edits in linear time with amortized constant delay, which forms the basis of a cost-based optimizer for acyclic joins. Second, we show the Maximum Cardinality Search algorithm by Tarjan and Yannakakis constructs the unique shallowest join tree for any Berge-acyclic query, thus enabling parallel execution of large join queries. Finally, we prove that a simple algorithm by Hu et al. converts any connected left-deep linear plan of a γ-acyclic query into a join tree, allowing reuse of optimizers developed for binary joins.

Cite as

Zheng Luo, Wim Van den Broeck, Guy Van den Broeck, and Yisu Remy Wang. Algorithms for Optimizing Acyclic Queries. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.ICDT.2026.17,
  author =	{Luo, Zheng and Van den Broeck, Wim and Van den Broeck, Guy and Wang, Yisu Remy},
  title =	{{Algorithms for Optimizing Acyclic Queries}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.17},
  URN =		{urn:nbn:de:0030-drops-256319},
  doi =		{10.4230/LIPIcs.ICDT.2026.17},
  annote =	{Keywords: Query Optimization, Join Trees, Enumeration}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2025.12

Tractable Conjunctive Queries over Static and Dynamic Relations

Authors: Ahmet Kara, Zheng Luo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract

We investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject to inserts and deletes. We characterise syntactically three classes of queries that admit constant update time and constant enumeration delay. We call such queries tractable. Depending on the class, the preprocessing time is linear, polynomial, or exponential (under data complexity, so the query size is constant). To decide whether a query is tractable, it does not suffice to analyse separately the sub-queries over the static relations and over the dynamic relations, respectively. Instead, we need to take the interaction between the static and the dynamic relations into account. Even when the sub-query over the dynamic relations is not tractable, the overall query can become tractable if the dynamic relations are sufficiently constrained by the static ones.

Cite as

Ahmet Kara, Zheng Luo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Tractable Conjunctive Queries over Static and Dynamic Relations. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kara_et_al:LIPIcs.ICDT.2025.12,
  author =	{Kara, Ahmet and Luo, Zheng and Nikolic, Milos and Olteanu, Dan and Zhang, Haozhe},
  title =	{{Tractable Conjunctive Queries over Static and Dynamic Relations}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.12},
  URN =		{urn:nbn:de:0030-drops-229534},
  doi =		{10.4230/LIPIcs.ICDT.2025.12},
  annote =	{Keywords: fully dynamic algorithm, constant enumeration delay, constant update time}
}

Search Results

Documents authored by Luo, Zheng

Algorithms for Optimizing Acyclic Queries

Abstract

Cite as

Tractable Conjunctive Queries over Static and Dynamic Relations

Abstract

Cite as

Thanks for your feedback!

Could not send message