Mathematical Foundation

When E.F. Codd introduced the relational model in 1970, he didn't just propose a new way to organize data—he grounded database management in rigorous mathematics. This wasn't an academic exercise; it was a strategic decision that would prove transformative.

Before the relational model, databases were engineering artifacts. Queries against hierarchical and network databases required intimate knowledge of physical storage structures. Each optimization was ad-hoc, each query language proprietary.

Codd's insight was that by basing data management on set theory and first-order predicate logic, query operations could be defined formally, optimized systematically, and proven correct mathematically. The database could reason about data without knowing how it was stored.

This mathematical foundation is why you can write SELECT * FROM employees WHERE salary > 50000 and trust that the database will find all matching records—regardless of how they're indexed, partitioned, or distributed across storage.

The relational model is built directly on set theory—the mathematical study of collections of objects. Understanding set theory illuminates why relations behave as they do.

Basic Set Concepts

A set is an unordered collection of distinct elements. Key properties:

• No duplicates: Each element appears at most once
• No ordering: {a, b, c} = {c, a, b}
• Membership: An element either is or isn't in a set (no partial membership)

Sets can be defined by:

• Enumeration: S = {1, 2, 3, 4, 5}
• Set-builder notation: S = {x | x is an integer and 1 ≤ x ≤ 5}
• Characteristic function: For each x, define whether x ∈ S

How Sets Map to Relations

Recall that a relation is formally a set of tuples. This set-theoretic definition immediately gives us:

1. No Duplicate Rows Since sets cannot contain duplicates, relations cannot contain duplicate tuples by definition. This is why SQL's DISTINCT keyword exists—SQL tables can violate pure set semantics.

2. Set Operations Work on Relations Because relations are sets, set operations (union, intersection, difference) apply directly. We can combine relations, find common elements, or compute differences—all with well-defined mathematical semantics.

3. Relations are Subsets of Cartesian Products Given domains D₁, D₂, ..., Dₙ for n attributes:

• The Cartesian product D₁ × D₂ × ... × Dₙ contains ALL possible combinations
• A relation R is a SUBSET of this Cartesian product
• R contains only the combinations that actually exist in our database

This is profound: the relation represents which facts are true out of all facts that could be true.

Domains:
  Department = {'Engineering', 'Marketing', 'Finance'}
  Level = {'Junior', 'Senior', 'Lead'}

Cartesian Product Department × Level (all 9 possible combinations):
  {('Engineering', 'Junior'), ('Engineering', 'Senior'), ('Engineering', 'Lead'),
   ('Marketing', 'Junior'), ('Marketing', 'Senior'), ('Marketing', 'Lead'),
   ('Finance', 'Junior'), ('Finance', 'Senior'), ('Finance', 'Lead')}

OpenPositions Relation (a subset representing actual open positions):
  {('Engineering', 'Senior'), ('Marketing', 'Junior'), ('Finance', 'Lead')}

This relation asserts:
  ✓ Engineering needs a Senior
  ✓ Marketing needs a Junior  
  ✓ Finance needs a Lead
  ✗ All other combinations are NOT open positions

While set theory provides the structural foundation, first-order predicate logic (also called first-order logic or predicate calculus) provides the foundation for expressing queries and constraints.

What is Predicate Logic?

Predicate logic extends propositional logic with:

• Variables that range over a domain of values
• Predicates that express properties of or relationships between variables
• Quantifiers that express how many elements satisfy a predicate

Predicates in the Relational Model

In relational databases, each relation can be viewed as a predicate:

Employee(emp_id, name, department, salary)

This is a 4-place predicate. The tuple (1001, 'Alice', 'Engineering', 95000) makes the predicate true:

Employee(1001, 'Alice', 'Engineering', 95000) = TRUE

A tuple NOT in the relation makes the predicate false:

Employee(9999, 'Nobody', 'Nowhere', 0) = FALSE

Quantifiers

Predicate logic uses two quantifiers:

Universal Quantifier (∀) — "for all"

• ∀x P(x) means "P(x) is true for every x in the domain"
• Example: ∀emp (Employee(emp) → emp.salary > 0)
  • "Every employee has a positive salary"

Existential Quantifier (∃) — "there exists"

• ∃x P(x) means "there is at least one x for which P(x) is true"
• Example: ∃emp (Employee(emp) ∧ emp.department = 'Engineering')
  • "There exists at least one employee in Engineering"

Logical Connectives

Predicates can be combined using:

• ∧ (AND): Both conditions must be true
• ∨ (OR): At least one condition must be true
• ¬ (NOT): Negation of a condition
• → (IMPLIES): If first is true, second must be true
• ↔ (IFF): Both conditions have the same truth value

SQL Query:
SELECT name FROM Employee WHERE salary > 80000 AND department = 'Engineering'

