Captain's Log: Database Management Systems, Spring 2007

January 12 (Friday)

Class canceled (instructor out of town)

January 15 (Monday)

University Holiday (Martin Luther King)

1: January 17 (Wednesday)

Introduction and motivation.
Go through syllabus.
Cover selected
slides from Chapter 1 in textbook.

2: January 19 (Friday)

Embark on Chapter 2, covering Sections 2.1 and 2.2 on relational algebra with fundamental operations.
We use many of the first 30
slides
from Chapter 2.

3: January 22 (Monday)

Homework 1 out.
Cover (most of) Section 2.3, introducing natural join.
Do Exercise 2.1(b), and Exercise 2.5(b,c,d).
Look at
slides 3239.

4: January 24 (Wednesday)

Introduce the division operation, thus finishing Section 2.3.
Cover
generalized projection (Sect. 2.4.1),
aggregate functions (Sect. 2.4.2),
and modification of the database (Sect. 2.6).
Do Exercise 2.5(e),
Exercise 2.11(a,b),
and Exercise 2.9(b).
Look at
slides 4043, 4853, 6066.

5: January 26 (Friday)

Homework 1 in; go through model solutions.
Cover outer joins (Sect. 2.4.3) and null values (Sect. 2.5),
thus finishing Chapter 2.
Do Exercise 2.1(c) (with and without explicit max operator),
Exercise 2.11(c),
Exercise 2.8 (with and without aggregates).
Look at
Chap 2 slides, 5459.

6: January 29 (Monday)

Graded Homework 1 back.
Cover Sections 3.13.4, introducing the basics of SQL.
Do Exercise 3.9,ac.
Look at
Chap 3 Slides, 123

7: January 31 (Wednesday)

Cover Sections 3.53.7, introducing several useful SQL constructs.
Do Exercise 3.9(d),
Exercise 3.2(g),
Exercise 3.2(c),
Exercise 3.9(e),
Exercise 3.2 (e).
Look at
Chap 3 Slides, 2439

8: February 2 (Friday)

Homework 2 out.
Show how to set up and run MySQL.
Cover Section 3.83.9, and Section 3.10.13.10.3.
Do Exercise 3.15(b).
Look at
Chap 3 Slides, pp. 4055

9: February 5 (Monday)

Finish Chapter 3, covering Section 3.10.4 and Section 3.11.
Do Exercises 3.7, 3.14, 3.21(b).
Look at
Chap 3 Slides, pp. 5662.

10: February 7 (Wednesday)

Homework 2 in.
Embark on Chapter 4 on advanced features of SQL,
covering
Sections 4.1 & 4.2.
Do Exercises 4.3(a), 4.4, 4.5.
Look at
Chap 4 Slides, pp. 119.

11: February 9 (Friday)

Finish Section 4,
covering Sections 4.3, 4.4 & 4.6.
(We skip Sections 4.5 & 4.8, and postpone Section 4.7.)
Do Exercise 4.10.
Go through model solutions for Homework 2, postponing Question 1.7.
Look at
Chap 4 Slides, pp. 2027, 4146, 5052.

12: February 12 (Monday)

Discuss Question 1.7 from Homework 2.
Embark on Chapter 5, covering the tuple relational calculus (Sect. 5.1).
Do Exercise 5.1(a,b,c), Exercise 5.11, Exercise 5.6(g).
Look at
Chap 5 Slides, pp. 311

13: February 14 (Wednesday)

Finish the tuple relational calculus (Sect. 5.1), by doing
Exercises 5.9 and 5.6(h).
Briefly cover the domain relational calculus (Sect. 5.2),
the theoretical foundation for QBE (QuerybyExample),
doing Exercise 5.6(g&h).
Cover the main aspects of QBE (Sect 5.3).
Look at
Chap 5 Slides, pp. 1231.
Graded Homework 2 back.

14: February 16 (Friday)

Homework 3 out.
Finish QBE (Section 5.3), doing Exercises 5.12(b,d,f,g,h).
Embark on Datalog (Sect 5.4).
Look at
Chap 5 Slides, pp. 3239, 5152.

15: February 19 (Monday)

Continue Datalog (Sect 5.4), with focus on negation.
Do Exercises 5.12(bcdfg)
Look at
Chap 5 Slides, pp. 5363.

16: February 21 (Wednesday)

Finish Datalog, with focus on recursion
which adds a lot of power; for recursion in SQL, see Section 4.7.
Also briefly discuss how recursion and negation interacts in Datalog.
Do Exercise 5.4(d).
Look at
Chap 5 Slides, pp. 6473.

