CPS 216: Advanced Database Systems
(Spring 2003)


Lecture Notes & Reading Assignments

WeekDate TopicNotes*Slides** Reading
12003-01-08 Introduction PDF PDF
22003-01-13 Relational model and algebra PDF PDF A Relational Model of Data for Large Shared Data Banks, by Codd (in red book).
2003-01-15 Relational database design PDF PDF
2003-01-17 Recitation session: E/R model and design PDF
32003-01-20 Martin Luther King, Jr. Day holiday A History and Evaluation of System R, by Chamberlin et al. (in red book).
2003-01-22 SQL schema definition and query basics PDF PDF
42003-01-27 SQL subqueries, aggregates, NULL's PDF PDF A Critique of the SQL Database Language, by Date. SIGMOD Record, 14(3), 1984.
2003-01-29 SQL modifications, constraints, triggers, views PDF PDF
2003-01-31 Recitation session: SQL PDF
52003-02-03 SQL index, transactions, and application programming PDF PDF A History and Evaluation of Critique of ANSI SQL Isolation Levels, by Berenson et al. SIGMOD 1995.
Weaving Relations for Cache Performance, by Ailamaki et al. VLDB 2001.
2003-02-05 Physical data organization PDF PDF
2003-02-07 Recitation session: SQL programming and Homework #1
62003-02-10 Indexing: basics, ISAM, B-tree PDF PDF The Evolution of Effective B-tree Page Organization and Techniques: A Personal Account, by Lomet. SIGMOD Record, 2001.
R-Trees: A Dynamic Index Structure for Spatial Searching, by Guttman. SIGMOD 1984 (in red book).
Generalized Search Trees for Database Systems, by Hellerstein et al. VLDB 1995 (in red book).
2003-02-12 Indexing: R-tree, GiST PDF PDF
72003-02-17 Data stream management (guest lecture by Jennifer Widom) PDF A Study of Index Structures for Main Memory Database Management Systems, by Lehman and Carey. VLDB 1986.
2003-02-19 Indexing: more GiST, hashing PDF PDF
2003-02-21 Recitation session: Homework #2
82003-02-24 Indexing: more hashing, text indexing PDF PDF Cache Conscious Indexing for Decision-Support in Main Memory, by Rao and Ross. VLDB, 1999.
Making B+-Trees Cache Conscious in Main Memory, by Rao and Ross. SIGMOD, 2000.
2003-02-26 Main-memory indexing PDF PDF
2003-02-28 Recitation session: midterm review
92003-03-03 Midterm exam Query Evaluation Techniques for Large Databases, by Graefe. ACM Computing Surveys, 1993.
2003-03-05 No class
102003-03-10 Spring recess
2003-03-12 Spring recess
112003-03-17 Query processing: scan, sort, hash PDF PDF Improved Query Performance with Variant Indexes, by O'Neil and Quass. SIGMOD, 1997 (in red book).
2003-03-19 Query processing using indexes PDF PDF
2003-03-21 Recitation session: midterm common problems
122003-03-24 Query processing: systems view PDF PDF An Evaluation of Buffer Management Strategies for Relational Database Systems, by Chou and DeWitt. VLDB, 1985 (in red book).
Query Rewrite Optimization Rules in IBM DB2 Universal Database, by Leung et al. (in red book).
2003-03-26 Buffer management PDF PDF
2003-03-28 Recitation session: quiz PDF
132003-03-30 Query optimization: rewrite PDF PDF Improved Histograms for Selectivity Estimation of Range Predicates, by Poosala et al. SIGMOD, 1996.
Access Path Selection in a Relational Database Management System, by Selinger et al. SIGMOD, 1979 (in red book).
2003-04-02 Query optimization: cost estimation PDF PDF
2003-04-04 Recitation session: quiz PDF
142003-04-07 Query optimization: algorithms PDF PDF Randomized Algorithms for Optimizing Large Join Queries, by Ioannidis and Kang. SIGMOD, 1990.
Online Aggregation, by Hellerstein et al. SIGMOD, 1997 (in red book).
Eddies: Continuously Adaptive Query Processing, by Avnur and Hellerstein. SIGMOD, 2000.
2003-04-09 Online query processing and optimization PDF PDF
152003-04-14 Transaction processing: concurrency control PDF PDF
2003-04-16 Transaction processing: recovery PDF PDF
2003-04-18 Recitation session: Homework #4
162003-04-21 More recovery; end-semester logistics PDF
172003-05-01 Final exam (D243 2-5pm)

* Generally available in the morning on the day of the lecture. They are intentionally made incomplete in order to keep the lectures more lively. You can print these slides out and use them for taking notes during the lecture. These slides may contain typos/errors that are corrected only in the complete version.

** Available on the same day after the lecture. They are complete, with typos/errors corrected.


Assignment Download Assigned Due
Homework #1 PDF Wednesday, 2003-01-22 Monday, 2003-02-10
Homework #2 PDF Wednesday, 2003-02-12 Wednesday, 2003-02-26
Homework #3 PDF Wednesday, 2003-03-26 Wednesday, 2003-04-09
Homework #4 PDF Wednesday, 2003-04-09 Wednesday, 2003-04-23
Project PDF Wednesday, 2003-01-22 See project description

Programming Notes