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
-
Rule-Based Query Optimization using the
Volcano Framework.
Chapter 2 from
Multiquery Optimization and Applications,
Prasan Roy, PhD thesis, 2000
(Jan 5, 2007)
- 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
-
Materialized View Selection and Maintenance Using Multi-Query
Optimization,
Hoshi Mistry, Prasan Roy, S. Sudarshan and Krithi Ramamritham
5B
SIGMOD 2001
PPT
-
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
-
Eddies: Continuously Adaptive Query Processing,
Avnur and Hellerstein, SIGMOD 2000.
(Eddies ppt by Amol Deshpande)
-
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)
-
Content-Based Routing: Different Plans for Different Data
Pedro Bizarro, Shivnath Babu, David DeWitt, Jennifer Widom
VLDB 2005
PPT PDF
(Tue 6 Feb)
-
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)
- 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
-
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
-
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
- 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.)
- Holistic Twig Joins: Optimal XML
Pattern Matching
Nicolas Bruno, Nick Koudas and D. Srivastava, SIGMOD 2002.
ppt, Fri Mar 9, 2007
Misc
-
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)
-
A Disk-Based Join With Probabilistic Guarantees
Christopher Jermaine, Alin Dobra, Subramanian Arumugam, Shantanu Joshi, Abhijit Pol
Talk by Christopher Jermaine
Fri 16 March.
-
Query Optimization of Web Services
Utkarsh Srivastava, Kamesh Munagala, Jennifer Widom and Rajeev Motwani,
SIGMOD 06
Tue 20 March: Ajay Kumar Sarda: ppt
-
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
-
ℓ-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
-
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)
- 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)
-
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
- 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
-
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
-
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)