Homework 2

Question 1: 10pts Consider a relation with schema $R(a,b,c,d)$ and functional dependencies $S=\{ab\rightarrow c, c\rightarrow d, d\rightarrow a\}$

a. What are all the non-trivial FDs that follow from the given FDs?

There are many: you should restrict yourself to FDs with single attributes on the right side.
Hint – My solution has 14 nontrivial FDs (including the original 3) with single attributes on the RHS.

b. What are the superkeys of R?

c. What are candidate keys of R?


Question 2: 10pts  For each of the following relation schemas and sets of FDs:

a. $R(a,b,c,d)$ with FDs $S= ab\rightarrow c, c\rightarrow d, d\rightarrow a\}$
b. $R(a,b,c,d)$ with FDs $S= b\rightarrow c, c\rightarrow d\}$
c. $R(a,b,c,d)$ with FDs $S= ab\rightarrow c, bc\rightarrow d, cd\rightarrow a, ad\rightarrow b\}$

Assume $R$ is in 1NF.

Do the following:

  1. Indicate all the 3NF violations. Describe how the FD violates 3NF.
  2. Decompose the relations, as necessary, into collections of relations that are all in 3NF.

Hint – Remember to indicate the keys of the new relations


Question 3: 10pts  For each of the relation schemas and sets of FDs from Question 2:

  1. Indicate all BCNF violations. Describe how the FD violates BCNF.
  2. Decompose the relations, as necessary, into collections of relations that are all in BCNF.

Hint – Remember to indicate the keys of the new relations


Question 4: 25pts  This exercise builds upon the Products schema from the last homework. Recall that the database schema consists of four relations, whose schemas are:

Product(maker, model, type)
PC(model, speed, ram, hd, price)
Laptop(model, speed, ram, hd, screen, price)
Printer(model, color, type, price)

Some sample data for the relations are shown below.

Product

makermodeltype
A1001pc
A1002pc
A1003pc
A2004laptop
A2005laptop
A2006laptop
B1004pc
B1005pc
B1006pc
B2007laptop
C1007pc
D1008pc
D1009pc
D1010pc
D3004printer
D3005printer
E1011pc
E1012pc
E1013pc
E2001laptop
E2002laptop
E2003laptop
E3001printer
E3002printer
E3003printer
F2008laptop
F2009laptop
G2010laptop
H3006printer
H3007printer

PC

model speed ram hd price
10012.6640962502114
10022.102048250995
10031.42204880478
10042.804096250649
10053.202048250630
10063.2040963201049
10072.204096200510
10082.208192250770
10092.204096250650
10102.808192300770
10112.808192160959
10122.804096160649
10133.06204880529

Laptop

model speed ram hd screen price
20012.00819224020.13673
20021.7340968017.0949
20031.8020486015.4549
20042.0020486013.31150
20052.16409612017.02500
20062.0081928015.41700
20071.83409612013.31429
20081.60409610015.4900
20091.6020488014.1680
20102.00819216015.42300

Printer

model color type price
3001Trueink-jet99
3002Falselaser239
3003Truelaser899
3004Trueink-jet120
3005Falselaser120
3006Trueink-jet100
3007Truelaser200

Write expressions of relational algebra to answer the following queries. You may use the sequence of operators notation if you wish. Show the result of your query. However, your answer should work for arbitrary data, not just this data.

a. What PC models have a speed of at most 3.00?

b. What manufacturers make laptops with a hard disk of at least 160GB?

c. Find the model number and price of all products (of any type) made my manufacturer B

d. Find the model numbers of all color laser printers

e. Find those manufacturers that sell Laptops, but not PCs.

f. Find those hard-disk sizes that occur in two or more PCs.

g. Find those pairs of PC models that have both the same speed and RAM. A pair should be listed only once; e.g., list $(i,j)$ but not $(j,i)$.


Question 5: 5pts  Draw expression trees for each of your expressions of Q4 (only a-e)


Question 6: 25pts  Denote answers to Q4 (only a-e) in tuple relational calculus.


Question 7: 10pts  Suppose relations $R$ and $S$ have $m$ tuples and $n$ tuples respectively. Give the minimum and maximum numbers of tuples that the results of the following expressions can have:

a. $R\cup S$

b. $R\bowtie S$

c. $\sigma_C (R)\times S$, for some condition $C$

d. $\Pi_L (R)-S$, for some list of attributes $L$


Question 8: 05pts Using the Laptop relation from Q4, suppose we compute the projection $\Pi_{\textrm{speed}} (\textrm{Laptop})$. What are the values of this expression as a set? As a bag? What is the average value of tuples in this projection, when treated as a set? As a bag?


Some exercises are from Garcia-Molina, Ullman, Widom. Database Systems. 2nd Edition.

This is an individual assignment. Discussion is allowed, but students may not write submitted solutions in the presence of a group.

Cite your sources.

Submissions must be uploaded to GradeScope and marked by the due date.