Relationship Set

In the previous page, we explored what a relationship is—a meaningful association between entity instances. But individual relationships don't exist in isolation. When we say "students enroll in courses," we're not describing a single connection between one student and one course. We're describing a pattern of connections that applies across many students and many courses.

This pattern, this collection of all relationship instances of the same type, is called a Relationship Set. Understanding relationship sets is crucial because they bridge the conceptual world of ER diagrams to the physical world of database tables. When you draw a diamond labeled "ENROLLS_IN" on an ER diagram, you're defining a relationship set. When that diagram becomes a database, that relationship set becomes either a foreign key column or an entire junction table.

A Relationship Set is the complete collection of all relationship instances of a particular relationship type at a given point in time. Just as an entity set is a collection of all entities of the same type, a relationship set is a collection of all relationship instances sharing the same structure and meaning.

Formal Definition:

Let E₁, E₂, ..., Eₙ be entity sets and R be a relationship type involving these entity sets. The relationship set of R is:

R = { (e₁, e₂, ..., eₙ) | e₁ ∈ E₁ ∧ e₂ ∈ E₂ ∧ ... ∧ eₙ ∈ Eₙ ∧ relationship holds }

In simpler terms: R is the set of all tuples where each tuple represents entities that are actually related.

Key Properties of Relationship Sets:

1. Homogeneity: All instances in a relationship set have the same structure—same participating entity types, same relationship meaning.

2. Time-Variance: The contents of a relationship set change over time as new relationships form and old ones dissolve. Alice may enroll in new courses or drop existing ones.

3. Subset Property: A relationship set is always a subset of the Cartesian product of its entity sets. Not every possible combination exists, only those where the relationship actually holds.

4. Unique Identification: Each relationship instance in the set is uniquely identified by the combination of participating entity identifiers (unless the relationship allows duplicates, which is rare).

Abstract definitions become concrete through visualization. Let's see what a relationship set actually looks like with real data.

Example: University Course Enrollment

Consider two entity sets:

• STUDENT = {(S101, Alice, 3.8), (S102, Bob, 3.2), (S103, Charlie, 3.5), (S104, Diana, 3.9)}
• COURSE = {(C201, Database Systems), (C202, Algorithms), (C203, Networks)}

The ENROLLS_IN relationship set might contain:

ENROLLS_IN = {
    (S101, C201),    -- Alice enrolled in Database Systems
    (S101, C202),    -- Alice enrolled in Algorithms  
    (S102, C201),    -- Bob enrolled in Database Systems
    (S102, C203),    -- Bob enrolled in Networks
    (S103, C202),    -- Charlie enrolled in Algorithms
    (S104, C201),    -- Diana enrolled in Database Systems
    (S104, C202),    -- Diana enrolled in Algorithms
    (S104, C203),    -- Diana enrolled in Networks
}

Visual Representation:

    STUDENT                ENROLLS_IN               COURSE
    ┌─────────┐                                   ┌───────────────────┐
    │ S101    │─────────────────┬────────────────▶│ C201 (Databases)  │
    │ Alice   │─────────────────│────┬───────────▶│ C202 (Algorithms) │
    └─────────┘                 │    │           └───────────────────┘
    ┌─────────┐                 │    │           ┌───────────────────┐
    │ S102    │─────────────────┤    │───────────▶│ C203 (Networks)   │
    │ Bob     │─────────────────│────┼───────────▶│                   │
    └─────────┘                 │    │            └───────────────────┘
    ┌─────────┐                 │    │
    │ S103    │─────────────────│────┘
    │ Charlie │                 │
    └─────────┘                 │
    ┌─────────┐                 │
    │ S104    │─────────────────┴────────────────▶ (all three courses)
    │ Diana   │
    └─────────┘

Relationship Set Cardinality:

The cardinality of a relationship set (how many instances it contains) is determined by actual data, not by schema constraints. Schema constraints (like 1:N or M:N) specify the maximum possible cardinality patterns, but the actual count depends on real-world enrollment.

In our example:

• |ENROLLS_IN| = 8 (eight enrollment instances)
• Maximum possible = |STUDENT| × |COURSE| = 4 × 3 = 12
• Density = 8/12 ≈ 67% of possible combinations exist

Just as entity sets have schemas (the template defining their structure), relationship sets have schemas too. The relationship set schema defines the structure that all instances in the set must follow.

Components of a Relationship Set Schema:

Schema Notation Example:

Relationship Set: ENROLLS_IN
├── Participating Entity Sets:
│   ├── STUDENT (role: student)
│   └── COURSE (role: course)
├── Cardinality: M:N (many-to-many)
├── Participation:
│   ├── STUDENT: Partial (not all students must enroll)
│   └── COURSE: Partial (not all courses must have enrollees)
├── Attributes:
│   ├── enrollment_date: DATE
│   ├── grade: VARCHAR
│   └── status: ENUM('active', 'withdrawn', 'completed')
└── Key: (student_id, course_id)

This schema tells us everything needed to understand the relationship set's structure without looking at actual data.

Every relationship set needs a way to uniquely identify its instances. This is where relationship keys come in. Understanding relationship keys is essential because they determine how relationship sets are implemented in physical databases.

The Fundamental Rule:

The key of a relationship set is derived from the keys of its participating entity sets. How they combine depends on the relationship's cardinality.

Key Derivation by Cardinality:

