CS 448/648 (Winter 2012)
Database Systems Implementation


Course Information Workload and Evaluation Schedule and Lecture Notes Assignments Exams CS648 Info Academic Integrity

Course Information

Note: There will be no CS448/648 lecture on Thursday Feb 16th, the date of the
midterm exam. On that day (only), instructor office hours will run from 1:00-4:00 in DC 3512.
Meeting Time and Place: TTh 1:00-2:20 in PHY 313
Instructor: Ken Salem, DC3512, userid: kmsalem
Office Hours: Mon 1:00-2:00, Tue 4:00-5:00, Thu 3:00-4:00
April office hours: Apr 5th 2:30-4:00, Apr 9th 1:00-2:00, Apr 10th 3:00-5:00
TAs: Changjiu Jin, userid: c4jin
Shahab Kamali, userid: skamali
Xin Liu, userid: x39liu
TA Office Hours: Shahab will hold office hours Wed 11:30-1:30 in DC3306
Discussion Board: We will be using Piazza for on-line discussion and announcements. We will be using Waterloo's LEARN system only for posting exam and assignment marks. Course personnel will not be monitoring the uw.cs.cs448 newsgroup this term.

E-mail to course personnel can be directed to userid at cs dot uwaterloo dot ca. The userids are listed above.

Course Description and Objectives

This is a second course on databases that focuses on DBMS internals. It is a project-oriented course that will provide the students, upon successful completion, with an appreciation of the intricacies and complexities of a DBMS and enable them to be able to design and implement the major components of it. The course objective will be achieved by focusing on three fundamental sub-objectives:
  1. To understand the fundamentals of storage systems and disk-based data structures;
  2. To understand the process of query processing and optimization; and
  3. To learn the implementation of transactions.

Complementary to the above objectives, the course has a training component where the students will gain experience, within the context of a number of assignments, in building components of a DBMS and incorporating them into an open source system such as MySQL or PostgreSQL. The lectures may be complemented by guest lectures on real-life DBMS implementation issues given by colleagues from industry. Further details can be found at http://www.cs.uwaterloo.ca/current/courses/course_descriptions/cDescr/CS448.

Workload and Evaluation

The course marking scheme for CS448 is:

In addition, you must pass the exams in order to pass the course. That is, having a weighted exam average above 50% is a necessary (but not sufficient) condition for passing.

Graduate students enrolled in CS648 have different requirements, and will use a different marking scheme. See the CS648 section for more information.

Assignment and exam marks will be posted on UW's LEARN on-line course system. Log in to LEARN using your WatIAM userId and password and select CS448/648 to view your marks once they have been posted. Mark posting is the only thing we will be using LEARN for this term. All course materials can be found on this web page, and Piazza will be used for discussion and announcements.

Optional Alternative Workload for CS448 Students

CS448 students who wish to participate in the SIGMOD 2012 Programming Contest have the option of doing so as a CS448 course project. CS448 students who choose this alternative will be evaluated using the CS648 workload and marking scheme, rather than the standard CS448 scheme. That is, their programming contest project will replace CS448 Assignment 3, and they will use the same project, exam and assignment marking weights as CS648 students. Details about the requirements for the SIGMOD programming contest as a course project can be found on the CS648 project page.

CS448 students who wish to use this alternative must elect to do so no later than January 24th. This election is not revocable after January 24th.

CS448 students who are interested in this alternative should elect to use it by sending e-mail to the instructor by the January 24th deadline. The e-mail should include name, ID number, and UW e-mail address. If you expect to work on the project with a group, please also include the names of the other group members.

Schedule and Lecture Notes

The table below shows planned lecture topics, along with the corresponding textbook chapters and links to the lecture notes (as they become available). The course textbook is Database Management Systems. R. Ramakrishnan and J. Gehrke. McGraw-Hill. 3rd Edition. The textbook is optional. It will be available through the Davis Centre Library course reserves.

Lecture notes are available in PDF format, one slide per page. Using Adobe Acrobat or a similar program, you should be able to print these with multiple slides per page to save paper and cost. Printing two slides per page, double-sided is a good option - the slides are still easy to read, even with substantial margins (for note taking) left around the slides.
Start End Topic Chapters Lecture Notes
Jan 03 Jan 03 Intro n/a PDF
Jan 03 Jan 05 DBMS Architecture n/a PDF
Jan 05 Jan 19 Data Storage Chapter 9 PDF
Jan 05 Jan 19 Access Methods Chapters 8,10,11 PDF
Jan 24 Feb 2 Query Processing Chapters 12,13,14 PDF
Feb 2 Mar 6 Query Optimization Chapter 15 PDF
Feb 9 Feb 9 Spatial Indexing (guest lecture) Chapter 28 PDF
Mar 6 Concurrency and Failures Chapters 16,17,18 PDF
Mar 27 Distributed Data Management Chapter 22 PDF


Assignment 0: PostgreSQL setup
Assignment 1: Prefix Key Compression
Assignment 2: Symmetric Hash Join
Assignment 3: Query Optimization


Midterm Exam
Final Exam
Study Materials

CS648 Information

Students enrolled in CS648 are responsible only for the first two assignments (A1 and A2). Instead of A3, CS648 students must do a final project. Information about the CS648 final project is available on the CS648 project information page. CS648 will use the following marking scheme, which differs from the CS448 marking scheme because of the project: Like CS448 students, CS648 students must pass the exams to pass the course. That is, having a weighted exam average above 50% is a necessary (but not sufficient) condition for passing.

Academic Integrity

In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research. The Office of Academic Integrity's website (www.uwaterloo.ca/academicintegrity) contains detailed information on UW policy for students and faculty. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in - and out - of the classroom.

Grievance: A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 - Student Petitions and Grievances, Section 4, http://www.adm.uwaterloo.ca/infosec/Policies/policy70.htm

Discipline: A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71 - Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71 - Student Discipline, http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm

Avoiding Academic Offenses: Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy, http://www.math.uwaterloo.ca/navigation/Current/cheating_policy.shtml

Appeals: A student may appeal the finding and/or penalty in a decision made under Policy 70 - Student Petitions and Grievances (other than regarding a petition) or Policy 71 - Student Discipline if a ground for an appeal can be established. Read Policy 72 - Student Appeals, http://www.adm.uwaterloo.ca/infosec/Policies/policy72.htm