Schedule and Readings

• Jan 24: 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, Jan 31: 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 1/29, 10am)
  • 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, Feb 7: Architecture of a Database System [show/hide]
  • Slides/Notes: [slides]
  • Questions about readings (Due: Tuesday 2/5, 10am)
  • 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 12, Feb 14: Query Processing [show/hide]
  • Slides/Notes: [slides]
  • Questions about readings (Due: Tuesday 2/12, 10am)
  • Required readings:
    1. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170 (1993) [link]
       
    2. Column-stores vs. row-stores: how different are they really? Abadi et al.; SIGMOD 2008 [link to pdf]
       

• Feb 19, Feb 21: Query Optimization, Data Streams [show/hide]
  • Slides/Notes: Continued from above
  • Questions about readings (Due: Tuesday 2/19, 10am)
  • 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 26, Feb 28: Parallel Databases, MapReduce, Key-value Stores [show/hide]
  • Slides/Notes: [parallel/mr slides]
  • Questions about readings (Due: Tuesday 2/26, 10am)
  • 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. PNUTS: Yahoo!'s Hosted Data Serving Platform; Cooper et al.; VLDB 2008 [link]
       
  • Optional readings/Background:
    1. Pig latin: a not-so-foreign language for data processing; SIGMOD 2008 [link]
       

• Mar 5, Mar 7: Access Methods, Auto-admin [show/hide]
  • Slides/Notes: [indexes], [auto-admin]
  • Questions about readings (Due: Tuesday 3/5, 10am)
  • Required readings:
    1. Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer. Generalized Search Trees for Database Systems. Proc. VLDB, 1995, 562-573.
       
    2. Self-tuning database systems: a decade of progress; Chaudhuri, Narasayya; VLDB 2007 [link]

• Mar 12, Mar 14: Data Mining [show/hide]
  • Slides/Notes: [spring 2011 slides]
  • Questions about readings (Due: Tuesday 3/12, 10am)
  • 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 19: Spring Break
  
• Mar 21: Spring Break
  
• Mar 26, Mar 28: Transactions: Overview, Concurrency [show/hide]
  • Slides/Notes: [transaction slides]
  • Questions about readings (Due: Tuesday 3/26, 10am)
  • 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]

• April 2, April 4: Transaction: Concurrecy, Recovery [show/hide]
  • Slides/Notes: Continued from above
  • Questions about readings (Due: Tuesday 4/2, 10am)
  • 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 9, April 11: Transactions: Replication, Distributed [show/hide]
  • Slides/Notes: Continued from above
  • Questions about readings (Due: Tuesday 4/9, 10am)
  • 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. Eventual Consistency; Vogels; CACM 2009. [link]
  • Optional readings/Background:
    1. Consensus on Transaction Commit; Gray, Lamport; TODS 2006. [link]
    2. (optional, but may be helpful to read before the above) A short note by Mike Stonebraker on CAP and Eventual Consistency.

• April 16, April 18: Data Integration, Information Extraction [show/hide]
  • Slides/Notes: [DI], [IE]
  • Questions about readings (Due: Tuesday 4/16, 10am)
  • 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]

• April 23, April 25: Data Cubes, Analytics [show/hide]
  • Slides/Notes: [cube slides]
  • Questions about readings (Due: Tuesday 4/23, 10am)
  • Required readings:
    1. Implementing data cubes efficiently; Harinarayanan et al.; SIGMOD 1996.
    2. The MADlib analytics library: or MAD skills, the SQL; Hellerstein et al.; VLDB 2012. http://arxiv.org/pdf/1208.4165

• April 30, May 2: XML, RDF [show/hide]
  • Slides/Notes: [xml slides], [RDF slides]
  • Questions about readings (Due: Tuesday 4/30, 10am)
  • 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.

• May 7, May 9: New Hardware [show/hide]
  • Slides/Notes: [slides]
  • Questions about readings (Due: Tuesday 5/7, 10am)
  • Required readings:
    1. Breaking the memory wall in MonetDB; Boncz et al.; CACM 2008 [ACM DL Link]
    2. GPUTeraSort: high performance graphics co-processor sorting for large database management; Govindraju et al.; SIGMOD 2006; [ACM DL link]

  
  
  [[[ Reading List/Schedule Tentative Beyond This Point ]]]
  
• May 18, 10:30am-12:30pm: Scheduled Final Exam for the Class
  

Web Accessibility