CS240B Advanced Databases

This is a graduate-level research-oriented course offered in Fall 2025. The course aims to introduce foundational knowledge and discuss recent advances in Databases. We will focus on the algorithmic aspect of data processing this quarter.

The lectures will be based on notes from a similar course at Universiy of Wisconsin (thanks to Paris Koutris who gave us the permission to use his notes).

Prerequisites

The students are expected to be familiar with the inner workings of relational databases, including the relational algebra, SQL, and join algorithms.

Grading

50% of the grade is based on homework assignments (every two weeks), involving writing both proofs and programs. The other 50% of the grade is based on a final project/report.

Reading

[1]

Amarilli, A. et al. 2024. A circus of circuits: Connections between decision diagrams, circuits, and automata. CoRR. abs/2404.09674, (2024). DOI:https://doi.org/10.48550/ARXIV.2404.09674.

[2]

Chen, H. 2009. A rendezvous of logic, complexity, and algebra. ACM Comput. Surv. 42, 1 (2009), 2:1–2:32. DOI:https://doi.org/10.1145/1592451.1592453.

[3]

Khamis, M.A. et al. 2016. Joins via geometric resolutions: Worst case and beyond. ACM Trans. Database Syst. 41, 4 (2016), 22:1–22:45. DOI:https://doi.org/10.1145/2967101.

[4]

Koutris, P. 2025. Generalized covers for conjunctive queries. 28th international conference on database theory, ICDT 2025, march 25-28, 2025, barcelona, spain (2025), 28:1–28:15.

[5]

Raszyk, M. et al. 2022. Practical relational calculus query evaluation. 25th international conference on database theory, ICDT 2022, march 29 to april 1, 2022, edinburgh, UK (virtual conference) (2022), 11:1–11:21.

[6]

Suciu, D. 2023. Applications of information inequalities to database theory problems. 38th annual ACM/IEEE symposium on logic in computer science, LICS 2023, boston, MA, USA, june 26-29, 2023 (2023), 1–30.