Relations

Relations

1

 

and



a ‘f‘ b in Haskell



2

.

is a subset

is a binary relation on




Binary Relations




, we often say that





loves(John, Mary) or ‘John loves Mary’ rather than John Mary loves



A binary relation between arbitrary sets of the binary product . If 

Notation







For



 



 

  



 

  





 

























 



 



 

3

 

 

 

 



 



  

 

  





 

 





 



 

 

 

 

 

 

  



 

 









 





















 



 

 

 

 

 

 

 







 

 

 

 









 







 





 















Example



 



 



, there are sixteen binary relations on :



 

 





 

 





 



 

 

 





 

 

 





Let



 

  

,


Diagram

.

and

is illustrated by the diagram

4

B

This representation will be used in this course.

Relation

 

  

    

   

A 



  

     

  

 

 



   

  



  



  



 



with . The directed graph 



  

Directed Graph



be a binary relation on   

Let of this relation is

A

 

  

     

 

  





 

 

  

  



5

Notice that the direction of the arrows matters. This representation will be used in Discrete maths 2.



   

    



  #

6

"

$

if and only if

"





!

"

Special representation The relation defined by represented by 

can be

  

  

 

 

  

  

is

and as before. The matrix

This representation can be generalised to arbitrary finite sets and , as discussed in the notes.

where T stands for True and F for False.

T T F

T F F





Matrix Representation  






 

,

 



  

Let   



representation of

  



 



7

You do not need to remember this representation.




Adjacency List We can store a relation using an array.

2

1

1

1

3



 &%

3











&%

 %

('

8

 %





on set

With a sparse relation, we can instead use an adjacency list.



Consider the binary relation . The adjacency list representation is  '





You do not need to remember this representation.

 %





*

*

,

 +*

*

* 

,

-ary relation



9

A unary relation, or predicate, over set that is, a subset of .

is a subset of a

is a 1-ary relation:

The definition of a 2-ary relation is the same as that of a binary relation.

*

)

A n-ary relation between sets -ary product .

-

.





.  

Examples



is prime is a unary relation on 0

1. The set 

/

.

2. The set is a -ary relation on the real numbers, which describes the surface of the unary sphere with centre . 











10





'



 1

/







21

 1



%

Let all with type

. Define the relations , by

or

4

,

5

;

3

and



Basic Relation Operators

Relation Union iff

3

 

and

.

  

Relation Intersection

and

6 

  



3

 

3 



 

if and only if

 

 



Relation Complement 

    

   

 

 3  

  

  3

iff

  

4 5 

 



11

Contrast the difference between the relation and set operators.

  

  

  

  

