Christoph Berkholz and Thomas Zeume

Week 2, August 10-14, 2020

Abstract:

This course offers an introduction to foundations and methods of database theory with a focus on logic-based query languages and their properties. In the first part we introduce classical connections between database query languages and logics. In particular we will see how logical methods help to study the algorithmic complexity of evaluating queries and how they help to understand the expressivity of query languages. In the second part we will apply these methods to dynamic query evaluation. Here we focus on two facets that are active research topics in the database theory community. The first one is the algorithmic complexity of dynamic query evaluation, which studies runtime guarantees for dynamic algorithms. The second one is the dynamic descriptive complexity framework, which studies the expressiveness of logically defined database updates.