Master thesis or Master practical course
The goal of this project is to formalise select topics from the lecture query optimisation for relational databases. The first part of the project concentrates on the basics of query optimisation which include query graphs and join trees. By defining a cost function on join trees, we can define the optimisation problem of join ordering. The analysis of optimisation algorithms for join ordering forms the second part of the project. We will focus on the IK, IKKBZ, and the dynamic programming algorithm.
Programming language: Isabelle/HOL
Prerequisites: Fundamentals of algorithm analysis and experience with Isabelle/HOL; English/German
Supervisor: Lukas Stevens
Professor: Prof. Tobias Nipkow