CMSC724: Database Management Systems

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

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

Schedule and Readings

Jan 27: Introduction/Overview [show/hide]
- Slides/Notes: [slides]
- Comments: For a nice historical overview, see the first paper ("Evolution of ..") in this ACM Computing Surveys, Mach 1976
Jan 29, Feb 3: History/Data Modeling [show/hide]
- Slides/Notes: [slides], [modeling text notes] [Some notes on Codd's paper], [normalization overview slides (spring 2011)]
- Questions about readings (Due: Tuesday 2/3, 3pm)
- Required readings:
  1. "A Relational Model of Data for Large Shared Data Banks". E. F. Codd. Commun. ACM 13(6): 377-387 (1970). [pdf]
  2. "What goes around comes around"; Mike Stonebraker and Joe Hellerstein; Redbook (google the title for the PDF).
  3. "Querying semi-structured data". Serge Abiteboul. ICDT 1997. [pdf]
- Optional readings/Background:
  1. 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]
  2. The Relational vs Network Models Debate
  3. Is your database relational ? Ted Codd Wikiepdia article
- Comments: 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.
Feb 5: Architecture of a Database System [show/hide]
- Slides/Notes: [slides]
- Questions about readings (Due: Thursday 2/5, 3pm)
- Required readings:
  1. "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 10, Feb 12: Query Processing [show/hide]
- Slides/Notes: [slides]
- Questions about readings (Due: Tuesday 2/10, 3pm)
- Required readings:
  1. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170 (1993) [link]
  2. Daniel Abadi, Peter A. Boncz, Stavros Harizopoulos, Stratos Idreos, Samuel Madden. The Design and Implementation of Modern Column-Oriented Database Systems. Foundations and Trends in Databases 5(3): 197-280 (2013) (original paper; A crop-merged version of that PDF)
- Optional readings/Background:
  1. Column-stores vs. row-stores: how different are they really? Abadi et al.; SIGMOD 2008 [link to pdf]
Feb 17, Feb 19: Query Optimization, Data Streams [show/hide]
- Slides/Notes: Continued from above
- Questions about readings (Due: Tuesday 2/17, 3pm)
- Required readings:
  1. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43; [link to pdf]
  2. Continuous queries over data streams; Babu, Widom; SIGMOD Record 2001[link to pdf]
- Optional readings/Background:
  1. A very nice overview of DB2 Optimizer (by Guy Lohman)
  2. "The 8 Requirements of Real-Time Stream Processing"; M. Stonebraker, U. Cetintemel, and S. Zdonik. In SIGMOD Record, 2005. [pdf]
Feb 24, Feb 26: Parallel Databases, MapReduce, Key-value Stores [show/hide]
- Slides/Notes: [parallel/mr slides]
- Questions about readings (Due: Tuesday 2/24, 3pm)
- Required readings:
  1. MapReduce: A Flexible Data Processing Tool; Jeffrey Dean and Sanjay Ghemawat; CACM 2010
  2. MapReduce and Parallel DBMSs: Friends or Foes? Stonebraker et al.; CACM 2010
  3. (Spark) Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing; Zaharia et al.; NSDI 2012
- Optional readings/Background:
  1. Pig latin: a not-so-foreign language for data processing; SIGMOD 2008 [link]
Mar 3, Mar 5: Data Streams [show/hide]
- Questions about readings (Due: Tuesday 3/3, 3pm)
- Required readings:
  1. Discretized streams: fault-tolerant streaming computation at scale; SOSP 2013 [link]
  2. Naiad: a timely dataflow system; SOSP 2013 [link]
Mar 10, Mar 12: Data Mining [show/hide]
- Slides/Notes: [spring 2011 slides]
- Questions about readings (Due: Tuesday 3/10, 3pm)
- Required readings:
  1. Tian Zhang, Raghu Ramakrishnan, Miron Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases. Proc. SIGMOD Conference, 1996, 103-114.
  2. John C. Shafer, Rakesh Agrawal, Manish Mehta. SPRINT: A Scalable Parallel Classifier for Data Mining. Proc. VLDB, 1996, 544-555.
  3. Surajit Chaudhuri, Vivek R. Narasayya, Sunita Sarawagi. Efficient Evaluation of Queries with Mining Predicates. Proc. ICDE, 2002, 529-.
