Tags:conceptdatabasefunctionaldependencies Status:🟩

---

Functional Dependencies

Summary

Functional dependencies (FDs) are a fundamental concept that plays a critical role in database normalization and ensuring data integrity. A functional dependency describes a relationship between attributes in a relation (table), where the value of one attribute (or a group of attributes) determines the value of another attribute (or group of attributes). They allow us to decide whether a database design is correct.

Details

The definition is $x\to y$, which translates to ‘the value of x functionally defines the value of y’.

Simple functional dependency

The value of sid determines the value of name for the student. Since a name is not unique we cannot use name to determine the address. If another student with the same name was inserted, then it would not be a functional dependency.

Combination

Two FDs $x\to y$ and $x\to z$ can be written in shorthand as $x\to yz$. But $xy\to z$ is not the same as the two FDs $x\to z$ and $y\to z$. A specific combination of x and y together that determine z. I.e. sid$\to$name,address is not the same as name,address$\to$sid.

Implied functional dependencies

Implied functional dependencies are dependencies that can be logically deduced from other functional dependencies in a database. They’re not directly stated but can be figured out using rules like transitivity or augmentation.

Functional Dependencies:

• The sid uniquely determines the name and address.
• The sid and cid uniquely determines the grade.

Implied Functional Dependencies:

• Since sid is part of the composite key (sid, cid), knowing sid alongside cid still allows us to know sid. This is a bit trivial but important. The same goes for cid.
• Since sid, cid is a composite key that uniquely identifies the grade, you can derive that knowing both sid and cid allows you to determine the grade of the student in that course.

Prime attribute types

A prime attribute type is an attribute type that is part of a candidate key. To be a part of a candidate key, the attribute types has to uniquely identify a record in a relation.

Closures

Closure refers to the set of attributes that can be functionally determined by a given set of attributes. It helps to understand the implications of the functional dependencies in a relation. Definition: Given a set $F$ of FDs $\{f_1,...,f_n\}$, we define the closure $F+$ is the set of all implied FDs.

We can compute the closure using Armstrong’s Axioms.

A functional dependency is trivial if the dependent attribute is already included in the determinant. In simpler terms, this means that all the attributes on the right-hand side (YYY) are already present in the left-hand side (XXX). If we have $AC\to BCD$, then $AC\to C$ is trivial, because it is already in $AC\to BCD$.

Armstrong’s Axioms

Neither x or y is necessarily one single attribute. They can be sets of attributes. (like the above image). Reflexivity: If x is a superset of y, then x determines y. Basically when y is a subset of x.

Decomposition

It’s the process of breaking down a table into two or more smaller tables to eliminate redundancy and maintain integrity. This process is important for achieving a well-structured database design, particularly in the context of normalization.

Old table	New table
Problems with the old big table

• Update Anomalies: If the room number changes, we need to make sure that we change all students records.
• Insert Anomalies: May not be possible to add a student unless they’re enrolled in a course.
• Delete Anomalies: If all the students enrolled in a course are deleted, then we lose the room number.

The solution is to decompose the old table into smaller tables. Since name and address only depends on sid it would make sense to decompose it into a separate table student.

Unavoidable and Redundant FDs

Unavoidable FDs

1. Definition: Unavoidable FDs are those that must always hold true for a relation.
2. Superkeys and Candidate Keys:
   • If A is a candidate key for a relation, then it will always determine any attribute B. This is expressed as: $A\to B$.
   • If $A_1,A_2$ forms a superkey, it also determines any attribute B. This can be expressed as: $A_1{A}_2\to B$.
3. Key Points:
   • Unavoidable FDs arise naturally from the definition of keys.
   • They reflect essential relationships between attributes that cannot be ignored.

Redundant FDs

1. Definition: Redundant FDs are those that can be derived or computed from other FDs.
2. No Need for Decomposition:
   • Redundant FDs do not require decomposition because they do not introduce new information. They can be inferred from existing FDs.
   • For example, if we have $A\to B$ and $B\to C$, then $A\to C$ is a redundant FD because it can be derived from the first two.
3. When to Decompose:
   • Decompose the relation only when FDs are not trivial, not unavoidable, and not redundant.
4. Key Points:
   • Identifying redundant FDs helps simplify the design without compromising the integrity of the data.
   • Focus on essential FDs to decide on the need for decomposition.