CS 3200: Database Design

This course studies the design of a database for use in a relational database management system. The entity-relationship model and normalization will be used in example problems. Relational algebra and the SQL language will be presented. Advanced topics include triggers, stored procedures, indexing, elementary query optimization, and fundamentals of concurrency and recovery. Students will implement a database schema and short application programs on one or more commercial relational database management systems.

News

[12/08/2010] Slides from Dec 6 and 8 lectures posted
[12/01/2010] Slides from Dec 1 and 2 lectures posted
[11/29/2010] Final project Milestone 8 posted
[11/29/2010] Slides from Nov 29 lecture posted
[11/22/2010] Slides from Nov 22 lecture posted
[11/17/2010] Slides from Nov 17 and 18 lectures posted
[11/15/2010] Slides from Nov 15 lecture posted
[11/15/2010] Project Milestone 7 posted
[11/09/2010] Milestone 6 deadline moved
[11/03/2010] Project Milestone 6 posted

Lectures

(Future lectures and events are tentative.)

Date Topic Remarks and Homework
09/08 Introduction Read chapter 1.
09/09 Introduction (cont.); Entity-Relationship Model Read relevant sections in chapter 2.
09/13 Entity-Relationship Model Read relevant sections in chapter 2.
09/15 Entity-Relationship Model; Relational Model Read chapter 2 and relevant sections in Chapter 3.

Optional HW just for fun: Try SQL queries like the one on slide 8 on your Milestone 1 database. Explore what happens when you modify the SELECT or WHERE clauses. (Hint: Right-click on your database, select "New Query". Then compose the query and click on "! Execute".)
09/16 Relational Model Read relevant sections in chapter 3.

Optional HW: Explore the different effects of update and delete options for foreign key relationships. Create some relations with foreign key references, insert a few "correct" tuples, then try to insert one that "points to" a non-existing entry. Similarly, try what happens when you delete the tuple that is referenced through the foreign key.
09/17 Project Milestone 1 due at 5pm  
09/20 Relational Model Read chapter 3.

Optional HW: Slide 24 shows how to model a 1-to-many relationship. How would we model a 1-to-1 relationship, i.e., where we also have an arrow from Employees pointing to Manages? Hint: It often helps to look at some example tuples.
09/22 Relational Algebra Read relevant sections in chapter 4.

Optional HW: Insert tuples that have the same values in one or more of the columns. Then perform a projection (SELECT AttrWithDuplicates FROM table) such that the result would have duplicate tuples. See if the DBMS eliminated the duplicates. Then try the same query using SELECT DISTINCT.
09/23 Relational Algebra; Schema Refinement Read relevant sections in chapters 4 and 19.
09/24 Project Milestone 2 due at 5pm  
09/27 Discussion of Milestone 2  
09/29 Schema Refinement Read relevant sections in chapter 19.

Optional HW: Go through the example on slide 6 and try to explain to a friend (i) what is wrong with the wide table SNLRWH and (ii) in what sense the two narrower tables SNLRH and RW are better.

Optional HW: For the example on slide 9, use the algorithm to check if DA->E and D->E are in F+.
09/30 Schema Refinement Read relevant sections in chapter 19.

Optional HW: Prove formally that relation Reserves(S, B, D, C) with set of FDs F={SBD->SBDC, S->C} is NOT in 3NF. Is it in BCNF?

Optional HW: Prove formally that relation Reserves(S, B, D, C) with set of FDs F={SBD->SBDC, S->C, C->S} is in 3NF.
10/04 Schema Refinement Read relevant sections in chapter 19.

Optional HW: Consider the example on slide 24, i.e., relation R=ABC with set of FDs F={A->B, B->C, C->A}. ABC is decomposed into X=AB and Y=BC. In class we discussed how we can argue that the closure of the union of FX and FY is identical to F+, even without completely generating FX, FY, or even F+. Try to create this same chain of arguments on your own, then explain this to a friend and see if you can convince her/him that this particular decomposition is dependency-preserving.
10/05 Project Milestone 3 due at 5pm  
10/06 Schema Refinement Read relevant sections in chapter 19.
10/07 SQL Read relevant sections in chapter 5.

