CS145 Introduction to Databases

NVIDIA Auditorium on TTh 3:00-4:20pm

Chat with us on the course Piazza site if you have any questions!

Description
This course covers database design and the use of databases in applications, with a short introduction to the internals of relational database engines. It includes extensive coverage of the relational model, relational algebra, and SQL. The course also features database design and relational design principles based on dependencies and normal forms. Many additional key database topics from the design and application-building perspective are also covered, including indexes, views, transactions, and integrity constraints. Systems such as MapReduce framework and key-value stores will also be covered. There will be a programming project, which explores database design and management in web applications by utilizing appropriate features of SQL.
Class Logistics

We're excited to once again utilize Jupyter notebooks to allow for more interactivity in the class. Installation instructions are available here. Python is used in the in-class activities, homework and projects.

For the attendance portion of the class (SCPD students are exempt from this), we will write a code on the board during class. From your primary stanford email, send a note to 145attendance@gmail.com with the code in the Subject Line of the email. Do not write anything other than the code in the subject line and make sure that the body of the email is empty. You are responsible for attending 8 classes + 2 guest lectures.

Lecture Plan

The reading material listed below is optional, but it refers to Database Systems: The Complete Book by Garcia-Molina, Ullman, and Widom. The lecture plan below may change.


# Date Topic Lecture Materials Extra Reading Material Assignments
Introduction and Querying
1 9/27 Course Logistics and Database History Lecture 1 (pdf)

Activities:
Notebook data: dataset_1.db
2 9/29 SQL: Introduction Lecture 2-3 (pdf)

Activities: Notebook data: dataset_1.db
Greenspun- SQL for web nerds PS #1:
3 10/4 SQL: Advanced Ch. 6
Database Design and Normal Forms
4 10/6 Database Design: ER Diagrams Lecture 4 (pdf)

Activity Solutions (pdf)
Ch. 2 Project Part 1
5 10/11 Database Design: Theory 1 Lecture 5-6 (pdf)

Activities:
Ch. 3.2-3.7 PS #1 Due
6 10/13 Database Design: Theory 2 PS #2:
Transactions
7 10/18 Transactions from a User's Perspective Lecture 7-8 (pdf)
Modified Lecture 8 (pdf)

Activities:
Ch. 8.6 Project Part 1 Due
8 10/20 Mechanisms for Transactions: Logging and Locking Ch. 18.1-18.4
Midterm
9 10/25 Midterm Review Midterm Review Slides (pdf) PS #2 Due
10 10/27 Midterm
Location: NVIDIA (Last Names: A-L) and Hewlett 200 (Last Names: M-Z)
Cheat-sheet
Introduction to Database Internals
11 11/1 IO Cost Models and External Sort Lecture 11-12 (pdf)
Lecture 12 (pdf)

Activities:
Ch. 11.4 Project Part 2
12 11/3 Indexing Ch. 13.1-13.3
13 11/8 Guest Lecture: Hakan Hacigumus, Google Ads
14 11/10 Access Methods and Operators Lecture 14 (pdf)
Lecture 15 (pdf)


Activities:
Ch. 15 (except 15.9)
15 11/15 Joins: A Cage Match Ch. 2 and 16.3 Project Part 2 Due

Project Part 3 PS #3:
16 11/17 Relational Algebra Lecture 16 (pdf)

Activities:
Ch. 2 and 16.3
Thanksgiving Break: 11/21-11/25
17 11/29 Query Optimization Lecture 17 (pdf)

Activities:
Bonus Activities:
NoSQL Systems, Wrap up & Final
18 12/1 Research Talk: Dark Data and Analytics Systems Activities: PS #3 Due
19 12/6 Final Exam Review Final Review Lecture (pdf)
Review Notes

20 12/8 Guest Lecture: Matei Zaharia, InfoLab Faculty and Spark Cocreator Project Part 3 Due

