wiki:cs222p-2020-winter

CS222P Winter 2020: Principles of Data Management

Schedule & Location

Lecture
Time: Tu/Th 3:30 pm – 4:50 pm (Check the UCI Calendar for holiday information)
Location: MSTB 120

Lab
Time: Fri 4:00 pm – 4:50 pm
Location: MSTB 118

Course Personnel

Name Office Hours Place Email
Instructor: Chen Li Th 2:15 pm - 3:15 pm DBH 2092 chenli AT ics.uci.edu
Assistant: Sadeem Alsudais Mon 1:30 pm - 2:30 pm ICS2 217 salsudai AT uci.edu
Assistant: Yicong Huang Fri 2:00 pm - 3:00 pm ICS2 216 yicongh1 AT uci.edu

Online Discussion

We are using Piazza for course discussion.

  • Please use Piazza properly. It's a place for students to exchange ideas. Don't post "easy" or "random" questions without much thinking.
  • To encourage students to actively participate in Piazza discussions and provide high-quality answers, we will select two students with the best Piazza performance. The top 2 students will get 2% extra credits in the overall scores.

Grade Book

Your grades will be returned through GradeScope (for regrades) and finally imported into Canvas.

Syllabus

ID Date Topic Readings Notes
1 01/07/2020, Tu DBMS Architecture Ch. 1; Chamberlin et al 1981 01
2 01/09/2020, Th Record/Page Formats Ch. 9.1, 9.2, 9.6, 9.7 02
3 01/14/2020, Tu Project 1 (Part 2), PAX, Column/Row stores, OLTP/OLAP, Heap Files 03
4 01/16/2020, Th Buffer Manager, Advice on projects Ditto
5 01/21/2020, Tu Project 2, Catalogs, Schema versioning, File Organizations Ch. 9 (remaining chapters), 12.1, 8.4 04
6 01/23/2020, Th Index Overview and ISAM Tree Index Ch. 8.4, Ch. 10 05
7 01/28/2020, Tu B+ tree Graefe 2011 (Sec. 1-3) 06
8 01/30/2020, Th Hashing, Comparisons of Indexes Ch. 11, Litwin 1980, Ch. 8.4 07
9 02/04/2020, Tu Indexing Performance Ch. 8.4 - 8.6 08
10 02/06/2020, Th Composite Indexes, Index-Only Plans Ditto Ditto
11 02/11/2020, Tu Project 3, External Sorting Ch. 13 09
12 02/13/2020, Th Selection, Projection, Duplicate elimination Ch. 14.1 - 14.3 10
13 02/18/2020, Tu Join: Blocked-based NLJ, Merge-based Ch. 14.4 11
14 02/20/2020, Th Join: Index-based, Hash-based (Grace, Simple, Hybrid) Ditto Ditto
15 02/25/2020, Tu Multi-attribute join, Theta join, Aggregation Ch. 14.5, 14.6, Ch. 15.2 12
16 02/27/2020, Th Project 4, Operator interface, Set operations Ditto Ditto
17 03/03/2020, Tu Cost estimation Ditto Ditto
18 03/05/2020, Th System-R Optimizer Ch. 15.3 - 15.6, Selinger et al 1979 13
19 03/10/2020, Tu System-R Optimizer, Cost estimation, Volcano Optimizer 14
20 03/12/2020, Th Parser, Other Indexes, Textbook Cover Page, Open Topics In-class and Zoom Ditto

Projects

The project is structured as a four-part, team-based (teams of one or two students), software development exercise:

Project Due Date Topic Proportions (50%) Private Tests
Project 1 Mon, week 3, Jan. 20th Record-Based File Manager (RBF) 9% P1 private tests
Project 2 Sat, week 5, Feb. 8th Relation Manager (RM) 14% P2 private tests
Project 3 Th, week 8, Feb. 27th Index Manager (IX) 14% P3 private tests
Project 4 Fri, week 10, Mar. 13th Query Engine (QE) 13% P4 private tests

Lab Section

