Sets and Relations

Sets and their notation, union, intersection and difference, Venn diagrams and SQL joins, Cartesian products, and relations with their properties.

Sets and elements

A set is a collection of objects, considered as one thing. The objects in it are its elements. Set theory is the language in which most of mathematics is written, and IT uses it every day without the name: group memberships, firewall object groups, the hosts in a subnet, the rows a query returns.

An element of a set is one of the objects it contains. "x is an element of A" is written x \in A, and "is not an element" is x \notin A. Kestrel Energy's admin group is

\text{admins} = \{\text{amara}, \text{mei}, \text{ravi}\}

so \text{mei} \in \text{admins} and \text{tomasz} \notin \text{admins}. Two properties set sets apart from lists:

  • No order. \{\text{amara}, \text{mei}\} and \{\text{mei}, \text{amara}\} are the same set.
  • No duplicates. An object is either in the set or not; listing it twice changes nothing.

The number of elements is the cardinality, written |A|: |\text{admins}| = 3. The set without elements is the empty set, \varnothing, with |\varnothing| = 0.

Two ways to describe a set

Small sets are written explicitly, by listing the elements between braces. Large or infinite sets are written implicitly, in set-builder notation: a variable, a vertical bar read "such that", and the condition the elements meet.

\{x \in \mathbb{N} \mid x \lt 1024\} \qquad \{x \in \mathbb{R} \mid 1 \lt x \le 3\}

Read the first as "the set of natural numbers x such that x is less than 1024": the 1024 port numbers 0 to 1023. The second is all real numbers greater than 1 and at most 3. The number sets \mathbb{N}, \mathbb{Z}, \mathbb{Q} and \mathbb{R} themselves are described on Numbers and Number Sets. Set-builder notation is also the model for Python's set comprehensions: {p for p in range(65536) if p < 1024} says almost the same in code.

Python's built-in set type behaves like a mathematical set: it drops duplicates and has no order. Turning a list into a set is the standard way to remove duplicates: 

alert_sources = ["portal-01", "db-01", "portal-01", "mail-01", "db-01", "portal-01"]
unique = set(alert_sources)
print(len(alert_sources), len(unique))
print(sorted(unique))
print("db-01" in unique, "web-02" in unique)
print({"amara", "mei"} == {"mei", "amara", "mei"})
6 3
['db-01', 'mail-01', 'portal-01']
True False
True

The output is sorted on purpose: a Python set of strings has no fixed order, and printing it directly can give a different order on every run.

Subsets and the power set

A is a subset of B, written A \subseteq B, when every element of A is also an element of B. Every set is a subset of itself, and the empty set is a subset of every set (there is no element in it that could fail the test: the vacuous truth from Logic and Boolean Algebra). When A \subseteq B and A \ne B, A is a proper subset, sometimes written A \subset B; because books differ on whether \subset allows equality, this page sticks to \subseteq.

In access control, "the permissions of the reader role are a subset of the permissions of the editor role" is a precise way to say that an editor can do everything a reader can.

The set of all subsets of A is its power set. Each element is either in a subset or not: two choices per element. With n elements that makes 2 \cdot 2 \cdots 2 = 2^{n} subsets. This is the same count as the rows of a truth table, and as the patterns of n bits; a bit mask is just a way to store a subset. 

from itertools import combinations

tiers = ["web", "db", "cache"]
subsets = [set(c) for size in range(len(tiers) + 1)
           for c in combinations(tiers, size)]
print(len(subsets), "=", 2 ** len(tiers))
for s in subsets:
    print(sorted(s))

admins = {"amara", "mei", "ravi"}
print({"mei"} <= admins, set() <= admins, admins <= admins)
8 = 8
[]
['web']
['db']
['cache']
['db', 'web']
['cache', 'web']
['cache', 'db']
['cache', 'db', 'web']
True True True

Union, intersection and difference

Three operations build new sets from two existing ones. Take the admins and the people on call this week at Kestrel Energy:

A = \{\text{amara}, \text{mei}, \text{ravi}\} \qquad B = \{\text{mei}, \text{tomasz}, \text{ravi}, \text{sanne}\}
  • The union A \cup B contains everything that is in A, in B, or in both: amara, mei, ravi, sanne, tomasz. Who gets the weekly access review?
  • The intersection A \cap B contains what is in both: mei and ravi. Who can fix a production problem tonight with full rights?
  • The set difference A \setminus B contains what is in A but not in B: amara. Note that the difference is not symmetric: B \setminus A is tomasz and sanne.

Two more are derived from these. The symmetric difference contains what is in exactly one of the two sets (amara, sanne, tomasz): the set version of XOR. And the complement \overline{A} contains everything that is not in A, relative to a universe U that you have to agree on, such as "all Kestrel staff". 

