Database Theory 200203
Lecturer: Dr Gavin Bierman (gmb@cl.cam.ac.uk)
Lecturer: Dr Anuj Dawar (ad260@cl.cam.ac.uk)
Taken by: Part II
The Lecture course has now finished! Please give us
feedback to help us improve the course!!
Lectures
Lecture 1 (GMB): Friday 25th April
Slides covered: 127
Errata:
 Slide 11: For the queries in this lecture, the relation schema Guide should have sort Cinema,Title,Time
 Slide 16: Second where case in semantics of cartesian product should be "R  q_2:m"
 Slide 22: Second bullet point should begin "U_1 n U_2 = ..."
 Slide 23: Replace first bullet point with "Can define generalized selection (as for SPC algebra)"
Lecture 2 (AD): Monday 28th April
Slides covered: 2845
Notation: The notation "q(I)" is the same as
" from the first lecture!
Errata:
 Slide 34: Line 1 should read "The active domain of a query q, ..."
 Slide 34: The "I" in line 6 and the last line should be calligraphic font
 Slide 40: The query in line two should have a closing "}"
Lecture 3 (AD): Wednesday 30th April
Slides covered: 4665
Errata:
 Slide 50: The existential quantifiers should be removed from the rules defining the relation A(x,y)
 Slide 53: Remove "in the database schema" from the first bullet point
Lecture 4 (AD): Friday 2nd May
Slides covered: 6681
Errata:
 Slide 71: The example program doesn't satisfy the range restriction! A simple fix is (assuming the graph is symmetric) is
T(x,y) < neg G(x,y), G(x,z), G(y,w)
T(x,y) < neg G(x,z), T(z,y), G(x,w)
 Slide 72: Third line from bottom should read "Tp(I) subset Tp(I')"
 Slide 74: Fourth line should read "For every relation R, there is an i such that all rules with R..."
 Slide 79: Definition of Formula is missing the clause "t=t" (equality of terms)
 Slide 80: The body of the while loop should read "T := T union pi(1,4,sigma(2=3,G*T))" (i.e. the subscript of the pi should be "1,4" not "1=4")
Lecture 5 (AD): Monday 5th May
Slides covered: 8297
Errata:
 Slide 95: Final part of Spoiler strategy should read "... OR j_r IN adom(J)"
 Slide 97: In the first line 4^m should read 2^(m+1)
Lecture 6 (GMB): Wednesday 7th May
Slides covered: 98118
Errata:
 Slide 109: Example 2 should read "...first component is contained in the second component."
 Slide 113: Oops! The query at the bottom is the cartesian product! The join of R and S on A=B is left for your homework!
References:
 Mackinouchi, A consideration of normal form of notnecessarilynormalized relations in the relational model. VLDB. 1977
 Jaeshcke & Schell, Remarks on the algebra on non first normal form relations. PODS, 1982.
 Thomas & Fischer, Nested relational structures. In "Advances in Computing research, vol 3". pages 269307. 1986
 Abiteboul & Bidoit, Non first normal form relations: An algebra allowing restucturing. Journal of Computer and System Sciences 33(3):361390, 1986.
Lecture 7 (GMB): Friday 9th May
Slides covered: 119154
Errata:
 Slide 132: All the attribute declarations need the keyword "attribute" at the start
 Slide 152: First bullet point should read "All DBMS manufacturers think you need this!"
References:
 Here is a (local) copy of the objectoriented database system manifesto
 Here is a (local) copy of the third generation database system manifesto
Lecture 8 (GMB): Monday 12th May
Slides covered: 155188
Errata:
 Slide 161: Oops my example isn't valid syntax! Replace "row" with "row:" on every line
 Slide 179: The intention is for you to guess what is returned by this path expression with a wildcard. (If you can't  use the galax implementation below)
The online implementation of XQuery I ran in lectures can be found
here
Examples Classes
We will hold two examples classes. There are two exercise sheets:
The classes will be as follows:
 Examples class 1  Dr Dawar: 16th May (To cover sheet 1)
 Examples class 2  Dr Bierman: 19th May (To cover sheet 2)
Lecture Notes
A 4up pdf copy of the lecture notes is available
here
Revised Syllabus
Original Syllabus
Errorspotters Hall of Fame
Thanks to Matthew Parkinson, Dominik Wee, Mark Williamson.
