Learning objectives
By the end of this week you can:
- 1 Represent relations as sets of pairs, matrices and directed graphs.
- 2 Test reflexivity, symmetry, antisymmetry and transitivity.
- 3 Find equivalence classes and explain partitions.
- 4 Classify functions as injective, surjective or bijective, and compose and invert them.
- 5 Explain hash functions and collisions in terms of functions.
★ the wow moment
A relational database is literally a set of relations.
Edgar Codd built the relational model in 1970 directly on this week's definitions. Every table you query is a relation, and every key constraint is a statement about functions.
Topics
- Relations and representations
- Properties of relations
- Equivalence relations and partitions
- Functions, domain, codomain, range
- Injective, surjective, bijective
- Composition and inverses; floor and ceiling
Before class
- Skim Rosen 2.3, 9.1, 9.5 (20 minutes is enough; we go through it together).
- Bring paper and a pen: part of every lecture is solving by hand.
In industry
-
Relational databases
Tables are relations; primary keys make them functions from key to row.
-
Hash tables
A hash function maps keys to buckets. It cannot be injective, which is why collisions must be handled.
-
Version control
Git's commit history is a relation (“is an ancestor of”) that is reflexive, antisymmetric and transitive: a partial order.
Lab 8: Relation Properties and Hashing
Check properties of relations, compute equivalence classes and transitive closure, and measure hash collisions.
due Fri, Nov 27 · 23:59 · 100 points · opens in week 10
Go deeper
- Mathematics for Computer Science (Lehman, Leighton, Meyer) · Chapters 4.3–4.4, 10
- Book of Proof (Richard Hammack) · Chapters 11–12, relations and functions
- Discrete Mathematics: An Open Introduction (Oscar Levin) · Section 0.4, functions
Tags:relationequivalence relationpartial orderfunctionbijectionhash