admins = {"amara", "mei", "ravi"}
on_call = {"mei", "tomasz", "ravi", "sanne"}
print(sorted(admins | on_call))      # union
print(sorted(admins & on_call))      # intersection
print(sorted(admins - on_call))      # difference
print(sorted(on_call - admins))
print(sorted(admins ^ on_call))      # symmetric difference
print(len(admins | on_call), len(admins) + len(on_call) - len(admins & on_call))
['amara', 'mei', 'ravi', 'sanne', 'tomasz']
['mei', 'ravi']
['amara']
['sanne', 'tomasz']
['amara', 'sanne', 'tomasz']
5 5

The last line checks a counting rule. Adding |A| and |B| counts the shared elements twice, so you subtract them once:

|A \cup B| = |A| + |B| - |A \cap B| = 3 + 4 - 2 = 5

This is the inclusion–exclusion principle, and it is how you avoid double counting in reports ("tickets about the portal or about billing").

Set operations obey the same laws as the logical connectives on Logic and Boolean Algebra, with \cup for OR, \cap for AND and complement for NOT. That is no coincidence: x \in A \cup B means exactly "x \in A or x \in B". So De Morgan's laws hold for sets too: \overline{A \cup B} = \overline{A} \cap \overline{B}.

Venn diagrams

A Venn diagram draws each set as a closed region, usually a circle, inside a rectangle that stands for the universe. Overlapping regions show every possible combination of membership, so you can read union, intersection and difference off the picture. Named after the logician John Venn, who described them in 1880, they are the quickest way to check a set calculation by eye.

Venn diagram of admins and on call inside a rectangle for all staff. Only admins: amara. Both: mei and ravi. Only on call: tomasz and sanne. Neither: hamid. admins on_call amara mei ravi tomasz sanne hamid A ∩ B U: all staff
Each region is one combination: only admins, both, only on call, neither. Hamid, the database administrator, is in the universe but in neither group.

Two sets give four regions, three sets give eight (again 2^{n}: each region is a choice of "in" or "out" for every set). Beyond three sets, circles can no longer show every combination, and diagrams quickly become unreadable; a table or a query is then the better tool.

Cartesian products and pairs

Sets have no order, but sometimes order matters: the pair (site, tier) is not the pair (tier, site). An ordered pair (a, b) has a first and a second element. The Cartesian product A \times B is the set of all ordered pairs with the first element from A and the second from B:

A \times B = \{(a, b) \mid a \in A,\ b \in B\} \qquad |A \times B| = |A| \cdot |B|

Kestrel Energy runs its portal in two data centers (AMS and GRQ) with three tiers each (web, db, cache). Every combination needs its own monitoring check: 2 \cdot 3 = 6 pairs. 

from itertools import product

sites = ["AMS", "GRQ"]
tiers = ["web", "db", "cache"]
pairs = list(product(sites, tiers))
print(len(pairs))
for site, tier in pairs:
    print(f"check-{site.lower()}-{tier}")
6
check-ams-web
check-ams-db
check-ams-cache
check-grq-web
check-grq-db
check-grq-cache

The name comes from René Descartes, whose coordinate plane is the product \mathbb{R} \times \mathbb{R}: every point is an ordered pair (x, y). In databases the same operation is the cross join, which pairs every row of one table with every row of another.

Sets in SQL

Relational databases are built on set theory, and SQL has the three set operations as keywords. They combine the rows of two queries with the same columns: UNION (union), INTERSECT (intersection) and EXCEPT (difference; Oracle has long called it MINUS).

Worked example: CMDB versus discovery

Amara Okafor compares the hosts in Kestrel Energy's configuration management database (CMDB) with the hosts a network scan found.

  1. Hosts in both lists (the intersection) are fine.
  2. Hosts in the CMDB but not found (CMDB minus discovered) may be switched off or decommissioned without an update.
  3. Hosts found but not in the CMDB (discovered minus CMDB) are unknown devices: a security question. 
CREATE TABLE cmdb (host TEXT);
CREATE TABLE discovered (host TEXT);
INSERT INTO cmdb VALUES ('web-01'), ('web-02'), ('db-01'), ('mail-01');
INSERT INTO discovered VALUES ('web-01'), ('web-02'), ('db-01'), ('cam-07');

SELECT host FROM cmdb INTERSECT SELECT host FROM discovered ORDER BY host;
SELECT host FROM cmdb EXCEPT SELECT host FROM discovered;
SELECT host FROM discovered EXCEPT SELECT host FROM cmdb;
SELECT COUNT(*) AS hosts FROM (SELECT host FROM cmdb UNION SELECT host FROM discovered);
host
------
db-01
web-01
web-02

host
-------
mail-01

host
------
cam-07

hosts
-----
5

UNION removes duplicates, as a set should: 4 + 4 rows become 5 distinct hosts. UNION ALL keeps them, which makes it a list operation rather than a set operation (and faster, because no duplicates have to be found).

Joins are not Venn diagrams

