Work in progress
Course Schedule
Weekly lecture slides, meeting plans, and primary readings
Weekly slides
Download the lecture slides as PDFs below. The meeting plan that follows links the companion notes, readings, and project checkpoints. Slides are added as the course develops; later meetings remain tentative.
| Week | Lecture slides (PDF) |
|---|---|
| 1 · Aug. 31–Sep. 4 | 02 · The Rust We Need |
| 2 · Sep. 7–11 | 03 · Semantics of Conjunctive Queries |
| 3 · Sep. 14–18 | 04 · Rust Macros; 05 · Relational Algebra |
| 4 · Sep. 21–25 | 06 · Relational Algebra: Selection and Projection; 07 · Physical Access: Indexes and Relation Layout |
| 5 · Sep. 28–Oct. 2 | 08 · Query Execution: Iterators, State, and Batches |
Meeting-by-meeting plan and primary readings
The course meets Monday and Wednesday from 3:00–4:15 p.m. Each column below is a separate class meeting, not a weekly topic followed by an elaboration of the same lecture. Week 1 supplies the Rust needed to read the project: one meeting uses the course cheat sheet with Rust Guide R.0.0, and the next begins the staged-programming sequence with Rust Conversation R.1. Rust then returns in ten later Wednesday conversations and project studios.
Five meetings are marked as student-led paper forums. One or more assigned leaders open each forum with the paper's claim, evidence, and a question or counterexample; the rest of the class comes prepared to test that account. A Rust/project studio is guided work during class, not an additional weekly programming assignment. Exceptions from the Fall 2026 academic calendar are attached to the affected meeting.
| Week | Center | Monday · 3:00–4:15 | Wednesday · 3:00–4:15 | Primary reading / due |
|---|---|---|---|---|
| 1 · Aug. 31–Sep. 4 | Rust for the course | Rust lecture and guided lab: use A Little Rust, Side by Side while working through Rust Guide R.0.0: values, ownership, borrowing, enums, structs, and iterators | Rust Conversation R.1: make written code a typed syntax value; separate macro expansion, compilation, and runtime | Rust Book Ch. 4, Ch. 6, and §20.5 are references, not prerequisites |
| 2 · Sep. 7–11 | CQ meaning | No class · Labor Day | Introductory slides (PPTX), Conversation 1.1, and Conversation 1.2: databases, rules, valuations, query images, and why we compile a query | Abiteboul, Hull, and Vianu, Foundations of Databases, §§3.1–3.3, 4.1–4.2 |
| 3 · Sep. 14–18 | From CQs to logical join plans | Conversation 1.3, Conversation 2.1, Conversation 2.2, and Conversation 2.3: translate valuation semantics into SPJR, interpret a flat join as binary trees, compare intermediate rows and columns, and earn the query hypergraph | Conversation 2.4, Conversation 2.5, and Rust conversation R.2: derive required schemas, build one deterministic join–project plan, then map written syntax into a derived AST | Abiteboul, Hull, and Vianu, Foundations of Databases, §§4.4, 6.1, 6.4; Garcia-Molina, Ullman, and Widom, Database System Implementation, selected §§6.2–6.4 |
| 4 · Sep. 21–25 | Selection, projection, and physical access | Derive safe projection and early selection; compare equivalent relational-algebra plans and the intermediate rows and columns they retain | Compare scans, sorted arrays, hash indexes, and B+ trees; trace row IDs through row, column, and PAX layouts. Rust conversation and practicum 1: R.3 | Foundations of Databases, §§4.4, 6.1; Database System Implementation, selected §§6.2–6.4; practicum 1 |
| 5 · Sep. 28–Oct. 2 | Query execution and join order | Trace iterator state, indexed nested-loop joins, hash joins, and batches; connect pull and push control to the same logical plan | Student-led paper forum and Rust/project studio: compare left-deep orders and their intermediate work; introduce dynamic-programming search, then instrument two equivalent plans and check their answers | Neumann, Efficiently Compiling Efficient Query Plans for Modern Hardware, §§1, 3.1–3.2; Selinger et al., Access Path Selection in a Relational Database Management System, §5; R1 due |
| 6 · Oct. 5–9 | AGM bounds | Derive a fractional edge cover and its output-size bound; distinguish output size from the work of a chosen binary plan | Rust/project studio and practicum 2: generate controlled relation sizes, measure intermediate work, and compare the trace with the bound | Atserias, Grohe, and Marx, Size Bounds and Query Plans for Relational Joins, §§2–3.1; practicum 2. Fall Break is Friday and cancels neither meeting |
| 7 · Oct. 12–16 | Yannakakis | Student-led paper forum: build a join tree and justify the bottom-up and top-down semijoin passes | Rust/project studio: inspect the join-tree analysis, trace both reduction passes, and check reduced-instance enumeration | Yannakakis, Algorithms for Acyclic Database Schemes, §§2, 4 |
| 8 · Oct. 19–23 | Worst-case-optimal joins | Student-led paper forum: contrast binary and variable-at-a-time execution; derive Generic Join under one variable order | Rust/project studio: trace trie cursors and Leapfrog intersection, then compare the counters with a binary plan | Veldhuizen, Leapfrog Triejoin, §§1, 3.1–3.5 |
| 9 · Oct. 26–30 | Practical predicate transfer | Rust/project studio: integrate the semijoin and triejoin stages, run the R2 correctness checks, and prepare one implementation question for the guest | Hangdong Zhao guest lecture: predicate transfer, runtime filters, zone maps, and related system details | Yang et al., Predicate Transfer |
| 10 · Nov. 2–6 | Positive Datalog | Treat a positive Datalog program as recursive CQ evaluation; derive model, fixed-point, and proof views | Rust/project studio: trace naive fixed-point evaluation and account for rounds, duplicates, and termination | Foundations of Databases, §§12.1–12.4; R2 due |
| 11 · Nov. 9–13 | Semi-naive evaluation | Derive delta rules and candidate sets from the naive evaluator | Rust/project studio and practicum 3: follow full, delta, and candidate relations through code; check duplicates and termination | Foundations of Databases, §13.1; practicum 3 |
| 12 · Nov. 16–20 | Extending Datalog to ontology reasoning | Negation, disjunction, and the semantic commitments introduced by each extension | Student-led paper forum: ontology-based data access case study; test which conclusions follow from the paper's semantics | Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP |
| 13 · Nov. 23–27 | Project checkpoint | Select the advanced extension; state its semantic contract, baseline, and correctness oracle | No class · Thanksgiving Holiday | No reading or work due |
| 14 · Nov. 30–Dec. 4 | Probabilistic and neuro-symbolic Datalog | Student-led paper forum: compare exact, top-k, and differentiable proof evaluation on one supplied example | Rust/project studio: failure-case clinic, work counters, baselines, and final release check | Huang et al., Scallop, §§2–4.2; R3 due |
| 15 · Dec. 7–11 | Synthesis | Short project presentations and cross-course connections | Remaining presentations and synthesis; Zoom participation is permitted | No reading; No-Test Week |
Labor Day cancels Monday, September 7. Fall Break is Friday, October 9, so it cancels neither meeting. Thanksgiving recess cancels Wednesday, November 25, but Monday remains a class meeting. Week 15 has no quiz or examination; project presentations are the only graded activity, as permitted by the university's No-Test Days policy.
Release map
The project releases R1–R3 are submission checkpoints. They are distinct from the instructional Rust Conversations R.1–R.3 linked above.
| Release | Project stages | Planned point in course |
|---|---|---|
| R1 | Binary physical plan and execution control | End of Week 5 |
| R2 | Semijoin reduction and triejoin | End of Week 10 |
| R3 | Semi-naive evaluation and one advanced extension | End of Week 14 |
The project page defines each release's implementation and evaluation contract. This page is the authoritative location for meeting activities, due weeks, and calendar adjustments.