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)
When is a relation transitive?
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)
What is a P-Closure?
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’
What is an equivalence relation?
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
What is an equivalence class?
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.
Example of an equivalence class: What would [B]R be if
A = { A, B, C, S }
R = {(A,B), (B,C), (S,A)}
- extend the table to include reflexive closures
+ (A,A), (B,B), (C,C), (S,S) - extend the table to include all reflexive closures
+ (B,A), (C,B), (A,S) - extend the table to include all transitive closures
+ (A,C), (S,B) - All values for [B] R would be all values with first value as B so [B] R = {B, A, C}
What is asymmetric?
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.
What is an example of asymmetric?
“Less than or equal to”
as: assuming ≤ ⊆ N X N, if x ≤ y and y ≤ x then x MUST BE = y
What is a partial order?
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
What is a connex?
R is a connex iff for every x,y ∈ R either:
(x,y) ∈ R
(y, x) ∈ R
x = y
What is a total order?
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
