Computer LaboratoryDatabase Theory

# Database Theory2002-03

Lecturer: Dr Gavin Bierman (gmb@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

## Error-spotters Hall of Fame

Thanks to Matthew Parkinson, Dominik Wee, Mark Williamson.

 © 2003 University of Cambridge Computer Laboratory Please send any comments to pagemaster@cl.cam.ac.uk Page last updated on 19-May-2003 at 11:57 by Gavin Bierman