Solutions to Spring 1997 Final Exam |

The following error codes were used:

- A: Making the name of the capital an attribute (-1).
- B: Making isCapital an attribute of City (-2).
- C or F: Making the relationship between cities and counties weak (-4).
- D: Duplicating information as both an attribute and relationship (-4).
- E: Wrong arrows (-1, each).
- G: Not identifying weak entity sets (-2).

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

Error Codes:

- A: missing state in CityCounty (-1).
- B: Not E/R based (-5).
- C: Redundant relations (-1, each).

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:

- A: No key for State (-1).
- B: Inventing keys for City or County (-2, each).
- C: Set<...> missing.
- D: Using IsCapital as an attribute (-1).
- E: State capital an attribute rather than relationship (-1).
- F: Duplication (-4).
- G: Missing relations (-2 per pair).
- H: Using attributes for relations (-2, each).

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

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.

(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.

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 );

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

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:

- A: Unsafe rule (-2).
- B: ``no blue arc out'' not handled in (c). (-2)
- C: Binary predicate in (c). (-1)
- D: Using OR in a Datalog rule (-2).

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;

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.

(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:

- A: unsafe negation (-1)
- B: Finding the nonmaximal A's in (c). (-4)
- C: Incorrect attributes in the union (part a) or difference (part b). (-2)
- D: Forgetting that C is not an attribute of R (-2).
- E: Missing projection in part (b). (-2)