CS122C/CS222 Fall 2016: Principles of Data Management
Course Personnel
Instructor:
Chen Li
E-Mail: chenli AT ics DOT uci DOT edu
Office: DBH 2092
Office hours: Tue 11:00-noon, Thu 2 - 3 pm
Assistant:
Te-Yu Chen
E-mail: teyuc AT uci DOT edu
Office: DBH 3219
Reader hours: Mon/Wed 14:00-15:00
Eun-Jeong Shin
E-mail: ejshin1 AT uci DOT edu
Office: DBH 2099
Reader hours: Fri 11:00-noon
Online Discussion: https://piazza.com/uci/fall2016/cs222cs122c/home
- 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. Each student will get 2% extra credits in the overall scores.
Announcements
- The deadline to drop the course is Sept 29, Thursday, before the lecture. After that, "you are in"!
- For students who are still on the waiting list, please continue attending the lectures. We have increased the enrollment capacity to 79 to accommodate the demand.
- For all students, please notice that the first project is already online, and you are encouraged to start working on it soon.
Syllabus
Date | Topic | Readings | Notes |
09/22/16, Th | DBMS Architecture | Ch. 1; Chamberlin et al 1981 | PDF, PPT, guest lecture by Prof. Mike Carey |
09/27/16, Tu | Course Overview, Project 1, Disks and Files | Ch. 9.1-9.4; Stonebraker 1981 | PDF, PPT |
09/29/16, Th | Page structure, Heap Files, | Ch. 9.5-9.8 | PDF, PPT |
10/04/16, Tu | Catalogs, Buffer Manager, | Ch. 8-8.4 | PDF, PPT |
10/06/16, Th | Project 2, Heap Files, Sorted files | ditto | ditto |
10/11/16, Tu | Index Overview and ISAM Tree Index | ditto | PDF, PPT |
10/13/16, Th | Schema versioning, B+ tree | Ch. 10; Graefe 2011 (Sec. 1-3) | PDF, PPT |
10/18/16, Tu | B+ tree | ditto | ditto |
10/20/16, Th | Static Hashing, Extendible Hashing, Linear Hashing | Ch. 11; Fagin et al 1979; Litwin 1980 | PDF07, PPT07, PDF08, PPT08 |
10/25/16, Tu | Indexing and Performance | Ch. 8.5-8.6 | PDF, PPT |
10/27/16, Th | Project 3, ditto | ditto | ditto |
11/01/16, Tu | Midterm (extra class room, ICF101) | ||
11/03/16, Th | External Sorting | Ch. 13 | PDF, PPT, |
11/08/16, Tu | Selection, Projection | Ch. 14.1 - 14.3 | PDF, PPT |
11/10/16, Th | Join | Ch. 14.4 | PDF, PPT |
11/15/16, Tu | Set operations, Aggregation, Query Plans | Ch. 14.5, 14.6, Ch. 12 | PDF, PPT |
11/17/16, Th | Project 4, ditto | Ditto | |
11/22/16, Tu | Cost estimation | Ch. 15.2 | PDF, PPT |
11/29/16, Tu | Plan Optimization (System-R) | Ch. 15.3, Selinger et al 1979 | PDF, PPT |
12/01/16, Th | System-R Optimizer, Open Topics, Course Wrap Up | Ditto | PDF, PPT |
Projects
The project is structured as a four-part, team-based, software development exercise:
Project | Due Date | Topic | Teams | Proportions (45%) | Graded By |
Project 1 | Wed, Oct. 5 | Record-Based File Manager (RBF) | Solo Project | 8% | Te-Yu |
Project 2 | Wed, Oct. 26 | Relation Manager (RM) | Pair Project | 12% | Eun-Jeong |
Project 3 | Thu, Nov. 17 | Index Manager (IX) | Pair Project | 13% | Te-Yu |
Project 4 | Thu, Dec. 1 | Query Engine (QE) | Pair Project | 12% | Eun-Jeong |
Schedule & Location
Lecture
Days: Tuesdays and Thursdays
Time: 9:30 am – 10:50 am
Location: MSTB 120
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), CS 143A (Principles of Operating Systems), and CS 152 (Computer Systems Architecture). Please don't attempt this class without the required background! (Doing so has not proven to be a great idea for students historically. :-))
Grading Breakdown
Class Participation: 5%
Midterm Exam: 25%
Final Exam: 25%
Four-Part Programming Project: 45%
This mixture of grading criteria for CS222 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 exams 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 two exams will be closed-book, but you may bring an 8.5"x11" two-sided cheat sheet to each exam if you like.
For all the graded projects and exams, 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.
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.
- Fagin, R., et al, 1979. Extendible Hashing—A fast access method for dynamic files. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 315-344.
- 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.
Class Participation
As mentioned above, a small fraction of the course grade will be for "class participation". At various times I will ask for feedback via EEE or Piazza, and everyone will be expected to respond. This feedback will help me guide the lectures, projects, etc., during this quarter and future quarters. This small but important portion of your grade will be determined largely by whether or not you participate online. (Note that it'll be easy to get the full participation credit - you will just have to be enrolled on Piazza and then answer these infrequent surveys by their deadlines, which by the way will also include the final "instructor evaluation" at the end of the course.) 5% of the class participation grade will be based on online participation.
Class Discussion Forum
We will be using Piazza for online class discussions. This system is highly catered to getting you help fast and efficiently from classmates, the Reader(s), and the instructor. Rather than emailing questions to any of us on the teaching staff, we'll ask you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@…. Please make Piazza participation (at least monitoring the activity there) a part of your regular CS122C/222 routine!
You can find our class page at: https://piazza.com/uci/fall2016/cs222cs122c/home
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.
Comprehensive Exam Option
Computer Science graduate students wishing to satisfy the MS Comprehensive Exam requirement in Database Systems via CS222 should notify the instructor and the Student Advising Office (SAO) of this intention via e-mail before the day of the final exam. For such students, a weighted mix of your midterm and final exam performance will be used to determine your MS Comprehensive Exam grade (P or F) at the end of the course, and this grade will be reported to SAO. Students who do not pass successfully can try the exam again the next time CS 222 is offered by taking the midterm and final exams in that offering of the course; hopefully this will not be necessary for anyone. (Students who do this are advised to informally audit the next offering of the class; this is because the course emphasis and expected knowledge can vary a bit by term and by instructor, and also because you'll probably need the review to pass.)
Notice about Projects
- Students should work on parts 2-4 of the project in groups of two. Please let us know about your group by following the instructions that will be provided via Piazza when the time comes to do so. (In general, you should keep a close eye on Piazza all throughout the quarter!)
- Students who strongly prefer to work alone for one reason or another may do so by requesting permission from the instructor — although it’s not advisable, and you will not get any “discount” on the assignment requirements if you opt to take this path.
- 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 a Reader 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 48-hour "grace period" for each assignment, and will therefore accept solution submissions that are turned in within 48 hours of the due date (i.e., less than two days 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 5% (out of 100%). You are recommended NOT to use the grace period, as you will lose not only 5%, 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 two-day 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). Any student found to be cheating or aiding others in cheating will be academically prosecuted to the maximum extent possible — so you will 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
- A helpful reference for C/C++ libraries: http://www.cplusplus.com/reference/
- A tutorial on programming in C/C++ and guide on related resources: http://www.cprogramming.com/tutorial.html#c++tutorial
- A tutorial on learning C++ for Java programmers: http://pages.cs.wisc.edu/~hasti/cs368/CppTutorial/index.html
Midterm Exam
Time Nov. 1, Tuesday, In-class. Closed books. You can bring an A4-sized "cheat sheet."
Final Exam
Thursday, December 8, 2016, 8:00 a.m. - 10:00 a.m
Usual classroom and an extra classroom Interim Classroom Facility (ICF) 101. Closed books, Closed notes. You can bring an A4-sized "cheat sheet." The exam will cover all materials taught in this quarter, with a more emphasis on those after the midterm.
Attachments (36)
-
cs222-lecture01.ppt
(1.1 MB) -
added by chenli 8 years ago.
Lecture 01: PPTX
-
cs222-lecture01.pdf
(436.9 KB) -
added by chenli 8 years ago.
Lecture 01: PDF
-
cs222-lecture02.ppt
(1.2 MB) -
added by chenli 8 years ago.
Notes 02 PPT
-
cs222-lecture02.pdf
(431.6 KB) -
added by chenli 8 years ago.
Notes 02 PDF
-
cs222-lecture03.pdf
(230.4 KB) -
added by chenli 8 years ago.
Lecture 03: PDF
-
cs222-lecture03.ppt
(806.0 KB) -
added by chenli 8 years ago.
Lecture 03: PPT
-
cs222-lecture04.pdf
(267.6 KB) -
added by teyuc 8 years ago.
Lecture 04: PDF
-
cs222-lecture04.ppt
(475.0 KB) -
added by teyuc 8 years ago.
Lecture 04: PPT
-
cs222-lecture05.ppt
(2.3 MB) -
added by chenli 8 years ago.
Lecture 05: PPT
-
cs222-lecture05.pdf
(147.7 KB) -
added by chenli 8 years ago.
Lecture 05: PDF
-
cs222-notes06.ppt
(3.4 MB) -
added by chenli 8 years ago.
Notes 06 PPT
-
cs222-notes06.pdf
(195.2 KB) -
added by chenli 8 years ago.
Notes 06 PDF
-
cs222-notes07.pdf
(176.2 KB) -
added by teyuc 8 years ago.
Notes 07 PDF
-
cs222-notes07.ppt
(475.5 KB) -
added by teyuc 8 years ago.
Notes 07 PPT
- 2010-fall-midterm.pdf (152.1 KB) - added by ejshin1 8 years ago.
- 2010-fall-midterm-solution.pdf (893.3 KB) - added by ejshin1 8 years ago.
-
cs222-notes08.ppt
(1.2 MB) -
added by chenli 8 years ago.
Lecture 08: PPT
-
cs222-notes08.pdf
(215.0 KB) -
added by chenli 8 years ago.
Lecture 08: PDF
-
cs222-notes09.ppt
(2.4 MB) -
added by chenli 8 years ago.
Notes 09 PPT
-
cs222-notes09.pdf
(159.4 KB) -
added by chenli 8 years ago.
Notes 09 PDF
-
cs222-notes10.ppt
(960.0 KB) -
added by chenli 8 years ago.
Notes 10 PPT
-
cs222-notes10.pdf
(255.3 KB) -
added by chenli 8 years ago.
Notes 10 PDF
-
cs222-notes11.ppt
(330.0 KB) -
added by chenli 8 years ago.
Lecture 11: PPT
-
cs222-notes11.pdf
(141.5 KB) -
added by chenli 8 years ago.
Lecture 11: PDF
-
cs222-notes12.ppt
(1.1 MB) -
added by chenli 8 years ago.
Lecture 12: PPT
-
cs222-notes12.pdf
(336.1 KB) -
added by chenli 8 years ago.
Lecture 12: PDF
- 2016-fall-midterm-solution.pdf (995.4 KB) - added by ejshin1 8 years ago.
-
cs222-notes13.ppt
(498.0 KB) -
added by chenli 8 years ago.
Notes 13 PPT
-
cs222-notes13.pdf
(225.3 KB) -
added by chenli 8 years ago.
Notes 13 PDF
-
cs222-notes14.pptx
(305.5 KB) -
added by chenli 8 years ago.
Lecture 14: PPT
-
cs222-notes14.pdf
(295.4 KB) -
added by chenli 8 years ago.
Lecture 14: PDF
- 2012-fall-final-solution.pdf (180.6 KB) - added by teyuc 8 years ago.
-
cs222-notes15.ppt
(742.5 KB) -
added by chenli 8 years ago.
Lecture 15: PPT
-
cs222-notes15.pdf
(270.2 KB) -
added by chenli 8 years ago.
Lecture 15: PDF
-
cs222-notes16.ppt
(1.4 MB) -
added by chenli 8 years ago.
Notes 16: PPT
-
cs222-notes16.pdf
(990.0 KB) -
added by chenli 8 years ago.
Notes 16: PDF