Functional Dependency
A functional dependency exists between two attributes if the value of one attribute uniquely determines the value of another attribute in the same table.
For example, if we have a table of customer orders with attributes order_id, customer_id, and order_date, then order_id is functionally dependent on customer_id because each customer_id corresponds to a unique order_id. In other words, if we know the customer_id, we can determine the order_id.
We represent functional dependencies with an arrow (->). Using the previous example, we can write customer_id -> order_id to show that order_id is functionally dependent on customer_id.
Trivial Functional Dependency
A trivial functional dependency is one where the dependent attribute is a subset of the determinant attribute.
For example, if we have a table of customer orders with attributes order_id, customer_id, and order_date, then order_id -> order_id is a trivial functional dependency because the determinant attribute order_id is also the dependent attribute.
Non-Trivial Functional Dependency
A non-trivial functional dependency is one where the dependent attribute is not a subset of the determinant attribute.
For example, customer_id -> order_id is a non-trivial functional dependency because the determinant attribute customer_id is not the same as the dependent attribute order_id.
Semi-Trivial Functional Dependency
A semi-trivial functional dependency is one where the dependent attribute is partially same as the determinant attribute.
For example, A ∩ B ≠ Φ and A ⊄ B is a semi-trivial functional dependency.
Non-functional Dependency
A non-functional dependency exists between two attributes if the value of one attribute does not uniquely determine the value of another attribute in the same table.
For example, if we have a table of customer orders with attributes order_id, customer_id, and order_date, then order_date is not functionally dependent on customer_id because multiple orders can have the same order_date even if they are placed by different customers. In other words, knowing the customer_id does not uniquely determine the order_date.
We represent non-functional dependencies with a double arrow (<->). Using the previous example, we can write customer_id <-> order_date to show that order_date is not functionally dependent on customer_id.
Inference Rules
Inference rules are a set of rules that we can use to deduce new functional dependencies based on existing functional dependencies.
Here are some common inference rules:
- Reflexivity: If B is a subset of A, then A → B.
- Augmentation: If A → B, then A,C → B,C for any set of attributes C.
- Transitivity: If A → B and B → C, then A → C.
- Pseudo-transitivity: If A → B and C,B → D, then A,C → D.
- Union: If A → B and A → C, then A → B,C.
- Decomposition: If A → B,C, then A → B and A → C.
- Closure: The closure of a set of attributes F, denoted as F+, is the set of all attributes that are functionally dependent on F.
These inference rules help us derive additional functional dependencies from the ones we already know.
Further used in Normal Forms