Predicate Logic:
{name | ∃emp_id, dept, sal (Employee(emp_id, name, dept, sal) 
                            ∧ sal > 80000 
                            ∧ dept = 'Engineering')}

Reading the formula:
"The set of all names such that there exists an employee with that name
who has a salary greater than 80000 and works in Engineering"

This is Tuple Relational Calculus notation—a formal query language
based directly on predicate logic.

Relational algebra is a procedural query language that operates on relations and produces relations. It consists of a set of operations that take one or two relations as input and produce a new relation as output.

Relational algebra is procedural: it specifies not just what to retrieve, but how to compute it—a sequence of operations.

The Fundamental Operations

Codd identified six fundamental operations from which all other operations can be derived:

Derived Operations

From the six fundamentals, we can derive useful shortcut operations:

Intersection (∩) Rows common to both relations. Derived: R ∩ S = R − (R − S)

Join (⋈) Combine related rows from two relations.

• Theta Join (⋈θ): Like Cartesian product, filtered by condition θ
• Natural Join (⋈): Join on common attribute names, removing duplicates
• Equijoin: Theta join where θ uses only equality

Division (÷) Rows in R associated with ALL rows in S. Useful for "find X that has all Y" queries.

Outer Joins Preserve rows that don't match:

• Left Outer Join (⟕): Keep all rows from left
• Right Outer Join (⟖): Keep all rows from right
• Full Outer Join (⟗): Keep all rows from both

Goal: Find names of employees in Engineering earning over $80,000

Relations:
  Employee(emp_id, name, department, salary)

Step-by-step Relational Algebra:
  1. Select Engineering employees:
     σ_department='Engineering' (Employee)
  
  2. Select high earners from step 1:
     σ_salary>80000 (σ_department='Engineering' (Employee))
  
  3. Project just the names:
     π_name (σ_salary>80000 (σ_department='Engineering' (Employee)))

Alternative combined notation:
  π_name (σ_department='Engineering' ∧ salary>80000 (Employee))

This algebraic expression is EQUIVALENT to:
  SELECT name 
  FROM Employee 
  WHERE department = 'Engineering' AND salary > 80000

The algebra provides a formal basis for query execution.

While relational algebra is procedural (specify HOW), relational calculus is declarative (specify WHAT). It describes the desired result without specifying how to compute it.

There are two equivalent forms of relational calculus:

1. Tuple Relational Calculus (TRC)

Variables range over tuples. Example:

{t.name | Employee(t) ∧ t.salary > 80000}

Reads: "The set of name values from tuples t where t is in Employee and t's salary exceeds 80000."

2. Domain Relational Calculus (DRC)

Variables range over domain values (attributes). Example:

{<n> | ∃e, d, s (Employee(e, n, d, s) ∧ s > 80000)}

Reads: "The set of name values n where there exist values e, d, s such that (e, n, d, s) is in Employee and s exceeds 80000."

Codd's Theorem: Equivalence

A fundamental result in database theory is Codd's Theorem, which states:

Relational algebra and the safe subset of relational calculus are expressively equivalent.

This means:

• Anything expressible in relational algebra can be expressed in relational calculus
• Anything expressible in safe relational calculus can be expressed in relational algebra
• They define the same class of queries

The "safe" qualifier is important. Unsafe calculus expressions can describe infinite results:

{t | ¬Employee(t)}  -- All tuples that are NOT employees

This describes infinitely many tuples! Safe calculus restricts expressions to guarantee finite results.

Why This Equivalence Matters

You can write queries declaratively (tell the database what you want) and the database can transform them to a procedural execution plan (how to get it). The mathematical equivalence guarantees the transformation is correct.

One of the greatest benefits of mathematical foundations is query optimization. Because relational operations obey algebraic laws, databases can transform queries into more efficient forms while guaranteeing identical results.

Algebraic Equivalences

Just as arithmetic obeys laws (a + b = b + a), relational algebra obeys laws:

Selection Laws:

• Cascade: σ_p1(σ_p2(R)) = σ_p1∧p2(R)
• Commutativity: σ_p1(σ_p2(R)) = σ_p2(σ_p1(R))

Projection Laws:

• Cascade: π_L1(π_L2(R)) = π_L1(R) if L1 ⊆ L2

Selection-Projection Commutativity:

• π_L(σ_p(R)) = σ_p(π_L(R)) if p uses only attributes in L

Join Laws:

• Commutativity: R ⋈ S = S ⋈ R
• Associativity: (R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)

Original Query (inefficient):
  π_name(Employee ⋈ Department) where department.budget > 1000000

This joins FIRST (expensive), then filters (cheap on small result).

Let Employee have 10,000 rows, Department have 100 rows.
Join produces all 10,000 employee-department combinations first.

Optimized Query (equivalent but faster):
  π_name(Employee ⋈ (σ_budget>1000000(Department)))

