Captain's Log: Database Management Systems, Spring 2011

1: January 19 (Wednesday)

Go through syllabus.
Introduction and motivation, giving a high-level perspective on database design. (Chapter 1 and Section 2.1).

2: January 21 (Friday)

Embark on the relational model:

• the basics (Section 2.2);
• how to define a schema in SQL (Section 2.3);
• the basic operators of relational algebra (Section 2.4);
• various types of constraints on tables (Section 2.5).

First Gradiance homework out.

3: January 24 (Monday)

We look more into the basic relational algebra:

• we do Exercises 2.4.5 (clarifying natural join versus theta-join) and 2.4.7 (estimating size of various expressions).
• we solve various queries: Exercise 2.4.4(c,d,e,f,g); for (g) we express "only one" as "at least one but not at least two".

Gradiance 1 due Tuesday night.

4: January 26 (Wednesday)

We do Exercise 2.4.4(h,i), as well as some more exercises that 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).

5: January 28 (Friday)

• Paper assignment 1 due at 1pm.

Start on Chapter 3 on how to design relational databases:

• we introduce the notion of functional dependencies,
  • covering Sections 3.1 & 3.2 except 3.2.8,
  • and doing Exercises 3.1.1; 3.2.1; 3.2.4.

January 31 (Monday)

University closed due to inclement weather.

February 2 (Wednesday)

Class canceled due to road/sidewalk conditions.

6: February 4 (Friday)

• Finish Section 3.2, on how to project functional dependencies onto a subset of attributes. Do 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). Do Exercise 3.3.1 (a,b).

Gradiance 2 due tomorrow night.

7: February 7 (Monday)

Cover Sections 3.4&3.5.1, with focus on goals for normalization:

• decomposition must always be lossless (which can be verified by "the chase");
• discuss the trade-off between preserving dependencies, as always done by 3NF, and avoiding anomalies, as always done by BCNF.

We do Exercise 3.4.1(a,b) and Exercise 3.4.2(b,c,d).
Graded paper Assignment 1 back.

8: February 9 (Wednesday)

• Present the 3NF synthesis algorithm, cf. Section 3.5.2-3, and do Exercise 3.5.2.
• Introduce multi-valued dependencies (MVD), cf. Section 3.6.1-3, and state some laws.

Gradiance 3 due tomorrow night.

9: February 11 (Friday)

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

10: February 14 (Monday)

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
  • checking whether dependencies follow from other dependencies
  • checking whether a decomposition is depencency-preserving

Gradiance 4 (on MVDs) due tomorrow night.

11: February 16 (Wednesday)

Embark on E/R design (Sections 4.1-6), covering the basic concepts, and doing Exercises 4.1.1, 4.1.2(-d), 4.1.3, 4.1.5.

12: February 18 (Friday)

• Continue E/R design, introducing weak entity sets (Section 4.4), subclasses (Section 4.1.11), and their translations (Sections 4.5-4.6).
• Do Exercises 4.1.5 (wrap up), 4.4.4, 4.5.1, 4.5.2, 4.1.6, 4.1.7.

Gradiance 5 (on simple E/R design) due tonight.

13: February 21 (Monday)

• One more example of query simplification by the chase.
• Introduce the notion of bags (Section 5.1), illustrated by Exercises 5.1.4 and 5.1.5.

14: February 23 (Wednesday)

• Recall the basic relational algebra, by briefly going through model solutions for Assignment 1.
• Extend the relational algebra (Section 5.2), illustrated by Exercises 5.2.1 and 5.2.2.

Paper assignment 2 due at 4pm.
Gradiance 6 (on advanced E/R design) due tonight.

15: February 25 (Friday)

• Go through model solutions for Assignment 2 (handed back today and Monday).
• Go through last year's Exam 1, Question 1.

16: February 28 (Monday)

• Go through last year's Exam 1, Question 2.
• Look at Exam 1 from 2009.
• Brief appetizer to Datalog (Sections 5.3-5.4).

Gradiance 7 (on bags and extended relational algebra) due tonight.
Paper assignment 3 due tomorrow at 4pm.

17: March 2 (Wednesday)

Exam I.

18: March 4 (Friday)

Continue 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).
• show how to use double negation to encode "for all".

19: March 7 (Monday)

Wrap up Datalog:

• Illustrate translation from Datalog to relational algebra by doing Exercise 5.4.5(a,b).
• mention the use of recursion.
• compare to Prolog.

Graded Assignment 3

• handed back
• solutions discussed

Start on SQL (Chapter 6):

• present the basic query structure

Gradiance 8 (on Datalog) due tomorrow night.

20: March 9 (Wednesday)

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

21: March 11 (Friday)

• We show how to express groups and aggregates in SQL; we have now covered Sections 6.1-6.4.
• Do Exercises 6.1.4(d,e,f), 6.2.3(a,c,e,f), and 6.3.2 (a).

22: March 14 (Monday)

• Do various exercises on SQL: 6.3.2(b,e), 6.4.7(b,c,d,e,f), 6.4.9, 6.3.6.
• Paper assignment 4 due at 4pm.
• Gradiance 9 (on SQL) due tonight.

23: March 16 (Wednesday)

