Topics in Database Systems: Topic: Modern Database Systems

CS 848, Waterloo, Spring '21 (still being updated)

  Instructor:   David Toman (david@uwaterloo.ca)
  Lectures:     Online (via Bongo), Wed 1:30-4pm
  Office:       DC 3344, x34777
  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).

  Lecture video (unedited!)

• Week 2: 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 2:

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

  Lecture video (apologies for running over time)

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

  Reading for week 3:

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

  Lecture video

  List of suggestions for presentations

• Week 4: Updating Databases.

  Reading for week 4:

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

  Lecture video

  List of suggestions for projects

• Week 5: Query Compilation: Interpolation

  Reading for week 5:

  • (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.

  Lecture video

• Week 6: ITB (in class presentation by Eva Feng)

  Lecture video

  Assignment (1-and only)

• Week 7: Identifying Objects and Referring Expressions

  Reading for week 7:

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

  Lecture video

• Weeks 8-12: Presentations/Projects
  • Current list of Presentations and Projects

• Week 13: Summary and wrap-up.

  ---

  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 due at the latest during week 6 of classes;
  2. presentation: 20-30 minutes in weeks 7-12(-13);
  3. report (in pdf, up to 10 pages), source code (if applicable)

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

  ---

  Assessment:

  class participation (0%--as class is asynchronous, but do show up if you can)
  1 assignment (20%),
  in class presentation of a topic/paper from the reading list or of class project (optional, up to 30%)
  project (50-80%)

  ---