This tutorial revisits Yannakakis algorithm (YA) as a central example of how database theory can guide practical query processing. Yannakakis algorithm gives an instance-optimal guarantee for evaluating acyclic joins, and its core ideas, including join trees, semijoin reduction, and information passing, have influenced decades of work in query evaluation. Recent studies have renewed interest in the Yannakakis algorithm by demonstrating that its structure-aware principles can be applied to modern database systems, yielding practical methods for robust SQL analytics. This tutorial introduces the foundations of the Yannakakis algorithm and acyclic query processing, surveys recent advances in theory and systems, and discusses how these ideas extend to query optimization and general queries beyond the multi-way joins. The goal is to give the audience both a clear conceptual understanding of Yannakakis algorithm and a broad view of its growing role in modern data management.
Paraschos Koutris, Stijn Vansummeren, Qichen Wang et al.· Proceedings of the VLDB Endo...· 0 citations
Hypertree decompositions are a cornerstone in the theory of answering conjunctive queries efficiently. However, they are not yet widely adopted in practice. Problems related to, e.g., the uniqueness of decompositions and succinct representations of all decompositions have so far mostly been neglected by the theory literature. In this paper, we present the first in-depth discussion of rerootability in hypertree decompositions---a property which we argue is essential for such problems. Rerootability leads us to projection-freeness, and we have to discuss normal form to recover tractability. Normal form, however, again obstructs rerootability, and for this reason, we define a relaxed notion of normal form which leads to a truly rerootable and tractable class. Experimental evidence suggests that the price we pay in terms of width increase for transitioning to this class of decompositions is moderate in practice.
Zhekai Jiang, Christoph Koch, Peter Lindner et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
