Relations

Posted on Edited on In , , Word count in article: 1.1k Reading time ≈ 4 mins.

Still for the quizzzzz... next week...

  • Discrete mathematics
  • Relations
  • Closures

Definition of Relations

Let and be sets. A binary relation from to is a subset of .

Properties of Relations

Reflexive

A relation on a set is called reflexive if for every element .

Symmetric

A relation on a set is called symmetric if whenever , for all .

Antisymmetric

A relation on a set such that for all , if and , then is called antisymmetric.

  • Notice that antisymmetric is NOT asymmetric

Transitive

A relation on a set is called transitive if whenever and , then , for all .

  • Following is the definitions pick from the exercises

Irreflexive

A relation on the set is irreflexive if for every

Asymmetric

A relation is called asymmetric if implies that .

Combining Relations

Definition

Let be a relation from a set to a set and a relation from to a set .
The composite of and is the relation consisting of ordered pairs , where , and for which there exists an element such that and .
We denote the composite of and by .

Powers

Let be a relation on the set . The powers are defined recursively by

Theorem of transitive 1

The relation on a set is transitive if and only if for .

n-ary Relations

Definition

Let be sets. An -ary relation on these sets is a subset of .
The sets are called the domains of the relation, and is called its degree.

Operations on n-ary Relations

Selection

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

Projection
  • Projections are used to form new -ary relations by deleting the same fields in every record of the relation.

The projection where , maps the -tuple to the m-tuple , where .

  • In other words, the projection deletes of the components of an -tuple, leaving the and components.

  • Fewer rows may result when a projection is applied to the table for a relation. This happens when some of the -tuples in the relation have identical values in each of the m components of the projection, and only disagree in components deleted by the projection.

Join
  • The join operation is used to combine two tables into one when these tables share some identical fields.

Let be a relation of degree and a relation of degree . The join , where and , is a relation of degree that consists of all -tuples , where the -tuple belongs to and the -tuple belongs to .

  • In other words, the join operator produces a new relation from two relations by combining all -tuples of the first relation with all -tuples of the second relation, where the last components of the -tuples agree with the first components of the -tuples.

Closures of Relations

Different Types of Closures

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

Definition

If is a relation on a set , then the closure of with respect to , if it exists, is the relation on with property that contains and is a subset of every subset of containing with property .

Transitive Closures

Let be a relation on a set . The connectivity relation consists of the pairs such that there is a path of length at least one from to in .

Theorem of transitive 2

The transitive closure of a relation equals the connectivity relation .

Zero–one matrix of the transitive closure of the relation R

Let be the zero–one matrix of the relation R on a set with n elements. Then the zero–one matrix of the transitive closure is

It's implement

ALGORITHM 1 A Procedure for Computing the Transitive Closure.
procedure transitive closure ( : zero–one matrix)


for to


return  { is the zero–one matrix for }

Warshall’s Algorithm

ALGORITHM 2 Warshall Algorithm.
procedure Warshall ( : zero–one matrix)

for to
for to
for to

return { is }

Cpp implement

  • This is the implement of the relation matrix class
RelationMatrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class RelationMatrix {
 public:
  pair<ll, ll> shape;
  vector<vector<ll>> values;

  RelationMatrix() = default;

  RelationMatrix(const ll rowsize, const ll colsize)
      : shape(rowsize, colsize), values(rowsize, vector<ll>(colsize, 0)) {}

  RelationMatrix& operator+(RelationMatrix& mat) {
    RelationMatrix* res = new RelationMatrix(mat.shape.first, mat.shape.second);
    if (!(mat.shape.first == shape.first && mat.shape.second == shape.second)) {
      throw invalid_argument("Wrong mat shape for add operation.");
      exit(-1);
    }
    for (ll i = 0; i < mat.shape.first; ++i) {
      for (ll j = 0; j < mat.shape.second; ++j) {
        res->values[i][j] = mat.values[i][j] + values[i][j] > 0 ? 1 : 0;
      }
    }
    return *res;
  }

  RelationMatrix& operator*(RelationMatrix& mat) {
    RelationMatrix* res = new RelationMatrix(mat.shape.first, mat.shape.second);
    if (!(mat.shape.second == shape.first)) {
      throw invalid_argument("Wrong mat shape for multiply operation.");
      exit(-1);
    }
    for (ll i = 0; i < shape.first; ++i) {
      for (ll k = 0; k < mat.shape.second; ++k) {
        for (ll j = 0; j < mat.shape.first; ++j) {
          res->values[i][k] =
              res->values[i][k] + values[i][j] * mat.values[j][k] > 0 ? 1 : 0;
        }
      }
    }
    return *res;
  }

  void clear() {
    for (ll i = 0; i < shape.first; ++i) {
      for (ll j = 0; j < shape.second; ++j) {
        values[i][j] = 0;
      }
    }
  }

  void unitify() {
    if (shape.first != shape.second) {
      throw invalid_argument("Not a n by n RelationMatrix.");
    }
    clear();
    for (ll i = 0; i < shape.first; ++i) {
      values[i][i] = 1;
    }
  }
};
  • This is the naive algorithm
naive algorithm
1
2
3
4
5
6
7
8
9
RelationMatrix naiveAlgo(RelationMatrix M) {
  RelationMatrix A = M;
  RelationMatrix B = A;
  for (ll i = 2; i <= M.shape.first; ++i) {
    A = A * M;
    B = B + A;
  }
  return B;
}
  • And this is warshall's algorithm
warshall
1
2
3
4
5
6
7
8
9
10
11
12
RelationMatrix warshall(RelationMatrix M) {
  RelationMatrix W = M;
  for (int k = 0; k < W.shape.first; k++) {
    for (int i = 0; i < W.shape.first; i++) {
      for (int j = 0; j < W.shape.first; j++) {
        W.values[i][j] =
            W.values[i][j] + (W.values[i][k] * W.values[k][j]) > 0 ? 1 : 0;
      }
    }
  }
  return W;
}