Schedule and Readings

Note

Class dates are final. Readings may still change.

Readings marked Main are the assigned papers for the module; written assignments draw on them. Additional readings are optional. Papers for the presentation and discussion sessions will be assigned separately.

Sept 1, Sept 3 — Introduction, Overview, and Background

In the first two classes we will cover:

  • The history of database management systems, what problems they are trying to solve, the state of the art, and what we plan to cover this semester.
  • The relational model, SQL, and how traditional relational database management systems are built (the Architecture paper below).
  • How to think broadly about the world of data management systems today, and how to place different works in context. Specifically, we will discuss the key design decisions that need to be made for a data management system — data models, languages and programming frameworks, storage models, transaction support, guarantees, and so on — and what the impact of those decisions might be. Most of this discussion will be at a high level, and we will dive deeper into several of these topics later in the course. We will also touch on orthogonal but important concerns such as streaming systems and immutability.

Slides: 1-Introduction · 424 Summary · 424 All Slides (419-page PDF)

Lecture notes (Module 1): Motivation, Definitions, and a Brief History · Background: A Review of CMSC 424 · Abstractions, Models, and Implementations

Main readings:

  1. Architecture of a Database System; Joe Hellerstein, Mike Stonebraker, James Hamilton; Foundations and Trends 2007. (original paper; crop-merged version) — an overview of how traditional database management systems are built, and some of the key design considerations.

Additional readings:

  1. Database System Concepts; Avi Silberschatz, Henry F. Korth, S. Sudarshan — the textbook for the undergraduate class, and a good reference for brushing up on background we do not cover in depth. [link]
  2. For a nice historical overview of database management systems, see the first paper (“Evolution of …”) in ACM Computing Surveys, March 1976.
  3. Concurrency Control and Recovery; Mike Franklin, 1997 — we will not cover this topic much, but the paper is a good introduction to material you should be comfortable with.
  4. Is your database relational? Ted Codd — see the Wikipedia article on Codd’s 12 rules.

Sept 8, 10, 15 — Data Models, Languages, and Programming Frameworks

We will dive into the different data models, query languages, and programming frameworks that have been proposed over the years for modeling and structuring data, and for querying and analyzing it. In particular: the relational model and SQL, the document data model (e.g., MongoDB), the entity-relationship model and ORM frameworks, MapReduce and Spark, graph data models, REST, OLAP, visualization, and machine learning frameworks — in varying levels of detail. We will also discuss the importance of schemas and the challenges of schema evolution.

Slides: 2-Models-Languages-Abstractions

Lecture notes (Module 2): A History of Data Models · Operations on Datasets · Query Languages · Programming Frameworks

Main readings:

  1. What Goes Around Comes Around; Mike Stonebraker and Joe Hellerstein; Redbook — summarizes how data models evolved over the last 50 years.
  2. A Survey of Research on Deductive Database Systems (Sections 1–4); Ramakrishnan and Ullman; 1993. [link]
  3. Declarative Networking: Language, Execution and Optimization (Sections 1, 2, and 4); Loo et al.; SIGMOD 2016.
  4. MapReduce: A Flexible Data Processing Tool (Sections 1–2); Jeffrey Dean and Sanjay Ghemawat; CACM 2010.
  5. Resilient Distributed Datasets (Sections 1–4); Zaharia et al.; NSDI 2012.
  6. SystemML: Declarative Machine Learning On MapReduce (Sections I–III(A)); Ghoting et al.; ICDE 2011.
  7. GraphX: Graph Processing in a Distributed Dataflow Framework (Sections 1–3); OSDI 2014. [link]

Additional readings:

  1. Database System Concepts; Silberschatz, Korth, Sudarshan — two appendices covering the network and hierarchical models in detail are available on the book webpage (6th edition). [link]
  2. Joachim W. Schmidt. Some High Level Language Constructs for Data of Type Relation. ACM TODS 2(3), 1977, 247–261.
  3. MapReduce and Parallel DBMSs: Friends or Foes?; Stonebraker et al.; CACM 2010.

Sept 17, 22, 24 — Storage Models and Indexing

We will discuss how data is stored on disk and in memory, and the impact of those design decisions. Specifically, we will cover row and column storage formats for databases, and the prevalent storage formats for data lakes that are widely used today.

Slides: 3-Storage

