Functional Dependencies

Let $R$ be a $k$ -ary relation $R / (A_{1}, \dots, A_{k})$ where $l (i) = A_{i}, 1 \leq i \leq k$ and let $X, Y$ be subsets of ${A_{1}, \dots, A_{k}}$
A functional dependency over the Attributes of $R$ is $X \to Y$ , $Y$ depends on $X$

We say that set of attributes X functionally determines the set of attributes Y in $R$
Usually forms a relation schema with its set of attributes

Example

Pasted image 20231212123130.png
Employee SIN numbers functionally determine employee names

SIN → EName

Project numbers functionally determines project names and locations

PNum → PName, PLoc

Project locations and the number of hours functionally determine allowances

PLoc, Hours → Allowance

What functional dependencies should hold as a consequence of the primary key of EmpProj?

SIN, PNum → SIN, PNum, Hours, EName, PName, PLoc, Allowance

Logical Consequence

Algorithm

Assume $R$ is a set of attributes, $X$ a subset of $R$ , and $F$ a set of FDs over $R$

function ComputeX+(X, F)
begin
    X+ := X;
    while true do
        if there exists (Y -> Z) ∈ F such that
            1. Y ⊆ X+
            2. Z ⊈ X+
        then X+ := X+ ∪ Z
        else exit;
    return X+;
end

Correctness Theorem: $(X \to Y) \in F^{+}$ if and only if $Y \subseteq C o m p u t e X^{+} (X, F)$

Armstrong’s Axioms

Keys

Superkey theorem for functional dependencies:
$X$ is a superkey of a relation with schema $R$ if and only if $R \subseteq C o m p u t e X^{+} (X, F)$