CMSC724: Database Management Systems

CMSC724: Database Management Systems
Prof. Amol Deshpande; CSIC 2120; Tue-Thur 11:00am-12:15pm

[Home]	[Schedule]	[Projects]	[Resources]

For each of the required papers, a critique must be submitted by 10:30am the day of the class. More below.

The posted slides may be from last time (annotated "spring 2009"), and I will post the updated slides before the class.

Schedule

Jan 25: Introduction/Overview [spring 2009 slides]
Jan 27: History/Data Modeling [spring 2009 slides] [text notes]
- (required reading - no summary) "What goes around comes around"; Mike Stonebraker and Joe Hellerstein; Redbook.
- (background/reference) 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. [link]
- (followup) The Relational vs Network Models Debate
Feb 1: History/Data Modeling [some notes on Codd's paper]
- (summary required) "A Relational Model of Data for Large Shared Data Banks". E. F. Codd. Commun. ACM 13(6): 377-387 (1970). [pdf]
- (summary required) "Querying semi-structured data". Serge Abiteboul. ICDT 1997. [pdf]
- (followup) Is your database relational ? Ted Codd Wikiepdia article
Feb 3: Anatomy of a Database System [spring 2009 slides]
- (required reading - no summary) "Anatomy of a Database System"; Joe Hellerstein and Mike Stonebraker; Redbook. (A newer version can be found at link. A crop-merged Version of that PDF)
- (summary required) Michael Stonebraker. Operating System Support for Database Management. Commun. ACM, 24(7), 1981, 412-418.
  (Instead of a critique/summary, you could instead write a paragraph on how today's OS can address some of the problems presented in this paper, e.g. look at mmap support in Unix.)
Feb 8: Query Processing [spring 2009 slides]
- (background/reference) Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170 (1993) [link]
- (summary required) Leonard D. Shapiro. Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst., 11(3), 1986, 239-264. [link to pdf]
Feb 10: Query Processing (Cntd notes from above)
- (summary required) Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price. Access Path Selection in a Relational Database Management System. Proc. SIGMOD Conference, 1979, 23-34. [link to pdf]
- (background/reference) Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43; [link to pdf]
- A very nice overview of DB2 Optimizer (by Guy Lohman)
Feb 15: Query Processing/Data Streams (Cntd notes from above)
- (summary required) Ron Avnur, Joseph M. Hellerstein. Eddies: Continuously Adaptive Query Processing. Proc. SIGMOD Conference, 2000, 261-272. [link to pdf]
- (summary required) Stratis Viglas, Jeffrey F. Naughton, Josef Burger. "Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources". VLDB 2003: 285-296 [pdf]
Feb 17: Eddies/Adaptive Query Processing (Cntd notes from above)
- (summary required) "The 8 Requirements of Real-Time Stream Processing"; M. Stonebraker, U. Cetintemel, and S. Zdonik. In SIGMOD Record, 2005. [pdf]
- (background/reference) Adaptive Query Processing; Amol Deshpande, Zack Ives, Vijayshankar Raman; FnT, 2007. [Paper PDF][PPT Slides]
Feb 22: Query Processing/Parallel Databases [spring 2009 slides]
- (summary required) David J. DeWitt Jim Gray. Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM, 35(6), 1992, 85-98.
- (summary required) Goetz Graefe. Encapsulation of Parallelism in the Volcano Query Processing System. Proc. SIGMOD Conference, 1990, 102-111.
- (background/followup) Database machines: an idea whose time has passed? A critique of the future of database machines; Boral and DeWitt; 1983 [Paper PDF]
Feb 24: Mapreduce/Parallel Databases [spring 2009 slides]
- (summary required) MapReduce: Simplified Data Processing on Large Clusters; Jeffrey Dean and Sanjay Ghemawat; OSDI'04: Sixth Symposium on Operating System Design and Implementation
- (summary required) MapReduce: A major step backwards; DeWitt and Stonebraker; 2008 [blog post 1] [blog post 2]
Mar 1: Data Storage and Access Methods [spring 2009 slides]
- (required reading - no summary) The HP AutoRAID Hierarchical Storage System; Wilkes, Golding, Staelin and Sullivan; ACM TOCS 1996 [link]
- (summary required) Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. Proc. SIGMOD Conference, 1990, 322-331.
Mar 3: Data Storage and Access Methods [spring 2009 slides]
- (summary required) Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer. Generalized Search Trees for Database Systems. Proc. VLDB, 1995, 562-573.
Mar 8: Extensible Systems [spring 2009 slides]
- (summary required) Michael Stonebraker. Inclusion of New Types in Relational Data Base Systems. Proc. ICDE, 1986, 262-269.
- (required reading - no summary) MauveDB: Supporting Model-based User Views in Database Systems; Amol Deshpande, Sam Madden; SIGMOD 2006.
Mar 10: Data Mining [spring 2009 slides]
- (summary required) Tian Zhang, Raghu Ramakrishnan, Miron Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases. Proc. SIGMOD Conference, 1996, 103-114.
Mar 15: Data Mining (Cntd notes from above)
- (summary required) John C. Shafer, Rakesh Agrawal, Manish Mehta. SPRINT: A Scalable Parallel Classifier for Data Mining. Proc. VLDB, 1996, 544-555.
- (summary required) Surajit Chaudhuri, Vivek R. Narasayya, Sunita Sarawagi. Efficient Evaluation of Queries with Mining Predicates. Proc. ICDE, 2002, 529-.
March 17: TBD.
Mar 22: Spring Break
Mar 24: Spring Break
March 29: Midterm (in-class)
March 31: TBD.
April 5: Transactions: Concurrency [spring 2009 slides]
- (summary required) Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, Irving L. Traiger. Granularity of Locks and Degrees of Consistency in a Shared Data Base. IBM, September, 1975.
- Berenson et al. A Critique of ANSI SQL isolation levels; SIGMOD 1995 [link]
April 7: Transactions: Concurrency (Cntd notes from above)
- (summary required) H. T. Kung, John T. Robinson. On Optimistic Methods for Concurrency Control. Proc. VLDB, 1979, 351.
- (summary required) Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981)
April 12: Transactions: Recovery [spring 2009 slides]
- (summary required) 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), 1992, 94-162. (Till Section 7)
April 14: Transactions: Distributed Databases [spring 2009 slides]
- (summary required) C. Mohan, Bruce G. Lindsay, Ron Obermarck. Transaction Management in the R* Distributed Database Management System. ACM Trans. Database Syst., 11(4), 1986, 378-396.
April 19: Guest Lecture: Probabilistic Databases [spring 2009 slides]
- (summary required) Efficient query evaluation on probabilistic databases; Nilesh Dalvi, Dan Suciu; VLDB 2004
April 21: Data Warehousing [spring 2009 slides]
- (summary required) Patrick E. O'Neil, Dallan Quass. Improved Query Performance with Variant Indexes.. Proc. SIGMOD Conference, 1997, 38-49.
April 26: Data Warehousing
- (summary required) Jim Gray, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, Murali Venkatrao, Frank Pellow, Hamid Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub Totals. Data Min. Knowl. Discov., 1(1), 1997, 29-53.
- (summary required) DynaMat: a dynamic view management system for data warehouses; Yannis Kotidis, Nick Roussopoulos. SIGMOD Conference 1999.
April 28: New Applications: Search Engines [spring 2009 slides]
- (summary required) Eric A. Brewer. Combining Systems and Databases: A Search Engine Retrospective.
May 3: New Applications: XML [spring 2009 slides]
- (summary required) Relational Databases for Querying XML Documents: Limitations and Opportunities; Jayavel Shanmugasundaram et al.; VLDB 1999
May 5: TBD.
May 10: TBD.

Critiques

This is a research-oriented class and hence the main work in this class is independently reading and evaluating research papers in the field of databases. For each of the assigned papers, you should submit a critique before the class. The critiques should show evidence of independent thinking, and there are many ways you could structure those. Here are two suggestions:

A short summary (4-5 lines), followed by 3 strong points of the paper (things you liked about it) and 3 weak points of the paper.
A short summary (4-5 lines), followed by 3 questions about the content of the paper.

I will post examples of some summaries after the first paper (or you can look at some examples from last year here).

The critique should be posted on the class forum in the thread corresponding to the paper. The forum is set to be a private forum, so you must join the group "CMSC 724 Spring 2011" before you can post in it. To join the group, follow the instructions at: Joining a Group.

Critiques are worth about 20% (along with class participation).

Late submissions or no submissions will be penalized. Missing upto two summaries is fine. Beyond that: 3 missed or late submissions - 5/20 points deducted. 4 missed submissions, 10/20 deducted. 5 missed submissions 20/20 deducted.