Room: Soda 310

Time: Tuesday, Thursday: 11-12:20

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.)

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 | Database Constraints |

10/10, 1012 | 6 | Incomplete, Probabilistic Databases |

10/16-10/20 | Workshop 2 at Simons | |

10/24, 10/26 | 7 | Semirings and K-Relations (Val Tannen) |

10/31, 11/2 | 8-9 | FAQ, Datalog, Chase |

11/7, 11/9 | 9 | Datalog, Chase (cont'd) |

11/13-11/17 | Workshop 3 at Simons | |

11/21, 11/28 | TBD |

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**

HW 1 due on Monday, 9/4

HW 2 due on Monday, 9/11

HW 3 due on Monday, 9/25

Task: pick a theory problem/result and explain it to a wide audience. Write a short report. Suggested length: 3-5 page. Give a short presentation (10'), in class: tentative date, Tuesday 12/5.

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

- 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.
- (MORE SUGGESTIONS COMING SOON)