*printable version*

# Test 1 Review B

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21]

### Problem R1b.1.

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)

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→namecitystatezip

zip→citystate

### Problem R1b.2.

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

advisor | major | student |

Burch | CSCI | Brown |

Burch | CSCI | Green |

### Problem R1b.3.

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

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

### Problem R1b.4.

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`

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

### Problem R1b.5.

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)

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.

### Problem R1b.6.

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.

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

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

### Problem R1b.7.

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)

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

### Problem R1b.8.

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.

{`permit_number`},
{`vin`}, and
{`tag_state`, `tag_number`}

### Problem R1b.9.

Suppose we have a relation
`R`(`a`, `b`, `c`, `d`, `e`)
with the following functional dependencies.

ab→ccd→ede→b

What is the closure of {

`a`,`b`,`e`}?What are the keys for

`R`?

{

`a`,`b`,`c`,`e`}{

`a`,`b`,`d`}, {`a`,`c`,`d`}, {`a`,`d`,`e`}

### Problem R1b.10.

Suppose we have a relation
`R`(`a`, `b`, `c`, `d`, `e`)
with the following functional dependencies.

ab→dac→eae→c

What is the closure of {

`a`,`c`}?What are the keys for

`R`?

{

`a`,`c`,`e`}The keys are {

`a`,`b`,`c`} and {`a`,`b`,`e`}.

### Problem R1b.11.

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.

{ `b`, `d` },
{ `a`, `c`, `d` }

### Problem R1b.12.

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

`a`,

`c`}, {

`a`,

`b`,

`d`}

### Problem R1b.13.

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…?

…its left side is a superkey.

### Problem R1b.14.

What condition must a relation satisfy to be in Boyce-Codd Normal Form (BCNF)?

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

### Problem R1b.15.

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.

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

### Problem R1b.16.

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.

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

### Problem R1b.17.

Give an example of a relation describing a telephone directory that is not in BCNF. Explain specifically why your 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.

### Problem R1b.18.

Suppose we have a relation whose attributes are
`a`, `b`, `c`, `d`, and `e`
with the FD basis:

`a`

`b`→

`c`,

`b`

`e`→

`d`,

`a`

`d`→

`b`

`c`

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

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

### Problem R1b.19.

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.

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

### Problem R1b.20.

Suppose that we have a relation
`R`(`a`, `b`, `c`, `d`)
with the functional dependencies

a→b

ac→d

bd→c

bcd→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.

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

### Problem R1b.21.

Suppose we have a relation
`R`(`a`, `b`, `c`, `d`, `e`)
with the following functional dependencies.

ab→cbc→dcd→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.

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