Further Reading: Relations

Annotated pointers for going deeper. Start with the textbook sections to firm up the four properties and the partition theorem, then branch toward whichever payoff pulls you: the relational-database story, the graph/closure algorithms, or the abstract-algebra view of equivalence and order.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), Chapter 9 ("Relations") The market-standard treatment: representing relations, the properties, equivalence relations and partitions, closures (including Warshall's algorithm), and n-ary relations with a database section. Its exercise bank is large and well-graded — the place to go for more drill than this chapter provides.

Epp, Discrete Mathematics with Applications (5th ed.), the relations chapters A notably careful, example-first development of equivalence relations and partitions, with unusually clear proofs of the equivalence-class/partition correspondence. Excellent if §12.4's theorem still feels slippery.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.) Freely available. A free, readable open textbook; its treatment of relations and equivalence classes pairs well with this chapter and costs nothing. Good for a second explanation in different words.

On equivalence, order, and partitions

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the relations and partial-orders chapters Freely available. The most CS-flavored presentation: equivalence relations and partial orders developed with the same "why a programmer needs this" spirit as our book, including the order-theory you'll meet again in Chapter 13. Highly recommended as a companion.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), the sections on Stirling and Bell numbers For the counting sequel to §12.4: how many partitions (equivalently, equivalence relations) does an n-element set have? Denser, but it is where the Bell numbers from Exercise 12.29 come from. Save it for after Part III's counting chapters.

On closures, reachability, and Warshall's algorithm

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), the all-pairs shortest-paths chapter The canonical reference for the Floyd–Warshall family. Read it to see how the transitive-closure idea of §12.5 generalizes to shortest paths — the same triple-nested-loop structure, with $\min/+$ in place of $\lor/\land$. This is the production answer to "how do I close a big relation fast."

Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.), the section on equivalence relations and partitioning A rigorous, classic account of equivalence relations and the algorithms (including union-find) that compute their classes — directly relevant to Case Study 2's deduplicator. For readers who want the algorithmic depth behind "extract the partition."

On the relational model (the §12.6 payoff)

Codd, "A Relational Model of Data for Large Shared Data Banks," Communications of the ACM (1970) Often freely available. The founding paper of relational databases — the document behind the chapter's epigraph. Short, historic, and surprisingly readable; it is striking to see joins and keys described as pure relation operations, exactly as §12.6 does, before SQL existed.

Suggested order

  1. Re-read §§12.3–12.5 here, then do Rosen Chapter 9's exercises for drill on the four properties and closures.
  2. Read Epp's equivalence-relations chapter (or Levin's, free) for a second take on the partition theorem, then attempt the Deep Dive converse proof (Exercise 12.34).
  3. For the database thread, skim Codd's 1970 paper alongside §12.6 — it makes the "tables are relations" claim land.
  4. For the algorithms thread, read CLRS on Floyd–Warshall after Exercise 12.35 (Warshall), and Knuth on equivalence/union-find alongside Case Study 2.
  5. Save Concrete Mathematics on Bell numbers for after Part III (counting).