DBMS

The Relational Model

Relational Algebra

So the output of any operation can be the input

JrCodex·7 min read

Jr Codex DBMS Notes

Level: Beginner–Intermediate Prerequisites: Chapter 2: Keys and Constraints Time to complete: ~20 minutes

Table of Contents

  1. Why an Algebra
  2. Selection and Projection
  3. The Set Operations
  4. Cartesian Product and Join
  5. Rename, Grouping and Division
  6. Composing Queries
  7. Why This Makes Optimisation Possible
  8. Summary & Next Steps

1. Why an Algebra

Relational algebra is a small set of operations that take relations as input and produce relations as output.

The Closure Property
─────────────────────────────────────────
  Every operation returns a RELATION.

  So the output of any operation can be the input
  to the next, without limit. This is why queries
  compose — subqueries, nested joins, CTEs all
  work for this one reason.

  Same idea as functions returning the same type
  they consume.
─────────────────────────────────────────

Six Primitives
─────────────────────────────────────────
  σ  SELECTION       choose ROWS
  π  PROJECTION      choose COLUMNS
  ∪  UNION           rows in either
  −  DIFFERENCE      rows in the first, not second
  ×  CARTESIAN       every pairing
  ρ  RENAME          rename a relation or attribute

  Everything else — joins, intersection, division —
  is DEFINED in terms of these six.
─────────────────────────────────────────

2. Selection and Projection

The two most common operations, and the two most often confused.

SELECTION  σ (sigma) — filters ROWS
─────────────────────────────────────────
  σ_condition(R)

  σ_city='Pune'(students)

  ┌────┬───────┬───────┬───────┐
  │ 1  │ Asha  │ Pune  │  88   │
  │ 3  │ Meera │ Pune  │  91   │
  └────┴───────┴───────┴───────┘
  Same columns. Fewer rows.

PROJECTION  π (pi) — chooses COLUMNS
─────────────────────────────────────────
  π_attributes(R)

  π_name,city(students)

  ┌───────┬───────┐
  │ Asha  │ Pune  │
  │ Ravi  │ Delhi │
  │ Meera │ Pune  │
  └───────┴───────┘
  Same rows. Fewer columns.
─────────────────────────────────────────

The Detail People Miss
─────────────────────────────────────────
  Projection REMOVES DUPLICATES, because the result
  is a set (Chapter 1).

    π_city(students)  ──►  {Pune, Delhi}   — 2 rows,
                            not 3

  SQL's SELECT does NOT deduplicate by default —
  you need SELECT DISTINCT. This is one of the
  places SQL departs from the algebra (Chapter 4).
─────────────────────────────────────────

# The algebra, in Python, to make the shapes concrete.
def select(rel, predicate):                 # σ
    return {t for t in rel if predicate(t)}
 
def project(rel, indices):                  # π
    return {tuple(t[i] for i in indices) for t in rel}    # set ──► dedupes
 
students = {(1,"Asha","Pune",88), (2,"Ravi","Delhi",74), (3,"Meera","Pune",91)}
 
print(select(students, lambda t: t[2] == "Pune"))    # 2 tuples
print(project(students, [2]))                        # {('Pune',), ('Delhi',)} — 2, not 3

3. The Set Operations

Union Compatibility
─────────────────────────────────────────
  ∪, ∩ and − require both relations to have:
    - the same NUMBER of attributes
    - corresponding attributes from the same
      DOMAINS

  You cannot union students with courses. You can
  union two relations of student names.
─────────────────────────────────────────

The Three
─────────────────────────────────────────
  UNION         R ∪ S    in R, or S, or both
  INTERSECTION  R ∩ S    in both
  DIFFERENCE    R − S    in R but not S

  INTERSECTION is not primitive:
      R ∩ S  =  R − (R − S)

  DIFFERENCE is the one that expresses NEGATION —
  "students not enrolled in anything" — and it is
  the hardest to express and the slowest to
  compute.
─────────────────────────────────────────

4. Cartesian Product and Join

CARTESIAN PRODUCT  ×
─────────────────────────────────────────
  R × S  pairs EVERY tuple of R with EVERY tuple
  of S.

  |R| = 1,000 and |S| = 1,000  ──►  1,000,000 rows

  Almost never what you want alone. It is the raw
  material joins are built from — and an
  accidental Cartesian product is the classic
  cause of a query that never finishes.

THETA JOIN  ⋈_condition
─────────────────────────────────────────
  R ⋈_c S  =  σ_c(R × S)

  Pair everything, then keep only pairs satisfying
  the condition. Conceptually. No real database
  materialises the product first (Module 6).

