Functional Dependencies: Inference, Keys, and Schema Design

All flashcards

What is a functional dependency?

It is a constraint stating that values of one attribute set determine values of another. If two tuples agree on the determinant, they must agree on the dependent attributes.

What are the determinant and dependent?

The determinant is the attribute set on the left of an FD; the dependent is the attribute set on the right. In $X \to Y$, X determines Y.

What makes an FD trivial?

An FD $X \to Y$ is trivial when $Y$ is a subset of $X$, such as $\{A,B\} \to A$.

What is the difference between a candidate key and a superkey?

Both determine every attribute in the relation. A candidate key is minimal, while a superkey may include unnecessary attributes.

Why does $VIN \to EngineCapacity$ not imply the reverse?

A VIN identifies one vehicle and therefore its capacity, but several vehicles may have the same capacity. Thus capacity need not identify a unique VIN.

Quiz questions

1. What does it mean that Armstrong’s axioms are sound and complete for functional-dependency inference?Answer: They derive only valid consequences and can derive every logically implied dependency.
2. For a relation with attribute set U and functional dependencies F, what does $X^+ = U$ establish?Answer: X is a superkey for the relation.
3. When do two functional-dependency sets F and G have equivalent meaning?Answer: When they imply exactly the same dependencies, so $F^+ = G^+$.
4. If a relation R satisfies $X \to Y$ and $Z$ contains its remaining attributes, which decomposition is lossless by Heath’s theorem?Answer: The projections on $XY$ and $XZ$, joined on their shared attributes.
5. What is a main purpose of normalization in relational database design?Answer: To reduce redundancy and undesirable update, insertion, and deletion anomalies.