Date Assistant Topic Notes
01/10/20, Fri Sadeem Alsudais Project Environment Setup Lab01
01/17/20, Fri Sadeem Alsudais Page Format and Record Manager Lab02
01/24/20, Fri Sadeem Alsudais Buffer Manager and PAX Lab03
01/31/20, Fri Sadeem Alsudais Disk I/O and B+ tree Lab04
02/07/20, Fri Sadeem Alsudais Hash Index Lab05
02/14/20, Fri Yicong Huang External Sorting Lab06
02/21/20, Fri Yicong Huang Projection, Blocked-based NLJ, Index-based Join Lab07
02/28/20, Fri Yicong Huang Theta Join, Hash-based Join (Simple, Grace, Hybrid) Lab08
03/13/20, Fri Yicong Huang Cost Estimation, Final Prep available on Canvas

Course Information

Course Description

This course provides an implementor's view of database management systems. It covers fundamental principles and implementation techniques, issues, and trade-offs related to database management systems. Topics covered include storage management, buffer management, record-oriented file systems, access methods, query processing, and query optimization. This course is a must for those students wishing to explore database management as an area of research and/or who plan on taking CS223 or CS224. A significant portion of database systems research as well as industrial database and information system development deals with adapting the basic database techniques covered in this course to new advances in hardware and software technologies or to the requirements of different applications and data types.

Prerequisites: CS 122A "Introduction to Data Management" and (ICS53 - "Principles in System Design" or CS143A - "Principles of Operating Systems"). Please don't attempt this class without the required background! Doing so has not proven to be a great idea for students historically. :-)

Using Github

You are required to use Github to manage your source code. Here are the instructions about how to use github to manage your projects and do submissions. For a team of 2 students, each member is expected to do the best effort to make equal contributions. We reserve the rights to deduct points for *both* students if we see unbalanced contributions.

Grading Breakdown

Final Exam: 50%
Programming Projects: 50%

This mixture of grading criteria for CS222P is intended to give equal "excelling opportunities" to both thinkers and do-ers. It's also intended to avoid overly weighting either team-based performance or individual performance. This is a hands-on project class, so expect to put a significant effort into your projects. The exam will be comprehensive with respect to the course material and will also ping you individually with respect to project knowledge, so be sure that you and your project partner make design decisions together. The final exam will be closed-book, but you may bring an 8.5"x11" two-sided cheat sheet to the exam if you like.

For all the graded projects and exam, if you disagree with the grading, you can discuss with us within two weeks after they are returned. After that, all the grades will be finalized. For final exam, the disputation deadline is subject to change upon University's grade submission timeline, please refer to Piazza for further announcements.

Textbooks

Required: Database Management Systems, 3rd edition, by R. Ramakrishnan and J. Gehrke, McGraw Hill, 2003.
Recommended: Readings in Database Systems, 4th edition, by J. Hellerstein and M. Stonebraker, MIT Press, 2005.

Other Readings

