Structural Decomposition Algorithms for Database Query Optimization
Event details
| Date | 19.06.2025 |
| Hour | 14:30 › 16:30 |
| Speaker | Zhekai Jiang |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Anastasia Ailamaki
Thesis advisor: Prof. Christoph Koch
Co-examiner: Prof. Michael Kapralov
Abstract
Select-project-join queries, i.e., conjunctive queries, constitute the cornerstone of analytical workloads in relational databases, and join operations are usually the determining factor of their performance. Current systems usually rely on cost-based dynamic programming and/or greedy algorithms to produce the optimal or near-optimal join ordering. In this proposal, we focus on an alternative set of methods that capture and leverage the structures of queries. We start with the case of acyclic queries and review the algorithm Yannakakis+ which efficiently evaluates them with a strong theoretical guarantee of the asymptotic complexity. We then examine the concept and algorithm of hypertree decompositions to handle cyclic queries. Finally, we discuss weighted hypertree decompositions as a potential approach to allow for cost-based optimization.
Selected papers
coming soon
Exam president: Prof. Anastasia Ailamaki
Thesis advisor: Prof. Christoph Koch
Co-examiner: Prof. Michael Kapralov
Abstract
Select-project-join queries, i.e., conjunctive queries, constitute the cornerstone of analytical workloads in relational databases, and join operations are usually the determining factor of their performance. Current systems usually rely on cost-based dynamic programming and/or greedy algorithms to produce the optimal or near-optimal join ordering. In this proposal, we focus on an alternative set of methods that capture and leverage the structures of queries. We start with the case of acyclic queries and review the algorithm Yannakakis+ which efficiently evaluates them with a strong theoretical guarantee of the asymptotic complexity. We then examine the concept and algorithm of hypertree decompositions to handle cyclic queries. Finally, we discuss weighted hypertree decompositions as a potential approach to allow for cost-based optimization.
Selected papers
coming soon
Practical information
- General public
- Free
Contact
- edic@epfl.ch