Relations (Mathematics)

Definition

Let $A$ and $B$ be sets. A binary relation from $A$ to $B$ is a subset of $A\times B$, where $\times$ denotes Cartesian product

Functions as Relations

A function $f$ from a set $A$ to a set $B$ can be seen as a binary relation from $A$ to $B$, where every element in $A$ is related to exactly one element in $B$

Relations on a Set

A relation on a set $A$ is a relation from $A$ to $A$, which is simply a subset of $A\times A$

Properties

Reflexive

A relation $R$ on a set $A$ is called reflexive if$(a,a)\in R$ for every element $a\in A$.

Symmetric

A relation $R$ on a set $A$ is called symmetric if $(a,b)\in R⟹(b,a)\in R$.

A relation $R$ on a set $A$ is called antisymmetric if for all $a,b\in A$, $(a,b)\in R\wedge (b,a)\in R⟹a=b$.

A relation $R$ on a set $A$ is called asymmetric if there is no $a,b\in A$, such that $(a,b)\in R\wedge (b,a)\in R$.

Transitive

A relation $R$ on a set $A$ is called transitive if $(a,b),(b,c)\in R⟹(a,c)\in R$

Property	Set Restriction
Reflexive	$I_A\subset R$
Non-reflexive	$R\cap I_A=\varnothing$
Symmetric	$R=R^{-1}$
Antisymmetric	$R\cap R^{-1}=I_A$
Asymmetric	$R\cap R^{-1}=\varnothing$
Transitive	$R\circ R\subset R$
where $R^{-1}=\left\{(b,a)\mid (a,b)\in R\right\}$

Combing Relations

Composition

Let $R$ be a relation from a set $A$ to a set $B$, and $S$ a relation from $B$ to a set $C$. The composite of $R$ and is the relation of ordered pairs $(a,c)$, where $a\in A,c\in C$, and for which there exists an element $b\in B$ such that $(a,b)\in R$ and $(b,c)\in S$. We denote the composite of $R$ and $S$ by $S\circ R$

Power

Let $R$ be a relation on the set $A$. The powers $R^n$, $n=1,2,3,\dots ,$ are defined recursively by

$$R^1=R,R^{n+1}=R^n\circ R$$

The relation $R$ on a set $A$ is transitive if and only if $R^n\subset R$ for $n=1,2,3,\dots$

$n$-ary Relations

Definition

Let $A_1,A_2,\dots ,A_n$ be sets. An $n$-ary relation on these sets is a subset of $A_1\times A_2\times \cdots \times A_n$. The sets $A_1,A_2,\dots ,A_n$ are called the domains of the relation, and $n$ is called its degree

Operators

Selection

Let $R$ be an $n$-ary relation and $C$ a condition that elements in $R$ may satisfy. Then the selection operator $s_C$ maps the $n$-ary relation $R$ to the $n$-ary relation of all $n$-tuples from $R$ that satisfy the condition $C$.

Projection

The projection $P_{i_1,i_2,\dots ,i_m}$ where $i_1<i_2<\cdots <i_m$, maps the $n$-tuple $(a_1,a_2,\dots ,a_n)$ to the $m$-tuple $(a_{i_1},a_{i_2},\dots ,a_{i_m})$, where $m\le n$.

Join

Let $R$ be a relation of degree $m$ and $S$ a relation of degree $n$. The join $J_p(R,S)$ where $p\le m$ and $p\le n$, is a relation of degree $m+n-p$ that consists of all $(m+n-p)$-tuples $(a_1.a_2,\dots ,a_{m-p},c_1,c_2,\dots ,c_p,b_1,b_2,\dots ,b_{n-p})$, where the $m$-tuple $(a_1,a_2,\dots ,a_{m-p},c_1,c_2,\dots ,c_p)$ belongs to $R$ and the $n$-tuple $(c_1,c_2,\dots ,c_p,b_1,b_2,\dots ,b_{n-p})$ belongs to $S$.

