Solutions to Spring 1997 Final Exam

Problem 1

(a) Here is an E/R diagram in postscript

The following error codes were used:

(b) 
Cities(name, pop, state)
States(name, pop)
Counties(name, pop, state)
CityCounty(cityName, countyName, state)
Capital(city, state)

Error Codes:

(c) 
interface State (key name) {
    attribute string name;
    attribute int pop;
    relationship Set<City> citiesIn inverse City::inState;
    relationship Set<County> countiesIn inverse County::inState;
    relationship City capital inverse City::isCapitalOf;
}

interface City {
    attribute string name;
    attribute int pop;
    relationship State inState inverse State::countiesIn;
    relationship State isCapitalOf inverse State::capital;
    relationship Set<County> inCounty inverse County::citiesIn;
}

interface County {
    attribute string name;
    attribute int pop;
    relationship State inState inverse State::countiesIn;
    relationship Set<City> citiesIn inverse City::inCounty;
}


Some error codes:




(d)


State(name, pop, capital)
City(name, pop, county, state)
County(name, pop, state)




Problem 2


(a)


cityName stateName -> cityPopulation isCapital
countyName stateName -> countyPopulation
stateName -> statePopulation



(b)


{cityName, countyName, stateName}
{countyName stateName}
{stateName}



(c)

Yes, there is a BCNF violation, but it is so rare that a city is
associated with several counties that it probably is harmful to
decompose.
In particular, it would separate counties and cities, and require a join
to ask or answer queries about which cities are in which counties.
Not only are these queries harder to write, but the time the system
takes to answer the query is almost certainly greater than if we left
the relation undecomposed.


Problem 3


(a) No dependencies at all.  Key = ABC, surely no violation.


(b) AB -> C and C -> A.
There are two keys, AB and BC.
C -> A is a BCNF violation, but it is not a 3NF violation because the
right side, A, is in a key.


(c) A -> B and B -> C.
The key is A, while B -> C violates both 3NF and BCNF.


Problem 4


(a)


SELECT name
FROM Inventory, Manf
WHERE manfID = manf AND
      description LIKE '%beer%';



(b)


SELECT manf, AVG(quantity)
FROM Inventory
GROUP BY manf;



(c)


UPDATE Inventory
SET quantiy = 0
WHERE manf IN
	(SELECT manfID FROM Manf WHERE name = 'Acme');



(d)


INSERT INTO Manf(manfID)
	((SELECT manf FROM Inventory)
		EXCEPT
	 (SELECT manfID from Manf)
	);



(e)


SELECT itemID
FROM Inventory i
WHERE EXISTS (
		SELECT *
		FROM Inventory
		WHERE description = i.description AND
		      price < i.price
	     );




Problem 5


(a)


Q := PI_{quantity} (Inventory)	/* Q is the set of all quantities */

R := PI_{itemID} (
	SIGMA_{Inventory.quantity < Q.quantity} (
			Inventory X Q
		)
	)	/* R is the set of itemID's whose quantity is
		   not maximum */

Ans := PI_{itemID}(Inventory) - R



(b)


P(manfId) <- Manf(manfID, _, _)
Ans(itemID) < Inventory(itemID, _, manf, _, _) AND NOT P(manf)



In the above, P is the set of manufacturer ID's mentioned in
Manf.



Problem 6



CREATE TABLE Manf(
	manfID	INT		PRIMARY KEY,
	name	CHAR(50)	UNIQUE,
	addr	CHAR(50)
);

CREATE TABLE Inventory(
	itemID		INT	PRIMARY KEY
				CHECK(itemID >= 0 AND
				      itemID <= 32000
				),
	description	CHAR(25),
	manf		INT	REFERENCES Manf(manfID),
	quantity	INT,
	price		FLOAT,
	CHECK(price <= 1000.0 OR quantity < 10)
);


Problem 7


(a)


SELECT i.manf.name
FROM Inventory i
WHERE i.itemID = 123



(b)


SELECT i.itemID, i.quantity
FROM Manf m, m.items i
WHERE m.name = "Acme"



(c)


SELECT m
FROM Manf m
WHERE FOR ALL i IN m.items:
	i.quantity >= 10



(d)


SELECT desc, SUM(SELECT p.i.quantity FROM partition p)
FROM Inventory i
GROUP BY desc: i.description




Problem 8


The empty set, {B}, {C}, {A,B}, {C,D}, {B,C,D}, and {A,B,C,D}.
You lost 1 point for forgetting the empty set and two points for any
other missing or incorrect set.


Problem 9


(a)


Ans(x,y) <- Blue(x,y)
Ans(x,y) <- Red(x,z) AND Ans(z,y)
Ans(x,y) <- Blue(x,z) AND Ans(z,y)



(b)


Ans(x,y) <- Red(x,y)
Ans(x,y) <- Red(x,w) AND Blue(w,z) AND Ans(z,y)



(c)


BlueOut(x) <- Blue(x,y)		/* the set of nodes with a blue arc out */

Path(x) <- BlueOut(x)		/* the set of nodes with a path to somewhere
Path(x) <- Red(x,y) AND Path(y)	   ending in a blue arc */

Ans(x) <- Path(x) AND NOT BlueOut(x)



Error Codes:




Problem 10



WITH RECURSIVE Path(x,y) AS
	BLUE
		UNION
	(SELECT Blue.x, Path.y
	 FROM Path, Blue
	 WHERE Path.x = Blue.y
	)
		UNION
	(SELECT Red.x, Path.y
	 FROM Path, Red
	 WHERE Path.x = Red.y
	)

Path;




Problem 11


(a)


CREATE ASSERTION MyAss CHECK(
	NOT EXISTS(R INTERSECT S)
);



(b)
No; the value-based check will only detect problems when a value is
inserted into R.
It will not catch the situation where a value x that exists in R is
inserted into S.


Problem 12


(a)


(SELECT A, C FROM R NATURAL JOIN S)
	UNION
(SELECT A, B AS C FROM R);



(b)


PI_{AC} (R |X| S) - RHO_{R(A,C)} (R)



(c)

P(A) <- R(A,B) AND R(X,Y) AND A > X	/* P = set of not-
		minimum A's (first components of tuples in R */

Ans(A) <- R(A,B) AND NOT P(A)



Error codes: