Relational Model and Relational Algebra

TL;DR

The relational model organizes data into tables (relations) with rows (tuples) and columns (attributes), forming the foundation of most modern databases. Relational algebra provides a formal set of operations to manipulate and query this data. Understanding these concepts helps you write efficient and precise database queries.

1. The Mental Model

Think of your data as a collection of spreadsheets, where each sheet is a table. Relational algebra gives you a toolbox of actions you can perform on these sheets to combine, filter, and extract exactly the data you need.

2. The Core Material

The relational model is all about structuring data. It defines how data is represented, stored, and retrieved.

• Relation (Table): A set of tuples (rows). It's like a spreadsheet.
• Tuple (Row): A single record in a relation.
• Attribute (Column): A named characteristic or property of the relation. Each attribute has a domain (a set of allowed values).
• Schema: The definition of a relation, including its name and attributes with their domains. Example: Students(StudentID, Name, Major).
• Key: An attribute (or set of attributes) that uniquely identifies each tuple in a relation.
  • Primary Key: A chosen candidate key to uniquely identify tuples. Must be unique and not null.
  • Foreign Key: An attribute (or set of attributes) in one relation that refers to the primary key of another relation, establishing a link.

Relational Algebra is a procedural query language that operates on relations and produces relations as output. It forms the theoretical basis for SQL.

Fundamental Relational Algebra Operations

Photo by Lum3n on Pexels

1. Selection (σ - sigma)

This operation filters tuples (rows) based on a given condition.
σ_condition(Relation)

2. Projection (π - pi)

This operation selects specific attributes (columns) from a relation, removing duplicate rows if they result from the projection.
π_attributes(Relation)

3. Union (∪)

Combines two relations, R and S, producing a new relation containing all tuples from both. Both relations must be union-compatible (have the same number of attributes, and corresponding attributes must have compatible domains).
R ∪ S

4. Set Difference (-)

Returns tuples present in R but not in S. Also requires union-compatibility.
R - S

5. Cartesian Product (×)

Combines every tuple from relation R with every tuple from relation S. If R has m tuples and S has n tuples, the result has m * n tuples. This operation is often the first step in joining relations.
R × S

Derived Relational Algebra Operations

Photo by Nothing Ahead on Pexels

These can be expressed using the fundamental operations but are common enough to have their own symbols.

1. Join (⋈)

Combines tuples from two relations based on a common attribute or condition. It's essentially a Cartesian product followed by a selection.
R ⋈_condition S

• Theta Join: R ⋈_condition S - General join where condition can be any valid comparison.
• Equijoin: R ⋈_A=B S - A theta join where the condition is an equality check on common attributes.
• Natural Join (⋈): R ⋈ S - An equijoin on all common attributes, removing duplicate columns. This is very common.

2. Intersection (∩)

Returns tuples common to both relations R and S. Requires union-compatibility.
R ∩ S (Equivalent to R - (R - S))

3. Division (÷)

This is used for "for all" type queries, like "find parts supplied by all suppliers." It's the most complex. If R has attributes A and B, and S has attribute B, then R ÷ S finds A values that are associated with all B values in S.

graph TD
    A["Relations (Tables)"] --> B{Relational Algebra Operations};
    B --> C["Selection (σ)"]
    B --> D["Projection (π)"]
    B --> E["Union (∪)"]
    B --> F["Set Difference (-)"]
    B --> G["Cartesian Product (×)"]
    B --> H["Join (⋈)"]
    B --> I["Intersection (∩)"]
    B --> J["Division (÷)"]
    C & D & E & F & G & H & I & J --> K["New Relation (Table)"]

3. Worked Example

Let's say we have two relations:

Students:
| StudentID | Name | Major |
| :-------- | :------ | :---- |
| 101 | Alice | CS |
| 102 | Bob | EE |
| 103 | Charlie | CS |

Courses:
| CourseID | Title | Department |
| :------- | :---------------- | :--------- |
| CS101 | Intro to CS | CS |
| EE205 | Digital Logic | EE |
| CS201 | Data Structures | CS |

Enrolled: (Records which student is in which course)
| StudentID | CourseID | Grade |
| :-------- | :------- | :---- |
| 101 | CS101 | A |
| 101 | CS201 | B |
| 102 | EE205 | C |
| 103 | CS101 | B |

Problem: Find the names of students majoring in 'CS' who are enrolled in 'CS101'.

1. Select CS majors:
   R1 = σ_Major='CS'(Students)
   Result R1:
   | StudentID | Name | Major |
   | :-------- | :------ | :---- |
   | 101 | Alice | CS |
   | 103 | Charlie | CS |

2. Select enrollments in CS101:
   R2 = σ_CourseID='CS101'(Enrolled)
   Result R2:
   | StudentID | CourseID | Grade |
   | :-------- | :------- | :---- |
   | 101 | CS101 | A |
   | 103 | CS101 | B |

3. Natural Join R1 and R2 on StudentID: This connects students to their CS101 enrollments.
   R3 = R1 ⋈ R2 (or R1 ⋈_StudentID=StudentID R2)
   Result R3:
   | StudentID | Name | Major | CourseID | Grade |
   | :-------- | :------ | :---- | :------- | :---- |
   | 101 | Alice | CS | CS101 | A |
   | 103 | Charlie | CS | CS101 | B |

4. Project student names:
   Result = π_Name(R3)
   Final Result:
   | Name |
   | :------ |
   | Alice |
   | Charlie |

This shows how you break down a complex query into smaller, manageable relational algebra operations.

4. Key Takeaways

• The relational model structures data into tables, rows, and columns, using keys to define relationships.
• Relational algebra provides a formal, procedural way to query and manipulate relations.
• Fundamental operations include Selection (filter rows), Projection (filter columns), Union, Set Difference, and Cartesian Product.
• Derived operations like Join, Intersection, and Division simplify common query patterns.
• Every relational algebra operation takes one or two relations as input and produces a new relation as output.
• Understanding relational algebra helps you grasp the logic behind SQL queries.

Common Mistakes to Avoid:
* Forgetting that Union, Set Difference, and Intersection require union-compatible relations.
* Confusing selection (rows) with projection (columns).
* Misunderstanding the "all" concept when trying to use division.
* Performing a Cartesian product when a join is more appropriate and efficient.

5. Now Try It

Given the Students and Enrolled relations from the example, write a relational algebra expression to find the StudentID of all students who are enrolled in any course.

What to do: Think about which operations you'd need to combine information about enrolled students, and then project the necessary attribute.

What success looks like: Your expression should correctly identify StudentID 101, 102, and 103. A possible solution is π_StudentID(Enrolled).