Association Rules from Data Mining

Count

The count of an itemset $I$, denoted by $\sigma (I)$, in a set of transaction $T=\left\{t_1,t_2,\dots ,t_k\right\}$ , where $k$ is a positive integer, is the number of transactions that contain this itemset. That is

Support

$$\sigma (I)=\left|\left\{t_i\in T\mid I\subset t_i\right\}\right|$$

The support of an itemset $I$ is the probability that $I$ is included in a randomly selected transaction from $T$. That is,

$$\mathrm{support}(I)=\frac{\sigma (I)}{\left|T\right|}$$

Association Rule

If $S$ is a set of items and $T$ is a set of transactions, an association rule is an implication of the form $I\to J$, where $I$ and $J$ are disjoint subsets of $S$. Use this notation we can define

$$\mathrm{support}(I\to J)=\frac{\sigma (I\cup J)}{\left|T\right|}$$

and

$$\mathrm{confidence}(I\to J)=\frac{\sigma (I\cup J)}{\sigma (I)}$$

Representation of Relations

Matrix Representation

Suppose that $R$ is a relation from $A=\left\{a_1,a_2,\dots ,a_m\right\}$ to $b=\left\{b_1,b_2,\dots ,b_n\right\}$. Then we can use a $m\times n$ matrix $M_R=(m_{ij})$ to represent the matrix, where

