Lecture 02: The Relational Model

1. Why Did the Relational Model Win?

Proposed by Edgar F. Codd in 1970 at IBM, the relational model replaced earlier hierarchical (tree) and network (graph) database systems.

• Earlier Systems (Hierarchical & Network): Required programmers to write procedural navigation code specifying how to traverse pointers through records. If physical storage changed, programs broke.
• The Relational Model: Uses simple tabular data structures based on first-order predicate logic and set theory. Users specify what data they need declaratively, leaving navigation and optimization to the DBMS engine.

2. Core Mathematical Definitions

Relations, Tuples, and Attributes

1. Domain (D): A set of atomic (indivisible) values.
   Example: salary_domain = { x ∈ ℝ | x >= 0 }, dept_name_domain = String(50).
2. Attribute (A_i): The named role played by a domain in a relation schema.
3. Relation Schema (R): The blueprint of the relation, denoted:

   R(A_1, A_2, ..., A_n)

   where each attribute A_i is defined over domain D_i = dom(A_i).
4. Tuple (t): An ordered mapping of values <v_1, v_2, ..., v_n> where each v_i ∈ dom(A_i).
5. Relation Instance (r(R)): A mathematical relation, defined as a finite subset of the Cartesian product of the attribute domains:

   r(R) ⊆ dom(A_1) × dom(A_2) × ... × dom(A_n)

Critical Properties of Relations (Derived from Set Theory)

• Tuples are unordered: There is no first or last tuple in a mathematical relation.
• Attributes are unordered: Attributes are referenced by name, not index.
• No duplicate tuples: Because a relation is a set, duplicate tuples cannot exist in a theoretical relation.
• Attribute values are atomic: First Normal Form (1NF) requires values to be non-decomposable (no nested lists or tables).

3. The Hierarchy of Keys

A key constraint enforces that no two distinct tuples in any valid relation instance have the exact same values for the key attributes.

+-------------------------------------------------------------+
| Superkeys                                                   |
|   (Any attribute set that uniquely identifies a tuple)      |
|                                                             |
|   +-----------------------------------------------------+   |
|   | Candidate Keys                                      |   |
|   |   (Minimal superkey: removing any attribute breaks  |   |
|   |    uniqueness)                                      |   |
|   |                                                     |   |
|   |   +---------------------------------------------+   |   |
|   |   | Primary Key                                 |   |   |
|   |   |   (The chosen candidate key; cannot be NULL)|   |   |
|   |   +---------------------------------------------+   |   |
|   +-----------------------------------------------------+   |
+-------------------------------------------------------------+

1. Superkey (SK)

A set of attributes K ⊆ R such that for any two distinct tuples t1, t2 ∈ r(R), t1[K] != t2[K].
Example: For student(id, name, email, tot_cred), {id}, {id, name}, and {id, email, tot_cred} are all superkeys.

2. Candidate Key (CK)

A superkey K that is minimal—meaning no proper subset of K is a superkey. If any attribute is removed from K, uniqueness is lost.
Example: If both id and email are unique, then {id} is a candidate key and {email} is another candidate key. {id, email} is a superkey, but not a candidate key.

3. Primary Key (PK)

The candidate key chosen by the database architect as the principal means of identifying tuples within the relation.
Rule: Primary key attributes can never accept NULL values (Entity Integrity Constraint).

4. Foreign Key (FK) & Referential Integrity

A set of attributes FK in a referencing relation r1 that matches the primary key PK of a referenced relation r2.

• Referential Integrity Constraint: For every tuple t1 ∈ r1, either:
  1. t1[FK] is NULL (if permitted), or
  2. There exists a tuple t2 ∈ r2 such that t1[FK] = t2[PK].

4. University Schema Relationships

erDiagram
    DEPARTMENT ||--o{ INSTRUCTOR : employs
    DEPARTMENT ||--o{ STUDENT : enrolls
    DEPARTMENT ||--o{ COURSE : offers
    INSTRUCTOR ||--o{ TEACHES : conducts
    INSTRUCTOR ||--o{ ADVISOR : advises
    STUDENT ||--o{ ADVISOR : has
    STUDENT ||--o{ TAKES : completes
    COURSE ||--o{ SECTION : instantiates
    SECTION ||--o{ TEACHES : taught_by
    SECTION ||--o{ TAKES : enrolled_in
    COURSE ||--o{ PREREQ : requires

5. Review Exercises & Conceptual Questions