Chapter 8
Relations and Their Properties

© Ray Wisman

Resources

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/index.html - Index to the Rosen text Web site learning resources.

http://highered.mcgraw-hill.com/sites/0072880082/student_view0/chapter8/extra_examples.html - Extra examples with solutions.

Introduction

Binary relations define how one thing is related to another.

Owns is a relation that defines how a person relates to an object.

Using mathematics, we define a person and object sets, such as:

person = { Luz, Chad, Josh }

object = { cell, book, car, horse }

And a relation, owns:

owns = { (Luz, horse), (Josh, cell), (Josh, book), (Chad, car) }

 

8.1 Relations and Their Properties

Definition 1

Binary relation from A to B is a subset of A x B.

Example 1

A = {Salem, Louisville}

B = {Indiana, Kentucky}

A x B = {(Salem, Indiana), (Louisville, Indiana), (Louisville, Kentucky),  (Salem, Kentucky)}

R = {(Salem, Indiana), (Louisville, Indiana)}

R ⊆ A x B

R is a binary relation from A to B

Definition

a R b denotes (a, b) ∈ R  a R b denotes (a, b) ∉ R When a R b, a related to b by R.

Example 2

A = {Salem, Nebo}

B = {Indiana, Kentucky}

A x B = {(Salem, Indiana), (Nebo, Indiana), (Nebo, Kentucky),  (Salem, Kentucky)}

R = (city, state) relates city to state

R = (city, state) is a binary relation from city to state.

R = {(Salem, Indiana), (Nebo, Kentucky)}                         "city is in state"

 

Example 3

A = {0, 1, 2}

B = {a, b}

A x B = { (0, a), (1, a), (0, b), (1, b), (2, a), (2, b) }

R = { (0, a), (1, a), (0, b), (2, b) }  ⊆  AxB

{ (0, a), (1, a), (0,  b), (2, b) } is a relation from A to B

 

Question 8.1

Does the figure at left represent a function?

 

Functions as Relations

Definition

Function f from A to B is assignment of exactly one element of B to each element of A. f(a) = b where b is the unique element of B assigned by f to the element a of A. f : A → B

Example

f : Names → Grades

 

Definition

Graph of function f from set A to B is set of ordered pairs { (a,b) | a ∈ A and f(a) = b} Graph of f ⊆ AxB, so is a relation from A to B.

Question 8.2

For figure above:

A= {Adams, Chou, Goodfriend, Rodriguez, Stevens}

B = {A, B, C, D, F}

The graph of the function defines what ordered pairs of AxB?

{ (Adams, A), ... }

 

Example

A = set of all US cities

B = set of all US states

R = (a,b) if city a is in state b

{(Salem, Indiana), (Louisville, Kentucky),  (Salem, Oregon)}

R is not the graph of a function because Salem occurs more than once as the first element.

Definition

Relation R from set A to B has every element in A the first element of exactly one ordered pair (a,b) of R A function can then be defined with R as its graph.

Example

A = Z

B = Z⁺

f(x) = x²

f : A → B is a function

Graph of f exists.

R = {(a, b) | b=a²}

R includes (-5, 25), (5, 25), (-2, 4), (2, 4)

R is the graph of a function because no a∈ A occurs more than once as the first element.

 

Question 8.3

Give the following relations as a set of ordered pairs (tuples).

Which of the following relations are also graphs?

a.

b.

c.

d.

 

Relations on a Set

Definition 2

Relation on the set A is a relation from A to A.

Example

A = {1,2,3,4}

A x A = {(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}

R = {(a,b) | b modulus a = 0}   a divides b relation.

   = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3), (4,4)}

Example

A = Z

R₁ = {(a, b) | a ≤ b}

From {(1,1), (1,2), (2,1), (1,-1), (2,2)}

R₁ contains (1,1), (1,2), (2,2)

Question 8.4

From {(1, 1), (1, 2), (2, 1), (1, -1), (2, 2)}

R₂ = {(a, b) | a > b}

R₂  contains

R₄ = {(a, b) | a = b}

R₄  contains

Example

Recall that R ⊆ A x A.

A x A has n² elements, |A| = n.

A = {a, b, c}

A x A = {(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c)}

|A x A| = |A|² = 3²

Set with m elements has 2^m subsets.

A = {a, b, c} has 2³ subsets

{a, b, c}, {a, b}, {a, c}, {b, c}, {a}, {b}, {c}, ∅

A with n elements.

A x A has n² elements.

A x A has ₂n² subsets.

There are ₂n² relations on a set with n elements.

A = {a, b, c}

|A x A| = 3² = 9 elements in A x A

₂3² = 2⁹ = 512 subsets and relations in A x A.

 

Properties of Relations

Definition 3

Reflexive relation R on A if ∀a∈A, (a, a) ∈ R.

Example   A = {1, 2, 3, 4}

R₁ = {(1, 1), (2, 2), (3, 3), (4, 4)} is reflexive

R₂ = {(1, 1), (2, 2), (3, 3)} is not reflexive, no (4, 4)

R₃ = {(a, b) | a = b} is reflexive

R₃ = {(1, 1), (2, 2), (3, 3), (4, 4)}

R₄ = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2)} is reflexive

R₅ = {(a, a) | a ≤ a} is reflexive

R₅ = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

Question 8.5.1 - Which are reflexive?

R₆ = {(1, 1)}

R₇ = {(2, 3), (1, 1), (2, 2), (3, 3), (4, 4)}

 

Definition 4

Symmetric relation R on A if ∀a∀b∈A, (a, b) ∈ R → (b, a) ∈ R.

Antisymmetric relation R on A if ∀a∀b∈A, (a, b) ∈ R ^ (b, a) ∈ R →  a = b

Example  A = {1, 2, 3, 4}, R ⊆ A x A

R0 = {(1, 2), (2, 3)} is not symmetric, no (2,1) ^ no (3,2)                                 is antisymmetric, no (2,1) v no (3,2) R1 = {(1, 1), (2, 2)} is symmetric and antisymmetric R2 = {(1, 1), (1, 2)} is not symmetric, no (2, 1)                                 is antisymmetric because (1, 1) R3 = {(1, 2), (2, 1)} is symmetric                                 not antisymmetric, (1, 2) ^ (2, 1) but 1≠2 R4 = {(a, b) | a = b} is symmetric and antisymmetric, (1, 1), (2, 2), etc.                                 {(1, 1), (2, 2), (3, 3), (4, 4)}