Change log:
Note: you may have to clear your browser's cache to get newest files!
  • 9/25/16 3:00pm - Lectures 1, 2, and 3 Updated
  • 10/04/16 3:30pm - Lecture 2-3 Updated
  • 10/04/16 5:00pm - Added activity solutions from Lectures 2-3
  • 10/04/16 5:10pm - Added Lecture 4
  • 10/06/16 11:20am - Updated Lecture 4
  • 10/06/16 11:30am - Added Project Part 1
  • 10/06/16 3:50pm - Added activity solutions from Lecture 4
  • 10/08/16 11:00pm - Added Lecture 5-6 and associated activities
  • 10/11/16 3:10pm - Updated Lecture 5-6 and associated activities
  • 10/11/16 3:20pm - Added PS2
  • 10/12/16 1:00pm - Updated PS2 submission template, added submission instructions, added Activity 5-1 solutions
  • 10/13/16 2:30pm - Updated PS2 pdf
  • 10/13/16 5:15pm - Added Lecture 6 Activity solutions pdf
  • 10/17/16 1:15am - Added Lecture 7-8 and Activities, Updated Lecture 4
  • 10/20/16 3:05pm - Uploaded modified Lecture 8 to website
  • 10/20/16 10:00pm - Uploaded Midterm Review + Midterm Cheatsheet
  • 10/22/16 12:45pm - Uploaded PS1 Solutions and Project 2
  • 10/25/16 2:15am - Updated Guest Lecture Date (Due to a Conflict)
  • 10/25/16 2:45am - Updated Midterm Logistics
  • 11/06/16 11:45pm - Added Project Part 3
  • 11/07/16 1:00pm - Updated class schedule for last three classes
  • 11/07/16 1:20pm - Uploaded PS2 Solutions
  • 11/10/16 11:50am - Uploaded Lecture 14-15 and Activity
  • 11/12/16 11:10am - Uploaded Bonus Activities
  • 11/12/16 11:25am - Added Review Notes for the Final
  • 11/13/16 12:15pm - PS3 Uploaded
  • 11/20/16 12:15pm - PS3 Submission Instructions Added
  • 11/22/16 2:15pm - Uploaded External Merge Sort Activity
  • 11/26/16 12:45pm - PS3 Q3 aii typo fixed - should be MRU
  • 11/28/16 12:25am - Lecture 17 Uploaded
  • 11/30/16 1:30pm - Lecture 17 and Lecture 14 Updated, Activity 17 Solns Posted
  • 12/01/16 2:30pm - Added Activity 18
  • 12/06/16 11:00am - Added PS3 Solutions
  • 12/06/16 2:50pm - Added Final Review
Midterm Exam
The midterm exam will be in class on October 27th from 3:00pm - 4:20pm. The locations will be:
  • NVIDIA Auditorium - Last Names A-L
  • Hewlett 200 - Last Names M-Z
Final Exam
The final exam will be on December 13th at 3:30pm. The location is in CEMEX Auditorium.
Grading
Lecture Attendance10%
Problem Sets20%
Programming Project20%
Midterm20%
Final30%

Note: SCPD students will be exempt from the "Lecture Attendance" portion. Grading will be scaled proportionately over the remaining segments.

Office Hours

Unless otherwise specified in the staff section below, office hours will be held in the open area of the Huang basement. CAs will bring signs to identify themselves. Please see the staff section below for office hours.

Note: the schedule of office hours may change from time to time, in which case an announcement will be made on the course Piazza.

Staff
Chris
Tara Balakrishnan (taragb@stanford.edu)
Adam Ginzberg (ginzberg@stanford.edu)
Amani Peddada (amanivp@stanford.edu)
Connie Zeng (czeng2@stanford.edu)
Don Mai (donmai@stanford.edu)
Helen Fang (hfang9@stanford.edu)
Jeffrey Pyke (pyke@stanford.edu)
Krister Johnson (kristerj@stanford.edu)
Lindsey Kostas (lmkostas@stanford.edu)
Luda Zhao (ludazhao@stanford.edu)
Russell Stewart (stewartr@stanford.edu)
Senthilnathan Viswanathan (svnathan@stanford.edu)
OHs
Late Policy
You will have three 24-hour "late days" that you can use throughout the quarter on any of the Problem Sets or Programming Projects, unless specified otherwise. Beyond these three late days, we will only grant extensions in the case of a severe medical or family emergency. Please use your late days wisely.
Honor Code and Collaboration Policy

We encourage you to discuss the Programming Projects and Problem Sets with other students; it's fine to discuss overall strategy and collaborate with a partner or in a small group, as both giving and receiving advice will help you to learn.

However, for the Programming Projects, you must write your own code: it's not OK to share code or write code collaboratively. (This includes posting and/or sharing your code publicly, such as on GitHub!) Likewise, for the Problem Sets, you must write up your own solutions to all of the problems, and you must cite all people you worked with. If you do not do so, we will consider this a violation of the Stanford Honor Code.

If you consult any resources outside of the materials provided in class, you must cite these sources. We reserve the right to assign a penalty if your answers are substantially derivative, but, as long as you provide appropriate citations, we will not consider this an Honor Code violation.

Students with Documented Disabilities
Students who may need an academic accommodation based on the impact of a disability must initiate the request through the Office of Accessible Education (OAE). OAE staff will evaluate the request with required documentation, recommend reasonable accommodations, and prepare an Accommodation Letter for faculty dated in the current quarter in which the request is being made. Students should contact OAE as soon as possible since timely notice is needed to coordinate accommodations: 563 Salvatierra Walk; phone: (650) 723-1066.