[SOLVED] Assignment 1 csc 370

Question 1 (15 marks)
Given two relations R and S, where R contains M tuples, S contains N tuples, and M > N > 0,
give the minimum and maximum possible sizes (in tuples) for the relation resulting from each
of the following expressions. For each case, you must state any assumptions about the schemas
for R and S needed to ensure expressions are meaningful.
(a) R ∪S
(b) R ∩S
(c) R −S
1
(d) R ×S
(e) σa=5(R)
(f ) πa(R)
(g) R ⊲⊳ S
Question 2 (30 marks)
Consider the following schema:
Suppliers(sid, sname, address)
Parts(pid, pname, colour)
Catalog(sid, pid, cost)
The key for Suppliers is sid, for Parts is pid, and for Catalog is sid and pid. The Catalog
relation associates prices charged for parts by suppliers.
Write the following queries using relational algebra. For items (a) through (e), use the “sequences of assignments” form. For items (f ) and (g), use the “expression tree” form. List all
assumptions. (Some marks will be given for the quality of your answers.)
(a) Find the names of suppliers who supply some blue part.
(b) Find the ids of suppliers who supply some blue or magenta part.
(c) Find the ids of suppliers who supply every magenta part.
(d) Find the ids of suppliers who supply every part.
(e) Find the ids of parts supplied by at least two different suppliers.
(f ) Find the ids of the most expensive parts supplied by company name named “Screw-2-You
Limited”.
(g) Find the ids of parts supplied by every supplier at less than or equal to $50. (If any supplier
either does not supply the part or charges more than $50 for it, then that part should not be
in the final relation.)
2
Question 3 (25 marks)
Recall the schema from Question 2. Using natural language describe what is computed by the
following queries. Make sure the rules of precedence as given in lectures are followed. Some
marks will be given for the quality of your answer (that is, simply describing the query literally
will not result in full marks).
(a) πsname(πsid(σcolour=“blue”(Parts)) ⊲⊳ (σcost<100(Catalog)) ⊲⊳ Suppliers)
(b) πsname(πsid((σcolour=“green”(Parts)) ⊲⊳ (σcost<25.5(Catalog)) ⊲⊳ Suppliers))
(c) (πsname((σcolour=“puce”(Parts)) ⊲⊳ (σcost<50(Catalog)) ⊲⊳ Suppliers)) ∩
(πsname((σcolour=“cyan”(Parts)) ⊲⊳ (σcost<50(Catalog)) ⊲⊳ Suppliers))
(d) (πsid((σcolour=“coral”(Parts)) ⊲⊳ (σcost<200(Catalog)) ⊲⊳ Suppliers)) ∩
(πsid((σcolour=“charcoal”(Parts)) ⊲⊳ (σcost<200(Catalog) ⊲⊳ Suppliers))
(e) πsname((πsid,sname((σcolour=“teal”(Parts)) ⊲⊳ (σcost<150(Catalog)) ⊲⊳ Suppliers)) ∩
(πsid,sname((σcolour=“eggshell white”(Parts)) ⊲⊳ (σcost<100(Catalog)) ⊲⊳ Suppliers)))
Question 4 (25 marks)
Consider a relation with schema S(A,B,C,D) with functional dependencies AB → C, BC → D,
C D → A, and AD → B. Answer each part below, and show all work (that is, show work towards
computing closures).
(a) What are all the nontrivial FDs that follow from the functional dependencies? Ensure that
all of your FDs have a single attribute on the right-hand side.
(b) What are all the keys of S?
(c) What are all superkeys for S that are not keys?
Question 5 (30 marks)
Consider a relation with schema R(A,B,C,D,E) with FDs AB →C, DE →C, and B → D. Answer
each part below, and show all work.
(a) Indicate all BCNF violations. You should also consider all FDs inferred by the given set. You
need not list violations for FDs having more than one attribute on the right-hand side.
(b) Decompose the relations as necessary into relations that are in BCNF.
3
Question 6 (30 marks)
Consider a relation Equities(B,O,I,S,Q,D). The attributes may be thought of as (roughly) a
stock broker, the broker’s office, a stock investor, the stock itself, number of shares of the stock
(quantity), and the yearly dividend produced by the stock1
. The set of FDs for this relation are
S → D, I → B, I S →Q, and B →O.
(a) What are all the keys for Equities?
(b) Verify that the given FDs are their own minimal basis. Some marks will be given for the
quality of your answer.
(c) Use the 3NF synthesis algorithm to find a lossless-join, dependency-preserving decomposition of Equities into 3NF relations. Are any of the resulting relations not in BCNF?
Question 7 (30 marks)
Consider a relation with schema T (A,B,C,D,E) with multi-valued dependencies A ։ B and
AB ։C and FDs A → D and AB → E.
(a) Find all 4NF violations.
(b) Decompose the relation into a collection of relation schemas in 4NF.
Question 8 (15 marks)
Suppose we have a relation schema R(A,B,C) with functional dependency A → B. Now consider that we go ahead and decompose this into S(A,B) and T (B,C). Provide an example of a relation instance for R where the projection onto S and T and subsequent rejoining (as described
in the course) does not yield the same relation instance. Put differently, πA,B (R) ⊲⊳ πB,C (R) 6= R.
1Lucky if you can get it these days.
4