$$m_{ij}=\{\begin{array}{ll}1,& \text{if}(a_i,b_j)\in R,\\ 0,& \text{if}(a_i,b_j)\notin R.\end{array}$$

The matrix of a relation on a set, which is a square matrix, can be used to determine whether the relation has certain properties. For example,

• $R$ is reflexive if all the elements on the main diagonal of $M_R$ are equal to $1$
• $R$ is symmetric if and only if $M_R$ is a symmetric matrix, i.e. $M_R=M_R^T$

Since $M_R$ is a 0-1 matrix, we can apply Boolean operations on it:

• $M_{R_1\cup R_2}=M_{R_1}\vee M_{R_2},M_{R_1\cap R_2}=M_{R_1}\wedge M_{R_2}$
• $M_{S\circ R}=M_R\odot M_S$, where $\odot$ is the Boolean product of 0-1 matrix (Pay attention to the order of $R$ and $S$! Otherwise due to the un-match matrix dimensions you cannot perform the matrix multiplication)
• $M_{R^n}=M_R^n$, where the first ${\cdot }^n$ represents the power of relation, and the second ${\cdot }^n$ is the Boolean power of 0-1 matrix

Directed Graph Representation

The relation $R$ on a set $A$ can be represented by the directed graph that has the elements of $A$ as its vertices and order pairs $(a,b)$, where $(a,b)\in R$, as edges. This assignment sets up a one-to-one correspondence between the relations on a set $A$ and their directed graphs with $A$ as their set of vertices.

Similarly, this graph can also be used to determine whether the relation has various properties.

• A relation is reflexive if and only if there is a loop at every vertex of the directed graph
• A relation is symmetric if and only if every edge of the graph is bi-directional.
• A relation is antisymmetric if and only if there are never two edges in opposite directions between distinct vertices.
• A relation is transitive if and only if whenever there is an edge from a vertex $x$ to a vertex $y$ to a vertex $z$, there is an edge from $x$ to $z$. (completing a triangle where each side is a directed edge with the correct direction)

Closures of Relations

Definition

If $R$ is a relation on a set $A$, it may or may not have some property $P$, such as reflexivity, symmetry or transitivity. When $R$ does not enjoy property $P$, we would like to find the smallest relation $S$ on $A$ with property $P$ that contains $R$.

If $R$ is a relation on a set $A$, then the closure of $R$ with respect to $P$, if it exists, is

• The relation $S$ on $A$ with property $P$ that contains $R$
• A subset of every subset of $A\times A$ containing $R$ with property $P$. (Minimum)

If there is a relation $S$ that is a subset of every relation containing $R$ with property $P$, it must be unique.

• Reflexive closure of $R$: $R\cup I_A$
• Symmetric closure of $R$: $R\cup R^{-1}$, where $R^{-1}=\left\{(b,a)\mid (a,b)\in R\right\}$
• Transitive closure of $R$? See below.

Paths in Directed Graphs

A path from $a$ to $b$ in the directed graph $G$ is a sequence of edges $(x_0,x_1),(x_1,x_2),(x_2,x_3),\dots ,(x_{n-1},x_n)$ in $G$, where $n\in \mathbb{N}$ and $x_0=a,x_n=b$. This path is denoted by $x_0,x_1,x_2,\dots ,x_{n-1},x_n$ and has length $n$.

In particular, we view the empty set of edges as a path of length zero from $a$ to $a$. A path of length $n\ge 1$ that begins and ends at the same vertex is called a circuit or cycle.

The term path also applies to relations. There is a path from $a$ to $b$ in $R$ if there is a sequence of elements $a,x_1,x_2,\dots ,x_{n-1},b$ with $(a,x_1)\in R$, $(x_1,x_2)\in R,\dots ,$ and $(x_{n-1},b)\in R$. Then we have the following theorem:

Let $R$ be a relation on a set $A$. There is a path of length $n$, where $n\in {\mathbb{N}}^{\ast }$, from $a$ to $b$ if and only if $(a,b)\in R^n$

Transitive Closures

Connectivity Relation

Let $R$ be a relation on a set $A$. The connectivity relation $R^{\ast }$ consists of these pairs $(a,b)$ such that there is a path of length at least one from $a$ to $b$ in $R$.

Because $R^n$ consists of the pairs $(a,b)$ such that there is a path of length $n$ from $a$ to $b$ (See the last theorem in section Paths in Directed Graphs). It follows that $R^{\ast }$ is the union of all the sets $R^n$. In other words

$$R^{\ast }=\bigcup _{n=1}^{\infty }{R}^n$$

Now we can see that, the transitive closure of a relation $R$ equals the connectivity relation $R^{\ast }$

Optimized Algorithm

How can be compute this relation since it may include $R^{\infty }$? To tackle with this issue, we introduce the following lemma, which is a natural result from The Pigeonhole Principle

Let $A$ be a set with $n$ elements, and let $R$ be a relation on $A$. If there is a path of length at least one in $R$ from $a$ to $b$, then there is such a path with length not exceeding $n$. Moreover, when $a\ne b$, if there is a path of length at least one in $R$ from $a$ to $b$, then there is such a path with length not exceeding $n-1$.

From this lemma, we can simplify the computation of $R^{\ast }$ as

$$R^{\ast }=\bigcup _{k=1}^n{R}^k$$

In practice, we usually use matrix to represents these relations, so we can compute the 0-1 matrix of the transitive closure of $R$ by

$$M_{R^{\ast }}=\underset{k=1}{\overset{n}{\bigvee }}{M}_R^k$$

Since the computation of a Boolean product takes $O(n^3)$, a fast Boolean power algorithm takes $O(\log n)$. As we can compute the Boolean product $O(n^3)$ and the matrix union $O(n^2)$ in a single step in the fast power algorithm, the total time complexity to compute the transitive closure takes $O(n^3\log n)$

Warshall's Algorithm

This is just a Boolean version of Floyd algorithm. Given the matrix of the initial relation, the algorithm outputs a new matrix indicating the connectivity relation (i.e. transitive relation) of the initial relation.

function Warshall(A): 
	n = number of vertices 
	for k from 1 to n: 
		for i from 1 to n: 
			for j from 1 to n: 
				A[i][j] = A[i][j] or (A[i][k] and A[k][j]) 
	return A

Common Relations

Equivalence Relation Partially Ordered Set