Relations

Math for CS · Axiom Academy

Generalizing functions: how elements of sets can be related A relation on a set A means R A A — pairs are drawn from the same set. You already know many relations without thinking of them that way: A relation on a finite set A = \ a_1, a_2, , a_n\ can be represented as an n n Boolean matrix M : Example: Let A = \ 1, 2, 3\ and R = \ (1,1), (1,2), (2,3), (3,3)\ : A relation on A can be drawn as a directed graph (digraph): each element is a node, and a b is a directed edge from a to b . The digraph for R = \ (1,1), (1,2), (2,3), (3,3)\ shows self-loops at 1 and 3, plus edges 1 2 and 2 3 . Databases: A relational database table is literally a relation — a set of tuples from a Cartesian product of column domains Graphs: An edge set E V V is a relation on vertices Object inheritance: "class A extends B" defines a relation on classes File systems: "directory contains file" is a relation on filesystem entries Access control: "user has permission on resource" is a relation on Composition of relations generalizes function composition: there exists some intermediate element b connecting a to c . A relation R A B is any set of ordered pairs from A and B Relations generalize functions — no requirement for unique outputs Representations: sets of pairs, Boolean matrices, digraphs Graphs, databases, inheritance hierarchies are all relations Relation composition corresponds to database joins

This is the written version of the interactive lesson above. See the full Math for CS course.