Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Computer Laboratory > Course material 2003-04 > Databases


Principal lecturer: Dr Gavin Bierman
Taken by: Part IB, Part II (General), Diploma

Past exam questions


Lecture 1: Friday 23rd April

Material covered: Pages 1-1 to 1-4

This was a general introduction lecture. The big ideas were the three level architecture and data independence.

Here are some links to various database systems - please have a play with one or more of these!

Lecture 2: Monday 26th April

Material covered: Pages 2-1 to 2-5

Today we covered E/R modelling, which is a diagrammatic technique for modelling enterprise data, and for conceptual design of database applications.

Typo! The relationship Sponsors on slides 25 and 27 should be a many:many, not a many:one relationship!

Here is a simple exercise in E/R modelling for you to have a crack at: why not cover this in your first supervision?

  • Oracle 9i Developer - This is the demo I ran in the lecture of Oracle's 9iDeveloper tool.
  • ERWin - This is a very popular ER modelling tool from Computer Associates.
  • PowerDesigner - This is another modelling tool from Sybase.

Lecture 3: Wednesday 28th April

Material covered: Pages 3-1 to 3-5

Today we looked at the basics of the relational model of data. This simple idea forms the heart of modern DBMSs. We also looked at simple features of SQL: creating tables, inserting and deleting data, and posing simple queries.

Here are some links and papers:

  • Here is a (local) copy of Codd's original paper proposing the relational data model from 1970! (Here is an HTML version) [Paper (c) ACM]
  • Here is lots of information about IBM's System R
  • Here is a (local) copy of the paper describing query optimization inside System R. (This technology is still used today!) [Paper (c) ACM]

Lecture 4: Friday 30th April

Material covered: Pages 4-1 to 4-5

Today we looked the relational algebra, which is an elementary query language for the relational model. We looked at the core operators, what they do, how they are "typed", and we finished by noticing that some queries were not expressible in the relational algebra (hence we concluded it is not Turing-complete).

Some people would like a new XP desktop

Typo! On slide 23 the thought-bubble should hang off the last sentence, not solution 2 (in fact solution 1 is probably more efficient). Sorry

Lecture 5: Monday 3rd May

Material covered: Pages 5-1 to 5-4

Today we looked at the relational calculus, which is another query language for the relational model. In contrast to the relational algebra it's a declarative language. We also considered the question of equivalence between the relational algebra and calculus.

Eek! One thing wasn't clear in this lecture: In the query on slide 13 the variable S ranges over all the attributes of the relation Sailors. However in the query on slide 15, the result is a set of pairs of (sname,age). Look at the body of this query - that's all that's stated about P!

Lecture 6: Wednesday 5th May

Material covered: Pages 6-1 to 6-5

