Tentative schedule -- copied from last year -- expect changes
Schedule and Readings
Aug 29, Aug 31, Sept 5: Introduction/Overview, and Background [show/hide]
In the first two clases, we will cover:
History of database management systems, what problems they are trying to solve, the state of the art, and what we plan to cover in this semester.
Relational Model, SQL, and how traditional relational database management systems are built (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/programming frameworks, storage models, transaction support,
guarantees, etc.), and what the impact of those design decisions might be. Most of this discussion will be at a high level, and we will dive deeper into
the specifics for a few of those topics later in the course. We will also talk about some of the orthogonal but important concerns like streaming
systems, and immutability.
"Architecture of a Database System"; Joe Hellerstein, Mike Stonebraker, James Hamilton; Foundations and Trends 2007. (original paper; A crop-merged Version of that PDF): An overview of how traditional database management systems are built, and some of the key design considerations.
Additional Readings:
Database System Concepts; Avi Silberschatz, Henry F. Korth, S. Sudarshan: This is the textbook for the undergraduate class and may be a good reference
to brush up on any background that we don't cover in depth in class. [link]
For a nice historical overview of database management systems, see the first paper ("Evolution of ..") in this ACM Computing Surveys, Mach 1976
Concurrency Control and Recovery; Mike Franklin, 1997 [pdf link]: We won't cover this topic much in this class, but this paper provides a nice introduction to it that you should be comfortable with.
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, we will discuss: Relational Model and SQL, Document data model (e.g., MongoDB), Entity-relationship Model and ORM frameworks, Map-Reduce and Spark, Graph data models, REST, OLAP, Visualization, Machine Learning Frameworks (in varying levels of detail). We will also discuss the importance of "schemas" and the challenges of "schema evolution".
Main readings:
(Sept 7) "What goes around comes around"; Mike Stonebraker and Joe Hellerstein; Redbook.: This paper summarizes how "data models" evolved over the last 50 years.
(Sept 7) A Survey of Research on Deductive Database Systems (Sections 1-4); Ramakrishnan and Ullman; 1993 (http://ilpubs.stanford.edu:8090/80/)
(Sept 12) Declarative Networking: Language, Execution and Optimization (Sections 1, 2, and 4); Loo et al.; SIGMOD 2016.
(Sept 12) MapReduce: A Flexible Data Processing Tool (Sections 1-2); Jeffrey Dean and Sanjay Ghemawat; CACM 2010
(Sept 14) SystemML: Declarative Machine Learning On MapReduce (Sections I-III(A)); Ghoting et al.; ICDE 2011.
(Sept 19) GraphX: Graph Processing in a Distributed Dataflow Framework (Section 1-3); OSDI 2014 ([link])
Optional Readings:
Database System Concepts; Avi Silberschatz, Henry F. Korth, S. Sudarshan. Two Appendixes covering network model and hierarchical model in detail are available on the book webpage (for the 6th edition). [link]
Joachim W. Schmidt. Some High Level Language Constructs for Data of Type Relation. ACM Transactions on Database Systems, 2(3), 1977, 247-261.
MapReduce and Parallel DBMSs: Friends or Foes? Stonebraker et al.; CACM 2010
Sept 26-28: Storage Models and Indexing[show/hide]
We will discuss how the data is stored on disks and in memory, and the impact of those design decisions. Specifically, we will discuss row and column storage formats for databases, and the prevalent storage formats for data lakes that are widely used today.
Main readings:
(Sept 21) Weaving Relations for Cache Performance; Ailamaki et al.; VLDB 2001.
(Sept 26) Integrating compression and execution in column-oriented database systems; Abadi et al.; SIGMOD 2006.
(Sept 26) Dremel: interactive analysis of web-scale datasets; Melnik et al.; SIGMOD 2010.
(Sept 28) Delta lake: high-performance ACID table storage over cloud object stores; Armbrust et al.; SIGMOD 2020.
Weeks of Oct 3, Oct 10, Oct 17, Oct 24, Oct 31, Nov 7: Query Processing and Optimization[show/hide]
We will go deeper into how queries are executed and optimized, focusing on more recent techniques for this. We will cover these topics for traditional relational database management systems, modern data warehouses, and data lakes.
Main readings:
(Oct 3) Goetz Graefe: Query Evaluation Techniques for Large Databases (Sections 1 and 2). ACM Comput. Surv. 25(2): 73-170 (1993) [link]
(Oct 3) Practical Skew Handling in Parallel Joins; VLDB 1996
(Oct 5) P. Boncz, et al., MonetDB/X100: Hyper-Pipelining Query Execution; CIDR, 2005
(Oct 5) Efficiently Compiling Efficient Query Plans for Modern Hardware; VLDB 2011 (you can skim Sections 4-)
(Oct 10) Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43;
(Oct 12) How good are query optimizers really?; VLDB 2015
(Oct 12) Outerjoin Simplification and Reordering for Query Optimization (Section 1-3); TODS 1997
(Oct 17) Extensible/Rule Based Query Rewrite Optimization in Starburst; SIGMOD 1992
(Oct 17) Unnesting arbitrary queries; BTW 2015
(Oct 19) Execution Strategies for SQL Subqueries; SIGMOD 2007
(Oct 24) Ron Avnur and Joseph M. Hellerstein. Eddies: Continuously Adaptive Query Processing. SIGMOD, 2000.
(Oct 24) Volker Markl, Vijayshankar Raman, David Simmen, Guy Lohman, Hamid Pirahesh, Miso Cilimdzic. Robust Query Processing Through Progressive Optimization. SIGMOD, 2004.