Question 1: 10pts Consider a relation with schema $R(x,y,z,w)$ and functional dependencies $S=\{x,y\rightarrow z; ~~ z\rightarrow w; ~~ w\rightarrow x\}$
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: 15pts For each of the following relation schemas and sets of FDs:
a. $R(x,y,z,w)$ with FDs $S= \{x,y\rightarrow z; ~~ z\rightarrow w; ~~ w\rightarrow x\}$
b. $R(x,y,z,w)$ with FDs $S= \{y\rightarrow z; ~~ z\rightarrow w\}$
c. $R(x,y,z,w)$ with FDs $S= \{x,y\rightarrow z; ~~ y,z\rightarrow w; ~~ z,w\rightarrow x; ~~ x,w\rightarrow y\}$
Assume $R$ is in 1NF.
Do the following:
- Indicate all the 3NF violations. Describe how the FD violates 3NF.
- 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: 15pts For each of the relation schemas and sets of FDs from Question 2:
- Indicate all BCNF violations. Describe how the FD violates BCNF.
- 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: 35pts This exercise builds upon the Products schema from the last homework. Recall that the database schema consists of four relations, whose schemas are:
- Gear (brand, model, category)
- Speaker (model, power, weight, price)
- Microphone (model, type, frequency_range, price)
- Instrument (model, type, material, price)
Some sample data for the relations are shown below.
Gear
| brand | model | category |
|---|---|---|
| A | 1001 | speaker |
| A | 1002 | speaker |
| A | 1003 | speaker |
| A | 2004 | microphone |
| A | 2005 | microphone |
| A | 2006 | microphone |
| B | 1004 | speaker |
| B | 1005 | speaker |
| B | 1006 | speaker |
| B | 2007 | microphone |
| C | 1007 | speaker |
| D | 1008 | speaker |
| D | 1009 | speaker |
| D | 1010 | speaker |
| D | 3004 | instrument |
| D | 3005 | instrument |
| E | 1011 | speaker |
| E | 1012 | speaker |
| E | 1013 | speaker |
| E | 2001 | microphone |
| E | 2002 | microphone |
| E | 2003 | microphone |
| E | 3001 | instrument |
| E | 3002 | instrument |
| E | 3003 | instrument |
| F | 2008 | microphone |
| F | 2009 | microphone |
| G | 2010 | microphone |
| H | 3006 | instrument |
| H | 3007 | instrument |
Speakers
| model | power | weight | price |
|---|---|---|---|
| 1001 | 280 | 40.00 | 21.14 |
| 1002 | 210 | 20.40 | 90.95 |
| 1003 | 142 | 20.40 | 45.78 |
| 1004 | 280 | 40.00 | 60.49 |
| 1005 | 320 | 20.40 | 60.30 |
| 1006 | 320 | 40.00 | 10.49 |
| 1007 | 220 | 40.00 | 52.10 |
| 1008 | 220 | 81.90 | 77.00 |
| 1009 | 220 | 40.00 | 60.50 |
| 1010 | 280 | 81.90 | 77.00 |
| 1011 | 280 | 81.90 | 95.90 |
| 1012 | 280 | 40.00 | 61.49 |
| 1013 | 306 | 20.50 | 52.99 |
Microphones
| model | type | freq_rng | price |
|---|---|---|---|
| 2001 | wired | 80-10000 | 367.30 |
| 2002 | wired | 40-20000 | 94.99 |
| 2003 | wired | 20-10000 | 54.99 |
| 2004 | cordless | 20-10000 | 110.50 |
| 2005 | cordless | 20-10000 | 250.00 |
| 2006 | cordless | 10-20000 | 174.00 |
| 2007 | wired | 20-10000 | 142.90 |
| 2008 | wired | 20-10000 | 900.00 |
| 2009 | cordless | 60-20000 | 68.59 |
| 2010 | wired | 100-30000 | 23.00 |
Instruments
| model | type | material | price |
|---|---|---|---|
| 3001 | guitar | wood | 99 |
| 3002 | trap | canvas | 239 |
| 3003 | trap | canvas | 899 |
| 3004 | piano | wood | 120 |
| 3005 | piano | plastic | 120 |
| 3006 | guitar | resin | 100 |
| 3007 | guitar | wood | 200 |
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 Speakers have a power of more than 300 Watts?
b. What brands of Speakers weight less than 30.00 kg?
c. Find the model number and price of all Gear (of any type) made my brand B
d. Find the model numbers of all wood instruments
e. Brands that sell Speakers but not Instruments.
f. Find those Instruments that have the same price.
g. Find those Speakers with same power and weight. 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 Speakers relation from Q4, suppose we compute the projection $\Pi_{\textrm{power}} (\textrm{Speakers})$. What are the values of this expression as a set? As a bag? What is the mean-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.