CMSC724: Database Management Systems

CMSC724: Database Management Systems
Prof. Amol Deshpande; CSIC 3118; Tue-Thur 3:30pm-4:45pm

[Home]	[Schedule]	[Assignments]	[Resources]

For each of the required papers, a critique must be submitted by 1:00pm the day of the class. More below.

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

Schedule

Jan 26: Introduction/Overview [slides]
- Today's discussion of history was partly from the first paper ("Evolution of ..") in this ACM Computing Surveys, Mach 1976
Jan 31: History/Data Modeling [slides], [modeling text notes]
- (summary required) "A Relational Model of Data for Large Shared Data Banks". E. F. Codd. Commun. ACM 13(6): 377-387 (1970). [pdf]
  
  Think about:
  Codd's paper was prescient and foreshadowed many developments in the relational model. How did the operators he define compare to the relational algebra operators of today (especially see his definition of "join")? "Connection Trap" is interesting concept, and somewhat subtle. Cood had beginnings of the idea of "normal forms" (he only defines 1NF though); but weak redundancy was one notion that did not lead anywhere. Notes: Some notes on the paper
- (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]
- (background/reference) The Relational vs Network Models Debate
- (background/reference) Is your database relational ? Ted Codd Wikiepdia article
Feb 2: History/Data Modeling (Continued from above) [normalization overview slides (spring 2011)]
- (summary required) "Querying semi-structured data". Serge Abiteboul. ICDT 1997. [pdf]
Feb 7: Architecture of a Database System [slides]
- (required reading - no summary) "Architecture of a Database System"; Joe Hellerstein, Mike Stonebraker, James Hamilton; Foundations and Trends 2007. (original paper; A crop-merged Version of that PDF)
Feb 9: Architecture of a Database System (Continued from above)
Feb 14: Query Processing [slides]
- (summary required) Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170 (1993) [link]
  
  Notes: This is a survey paper that covers the query processing architecture, operators, alternatives, advanced issues in great depth. You are required to read Sections 1 through 5.
  A critique/summary is required -- given the nature of the paper, this could either be questions about the paper -- something that you were not able to follow, or you could write some thoughts on how relevant are the tradeoffs discussed in the paper today -- e.g., query processing model/operators are based on the assumption that the data is disk-resident: how would this change if the storage media was primarily flash or a distributed key/value store like Google Bigtable where the data is stored in a distributed fashion in memory, with replication? Are large amounts of main memory making many of the tradeoffs irrelevant anyway?
Feb 16: Query Processing/Column-Stores (Slides cntd from above)
- (summary required) Column-stores vs. row-stores: how different are they really? Abadi et al.; SIGMOD 2008 [link to pdf]
Feb 21: In-class Midterm
Feb 23: Query Optimization (Slides cntd from above)
- (summary required) Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43; [link to pdf]
  
  Notes: This is also a (short) survey paper. See Feb 24 reading for suggestions on how to write a critique.
- A very nice overview of DB2 Optimizer (by Guy Lohman)
Feb 28: Data Streams (Slides cntd from above)
- (required reading -- summary not required) Continuous queries over data streams; Babu, Widom; SIGMOD Record 2001[link to pdf]
- (optional) "The 8 Requirements of Real-Time Stream Processing"; M. Stonebraker, U. Cetintemel, and S. Zdonik. In SIGMOD Record, 2005. [pdf]
Mar 1: Parallel Databases; Mapreduce [slides]
- (summary required) MapReduce: A Flexible Data Processing Tool; Jeffrey Dean and Sanjay Ghemawat; CACM 2010
- (summary required) MapReduce and Parallel DBMSs: Friends or Foes? Stonebraker et al.; CACM 2010
  
  Notes: Write a single critique for both the papers combined.
Mar 6: Key/Value Stores (Slides cntd from above)
- (summary required) PNUTS: Yahoo!'s Hosted Data Serving Platform; Cooper et al.; VLDB 2008 [link]
- (optional reading) Pig latin: a not-so-foreign language for data processing; SIGMOD 2008 [link]
Mar 8: Access Methods [slides]
- (summary required) Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer. Generalized Search Trees for Database Systems. Proc. VLDB, 1995, 562-573.
Mar 13: Data Mining [spring 2011 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-.
Mar 20: Spring Break
Mar 22: Spring Break
Mar 27: Transactions: Overview [slides]
- (required reading - no summary) Concurrency Control and Recovery; Mike Franklin, 1997 [pdf link]
  
  Notes: This is an overview article, and although no summary is required, the next 3-4 papers may be hard to follow without this (or some other equivalent) survey.
Mar 29: 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)
- (more details) A survey of B-tree locking techniques; Graefe, TODS 2010 [link]
April 3: Transactions: Concurrency (Cntd notes from above)
- (summary required) Berenson et al. A Critique of ANSI SQL isolation levels; SIGMOD 1995 [link]
April 5: Transactions: Recovery (Cntd notes from above)
- (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 10: Transactions: Replication (Cntd notes from above)
- (summary required) Dangers of replication and a solution; Gray et al.; SIGMOD 1996. [link]
- (no summary required) Eventual Consistency; Vogels; CACM 2009. [link]
- (optional, but may be helpful to read before the above) A short note by Mike Stonebraker on CAP and Eventual Consistency.
April 12: Transactions: Distributed Databases (Cntd notes from above)
- (summary required) Megastore: Providing Scalable, Highly Available Storage for Interactive Services. [link]
April 17: Data Warehousing [slides 1] [slides 2 - PPT]
- (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.
April 19: Data Warehousing (Cntd notes from above)
- (summary required) DynaMat: a dynamic view management system for data warehouses; Yannis Kotidis, Nick Roussopoulos. SIGMOD Conference 1999.
April 24: Auto Admin [spring 2011 slides]
- (summary required) Self-tuning database systems: a decade of progress; Chaudhuri, Narasayya; VLDB 2007 [link]
April 26: XML [spring 2011 slides]
- (summary required) Relational Databases for Querying XML Documents: Limitations and Opportunities; Jayavel Shanmugasundaram et al.; VLDB 1999
[[[ Reading List/Schedule Tentative Beyond This Point ]]]
May 1: Performance
- (optional) Ailamaki et al.; DBMSs on a modern processor: where does the time go?; VLDB 1999
- (summary required) Ailamaki et al.; Weaving relations for cache performance; VLDB 2001
May 3: Performance
- (summary required) FAST: fast architecture sensitive tree search on modern CPUs and GPUs; SIGMOD 2010
May 8-10: Project Presentations.
May 18, 10:30am-12:30pm: Scheduled Final Exam for the Class

Web Accessibility