NATURAL JOIN  ⋈
─────────────────────────────────────────
  Joins on ALL commonly-named attributes, and
  removes the duplicated column.

  students ⋈ enrollments
    joins on student id automatically

  Elegant in theory, risky in practice: add a
  column named `created_at` to both tables and the
  join silently changes meaning. Prefer an explicit
  condition.

OUTER JOINS
─────────────────────────────────────────
  Inner join DROPS tuples with no match. Outer
  joins KEEP them, padding with NULL.

  LEFT   ⟕   keep all of R
  RIGHT  ⟖   keep all of S
  FULL   ⟗   keep all of both

  "Students with their enrollments, INCLUDING
  students enrolled in nothing" is a left outer
  join — and the NULLs it produces are how you
  find them.
─────────────────────────────────────────

5. Rename, Grouping and Division

RENAME  ρ (rho)
─────────────────────────────────────────
  ρ_new(R)  or  ρ_new(a→b)(R)

  Needed for SELF-JOINS: to join students to
  students, one copy must be renamed, or the
  attribute names are ambiguous.

GROUPING AND AGGREGATION  γ (gamma)
─────────────────────────────────────────
  γ_city; COUNT(id)→n (students)

  Not part of the original algebra — the original
  had no aggregates — but standard in extended
  versions, and it is what SQL's GROUP BY compiles
  to.

DIVISION  ÷
─────────────────────────────────────────
  Answers "for ALL" questions.

  "Students enrolled in EVERY course"
      = π_student,course(enrollments) ÷ π_course(courses)

  Rare, and worth recognising because SQL has no
  division operator. It must be written as a
  double NOT EXISTS — the notorious
  "no course exists that this student is not
  enrolled in".
─────────────────────────────────────────

6. Composing Queries

A Full Query, Built Up
─────────────────────────────────────────
  "Names of Pune students scoring above 80, and
   the titles of courses they are enrolled in."

  π_name,title(
      σ_city='Pune' ∧ marks>80 (students)
      ⋈_students.id = enrollments.student_id
      enrollments
      ⋈_enrollments.course_id = courses.id
      courses
  )

  Read it inside out: filter, then join, then join,
  then keep two columns.
─────────────────────────────────────────

Order Matters for SPEED, Not for RESULT
─────────────────────────────────────────
  These two produce IDENTICAL results:

    σ_city='Pune'(students ⋈ enrollments)
    (σ_city='Pune'(students)) ⋈ enrollments

  The second filters BEFORE joining, so the join
  processes far fewer rows.

  That rewrite is called PUSHING DOWN THE
  SELECTION, and it is the single most valuable
  optimisation a query planner performs.
─────────────────────────────────────────

7. Why This Makes Optimisation Possible

This is why a whole chapter of algebra earns its place in a practical curriculum.

The Chain of Reasoning
─────────────────────────────────────────
  1. Relational algebra has ALGEBRAIC LAWS, like
     ordinary arithmetic:

       σ_a(σ_b(R))  =  σ_b(σ_a(R))     commutative
       σ_a(R ⋈ S)   =  σ_a(R) ⋈ S       pushdown
                        (when a only mentions R)
       π_x(π_y(R))  =  π_x(R)           when x ⊆ y
       R ⋈ S        =  S ⋈ R            commutative

  2. These laws are PROVABLE, because relations are
     sets and the operations are set operations.

  3. So the optimiser can transform your query into
     a different expression and KNOW the result is
     identical.

  4. Which means it can search for the CHEAPEST
     equivalent expression — the subject of
     Module 6.
─────────────────────────────────────────

The Payoff, Stated Plainly
─────────────────────────────────────────
  You write a query in whatever order reads
  clearly. The database rewrites it into something
  potentially very different, and is
  MATHEMATICALLY CERTAIN the answer is unchanged.

  That certainty is what the algebra buys, and it
  is why the declarative promise from Module 1 is
  keepable rather than aspirational.
─────────────────────────────────────────

8. Summary & Next Steps

Key Takeaways

  • Every operation takes relations and returns a relation, and that closure property is why queries compose without limit.
  • Selection filters rows, projection chooses columns and removes duplicates — SQL's SELECT does not deduplicate, which is a deliberate departure.
  • Joins are Cartesian product plus selection conceptually; outer joins keep unmatched tuples padded with NULL, which is how you find "rows with nothing matching".
  • The algebra's provable laws let the optimiser rewrite a query into a cheaper equivalent and be certain the result is identical — pushing selections below joins being the highest-value rewrite.

Concept Check

  1. π_city(students) on a 3-row table returns 2 rows. Why, and what does SQL do differently?
  2. Write out why σ_city='Pune'(students ⋈ enrollments) and (σ_city='Pune'(students)) ⋈ enrollments give the same answer but different performance.
  3. Why can an optimiser reorder your joins without risking a wrong answer?

Next Chapter

→ Chapter 4: From Algebra to SQL

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index