Mar 17, Mar 19: Spring Break
Mar 24, Mar 26: Transactions: Overview, Concurrency [show/hide]
- Slides/Notes: [transaction slides]
- Questions about readings (Due: Tuesday 3/24, 3pm)
- Required readings:
  1. Concurrency Control and Recovery; Mike Franklin, 1997 [pdf link]
  2. H. T. Kung, John T. Robinson. On Optimistic Methods for Concurrency Control. Proc. VLDB, 1979, 351.
  3. Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981)
- Optional readings/Background:
  1. A survey of B-tree locking techniques; Graefe, TODS 2010 [link]
March 31, April 2: Transaction: Concurrecy, Recovery [show/hide]
- Slides/Notes: Continued from above
- Questions about readings (Due: Tuesday 3/31, 3pm)
- Required readings:
  1. Berenson et al. A Critique of ANSI SQL isolation levels; SIGMOD 1995 [link]
  2. 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)
- Optional readings/Background:
  1. Mohan's overview papers.
April 7, April 9: Transactions: Replication, Distributed [show/hide]
- Slides/Notes: Continued from above
- Questions about readings (Due: Tuesday 4/7, 3pm)
- Required readings:
  1. 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.
  2. Dangers of replication and a solution; Gray et al.; SIGMOD 1996. [link]
  3. Quantifying Eventual Consistency with PBS; Bailis et al.; CACM 2014 [link]
  4. Dynamo: Amazon's Highly Available Key-Value Store; SOSP 2007 [link]
- Optional readings/Background:
  1. Eventual Consistency; Vogels; CACM 2009. [link]
  2. PNUTS: Yahoo!'s Hosted Data Serving Platform; Cooper et al.; VLDB 2008 [link]
  3. Consensus on Transaction Commit; Gray, Lamport; TODS 2006. [link]
  4. (optional, but may be helpful to read before the above) A short note by Mike Stonebraker on CAP and Eventual Consistency.
April 14, April 16: Access Methods, Approximate Query Processing [show/hide]
- Slides/Notes: [indexes], [auto-admin]
- Questions about readings (Due: Tuesday 4/14, 3pm)
- Required readings:
  1. The R*-tree: an efficient and robust access method for points and rectangles; SIGMOD 1990 [ACM DL Link]
  2. Online Aggregation; Hellerstein et al.; SIGMOD 1997 [ACM DL Link]
  3. BlinkDB; EuroSys 2013 [ACM DL Link]
- Optional readings/Background:
  1. Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer. Generalized Search Trees for Database Systems. Proc. VLDB, 1995, 562-573.
April 21, April 23: Data Cubes, Analytics [show/hide]
- Slides/Notes: [cube slides], TBP
- Questions about readings (Due: Tuesday 4/21, 3pm)
- Required readings:
  1. Implementing data cubes efficiently; Harinarayanan et al.; SIGMOD 1996.
  2. Dremel: Interactive Analysis of Web-Scale Datasets; VLDB 2010 [link]
  3. The MADlib analytics library: or MAD skills, the SQL; Hellerstein et al.; VLDB 2012. http://arxiv.org/pdf/1208.4165
April 28, April 30: XML, RDF, Graphs [show/hide]
- Questions about readings (Due: Tuesday 4/28, 3pm)
- Slides/Notes: [xml slides], [RDF slides]
- Required readings:
  1. Relational Databases for Querying XML Documents: Limitations and Opportunities; Jayavel Shanmugasundaram et al.; VLDB 1999
  2. SW-Store: a vertically partitioned DBMS for Semantic Web data management; Abadi et al.; VLDB 2008.
  3. Query languages for graph databases; Peter Wood; SIGMOD Record 2012 [ACM DL Link]
May 5, May 7: New Hardware [show/hide]
- Slides/Notes: [slides]
- Questions about readings (Due: Tuesday 5/7, 3pm)
- Required readings:
  1. Fast computation of database operations using graphics processors; SIGMOD 2004 [ACM DL Link]
  2. Breaking the memory wall in MonetDB; Boncz et al.; CACM 2008 [ACM DL Link]
  3. Data Processing on FPGAs; VLDB 2009[ACM DL Link]
May 12: Data Integration, Information Extraction [show/hide]
- Slides/Notes: [DI], [IE]
- Questions about readings (Due: Tuesday 5/12, 3pm)
- Required readings:
  1. Querying Heterogeneous Information Sources Using Source Descriptions; Levy et al.; VLDB 1996 [PDF]
  2. Information Extraction; Sarawagi; Foundations and Trends; (Only Chapters 1 and 2) [PDF]
May 18, 10:30am-12:30pm: Scheduled Final Exam for the Class

Web Accessibility