Joins are often drawn as Venn diagrams: an inner join as the overlap, a left join as a whole left circle. That picture is popular but misleading. UNION, INTERSECT and EXCEPT compare rows of the same shape, so a Venn diagram fits them. A join combines rows of different tables into wider rows, and one row can match many. Mathematically an inner join is a Cartesian product filtered by the join condition: all pairs (a, b) \in A \times B for which the condition holds. A left join adds the rows of A that have no partner, and an anti-join returns just those rows, which is the closest a join comes to a set difference.

Relations

Many facts in IT are about pairs: user is member of group, router is directly connected to router, service depends on service. A relation from a set A to a set B is a subset R \subseteq A \times B: the set of pairs that are related. You write (a, b) \in R or, shorter, a \mathrel{R} b. A table in a relational database stores exactly such a set of tuples, which is where the name of the relational model comes from.

For a relation on one set (from A to A itself) three properties decide how it behaves:

  • Reflexive: every element is related to itself, a \mathrel{R} a. "Is in the same subnet as" is reflexive; "is the parent of" is not.
  • Symmetric: if a \mathrel{R} b then b \mathrel{R} a. "Has a direct link to" is symmetric for cables; "depends on" is not.
  • Transitive: if a \mathrel{R} b and b \mathrel{R} c then a \mathrel{R} c. "Can reach" is transitive; "has a direct link to" is not.

Worked example: three routers

Tomasz Nowak models the links between three routers as a relation "is the same router as, or has a direct link to". R1 is cabled to R2, and R2 to R3.

Three routers R1, R2 and R3 in a row. Each has a loop to itself. Double arrows connect R1 with R2 and R2 with R3. A dashed curve from R1 to R3 marks the missing pair: the relation is not transitive. R1 R2 R3 (R1, R3) is missing: not transitive
The relation as a directed graph: an arrow from a to b for every pair (a, b), and a loop for every (a, a).
  1. Reflexive? Each router is related to itself (the loops): yes.
  2. Symmetric? Every link has a pair in both directions: yes.
  3. Transitive? R1 is related to R2 and R2 to R3, but R1 has no direct link to R3: no. One counterexample is enough to break a "for all" rule. 
# The relation as a set of pairs
R = {("R1", "R1"), ("R2", "R2"), ("R3", "R3"),
     ("R1", "R2"), ("R2", "R1"), ("R2", "R3"), ("R3", "R2")}
nodes = {"R1", "R2", "R3"}

reflexive = all((a, a) in R for a in nodes)
symmetric = all((b, a) in R for a, b in R)
transitive = all((a, d) in R for a, b in R for c, d in R if b == c)
print(reflexive, symmetric, transitive)

missing = sorted((a, d) for a, b in R for c, d in R if b == c and (a, d) not in R)
print(missing)
True True False
[('R1', 'R3'), ('R3', 'R1')]

Adding the missing pairs until nothing is missing gives the transitive closure: here, "can reach". Routing protocols compute exactly that kind of reachability; graphs are covered in Graphs and Trees.

Equivalence relations and orders

An equivalence relation is a relation that is reflexive, symmetric and transitive at the same time. It behaves like a relaxed "equals": the elements it relates are the same in one respect. Examples:

  • "has the same file extension as", for files;
  • "is in the same /24 subnet as", for IPv4 addresses;
  • "is congruent modulo n to", for whole numbers (see Modular Arithmetic).

The key fact: an equivalence relation splits its set into equivalence classes, groups in which everyone is related to everyone else, and no element belongs to two groups. Such a split is called a partition. Every subnet mask partitions the address space this way: 

import ipaddress
from collections import defaultdict

hosts = ["192.0.2.10", "198.51.100.7", "192.0.2.200", "203.0.113.5", "198.51.100.99"]

classes = defaultdict(list)
for h in hosts:
    network = ipaddress.ip_interface(h + "/24").network   # the class of h
    classes[network].append(h)

for network in sorted(classes):
    print(network, classes[network])
192.0.2.0/24 ['192.0.2.10', '192.0.2.200']
198.51.100.0/24 ['198.51.100.7', '198.51.100.99']
203.0.113.0/24 ['203.0.113.5']

Each network address is a label for one equivalence class: two hosts are "in the same subnet" exactly when they get the same label. Grouping by a key, in Python or with SQL's GROUP BY, is always a partition by an equivalence relation.

Orders

A second important kind of relation puts things in order instead of grouping them. A partial order is reflexive, transitive and antisymmetric: if a \mathrel{R} b and b \mathrel{R} a, then a = b. Examples are \le on numbers, \subseteq on sets, and "is installed no later than" (or: "equals or must be installed before") on software packages. "Partial" means that some pairs are not comparable at all: neither \{\text{web}\} \subseteq \{\text{db}\} nor the reverse. Package managers and build tools sort dependencies so that this order is respected, and a dependency cycle (A needs B, B needs A) breaks antisymmetry, and then no valid install order exists.