R1 R2 R3

Question 8.5.2 - Symmetric/Antisymmetric for A = {1, 2, 3, 4}, R ⊆ A x A?

R₆ = {(3, 4), (1,1), (4, 3)}

R₇ = {(1, 3), (2, 3)}

What is: (1, 2) ∈ {(1, 2)} ^ (2, 1) ∈ {(1, 2)} 

What is: False →  1 = 2

R₈ = {(1, 2)}                     

 

Definition 5

Transitive relation R on A if ∀a∀b∀c∈A, (a, b) ∈ R ^ (b, c) ∈ R → (a, c) ∈ R.

Example  A = {1, 2, 3, 4}, R ⊆ A x A

R1 = {(1, 2), (2, 3), (1, 3)} is transitive (1, 2) ∈ R1 ^ (2, 3) ∈ R1 → (1, 3) ∈ R1 R2 = {(1, 2), (2, 3)} is not transitive                                 because (1,3) ∉ R2 R3 = {(1, 1)} is transitive (1, 1) ∈ R3 ^ (1, 1) ∈ R3 → (1, 1) ∈ R3 R4 = {(a, b) | a = b} is transitive R5 = {(2, 3), (3, 4), (3, 2)} is not transitive                                            because (2, 4) ∉ R5

R1 R2 R5

Question 8.6.1 - Transitive for A = {1, 2, 3, 4}, R ⊆ A x A?             

R₆ = {(3, 4), (3, 3), (4, 3)}

R₇ = {(2, 3), (3, 4), (2, 4)}

R₈ = {(1, 2), (2, 3), (1, 3), (3, 1)}

 

Definition 5

Transitive relation R on A if ∀a∀b∀c∈A, (a, b) ∈ R ^ (b, c) ∈ R → (a, c) ∈ R.

Example

A = Z⁺

Is divides operation transitive?

a divides b means that b=ak where k is a positive integer, b is a multiple of a

4 divides 12, where 12 = 4(3)

b = 12

a = 4

k=3

Assume:

a divides b, meaning b = ak

(a, b)

b divides c, meaning c = bj

(b, c)

b = ak c = bj	k and j are positive integers satisfying divides assumptions
c = (ak)j	Substitute b = ak
c = a(kj)	c is a multiple of a, a divides c
(a, c)	divides operation is transitive.

Example

Reflexive relation R on A, if ∀a∈A, (a, a) ∈ R.

Symmetric relation R on A, if ∀a∀b∈A, (a, b) ∈ R → (b, a) ∈ R.

Antisymmetric relation R on A, if ∀a∀b∈A, (a, b) ∈ R ^ (b, a) ∈ R →  a=b.

Transitive relation R on A, if ∀a∀b∀c∈A, (a, b) ∈ R ^ (b, c) ∈ R → (a, c) ∈ R.

Relations on the set A = {1, 2, 3}

	reflexive	symmetric	antisymmetric	transitive
R0 = {(1,1), (2,2), (3,3)}	Yes	Yes	Yes	Yes
R1 = {(2,2), (2,3), (3,2)}	No	Yes	No (2,3) (3,2)	No (3,3)
R2 = {(1,1), (1,2), (2,1), (2,2), (3,3)}	Yes	Yes	No (1,2) (2,1)	Yes
R3 = {(2,3), (3,2)}	No	Yes	No (2,3) (3,2)	No (2,2) (3,3)
R4 = {(1,2), (2,3), (1,3)}	No	No	Yes	Yes

Other relation representations than ordered tuples of relations make determining properties simpler. More later.

 

Combining Relations

Relations from A to B are subsets of A x B and can be combined in any way two sets can be combined.

Example

A = {0, 1, 2}

B = {a, b}

A x B = { (0, a), (1, a), (0, b), (1, b), (2, a), (2, b) }

R₁ = {(0, a), (0, b)}

R₂ = {(0, b), (1, a), (1, b)}

R₁ ∩ R₂ = {(0, b)}

R₁ U R₂ = {(0, a), (0, b), (1, a), (1, b)}

R₁ - R₂ = {(0, a)}

R₂ - R₁ = {(1, a), (1, b)}

R₁ ⊕ R₂ = R₁ U R₂ - R₁ ∩ R₂
             = {(0, a), (0, b), (1, a), (1, b)} - {(0,b)}
             = {(0, a), (1, a), (1, b)}

Example

R (real numbers) is universe of discourse

R₁ = {(a, b) | a < b}

R₂ = {(a, b) | a > b}

R₁ ∩ R₂ =∅

R₁ U R₂ = {(x, y) | x ≠ y}

R₁ - R₂ = R₁

R₂ - R₁ = R₂

R₁ ⊕ R₂ = R₁ U R₂ - R₁ ∩ R₂ = {(x, y) | x ≠ y}

Symmetric difference is those elements in R₁ or R₂  but not both

Question 8.6.2              

R₁ = {(3, 4), (3, 3), (4, 3)}

R₂ = {(3, 3), (3, 4), (2, 4)}

1. R₁ ∩ R₂ =
   
2. R₁ ⊕ R₂ =

    

Definition 6

S ○ R Composite relation of R and S where R from A to B S from B to C is the ordered pairs: (a, c), where a ∈ A and c ∈ C for which b ∈ B such that (a, b) ∈ R ^ (b, c) ∈ S

Example

A = Food = {nuts, salad, water}

B = Fat = {yes, no}

C = Servings = {0, 1, 2}

R = {(nuts, yes), (salad, no), (water, no)}

R from Food to Fat

S = {(yes, 1), (no, 3), (no, 2)}

S from Fat to Servings

S ○ R from Food to Servings

R (nuts, yes) S         (yes, 1)	(salad, no)          (no,3)          (no,2)	(water, no)           (no,3)           (no,2)
S○R    (nuts, 1)	(salad, 3) (salad, 2)	(water, 3) (water, 2)

Question 8.6.3 - Complete the table for: S ○ R

A = {0, 1, 2}

B = {a, b}

C = {X, Y, Z}

R = {(0, a), (1, b), (2, b)}                        R from A to B

S = {(a, X), (b, Y), (a, Z)}                        S from B to C

S ○ R = {(0, X), (0, Z), (1, Y), (2, Y)}        S ○ R from A to C

R (0,a) S    (a, X)       (a, Z)	(1,b)    (b, Y)	(2,b)       ?
S○R       ?	?	?

 

Definition 7

