Captain's Log: Database Management Systems, Spring 2009

1: January 16 (Friday)

Go through syllabus.
Introduction and motivation, giving a high-level perspective on database design (Chapter 1 and Section 2.1).

January 19 (Monday)

University Holiday (Martin Luther King)

2: January 21 (Wednesday)

Embark on the relational model: the basics (Section 2.2); how to define a schema in SQL (Section 2.3); most of the basic operators of relational algebra (Section 2.4.1-2.4.7).
First Gradiance homework out.

3: January 23 (Friday)

Finish basic relational algebra, listing all the operators (Section 2.4) which can be used to express various types of constraints on tables (Section 2.5).
Do Exercise 2.4.5 & Exercise 2.4.3 (c,d,e).
Gradiance HW1 due at midnight.

4: January 26 (Monday)

Wrap up basic relational algebra by doing Exercise 2.4.3(f,g,i), Exercise 2.4.7, and Exercise 2.4.10 which introduces the quotient operator (cf. slides).

5: January 28 (Wednesday)

Start on Chapter 3 on how to design relational databases, introducing the notion of functional dependencies thus covering most of Sections 3.1 & 3.2.
Do Exercises 3.1.1 & 3.2.1.

6: January 30 (Friday)

Continue Section 3.2, with focus on: proof that the attribute closure algorithm is sound and complete; the notion of a minimal basis; projecting functional dependencies onto a subset of attributes.
Do Exercise 3.2.10 (a,b)
Assignment 1 (on paper) due at 4pm.

7: February 2 (Monday)

Continue Chapter 3, on decomposing relations: why (avoid anomalies), how (for instance BCNF as in Section 3.3), and what not to do (lose information, cf. Section 3.4.1).
Do Exercises 3.3.1 (a,c), Exercise 3.3.2, Exercise 3.3.3.
Gradiance HW2 (functional dependencies) due at midnight.

8: February 4 (Wednesday)

Cover Sections 3.4 & 3.5, with focus on the trade-off between preserving dependencies, as always done by 3NF, and avoiding anomalies, as always done by BCNF.
Introduce "the chase" to show that selected decompositions, in particular those that convert into BCNF, are lossless.
Gradiance HW3 (advanced functional dependencies) due at midnight.
Last day for 100 % refund.

9: February 6 (Friday)

Introduce multi-valued dependencies (MVD) and 4NF (Sections 3.6 & 3.7).
Emphasize how the chase is very useful to check whether dependencies follow from other dependencies, and also to check if a given decomposition is lossless (Exercise 3.4.1(a,b)).
Graded Assignment 1 back; go through model solutions.
Gradiance HW4 (on normalization) due tomorrow morning.

10: February 9 (Monday)

Finish MVDs, in particular give 4NF decomposition algorithm, doing Exercises 3.6.2 and Exercise 3.7.1.
Mention that there are even more sophisticated normal forms (very rarely used in practice though), and that a database can be badly designed even though it is normalized.
Gradiance HW5 (on multi-valued dependencies) due tomorrow morning.

11: February 11 (Wednesday)

Embark on E/R design (Chapter 4), covering the basic concepts and doing Exercises 4.1.1, 4.1.2, 4.1.3, 4.1.5.
Last day for 50 % refund.

12: February 13 (Friday)

Continue E/R design, introducing weak entity sets (Sect. 4.4) and subclasses (Sect. 4.1.11).
Discuss how to translate E/R diagrams into relational databases (Sects. 4.5-6).
Illustrate how the Chase can also be used for query simplification.
Gradiance HW6 (on basic E/R design) due tomorrow morning.

13: February 16 (Monday)

Give one more example (put on K-State Online) of how the Chase is used for query simplification.
Do Exercise 3.4.2 on dependency preservation. so as to prepare for the upcoming Assignment 2.
Do Exercise 3.5.2, thereby finishing Chapter 3.
Do Exercise 4.4.4, illustrating the notion of weak entity set.
Gradiance HW7 (on translating E/R) due tomorrow morning.

14: February 18 (Wednesday)

Introduce the notion of bags (Section 5.1), illustrated by Exercises 5.1.3(b), 5.1.4(a,b,h), 5.1.5 (b).
Extend the relational algebra (Section 5.2).
Assignment 2 (on paper) due at 4pm.
Tomorrow (Feb 19) is last day to drop without W being recorded.

15: February 20 (Friday)

Go through model solutions for Assignment 2.
Get more familiar with bags through Exercise 5.1.5(a,c).
Get more familiar with the extended relational algebra through Exercises 5.2.1 and 5.2.2.
Illustrate bad E/R design by Exercise 4.2.1.

16: February 23 (Monday)

Work through some examples of E/R design: Exercise 4.2.4, Exercises 4.5.1&2.
Embark on Datalog (Sections 5.3-5.4).
Assignment 3 (on paper) due tomorrow Tuesday at 4pm.

17: February 25 (Wednesday)

Gradiance HW8 (on bags and on extended relational algebra) due this morning.
Exam I.

18: February 27 (Friday)

Continue Datalog: give precise semantics (Section 5.3.4) with safety being a sufficient (but not necessary, cf. Exercise 5.3.3) condition for finiteness; discuss the proper use of negation.
Do Exercise 5.3.2(a,e,g,i) & Exercise 5.4.1(e,g)

19: March 2 (Monday)

Graded Exam 1 back; go through model solutions.
Go through model solutions for Assignment 3.
Illustrate translation from Datalog to relational algebra by doing Exercise 5.4.5(a,b).
Gradiance HW9 (on Datalog) due tomorrow morning.

