CS 764, Fall 2009: Topics in Database Management Systems

Coordinates: CS 1257, 01:00 PM - 02:15 PM, Tu, Th
Instructor: J. Patel
Office Hours: Tuesday noon-1:00PM or by appointment

Description

This course covers a number of advanced topics in development of database management systems (DBMs) and the application of DBMSs in modern applications. Topics to be discussed include advanced concurrency control and recovery techniques, query processing and optimization strategies for relational database systems, advanced access methods, parallel and distributed database systems, extensible database systems, data analysis on large databases.

The course material will be drawn from a number of papers in the database literature. We will cover about 2 papers per week. All students in this class are expected to read the papers before coming to the lecture.

Prequesites: CS 564 or equivalent. If you have concerns about meeting the prerequisties, please contact the instructor.

Text: There is no formal textbook for this course. The reading list is a collection of papers, which is posted on the course web page.
 
Reference text: The following two sources will be used occassionally in this course. Note you don't need to buy these books.

Course Project

A big component of this course is a research project. For the project, you pick a topic in the area of database systems, and explore it in detail. I will provide a list of suggested project topics, though you are free to select a project outside of this list provided you get prior approval. I require that you meet with me periodically throughout the semester updating me on the progress of your project. I will help with the direction, but unless you take the initiative to actively explore the topic you choose, you are unlikely to accomplish much in the project (which will adversely affect your project grade).

The course project is a group project, and each group must be of size 2 or 3. Please start looking for project partners right away. I will facilitate informal group formation by holding a socializing session at the end of the first few lectures, but it is your responsibility to form and manage groups.

The course project will include an interim course project report, a short project presentation at the end of the semester, and a final project report with a demo. I organize the final project presentation in a workshop-like format. The workshop is called DAWN. Here is the program for DAWN'08 (the last time I taught the course in Fall 2008).

Grading and Deadlines (Tentative!)

Midterm 30% 1:00-2:15PM, October 15, 2009.
Final 30% 1:00-2:15PM, December 15, 2009.
Course Project 40% Project selection. Due Sept 24, 1:00PM.
5% for interm course report. Due October 27, 1:00PM.
30% for project report and demo. Demos are scheduled by appointment. Demos must be scheduled between Dec 18 and 22. Final report due by Dec 22, 1:00PM.
5% for short project presentation as part of a workshop called DAWN'09, held during the class on Dec 8 and 10.  

Reading List

Here is the reading list. Links to local copies on this page are password protected. Passwords will be given out on the first day of class.  This list is subject to change during the semester. When changes happen, I will let you know in advance.
Query Processing
I will assume you have covered chapters 12-15 of the Cow book, or its equivalent, in your UG course.
  1. Join Algorithms: Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264 (1986)
  2. Query Optimization-1: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 
  3. Query Optimization-2: Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43
Buffer Management
  1. Buffer Management: Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. Algorithmica 1(3): 311-336 (1986).
Advanced Transaction Management
I will assume you have covered chapters 16-18 of the Cow book, or its equivalent, in your UG course.
  1. Granularity of Locks: Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, Irving L. Traiger: Granularity of Locks and Degrees of Consistency in a Shared Data Base. IFIP Working Conference on Modelling in Data Base Management Systems 1976.
  2. Oracle CC: Multiuser Concurrency in Oracle. Access from UW via link. Click on "Start Reading Online" and go to Chapter 8: Oracle Multiuser Concurrency. If you have trouble accessing the link contact the instructor.
  3. Optimistic CC: H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226 (1981).
  4. B-tree Locking: Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670 (1981)
  5. Aries Recovery: C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162 (1992)
  6. 2-Phase Commit: C. Mohan, Bruce G. Lindsay, Ron Obermarck: Transaction Management in the R* Distributed Database Management System. ACM Trans. Database Syst. 11(4): 378-396 (1986)
Parallel and Distributed DBMSs
  1. Distributed DBMSs: Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah, Jeff Sidell, Carl Staelin, Andrew Yu: Mariposa: A Wide-Area Distributed Database System. VLDB Journal 5(1): 48-63 (1996).
  2. Replication: Jim Gray, Pat Helland, Patrick E. O'Neil, Dennis Shasha: The Dangers of Replication and a Solution. SIGMOD Conference 1996: 173-182.
  3. Parallel DBMSs: David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Comm. ACM 35(6): 85-98 (1992).
Advanced Access Methods
  1. R-tree: Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57.
  2. Bitmap Indices: Patrick E. O'Neil, Dallan Quass: Improved Query Performance with Variant Indexes. SIGMOD Conference 1997: 38-49.
Advanced Data Models
  1. OODBMS: Charles Lamb, Gordon Landis, Jack A. Orenstein, Danel Weinreb: The ObjectStore Database System. CACM 34(10): 50-63 (1991).
  2. Bucky: Michael J. Carey, David J. DeWitt, Jeffrey F. Naughton, Mohammad Asgarian, Paul Brown, Johannes Gehrke, Dhaval Shah: The BUCKY Object-Relational Benchmark (Experience Paper). SIGMOD Conference 1997: 135-146.
  3. Data Model History, and XML as a data model
  4. XQuery 
Data Analysis and Decision Support
  1. OLAP: Jim Gray et al.: Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals. Data Mining and Knowledge Discovery 1(1): 29-53 (1997).
  2. Mining: Rakesh Agrawal, Ramakrishnan Srikant: Fast Algorithms for Mining Association Rules in Large Databases. VLDB 1994: 487-499.
Misc (time permitting)
  1. DBMS and MR: Andrew Pavlo, Erik Paulson, Alexander Rasin, Daniel J. Abadi, David J. DeWitt, Samuel Madden, Michael Stonebraker: A comparison of approaches to large-scale data analysis. SIGMOD Conference 2009: 165-178
  2. C-Store: Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Samuel Madden, Elizabeth J. O'Neil, Patrick E. O'Neil, Alex Rasin, Nga Tran, Stanley B. Zdonik: C-Store: A Column-oriented DBMS. VLDB 2005: 553-56.
The Art of Reading Papers (read on your own)
  1. Read Efficiently: Michael J. Hanson and updated by D. McNamee: Efficient Reading of Papers in Science and Technology, 1989.    
  2. Write Well: Patrick Valduriez, “Some Hints to Improve Writing of Technical Papers”, Correspondence in Engineering of Information Systems, Hermes, Vol. 2, No. 3, 1994.