17: February 23 (Friday)

Homework 3 in.
Embark on the ER model, covering Sections 6.16.4.
Do Exercise 6.1.
Look at
Chap 6 Slides, pp. 127.

18: February 26 (Monday)

Homework 4 out.
Continue the ER model, covering Sections 6.56.6.
Do Exercises 6.17 & 6.2.
Look at
Chap 6 Slides, pp. 2835.

19: February 28 (Wednesday)

Finish the ER model, covering Sections 6.76.10.
Look at
Chap 6 Slides, pp. 3859.
Go through model solutions for Homework 3.

March 2 (Friday)

Class canceled (xPOTUS in town)

20: March 5 (Monday)

Homework 4 in. Graded Homework 3 back.
Introduction to relational database design, covering
Section 7.1 and Section 7.3.1.
Look at relation schema r(S,A,D) where S > A and A > D:
decomposing into (S,A) and (A,D) is lossless and dependencypreserving;
decomposing into (S,A) and (S,D) is lossless but not dependencypreserving;
decomposing into (S,D) and (A,D) is not lossless.
Do Exercises 7.2 & 7.9.
Look at Chap 7 Slides, pp. 17, 1116.

21: March 7 (Wednesday)

Oracle accounts now available; see
here for how to use them.
Prove a
sufficent condition for
a decomposition to be lossless.
Finish Sections 7.2 & 7.3,
motivating and introducing various normal forms;
3NF is motivated by considering a relation with
the dependencies C > P and PH > C.
We can always decompose into BNCF, and always
decompose dependency preserving into 3NF;
but sometime we have to choose between
(i) get BNCF but not preserve dependencies,
(ii) preserve dependencies but "only" get 3NF.
Look at Chap 7 Slides, pp. 810, 1724.
Go through model solutions for (the very openended) Homework 4.

22: March 9 (Friday)

Homework 5 out.
Cover Section 7.4 on functional dependencies.
Do Exercises 7.5, 7.19 (for augmentation), 7.20, 7.22.
Illustrate the computation of canonical cover by
the example on top of p.285.
Illustrate the algorithm on p.287 (lower part), checking for dependency
preservation, on two decompositions.
Look at
Chap 7 Slides, pp. 2541.

23: March 12 (Monday)

Graded Homework 4 back.
Cover Section 7.5, decomposing into BCNF/3NF.
Do Exercises 7.25
and 7.27, decomposing the schema from Exercise 7.1 into BCNF/3NF
(though it is already in 3NF!)
Also look at decomposing ABCD wrt. dependencies A > C and B > D
(showing why one schema must contain a candidate key),
and wrt. dependencies AB > CD and A > C
(showing why one must first take the canonical cover).
Look at
Chap 7 Slides, pp. 17,20,4356 (the schema on p.55 is already in 3NF!)

24: March 14 (Wednesday)

Introduce multivalued dependencies (Sect. 7.6.1),
prove that alpha > beta implies alpha >> beta,
and show (Exercise 7.29) that >> has some surprising properties.
Introduce "The Chase".
Introduce 4NF (Section 7.6.2), and prove that 4NF implies BCNF.
Look at Chap 7 Slides, pp. 23, 5767.

25: March 16 (Friday)

Homework 5 in
(can be extended to Monday 19th, at the cost of 10 points).
Decomposition into 4NF (Section 7.6.3).
Prove that decomposing (A,B,C) into (A,B) and (B,C)
is lossless if and only if there is a multivalued dependency
B >> A.
Other normal forms (Section 7.7), including
general join dependencies.
Take a step back, looking at the big design picture (Section 7.8).
Look at Chap 7 Slides, pp. 6773.

March 1923

Spring break.

26: March 26 (Monday)

Homework 6 out.
Go through model solutions for Homework 5.
Embark on Data Analysis and Mining (Chapter 18),
covering most of Data Analysis and OLAP (Section 18.2).
Look at Chap 18 Slides, pp. 114
(mention Exercises 18.4 & 18.8).

27: March 28 (Wednesday)

Graded Homework 5 back.
Finish Data Analysis and OLAP (Section 18.2).
Cover Data Warehousing (Section 18.3).
Do Exercises 18.1 & 18.3.
Express "ranking" (even the "dense" kind), using
the "count" aggregate.
Look at Chap 18 Slides, pp. 1629.
Discuss the challenging Question 3 of HW 6.

28: March 30 (Friday)