20: March 4 (Wednesday)

Wrap up Datalog, by discussing recursion.
Graded Assignments 2 & 3 back.
Crash course on the basics of SQL (Sections 6.1 & 6.2).

21: March 6 (Friday)

Cover more advanced features of SQL, such as nested queries and grouping (Sections 6.3 & 6.4).

22: March 9 (Monday)

Do Exercise 6.1.4(d,e,f) and Exercise 6.2.3(a,c,e,f).
Gradiance 10 (on basic SQL) due tomorrow morning.

23: March 11 (Wednesday)

To prepare for Assignment 4, discuss general Datalog paradigms, in particular how to express "for all".
Do Exercise 6.2.3(f) using aggregates and "having", and translated it into relational algebra (cf. Exercise 6.4.9).
Do Exercise 6.4.7(b,c,d,e,f).
Gradiance 11 (on SQL with groups and aggregates) due tomorrow morning.

24: March 13 (Friday)

Cover database modification (Section 6.5).
Motivate the need for transactions being atomic and serializable, and briefly discuss how this is modeled in SQL (Section 6.6).
Now we are done with Chapter 6, we discuss what to cover in the remaining weeks.
Assignment 4 (on paper) due at 4pm.

March 16-20

Spring break.

March 23-27

Class canceled (instructor out of town)
Monday, March 23, is last day to drop the course.
Gradiance Lab project on Bookstores due the morning of Saturday, March 28.

25: March 30 (Monday)

Graded Assignment 4 back, briefly discuss model solutions.
Introduce basic notions of transactions (Section 17.1) and schedules (Sections 18.1-18.2). Do Exercise 18.2.4(a,b).
Gradiance 12 (on SQL isolation levels and on transactions preserving "consistency") due tomorrow morning.

26: April 1 (Wednesday)

Cover lock-based protocols (Sections 18.3-18.7).
Phase I of Project due at 4pm.

27: April 3 (Friday)

Cover recoverability and ACR schedules (Sections 19.1.1-19.1.4).
Cover concurrent protocols based on timestamps (Section 18.8); do Exercise 18.8.1(d) and Exercise 18.8.2(c).
Gradiance 13 (on serializability) due tomorrow morning.

28: April 6 (Monday)

Cover concurrent protocols based on validation (Section 18.9); do Exercise 18.9.1(f).
Briefly cover the handling of system failures, in particular the "undo" logging protocol (Section 17.2).
Graded Phase I of Project back.
Discuss Question 4 (on concurrency control) from last year's final exam.
Gradiance 14 (on concurrency protocols) due tomorrow morning.
Gradiance 15 (on logging and recovery) due Wednesday morning.

29: April 8 (Wednesday)

Exam II

April 10 (Friday)

Class canceled (Good Friday)

30: April 13 (Monday)

Discuss extra features of SQL: Constraints and how to enforce them (Chapter 7), doing Exercises 7.2.5(c) and 7.4.2(d).

31: April 15 (Wednesday)

Continue extra features of SQL: Views and Indexes (Chapter 8).
Do Exercise 8.5.3; sketch Exercise 8.4.2.
Gradiance 16 (on constraints and views) due Friday morning.

April 17 (Friday)

Class canceled (All-University Open House)

32: April 20 (Monday)

Graded Exam 2 back; go through model solutions.
Briefly discuss some advanced features of SQL: Authorization (Section 10.1), Recursion (Section 10.2) doing Exercise 10.2.1(b).

33: April 22 (Wednesday)

Briefly discuss other advanced features of SQL: the Object-Relational Model (Sections 10.3-5); OLAP (Section 10.6).
Briefly discuss secondary storage management (Chapter 13).
Gradiance 17 (on authorization, recursion, object-relational) due Friday morning.

34: April 24 (Friday)

Embark on Index Structures, with focus on B-trees (Section 14.2) and Hash tables (Section 14.3).

April 27 (Monday)

Class canceled (Landon Lecture at 3:30pm by Gen. David Petraeus).
Phase II of Project due at 4pm. Each team should schedule a presentation with the GTA.
Gradiance 18 (on secondary storage) due tonight.

35: April 29 (Wednesday)

Cover Linear Hashing (Section 14.3.7-14.3.8).
Cover Multi-dimensional Indexes (Sections 14.4-14.7).
Embark on Query Execution, covering one-pass algorithms (Sections 15.1-15.2).
Gradiance 19 (on B-trees and hash tables) due tonight.

36: May 1 (Friday)

Finish Query Execution, covering nested-loop joins (Section 15.3), two-pass algorithms based on sorting (Section 15.4) and hashing (Section 15.5), and index-based algorithms (Section 15.6).
Project report due at 4pm.

37: May 4 (Monday)

Gradiance 20 (on multi-dimensional indexes) due in the morning.
Embark on the Query Compiler (Chapter 16), with focus on algebraic equivalences and size estimates, covering Sections 16.1-16.4 except for 16.4.4-16.4.6.
Do Exercises 16.2.4, 16.2.5, and 16.4.1(b,e,f,h).
Project demos start.

38: May 6 (Wednesday)

Cover join size estimates (Sections 16.4.4-16.4.6), doing Exercise 16.4.1, and join-order optimization (Section 16.6), doing Exercise 16.6.1.

39: May 8 (Friday)

Gradiance 21 (on query execution) due in the morning.
Review session, looking at previous exam questions.
Gradiance 22 (on query compilation) due tonight.

May 11 (Monday)

Final exam, 4:10-6:00pm