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
    

• Feb 1, Feb 3: Background [show/hide]
  • Slides/Notes: [slides data models], [normalization overview slides (spring 2011)] [slides architecture]
  • Background readings:
    1. "What goes around comes around"; Mike Stonebraker and Joe Hellerstein; Redbook.
       
    2. "Architecture of a Database System"; Joe Hellerstein, Mike Stonebraker, James Hamilton; Foundations and Trends 2007. (original paper; A crop-merged Version of that PDF)
       
    3. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170 (1993) [link]
       
  • More 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
       

• Feb 8, Feb 10: Architectures [show/hide]
• Slides/Notes: [slides oltp],
  • Required readings:
    1. (Feb 8) Parallel database systems: the future of high performance database systems; DeWitt, Gray; CACM 1992
    2. (Feb 8) Stonebraker et al. C-store: A Column-oriented DBMS. SIGMOD, 2005.
    3. (Feb 10) Cristian Diaconu, Craig Freedman, Erik Ismert, Per-Ake Larson, Pravin Mittal, Ryan Stonecipher, Nitin Verma, Mike Zwilling. Hekaton: SQL Server's Memory-optimized OLTP Engine. SIGMOD, 2013.
    4. (Feb 10) Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, Michael Stonebraker. OLTP Through the Looking Glass, and What We Found There. SIGMOD, 2008.
• Feb 15, Feb 17: Query Optimization [show/hide]
  • Slides/Notes: [slides]
  • Background readings:
    1. Overview Chapter in the Redbook by Hellerstein
    2. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998: 34-43;
  • Required readings:
    1. (Feb 15) Access path selection in a relational database management system; Selinger et al.; SIGMOD 1979
    2. (Feb 15) Selectivity estimation without the attribute value independence assumption; Poosala and Ioannidis; VLDB 1997
    3. (Feb 17) Ron Avnur and Joseph M. Hellerstein. Eddies: Continuously Adaptive Query Processing. SIGMOD, 2000.
    4. (Feb 17) Volker Markl, Vijayshankar Raman, David Simmen, Guy Lohman, Hamid Pirahesh, Miso Cilimdzic. Robust Query Processing Through Progressive Optimization. SIGMOD, 2004.
• Feb 24, Feb 29: Large-scale Data Analysis Systems [show/hide]
  • Slides/Notes: [slides]
  • Background readings:
    1. Overview Chapter in Redbook by Bailis
       1. Required readings:
          1. (Feb 24) MapReduce: A Flexible Data Processing Tool; Jeffrey Dean and Sanjay Ghemawat; CACM 2010
             
          2. (Feb 24) MapReduce and Parallel DBMSs: Friends or Foes? Stonebraker et al.; CACM 2010
             
          3. (Feb 29) Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing; Zaharia et al.; NSDI 2012
          4. (Feb 29) Yuan Yu, Michael Isard, Dennis Fetterly, Mihai Budiu. DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language. OSDI, 2008.
• Mar 2, Mar 8: Data Streams/Dataflow Engines [show/hide]
  • Required readings:
    1. (Mar 2) Continuous queries over data streams; Babu, Widom; SIGMOD Record 2001[link to pdf]
       
    2. (Mar 2) The Design of the Borealis Stream Processing Engine; Abadi et al.; CIDR 2005
    3. (Mar 8) Discretized streams: fault-tolerant streaming computation at scale; SOSP 2013 [link]
    4. (Mar 8) Naiad: a timely dataflow system; SOSP 2013 [link]
• Mar 21, Mar 23: Machine Learning Systems [show/hide]
  • Required readings:
    1. (Mar 21) The MADlib analytics library: or MAD skills, the SQL; Hellerstein et al.; VLDB 2012. [pdf]
    2. (Mar 21) Towards a unified architecture for in-RDBMS analytics; Feng et al.; SIGMOD 2012 [link to pdf]
    3. (Mar 23) Distributed GraphLab: a framework for machine learning and data mining in the cloud; VLDB 2012 [link to pdf]
    4. (Mar 23) Scaling Distributed Machine Learning with the Parameter Server; OSDI 2014 [link]
• Mar 28: Graphs [show/hide]
  • Required readings:
    1. (Mar 28) GraphX: Graph Processing in a Distributed Dataflow Framework; OSDI 2014 [link]
    2. (Mar 28) SQLGraph: An Efficient Relational-Based Property Graph Store; SIGMOD 2015 [link]
• Mar 30: Project Presentations I
• April 4: XML, RDF [show/hide]
  • Required readings:
    1. (April 4) RDF-3X: a RISC-style Engine for RDF; VLDB 2008[link to pdf]
    2. (April 4) Relational Databases for Querying XML Documents: Limitations and Opportunities; Jayavel Shanmugasundaram et al.; VLDB 1999
• April 6, April 11: Interactive Analytics [show/hide]
  • Required readings:
    1. (April 6) Implementing data cubes efficiently; Harinarayanan et al.; SIGMOD 1996.
    2. (April 6) Dremel: Interactive Analysis of Web-Scale Datasets; VLDB 2010 [link]
    3. (April 11) BlinkDB; EuroSys 2013 [ACM DL Link]
    4. (April 11) Interactive data analysis: the Control project; IEEE Computer 1999
• April 13: Transactions (Basics)
• Slides/Notes: [slides]
  • Background readings:
    1. Concurrency Control and Recovery; Mike Franklin, 1997 [pdf link]
       
  • Required readings:
    1. (April 13) H. T. Kung, John T. Robinson. On Optimistic Methods for Concurrency Control. Proc. VLDB, 1979, 351.
       
    2. (April 13) Berenson et al. A Critique of ANSI SQL isolation levels; SIGMOD 1995 [link]
       
• April 18: Project Presentations
• April 20: No Class
• April 25, April 27, May 2: Transactions
  • Required readings:
    1. (April 25) Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981)
    2. (April 25) Shore-MT: a scalable storage manager for the multicore era; Johnson et al.; EDBT 2009
    3. (April 27) Dynamo: Amazon's Highly Available Key-Value Store; SOSP 2007 [link]
    4. (April 27) 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.
    5. (May 2) N. Malviya, et al., Rethinking Main Memory OLTP Recovery, in ICDE, 2014
    6. (May 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)
       
• May 4: Data Science Workflows; Provenance
  • Required readings:
    1. (May 9) DataHub: Collaborative Data Science and Dataset Version Management at Scale; CIDR 2015.
    2. (May 9) Kepler: an extensible system for design and execution of scientific workflows; SSDBM 2004.
• May 9: Data Integration; Information Extraction
  • Required readings:
    1. (May 9) Querying Heterogeneous Information Sources Using Source Descriptions; Levy et al.; VLDB 1996
    2. (May 9) WebTables: exploring the power of tables on the web; Cafarella et al.; VLDB 2008
• May 18, 10:30am-12:30pm: Scheduled Final Exam for the Class
  

Web Accessibility