CS 632: Advanced DBMS

S. Sudarshan

Spring 2018  

All students must sign up for CS 632 on Piazza; details are on the CS 632 Moodle page.

Previous offerings: 2017, 2016, 2015, 2014, 2013, 2011, 2010, 2009, 2007, 2006, 2004, 2003, 2002, 2001, 2000, 1999.

About The Course

Reading material will consist primarily of research papers. All students will have to present a research paper of their choice, either from the list below or other papers subject to instructors approval. There will also be two exams (midsem/endsem), assignments, and a course project.

Grading scheme: Anyone who does an exceptional course project that has the potential to be a publishable paper is eligible for a straight AA grade. Otherwise the grading breakup would be midsem 25, endsem 40, project 20 and assignments plus seminar presentation 15 (the breakup of these will depend on whether we have individual or joint seminars, which depends on the final enrollment).
Midsem paper and End sem paper from 2016

Assignments To be decided.

Project The project is mandatorily an implementation oriented project. You may still need to do some literature survey to figure out your project though. Projects should be done in groups of 2. A basic project will take any of the papers we study in the course, or other related papers, and implement the algorithms in the paper, and do a very basic performance study. However, I would expect most projects to improve upon existing techniques. A more advanced project would take a problem specification for which no solution is publicly available, figure out how to solve it, and implement the solution.

Textbook (for background material only): Database System Concepts, 6th Ed.
Avi Silberschatz, Hank Korth, and S. Sudarshan. McGraw Hill, 2010.
(book home page)

NOTE: The list of topics below is subject to change during the semester, especially those later in the semester Talk (odp) (by Pranav Gupta)
Topic/Paper Schedule
Massively Parallel Data Management Systems (a.k.a. Big Data Systems)
1. Parallel and Distributed Databases
  1. Database System Architectures
  2. Parallel and Distributed Storage Systems
  3. Parallel and Distributed Query Processing, and
  4. Parallel and Distributed Transaction Processing
I will supply reading material in hard copy, through one of the xerox shops on campus.
Updated slides for this part will be available via moodle.
2a Guest Lecture:
Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees. Anshuman Dutt, Vivek R. Narasayya, Surajit Chaudhuri,
SIGMOD Conference 2017: 1539-1554
Talk by Anshuman Dutt
Video for internal IIT use only
2. Bigtable: A Distributed Storage System for Structured Data
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber, OSDI 06)
Video of talk by Jeff Dean: Local mp4 copy OR on video.google.com

Related papers, not required reading:
Talk (ppt)
3. In Search of an Understandable Consensus Algorithm
Diego Ongaro and John Ousterhout
Proc ATC14, USENIX Annual Technical Conference (2014), USENIX
(This is the Raft paper)
(Extended Version of paper)
Talk (pptx)
Talk (pdf) by Ousterhout
4. Spanner: Google's Globally-Distributed Database
James C. Corbett et al., OSDI 2012
Talk (pptx)
5. PNUTS: Yahoo!'s Hosted Data Serving Platform,
Brian F. Cooper, Raghu Ramakrishnan, Utkarsh Srivastava, Adam Silberstein, Philip Bohannon, Hans-Arno Jacobsen, Nick Puz, Daniel Weaver and Ramana Yerneni.
VLDB (industry track) 2008.

Related papers, not required reading:
  • database implementation on S3 (Brantner et al SIGMOD 2008)
VLDB Talk by Brian Cooper (ppt)
6. Asynchronous view maintenance for VLSD databases
Parag Agrawal, Adam Silberstein, Brian F. Cooper, Utkarsh Srivastava, Raghu Ramakrishnan, SIGMOD 2009

Old talk (odp) and (pdf)
Related papers, not required reading:
  • The Megastore paper (see above), to understand how it does asynchronous maintenance of indices.
Talk (ppt)
7. Pregel: a system for large-scale graph processing
Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, Grzegorz Czajkowski, SIGMOD 2010.
Talk (pptx) by (Gaurav Malpani and Mayank Singhal)
Related papers, not required reading:
Talk (pptx)
Query Optimization
8. Rule-Based Query Optimization using the Volcano Framework.
Chapter 2 from Multiquery Optimization and Applications,
Prasan Roy, PhD thesis, IIT Bombay, 2000.

