Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Database Theory
Computer Laboratory > Course material 2002-03 > Database Theory

Database Theory

Lecturer: Dr Gavin Bierman (
Lecturer: Dr Anuj Dawar (
Taken by: Part II

The Lecture course has now finished! Please give us feedback to help us improve the course!!


Lecture 1 (GMB): Friday 25th April

Slides covered: 1-27


  • 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: 28-45

Notation: The notation "q(I)" is the same as $[\!\vert q \vert\!]_{\cal I}$ " from the first lecture!


  • 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: 46-65


  • 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: 66-81


  • 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: 82-97


  • 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: 98-118


  • 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!


  • Mackinouchi, A consideration of normal form of not-necessarily-normalized 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 269-307. 1986
  • Abiteboul & Bidoit, Non first normal form relations: An algebra allowing restucturing. Journal of Computer and System Sciences 33(3):361-390, 1986.

Lecture 7 (GMB): Friday 9th May

Slides covered: 119-154


  • 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!"


  • Here is a (local) copy of the object-oriented database system manifesto
  • Here is a (local) copy of the third generation database system manifesto

Lecture 8 (GMB): Monday 12th May

Slides covered: 155-188


  • 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 on-line 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 4-up pdf copy of the lecture notes is available here

Revised Syllabus
Original Syllabus

Error-spotters Hall of Fame

Thanks to Matthew Parkinson, Dominik Wee, Mark Williamson.