Today we looked at some more SQL and wrote some more subtle queries. We saw that SQL has lots of nice features like string matching, arithmetic, ranges (and lots more that wasn't shown!). We also saw that SQL allows you to specify lots of nice integrity constraints, e.g. primary keys, candidate keys, foreign keys, semantic integrity constraints, ... The neat thing is that SQL enforces these for you automatically when you touch the relations!

Lecture 6: Friday 7th May

Material covered: Pages 7-1 to 7-5

Today we started the process of considering whether our database design was a good one. We identified an important semantic concept: functional dependency. This will be the key concept for us to decide if a design is good or not (next lecture). However, for now we looked at some of the theory of functional dependencies.

Clarification: I use two turnstiles in the notes |- and |=. The first denotes logical implication, i.e. F |- X->Y means that I can deduce that X->Y given an FD set F. The second means deducible from Armstrong axioms i.e. F |= X -> Y iff it is deducible from reflexivity, augmentation and transitivity rules and the obvious identity rule.

The cool thing is that the two relations are equivalent! (That's the soundness and completeness results on slide 20.)

Example: Is it the case that given an FD set F={a -> b, a -> c} that a -> b,c? The answer's yes, let's use Armstrong's rules:

F |= a -> b	{Assn}			F |= a -> c	{Assn}		
----------------------			----------------------
F |= a,a -> a,b  {Aug}			F |= a,b -> b,c  {Aug}
F |= a -> b,c 	{Trans}

Lecture 8: Monday 10th May

Material covered: Pages 8-1 to 8-4

Today we looked at decomposing relations - this process is often refered to as normalization. First we defined what a decomposition is and then identified those that are said to be lossless-join decompositions. Clearly these are the only ones we're interested in.

Another class were dependency-preserving. This is a desirable property but not essential.

We also looked at two so-called normal forms for relations: Boyce-Codd normal form and third normal form. These are forms that real-world DBAs aim for. (There are other normal forms, but they are hard to acheive.)

We like muffins!

Lecture 9: Wednesday 12th May

Material covered: Pages 9-1 to 9-5

Today we looked at some of the more advanced features of SQL, including ORDER BY, GROUP BY, aggregation, NULLs, various JOINS and views. We looked at these in mysql. We also considered how we might extend the relational algebra so it is capable of representing these sorts of operations.

Chris Date published this critique of SQL in 1984.

Clarification On slide 17, the final bullet point is better written : Result is the relation consisting of one tuple for each group. The components of that tuple are the values associated with each element of L for that group

Here are some concrete examples of full outer, left outer and right outer joins.

Lecture 10: Friday 14th May

Material covered: Pages 10-1 to 10-5

Today we considered some of the technicalities of supporting concurrent users in a database system. We looked at transactions, the problems of interleaving transactions, and a beautiful protocol (strict two-phase locking) for ensuring that we only generate serialised schedules.

(The Dip/2G-ers were wowed by this new material; the Ib-ers were amazed by Dr Bierman's ability to summarize the interesting bits of 24 hours of CSA lectures into 50 minutes :-))

Jim Gray, now at Microsoft, won the Turing award for his work on transactions in database systems.

Lecture 11: Monday 16th May

Material covered: Pages 11-1 to 11-6

Today we considered various extensions to the relational model:

  1. First we considered relaxing the restriction of first normal form. We allowed relations as values - yielding the NF2/not 1NF/nested relational model. We looked at two new operators for the corresponding algebra - NEST and UNNEST
  2. Second we looked at the revolutionary approach to making databases object-oriented: the object database system. We looked at the ODMG proposal - the standard for such systems.
  3. Third we looked at the evolutionary approach to making databases object-o\ riented: the object-relational database system. (This is the route taken by all major vendors.) We looked briefly at SQL:1999 which is the standard proposal for O/R database system.

Some references you may wish to check out:

Lecture 12: Wednesday 18th May

Material covered: Pages 12-1 to 12-6

Today we wiped away a tear as the course came to a triumphant end by considering one of the hot areas in databases: semi-structured data, i.e. XML! We first looked at XML, and then XPATH/XQuery - the W3C query languages for XML.

Some useful links:


  • Slide 7 - XML stands for Extensible Markup language :-)
  • Slide 31 refers to an XQuery algebra - this is now called core XQuery


  • Date, C.J. (2003). An Introduction to Database Systems. Addison Wesley (8th ed.).
  • Elmasri, R. & Navathe, S.B. (2003). Fundamentals of Database Systems. Addison Wesley (4th ed.).
  • Silberschatz, A., Korth, H.F. & Sudarshan, S. (2002). Database System Concepts. McGraw Hill (4th ed.).
  • Ullman, J. & Widom, J. (1997). A First course in Database Systems. Prentice Hall.
  • Stonebraker, M. & Brown, P. (1999). Object-Relational DBMSs. Morgan Kaufmann (2nd ed.).
  • Cattell, R., Barry, D. et al. (2000). The Object Database Standard ODMG: 3.0. Morgan Kaufmann.

Prize answers

Here are answers to the prize questions in the notes (in .ps format).

Error-spotters Hall of Fame

Simon Chan, Rahul Vohra, David Waller, Gareth Williams.