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 32--39.
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 40--43, 48--53, 60--66.
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, 54--59.
6: January 29 (Monday)
Graded Homework 1 back.
Cover Sections 3.1-3.4, introducing the basics of SQL.
Do Exercise 3.9,a-c.
Look at Chap 3 Slides, 1--23
7: January 31 (Wednesday)
Cover Sections 3.5-3.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, 24--39
8: February 2 (Friday)
Homework 2 out.
Show how to set up and run MySQL.
Cover Section 3.8-3.9, and Section 3.10.1-3.10.3.
Do Exercise 3.15(b).
Look at Chap 3 Slides, pp. 40-55
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. 56-62.
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. 1-19.
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. 20-27, 41-46, 50-52.
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. 3-11
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 (Query-by-Example), doing Exercise 5.6(g&h).
Cover the main aspects of QBE (Sect 5.3).
Look at Chap 5 Slides, pp. 12-31.
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. 32-39, 51-52.
15: February 19 (Monday)
Continue Datalog (Sect 5.4), with focus on negation.
Do Exercises 5.12(bcdfg)
Look at Chap 5 Slides, pp. 53-63.
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. 64-73.
17: February 23 (Friday)
Homework 3 in.
Embark on the E-R model, covering Sections 6.1-6.4.
Do Exercise 6.1.
Look at Chap 6 Slides, pp. 1-27.
18: February 26 (Monday)
Homework 4 out.
Continue the E-R model, covering Sections 6.5-6.6.
Do Exercises 6.17 & 6.2.
Look at Chap 6 Slides, pp. 28-35.
19: February 28 (Wednesday)
Finish the E-R model, covering Sections 6.7-6.10.
Look at Chap 6 Slides, pp. 38-59.
Go through model solutions for Homework 3.
March 2 (Friday)
Class canceled (x-POTUS 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 dependency-preserving; decomposing into (S,A) and (S,D) is lossless but not dependency-preserving; decomposing into (S,D) and (A,D) is not lossless.
Do Exercises 7.2 & 7.9.
Look at Chap 7 Slides, pp. 1-7, 11-16.
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. 8-10, 17-24.
Go through model solutions for (the very open-ended) 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. 25-41.
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,43-56 (the schema on p.55 is already in 3NF!)
24: March 14 (Wednesday)
Introduce multi-valued 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, 57-67.
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 multi-valued 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. 67-73.
March 19-23
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. 1-14 (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. 16-29.
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, 43-47.
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. 32--36.
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 information-gain and information-gain ratio when computing the best split.
Bayesian classifiers (Sect. 18.4.2.2).
Look at Chap 18 Slides, pp. 36--41.
April 13 (Friday)
Class canceled (All-University 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 lock-based protocols (Section 16.1), including graph-based (Section 16.1.5).
Sketch a proof that the two-phase 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. 1--18.
35: April 20 (Friday)
Homework 7 in.
Continue concurrency control, covering and mentioning 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. 19--23, 32--48.
36: April 23 (Monday)
We now turn our attention to back-end issues, and cover Sections 12.1-12.4, with focus on B+ trees.
Look at Chap 12 Slides, pp. 1--40.
37: April 25 (Wednesday)
Phase II of Project in. (Prepare to give demos today or tomorrow.)
(Part of) Homework 8 out.
Cover Sections 12.5-12.9, with focus on hashing.
Do Exercises 12.7 & 12.25.
Look at Chap 12 Slides, pp. 41--72.
38: April 27 (Friday)
Graded Homework 7 back; go through model solutions.
Wrap up Chapter 16, looking at Chap 16 Slides, pp. 49--53, covering Introduction to Query Processing (Sections 13.1-13.2), doing Exercise 13.1.
Cover Section 13.3, discussing a variety of ways to implement selection.
Look at Chap 13 Slides, pp. 1--14.
39: April 30 (Monday)
All of Homework 8 out.
Finish Query Processing, covering Sections 13.4-13.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. 15--50.
Introduction to Query Optimization, covering Section 14.1, looking at Chap 14 Slides, pp. 1--5.
40: May 2 (Wednesday)
Refresh hash-join (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. 3--5, 34--41, 52--55.
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 86--89 in textbook).
Look at Chap 14 Slides, pp. 7--32, 42--46.
May 7 (Monday)
Optional review session in N122, 4:30-5:30pm.
May 9 (Wednesday)
Final exam, 4:10--6:00pm.

Torben Amtoft