Rn the powers of relation R for n=1,2,3,... are defined by: R1 = R Rn+1 = Rn ○ R

Example

R = {(1, 1), (2, 1), (3, 2), (4, 3)}

R² = R○R

R² contains (a, c) if (a, b) and (b, c) ∈ R.

R (1,1) R    (1,1) (2,1)    (1,1) (3,2)    (2,1) (4,3)    (3,2) R2 (1, 1) (2, 1) (3, 1) (4, 2)

R   R2

R² = {(1, 1), (2, 1), (3, 1), (4, 2)}

R³ = R²○R

R³ contains (a,c) if (a,b) ∈ R² and (b,c) ∈ R.

R2 (1,1) R      (1,1)	(2,1)    (1,1)	(3,1)    (1,1)	(4,2)    (2,1)
R3   (1,1)	(2,1)	(3,1)	(4,1)

R³ = {(1, 1), (2, 1), (3, 1), (4, 1)}

R⁴ = R³ ○ R

R⁴ contains (a,c) if (a,b) ∈ R³ and (b,c) ∈ R.

R3 (1,1) R      (1,1)	(2,1)    (1,1)	(3,1)    (1,1)	(4,1)    (1,1)
(1,1)	(2,1)	(3,1)	(4,1)

R⁴ = {(1, 1), (2, 1), (3, 1), (4, 1)}

Note that R³ = R⁴ = R⁵ = ... = Rⁿ

Question 8.6.4 - Complete the table for: R²

R = {(1, 1), (2, 3), (3, 2), (4, 3)}

R² = R○R

R (1,1) R    (1, 1)	(2,3)    (3, 2)	?	?
R○R       (1, 1)	?	?	?

 

Theorem 1

Transitive relation R on A iff Rn ⊆ R for n=1,2,3,...

Example

R = {(1, 1), (2, 1), (3, 2), (4, 3)}

R² = R ○ R = {(1, 1), (2, 1), (3, 1), (4, 2)} not a subset of R, therefore R not transitive

R (1,1) R    (1,1) (2,1)    (1,1) (3,2)    (2,1) (4,3)    (3,2) R2 (1, 1) (2, 1) (3, 1) (4, 2)

R   R2

R is not transitive because (4, 3), (3, 2) belongs to R but (4,2) does not.

R is not transitive because (3, 2), (2, 1) belongs to R but (3,1) does not.

 

Example

R   = {(1, 1), (2, 1), (3, 1), (4, 1)}

R² = {(1, 1), (2, 1), (3, 1), (4, 1)} ⊆ R

R (1,1) R    (1,1)	(2,1)    (1,1)	(3,1)    (1,1)	(4,1)    (1,1)
R2 (1,1)	(2,1)	(3,1)	(4,1)

R² = R

R is transitive by observing that all Rⁿ ⊆ R

Theorem 1

Transitive relation R on A iff Rn ⊆ R for n=1, 2, 3, ...

Question 8.7

R   = {(1, 2), (2, 3), (1, 3)}

1. What is R²?
   
2. Is R transitive?
   

Definition

R-1 Inverse relation of R from A to B is relation from B to A: R-1 = {(b, a) | (a, b) ∈ R}

Example

A = {0, 1, 2} B = {a, b} R = {(0, a), (1, b), (2, b)} R-1 = {(a, 0), (b, 1), (b, 2)}

R  R-1

Question 8.8

Food = {nuts, salad, water}

Fat = {yes, no}

R = {(nuts, yes), (salad, no), (water, no)}

R from Food to Fat

R^-1 = ?

Definition

R-1 Inverse relation of R from A to B is relation from B to A: R-1 = {(b, a) | (a, b) ∈ R}

 

8.2 n-ary Relations and Their Applications

Introduction

Basis of Relational databases.

Definition 1

n-ary relation on A1, A2, A3,...,An  is a subset of A1 x A2 x A3 x ... x An Domain of the relation is  A1, A2, A3,...,An Degree of the relation is n.

Example

R is the relation of 4-tuple (Student Name, Class, Grade, Room)

R = {(Ray, C251, C+, PS016), (Alice, C105, A-, PS110) }

Domain:

A1 student names

A2 class

A3 possible grades

A4 rooms

Degree is 4.

4-tuple

Example

R is a relation on N x N x N

R = {∀a∀b∀c∈N, (a, b, c) | a < b < c}

(1, 2, 3), (3, 4, 5)         belong to R because 1 < 2 < 3 and 3 < 4 < 5

(3, 4, 2), (3, 3, 3)         do not belong to R because 3 < 4 > 2 and 3 = 3 = 3

Domain is N.

Degree is 3.

3-tuple

 

Databases and Relations

Definitions

Relational data model based on concept of relation. Record consists of a n-tuple. Fields are the n-tuple entries. Table another name for relation. Attribute corresponds to a table column.

Example

4-ary relation

Student_name x ID_number x Major x GPA

(Ackermann, 231455, Computer Science, 3.88)
(Ackermann, 231455, Computer Science, 3.45)
(Ackermann, 888323, Computer Science, 3.49)
                            :

Record

(Student_name, ID_number, Major, GPA) ⊆ Student_name x ID_number x Major x GPA

(Ackermann, 231455,Computer Science, 3.88)

Table - Students

{ (Ackermann, 231455, Computer Science, 3.88),
   (Adams, 888323, Physics, 3.45)                           
       :
}

Fields

Ackermann, 231455, Computer Science, 3.88

Attribute

Student_name, ID_number, Major, GPA

Question 8.9    Table 1

1. What is the degree of the relation?
   
2. What is the domain of the relation?

3. {Adams, 888323, Physics, 3.45} ⊆  Student_name x ID_number x Major x GPA
   
4. {Chou, 888323, Physics, 3.45} ⊆  Student_name x ID_number x Major x GPA

Definitions

Relational data model based on concept of relation. Record consists of a n-tuple. Fields are the n-tuple entries. Table another name for relation. Attribute corresponds to a table column.

Definitions

Primary key is a domain (attribute) of the n-ary relation in which the domain value determines the n-tuple. Primary key values must be unique.

Example

Student_name, ID_number are uniquely defined and could be primary keys.

Domain ID_number is all legal student numbers, each uniquely defined, is a key.

Domain Major is not a key because duplicate Computer Science value.

Question 8.10

Can GPA be a primary key? Explain.

 

Definitions

Extension, the current collection of n-tuples in a relation. Intension includes the database name and attributes, the more permanent part of the database.

