Solutions to Spring 1997 Final Exam

### Problem 1

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

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).
(b)
```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).
(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:

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

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

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

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:

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)

```