Topics in Database Systems: Topic: Modern Database Systems

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

  Instructor:   David Toman (david@uwaterloo.ca)
  Lectures:     10:30-01:20W in DC 2568
  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).

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

  List of suggestions for projects

• Week 4: Updating Databases.

  Reading for week 4:

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

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

• Week 6: Identifying Objects and Referring Expressions

  Reading for week 6:

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

• Week 7:
  • Summary of the lectures (myself, ~30")

• Week 8: Presentations
  • Amy Bhatia: C-Store-A Column Oriented DBMS
  • Zhenyu Sun: Scalable SQL and NoSQL Data Stores

• Week 9: Presentations
  • Anuradha Kulkarni: Survey of MMDB recovery techniques
  • Senyu Fu: Distributed DBs: Merging Strategies

• Week 10: Presentations
  • Lixian Liu: Speak to your Parser
  • Boren Zang: High-Performance Concurrency Control Mechanisms for Main-Memory Databases

• Week 11: Presentations
  • no class due to illness

• Week 12: Presentations and Summary/wrap-up.
  • Tavian Barnes: The Aurora Single Level Store Operating System
  • 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 due during week 6 of classes;
  2. presentation: 20-30 minutes in weeks 7-12;
  3. report (in pdf, up to 10 pages), source code (if applicable)
     DUE: August 09, 2022 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 or solutions to assignments (20%)
  in class presentation either of your project or of a paper from the reading list (30%)
  project (50%)

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

  ---