Example

Extension

All 4-tuples of Students

Adding or deleting another n-tuple would create a new extension of the relation.

Intension

Students, Student_name, ID_number, Major, GPA

 

Definition

Composite key, domains which in combination uniquely identify n-tuples in an n-ary relation, the Cartesian product of the domains.

Example

Major x GPA

Cartesian product of domain fields Major x GPA for Table 1 is a composite key because while neither domain fields are unique, no 4-tuples have same Major and GPA values.

Major	GPA
Computer Science	3.88
Physics	3.45
Computer Science	3.49
Mathematics	3.45
Mathematics	3.90
Psychology	2.99

Question 8.11

Why would Major x GPA be a bad choice as a composite key?

 

Operations on n-ary Relations

Definition 2

Selection operator sc maps n-ary relation R to the n-ary relation of all n-tuples from R that satisfy the condition C.

Example

R is the relation of Table 1.

Condition C is condition Major="Computer Science"

s_{Major="Computer Science"} 

selection operator on R result is the 4-tuples:

(Ackermann, 231455, Computer Science, 3.88) (Chou, 102147, Computer Science, 3.49)

SQL    s_{Major="Computer Science"}

Select * from Students where Major = "Computer Science"

Question 8.12

s_{GPA > "3.5"}?

 

Definition 3

Projection Pi1i2i3...im where i1<i2<i3<...<im maps the n-tuple (a1,a2,a3,...,an) to the m-tuple (ai1,ai2,ai3,...,aim), where m ≤ n

The projection reduces a n-tuple to a m-tuple.

Example

 P_1,3,5 applied to

1	2	3	4	5	6	7
(a,	b,	c,	d,	e,	f,	g)
(X,	Y,	Z,	A,	B,	C,	D)

is    (a, c, e)
      (X, Z, B)

Example

m=4

P₄

applied to Table 1 ignores columns Student_name, ID_number and Major, leaving unique values of GPA.

SQL

Select GPA from Students.

Leaves all values of GPA, including non-unique.

P4 applied to Table 1 GPA 3.88 3.45 3.49 3.90 2.99

SQL applied to Table 1 GPA 3.88 3.45 3.49 3.45 3.90 2.99

Example

m=2

P_{1, 2}

applied to Table 3, deletes column 3, result is Table 4.

SQL

Select Student, Major from Enrollments.

All Student and Major record entries returned.

Question 8.13

P_2,4         applied to Table 1.

 

Definition 3

Join Jp(R, S) where p≤ m and p≤ n is a relation of degree m+n-p that consists of (m+n-p)-tuples (a1,a2,a3,...,am-p, c1,c2,c3,...,cp, b1,b2,b3,...,bn-p) where the m-tuple (a1,a2,a3,...,am-p, c1,c2,c3,...,cp) belongs to R and the n-tuple (c1,c2,c3,...,cp, b1,b2,b3,...,bn-p) belongs to S. R is a m-degree and S a n-degree relation.

J_p(R, S) produces new relation from R and S relations when tables share identical fields.

The last p components of R and first p components of S agree.

Combines all m-tuples from R with all the n-tuples of S.

Example

J₂

applied to Table 5 and Table 6 results in Table 7.

p=2

m=3 (a1,a2,a3,...,am-p,c1,c2,c3,...,cp) Table 5 - (a1,c1,c2) a1 = Professor c1 = Department c2 = Course_number

n = 4 (c1,c2,c3,...,cp,b1,b2,b3,...,bn-p) Table 6 - (c1,c2,b1,b2) c1 = Department c2 = Course_number b1 = Room b2 = Time

Physics 551 is only in relation Table 5 and Mathematics 611 is only in relation Table 6,
so are not included in the resulting Table 7 relation.

J₂ applied to Table 5 and Table 6 results in Table 7, the relation of:

Table 7 ⊆Professor x Department x Course_number x Room x Time

SQL

SELECT * FROM Teaching_Assignments INNER JOIN Class_Schedule ON

Teaching_Assignments.Department = Class_Schedule.Department AND

Teaching_Assignments.Course_number = Class_Schedule.Course_number

Question 8.14.1

Why does Grammer only occur once in the relation produced J₂ applied to Table 5 and Table 6?

SQL

Structured Query Language

SELECT is a projection.

Example

SELECT Departure_time FROM Flights WHERE Destination = 'Detroit'

Condition and projection applied to Table 8.

s_{Destination = "Detroit"}

Condition C is Destination = 'Detroit'

P₅

m=5

Departure_time

08:10

08:47

09:44

Question 8.14.2   

What is the result on Table 8 of P₃

What is the result of:

SELECT Gate FROM Flights

Example

SELECT Professor, Time FROM Teaching_Assignments INNER JOIN Class_Schedule ON

Teaching_Assignments.Department = Class_Schedule.Department AND

Teaching_Assignments.Course_number = Class_Schedule.Course_number

WHERE Teaching_assignments.Department='Mathematics'

J₂ applied to Table 5 and 6 common fields Department and Course_number, resulting in relation Table 7.

P_1,5 and s_{Department="Mathematics"} condition applied to relation Table 7.

Result is (Rosen, 3:00 P.M.)

P_1,5 and s_{Department="Mathematics"} condition applied to relation Table 7.

Result is (Rosen, 3:00 P.M.)

Question 8.14.3   

What is J₃ applied to Table 1 and 2?

P_1,3,5 applied to the result?

Table 1 1 2 3 a b c X Y Z

Table 2 6 7 c R b G

What is the corresponding SQL?

 

8.3 Representing Relations

Representing Relations Using Matrices

Relation Refresher

Let sets A and B exist and form a binary relation R from A to B, where R ⊆ A x B  the ordered pair (a, b) ∈ R, where a ∈ A, and b ∈ B

Matrix Representation

2-dimensional matrix is used for binary relations

One row for each element of  A

One column for each element of B

Example

A = {0, 1, 2} - number of rows = |A| B = {a, b} - number of columns = |B| R = { (0, a), (1, a), (0, b), (2, b) }  ⊆  A x B

a b 0 1 1 1 1 0 2 0 1

Example - page 538 (Rosen 6e)

A = {1, 2, 3} - number of rows = |A| B = {1, 2} - number of columns = |B| R = { (a, b) | a > b} = {(2, 1), (3, 1), (3, 2)}

1 2 1 0 0 2 1 0 3 1 1

Example

