Database Management System

Course Description

This course covers database management system design principles and techniques. Possible topics include internal design of DBMS, indexing, query processing, distributed scientific databases, computational geometry, geographic information systems, and data intensive computing. We will select and read some of milestone papers in DBMS history as well as the state-of-the-art DB papers.

Recommend but NOT required Textbook

1. Database System Concepts, by Abraham Silberschatz, Henry F. Korth, S. Sudarshan, McGraw-Hill, 6th Edition
2. Readings in Database Systems, by Hellerstein and Stonebraker, MIT Press, 4th Edition Redbook Web Site

Reading List

Here is the list of papers in excel sheet. Write your name beside the paper you want to present. All students are to select two papers.

Upload your quiz material and presentation file to this link

1. David A. Patterson, Garth Gibson and Randy H. Katz "A case for redundant arrays of inexpensive disks (RAID)", SIGMOD 88
2. Michael Stonebraker. Operating System Support for Database Management.. Commun. ACM, 24(7), 1981, 412-418.
3. A. Guttman, R-Trees: A Dynamic Index Structure For Spatial Searching, SIGMOD 84
4. N. Beckmann, H.P. Kriegel, R. Schneider, B. Seeger, R*-tree: An Efficient and Robust Access Method for Points and Rectangles, SIGMOD 90
5. C. Mohan et al. "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-ahead Logging" ACM Transactions on Database Systems, Vol 17, No. 1, March 1992
6. S. Berchtold, D. A. Keim, The X-Tree: An Index Structure for High-Dimensional Data, VLDB 96
7. K. Chakrabarti, S. Mehrotra, The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces, ICDE 99
8. Indyk, Piotr.; Motwani, Rajeev. , "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.". Symposium on Theory of Computing, 1998
9. N. Roussopoulos, S. Kelley, F. Vincent: Nearest Neighbor Queries. SIGMOD 95
10. S. Venkataraman, N. Tolia, P. Ranganathan, R. H. Campbell, "Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory", USENIX FAST, 2011
11. J. Dean and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, in OSDI 2004
12. A. Pavlo, E. Paulson, A. Rasin, D. J. Abadi, D. J. DeWitt, S. Madden, and M. Stonebraker, A Comparison of Approaches to Large Scale Data Analysis, in SIGMOD '09
13. M. Stonebraker, D. Abadi, D. J. DeWitt, S. Madden, E. Paulson, A. Pavlo, and A. Rasin, MapReduce and parallel DBMSs: friends or foes?, in Communications of the ACM, January 2010
14. M. Stonebraker, SQL databases v. NoSQL databases, in Communications. ACM 53(4): 10-11 (2010)
15. F. Chang et al., Bigtable: A distributed storage system for structured data, OSDI 2006
16. G. DeCandia et al., Dynamo: Amazon's highly available key-value store, SOSP 2007
17. B. F. Cooper et al., PNUTS: Yahoo!'s hosted data serving platform, VLDB 2008
18. A.Thusoo, et al., Hive: A Warehousing Solution Over a MapReduce Framework, VLDB 2009
19. A.Lakshman, P. Malik., Cassandra: A Decentralized Structured Storage System, ACM SIGOPS Operating Systems Review, Volume 44 Issue 2, April 2010
20. J. Baker, et al., MegaStore: Providing Scalable Highly-Available Storage for Interactive Services, CIDR 2011
21. Wongun Lee, Keonwoo Lee, Hankeun Son, Wook-Hee Kim , Beomseok Nam, Youjip Won "WALDIO: Eliminating the Filesystem Journaling in Resolving the Journaling of Journal Anomaly" 2015 USENIX Annual Technical Conference (USENIX ATC '15), Santa Clara, CA, Jun. 2015
22. Wook-Hee Kim, Jinwoong Kim, Woongki Baek, Beomseok Nam, and Youjip Won "NVWAL: Exploiting NVRAM in Write-Ahead-Logging", 21st International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '16), (22% a/r), Atlanta, GA, Apr. 2016
23. Se Kwon Lee, K. Hyun Lim, Hyunsub Song, Beomseok Nam, and Sam H. Noh "WORT: Write Optimal Radix Tree for Persistent Memory Storage Systems", the 15th USENIX Conference on File and Storage Technologies (FAST '17), Santa Clara, CA. Feb. 2017
24. Deukyeon Hwang , Wook-Hee Kim , Youjip Won, and Beomseok Nam "Endurable Transient Inconsistency in Byte-Addressable Persistent B+-Tree", the 16th USENIX Conference on File and Storage Technologies (FAST '18), Oakland, CA. Feb. 2018

Midterm Exam Topics

Here are some of the topics we covered in class. It is important to know their key ideas and how they operate. Their meaning and purpose in the system, their role in the system, etc. Do not learn them skeptically.

• B-Tree and B+Tree algorithms and difference between the two trees
• R-Tree algorithm
• NoSQL vs SQL and Cassandra
• Journaling in Database and its effect on system
• CDDS
• WALDIO
• MapReduce
• Bloom Filter
• BigTable