CSE 444 Readings

Please note that I will refine the list of readings as we go along.

We provide book chapter information for both books: The Ullman book (chapters are inside the brackets) and the Ramakrishnan book [chapters are specified inside the square brackets]

Lecture 2: Review of relational model and SQL

• The Relational Model of Data (Chapter 2) [Chapter 3]
• Relational Algebra (Sections 5.1, 5.2, and 5.4) [Chapter 4]
• SQL (Chapter 6 except for Section 6.6) [Chapters 3 and 5]

Lecture 3: DBMS architecture and deployments

• Overview of a DBMS (Section 1.2) [Chapter 1]
• SQL in a Server Environment (Sections 9.1 and 9.2) [Section 7.5]
• Optional: Weaving Relations for Cache Performance Sections 2.1 and 3

Lectures 4-6: Data storage and indexing

• Views and Indexes in SQL (Chapter 8) [Section 3.6 and 8.5]
• Data storage (Sections 13.5 and following except for 13.6.3 and 13.6.4) [Sections 8.1-8.3, Sections 9.5-9.7]
• Buffer management (Section 15.7) [Section 9.4]
• Indexes (Sections 14.1 through 14.4) [Sections 8.1-8.3, Chapters 10 and 11]

Lectures 7-8: Query execution and operator algorithms

• Query Execution and Operator Algorithms (Chapter 15) [Chapters 12, 13, and 14]

Lectures 9-12: Query optimization

• Query Optimization (Chapter 16) [Chapter 15]
• Optional: P. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, and T. Price. Access Path Selection in a Relational Database Management System. Proceedings of ACM SIGMOD, 1979. Pages 22-34. Also in the Red Book (3rd ed and 4th ed) [pdf]
  • This paper is very hard to read
  • But the example on page 30 (i.e., page 8 in the pdf) in the section called: "Example of tree" is readable and corresponds to the example that we went through in class.

Lectures 13-18: Transactions

• Transactions in SQL (Section 6.6) [Section 16.6]
• Transactions and concurrency control (Chapters 18 and 19) [Chapters 16 and 17]
• Transactions and recovery (Chapter 17 and 19) [Chapter 18]
• Michael J. Franklin. Concurrency Control and Recovery. The Handbook of Computer Science and Engineering, A. Tucker, ed., CRC Press, Boca Raton, 1997. [pdf]

Lectures 19-21: Parallel data processing

• Definition and basic concepts in parallel databases (Section 20.1) [Sections 22.1-22.6]
• Map-reduce (Section 20.2); Chapter 2 (Sections 1,2,3 only) of Mining of Massive Datasets, by Rajaraman and Ullman.
• MapReduce: Simplified Data Processing on Large Clusters. Jeffrey Dean and Sanjay Ghemawat. OSDI'04: Sixth Symposium on Operating System Design and Implementation.

Lectures 22-24: Distribution and Replication

• Distributed query processing (Sections 20.3 through 20.6) [Sections 22.7 until the end of the chapter]
• C. Mohan, B. Lindsay, and R. Obermarck. Transaction Management in the R* Distributed Database Management System. ACM Transactions On Database Systems 11 (4), 1986. Also in the Red Book (3rd and 4th ed). [pdf]

Lectures 25-27: NoSQL and NewSQL

• Scalable SQL and NoSQL Data Stores by Rick Cattell, SIGMOD Record, December 2010 (Author keeps revising this survey).
• SQL Databases v.s. NoSQL Databases by Mike Stonebraker, CACM Blog.
• Dynamo: Amazon's highly available key-value store. By Giuseppe DeCandia et. al. SOSP 2007.
• Bigtable: A Distributed Storage System for Structured Data. ByFay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. OSDI 2006.
• The end of an Architectural Era: (It’s Time for a Complete Rewrite) By M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland in VLDB ’07: Proceedings of the 33rd international conference on Very large data bases, 2007, pp. 1150-1160.
• The VoltDB Main Memory DBMS, IEEE Data Engineering Bulletin, 2013, pp. 21-27.