Hamish Burke | 2025-05-22

Related to: #databases

Functional Dependency

$X\to Y$ is functional dependent if

• For every pair of tuples in every possible instance, equality on the attributes in $X$ forces equality on the attributes in $Y$
• $X,Y$ are subsets of attributes

Equality on the attributes

• Two tuples have exactly the same values in every column of the attribute set in question

Minimal Cover

Example

STUDENT(studentID,name,major)

Tuples:

1,Alice,CS

2,Bob,EE

Functional dep:

• studentID -> name, major
• Means every time its said studentID, it'll be the exact same name and major

Functional Dependency Closure

• $F+=\{X\to Y|X\subset R,Y\subset R,\text{and}X\to Y\text{follows from F vis Armstrong’s rules}\}$
• Eg all valid FD's can be inferred using repeated applications of
  • Reflexivity
  • Augmentation
  • Transitivity

Example

• $R=\{A,B,C\}$
• $F=\{A\to B,B\to C\}$

$F+=\{A\to B,B\to C,A\to C,AB\to BC,A\to BC,A\to A,B\to B\}$