Concept 1 / 8
Mathematical Foundations: Sets, Cartesian Products, Relations
The relational model is built on set theory. Key building blocks:
Set: A collection of distinct elements. Sets have no duplicates and no order. Notation: A = {1, 5, 6}, |A| = cardinality.
Cartesian Product: S₁ × S₂ = {(s₁, s₂) | s₁ ∈ S₁, s₂ ∈ S₂} — all ordered pairs. For n sets: Π S₁×...×Sₙ.
Relation: A subset R ⊆ S₁ × ... × Sₙ of a Cartesian product. Arity = number of participating sets.
Function: A relation f ⊆ S₁ × S₂ where for each s₁ there is exactly one s₂. Notation: f(s₁) = s₂.
Partial function: At most one s₂ per s₁. Write f(s₁) = ⊥ when no pair exists.
Total vs. Functional relations:
| Property | Meaning |
|---|---|
| Total on Sᵢ | Every value in Sᵢ appears in ≥ 1 tuple |
| Functional on Sᵢ | Every value in Sᵢ appears in ≤ 1 tuple |
Why this matters: A primary key constraint is exactly the requirement that the relation is functional on the key attribute set.