RELATIONS Flashcards
What is a cartesian product?
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)}
What is the notation for cartesian product?
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)}
Does order matter for cartesian products?
E.g. does A X B = B X A ?
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)
What is a relation?
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
Example of relation: Which pairings would relation_example include if A = { 1, 2, 3} B = { a, b, c} ?
relation_example = { (1,b), (2,c), (3,a) }
(example)
What is infix notation for relations?
Written as x R y where (x,y) ∈ R
(pairing (x,y) adhere to rules of relation R and is an element of R)
Example of relation: How does infix notation x < y work?
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
Which other forms can relations be shown in?
Tables = each row pairing is a pairing of relation.
Mapping = values on the left map to their pairing on the right.
How are relations often used?
Often used in databases
e.g. (Molly, Sheppard) ∈ Last_Name as there is a relation of Molly to Sheppard in the Last_Name field.
What is relational composition?
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
How is relational composition written?
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}
How do you draw relational composition through mappings?
Remove the middle relation and follow all relations from set A to point straight to its specific destination in set B.
What is relational inverse?
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)
How is relational inverse written?
R^-1
R^-1 = { (b,a) ∈ B X A | (a,b) ∈ R}
What is domain?
set of all elements of A which have a relation by R to some element in B
How is domain written?
dom(R)
suppose R ⊆ A X B
dom(R) = { a ∈ A | exists b ∈ B such that (a,b) ∈ R}
Important property of all domains =
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
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)}
dom(R) = {B, E, F}
What is range?
set of all elements in B that are related by R to something in A
How is range written?
RAN(R) =
ran(R) = { b ∈ B| exists a ∈ A such that (a,b) ∈ R}
What is an important property of Range?
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
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)}
ran(R) = {1, 3, 4, 5}
When is a relation reflexive?
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)
When is a relation symmetric?
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)
