Captain's Log: Database Management Systems, Spring 2005

January 12 (Wednesday)

Introduction to course. Syllabus handed out. Cover Chapter 1 of the textbook.
Slides (Silberschatz, pp 1-21).

January 14 (Friday)

Embark on the ER-model (Chap 2). Entity sets; Relationship sets; E-R Diagrams; Cardinality constraints; Keys; Binary vs. Ternary Relationships.
Slides (pp 3-5, 7-8, 11-13, 14-23, 24, 26-28).

January 17 (Monday)

University Holiday (Martin Luther King)

January 19 (Wednesday)

Homework 1 out.
Continue Chap 2: draw ER-diagram for car-insurance company (Exercise 2.2) and convert it to table representation; mention weak entity sets.
Slides (pp 31, 32, 34)

January 21 (Friday)

Finish Chapter 2: specialization/generalization; draw ER-diagram for university course offerings (Exercise 2.4).
Slides (pp 38,41,64-65,59,45,47-50).

January 24 (Monday)

Homework 1 in. Homework 2 out.
Start on Chapter 3, introducing the Relational Algebra.
Slides (pp 2,5-6,11,14-16,17,19,21,23,25,27,28,29-33,35,38,40).

January 26 (Wednesday)

Continue Relational Algebra (division operator, aggregate functions, outer joins, etc.)
Slides (pp 34, 39-40,42-44,46,45,49-53,55-57)

January 28 (Friday)

Graded Homework 1 back.
Finish Relational Algebra (null values, modifying the database, views).
Slides (pp 58-59,60-66,69-72)

January 31 (Monday)

Homework 2 in. Homework 3 out.
Finish Chapter 3, covering the Tuple Relational Calculus.
Exercise 3.13. Exercise 3.5 (f,h).
Slides (pp 74-82)

February 2 (Wednesday)

Embark on Chapter 4 about SQL, covering the essential language constructs.
Slides (pp 1-29)

February 4 (Friday)

Graded Homework 2 back.
Continued Chapter 4 about SQL, introducing some convenient features and also covering how to specify the format of the database.
Slides (pp 30-35,36-37,39,55-60)

February 7 (Monday)

Homework 3 in.
Accounts on Oracle are now ready. The use of SQLplus was illustrated, looking at an example of how to set up the bank database (and also set up the employee database).
Finished Chapter 4 about SQL: how to modify the database, etc.
Slides (pp 43-47,48-49,50,61-65).
Look at Exercise 4.9.

February 9 (Wednesday)

Homework 4 out.
Start on Chapter 6, covering integrity issues.
Slides (pp 2-3,4-10,11-13,14-16,17-20,22-23,25)
Look at Exercises 6.4 and 6.3.

February 11 (Friday)

Graded Homework 3 back, going through several of the exercises.
Finish Chapter 6, covering security issues.
Slides (pp 26-31,34-40,42-45)

February 14 (Monday)

Start on Section 5.2 on Datalog.
Slides (pp 36-51)

February 16 (Wednesday)

Homework 4 in. Homework 5 (including Part I of Project) out.
Finish Section 5.2 on Datalog, covering recursion.
Slides (pp 52-57,59).
Look at Exercise 5.8, (c) & (d).

February 18 (Friday)

Torben out of town (also no office hours on Feb 17); Jorge will be in class so as to answer questions about project.

February 21 (Monday)

Torben out of town; Jorge will be in class so as to answer questions about project.

February 23 (Wednesday)

Embark on Chapter 7, setting goals for good database design and introducing the crucial notion of functional dependency. A key result and its proof.
Slides (pp.1-14)

February 25 (Friday)

Homework 5 (including Phase I of Project) in. Homework 6 out.
Graded Homework 4 back, briefly going through some of the exercises.
Continue Chapter 7, elaborating on functional dependencies.
Slides (pp.15-26)

February 28 (Monday)

Continue Chapter 7, covering Boyce-Codd Normal Form (BCNF) and the decomposition into such.
We compare several ways of decomposing a relation over (A,B,C) with dependencies A -> B and B -> C: decomposing into (A,C) and (B,C) is not lossless and must therefore be avoided; decomposing into (A,B) and (A,C) is lossless but loses dependencies (to check whether an insertion respects B -> C the join has to be recomputed); decomposing into (A,B) and (B,C) is lossless and preserves all dependencies :)
Slides (pp.27-38)

March 2 (Wednesday)

Continue Chapter 7, introducing the notion of 3NF: this is weaker than BCNF, but always allows for a dependency-preserving decomposition.
Slides (pp.39-51)

March 4 (Friday)

Homework 6 in.
Homework 7 (including Phase II and III of Project) out.
Continue Chapter 7, covering multi-valued dependencies and 4NF.
Slides (pp.52-64)

March 7 (Monday)

Graded (non-project part of) Homework 5 back.
Introduce the Chase: how to optimize queries, using dependency information.
See an example of Join dependencies (generalize multi-valued dependencies).
Finish Chapter 7, using slides from book (pp.65-67,71-72).
(An extra example of the use of dependencies, taken from Maria Zamfir Bleyberg.)

March 9 (Wednesday)

Embark on Chapter 22: cover the basic notions of Online Analytical Processing (OLAP), and some SQL extensions facilitating OLAP.
Slides (pp.1-23)

March 11 (Friday)