A = {a1, a2, a3} - number of rows = |A| B = {b1, b2, b3, b4, b5} - number of columns = |B| Question 8.15.1 R = ?

b1 b2 b3 b4 b5 a1 0 1 0 0 0 a2 1 0 0 1 0 a3 0 0 1 0 1

 

Question 8.15.2 Complete the matrix for R = {(a1, b1), (a2, b1), (a1, b2), (a2, b2)}

b1 b2 b3 a1       a2       a3

Definitions

A relation on set A is a relation from A to A. R ⊆ A x A A square matrix when the number of rows = number of columns

Example

A = {a1, a2, a3} - number of rows = columns = |A|         R = A x A = {(a1, a1), (a1, a2), (a1, a3),   (a2, a1), (a2, a2), (a2, a3),   (a3, a1), (a3, a2), (a3, a3)}

a1 a2 a3 a1 1 1 1 a2 1 1 1 a3 1 1 1

 

Reflexive relations have all 1's on the diagonal

Example

A = {a1, a2, a3} - number of rows = columns = |A| R = {(a1, a1), (a2, a2), (a3, a3)} Reflexive

a1 a2 a3 a1 1 0 0 a2 0 1 0 a3 0 0 1

Question 8.16

A = {a1, a2, a3} - number of rows = columns = |A| R = {(a1, a1), (a2, a2), (a3, a3), (a2, a3), (a3, a2)} Reflexive?

a1 a2 a3 a1 1 0 0 a2 0 1 1 a3 0 1 1

 

Definition

Symmetric relation R iff ∀i∀j mij = mji

Antisymmetric relation R iff ∀i∀j i≠j ^ mij ≠ mji

Example

R = {(a1,b1)}(a1,b2),(a2,b1),         (a2,b2),(a2,b3),(a3,b2),(a3,b3)} Reflexive because 1s on diagonal. Symmetric because matrix is symmetric. Not antisymmetric.

b1 b2 b3 a1 1 1 0 a2 1 1 1 a3 0 1 1

Question 8.17

R = {(a1,b1)}(a1,b2),(a2,b2)} Symmetric? Antisymmetric? Reflexive?

b1 b2 b3 a1 1 1 0 a2 0 1 0 a3 0 0 0

Question 8.18

R = {(a1,a1),(a2,a2),(a3,a3),(a2,a3),(a3,a2)} Symmetric? Antisymmetric? Reflexive?

a1 a2 a3 a1 1 0 0 a2 0 1 1 a3 0 1 1

Definition

Transitive relation R on A, if ∀a∀b∀c∈A, (a,b) ∈ R ^ (b,c) ∈ R → (a,c) ∈ R.

Example

Transitivity is not so obvious in matrix or graph representations.

R = {(a1, b1), (a2, b1), (a1, b2), (a2, b2)} Transitive. Best seen here by examining only the subscripts in ordered tuples. (2,1) ^ (1,2) → (2,2) (1,2) ^ (2,1) → (1,1)

b1 b2 b3 a1 1 1 0 a2 1 1 0 a3 0 0 0

Definition

MR1 U R2 = MR1 v MR2

MR1 ∩ R2 = MR1 ^ MR2

Example

MR1 1 2 3 1 1 0 0 2 0 1 0 3 0 0 1	MR2 1 2 3 1 1 0 1 2 0 0 0 3 1 0 1
MR1 U R2 1 2 3 1 1 0 1 2 0 1 0 3 1 0 1	MR1 ∩ R2 1 2 3 1 1 0 0 2 0 0 0 3 0 0 1

Question 8.18.1

MR1 1 2 3 1 1 0 0 2 0 0 0 3 1 0 1

MR2 1 2 3 1 1 0 1 2 0 0 0 3 1 0 0

Give the matrices for:

MR1 U R2 = MR1 v MR2

MR1 ∩ R2 = MR1 ^ MR2

Question 8.18.2

Give as tuples ^MR₁ ∩ R₂

 

Definition

Boolean product MS○R =MR¤MS

Example

MR¤MS 1 2 3 1 1 0 1 2 0 0 0 3 0 0 0

=

MR 1 2 1 1 0 2 0 1 3 0 0

¤

MS 1 2 3 1 1 0 1 2 0 0 0

MR¤MS 1 2 3 1 (1^1)v(0^0) (1^0)v(0^0) (1^1)v(0^0) 2 (0^1)v(1^0) (0^0)v(1^0) (0^1)v(1^0) 3 (0^1)v(0^0) (0^0)v(0^0) (0^1)v(0^0)

MR¤MS 1 2 3 1 (R1,1^S1,1)v(R1,2^S2,1) (R1,1^S1,2)v(R1,2^S2,2) (R1,1^S1,3)v(R1,2^S2,3) 2 (R2,1^S1,1)v(R2,2^S2,1) (R2,1^S1,2)v(R2,2^S2,2) (R2,1^S1,3)v(R2,2^S2,3) 3 (R3,1^S1,1)v(R3,2^S2,1) (R3,1^S1,2)v(R3,2^S2,2) (R3,1^S1,3)v(R3,2^S2,3)

Example

MS¤MR 1 2 1 1 1 2 0 0

=

MS 1 2 3 1 1 0 1 2 0 0 0

¤

MR 1 2 1 1 0 2 0 1 3 0 1

Question 8.19.1

MS¤MR 1 2 1     2

=

MS 1 2 3 1 1 0 1 2 0 1 0

¤

MR 1 2 1 1 0 2 1 1 3 0 0

Question 8.19.2

MR¤MS 1 2 3 1       2       3

=

MR 1 2 1 1 0 2 1 1 3 0 0

¤

MS 1 2 3 1 1 0 1 2 0 1 0

 

Representing Relations Using Digraphs

Definition 1

Directed graph (digraph) Set V of vertices (nodes) Set E ordered pairs of elements of V called edges (arcs) Vertex a is initial vertex of edge (a,b). Vertex b is terminal vertex of edge (a,b). Edge (b,b) is a loop.

Example

V_ertices = {a, b, c, d}

E_dges = {(a, d), (a, b), (b, b), (b, d), (c, b), (c, a), (d, b)}

a b c d a 0 1 0 1 b 0 1 0 1 c 1 1 0 0 d 0 1 0 0

Example

V = {1,2,3,4}

Question 8.20.1

E = ?

1 2 3 4 1 1 0 1 0 2 1 0 1 1 3 1 1 0 0 4 1 0 0 0

