n-ary Relations & Relational Databases
n-ary relations, domains and degree, the relational data model, records and fields, primary and composite keys, extension vs intension, and the selection, projection and join operators.
▶Lecture videos
Click any timestamp — here or inside the notes — to jump the video to that moment. Your position is remembered.
Introduction to n-ary Relations
From pairs to n-tuples: the "sum to" relation and the phone contacts example.
00:13n-ary relations extend binary relations; the foundation of relational databases00:40Binary recap: "less than" as a set of pairs01:09A triple relation: "sum to" (a + b = c)02:27Every tuple in a relation has the same length; n-ary relations and n-tuples03:00Tuples can come from different sets (names × phone numbers)04:23Key idea: a set of n-tuples from a cross product of n setsLesson 10 – n-ary Relations
Main lesson.
01:40Definition 1: n-ary relations02:52Example 10.1.204:17Example 10.1.307:11The relational data model09:33Extension and intension of a database10:47Primary keys: student names as identifiers12:26Example 10.2.2: composite keys16:21Definition 2: the selection operator19:36Definition 3: projection20:29Example 10.3.2: projection P1,321:58Example 10.3.324:34Example 10.3.429:21Example 10.3.5: the join operator31:38Self-assessment exercises1From pairs to n-tuples
Relationships often involve more than two things:
- a patient's name, height and weight
- a product's name, item number, manufacture date, expiry date and price
- three integers in increasing order
These are especially common in database management systems.
"Less than" is a set of pairs like (0, 1). But a relation can involve triples. The sum to relation S holds for (a, b, c) when a + b = c:
- (2, 2, 4) ∈ S
- (0, 1, 1) ∈ S
- (5, −2.1, 2.9) ∈ S
S ⊆ ℝ × ℝ × ℝ. Within one relation, every tuple has the same length 02:27.
Let A₁, A₂, …, Aₙ be sets. An n-ary relation on these sets is a subset of A₁ × A₂ × ⋯ × Aₙ.
- The sets A₁, …, Aₙ are the domains of the relation.
- n is its degree.
- The elements are ordered n-tuples (tuples).
The domains don't have to be the same set. A phone contact list relates names to phone numbers, a subset of Names × Numbers 03:00.
Examples
| Example | Relation | In R | Not in R | Degree / domains |
|---|---|---|---|---|
| 10.1.1 | (a, b, c) ∈ ℕ³ with a < b < c | (1, 2, 3) | (2, 4, 3) | 3; all ℕ |
| 10.1.2 | (a, b, c) ∈ ℤ³ forming a geometric progression (b = ar, c = ar², r integer) | (2, 6, 18): r = 3 | (3, 6, 24): 6/3 = 2 ≠ 4 = 24/6 | 3; all ℤ |
| 10.1.3 | (x, y, m) with m ≥ 1 and x ≡ y (mod m) | (8, 2, 3), (−1, 9, 5), (14, 0, 7) | (7, 2, 3), (−2, −8, 5), (11, 0, 6) | 3; ℤ, ℤ, ℤ⁺ |
| 10.1.4 | Flights (A, N, S, D, T, U): airline, flight no., start, destination, departure time, duration | (SriLankan Airlines, 302, Colombo, Singapore, 07:25, 04:00) | — | 6; airlines, numbers, cities, cities, times, durations |
2Databases & the relational data model
- Databases constantly add, delete, update, search and combine records, thousands of times a day. How data is stored decides how fast that is.
- The relational data model represents a database as an n-ary relation.
| Term | Meaning |
|---|---|
| Record | An n-tuple |
| Field | One entry of the tuple (an attribute) |
| Table | How the relation is displayed: each column = an attribute, each row = a record |
Table 10.2.1: students (4-tuples)
| Student_name | Student_index_number | Area_of_specialization | GPA |
|---|---|---|---|
| Ackermann | 231455 | Computer Science | 3.88 |
| Adams | 888323 | Physics | 3.45 |
| Chou | 102147 | Computer Science | 3.49 |
| Goodfriend | 453876 | Mathematics | 3.45 |
| Rao | 678543 | Mathematics | 3.90 |
| Stevens | 786576 | Psychology | 2.99 |
3Primary keys, composite keys, extension & intension
A domain is a primary key if its value uniquely determines the n-tuple: no two tuples share that value.
A Cartesian product of domains whose combined values uniquely identify each tuple.
| Field | Primary key? | Why |
|---|---|---|
| Student_name | ✓ (in this extension) | All names are different |
| Student_index_number | ✓ | All unique |
| Area_of_specialization | ✗ | Computer Science and Mathematics repeat |
| GPA | ✗ | 3.45 repeats |
| Area × GPA | ✓ composite key | No two rows share both area and GPA |
| Term | Meaning |
|---|---|
| Extension | The current collection of tuples, which changes as records are added or deleted |
| Intension | The permanent part: the database's name and attributes |
Being a primary key is time-dependent: new records may break uniqueness. So choose keys that work for all possible extensions, by looking at the intension.
- The index number is a good key (no two students ever share one).
- The name is a bad key (two students can share a name).
4Operations: selection, projection, join
Selection Sᴄ (Definition 2)
The selection operator Sᴄ maps a relation R to the relation of all tuples in R that satisfy condition C. It picks rows.
- C₁: Area = "Computer Science" → (Ackermann, 231455, Computer Science, 3.88) and (Chou, 102147, Computer Science, 3.49)
- C₂: GPA > 3.5 → Ackermann and Rao
- C₃: Area = "Computer Science" ∧ GPA > 3.5 → (Ackermann, 231455, Computer Science, 3.88) only
Projection Pi₁, i₂, …, iₘ (Definition 3)
The projection Pi₁,…,iₘ (with i₁ < i₂ < … < iₘ) maps (a₁, …, aₙ) to (ai₁, …, aiₘ). It keeps columns and deletes n − m of them.
- P₁,₃ on (2, 3, 0, 4) gives (2, 0).
- P₁,₃ on (Jane Doe, 234111001, Geography, 3.14) gives (Jane Doe, Geography).
- P₁,₄ on Table 10.2.1 keeps Student_name and GPA (Table 10.3.1).
If tuples differ only in the deleted columns, they become identical after projection and merge into one. Table 10.3.2 has 8 rows (Glauser ×3, Marcus ×3, Miller ×2, one per course). P₁,₂ (Student, Area) gives only 3 rows: Glauser–Biology, Marcus–Mathematics, Miller–Computer Science.
Join
The join combines two tables on identical fields into one table.
Example 10.3.5: join Teaching_assignments (Lecturer, Department, Course_code) with Class_schedule (Department, Course_code, Venue, Time) on the common fields Department and Course_code. The result is Table 10.3.6 (Lecturer, Department, Course_code, Venue, Time).
Expect:
- Listing tuples in an n-ary relation (e.g. 0 < a < b < c < 5)
- Stating the degree and domains
- Finding primary and composite keys in a table, and judging likely keys (student ID: yes; name and phone: no; ISBN for books)
- Performing selection, projection (watch for merged rows) and join
5Quick revision sheet
| Concept | Remember it as |
|---|---|
| n-ary relation | Subset of A₁ × ⋯ × Aₙ; domains Aᵢ; degree n |
| Tuple length | Fixed within a relation |
| Relational model | Records = n-tuples; fields = entries; displayed as tables |
| Primary key | One field that uniquely identifies tuples (index number) |
| Composite key | A combination of fields (Area × GPA) |
| Extension / intension | Current tuples / permanent name + attributes |
| Selection Sᴄ | Keep rows satisfying C (CS ∧ GPA > 3.5 → Ackermann) |
| Projection Pi… | Keep columns; rows may merge |
| Join | Combine tables on common fields (Department, Course_code) |
?Self-check quiz
11 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.