Relations
Relations and Their Properties
Definition of Relations

Relations are formal means to specify which elements from two or more sets are related to each other.
For example, students who takes courses, there are relations between students and courses; integers and their divisors, there are relations between integers and divisors.

Let $A$ and $B$ be two sets. A binary relation $R$ from $A$ to $B$ is a subset of $A×B$.

Generally, let $A_{1},A_{2},A_{3},A_{4},⋯,A_{n}$ be $n$ sets. An nary relation $R$ on these sets is a subset of $A_{1}×A_{2}×⋯A_{n}$.

$aRb$ means that $(a,b)∈R$.
Complementary and Inverse of Relations
 Let $R:A,B$ be any binary relations, the complement of $R$, is the binary relation defined by ${(a,b)∣(a,b)∈R}=(A×B)−R$.
 Any binary relation $R:A×B$, has an inverse relation $R_{−1}:B×A$, which is defined by$R_{−1}:{(b,a)∣(a,b)∈R}$.
Functions as relations
 A function $f,A→B$ is a special case of a relation from $A$ to $B$.
 Relations are a generalization of function.
 Relations allow unmapped elements in $A$.
 Relations allow onetomany mappings.
 Relations also allow manytoone and manytomany mappings.
Relations on a Set
 A binary from a set $A$ to itself is called a relation on the set $A$.
 A relation on a set A is a subset of $A_{2}$.
Properties of Relations
Reflexivity
 A relation $R$ is reflexive if $∀a∈A,aRa$.
 A relation $R$ is irreflexive if its complementary relation is reflexive.
Symmetry
 A binary relation $R$ on $A$ is symmetry if $R=R_{−1}$, that is if $(a,b)∈R↔(b,a)∈R$
 A binary relation $R$ is antisymmetric if $∀a=b,(a,b)∈R→(b,a)∈R$
Transitivity
 A relation $R$ is transitive if $(a,b)∈R∧(b,c)∈R→(a,c)∈R$.
Examples in Mathematics:
reflexive  symmetric  antisymmetric  transitive  

$=$  yes  yes  yes  yes 
$=$  no  yes  no  no 
$∅$  no  yes  yes  yes 
Composition
The composition of two relations $R:A→B$ and $S:B→C$, denoted by $S∘R$, is the relation from $A$ to $C$ containing all pairs $(x,z)$ such that there is one $y∈B$ with $(x,y)∈R$ and $(y,z)∈S$.
Power of a Relation
Composing the Parent relation with itself
Let $R$ be a binary relation on $A$, then the power $R_{n}$ of the relation $R$ can be defined inductively by:
 Basic Step: $R_{1}=R$
 Inductive Step: $R_{n+1}=R_{n}∘R$
Theorem: The relation $R$ on a set A is transitive if $R_{n}⊆R$ for $n=1,2,3,⋯$.
nary Relations and Their Applications
nary Relations
 An nary relation $R$ on sets $A_{1},A_{2},A_{3},⋯,A_{n}$, a subset $R⊆A_{1}×A_{2}×⋯A_{n}$.
 The sets $A_{i}$ are called the domains of $R$.
 The degree of $R$ is $n$.
Relational Database
Database
 A database is viewed as a collection of records, each being a tuple of the form $(value_{1},value_{2},...,value_{n})$.
 In order to uniquely identify tuples in a database, we need to specify a field , which is the primary key.
 Some database may not have primary key, instead they use a composite key made up of multiple fields.
Relational Database
 A model for databases, based on relations.
 A domain $A_{i}$ is a primary key for the database if the relation R is functional in $A_{i}$.
 A composite key for the database is a set of domains $A_{i},A_{j},⋯$, such that $R$ contains at most 1 ntuple $(a_{i},a_{j},⋯)$for each composite value.
Operations on nary relations
 Selection
 Projection
 Join
Representing of Relations
Using ZeroOne Matrices
We can represent a binary relation $R:A×B$ by an $∣A∣×∣B∣$ 01 matrix $M_{R}=[m_{ij}]$, let $m_{ij}=1$ if $(a_{i},b_{j})∈R$.
We can see some relation characteristics in the zeroone matrix.
 Reflexive: all 1 are on diagonal
 Irreflexive: all 0 are on diagonal
 Symmetric: all identical across diagonal
 Antisymmetric: all 1 are across from 0.
Using Directed Graphs
A relation $R:A×B$ can be represented as a graph $G_{R}(V_{G}=A∪B,E_{G}=R)$.
Closures of Relations
Closures
For any property X , the "X closure" of a set A is defined as the smallest superset of A that has the given property.
For example:
 The reflexive closure of relation $R$ on $A$ is obtained by adding $(a,a)$ to $R$ for each $a∈A$, as $R∨I_{A}$.
 The symmetric closure of $R$ is obtained by adding $(b,a)$ to $R$, as $R∨R_{−1}$.
 The transitive closure or connectivity relation of $R$ is obtained by repeatedly adding $(a,c)$ to $R$ for each $(a,b),(b,c)$ in $R$.
Paths in Digraphs
A path of length $n$ from node $a$ to $b$ in the directed graph $G$ is a sequence $(a,x_{1}),(x_{1},x_{2}),⋯,(x_{n−1},b)$ of $n$ ordered pairs in $E_{G}$.
 An empty sequence of edges is considered a path of length 0 from a to a.
 If any path from $a$ to $b$ exists, then we say that a$a$ is connected to $b$.
 A path of length $n≥1$ from a to itself is called a circuit or a cycle.
 There exists a path of length $n$ from $a$ to $b$ in $R$ if and only if $(a,b)∈R_{n}$.
Let R be a relation on a set $A$, the connectivity relation $R_{∗}$ consist of their pairs $(a,b)$ such that there is a path of length at least one from $a$ to $b$ in $R$.
As $R_{n}$ consists of the pairs $(a,b)$ such that there is a path of length $n$ from $a$ to $b$, it follows that $R_{∗}$ is the union of all the sets $R_{n}$.
$R_{∗}=U_{n=1}R_{n}$
Theorem: Let $R$ be a relation on a set $A$, then $R_{∗}$ equals the transitive closure of $R$
$t(R)=R_{∗}=U_{n=1}R_{n}$
But in fact if $A$ is a set with $∣A∣=n$, and let $R$ be a relation on $A$. Then
$U_{n=1}R_{n}$
which is much easier to calculate.
Warshall's Algorithm
As we have seen, using the Theorem and its lemma, it is still difficult to calculate the transitive closure, so we have a algorithm:
procedure Warshall(M, n X n zeroone matrix)
W := M
for k:=1 to n
for j:=1 to n
for j:=1 to n
w[ij] = w[ij]  (W[ik] & W[ki])
return W