Captain's Log: Database Management Systems, Spring 2012

1: January 18 (Wednesday)

• Go through syllabus.
• Introduction and motivation, giving a high-level perspective on database design. (Chapter 1 and Section 2.1).
• Present the basic relational model (Section 2.2).
• first Gradiance homework posted (in the evening).

2: January 20 (Friday)

Continue the relational model:

• how to define a schema in SQL (Section 2.3);
• the basic operators of relational algebra (Section 2.4);
• do Exercises 2.4.5, clarifying natural join versus theta-join, and 2.4.7(a,b), estimating the size of various expressions.

3: January 23 (Monday)

We practice how to express queries in the basic relational algebra, doing Exercises 2.4.4(c-i).

• for (g) we express "only one" as "at least one but not at least two".

Gradiance 1 due Tuesday night.

4: January 25 (Wednesday)

We state various types of constraints on tables (Section 2.5), and further illustrate the surprising power of basic relational algebra:

• we find the maximum displacement, by removing all displacements that are not the largest;
• we find the ships that have participated in all battles, using the quotient operator (cf. Exercise 2.4.10) which can be expressed using the basic operators (cf. online slides).

We motivate design theory, the topic of Chapter 3.

5: January 27 (Friday)

Assignment 1 (on paper) due at noon.
Introduce the notion of functional dependencies (Sections 3.1 & 3.2, except 3.2.8), doing Exercises 3.1.1 and 3.2.1.

6: January 30 (Monday)

• Cover Section 3.2.8, on the projection of FDs, doing Exercise 3.2.10(a,b).
• Cover Section 3.3, explaining "anomalies" that may occur in database design and how they are often cured by decomposing into Boyce-Codd normal form (BCNF), doing Exercise 3.3.1 (a,b).
• Prove, using "the chase", that BCNF decomposition is always lossless (Section 3.4.1).

Gradiance 2 due tomorrow night.

7: February 1 (Wednesday)

• Introduce the notion of dependency preservation (Section 3.4.4).
• Discuss the trade-off between preserving dependencies, as always done by 3NF (Section 3.5.1) and avoiding anomalies, as always done by BCNF.
• Do parts (a,b,c) in Exercises 3.4.1 & 3.4.2, illustrating how to use the chase to test for losslessness (Sects. 3.4.2-3) and dependency preservation.

Gradiance 3 due Thursday night.

8: February 3 (Friday)

• Present the 3NF synthesis algorithm (Sections 3.5.2-3), illustrated by, e.g., Exercise 3.5.2.
• Introduce multi-valued dependencies (MVD), cf. Sections 3.6.1-2.

9: February 6 (Monday)

Give back graded Assignment 1, and continue MVDs:

• State some laws (Section 3.6.3), as in Exercise 3.7.3(b).
• Introduce 4NF and show how to decompose into 4NF (Section 3.6.4-6), as illustrated by Exercise 3.6.2.

Gradiance 4 due Tuesday night.

10: February 8 (Wednesday)

Wrap up Chapter 3:

• Mention that there are even more sophisticated normal forms (very rarely used in practice though)
• Mention that a database can be badly designed even though it is normalized
• Emphasize how the chase is very useful (cf. Section 3.7) for
  • query simplification (example on K-State Online);
  • checking whether dependencies follow from other dependencies, as illustrated by Exercises 3.7.1 and 3.7.2;
  • checking whether a decomposition is depencency-preserving.

Briefly introduce E/R design (Chapter 4).
Gradiance 5 due Thursday night.

11: February 10 (Friday)

• Cover the basic concepts of E/R design (Sections 4.1-3 except 4.1.11, and Sections 4.5.1-3)
• Do Exercises 4.1.1, 4.1.2(-d), 4.1.3, 4.1.5.

12: February 13 (Monday)

• Continue E/R design, introducing subclasses (Section 4.1.11), weak entity sets (Section 4.4), and their translations (Sections 4.6 & 4.5.4).
• Do Exercises 4.1.5 (wrap up), 4.4.4(a), 4.4.1&2, 4.5.1&2.

Gradiance 6 due Tuesday night.

13: February 15 (Wednesday)

• Introduce the notion of bags (Section 5.1), illustrated by Exercises 5.1.4 and 5.1.5.
• Extend the relational algebra (Section 5.2).

Gradiance 7 due Thursday night.

14: February 17 (Friday)

Assignment 2 (on paper) due at noon.

• Illustrate the extended relational algebra by Exercises 5.2.1 and 5.2.2.
• Discuss last year's Exam 1, Question 1.

15: February 20 (Monday)

• Discuss Assignment 2, just graded.
• Discuss Assignment 3, handed in at noon.
• Discuss last year's Exam 1, Question 2.
• Briefly discuss Exam 1 from 2010.

Gradiance 8 due tonight

16: February 22 (Wednesday)

Exam I.

17: February 24 (Friday)

Introduce Datalog (Sections 5.3-5.4):

• illustrate basic programming techniques, by Exercise 5.3.2 (c,e,i).
• present a 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, illustrated by Exercise 5.3.2(g).

18: February 27 (Monday)

Wrap up Datalog:

• show how to use double negation to encode "for all".
• mention the use of recursion.
• compare to Prolog.

Embark on SQL (Chapter 6):

• present the basic query structure

Gradiance 9 due tomorrow night.

19: February 29 (Wednesday)

We present numerous features of SQL, including subqueries, covering much of Sections 6.1-6.4.

20: March 2 (Friday)

• We show how to express groups and aggregates in SQL; we have now covered Sections 6.1-6.4.
• Do various exercises, sometimes presenting multiple solutions: 6.1.4(d,e,f); 6.2.3(a,c,e).

21: March 5 (Monday)