Detailed M:N Key Analysis:

For many-to-many relationships, understanding why both keys are needed is crucial:

ENROLLS_IN instances:
(S101, C201) -- Alice in Databases
(S101, C202) -- Alice in Algorithms  
(S102, C201) -- Bob in Databases

• Using only student_id as key? S101 appears twice → not unique → fails
• Using only course_id as key? C201 appears twice → not unique → fails
• Using (student_id, course_id) together? Each combination unique → works

This composite key guarantees that a student can't be enrolled in the same course twice simultaneously, which is usually the desired constraint.

Weak Entity Considerations:

When a weak entity participates in a relationship, its full identifier (including the owner's key) may be needed:

Relationship: LOGS (between EMPLOYEE and WORK_ENTRY)

WORK_ENTRY is weak, identified by EMPLOYEE + entry_number

Key of LOGS relationship:
└── Just WORK_ENTRY's full key: (employee_id, entry_number)
    └── This already includes employee_id implicitly

The identifying relationship that creates the weak entity dependency is a special case—it's inherent to the weak entity's existence rather than an association with independent meaning.

Cardinality constraints are rules that limit how many relationship instances each entity can participate in. These constraints are part of the relationship set schema and are enforced by the database.

Understanding Min-Max Notation:

Modern ER modeling often uses (min, max) notation on each side of a relationship:

EMPLOYEE ─(0,N)──── WORKS_IN ────(1,1)─ DEPARTMENT

Reading this:

• Employee side: (0,N) = An employee participates in 0 to N instances → Each employee can work in at most N departments (typically N=1 in practice), and might work in zero (optional)
• Department side: (1,1) = A department participates in exactly 1 instance... wait, that doesn't make sense for this example.

Correct interpretation:

EMPLOYEE ─(1,1)──── WORKS_IN ────(1,N)─ DEPARTMENT

• Each employee works in exactly 1 department: (1,1)
• Each department has at least 1, possibly many employees: (1,N)

How Cardinality Affects Relationship Set Content:

1:1 Example (MANAGES)

MANAGES = {
    (E001, D01),  -- CEO manages Executive
    (E002, D02),  -- CTO manages Technology
    (E003, D03),  -- CFO manages Finance
}

Each employee appears at most once. Each department appears at most once.

1:N Example (WORKS_IN)

WORKS_IN = {
    (E001, D01),
    (E002, D01),  -- Same department, different employees
    (E003, D01),
    (E004, D02),
    (E005, D02),
}

Each employee appears exactly once. Departments can appear multiple times.

M:N Example (ENROLLS_IN)

ENROLLS_IN = {
    (S01, C01),
    (S01, C02),  -- Same student, different courses
    (S02, C01),  -- Same course, different students
    (S02, C03),
}

Students and courses can both appear multiple times.

Relationship sets, like entity sets, support various operations that modify their contents or query their structure. Understanding these operations helps in both database design and application development.

Basic Operations:

Advanced Query Operations:

Join Operations: Relationship sets enable joining entity sets to get combined information:

-- Conceptually: Combine STUDENT, ENROLLS_IN, and COURSE
-- to get student names with their course names

FOR EACH (s_id, c_id) IN ENROLLS_IN:
    student = STUDENT.get(s_id)
    course = COURSE.get(c_id)
    OUTPUT (student.name, course.title)

Aggregation Operations:

-- Count enrollments per student
GROUP ENROLLS_IN BY student_id
COUNT instances per group

-- Average enrollments per course
GROUP ENROLLS_IN BY course_id
AVERAGE(count per group)

Path Operations: Relationship sets can be traversed to follow chains:

-- Find all students in the same courses as Alice
FOR (alice_id, course_id) IN ENROLLS_IN WHERE student = Alice:
    FOR (other_student, course_id) IN ENROLLS_IN:
        IF other_student ≠ Alice:
            COLLECT other_student

ER diagrams use specific visual conventions to represent relationship sets. Understanding these conventions allows you to read and create accurate diagrams.

Chen Notation (Classic ER):

   ┌──────────┐         ┌────────────┐         ┌──────────┐
   │ STUDENT  │─────────◇ ENROLLS_IN ◇─────────│  COURSE  │
   │          │         │            │         │          │
   │  ▪ id    │         │  ▪ date    │         │  ▪ id    │
   │  ▪ name  │         │  ▪ grade   │         │  ▪ title │
   └──────────┘         └────────────┘         └──────────┘
        │                     │                     │
     Entity              Relationship            Entity
       Set                   Set                   Set

Key conventions:

• Rectangles = Entity Sets
• Diamonds = Relationship Sets
• Lines connect relationship diamonds to participating entity rectangles
• Relationship attributes attach directly to the diamond

Cardinality Notation Styles:

1. Letter Notation (Chen original):

EMPLOYEE ────── N ──◇── 1 ────── DEPARTMENT
(Read: N employees to 1 department = Many-to-One)

2. Crow's Foot Notation (popular in industry):

EMPLOYEE ──────┤├────── DEPARTMENT
                │
         │├ = "many" (crow's foot)
         ─○ = optional (zero or more)
         ─| = mandatory (exactly one)

3. (Min, Max) Notation (most precise):

EMPLOYEE ─(1,1)────◇───(1,N)─ DEPARTMENT
(Each employee in exactly 1 dept; each dept has 1+ employees)