Question 8.20.2 - Draw the digraph for:

	a	b	c	d
a	1	1	0	0
b	0	0	0	1
c	1	0	0	1
d	0	0	1	0

 

Example

(a) R = {(a, a), (b, b), (c, c), (b, c), (c, b)}

Reflexive because for all vertices {a, b, c} there is a loop.

Not symmetric because edge (a, b) but no (b, a).

Not antisymmetric because (b, c) and (c, b)

Not transitive because edges (a, b) and (b, c) but no (a, c).

Example

(b) S = {(a, c), (c, a), (a, d), (d, a), (d, d), (a, b), (b, a), (b, b)}

Not reflexive because for all vertex {a, b, c, d} there is not a loop, no (a, a) or (c, c).

Symmetric because for all edges there exists an opposite edge.

Not antisymmetric because (a, c) and (c, a).

Not transitive because edges (c, a) and (a, b) but no (c, b).

 

Question 8.21

For the digraph at right, give: Vertices = Edges = Corresponding matrix.

 

8.4 Closures of Relations

Introduction

We have seen that relations can be represented as digraphs, which can model communication, roads, air or other connected systems.

Methods for determining the interconnectivity of nodes in a network and other network qualities is often critical. This section examines some of the methods.

Closures

Reflexive relations have all 1's on the diagonal

Example

R is not reflexive.

A = {1, 2, 3} R = {(1, 1), (1, 2), (2, 1), (3, 2)}

1 2 3 1 1 1 0 2 1 0 0 3 0 1 0

What set of pairs is smallest that make R reflexive?

A = {1, 2, 3} R = {(1, 1), (1, 2), (2, 1), (3, 2)}         S = R U {(1, 1), (2, 2), (3, 3)}

1 2 3 1 1 1 0 2 1 1 0 3 0 1 1

Definition

Reflexive closure of R is smallest reflexive relation that contains R. Reflexive closure of R = R U Δ, the diagonal relation on A.

Example

Find the reflexive closure of R = {(a,b) | a < b }

R U Δ

= {(a, b) | a < b } U {(a, a) | a ∈ Z}

= {(a, b) | a ≤ b}

A = {1, 2, 3} R = {(1, 2), (2, 3), (1, 3)} S = R U {(1, 1), (2, 2), (3, 3)}

R=

1 2 3 1 0 1 1 2 0 0 1 3 0 0 0

S=

1 2 3 1 1 1 1 2 0 1 1 3 0 0 1

 

Symmetric relations have edges in both directions between all connected vertices.

Example

R is not symmetric.

A = {1, 2, 3} R = {(1, 1), (1, 2), (2, 1), (3, 2)}

1 2 3 1 1 1 0 2 1 0 0 3 0 1 0

What set of pairs is smallest that make R symmetric?

Need to add (b, a) for (a, b) in R.

A = {1, 2, 3} R = {(1, 1), (1, 2), (2, 1), (3, 2)}         S = R U {(2, 3)}

1 2 3 1 1 1 0 2 1 0 1 3 0 1 0

Question 8.22

What is smallest set of pairs that make R symmetric?

Need to add (b, a) for each (a, b) in R.

A = {1, 2, 3} R = {(1, 1), (2, 1), (3, 2)}                    S = R U { ? }

1 2 3 1 1 0 0 2 0 0 0 3 1 1 0

Definition

R-1 Inverse relation of R from A to B is relation from B to A: R-1 = {(b, a) | (a, b) ∈ R}

Example

A = {0, 1, 2} B = {0, 1, 2} R    = { (0, 0), (1,1), (2, 1) } R-1 = { (0, 0), (1, 1), (1, 2) }

0 1 2 0 1 0 0 1 0 1 0 2 0 1 0

Definition

Symmetric closure of R is smallest symmetric relation that contains R. Symmetric closure of R = R U R-1 R-1 = {(b, a) | (a, b) ∈ R}

Example

Find the symmetric closure of R = {(a, b) | a > b }

R U R^-1

= {(a, b) | a > b } U {(b, a) | (a, b) ∈ R}

= {(a, b) | a ≠ b}

A = {1, 2, 3} R = {(2, 1), (3, 1), (3, 2)}

1 2 3 1 0 0 0 2 1 0 0 3 1 1 0

R-1 = {(1, 2), (1, 3), (2, 3)} R U R-1       = {(2, 1), (3, 1), (3, 2)} U {(1, 2), (1, 3), (2, 3)} R is a > b R-1 is a < b

1 2 3 1 0 1 1 2 1 0 1 3 1 1 0

Question 8.23

Find the symmetric closure of R by finding R^-1 and R U R^-1.

A = {1, 2, 3} R = {(1, 1), (2, 1), (3, 2)}      R-1 = { ? } R U R-1 = { ? }

1 2 3 1 1 0 0 2 1 0 0 3 0 1 0

 

Definition

Transitive relations: if edges (a, b) and (b, c) then edge (a, c).

Example

R is not transitive because (3, 2) and (2, 1) but no (3, 1).

A = {1, 2, 3} R = {(3, 2), (2, 1)}

1 2 3 1 0 0 0 2 1 0 0 3 0 1 0

What set of pairs is smallest that make R transitive?

Can we just add (a, c) for (a, b) and (b, c) in R?

In this case, yes.

R U {(3, 1)} is transitive.

A = {1,  2, 3} R = {(3, 2), (2, 1), (3, 1)}

1 2 3 1 0 0 0 2 1 0 0 3 1 1 0

Example

R is not transitive because (1, 3) and (3, 2) but no (1, 2).

R is not transitive because (2, 1) and (1, 3) but no (2, 3).

Question 8.24.1

Give another example why not transitive.

A = {1, 2, 3, 4} R = {(1, 3), (1, 4), (2, 1), (3, 2)}

1 2 3 4 1 0 0 1 1 2 1 0 0 0 3 0 1 0 0 4 0 0 0 0

For (a, b) and (b, c), can we just add (a, c) in R?

In this case, no.

R U {(1, 2), (2, 3), (2, 4), (3, 1)} is still not transitive.

Adding (3, 1) now contains (3, 1) and (1, 4) but not (3, 4).

A = {1, 2, 3, 4} R = {(1, 3), (1, 4), (2, 1), (3, 2)} R U {(1, 2), (2, 3), (2, 4), (3, 1)}      = {(1,3),(1,4),(2,1),(3,2),(1,2),(2,3),(2,4),(3,1)}