This filters Department FIRST (cheap), then joins with smaller set.

If only 10 departments have budget > 1M:
- Original: Join 10000 × 100, then filter → 1,000,000 comparisons
- Optimized: Filter to 10 depts, join 10000 × 10 → 100,000 comparisons

10x faster, mathematically guaranteed to give identical results!

Common Optimization Strategies

1. Push Selections Down Apply filters as early as possible to reduce intermediate result sizes. This is almost always beneficial.

2. Push Projections Down Remove unneeded columns early to reduce memory and I/O. Be careful: some operations need columns that might be projected out prematurely.

3. Reorder Joins Since joins are commutative and associative, the optimizer can choose the most efficient join order. For n tables, there are (2n-2)! / (n-1)! possible orders.

4. Choose Join Algorithms Based on table sizes and indexes, choose between:

• Nested Loop Join: Good for small outer table
• Hash Join: Good for equality joins on large tables
• Merge Join: Good when inputs are sorted

5. Use Indexes Replace table scans with index lookups when conditions use indexed columns.

The mathematical foundation enables us to express and enforce integrity constraints—rules that define valid database states. Constraints can be expressed as predicate logic formulas that must be true for every valid database instance.

Types of Integrity Constraints

Referential Integrity in Depth

Referential integrity ensures that foreign key values match existing primary keys. Formally:

∀r ∈ R: r.foreign_key = NULL ∨ ∃s ∈ S: r.foreign_key = s.primary_key

This means: Every foreign key value is either NULL (if allowed) or refers to an existing primary key.

Enforcement Actions:

When a referenced primary key is deleted or updated:

• RESTRICT / NO ACTION: Reject the operation if references exist
• CASCADE: Delete/update referencing rows too
• SET NULL: Set foreign key to NULL
• SET DEFAULT: Set foreign key to default value

Business Rule: 
"A manager's salary must be greater than all their direct reports"

Predicate Logic:
∀m, e ∈ Employee: 
  (e.manager_id = m.emp_id) → (m.salary > e.salary)

SQL CHECK (complex, requires triggers in most DBMSs):
Only expressible via triggers or application logic in standard SQL

Another Rule:
"Every department must have at least one employee"

Predicate Logic:
∀d ∈ Department: ∃e ∈ Employee: e.department_id = d.id

This is an ASSERTION (not directly supported in most DBMSs).
Workaround: Use triggers or application-level enforcement.

The gap between theoretical expressiveness and practical SQL
is why understanding the theory helps—you know what's missing.

Functional dependencies (FDs) are a mathematical concept central to database design. They describe how attribute values depend on each other.

Definition

A functional dependency X → Y holds in relation R if, whenever two tuples have the same values for attributes X, they must also have the same values for attributes Y.

In predicate logic:

∀t1, t2 ∈ R: t1.X = t2.X → t1.Y = t2.Y

Example:

• emp_id → name, department, salary

  If two tuples have the same emp_id, they must have the same name, department, and salary. This makes emp_id a candidate key.

• zip_code → city, state (in US)

  A zip code determines the city and state.

Armstrong's Axioms

Functional dependencies obey a complete set of inference rules called Armstrong's Axioms:

1. Reflexivity: If Y ⊆ X, then X → Y

• Any set of attributes determines its subsets
• {A, B} → B is always true (trivial FD)

2. Augmentation: If X → Y, then XZ → YZ

• Adding attributes to both sides preserves the FD
• If emp_id → name, then {emp_id, dept} → {name, dept}

3. Transitivity: If X → Y and Y → Z, then X → Z

• Dependencies chain together
• If emp_id → dept_id and dept_id → dept_name, then emp_id → dept_name

Derived Rules:

• Union: If X → Y and X → Z, then X → YZ
• Decomposition: If X → YZ, then X → Y and X → Z
• Pseudotransitivity: If X → Y and WY → Z, then WX → Z

These rules are sound (only produce valid implications) and complete (can derive all valid implications).

Relation: CourseSection(course_id, section, semester, year, instructor, room)

Functional Dependencies:
  1. {course_id, section, semester, year} → instructor
  2. {course_id, section, semester, year} → room
  3. {room, semester, year} → course_id, section  (room is used for one course at a time)

Question: What are the candidate keys?

Analysis:
  - From FDs 1 & 2 (union): {course_id, section, semester, year} → {instructor, room}
  - This means {course_id, section, semester, year} determines ALL other attributes
  - Therefore it's a superkey
  
  - Is it minimal? Yes—no subset determines all attributes
  - Therefore it's a CANDIDATE KEY

  - From FD 3: {room, semester, year} → {course_id, section}
  - Combined with FD 1: {room, semester, year} → entire relation
  - Therefore {room, semester, year} is ANOTHER candidate key!

The relation has two candidate keys.