Topics in Database Systems: Topic: Modern Database Systems

CS 848, Waterloo, Fall '26 (still being updated)

  Instructor:   David Toman (david@uwaterloo.ca)
  Lectures:     Wednesday 3:00-5:50PM in DC 2568
  Office:       DC 3344
  Class Info:   http://cs.uwaterloo.ca/~david/cs848/

Summary:

Textbook

You can get an electronic (pdf) copy of the textbook here for free (while on UW campus network), or a hard-copy if you prefer from Amazon.

Class Schedule and Outlines:

• Week 1: Introduction and organization and Goals (aka why are we here?)

  Basic goals of the class/lectures, discussion of existing approaches and alternatives. In part based on:
  OLTP Through the Looking Glass, and What We Found There. (Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, and Michael Stonebraker. SIGMOD 2008).

  Reading for week 1:

  • Chapters 1 and 2 from the textbook,
  • original paper on relational model by Ted Codd (this has led to Codd's Turing Award),
  • a refresher on relational calculus and relational calculus reference (optional: in case you need to get up to speed).

• Week 1: Queries and Plans.

  We introduce a case study of applying relational technology in non-traditional setting, such as embedded systems: the Linux kernel and discuss the desiderata for alternative approaches to relational query processing; this discussion will highlight the goals of the class. Reading for week 1:

  • Chapter 3 and 4 from the textbook,
  • a refresher on relational algebra and query evaluation and
  • Graefe G. Query evaluation techniques for large databases. ACM Comput. Surv., 25(2):73-170, 1993. (optional, but extensive survey of common approaches)

  List of suggestions for presentations

• Week 2: Extra-logical features: duplicates and ordered data.

  Reading for week 2:

  • Chapter 5.2 from the textbook,
  • Duplicate elimination elinimation,
  • Classical query optimizers: Starburst and Volcano,

  List of suggestions for projects

• Week 3: Updating Databases.

  Reading for week 3:

  • Chapter 6 from the textbook,
  • How to deal with anonymous objects? The Constant Complement approach

• Week 4: Query Compilation: Interpolation

  Reading for week 4:

  • (rest of) Chapter 5 from the textbook
  • On Enumerating Query Plans Using Analytic Tableau,
  • An Interpolation-based Compiler and Optimizer for Relational Queries
    
  • classical "rewriting using views" paper
  • (optional) Interpolant construction from tableaux and resolution proofs,
  • (optional) Sequent Calculus for Propositional Logic.

• Week 5: Identifying Objects and Referring Expressions

  Reading for week 5:

  • On Referring Expressions in Query Answering over First Order Knowledge Bases. (KR 2016 best paper),
  • On Referring Expressions in Information Systems Derived from Conceptual Modelling.

• Reading Week-Week 6

• Week 7:

  Summary of the lectures (myself, ~30")
  Presentations:

  • Krish Patel:
    • C-Store: A Column-oriented DBMS
    • Column-Stores vs. Row-Stores: How Different Are They Really
    • Integrating compression and execution in column-oriented database systems

• Week 8: Presentations
  • Maggie Simmons: Formal verification for query compilation and optimization
  • James You: Database Theory in Action: Search-Based Program Optimization, Relational e-matching

• Week 9: Presentations
  • Ahmed El Shatshat: History Repeats Itself: Sensible and NonsenSQL Aspects of the NoSQL Hoopla
  • Chanaka Lakmal Lokupothagamage Don: Dynamo: Amazon’s Highly Available Key-value Store

• Week 10: Presentations
  • Baoming Chang: Anti-Caching: A New Approach to Database Management System Architecture
  • Pranshu Kumar: Lock-free algorithms

• Week 11: Presentations

• Week 12: Presentations and Summary/wrap-up.
  • Summary of the class

  ---

  Projects:

  Preferred projects will be related to applying (some) of the ideas presented in this class to your own area of research: this can further your own research and may help you to consider alternative views/approaches to what you have been thinking about already.
  1. project proposal: one page in pdf due during week 7 of classes;
  2. report (in pdf, up to 10 pages), source code (if applicable)
     DUE: December 08, 2026 by email (use Subject: "CS848 Project (your name)" in the email)

  If you don't see any relation to your own research, here are a few alternative options.

  ---

  Assessment:

  class participation (10%)
  in class presentation either of your project or of a paper from the reading list (30%)
  project (60%)

  Contingency plan: if necessary due to health situation, the classes (including presentations) will move to LEARN/Bongo.

  ---