Cover some extra/advanced features of SQL:

• Database modification (Section 6.5), doing Exercise 6.5.2(a,c,d,e).
• Constraints and how to enforce them (Chapter 7)

Gradiance 10 (more SQL) due tonight.

24: March 18 (Friday)

• Graded Assignment 4 handed back; go through model solutions.
• Exercises for constraints and triggers (Chapter 7): 7.2.5(c); 7.4.2(d); 7.5.3(e).
• Views and their modifications (Sections 8.1-2).

Gradiance Lab project (on Bookstore) due tonight.

March 21-25

Spring break.

25: March 28 (Monday)

Cover more extra/advanced features of SQL:

• Materialized Views (Section 8.5), doing Exercise 8.5.3.
• Authorization (Section 10.1), doing Exercises 10.1.2 and 10.1.3.
• Recursion (Section 10.2), doing Exercise 10.2.1(b).

Graded Exam I back.

26: March 30 (Wednesday)

Cover basic notions of

• transactions (Section 17.1), and
• schedules and serializability (Sections 18.1-18.2), doing Exercises 18.2.4(a,c) & 18.2.5.

Gradiance 11 (misc SQL) due tomorrow night.

27: April 1 (Friday)

Project out.

• Recoverability and ACR schedules (Section 19.1.1-19.1.4), doing some of Exercise 19.1.4
• SQL isolation levels (Section 6.6)
• Basics of Lock-based protocols (Sections 18.3-18.4.4), doing Exercise 18.3.3 (a,c)

28: April 4 (Monday)

Advanced Lock-based protocols:

• Increment locks (Section 18.4.5), illustrated by Exercise 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 (serializability) due tonight.

29: April 6 (Wednesday)

• Concurrent protocols based on timestamps (Section 18.8), illustrated by Exercises 18.8.1(c,d) and 18.8.3.

Gradiance 13 (properties of schedules) due tomorrow night.

30: April 8 (Friday)

• Concurrent protocols based on validation (Section 18.9), illustrated by Exercise 18.9.1(f).
• Briefly cover the handling of system failures, in particular the "undo" logging protocol (Section 17.2).
• Start a brief summary of secondary storage management (Chapter 13).

31: April 11 (Monday)

Phase 1 of project due at noon.

• Finish a brief summary of secondary storage management (Chapter 13).
• Introduction to index structures (Sections 8.3 & 8.4, and 14.1), sketching Exercises 14.1.1 and 8.4.2.

Gradiance 14 (concurrency protocols) due tomorrow night.

32: April 13 (Wednesday)

Exam II

April 15 (Friday)

Class canceled (All-University Open House)

33: April 18 (Monday)

• B-trees (Section 14.2)
• Hash tables (Section 14.3)
• Start on Multi-dimensional Indexes (Sections 14.4-14.7):
  • cover grid files (Section 14.5.1-4) as illustrated by Exercise 14.5.5

34: April 20 (Wednesday)

Finish Multi-dimensional Indexes (Sections 14.4-14.7):

• Partititioned hash functions (Section 14.5.5-6)
• Tree structures (Section 14.6)
• Bitmaps (Section 14.7)

Embark on Query Execution (Chapter 15):

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

Gradiance 15 (logging and disks) due tomorrow night.

April 22 (Friday)

Class canceled (Good Friday)

35: April 25 (Monday)

Continue Query Execution:

• two-pass algorithms based on sorting (Section 15.4)
• two-pass algorithms based on hashing (Section 15.5)

Graded Exam 2 back.
Gradiance 16 (B-trees and hash indices) due tonight.

36: April 27 (Wednesday)

Finish Query Execution:

• index-based algorithms (Section 15.6), doing Exercises 15.6.1(b) and 15.6.2.

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

• the elimination of subqueries (Section 16.3.2);
• algebraic equivalences (Section 16.2), doing Exercises 16.2.4 and 16.2.8(a).

Gradiance 17 (on multidimensional indexes) due tonight.

37: April 29 (Friday)

Continue the Query Compiler, with focus on

• size estimates (Section 16.4), illustrated by Exercises 16.4.1(a,b,d,e,f,h,i) and 16.5.1.

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

38: May 2 (Monday)

Finish the Query Compiler:

• focus on join-order optimization (Section 16.6);
• illustrate by Exercises 16.4.2, 16.6.1, 16.6.2 and 16.7.1.

Gradiance 18 (on query execution) due tomorrow night.

39: May 4 (Wednesday)

Embark on Data Mining:

• On-Line Analytic Processing (OLAP, Sections 10.6-7).
• frequent itemsets (Section 22.1) and how to compute them (Section 22.2), illustrated by Exercises 22.1.1 and 22.2.1.
• Jaccard similarity (Section 22.3), illustrated by Exercise 22.3.3.

40: May 6 (Friday)

• the notion of PageRank for web pages (Sections 23.1-3), illustrated by Exercises 23.2.1 and 23.2.3(ii).
• Brief review session, looking at the final exam from S'09.

Gradiance 19 (on query optimization) due tonight.

May 10 (Tuesday)

Gradiance 20 (on data mining) due tonight.

May 12 (Thursday)

Final exam, 11:50am-1:40pm