1 2 3 4 1 0 1 1 1 2 1 0 1 1 3 1 1 0 0 4 0 0 0 0

Transitive closure more complicated that reflexive or symmetric, explored further below.

Question 8.24.2

For (a, b) and (b, c), just adding (a, c) in R did not work.

What is the problem and what is a possible approach to a solution?

 

Paths in Directed Graphs

Definition 1

Path from a to b in digraph G is sequence of edges (x0, x1), (x1, x2), ..., (xn-1, xn) = (a, x1), (x1, x2), ..., (xn-1, b)   Path can pass through a vertex more than once. Path (x0, x1), (x1, x2), ..., (xn-1, xn) has length = n. Loop or circuit is path a to a of length n > 0.

Question 8.25.1 Which of the following are paths? (a, a) (d, e) (a, e), (e, d), (d, a) (a, a), (a, a) (a, b), (b, e), (e, d) (a, e), (e, c), (c, d), (d, b) (e, b), (b, a), (a, b), (b, a), (a, b), (b, e) Question 8.25.2 Which are circuits? Question 8.25.3 What is the path length for 1, 3, 7 above? Question 8.25.4 What is the path length of: (x0, x1), (x1, x2), (x2, x3)

 

Composition of Relations Review

R = {(1, 2), (2, 3), (3, 4), (4, 1)}

R² = R○R

R² contains (a, c) if (a, b) and (b, c) ∈ R.

R (1,2) R    (2,3)	(2,3)    (3,4)	(3,4)    (4,1)	(4,1)    (1,2)
R2 (1,3)	(2,4)	(3,1)	(4,2)

R² = {(1, 3), (2, 4), (3, 1), (4, 2)}

R³ = R²○R

R = {(1, 2), (2, 3), (3, 4), (4, 1)}

R³ contains (a, c) if (a, b) ∈ R² and (b, c) ∈ R.

R2 (1,3) R      (3,4)	(2,4)    (4,1)	(3,1)    (1,2)	(4,2)    (2,3)
R3  (1, 4)	(2, 1)	(3, 2)	(4, 3)

R³ = {(1, 4), (2, 1), (3, 2), (4, 3)}

Question 8.26

R³ = {(1, 4), (2, 1), (3, 2), (4, 3)}

R =  {(1, 2), (2, 3), (3, 4), (4, 1)}

R⁴ contains (a, c) if (a, b) ∈ R³ and (b, c) ∈ R.

Find R⁴ = R³○R

 

Theorem 1

R is a relation on set A. Path from a to b of length n in R, n > 0, iff (a, b) ∈ Rn

Implies a way to determine transitive relations of length n by computing Rⁿ.

Example

R = {(1, 2), (2, 3), (3, 4), (4, 1)}

R² = {(1, 3), (2, 4), (3, 1), (4, 2)}

Path (1, 2), (2, 3) of length 2 in R:

(1, 3) ∈ R²

Path (2, 3), (3, 4) of length 2 in R:

(2, 4) ∈ R²

 

R = {(1, 2), (2, 3), (3, 4), (4, 1)}

R³ = {(1, 4), (2, 1), (3, 2), (4, 3)}

Path (1, 2), (2, 3), (3, 4) of length 3 in R:

(1, 4) ∈ R³

 

R = {(1, 2), (2, 3), (3, 4), (4, 1)}

R⁴ = {(1, 1), (2, 1), (3, 1), (4, 1)}

Path (1, 2), (2, 3), (3, 4), (4, 1) of length 4 in R:

(1, 1) ∈ R⁴

 

Transitive Closures

Transitive closure of a relation is equivalent to determining which pairs of vertices in the associated directed graph are connected by a path.

The method for finding a transitive closure is based on matrices, at the end of this section.

Example

If a, b, c, d are connected subway stop pairs, the transitive closure is the relation containing pairs connected by a path.

Below, one can travel from a to b, b to c, and c to d.

Transitive closure determines all other travel connections; from a to c, a to d, b to d.

For relation: R = {(a, b), (b, c), (c, d)}

MR a b c d a 0 1 0 0 b 0 0 1 0 c 0 0 0 1 d 0 0 0 0

is the transitive closure MR* MR* = {(a, b), (b, c), (c, d), (a, c), (a, d), (b, d)}

MR* a b c d a 0 1 1 1 b 0 0 1 1 c 0 0 0 1 d 0 0 0 0

 

Definition 2

R is a relation on set A. R* connectivity relation consists of the pairs (r, s) such that there is path length, n > 0, from r to s in R.

Example

R relation contains all subway stops in New York.

(r, s) ∈ R if possible to travel from r to s without changing trains.

R = {(a, b), (b, c), (c, d)}

What is R²?

If (r, s) and (s, t) ∈ R then (r, t) ∈ R²

(r, s)     (s, t)     (r, t)

Can travel path r to t making 1 change, at stop s.

The path (r, s), (s, t) is length 2,

1 change at s.

R = {(a, b), (b, c), (c, d)}

R² = R○R

R (a, b) R     (b,c)	(b, c)     (c,d)
R2 (a, c)	(b, d)

R² = {(a, c), (b, d)}

What is R³?

R³ are those pairs (r, s) where can travel (r, x₁), (x₁, x₂), (x₂, s).

The path (r, x₁), (x₁,x₂), (x₂, s) is length 3,

2 changes, at stop x₁and  x₂

R² = {(a, c), (b, d)}

R = {(a, b), (b, c), (c, d)}

R³ = R²○R

R2 (a, c) R       (c, d)

R3 (a, d)

R³ = {(a, d)}

What is Rⁿ?

Rⁿ are those pairs (r, s) where can travel  (r, x₁), (x₁, x₂), ..., (x_n-1, s).

The path (r, x₁), (x₁, x₂), ..., (x_n-1, s) is length n,

n-1 changes, at stop x₁, x₂, ..., x_n-1

R

R2

R3

What is R^*?

                         

R^* = R U R² U R³

     = {(a, b), (b, c), (c, d)} U {(a, c), (b, d)} U {(a, d)}

     = {(a, b), (b, c), (c, d), (a, c), (b, d), (a, d)}

R^* contains (r, s) if it is possible to travel from r to s making as many train changes as necessary.

Theorem 2

Transitive closure of relation R equals the connectivity relation R*.

The transitive closure of the New York subway is the relation R^* which contains all pairs of train stops connected by a path.

 

Lemma 1

