Test 1 Review B: Questions
Define the term functional dependency (represented using the notation A → B), and identify and explain at least two unrelated functional dependencies based on the below table schema; each should be nontrivial.
customers(cust_id, name, city, state, zip)
Suppose we had a relation giving students and their advisors, including advisor, student, major (assuming each student has exactly one major). A classmate suggests that the FD advisor major → student would apply to this relation. Give a realistic example of specific rows in this relation that would be inconsistent with this. (Use last names to identify advisors and students.)
Consider the following table for Super Bowl results, with some example rows listed for the years 2008–2012.
| year | city | mascot | score | opponent |
| 2012 | New York | Giants | 21 | 17 |
| 2011 | Green Bay | Packers | 31 | 25 |
| 2010 | New Orleans | Saints | 31 | 17 |
| 2009 | Pittsburgh | Steelers | 27 | 23 |
| 2008 | New York | Giants | 17 | 14 |
Would mascot → city be an FD for this table? Explain why or why not. (There's no penalty for inaccurate impressions of how football works, given that your assumptions are well-stated and reasonable.)
Hendrix's Public Safety office proposes the following schema for tracking parking permits.
permits(permit_number, student_id, vin, tag_state, tag_number, year, make, model)
The tag_state and tag_number attributes are for identifying cars by license plate, and the vin attribute tracks the vehicle identification number, which is unique to each car in the world.
For each of the following proposed functional dependencies, explain why or why not it would apply to this table.
- tag_state tag_number → student_id
- year make model → permit_number
Identify and explain at least two unrelated functional dependencies based on the below table schema; each should be nontrivial.
orders(invoice_id, customer_name, item_id, cost)
Suppose we have a relation for college courses with the following schema.
courses(discipline, number, title, description, department)
For example, it might contain the following.
discipline number title description department CSCI 340 Database Systems a fun course Mathematics & Computer Science MATH 130 Calculus I a good course Mathematics & Computer Science SPAN 110 Spanish I an introductory course Foreign Languages
Write down at least two substantially different nontrivial functional dependencies that this table would have (based on the above table and what you know about Hendrix).
For the following schema, identify a nontrivial functional dependency (FD) and explain why the functional dependency might apply to the table, with specific reference to the attributes' meaning.
locations(latitude, longitude, elevation, place_name)
Hendrix's Public Safety office proposes the following schema for tracking parking permits.
permits(permit_number, student_id, vin, tag_state, tag_number, year, make, model)
The tag_state and tag_number attributes are for identifying cars by license plate, and the vin attribute tracks the vehicle identification number, which is unique to each car in the world. Public Safety is willing to issue multiple permits to the same person, to different vehicles; but no vehicle ever receives multiple permits.
Identify three different keys for this table. Feel free to specify any unusual assumptions you must make for a key to be valid.
Suppose we have a relation R(a, b, c, d, e) with the following functional dependencies.
a b → c
c d → e
d e → b
What is the closure of { a, b, e }?
What are the keys for R?
Suppose we have a relation R(a, b, c, d, e) with the following functional dependencies.
a b → d
a c → e
a e → c
What is the closure of {a, c}?
What are the keys for R?
Suppose we have a relation R(a, b, c, d) with the functional dependencies a b → c, a c → b, and b d → a. Identify the keys for this relation.
Suppose we have the schema R(a, b, c, d), with the FDs c → b, a c → d, and b d → c. Identify two keys for R.
Complete the following definition: A relation is in BCNF (Boyce-Codd Normal Form) if for every FD applying to the table, the FD is either trivial or…?
What condition must a relation satisfy to be in Boyce-Codd Normal Form (BCNF)?
Give an example of a relation for Hendrix housing assignments that is not in BCNF. Explain why your relation is not in BCNF by giving a specific violating FD and explaining why it violates BCNF.
Give an example of a relation describing a library card catalog that is not in BCNF. Explain specifically why your relation is not in BCNF.
Give an example of a relation describing a telephone directory that is not in BCNF. Explain specifically why your relation is not in BCNF.
Suppose we have a relation whose attributes are a, b, c, d, and e with the FD basis:
a. What are the keys for this relation? (There are two.)
b. Explain why this relation is not in Boyce-Codd Normal Form, with specific reference to the relation and its FDs.
Suppose we have the schema R(a, b, c, d) with the FD a → b d. The set {a, c} is a key for R. Explain why this relation is not in BCNF, and decompose it into two relations that are in BCNF.
Suppose that we have a relation R(a, b, c, d) with the functional dependencies
a → b
a c → d
b d → c
b c d → a
The keys for this relation are { a, c }, { a, d }, and { b, d }. Decompose the relation so that it is in BCNF, and explain your answer.
Suppose we have a relation R(a, b, c, d, e) with the following functional dependencies.
a b → c
b c → d
c d → e
The one key for this relation is {a, b}. Explain why this relation is not in BCNF, with specific reference to its FDs. Decompose the relation into BCNF relations, explaining with each step which FD you are using.
Test 1 Review B: Solutions
A functional dependency A → B applies to a relation if for any two rows agreeing on the attributes of A, those rows must necessarily agree on the attributes of B.
Examples for the given table include:
cust_id → name city state zip
zip → city state
| advisor | major | student |
| Burch | CSCI | Brown |
| Burch | CSCI | Green |
No, it is not a valid FD, because teams sometimes switch cities keeping the same mascot; thus, knowing the mascot, I cannot determine the city. An example would be the Oakland Raiders, who moved to Los Angeles in the 1982 while remaining the Raiders, and then they moved back to Oakland in 1995. In fact, they actually did win the Super Bowl both as the Oakland Raiders and as the Los Angeles Raiders; although even if they did not, such a circumstance could happen in the future. (Another example is the Colts, who moved from Baltimore to Indianapolis in 1984, preserving their mascot. They won both before (1970) and after (2006) that move.)
(However, both the year and the mascot would be enough to determine the city, so that would be a valid FD: The NFL ensures that no two teams have the same mascot.)
- This is an FD, since the state and tag number specify a unique license plate, which will be unique to each student.
- This is not an FD, since two different students would have cars of identical year, make, and model (for example, two students might have 2008 Volkswagen Beetles), so the table could include two rows with different permit numbers and an identical year-make-model combination.
One FD is invoice_id → customer_name, since only one customer receives each invoice.
Another potential example is the FD item_id → cost, asserting that each item has a fixed cost charged to all customers. This FD may not apply: Items' costs may change over time, and it may be that special discounts are negotiated for some particular customers. In that case, a reasonable alternative is invoice_id item_id → cost, asserting that on any invoice, only one cost for an item appears.
discipline → department
discipline title → number description
(I'd accept discipline number →
title, too, but actually the titles vary on some
topics
courses (as CSCI 490).)
latitude longitude → elevation would likely apply: The latitude and longitude identify a particular location on the earth's surface, which would have an unique elevation associated with it.
{permit_number}, {vin}, and {tag_state, tag_number}
{ a, b, c, e }
{ a, b, d }, { a, c, d }, { a, d, e }
{a, c, e}
The keys are {a, b, c} and {a, b, e}.
{ b, d }, { a, c, d }
…its left side is a superkey.
Every nontrivial function dependency must have a left side that is a superkey (i.e., the left side of the functional dependency must actually determine all attributes of the relation).
rooms(student_id, last_name, hall, room_no, floor_area)
This is not in BCNF because hall room_no → floor_area is a valid FD: After all, hall and room_no together specify the exact room, so we know the floor area just from that information. However, its LHS {hall, room_no} is not a superkey, since some rooms have multiple students assigned to them and so student_id cannot be determined from just these two attributes.
books(call_number, title, author, birth_date)
It would be reasonable to suppose that the FD author → birth_date would apply to this relation, as each author can only be born in on one day (ignoring the issue of multiple authors with identical names). However, author is not itself a superkey, since the library may contain multiple books by some authors, so this relation is not in BCNF.
directory(name, address, phone)
If multiple people may be listed for the same telephone number, then phone is not itself a superkey, since it is not enough to identify a single row of the relation. But the FD phone → address might also apply to this relation, in which case the relation is not in BCNF, since the FD's left side (phone) is not itself a superkey.
a. The keys are {a, b, e} and {a, d, e}. (Any key must include a and e, since neither of these can be determined from any FD; but these don't on their own determine anything. Moreover, adding c doesn't help determine either of the remaining attributes — adding b to a and e determines all other attributes, as does adding d.)
b. It is not in BCNF because the FD a b → c has a left side ({a, b}) that is not a superset of one of the keys. (For that matter, none of the three listed FDs have a left side that's a superset of one of the keys.)
It is not in BCNF since the FD's left side isn't a superkey — in fact, it is a proper subset of the key.
The relation would be decomposed into the two BCNF relations S(a, b, d) and T(a, c).
It is not in BCNF due to the a → b FD. We can decompose the relation into two BCNF relations, S(a, b) and T(a, c, d).
It is not in BCNF because the FD b c → d does not have a superkey on its left side: {b, c} is not a superset of {a, b}. (The FD c d → e has the same problem.)
To decompose, we might first start with the violating FD b c → d. Note that the closure of {b, c} is {b, c, d, e}, so we decompose R into (b, c, d, e) and (a, b, c). We'd then observe that the first relation isn't in BCNF due to the c d → e FD, so we'd split this relation further into (c, d, e) and (b, c, d). We thus end up with three relations: (a, b, c), (c, d, e), and (b, c, d).