Optional HW: Choose one of the example SQL queries that has two relations in the FROM clause. Then manually run the conceptual evaluation strategy on the example data. Make sure you perform each step completely.
10/11 No class: Columbus Day  
10/13 SQL Read relevant sections in chapter 5.
10/14 SQL Read relevant sections in chapter 5.
10/15 Project Milestone 4 due at 5pm  
10/18 SQL Read relevant sections in chapter 5.

Optional HW: Run the conceptual evaluation algorithm (slide 21) to manually and step-by-step compute the result for the queries on slides 22, 24, 25, and 27. Notice how adding a constraint to the WHERE or HAVING clause has a very different effect on the computation. Also think about which other attributes could be used in the WHERE or HAVING clauses to add other possible constraints.

Optional HW: In your own words, explain why for the query on slide 26 we cannot add "HAVING B.color = 'red'" to the query (i.e., move that constraint from the WHERE clause to the HAVING clause). Why does it have to be in the WHERE clause? If we wanted it in the HAVING clause, we need to use EVERY(B.color='red') or similarly with ANY. Why is that so and how is the result affected by EVERY versus ANY?
10/20 SQL Read chapter 5.
10/21 Midterm Exam The midterm takes place at the same time and location as the lecture. Please make sure you arrive on time.
10/25 Relational Calculus Read relevant sections in chapter 4.

Optional HW: Try to write the SQL queries we discussed in previous lectures in domain relational calculus.
10/27 DB Application Development Read relevant sections in chapter 6 and look at the Java API (java.sql in particular) for the interfaces and methods we discussed.
10/28 DB Application Development Read relevant sections in chapter 6 and look at the Java API (java.sql in particular) for the interfaces and methods we discussed.
10/29 Project Milestone 5 due at 5pm  
11/01 Storage and Indexing Read relevant sections in chapter 8. Look at java.util.HashMap and java.util.TreeMap.
11/03 Storage and Indexing Read relevant sections in chapter 8.
11/04 Storage and Indexing Read relevant sections in chapter 8.
11/08 Storage and Indexing Read relevant sections in chapter 8.
11/10 Storage and Indexing Read relevant sections in chapter 8.
11/11 No class: Veterans Day  
11/12 Project Milestone 6 due at 5pm  
11/15 Query Evaluation Read relevant sections in chapter 12.
11/17 Query Evaluation Read relevant sections in chapter 12.
11/18 Query Evaluation, Discussion of HW 6 solution Read relevant sections in chapter 12.
11/22 Transactions
Project Milestone 7 due at 5pm		 Read relevant sections in chapter 16.
11/24, 25 No class: Thanksgiving  
11/29 Transactions Read relevant sections in chapter 16.

Optional HW: Review the anomalies discussed on the slides and manually simulate the Strict 2PL protocol to see how locking prevents these anomalies from occurring.
12/01 Transactions; Recovery Read relevant sections in chapter 16 and 18
12/02 Recovery Read relevant sections in chapter 18
12/06 Course review and final exam prep
Project Milestone 8 due at 5pm		 Make sure you can answer or explain all questions and points made in the slides. Go over the HWs and slides, and read the relevant book chapters.
12/08 MapReduce and SQL Injections
Questionnaire due at 5pm		  
12/16 Final Exam As of 12/08 the final exam will take place 8:00-10:00am on 12/16, in WVH 110. This information is provided for convenience only. Please look at the appropriate NEU pages for the official and most up-to-date information.

Course Information

Instructor: Mirek Riedewald

TA: Yue Huang

Meeting times: MWR 10:30am - 11:35am
Meeting location: WVH 108

Prerequisites

CS 2510 (CS U213)

Grading

Textbook

Raghu Ramakrishnan and Johannes Gehrke. Database Management Systems, 3rd edition, McGraw Hill, 2002

Academic Integrity Policy

A commitment to the principles of academic integrity is essential to the mission of Northeastern University. The promotion of independent and original scholarship ensures that students derive the most from their educational experience and their pursuit of knowledge. Academic dishonesty violates the most fundamental values of an intellectual community and undermines the achievements of the entire University.

For more information, please refer to the Academic Integrity Web page.