(3

  

  



        

   

     

;

,

Let

5

4



3

3



  ' 

('



12



  7 



 7

 

 7





 



  7

 '  %





  7

 ' 

 



 %



 ' +7 

such that

 ' 





 7



  7

 7



 7





 %

 %

 

  '







 '





 

 %

 %







 '

 %

  7





 7



 '



 









 '



&%





 7



&%

Example







 '

+7

  % &

 









 '



 7





 '







  % &

3

&%



 %





&%

&%









3

be binary relations on

 '

and



Identity Relation

More Operators

8



8

13

denote an arbitrary binary relation. The inverse , is defined by if and only if .



.

 

 

9





Given any set , the identity on , written id , is a binary relation on defined by id .

:9














Inverse relation 

 



3

Let of , written 





 9









 % 

 







 '



 '  

  '

  7

 7





(' 

  7

  %  7

 %

 



.



 %





 '

.

and

 7 

Example

14 

&%

be a binary relation on









9





9 

 9

Let



.

Notice the difference between 



such that

given earlier.

Composition of Relations

3

and , then the composition of , is defined (for arbitrary and ) by 

?

3






if and only if



is only defined if the types of

composed with ’ or ‘



3

may be read as ‘

 

Given with , written

The notation circle ’. The relation match.

*



and









(g.f) x = g ( f x) 15

Very confusing!

Contrast with the Haskell notation for functional composition:

3





<

=

3

;









>



< 3

=







3 <

<

= 3

3

3

Let 

and 3

3 <

<



3 





 

&%

&%  % 



16



 '

 %

(' 



  '

 %

 7

 7 



  7



 ' 

 



 %



 ' +7 

such that

 7 



  7

 7



 '









 7



 '





 '











 %







+7

















 



&%

Example

 '





&%





be binary relations on

3








<

id .

Equalities between Relations , then id 8 <








is shorthand for





;

 



B

and 17

3 /

A 

< 3

.

*

A

< 

A

<  3

;

<




1. If

/





@

2. is associative: that is, for arbitrary relations and and , then

3 



 3

The proof of part 1 is left to you.



 

<

Notation 





 

C 

<

be an arbitrary member of

3 <  A C

<

  3 < 

<

 

 C 

? 3



.

C

A

3 / C

A 

A

C

 C

/ C

 

A

<  A

?



< 3

3 /

A

 3

 /



/

<

.

C

3

?

3



 /

/



>

 * 





 



? *

 A





<

*





/>

/> *

 *



?

/>







A  3





<



 *

 

/>

iff

18

A

/>

 *

iff

<

>

 *

iff

>

iff





iff

<

iff

iff

3

A

Proof of part 2

Let

We have shown that 



Let 1.

3.

Negative Results be a binary relation on . Then ;

id . 8

19



 

 





 



 3

 

 

  

   

 

A counter-example to part 1 is







 

Proof The way to prove that a property does not hold is to provide a counter-example.

2. composition is not commutative;

  6 





9  9 



6

A counter-example to part 2 is and where . Part 3 is left as an exercise. 



  <

.

Application to Relational Databases

Walker, S.

Smith, J.

Jackson, B.

Brown, B

...

name

...

4 Ash Gr.

9 Elm St.

1 Oak Dr.

5 Lawn Rd.

...

address

...

189

156

167

105

...

number

...

189

156

105

...

number

...

C

A

A

...

grade

Here are two example databases:

...

20

Walker, S

Smith, J

Brown, B

...

name

...

4 Ash Gr.

9 Elm St.

5 Lawn Rd.

...

address

...

189

156

105

...

number

...

C

A

A

...

grade

Join operator

...

Notice that candidate 167 did not sit the exam, and so therefore does not appear in the join. 21

Walker, S

Smith, J

Brown, B

...

name

...

4 Ash Gr.

9 Elm St.

5 Lawn Rd.

...

address

...

C

A

A

...

grade

Projection operator

...

22

Smith, J

Brown, B

...

name

...

9 Elm St.

5 Lawn Rd.

...

address

...

A

A

...

grade

Select operator

...

23

Question

What is the connection between relational composition and the operators for relational databases?

24

Equivalence Relations: Motivation

Two Haskell functions and are , if and only if, for all terms equivalent, written in type , then if terminates then terminates and , and if does not terminate then does not terminate.

I

; M ?

reflexivity

D

The following properties are satisfied:

F

MON

;

I

I

symmetry

L

D

transitivity

H

D

.E

D

D L

25

D

P

D

F

PN

P*

M*

I

.E

L

D

D

H

I

I

D

D

L D

D

H

H

G

D M

D M

E

D

D 

D D

D D M

I

D* L  L 

D

H

K K K

J J J

G

.



/

.



Properties of Relations



be a binary relation on . Then  

Let



;

RQ

 * ?

K

26





 /

N

*   

 



 

 *

K

is reflexive if and only if

/ 

1.





is symmetric if and only if is transitive iff



2. 3.

K

   

;

and

Examples

are reflexive and transitive, but not

1. The equality relation on sets is reflexive, symmetric and transitive. 2. The relations symmetric.



27

3. The relation on numbers is transitive, but not reflexive or symmetric.

!



is reflexive if and only if id

The proof is easy and is left as an exercise.

28

.





8 



9





Proposition

1. The relation

is symmetric if and only if

be a binary relation on .

2. The relation

is transitive if and only if



Let

3. The relation

< 









.

.

Let

a binary relation on .







Equivalence Relations

be a set and



An equivalence relation is a bit like a weak equality: means that and are in some sense indistinguishable. 

29

is an equivalence.

The relation is an equivalence relation if and only if reflexive, symmetric and transitive. 

We sometimes just say that







is

-



on

S

defined by .



Examples of Equivalence Relations

 

  .

S /

1

Y






V

F











V



V

X

V



30

5. The logical equivalence between formulae, given by if and only if .


4. Given a set Student and a map age Student age ’. relation ‘ sameage iff age

-

/

-

6

3

 -

 





 /

-



  3

, the binary relation divides into .

1. Given defined by

-

3. The identity relation id



8









for iff

2. The binary relation on the set iff

 UT

.





.





 /

W

, the

[

[\

instead of



. 



 *

when the relation



[\



Z

, the , is

is apparent.

[\

Equivalence classes



Z





 



Let be an equivalence relation on . For any equivalence class of with respect to , denoted defined as We write

 Z

 Z

The set of equivalence classes is called the quotient set

31



]



.





-

Examples

1. Given for , the binary relation on defined by iff divides into . The set represents the integers modulo .





6

-

1

-

 UT







S

S

defined by 2. The binary relation on the set iff . The set is the usual way of representing the rational

]

-



  3

 /

] 3



-





numbers.



 /

S



-



32





3





-



/





-

S

/







Z  [6

N

Z

33

.

;

forms a partition

[

  Z

  Z

 Z 

 [

Proposition

8

The set of equivalence classes of : that is,

5 [

_

is non-empty;

 Z

^ [

each

*

.

[

the classes cover : that is,

 

[



Z

the classes are disjoint: K

J J J

Given

Suppose

, then

.

and .

by symmetry.

[

Proof by reflexivity and so

, and hence

.

, and hence the classes cover . , and let and

.

, observe that . Now , by transitivity. Hence and using a similar argument, so

34

[



Z

5



Z 







  

Z



[





   [

[





Z 





[ 

Z



`

  

Z `



 



Z  [6 Z 

Z  [

` 



[ `

This means that



[

[  Z

`



[

[



Z 

Given any , so

Z



Z

 8 

Z

5



^ _

 

[

  





Transitive Closure: Example

Knock

ba

Paris

London



ba

Manchester

Dubin

Madrid





Rome

Edinburgh



35

Define the relation by if and only if there is a trip from to . We would like to calculate from . 

Define a set City of cities and a binary relation on City such that iff there is a direct flight from to . For example 





ba



to , for some

from

to .

.

for some

It is the smallest transitive relation containing

36

.

c



%

-

Transitive Closure: Example continued





 

-

from

,







-

iff there is a path of length

iff 

.



if and only if there is a path of length

An equivalent definition is

 a

The relation is called the transitive closure of



 % , 

ba c 

 

.

Transitive Closure: Example continued (again)

-

is

,



*< 4 ,

, <

 < 4*



Another way of defining



times









*

 *

 * 

<





9 , 

since is associative

 *

 *

37

, d

*

*

<

 <



4

,

   * *

< 4

* *



   *  *  a

Example Program modules can import other modules. You have seen this already in the Haskell course.

if

imports

e

and

e

e

imports

e

.

They can also depend indirectly on modules via some chain of importation: depends on

e

38

The relation ‘depends’ is the transitive closure of the relation ‘imports’.

e

Example Two people are related iff 1. either one is the parent of the other; or 2. they are married; or

3. there is a chain of such relationships joining them directly.

Consider a universal set People, and three relations Married, Parent and Relative.





Parent 4

Parent 39

 4 

Married

a



9

The relation Relative is defined using the transitive closure: Relative



 

 4



*

*

*

 4

d

, 

4

,



40



Transitive Closure

4



Definition

ga

Let be a binary relation on . The transitive closure of or , is : that is, written 

f



The transitive closure of a binary relation always exists.



,

Exercise

Manchester

Paris

London

Rome

Edinburgh

Back to the Example

Knock

Dubin

Madrid

Construct the transitive closure. 41

*

 *

*

*

, compute successively 4

elements.

.

represents all paths of length



Computing the Transitive Closure To calculate

The relation between and .

4

-

is finite, the process will come to an end.

4





4*

 

 4

*

*

is defined has



%

Suppose the set on which

.

,

 4*

 +* 

4

9



-



If

 6

Then

with

*

ba

4

4

Find such an

ba

ba

Exercise

4*

, ,

42

*

4 

 

 

4

 



Algorithm We may describe our procedure by the following Kenya-like algorithm: Input h i

jlk h jlk

m

h i

jlk

i h

n

43

while not

i

j2k

o

m i

m

m i p

jlk

do

i h

n

od Output

m

There are many ways of improving the algorithm. See Warshall’s algorithm described in Discrete Maths 2.