• DatabaseRevision

MSc Revision Notes - Database

Useful links

SQL division

Exam topics

Main topics

• Relational algebra
• SQL DML, DDL
• Transactions

Other topics

• Host language suport (Don't need specific language details)
• Normalization
• Oracle storage structures
• Query optimization
• Triggers
• Object databases
• Distributed databases

Relational algebra

Relational operators

• UNION: A UNION B is the set of tuples belonging to A or B (or both)
• INTERSECT: A INTERSECT B is the set of tuples belonging to both A and B
• MINUS: A MINUS B is the set of tuples belonging to A but not to B
• TIMES: A TIMES B is the set of all tuples T such that T is the concatenation of a tuple belonging to A and a tuple belonging to B
• SELECTION: 'Horizontal' subset of a single operand relation. Eg, SUPPLIER WHERE CITY = 'PARIS'
• PROJECTION: 'Vertical' subset of a single operand relation. Eg, SUPPLIER[CITY]
• JOIN: A natural join. A join on each attribute found in both tables.

• DIVIDEBY: Each tuple in relation A related to all the tuples in relation B

SQL division

3 sections:

1. select [whatever] such that
2. there is no [whatever]
3. that is not [something]

So, find the name and city of each project supplied with every red part (TABLE 1 / TABLE 2) JNAME, CITY such that there are no red parts that are not supplied:

1. SELECT DISTINCT JNAME, CITY
   FROM PROJECT JOIN SUPPLY S1 ON PROJECT.J# = S1.J#  <-- TABLE 1
   WHERE NOT EXISTS
2. (SELECT * FROM PART WHERE COLOUR = 'RED'  <-- TABLE 2
    AND NOT EXISTS
3.  (SELECT * FROM SUPPLY S2
     WHERE S1.J# = S2.J#
     AND S2.P# = PART.P#))

1. SELECT attribute FROM t1 t1a WHERE NOT EXISTS

2. (SELECT * FROM t2 WHERE NOT EXISTS

3. (SELECT * FROM t1 t1b WHERE t1a.t1key = t1b.t1key AND t1b.t2key = t2.t2key))

Transactions

• To deal with the failure of an individual transaction, due to automatic or explicit ROLLBACK, the DBMS maintains a log of before image records.

• These before image records are processed in reverse to rollback a transaction.

• To deal with the failure of all current transactions because of a general system failure all uncompleted transactions are rolled back using before image records. But because database operations are not immediately written out to disk, the DBMS stores a log of after image records which contains enough information to enable a record that has been updated to be restored to its state after update.

• These after images are processed in forwards order.
• To deal with complete system failure we need backups!
• Write-ahead log protocol ensures before and after image records are written to the log file before the corresponding database record is written to the database.

Checkpointing

• To recognise which transactions need to be rolled back, at certain intervals all main memory buffers are written to disk and a checkpoint record is written to the log.
• In the event of a failure, only those transactions in progress at the time of the last checkpoint and later need to be considered.
• The procedure is as follows:
  • Start with two lists of transactions
    1. An UNDO list - transactions recorded in the last checkpoint record
    2. A REDO list - initially empty
  • Work forwards through the log from the checkpoint
    • If a log entry for starting a transaction is found, add that transaction to the UNDO list.
    • If a COMMIT log entry is found, move the committed transaction from the UNDO list to the REDO list.
  • Work backwards through the log undoing transactions in the UNDO list by restoring before images.
  • Work forwards through the log redoing transactions in the REDO list by restoring after images.

CategoryBbkRevision