Assignment 4 (on paper) due at noon.

• Graded Exam 1 handed back and discussed.
• Do more exercises on SQL: 6.2.3(f), 6.3.2(a,b,e),

Gradiance 10 due tomorrow (Tuesday) night.

22: March 7 (Wednesday)

Finish SQL:

• Cover Database modification (Section 6.5).
• Do a few more exercises: 6.4.7(b,c,e,f), 6.4.9, 6.5.2(a,c,d,e).

Gradiance 11 due tomorrow (Thursday) night.

23: March 9 (Friday)

Cover basic notions of

• Transactions (Section 17.1)
• Schedules and serializability (Sections 18.1-18.2), doing Exercise 18.2.4(a,c)

24: March 12 (Monday)

Finish Transactions:

• recall serializability, cf. Exercise 18.2.5
• Recoverability and ACR schedules (Section 19.1.1-19.1.4). doing some of Exercise 19.1.4
• SQL isolation levels (Section 6.6).

Embark on Concurrency Control:

• Two-Phase Locking (Section 18.3), doing Exercise 18.3.3 (a)
• Extensions of Two-Phase Locking (Section 18.4)

Gradiance Lab project (on Presidents) due tonight.

25: March 14 (Wednesday)

Advanced Lock-based protocols:

• Increment locks (Section 18.4.5)
• Multiple granularity (Section 18.6), illustrated by Exercise 18.6.1(a)
• Tree lock protocol (Section 18.7), illustrated by Exercise 18.7.2 (without the counting!)

Gradiance 12 due tonight.

26: March 16 (Friday)

Graded Assignment 4 given back.
Project out.

• Concurrent protocols based on timestamps (Section 18.8), illustrated by Exercises 18.8.1(c,d)
• Concurrent protocols based on validation (Section 18.9) illustrated by Exercise 18.9.1(f).

Gradiance 13 due tonight.

March 19-23

Spring break.

March 26 (Monday)

Class canceled (instructor out of town)

March 28 (Wednesday)

Class canceled (instructor out of town)
Gradiance 14 due tonight.

March 30 (Friday)

Class canceled (instructor out of town)

27: April 2 (Monday)

Wrap up transaction management:

• Show that the two-phase locking and timestamp protocols are incompatible, and that also the latter may give rise to deadlocks (Exercise 18.8.3)
• Briefly cover the handling of system failures, in particular the "undo" logging protocol (Section 17.2).

Embark on some extra/advanced features of SQL (selected from Chapters 7-10):

• Constraints and how to enforce them (Sections 7.1-7.4), doing Exercise 7.2.5(c).

28: April 4 (Wednesday)

Continue extra/advanced features of SQL:

• Exercise 7.4.2(d), illustrating assertions versus tuple-based checks
• Triggers (Section 7.5), illustrated by Exercise 7.5.3(e)
• Views and their modifications (Sections 8.1-2)
• Materialized Views (Section 8.5), doing Exercise 8.5.3

29: April 6 (Friday)

Phase 1 of Project due at noon.

• Authorization (Section 10.1), doing Exercise 10.1.2.
• Recursion (Section 10.2), doing Exercise 10.2.1(b).
• A brief summary of secondary storage management (Chapter 13).

30: April 9 (Monday)

• Discuss exam sets from 2010 and 2011.
• Introduction to index structures (Sections 8.3 & 8.4, and 14.1), doing Exercise 14.1.1.

Gradiance 15 due tonight.
Gradiance 16 due tomorrow night.

31: April 11 (Wednesday)

Exam II.

32: April 13 (Friday)

After the motivating Exercise 8.4.2, introduce various index structures:

• B-trees (Section 14.2)
• Hash tables (Section 14.3.1-4)

33: April 16 (Monday)

Continue Index structures:

• Extensible and Linear Hash tables (Sections 14.3.5-8)
• Multi-dimensional Indexes (Sections 14.4-14.7), including
  grid files (Section 14.5.1-4 and illustrated by Exercise 14.5.5),
  partititioned hash functions (Section 14.5.5-6),
  tree structures (Section 14.6), and
  bitmaps (Section 14.7).

Hand back graded Phase I of Project.

34: April 18 (Wednesday)

Graded Exam 2 handed back and discussed.
Embark on Query Execution (Chapter 15):

• One-pass algorithms (Section 15.2)
• Nested-loop joins (Section 15.3)

Gradiance 17 due tomorrow night.

April 20 (Friday)

Class canceled (All-University Open House)

35: April 23 (Monday)

Finish Query Execution:

• two-pass algorithms based on sorting (Section 15.4)
• two-pass algorithms based on hashing (Section 15.5)
• index-based algorithms (Section 15.6), doing Exercises 15.6.1(b) and 15.6.2.

Gradiance 18 due tonight.

36: April 25 (Wednesday)

Embark on the Query Compiler (Chapter 16), with focus on

• algebraic equivalences (Section 16.2)
• the elimination of subqueries (Section 16.3.2)
• size estimates (Section 16.4), illustrated by Exercises 16.4.1(a,b,d,e,f,h,i) and 16.5.1.

Gradiance 19 due tonight.

37: April 27 (Friday)

Finish the Query Compiler:

• focus on join-order optimization (Section 16.6);
• illustrate by several exercises: 16.4.2, 16.6.1, 16.6.2.

Phase 2 of Project due at 4pm. Each team should schedule a presentation with the GTA.

38: April 30 (Monday)

Instructor out of town.
Project demos with TA.

39: May 2 (Wednesday)

Instructor out of town.
Project demos with TA.
Gradiance 20 due tonight.

40: May 4 (Friday)

Review session, going through previous exam sets.
Gradiance 21 due Monday night.

May 8 (Tuesday)

Final exam, 4:10-6:00pm