The following papers are mostly drawn from the Hellerstein and Stonebraker book or can be found via UCI's ACM Digital Library subscription (http://dl.acm.org). You will be responsible both for the material covered in the lectures and the material covered in the readings listed in the Syllabus below.

  • Abadi, D., Madden, S., and Hachem, N. 2008. Column-stores vs. Row-stores: How Different are They Really?. Proc. ACM SIGMOD Intl. Conf. on Management of Data (Vancouver, Canada, June 2008).
  • Alsubaiee, S., et a., 2014. AsterixDB: a scalable, open source BDMS. Proc. VLDB Endow. 7, 14 (Oct. 2014), 1905-1916.
  • Chamberlin, D., et al, 1981. A history and evaluation of System R. Commun. ACM 24, 10 (Oct. 1981), 632-646.
  • Dean, J., and Ghemawat, S., 2004. MapReduce: Simplified data processing on large clusters. Proc. 6th USENIX Symp. on Op. Sys. Design and Impl. (OSDI'04) (San Francisco, CA, December 2004).
  • DeWitt, D. and Gray, J. 1992. Parallel database systems: The future of high performance database systems. Commun. ACM 35, 6 (June 1992), 85-98.
  • Graefe, G., 2011. Modern B-Tree Techniques. Foundations and Trends in Databases 3, 4 (Sept. 2011) 203-402. (Available from the UCI intranet at: http://dx.doi.org/10.1561/1900000028)
  • Guttman, A. 1984. R-trees: A dynamic index structure for spatial searching. Proc. ACM SIGMOD Intl. Conf. on Management of Data (Boston, Massachusetts, June 1984).
  • Litwin, W., 1980. Linear hashing: A new tool for file and table addressing. Proc. 6th Int'l. Conf. on Very Large Data Bases, Montreal, Oct. 1980.
  • Nievergelt, J., Hinterberger, H., and Sevcik, K. C. 1984. The Grid File: An adaptable, symmetric multikey file structure. ACM Trans. Database Syst. 9, 1 (March 1984), 38-71. (optional)
  • Selinger, P. G. et al, 1979. Access path selection in a relational database management system. Proc. ACM SIGMOD Int'l. Conf. on Management of Data (Boston, Massachusetts, May-June 1979).
  • Shapiro, L. D. 1986. Join processing in database systems with large main memories. ACM Trans. Database Syst. 11, 3 (Aug. 1986), 239-264.
  • Stonebraker, M. 1981. Operating system support for database management. Commun. ACM 24, 7 (July 1981), 412-418.

Programming Project

This class is intended to teach the principles involved in DBMS implementation, so it will include a significant programming component. The project will be aimed at giving you a sense of what goes on inside a DBMS, and what the issues and challenges are in building a system "now" that will be managing data of various user-defined shapes and sizes "later". You will try your hand at record-based file storage, indexing, and relational runtime system programming (a.k.a. query operators). The language for the project will be C++ - hopefully you either have C++ experience or you have Java experience and can learn C++ quickly. Our assistant(s) will run the project, and they can provide you with additional suggestions for material to help you "spin up" on C++ programming, debugging, and tools in case you need to do a bit of remedial work on the side in order to tackle the project successfully. The course has the same requirements for both graduate students and undergraduate students.

Notice about Projects

  • Making teams: Project grades will be team based. Each team can have at most two people. Please let us know about your group by adding your team members' names Group Signup Sheet followed by the group id (please do so even if you are alone in your group). A student can always leave his/her team during the quarter with a notice at least two weeks prior to the next project's deadline. Also, please note that it is not permitted to join a new team after splitting.
  • The projects are doable by individuals, which can be more challenging but rewarding.
  • Students are allowed to add attributes, methods, and classes, as long as the public signatures provided in the codebase are kept and implemented. We will be testing your code by calling the methods that are declared in the signatures.
  • Students also have the freedom to use other open-source libraries or packages (e.g., Gtest and Boost) to implement and test their code. Just please make sure that you: (1) get the okay from us before using any additional packages; (2) list such packages clearly in your project document; and (3) write your makefile correctly so that your project can still be built by calling the 'make' command.

Project Late Policy

  • The official due date for each assignment is listed here on the wiki, and it is expected that students will turn most work in on or before that date.
  • We will offer a 24-hour "grace period" for each assignment, and will therefore accept solution submissions that are turned in within 24 hours of the due date (i.e., less than one day late). No need to ask - this time is yours in the event that you need it for some unforeseen reason. If you use it, your score will be deducted by 10 points (out of 100). You are recommended NOT to use the grace period, as you will lose not only 10 points, but also valuable time from the next assignment's working period for every hour that you run late.
  • Late assignments after the grace period will NOT be accepted, so do always aim to be on time! (Please don't even ask, as this is what the 24-hour grace period is intended for. :-))

Cheating Policy

Cheating is an area where the instructor for this course has absolutely no patience or sympathy whatsoever. You are all here to learn, and cheating defeats that purpose and is unfair to your fellow students. Students will be expected to adhere to the UCI and ICS Academic Honesty policies (and should see http://www.editor.uci.edu/catalogue/appx/appx.2.htm#academic and http://www.ics.uci.edu/ugrad/policies/index.php#academic_honesty to read their details). We run a software package to search for cheating cases in projects. Any student found to be cheating or aiding others in cheating will be academically prosecuted to the maximum extent possible — so you may fail the course with no option for a second chance. This policy will be strictly adhered to; no exceptions will be possible regardless of the impact it may have on your studies, your work plans, your visa status, or anything else. Don’t cheat and you won’t have issues. Just say no to cheating!

C/C++ Resources

Final Exam

Time: Mar 17th Tuesday, 4:00 pm - 6:00 pm at RH 101
Closed books, Closed notes. You can bring an A4-sized "cheat sheet." The exam will cover all the materials taught in this quarter.

Sample midterm, Sample final



Last modified 4 months ago Last modified on Mar 21, 2020 9:08:52 PM

Attachments (15)