Captain's Log: Database Management Systems, Spring 2012

1: January 18 (Wednesday)


Go through syllabus.

Introduction and motivation,
giving a highlevel 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 thetajoin,
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(ci).

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 BoyceCodd 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 tradeoff 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.23) and dependency preservation.
Gradiance 3 due Thursday night.

8: February 3 (Friday)


Present the 3NF synthesis algorithm (Sections 3.5.23),
illustrated by, e.g.,
Exercise 3.5.2.

Introduce multivalued dependencies (MVD), cf. Sections 3.6.12.

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.46),
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 KState Online);

checking whether dependencies follow from other dependencies,
as illustrated by Exercises 3.7.1 and 3.7.2;

checking whether a decomposition is depencencypreserving.
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.13 except 4.1.11,
and Sections 4.5.13)

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.35.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.16.4.

20: March 2 (Friday)


We show how to express groups and aggregates in SQL;
we have now covered Sections 6.16.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.118.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.119.1.4).
doing some of Exercise 19.1.4
 SQL isolation levels (Section 6.6).
Embark on Concurrency Control:
 TwoPhase Locking (Section 18.3),
doing Exercise 18.3.3 (a)
 Extensions of TwoPhase Locking (Section 18.4)
Gradiance Lab project (on Presidents) due tonight.

25: March 14 (Wednesday)

Advanced Lockbased 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 1923

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 twophase 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 710):

Constraints and how to enforce them (Sections 7.17.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 tuplebased checks

Triggers (Section 7.5), illustrated by Exercise 7.5.3(e)

Views and their modifications (Sections 8.12)

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:

Btrees (Section 14.2)

Hash tables (Section 14.3.14)

33: April 16 (Monday)

Continue Index structures:

Extensible and Linear Hash tables (Sections 14.3.58)

Multidimensional Indexes (Sections 14.414.7),
including
grid files
(Section 14.5.14 and illustrated by Exercise 14.5.5),
partititioned hash functions (Section 14.5.56),
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):

Onepass algorithms (Section 15.2)

Nestedloop joins (Section 15.3)
Gradiance 17 due tomorrow night.

April 20 (Friday)

Class canceled (AllUniversity Open House)

35: April 23 (Monday)

Finish Query Execution:

twopass algorithms
based on sorting (Section 15.4)

twopass algorithms based on hashing (Section 15.5)

indexbased 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 joinorder 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:106:00pm
Torben Amtoft