Database Theory 2002-03
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: 1-27
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: 28-45
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: 46-65
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: 66-81
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: 82-97
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: 98-118
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 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
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 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
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 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.
|