Query optimization for databases

Chair for Logic and Verification

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