Solutions for HW 5 - Spring 2006

1 [20pts] ER to Relational
---------------------------

CREATE TABLE Authors(
Aname VARCHAR,
AAddr VARCHAR,
PRIMARY KEY (Aname)
)

CREATE TABLE Publishers(
Pname VARCHAR,
PAddr VARCHAR,
PRIMARY KEY (Pname)

CREATE TABLE Books(
ISBN VARCHAR,
Title VARCHAR, 
Year  INT,
PName	VARCHAR NOT NULL,
PRIMARY KEY (ISBN)
FOREIGN KEY (PName) REFERENCES Publishers)
	
CREATE TABLE WrittenBy(
AName VARCHAR,
ISBN VARCHAR,
PRIMARY KEY (AName, ISBN),
FOREIGN KEY (AName) REFERENCES Authors,
FOREIGN KEY (ISBN) REFERENCES Books)
	
Note, the participation constraint that books must have an
entry in WrittenBy is not easily implemented.  Posible solutions
are to use an "assertion" or a "check" constraint.  If you just mentioned
the difficulty of this, you got full points.

Note that only four tables are needed, as the "Published_by" relationship can
be embbeded in the "Books" table due to the one-to-many constraint.

Note that for grading purposes, the data types don't really matter, as long
as they are reasonable.

2) Candidate Keys [10 pts]
--------------------------

CF and ABF 

3) Functional Dependencies [10 points]
--------------------------------------

1) AB->C given
2) AB->BC augmentation of (1) with B
3) BC->D given
4) AB->D transtivity of (2) and (3)
5) D->E given
6) AB->E transitivity of (4) and (5)

(there are other correct ways to get it, too).

4) BCNF [10 Points]
-------------------

R is not in BCNF.  Any one of AB->C, BC->A, BC->D, D->E is sufficient to show this
as none of those left-hand sides are keys, and none of them are trivial.

Decompose into: ABC  ABDF  and DE

You get this by first decomposing into ABC and ABDEF (lossless since AB is a key for ABC)
Then decomposing ABDEF into ABDF and DE (lossless since D is a key for DE).

(there are likely other correct decompositions as well, but you need at least three relations)

5) Concurrency Control [20 pts]
-------------------------------

Yes, it is conflict serializable (no cycles in the dependency graph), and is equivalent to the 
order: T1, T3, T4, T2

6) Recovery - Analysis [10 pts]
--------------------------------
a) All records since last checkpoint, which means all the shown entries, are read.
b)
Transaction Table
Trans       |   Last LSN        | stat
T3          |   70              |  running
T2          |   80              |  aborting

Dirty Page Table
PageID      |   recLSN
P1          |   10
P3          |   20
P4          |   40
P2          |   70


7) Recovery - Redo [10 points]
------------------------------
a) Since the smallest recLSN is 10, REDO starts there.
b) All pages in the dirty page table: P1, P3, P4, P2 are read from disk.
c)
Assuming no updates made it out to disk, all updates are redone, so:
10, 20, 40, 50, and 70



8) Recovery - Undo [10 points]
--------------------------------

a) starting from 80 and 70, we will read: 80, 70, 50, 40, and 20
b) undone operations will be: 70, 50, 40, and 20
c) New log records are (LSNs aren't important except that they must be increasing):

90  CLR T3 LSN = 70; undoNextLSN = 40
100 CLR T2 LSN = 50; undoNextLSN = 20
110 CLR T3 LSN = 40; undoNextLSN = null
120 T3 end
130 CLR T2 LSN = 20; undoNextLSN = null
140 T2 end