Lecture notes (Module 3): Background · PAX · Column Stores and Compression · Dremel · Delta Lake

Main readings:

  1. Weaving Relations for Cache Performance; Ailamaki et al.; VLDB 2001.
  2. Integrating Compression and Execution in Column-Oriented Database Systems; Abadi et al.; SIGMOD 2006.
  3. Dremel: Interactive Analysis of Web-Scale Datasets; Melnik et al.; SIGMOD 2010.
  4. Delta Lake: High-Performance ACID Table Storage over Cloud Object Stores; Armbrust et al.; SIGMOD 2020.

Sept 29, Oct 1 — Paper Presentations and Discussions

Paper presentations and discussions. Papers and reviewer assignments to follow.

Critiques due: Thursday, Sept 24, 11:59pm. See Assignments.

Oct 6 — No class

Oct 8, 15, 20 — Query Processing and Optimization I (NO CLASS OCT 13 – FALL BREAK)

We will go deeper into how queries are executed and optimized, focusing on more recent techniques. We cover these topics for traditional relational database management systems, modern data warehouses, and data lakes.

Slides: 4-Query-Part-1 · 4-Query-Part-2

Lecture notes (Module 4): Query Evaluation Techniques · Parallel Execution and Skew · Vectorized Execution · Compilation and Morsel-Driven Parallelism

Main readings:

  1. Goetz Graefe. Query Evaluation Techniques for Large Databases (Sections 1 and 2). ACM Computing Surveys 25(2): 73–170, 1993. [link]
  2. Practical Skew Handling in Parallel Joins; VLDB 1992.
  3. P. Boncz et al. MonetDB/X100: Hyper-Pipelining Query Execution; CIDR 2005.
  4. Efficiently Compiling Efficient Query Plans for Modern Hardware; VLDB 2011. (You can skim Sections 4 onward.)
  5. Surajit Chaudhuri. An Overview of Query Optimization in Relational Systems. PODS 1998: 34–43.

Oct 22, 27, 29 — Query Processing and Optimization II

Continued from above.

Main readings:

  1. How Good Are Query Optimizers, Really?; VLDB 2015.
  2. Outerjoin Simplification and Reordering for Query Optimization (Sections 1–3); TODS 1997.
  3. Extensible/Rule Based Query Rewrite Optimization in Starburst; SIGMOD 1992.
  4. Execution Strategies for SQL Subqueries; SIGMOD 2007.
  5. Ron Avnur and Joseph M. Hellerstein. Eddies: Continuously Adaptive Query Processing. SIGMOD 2000.
  6. Volker Markl, Vijayshankar Raman, David Simmen, Guy Lohman, Hamid Pirahesh, Miso Cilimdzic. Robust Query Processing Through Progressive Optimization. SIGMOD 2004.
  7. Permutable Compiled Queries: Dynamically Adapting Compiled Queries Without Recompiling; VLDB 2018.

Nov 3, 5, 10 — Paper Presentations and Discussions

Paper presentations and discussions. Papers and reviewer assignments to follow.

Critiques due: Thursday, Oct 29, 11:59pm. See Assignments.

Nov 12 — Query Processing and Optimization III

Continued from above.

Main readings:

  1. Skew Strikes Back: New Developments in the Theory of Join Algorithms; SIGMOD Record 2013.
  2. Optimizing Imperative Functions in Relational Databases with Froid; VLDB 2018.

Nov 17, 19 — Data Streams and Dataflow Engines (No class November 24)

We will spend a few classes discussing topics in processing data in real time.

Main readings:

  1. Maintenance of Materialized Views: Problems, Techniques, and Applications; A. Gupta, I. S. Mumick; IEEE Data Eng. Bull., 1995.
  2. Discretized Streams: Fault-Tolerant Streaming Computation at Scale; SOSP 2013.
  3. Watermarks in Stream Processing Systems: Semantics and Comparative Analysis of Apache Flink and Google Cloud Dataflow; VLDB 2021.
  4. Incremental, Iterative Data Processing with Timely Dataflow; CACM 2016.

Dec 1, 3 — Paper Presentations and Discussions

Paper presentations and discussions. Papers and reviewer assignments to follow.

Critiques due: Tuesday, Nov 24, 11:59pm (a Tuesday rather than the usual Thursday, since that Thursday is Thanksgiving). See Assignments.

Dec 8, 10 — Project Presentations