Homework 7 (including Phase II of Project) in.
Go through Homework 6 (though not graded yet), with extra focus upon how to prove that a given decomposition is BCNF/3NF.
A lively discussion about how to solve Exercise B from Homework 7.

March 14 (Monday)

Midterm exam.
Instructor has no office hours Tuesday (Mar 15).

March 16 (Wednesday)

Take-home part of Midterm due.
Continue Chapter 22, embarking on data mining and covering pp.25-35 of the slides. Also see an example of constructing a decision tree (taken from Maria Zamfir Bleyberg), and go through examples on how to use the notion of information-gain ratio to compute the best split.

March 18 (Friday)

Graded Homework 6 back.
Almost finish Chapter 22: Bayesian classifiers, association rules, data warehousing.
Slides (pp.36-39,41-46,49,52-57)

March 21-25

Spring break.
Homework 8 (including Phase III of Project) out.
Homework 9 (including Phase IV of Project) out.

March 28 (Monday)

Briefly cover information retrieval: Slides, pp.59-78.
Introduce XML (Chapter 10). Slides (pp.1-13)

March 30 (Wednesday)

Continue XML, covering DTD, XML schema, XPath. Slides (pp.14-30)

April 1 (Friday)

Homework 8 (including Phase III of Project) in.
Homework 10 (including Phase V of Project) out.
Covering XQuery and XSLT (doing Exercises 10.5, 10.6, 10.7). Slides (pp.31-46)

April 4 (Monday)

Torben out of town this week; Jorge will be in class to discuss project etc.

April 6 (Wednesday)

Homework 9 (excluding Phase IV of Project) in.
Torben out of town this week; Jorge will be in class to discuss project etc.

April 8 (Friday)

No class (University Open House)

April 11 (Monday)

Phase IV of Project (part of Homework 9) in.
Wrap up Chap 10 on XML. Slides (pp.48-56)
As a preparation for back-end issues, we present highlights of Chapter 11 on Storage and File Structure. Slides (pp 3-4,8-10,14-16,19-22,26,29,34-36,39-40)

April 13 (Wednesday)

Homework 11 out.
After warming up by finishing Chapter 11 (pp 46-48 of slides), we started on Chapter 12: today our focus was B+-trees. Slides (pp 1-37)
Instructor has no office hours Thursday.

April 15 (Friday)

Briefly cover the solution key for the XML part of HW 9.
Almost finish Chapter 12, with focus on hashing. Slides (pp 38-65)

April 18 (Monday)

Phase V of Project (Homework 10) in.
After covering bitmaps (pp. 66-70 from Chapter 12 slides), we embark on Chapter 13 on Query Processing: today, focus is on discussing various way to process a selection operator. Slides (pp 1-18)

April 20 (Wednesday)

Finish Chapter 13, discussing various way of implementing the join operation, as well as other operations on relational algebra. Slides (pp.19-49). Do Exercise 13.13.

April 21 & April 22

Project demos (please sign up if you haven't done already!)
On April 21, Torben's office hours will be from 3:00 to 3:45pm.

April 22 (Friday)

Homework 11 in. Homework 12 out.
Start on Chapter 14 on query optimization, about size estimation etc. (pp.1-33 of slides). Do Exercise 14.8 (a & b & c).

April 25 (Monday)

Graded (in-class part of) midterm back (solution key).
Briefly cover the solution key for HW 11.
Briefly cover the solution key for (the textbook part of) HW 8.
Briefly discuss Exercise 14.9.

April 27 (Wednesday)

Finish Chapter 14 on query optimization, with focus on join ordering and on maintenance of materialized views. Slides (pp.34-48,53-62)
Start on Chapter 15 on Transactions, giving examples of how database consistency may be violated by system failure or by unrestrained concurrent execution. Slides (pp.1-5)

April 29 (Friday)

TEVAL (if you were not there, you can go to the front office and fill out the two questionnaires).
Finish Chapter 15 on Transactions, introducing the key notion of serializability: a schedule is correct if it is (conflict) equivalent to a serial schedule. Slides (pp.6-33)

May 2 (Monday)

Homework 12 in. Homework 13 out.
Embark on Chapter 16: the two-phase locking protocol, graph-based locking protocols, (start on) timestamp-based protocols. All are designed to ensure serializable (and preferably non-deadlocking, and cascade-free) schedules.
Slides (pp.1-20).
Discuss Exercises 16.13, 16.1, 16.23, 16.7, 16.6, 16.9&10.

May 4 (Wednesday)

Graded (take-home part of) midterm back (solution key).
Graded Homeworks 7 and 8 back.
Continue Chapter 16, with more protocols: finish timestamp-based, briefly cover validation-based, cover multiple-granularity locking schemes. Slides (pp.21-33). Discuss Exercise 16.26.

May 6 (Friday)

Homework 13 in (alternatively, email Jorge on Saturday before 2pm).
Graded Homeworks 9 and 11 back.
Discuss Homework 12.
Finish Chapter 16: cover multiversion schemes (slides 34-38), compare different protocols (Exercise 16.21), mention the phantom phenomenon (slides 46-52).
Highlights of Chapter 17: log-based recovery (slides 11,12,13,15,16,19), checkpoints (slide 22), need for logical undo rather than physical (slides 39-42).

May 9 (Monday)

Optional review session in N122, 4:30-5:15pm.

May 10 (Tuesday)

Final exam, 4:10-6:00pm.