Jan 24, Jan 26: 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:
(Jan 31) "What goes around comes around"; Mike Stonebraker and Joe Hellerstein; Redbook.: This paper summarizes how "data models" evolved over the last 50 years.
(Jan 31) A co-Relational Model of Data for Large Shared Data Banks; Meijer and Bierman; CACM 2011.
(Feb 2) A Survey of Research on Deductive Database Systems (Sections 1-4); Ramakrishnan and Ullman; 1993 (http://ilpubs.stanford.edu:8090/80/)
(Feb 2) Declarative Networking: Language, Execution and Optimization (Sections 1, 2, and 4); Loo et al.; SIGMOD 2016.
(Feb 7) MapReduce: A Flexible Data Processing Tool (Sections 1-2); Jeffrey Dean and Sanjay Ghemawat; CACM 2010
(Feb 9) SystemML: Declarative Machine Learning On MapReduce (Sections I-III(A)); Ghoting et al.; ICDE 2011.
(Feb 14) 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
Feb 16, Feb 21, Feb 23: 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:
(Feb 16) Weaving Relations for Cache Performance; Ailamaki et al.; VLDB 2001.
(Feb 21) Integrating compression and execution in column-oriented database systems; Abadi et al.; SIGMOD 2006.
(Feb 21) Dremel: interactive analysis of web-scale datasets; Melnik et al.; SIGMOD 2010.
(Feb 23) Delta lake: high-performance ACID table storage over cloud object stores; Armbrust et al.; SIGMOD 2020.
Weeks of Feb 28, March 7, March 14, March 28, and April 4 : 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:
(Feb 28) Goetz Graefe: Query Evaluation Techniques for Large Databases (Sections 1 and 2). ACM Comput. Surv. 25(2): 73-170 (1993) [link]
(Feb 28) Practical Skew Handling in Parallel Joins; VLDB 1996
(March 2) P. Boncz, et al., MonetDB/X100: Hyper-Pipelining Query Execution; CIDR, 2005
(March 2) Efficiently Compiling Efficient Query Plans for Modern Hardware; VLDB 2011 (you can skim Sections 4-)
(March 7) Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43;
(March 9) How good are query optimizers really?; VLDB 2015
(March 9) Outerjoin Simplification and Reordering for Query Optimization (Section 1-3); TODS 1997
(March 14) Extensible/Rule Based Query Rewrite Optimization in Starburst; SIGMOD 1992
(March 14) Unnesting arbitrary queries; BTW 2015
(March 16) Execution Strategies for SQL Subqueries; SIGMOD 2007
(March 28) Ron Avnur and Joseph M. Hellerstein. Eddies: Continuously Adaptive Query Processing. SIGMOD, 2000.
(March 28) Volker Markl, Vijayshankar Raman, David Simmen, Guy Lohman, Hamid Pirahesh, Miso Cilimdzic. Robust Query Processing Through Progressive Optimization. SIGMOD, 2004.