CS 632: Advanced DBMS
(better titled perhaps as Advances in Data Based Systems)

S. Sudarshan

Spring 2007  

Previous offerings: 2006, 2004, 2003, 2002, 2001, 2000, 1999.

This years format will include paper presentations from all students taking the course, in addition to exam(s) and a project. Reading material will consist primarily of research papers.
Textbook (for background material only): Database System Concepts, 5th Ed. Avi Silberschatz, Hank Korth, and S. Sudarshan. McGraw Hill, 2005. ( Slides for all book chapters )

    Multi Query Optimization

  1. Rule-Based Query Optimization using the Volcano Framework.
    Chapter 2 from Multiquery Optimization and Applications, Prasan Roy, PhD thesis, 2000
    (Jan 5, 2007)
  2. 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. ppt
    (Jan 5, 2007)

    Materialized Views

  3. Materialized View Selection and Maintenance Using Multi-Query Optimization,
    Hoshi Mistry, Prasan Roy, S. Sudarshan and Krithi Ramamritham 5B
    SIGMOD 2001
    PPT
  4. An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server,
    Surajit Chaudhuri, Vivek R. Narasayya, VLDB 1997: 146-155
    Slides PPT
    (This talk will also cover the following paper, which is NOT on the reading list for the course:
    Automated Selection of Materialized Views and Indexes in SQL Databases,
    Sanjay Agrawal, Surajit Chaudhuri, Vivek R. Narasayya, VLDB 2000: 496-505)

    Adaptive Query Processing

  5. Eddies: Continuously Adaptive Query Processing,
    Avnur and Hellerstein, SIGMOD 2000.
    (Eddies ppt by Amol Deshpande)
  6. Goals and Benchmark for Autonomic Configuration Recommenders
    Mariano P. Consens, Denilson Barbosa, Adrian M. Teisanu, Laurent Mignet, SIGMOD 2005: 239-250
    (Talk by Laurent Mignet, Fri 2 Feb)
  7. Content-Based Routing: Different Plans for Different Data
    Pedro Bizarro, Shivnath Babu, David DeWitt, Jennifer Widom VLDB 2005
    PPT PDF (Tue 6 Feb)
  8. Robust Query Processing through Progressive Optimization,
    Volker Markl, Vijayshankar Raman, David E. Simmen, Guy M. Lohman, Hamid Pirahesh, SIGMOD 2004: 659-670
    PPT PDF (Fri 9 Feb)
  9. Parametric approach to spatio-temporal-belief data,
    Talk by Sashi Gadia, Feb 13 (paper and slides not available, contents dropped from course)

    Feb 16: Holiday

    Midsemester Exam

    No classes on Feb 20 and 23

    Peer to Peer Systems

  10. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications,
    I. Stoica, R. Morris, D. Karger, M. Frans Kaashoek, H. Balakrishnan,
    In Proc. ACM SIGCOMM 2001. Expanded version appears in IEEE/ACM Trans. Networking, 11(1), February 2003.

    ( Extra Paper (not assigned reading):
    A Scalable Content-Addressable Network,
    S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Shenker, In Proc. ACM SIGCOMM 2001)
    Talk (in pdf) Tue Feb 27, 2007

    Query Processing

  11. Reducing Order Enforcement Cost in Complex Query Plans
    Ravindra Guravannavar and S. Sudarshan, ICDE 2007 (to appear)
    Talk by Ravi G. (ppt) Fri March 2, 2007

    XML Query Processing

  12. Structural Joins: A Primitive for Efficient XML Query Pattern Matching,
    D. Srivastava, S. Al-Khalifa, H.V. Jagadish, N. Koudas, J.M. Patel, Y.Wu, ICDE 2002.
    (Extra paper, not required reading: ORDPATHs: Insert-Friendly XML Node Labels,
    Patrick E. O'Neil, Elizabeth J. O'Neil, Shankar Pal, Istvan Cseri, Gideon Schaller, Nigel Westbury, SIGMOD 2004: 903-908.)
  13. Holistic Twig Joins: Optimal XML Pattern Matching Nicolas Bruno, Nick Koudas and D. Srivastava, SIGMOD 2002.
    ppt, Fri Mar 9, 2007

    Misc

  14. Redundancy and Information Leakage in Fine-Grained Access Control,
    Govind Kabra, Ravishankar Ramamurthy and S. Sudarshan
    Talk: ppt, Tue 13 March (also covered: Overview of database security and an Overview of Finegrained Authorization)
  15. A Disk-Based Join With Probabilistic Guarantees
    Christopher Jermaine, Alin Dobra, Subramanian Arumugam, Shantanu Joshi, Abhijit Pol
    Talk by Christopher Jermaine Fri 16 March.
  16. Query Optimization of Web Services
    Utkarsh Srivastava, Kamesh Munagala, Jennifer Widom and Rajeev Motwani, SIGMOD 06
    Tue 20 March: Ajay Kumar Sarda: ppt
  17. Buffering Database Operations for Enhanced Instruction Cache Performance
    Jingren Zhou and Kenneth A. Ross, SIGMOD 2004
    (Extra papers, not required reading: Making B+-trees Cache Conscious in Main Memory, Jun Rao and Kenneth A. Ross, SIGMOD 2000,
    Weaving Relations for Cache Performance, Anastassia Ailamaki, David J. DeWitt, Mark D. Hill and Marios Skounakis, VLDB 2001. )
    (Talk (pdf) in 2006 by Kamlesh/Unmesh )
    (Talk:pdf, Fri 23 March: Namrata Jain)

    Privacy

  18. ℓ-Diversity: Privacy Beyond k-Anonymity,
    Ashwin Machanavajjhala Johannes Gehrke Daniel Kifer Muthuramakrishnan Venkitasubramaniam
    Talk: ppt, Sat 24 March, B Aditya Prakash)

    (Extra papers: Mondrian Multidimensional K-Anonymity K. LeFevre, D. DeWitt, and R. Ramakrishnan. ICDE 2006
    Incognito: Efficient Full-Domain K-Anonymity., K. LeFevre, D. DeWitt, and R. Ramakrishnan, SIGMOD 2005.
    Protecting Privacy when Disclosing Information: k-Anonymity and its Enforcement through Generalization and Suppression,
    Pierangela Samarati and Latanya Sweeney, Procs. of the IEEE Symposium on Research in Security and Privacy, 1998.)
    Talk (pdf)

    Query Optimization

  19. Towards a robust query optimizer, a principled and practical approach,
    Brian Babcock and Surajit Chaudhuri, SIGMOD 2005.
    (Extra Paper: Least Expected Cost Query Optimization: What Can We Expect
    Francis Chu, Joseph Halpern and Johannes Gehrke, PODS 2002)
    (Talk: pdf, Tue 27 March: Rohan Noguiera)
  20. Querying the Internet with PIER
    Ryan Huebsch, Joseph M. Hellerstein, Nick Lanham, Boon Thau Loo, Scott Shenker, and Ion Stoica, VLDB 03
    (Talk:ppt, Fri 30 March: Neha Singh)
  21. Relaxing Join and Selection Queries
    Nick Koudas, Chen Li, Anthony K. H. Tung, and Rares Vernica, VLDB 06
    (Tue 3 April: ppt Pradnya)

    IR and DB

  22. Keyword Searching and Browsing in Databases using BANKS
    Gaurav Bhalotia, Charuta Nakhe, Arvind Hulgeri, Soumen Chakrabarti and S. Sudarshan, ICDE 2002
    (Fri 6 April: pdf Ramdas Rao) (Extra papers: Bidirectional Search (VLDB 2005) and Sphere Search (VLDB 2005)

    OLAP

  23. OLAP Over Uncertain and Imprecise Data Douglas Burdick, Prasad Deshpande, T. S. Jayram, Raghu Ramakrishnan and Shivakumar Vaithyanathan, VLDB 2005
    (Tue 10 April: Talk: Olap basics(pdf) and OLAP on uncertain/imprecise data (pdf)
    presented by Chaitanya, talk prepared by Manuj and Kamalakar in 2006)
    (Related material if you are interested, but not part of CS632: Probablistic Databases talk by Amol Deshpande on 12 Jan 2006)

    Data Dissemination

  24. An Efficient and Resilient Approach to Filtering and Disseminating Streaming Data,
    Shetal Shah, Shyamshankar Dharmarajan and Krithi Ramamritham, VLDB 2003
    (Fri 13 April, Dynamic Data Dissemination Talk ppt by Krithi Ramamritham)
    Talk (in ppt) by Shetal Shah (from 2006)