Related papers, not required reading:
Talk (ppt)
9. (Mar 15/19) Incorporating Partitioning and Parallel Plans into the SCOPE Optimizer
Jingren Zhou, Per-Ake (Paul) Larson, and Ronnie Chaiken,
in Proc. of the Int'l Conf. on Data Engineering (ICDE), 2010.
Related papers, not required reading:
Talk (pptx)
Main-Memory Databases
10. (Mar 19/20) Hekaton: SQL server's memory-optimized OLTP engine.
Cristian Diaconu, Craig Freedman, Erik Ismert, Per-Åke Larson, Pravin Mittal, Ryan Stonecipher, Nitin Verma, Mike Zwilling
SIGMOD Conference 2013: 1243-1254
Talk has been put up on Moodle site
11. (Mar 22) Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age
Viktor Leis, Peter Boncz, Alfons Kemper, Thomas Neumann, SIGMOD 2014
Adaptive Query processing
12. (Mar 26) Robust Query Processing through Progressive Optimization,
Volker Markl, Vijayshankar Raman, David E. Simmen, Guy M. Lohman, Hamid Pirahesh, SIGMOD 2004: 659-670
Talk (ppt) from 2016
Talk (ppt) (to be presented by Adarsh Rathore)
13. (Apr 27/2) Plan bouquets: query processing without selectivity estimation.
Anshuman Dutt, Jayant R. Haritsa, SIGMOD Conference 2014: 1039-1050
Talk (ppt) from authors
Talk (ppt)
RDF Processing
14. (Apr 2/5) RDF-3X: a RISC-style Engine for RDF
Thomas Neumann, Gerhard Weikum, VLDB 2008
Talk in 2013 (pptx) Talk in 2014 (odp) Talk in 2015 (odp) Talk (pptx) by Indradyumna Roy, 2016
Talk (odp) (by Megha Agarwal)
IR and DB
15. (Apr 5/9) Keyword Searching and Browsing in Databases using BANKS
Gaurav Bhalotia, Charuta Nakhe, Arvind Hulgeri, Soumen Chakrabarti and S. Sudarshan, ICDE 2002

Related papers, not required reading: Talk (odp) by Pooja Agrawal, 2016
Overview talk (ppt),
Talk (pptx) (by Aarti Sharma)
16. (Apr 9/10) Human-powered sorts and joins
Adam Marcus, Eugene Wu, David Karger, Samuel Madden, and Robert Miller.
Proc. VLDB Endow. 5, 1 (September 2011), 13-24.

Related papers, not required reading:
Talk (by Ashwini Pale)
Test Data Generation
17. (Apr 12) Generating Test Data for Killing SQL Mutants: A Constraint-based Approach,
Shetal Shah, S. Sudarshan, Suhas Kajbaje, Sandeep Patidar, Bhanu Pratap Gupta, Devang Vira, ICDE 2011
Talk (ppt) by Shetal Shah in 2013
Related papers, not required reading: Talk (pdf) from 2014
Talk (pdf) from 2016 by Saurabh Sarda Talk (odp) from 2017 by Udbhas Hazra
Talk presented by Sai Prasad
Streaming Data and Reactive Applications
18. (Apr 16) MillWheel: Fault-Tolerant Stream Processing at Internet Scale
Tyler Akidau, Alex Balikov, Kaya Bekiroglu, Slava Chernyak, Josh Haberman, Reuven Lax, Sam McVeety, Daniel Mills, Paul Nordstrom, Sam Whittle
VLDB 2013
Talk presented in 2014 by Mohit Sirohi Talk (pptx) by Mandar Pawar
Related papers
Talk (pptx) (by K. Ravi Shankar)
19. (Apr 17 or 18) Program Transformations for Asynchronous and Batched Query Submission,
Karthik Ramachandra, Mahendra Chavan, Ravindra Guravannavar, and S. Sudarshan,
IEEE Trans. on Knowledge and Data Engineering (TKDE), pp. 531-544, Vol. 27, No. 2, Feb 2015
Related papers, not required reading:
Talk 1: Overview,
Talk 2: To be presented by Ishwari Patil in odp
20. (Apr 19) Discussion on future of data management.
This is probably the end of the 2018 Spring session
xx. (Apr xx) Monitoring Streams - A New Class of Data Management Applications,
Donald Carney, Ugur Cetintemel, Mitch Cherniack, Christian Convey, Sangdon Lee, Greg Seidman, Michael Stonebraker, Nesime Tatbul, Stanley B. Zdonik
VLDB 2002: 215-226
Talk in 2011 (pptx) by Joydip Datta and Debarghya Majumdar
, and Talk in 2013 (pptx) by Ajay Gupta,Vinit Deodhar Talk from 2015 (pptx) by Kuldeep Sharma

Related papers, not required reading
Talk (pptx) To be presented by Karnam Ravi Shankar
Also an overview talk on data streams: PODS 2002 talk by Motwani
Declarative Data Processing (outside of databases)
xx. (Apr 3/4) Declarative Networking: language, execution and optimization
Boon Thau Loo, Tyson Condie, Minos Garofalakis, David E. Gay, Joseph M. Hellerstein, Petros Maniatis, Raghu Ramakrishnan, Timothy Roscoe, and Ion Stoica
(A modified version titled "Declarative Networking" appeared in CACM 52(11), Nov 2009 )

Talk (pptx) by Harsh Vardhan and Sandeep Joshi
Talk 2014 (pdf) (Akshay Bapat)
Talk (Kuldeep Punjabi)
Talk (Upendra Jeliya)
Query Optimization: Beyond The Box
16. Diamond: Automating Data Management and Storage for Wide-area, Reactive Applications
Irene Zhang, Niel Lebeck, Pedro Fonseca, Brandon Holt, Raymond Cheng, Ariadna Norberg, Arvind Krishnamurthy, Henry M. Levy
OSDI 2015
Talk at OSDI
If Time Permits ....
xxx. Efficient and Extensible Algorithms for Multi-Query Optimization,
Prasan Roy, S. Seshadri, S. Sudarshan, and Siddhesh Bhobhe,
In ACM SIGMOD Conf. on the Management of Data., 2000.
Talk (ppt)