From Algebra to SQL

Jr Codex DBMS Notes

Level: Beginner–Intermediate Prerequisites: Chapter 3: Relational Algebra Time to complete: ~15 minutes

Table of Contents

1. The Translation Table
2. Reading a Query as Algebra
3. Where SQL Departs from the Model
4. The Logical Order of Evaluation
5. Summary & Next Steps

1. The Translation Table

2. Reading a Query as Algebra

SELECT DISTINCT s.name, c.title
FROM students s
JOIN enrollments e ON s.id = e.student_id
JOIN courses c     ON e.course_id = c.id
WHERE s.city = 'Pune' AND s.marks > 80;

The Same Query, as Algebra
─────────────────────────────────────────
  π_name,title(
      σ_city='Pune' ∧ marks>80 (
          students ⋈_s.id=e.student_id enrollments
                   ⋈_e.course_id=c.id  courses
      )
  )

  SELECT DISTINCT  ──►  π
  FROM / JOIN      ──►  ⋈
  WHERE            ──►  σ
  AS (s, e, c)     ──►  ρ
─────────────────────────────────────────

The Useful Habit
─────────────────────────────────────────
  When a query returns the wrong rows, translate it
  back to algebra in your head:

    "which σ is filtering?"
    "is this a ⋈ or an accidental ×?"
    "am I projecting before or after the filter?"

  Most wrong-result bugs are a selection applied at
  the wrong point, or a join condition that is
  missing — which turns ⋈ into ×.
─────────────────────────────────────────

3. Where SQL Departs from the Model

SQL is not a faithful implementation of the algebra. Four differences matter in practice.

1. TABLES ARE BAGS, NOT SETS
─────────────────────────────────────────
  SQL permits duplicate rows unless a key forbids
  them, and SELECT keeps duplicates.

  WHY: deduplication requires sorting or hashing
  the entire result — expensive, and usually
  unnecessary. SQL made you ask for it.

  CONSEQUENCE: use UNION ALL rather than UNION when
  you know there are no duplicates. It skips the
  dedup pass entirely and is substantially faster.

2. COLUMN ORDER IS SIGNIFICANT
─────────────────────────────────────────
  SELECT * returns columns in schema order, and
  INSERT without a column list depends on it.

  The algebra says attribute order is meaningless.
  SQL disagrees, which is why both of those
  constructs break when a column is added.

3. THREE-VALUED LOGIC
─────────────────────────────────────────
  NULL makes comparisons UNKNOWN (Chapter 1), so
  SQL's WHERE is not simple boolean logic.

  A consequence worth knowing:
    NOT IN (subquery containing a NULL) returns NO
    ROWS, ever. Use NOT EXISTS instead.

4. ORDER BY AND LIMIT
─────────────────────────────────────────
  Relations are unordered, so ORDER BY is outside
  the algebra entirely — it converts a relation
  into a LIST on the way to the client.

  This is why ORDER BY is only valid at the very
  end of a query, not inside a subquery where it
  would be meaningless.
─────────────────────────────────────────

-- Difference 1, in practice:
SELECT city FROM students;                 -- duplicates kept: Pune, Delhi, Pune
SELECT DISTINCT city FROM students;        -- the algebra's π: Pune, Delhi
 
-- Difference 3, the NOT IN trap:
SELECT * FROM students
WHERE id NOT IN (SELECT student_id FROM enrollments);
-- If ANY student_id is NULL, this returns ZERO rows.
 
SELECT * FROM students s
WHERE NOT EXISTS (SELECT 1 FROM enrollments e WHERE e.student_id = s.id);
-- Correct regardless of NULLs. Prefer this form.

4. The Logical Order of Evaluation

SQL is written in one order and evaluated in another. Knowing the real order resolves most beginner confusion.

Written Order  vs  Logical Order
─────────────────────────────────────────
  WRITTEN            LOGICAL (what happens)
  ─────────────────────────────────────────
  SELECT             1. FROM / JOIN
  FROM               2. WHERE
  WHERE              3. GROUP BY
  GROUP BY           4. HAVING
  HAVING             5. SELECT
  ORDER BY           6. DISTINCT
  LIMIT              7. ORDER BY
                     8. LIMIT
─────────────────────────────────────────

Three Confusions This Explains
─────────────────────────────────────────
  "Why can't I use a SELECT alias in WHERE?"
    WHERE runs at step 2; the alias is created at
    step 5. It does not exist yet.

  "What is the difference between WHERE and HAVING?"
    WHERE filters ROWS before grouping (step 2).
    HAVING filters GROUPS after (step 4). So
    WHERE cannot see aggregates, and HAVING can.

  "Why CAN I use a SELECT alias in ORDER BY?"
    ORDER BY runs at step 7, after SELECT has
    created it.
─────────────────────────────────────────

-- Fails: `total` does not exist at WHERE time.
SELECT city, COUNT(*) AS total FROM students
WHERE total > 1 GROUP BY city;
 
-- Correct: filter GROUPS with HAVING.
SELECT city, COUNT(*) AS total FROM students
GROUP BY city HAVING COUNT(*) > 1
ORDER BY total DESC;          -- but the alias IS available here

The Performance Corollary
─────────────────────────────────────────
  WHERE runs before grouping; HAVING runs after.

  So a condition that could be written either way
  belongs in WHERE — it discards rows before the
  expensive grouping step, rather than after.
─────────────────────────────────────────

5. Summary & Next Steps

Key Takeaways

• Every SQL clause maps onto an algebra operation, and translating a misbehaving query back into algebra usually locates the bug — most often a missing join condition turning ⋈ into ×.
• SQL uses bags rather than sets, so SELECT keeps duplicates and UNION ALL is faster than UNION when you know there are none.
• NOT IN against a subquery containing NULL returns no rows at all; NOT EXISTS is the correct form.
• SQL is evaluated in a different order than it is written, which explains why aliases work in ORDER BY but not WHERE, and why filters belong in WHERE rather than HAVING when either would work.

Module 2 Complete — What's Next

You have the formal model: relations, keys, constraints, and the algebra SQL compiles to. Module 3 turns that into fluent, practical SQL — the language you will actually spend your time writing.

Concept Check

1. Why does SELECT city FROM students return three rows where π_city(students) returns two?
2. A query filters on WHERE total > 1 where total is a SELECT alias, and errors. Explain using the logical evaluation order.
3. When both would produce the same result, why should a condition go in WHERE rather than HAVING?

Next Module

→ Module 3: SQL Fundamentals

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