CS294-248: Topics in Database Theory

Room: Soda 310

Time: Tuesday, Thursday: 11-12:20

Description

Prerequisites

Is this course for you?

This is an advanced course. If you are unsure whether this course is for you, take this very simple self test.

It covers only theory. If you are interested in advances systems topics, I strongly recomment CS286: Graduate DB Systems in Spring 2024. (This is a natural graduate-level follow-on to the undergrad CS186 class.)

Schedule

First lecture will be on Tuesday, 8/29.

Dates/Videos	Unit	Content
8/21-8/25		Bootcamp at Simons. It is recommended that you attend 1 or 2 of the mini-courses
8/29, 8/31	1	Logic and Queries
9/5, 9/7	2	Conjunctive Queries
9/12, 9/14	3	Incremental View Maintenance (Dan Olteanu)
9/19, 9/21	4	AGM Bound, Worst-Case Optimal Algorithms (Hung Ngo)
9/25-9/27		Workshop 1 at Simons
10/3,10/5	5	Information Inequalities and Database Constraints
10/10,10/12	6	Database Constraints (cont'd), Repairs, Incomplete Databases
10/16-10/20		Workshop 2 at Simons
10/24,10/26	7	Semirings and K-Relations, WCOJ and Tree Decomposition (white-board only) Recommended talk by Reinhard Pichler slides, talk.
10/31, 11/2	8-9	FAQ (Hung Ngo), Introduction to Datalog (whiteboard only)
11/7, 11/9	9	Datalog (cont'd) by Zoom only11/9 lecture CANCELED
11/13-11/17		Workshop 3 at Simons
11/21, 11/28	9	Datalog, Final review of the class

Zoom link

(Zoom link for the final presentations is further below)

Available here (the zoom link is on the left).

Direct link is here. You need to be authenticated.

But please attend all lectures in person

Homework Assignments

HW 1 due on Monday, 9/4

HW 2 due on Monday, 9/11

HW 3 due on Monday, 9/25

HW 4 due on Monday, 10/9

Final Report and presentation

When: Thursday, November 30th, 9:30am

Where: The Simon's Institute, Calvin Lab CR116

Task: pick a theory problem/result and explain it to a wide audience. Give a short presentation (15' including questions).

ReportWrite a short report, say about 2-5 pages. Please submit it (via bcourses) by November 29, i.e. before the presentation

Some suggested topics (but feel free to choose beyond these).

• Is your research related in any way to a theory problem? You can pick that one and present it.
• 0/1 Law for First Order Logic.
• Existential Second Order Logic = NP
• Ehrenfeucht-Fraisse Games
• Pebble Games
• Suppose a query written in FO is monotone. Can we write this query as a UCQ (Union of Conjunctive Queries)? Reference.
• Order-invariant queries in FO are strictly more expressive than FO. This is a famous example by Gurevich, see exercise 17.27 in the Alice-book.
• Is stratified datalog as expressive as fixpoint logic? (Fixpoint logic means FO extended with fixpoint of monotone queries.) This was stated by Chandra and Harel (Theorem 5.4): you don't need to read that paper, because it was found to be wrong! Who proved that it is wrong? What is the fixpoint query that cannot be written in stratified datalog?
• Describe the different, alternative definitions of acyclicity for hypergraphs: alpha-acyclic, beta-acyclic, gamma-acyclic, and Berge-acyclic. This is classic, well known topic, from this landmark paper. The paper is long, deep, and very well written. Your task in this project would be to present the main ideas in a simple, understandable way.

Simons' Program

Final Presentations

Zoom link: here

Grading