R is a relation on set A of n elements. If R contains path a to b of length > 0, then there is a path with length ≤ n. When a≠b, if R contains path a to b of length > 0, then there is a path with length ≤ n-1.

Note that n elements can have a path no longer than length n-1 without a circuit.

{a, b, c, d}, 4 elements, has among several possible longest paths of length 3:

(a, b), (b, c), (c, d).

Example

Path a to b may include a circuit, as below.

a≠b implies any circuit does not include a and b.

We would like to remove that circuit in determining transitive closure.

 

 

Question 8.27.1

Find the zero-one matrix M^[2]_R ⁼ M_R¤M_R

MR	1	2	3
1	0	1	0
2	1	0	1
3	0	0	0

 

Theorem 3

MR is the zero-one matrix of R on set of n elements. Zero-one matrix on transitive closure R* is: MR*= MR v M[2]R v M[3]R v ... v M[n]R

Example

A = {1, 2, 3}        |A| = 3        R⊆ AxA

R = {(1, 1), (1, 3), (2, 2), (3, 1), (3, 2)}

Find the zero-one matrix ^MR^* of the transitive closure of the relation R where:

MR 1 2 3 1 1 0 1 2 0 1 0 3 1 1 0

^MR^*= M_R v M^[2]_R v M^[3]_R

M[2]R 1 2 3 1 1 1 1 2 0 1 0 3 1 1 1

=

MR 1 2 3 1 1 0 1 2 0 1 0 3 1 1 0

¤

MR 1 2 3 1 1 0 1 2 0 1 0 3 1 1 0

M[3]R 1 2 3 1 1 1 1 2 0 1 0 3 1 1 1

=

M[2]R 1 2 3 1 1 1 1 2 0 1 0 3 1 1 1

¤

MR 1 2 3 1 1 0 1 2 0 1 0 3 1 1 0

n=3 for 3 x 3 MR

MR* 1 2 3 1 1 1 1 2 0 1 0 3 1 1 1

=

MR 1 2 3 1 1 0 1 2 0 1 0 3 1 1 0

v

M[2]R 1 2 3 1 1 1 1 2 0 1 0 3 1 1 1

v

M[3]R 1 2 3 1 1 1 1 2 0 1 0 3 1 1 1

^MR^*= {(1,1), (1,3), (2,2), (3,1), (3,2), (1,2), (3,3)}

 

Calculating M^[2]_R

M[2]R 1 2 3 1 (MR1,1^MR1,1)v(MR1,2^MR2,1)v(MR1,3^MR3,1) (MR1,1^MR1,2)v(MR1,2^MR2,2)v(MR1,3^MR3,2) (MR1,1^MR1,3)v(MR1,2^MR2,3)v(MR1,3^MR3,3) 2 (MR2,1^MR1,1)v(MR2,2^MR2,1)v(MR2,3^MR3,1) (MR2,1^MR1,2)v(MR2,2^MR2,2)v(MR2,3^MR3,2) (MR2,1^MR1,3)v(MR2,2^MR2,3)v(MR2,3^MR3,3) 3 (MR3,1^MR1,1)v(MR3,2^MR2,1)v(MR3,3^MR3,1) (MR3,1^MR1,2)v(MR3,2^MR2,2)v(MR3,3^MR3,2) (MR3,1^MR1,3)v(MR3,2^MR2,3)v(MR3,3^MR3,3)

Example

A = {a, b, c, d}       |A| = 4        R⊆ A x A

R = { (a, b), (b, c), (c, d) }

Find the zero-one matrix ^MR^* for the transitive closure of R:

MR a b c d a 0 1 0 0 b 0 0 1 0 c 0 0 0 1 d 0 0 0 0

^MR^*= M_R v M^[2]_R v M^[3]_R v M^[4]_R                     n=4 for 4 x 4 ^MR

^MR^*= { (a, b), (b, c), (c, d), (a, c), (a, d), (b, d) }

Question 8.27.2

What value is n in M^[n]_R for a 10 x 10 ^MR

Question 8.27.3

Find the zero-one matrix ^MR^* of the transitive closure of the relation R where:

MR	1	2	3
1	0	1	0
2	0	0	1
3	0	0	0

^MR^*= M_R v M^[2]_R v M^[3]_R                     n=3 for 3x3 ^MR

M^[2]_R = M_R ¤ M_R

M^[3]_R = M^[2]_R ¤ M_R

Question 8.28.1

How many ^ and v are necessary to compute one entry of: M^[2]_R = M_R ¤ M_R

MR	1	2	3
1	0	1	0
2	0	0	1
3	0	0	0

How many in terms of n?

Question 8.28.2

How many entries are there for a 3x3 M^[2]_R

How many in terms of n?

Question 8.28.3

Using the two answers above, what is the complexity of M^[2]_R = M_R ¤ M_R for a 3x3 ^MR

In terms of n?

Question 8.28.4

How many v are necessary to compute M_R v M^[2]_R

In terms of n?

MR a b c d a 0 1 0 0 b 0 0 1 0 c 0 0 0 1 d 0 0 0 0

v

M[2]R a b c d a 0 0 1 0 b 0 0 0 1 c 0 0 0 0 d 0 0 0 0

Question 8.28.5

Do these take the same time to compute?

M^[2]_R = M_R ¤ M_R

M^[3]_R = M^[2]_R ¤ M_R

What is the complexity of either in terms of n?

What is the complexity in computing M^[2]_R v M^[3]_R

What are a-e below?

What is the complexity of:

^MR^*= M_R v M^[2]_R v M^[3]_R v ... v M^[n]_R

Definition

ALGORITHM 1  A Procedure for Computing the Transitive Closure procedure transitive closure( MR : zero-one n x n matrix ) A := MR B := A for i := 2 to n A := A ¤ MR B := B v A

Execution Count a. b. c. d. e.

M_R is n x n matrix.

A := A ¤ M_R, is n² * 2n = 2n³ complexity.

2n bit operations are required to compute each element of A.

(M_R1,1^M_R1,1) v (M_R1,2^M_R2,1) v (M_R1,3^M_R3,1)

n x n elements

B := B v A, is n² complexity

The for executes n-1 times

A := A ¤ M_R is 2n³ complexity

B := B v A is n² complexity

Complexity

2n³(n-1) + n²(n-1) = 2n⁴ - n³ - n²

2n⁴ - n³ - n² is O(n⁴) complexity.

 

Warshall's Algorithm

O(n³) complexity