RELATIONS

Question 1

What is a cartesian product?

Answer 1

The cartesian product of sets A and B is a set of all ordered pairs (x,y) where x ∈ A and y ∈ B.

e.g. A = { 1, 2, 3} B = { a, b, c}
A X B = { (1,a), (1,b), (1,c), (2,a), (2,b), (2,c), (3,a), (3,b), (3,c)}

Question 2

What is the notation for cartesian product?

Answer 2

A X B

e.g. A = { 1, 2, 3} B = { a, b, c}
A X B = { (1,a), (1,b), (1,c), (2,a), (2,b), (2,c), (3,a), (3,b), (3,c)}

Question 3

Does order matter for cartesian products?
E.g. does A X B = B X A ?

Answer 3

YES order matters! A X B != B X A
This is because (A = { 1, 2, 3} B = { a, b, c})
A X B = { (1,a) ….
B X A = { (a,1) ….
(1,a) != (a,1)

Question 4

What is a relation?

Answer 4

A subset of the cartesian product.
This can include some, all or none of the pairings.

e.g. where A = { 1, 2, 3} B = { a, b, c}
The Relation “R” ⊆ A X B

Question 5

Example of relation: Which pairings would relation_example include if A = { 1, 2, 3} B = { a, b, c} ?

Answer 5

relation_example = { (1,b), (2,c), (3,a) }
(example)

Question 6

What is infix notation for relations?

Answer 6

Written as x R y where (x,y) ∈ R
(pairing (x,y) adhere to rules of relation R and is an element of R)

Question 7

Example of relation: How does infix notation x < y work?

Answer 7

This is a relation as it is a subset of the cartesian product of all natural numbers (R ⊆ N X N) . However, only (x,y) where x < y is inluded in the subset

Question 8

Which other forms can relations be shown in?

Answer 8

Tables = each row pairing is a pairing of relation.
Mapping = values on the left map to their pairing on the right.

Question 9

How are relations often used?

Answer 9

Often used in databases
e.g. (Molly, Sheppard) ∈ Last_Name as there is a relation of Molly to Sheppard in the Last_Name field.

Question 10

What is relational composition?

Answer 10

A new relation of pairing (a,c) where there exists a value for b which fits (a,b) into relation R and (b,c) into relation S
supposing R ⊆ A X B and S ⊆ B X C

Question 11

How is relational composition written?

Answer 11

Supposing R ⊆ A X B and S ⊆ B X C,
R;S = { (a,c) ∈ A X C | exists b ∈ B such that (a,b) ∈ R and (b,c) ∈ S}

Question 12

How do you draw relational composition through mappings?

Answer 12

Remove the middle relation and follow all relations from set A to point straight to its specific destination in set B.

Question 13

What is relational inverse?

Answer 13

Flip the arrows of the mapping diagram.
Suppose R ⊆ A X B
then (b,a) ∈ R^-1 (inverse B X A) iff (a,b) ∈ R (normal A X B)

Question 14

How is relational inverse written?

Answer 14

R^-1

R^-1 = { (b,a) ∈ B X A | (a,b) ∈ R}

Question 15

What is domain?

Answer 15

set of all elements of A which have a relation by R to some element in B

Question 16

How is domain written?

Answer 16

dom(R)

suppose R ⊆ A X B
dom(R) = { a ∈ A | exists b ∈ B such that (a,b) ∈ R}

Question 17

Important property of all domains =

Answer 17

R ⊆ A X B then dom(R) ⊆ A
domain of relation will always be a subset of A.
for any a, if a ∈ dom(R) then a ∈ A

Question 18

Example of domain = What will dom(R) be if:
A = {A, B, C, D, E, F}
B = {1,2,3,4,5,6}
R = {(B,1), (B,3), (E,4), (F,5)}

Answer 18

dom(R) = {B, E, F}

Question 19

What is range?

Answer 19

set of all elements in B that are related by R to something in A

Question 20

How is range written?

Answer 20

RAN(R) =

ran(R) = { b ∈ B| exists a ∈ A such that (a,b) ∈ R}

Question 21

What is an important property of Range?

Answer 21

R ⊆ A X B then ran(R) ⊆ B
range of relation will always be a subset of B.
for any a, if a ∈ dom(R) then a ∈ A

Question 22

Example of range= What will ran(R) be if:
A = {A, B, C, D, E, F}
B = {1,2,3,4,5,6}
R = {(B,1), (B,3), (E,4), (F,5)}

Answer 22

ran(R) = {1, 3, 4, 5}

Question 23

When is a relation reflexive?

Answer 23

Assuming R ⊆ A X A, R is reflexive iff for every x ∈A then (x,x) ∈ R
- every element in equals relation is equal to itself
- greater or equal to itself
- every element is a multiple of itself
(1,1), (2,2), (3,3)

Question 24

When is a relation symmetric?

Answer 24

Assuming R ⊆ A X A, R is symmetric iff (x,y) ∈ R then (y,x) ∈R
- x = y if and only if y = x
- sibling of (Ali, Bob) ∈ Sibling_of only if (Bob, Ali) ∈ Sibling_of
(1,2), (2,1)

Question 25

When is a relation transitive?

Answer 25

assuming R ⊆ A X A, if (x,y) ∈ R and (y,z) ∈ R implies that (x,z) ∈ R
- if x = y and y = z then x = z
- ancestor_of > (Ali, Bob) ∈ Ancestor_of and (Bob, Clair) ∈Ancestor_of then (Ali, Claire) ∈ Ancestor_of
(1,2), (2,1) (1,1)

Question 26

What is a P-Closure?

Answer 26

An extension to a relation to meet a specific property.
Assume R ⊆ A X A, A new relation R’ will contain at least R as well as the minimum amount of pairs to meet property (e.g. reflexive, symmetric, transitive)
R ⊆ R’

Question 27

What is an equivalence relation?

Answer 27

Assume R ⊆ A X A is an equivalence relation over A iff R is REFLEXIVE, SYMMETRIC AND TRANSITIVE
So, equiv. relation over A if
- x ∈ A then (x,x) ∈ R
- (x,y) ∈ R then (y,x) ∈ R
- (x, y) ∈ R and (y,z) ∈ R then (x,z) ∈ R

Question 28

What is an equivalence class?

Answer 28

Equivalence relations allow to define an equivalence class
> An equivalence class of P when [a]p is a set of elements b that are related to a via P.
- contains all elements b where “b is the same as a as far as p can distinguish”
extend the table of pairings to include all transitive, reflexive and symmetric and then create a set of all in left column.
Any element you can get to from x if [x]R where R is an equivalence class.

Question 29

Example of an equivalence class: What would [B]R be if
A = { A, B, C, S }
R = {(A,B), (B,C), (S,A)}

Answer 29

1. extend the table to include reflexive closures
   + (A,A), (B,B), (C,C), (S,S)
2. extend the table to include all reflexive closures
   + (B,A), (C,B), (A,S)
3. extend the table to include all transitive closures
   + (A,C), (S,B)
4. All values for [B] R would be all values with first value as B so [B] R = {B, A, C}

Question 30

What is asymmetric?

Answer 30

Assuming R ⊆ A X A, R is asymmetric iff (x,y) ∈ R and (y,x) ∈R implies x = y
if (x,y) ∈ R but x != y then (y,x) ∉ R.

Question 31

What is an example of asymmetric?

Answer 31

“Less than or equal to”
as: assuming ≤ ⊆ N X N, if x ≤ y and y ≤ x then x MUST BE = y

Question 32

What is a partial order?

Answer 32

When a relation is REFLEXIVE, ANTISYMMETRIC + TRANSITIVE (RAT)
e.g. ≤ is partial order as it reflexive (as x can = y), antisymmetric and transitive if x ≤ y and y ≤ z then x ≤ z

Question 33

What is a connex?

Answer 33

R is a connex iff for every x,y ∈ R either:
(x,y) ∈ R
(y, x) ∈ R
x = y

Question 34

What is a total order?

Answer 34

If partial order + connex then must be TOTAL ORDER

e.g. ≤ is partial order and for any x,y either x ≤y OR y ≤ x or y = x so is also a connex
therefore, is a total order