Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 79 ยท Relational Algebra and Calculus

Division, Aggregation and Extended Operators

Master relational division for 'for all' queries, the double NOT EXISTS pattern in SQL, plus the grouping and aggregate operator and generalized projection.

Some questions sound simple in English and are surprisingly awkward in a query language: "Which students took every course on this list?", "Which suppliers deliver all the parts we need?". These are "for all" questions. The five basic operators (select, project, union, difference, product) can express them, but only through an awkward detour. Relational algebra therefore gives them their own operator, division, and SQL programmers meet them as the double NOT EXISTS pattern.

This lesson also covers the extended operators that real queries need but the classic algebra lacks: aggregation with grouping, and projection that computes new values. They move the algebra from a theory of sets to something that looks like actual SQL.

Relational division

Division R รท S needs a particular shape. Let R have attributes (A, B) and S have attributes (B), where B is a set of attributes that R and S share. Then R รท S returns the values of A that appear in R together with every B value in S.

Reading R รท S

R (A, B) Pairs, such as student and course taken.
S (B) The list that must all be covered.
R รท S The A values paired with every B in S.

Answers "for all" questions.

1 / 2

The three steps in the second slide are the whole definition:

TEXT
R รท S  =  ฯ€A(R)  โˆ’  ฯ€A( (ฯ€A(R) ร— S) โˆ’ R )

Read it as a story. Take every A value that appears in R. Pair each with every B in S: that is what would exist if everyone were complete. Subtract the pairs that actually exist: what remains are the missing pairs. Any A value with at least one missing pair fails the "for all" test, so remove those A values from the starting list. The survivors are the answer.

Here is a concrete case in the school dataset. The relation R is the set of distinct (student, course) pairs from enrollments, and S is the set of two courses CS100 and CS210. The question: which students took both? The next query follows the three steps literally, using SQL set operators.

SQL Division built from product and difference ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

The answer has 17 students: 1, 3, 4, 5, 9, 12, 15, 18, 19, 20, 21, 22, 23, 24, 27, 31 and 32. That matches the 17 students you found by intersecting two rosters in Union, Intersection, Difference and Cartesian Product. With only two courses an intersection is enough; division generalizes to a list of any length, which can even be computed from another table.

Division in SQL: the double NOT EXISTS

SQL has no DIVIDE operator. The idiom that replaces it is a logical rewrite: "there is no required course for which there is no enrollment of this student".

SQL Students enrolled in all of the listed courses ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

The result is the same 17 students. Read the nesting from the outside in: a student qualifies if the set of courses they are missing is empty. It is a double negation, and it is why the pattern looks unnatural at first. Changing the course list changes the query. Remove the IN (...) filter to ask for students enrolled in every course in the table and the answer is empty, because nobody took CS300: one unreachable course in S is enough to empty the result.

A second approach counts instead of negating. It is easier to read, but it relies on the pairs being unique, which is why count(DISTINCT ...) matters:

SQL Division by counting ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

Again 17 rows. Both forms are valid. The counting version is shorter, and the NOT EXISTS version is closer to the algebra, and usually the safest when the list can contain duplicates.

Aggregation and grouping

The classic algebra has no way to count or average, because a tuple is just a value in a set. The aggregate operator (written with the letter gamma, ฮณ) adds it:

TEXT
ฮณ grouping attributes ; aggregate functions ( R )

It groups the tuples of R by the grouping attributes and produces one output tuple per group, with one column per aggregate (COUNT, SUM, AVG, MIN, MAX). With no grouping attributes the whole relation is one group, and the result has a single tuple.

TEXT
ฮณ course_id ; COUNT(*) โ†’ n, AVG(grade) โ†’ avg_grade ( enrollments )

This is exactly SQL's GROUP BY. The grouping attributes appear in the output together with the aggregates.

SQL The aggregate operator is GROUP BY ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

There are nine rows, not ten: CS300 has no enrollments, so no group exists for it. Groups come from tuples that exist. If you need a row for empty groups too, you must start from courses and use an outer join. A second subtlety: avg(grade) ignores NULL grades (the table has 299 enrollments but only 275 graded), so the count and the average can describe different sets of rows.

SQL Aggregates without grouping, and nulls inside them ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

Generalized projection

The ordinary projection ฯ€ only picks columns. Generalized projection lets the list contain expressions over the attributes, such as arithmetic, string functions and constants, each optionally renamed:

TEXT
ฯ€ code, credits * 15 โ†’ contact_hours (courses)

In SQL that is just the select list, which is why a query such as SELECT credits * 15 AS contact_hours is already algebra with an extension.

SQL Generalized projection: computed columns ยท database: school

Press Run (or Ctrl + Enter) to see the result here.

Other extended operators

Real engines add a few more operators beyond the ones in this chapter. You will meet them in query plans.

  • Sorting ฯ„ (ORDER BY): the result is a list, not a set, so it leaves the pure model.
  • Duplicate elimination ฮด (DISTINCT): turns a bag into a set.
  • Outer joins, covered in Joins in Relational Algebra.
  • Limit/top-k, which keeps the first n tuples of a sorted result.

The next lesson builds an interpreter for most of the operators, so you can see them run as ordinary code.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What kind of query is relational division designed for?

    R รท S keeps the A values that appear in R with every B value of S.
  2. 2. In R(A, B) รท S(B), how do you obtain the 'missing' pairs?

    Build every possible (A, B) combination and subtract the ones that really exist. What remains is what each A is missing.
  3. 3. How is division usually written in SQL?

    SQL has no division operator. The double negation 'no required item that is not present' expresses it.
  4. 4. Why does a GROUP BY over enrollments return no row for a course nobody took?

    To list zero-count groups, start from the table of courses and LEFT JOIN the enrollments.
  5. 5. What does generalized projection add to ordinary projection?

    Generalized projection allows arithmetic and functions in the projection list, like a SQL select list.

Summary

  • Division R รท S returns the A values of R(A, B) paired with every B in S(B); it equals ฯ€A(R) โˆ’ ฯ€A((ฯ€A(R) ร— S) โˆ’ R).
  • In SQL, express division with a double NOT EXISTS, or by comparing COUNT(DISTINCT ...) with the size of the required list.
  • The aggregate operator ฮณ groups tuples and applies COUNT, SUM, AVG, MIN, MAX; groups exist only for data that exists.
  • Aggregates skip nulls, so a count of rows and a count of a column may differ.
  • Generalized projection allows computed expressions in the projection list; sorting and duplicate elimination are further extensions.

Next: turn the algebra into running code in Build a Relational Algebra Interpreter.