Homework 6 in; go through model solutions.
Embark on Data Mining (Section 18.4),
covering Association Rules (Sect. 18.4.3),
with key notions of support
and confidence.
Do Exercises 18.13 & 18.15.
Look at Chap 18 Slides, pp. 30, 4347.

29: April 2 (Monday)

Midterm exam,
part I

30: April 4 (Wednesday)

Midterm exam,
part II

April 6 (Friday)

Class canceled (Good Friday)

31: April 9 (Monday)

Graded Part II of Midterm back; go through model solutions.
Graded Homework 6 back.
Continue Data Mining, covering
decision tree classifiers (Sect. 18.4.2.1),
motivated by
an example of constructing a decision
tree (taken from Maria Zamfir Bleyberg).
Look at Chap 18 Slides, pp. 3236.

32: April 11 (Wednesday)

Phase I of Project in.
Graded Part I of Midterm back; go through model solutions.
An example
on how to use the notions
of informationgain
and informationgain ratio when computing
the best split.
Bayesian classifiers (Sect. 18.4.2.2).
Look at Chap 18 Slides, pp. 3641.

April 13 (Friday)

Class canceled (AllUniversity Open House)
Homework 7 out.

33: April 16 (Monday)

Cover Chapter 15 on Transactions,
with key topics:
ACID,
(conflict) serializability,
(cascadeless) recoverability.
Look at Chap 15 Slides.

34: April 18 (Wednesday)

Embark on concurrency control,
covering lockbased protocols (Section 16.1),
including graphbased (Section 16.1.5).
Sketch a proof that the twophase locking protocol yields
only serializable schedules
(cf. Exercise 16.1).
Do Exercise 16.5; mention Exercises
16.10&15&20.
Look at Chap 16 Slides, pp. 118.

35: April 20 (Friday)

Homework 7 in.
Continue concurrency control,
covering

multiple granularity (Section 16.4)

timestampbased protocols (Section 16.2)
and mentioning

validationbased protocols (Section 16.3)

multiversion schemes (Section 16.5).
Do Exercises 16.16&24&25.
Mention Exercises 16.12&22.
Encourage looking at the
suggested solution to Exercise 16.14,
comparing the various protocols.
Look at Chap 16 Slides, pp. 1923, 3248.

36: April 23 (Monday)

We now turn our attention to backend issues, and cover
Sections 12.112.4, with focus on B+ trees.
Look at
Chap 12 Slides, pp. 140.

37: April 25 (Wednesday)

Phase II of Project in.
(Prepare to give demos today or tomorrow.)
(Part of) Homework 8 out.
Cover Sections 12.512.9, with focus on hashing.
Do Exercises 12.7 & 12.25.
Look at
Chap 12 Slides, pp. 4172.

38: April 27 (Friday)

Graded Homework 7 back; go through model solutions.
Wrap up Chapter 16, looking at
Chap 16 Slides, pp. 4953,
covering

insert and delete operations (Section 16.7),
including the phantom phenomenon

weak levels of consistency (Section 16.8).
Introduction to Query Processing (Sections 13.113.2),
doing Exercise 13.1.
Cover Section 13.3, discussing a variety of ways to implement
selection.
Look at
Chap 13 Slides, pp. 114.

39: April 30 (Monday)

All of Homework 8 out.
Finish Query Processing, covering Sections 13.413.7,
in particular discuss a variety of ways to implement
sorting (Sect. 13.4) and join (Sect. 13.5).
Look at
Chap 13 Slides, pp. 1550.
Introduction to Query Optimization, covering Section 14.1, looking at
Chap 14 Slides, pp. 15.

40: May 2 (Wednesday)

Refresh hashjoin (Section 13.5.5).
Cover Estimating Statistics (Section 14.3).
Cover Materialized Views
(Section 14.5).
Do Exercises 14.4 & 14.5.
Look at
Chap 14 Slides, pp. 35, 3441, 5255.

41: May 4 (Friday)

Homework 8 in.
Go through model solutions.
Cover Section 14.2 on Equivalent Expressions.
Cover Section 14.4 (except Section 14.4.4) on choice of evaluation plan.
Give an example (p.589)
where "perform selection early" is a bad idea.
Do Exercise 14.2(abc), some of Exercise 14.3(b)
(for part a, see pp 8689 in textbook).
Look at
Chap 14 Slides, pp. 732, 4246.

May 7 (Monday)

Optional review session in N122, 4:305:30pm.

May 9 (Wednesday)

Final exam, 4:106:00pm.
Torben Amtoft