Introduction to Database Systems – Part 2
Math Concepts
What are the Math Concepts behind Databases?
Set
Tuple
Cartesian Product of Sets
Relation
Set Notation
Set Notation
We need set notation to represent formal definitions in this course.
A set is a collection of distinct elements.
Two basic properties of sets
The elements in a set have no order.
e.g., {1, 2, 3} = {2, 3, 1}
Each element can not be in the set more than once.
e.g., {Monday, Monday, Tuesday, Wednesday, Thursday, Friday,
Friday} is Not a set. Note that Multisets allow to have duplicate
elements.
Set Notation
Two ways of specifying a set
1 {x1, . . . , xn} (i.e., list all the elements in a set)
{ 2, 3, 4, 5 }
{Sydney, Melbourne, Canberra}
{} or ∅, i.e., the empty set.
2 {x |ϕ} (i.e., describe the elements that satisfy a property ϕ)
{x | x is a student currently enrolled in COMP7240}
{x | x is an integer and x > 0}
Set Operations
Membership: x ∈ A if x is in the set A; x 6∈ A if x is not in the set A.
Set Operations
Equality: If A and B have the same elements, we write A = B; otherwise we
write A 6= B.
{x | x is an integer, x > 1 and x < 6 } = {2, 3, 4, 5} If one set contains some element that is not in the other set, then they are different. Set Operations Subset: A is called a subset of B if every element of A is in B and we write A ⊆ B; Proper subset: A is called a proper subset of B if A ⊆ B and A and B are not equal, and we write A ⊂ B. Set Operations Subset: A is called a subset of B if every element of A is in B and we write A ⊆ B; Proper subset: A is called a proper subset of B if A ⊆ B and A and B are not equal, and we write A ⊂ B. Set Operations Union: A ∪ B for the set containing everything in A and everything in B. {3, 4, 5} ∪ {3, 5, 7, 9} = {3, 4, 5, 7, 9}. Set Operations Intersection: A ∩ B for the set of elements that are in both A and B {3, 4, 5} ∩ {3, 5, 7, 9} = {3, 5}. Set Operations Difference: A− B is the elements from A that are not in B {3, 4, 5} − {3, 5, 7, 9} = {4}. Set Operations – Exercise Let A = {1, 2, 3} and B = {true, false}. Which of the following are correct? 1 {2} ∈ A No! {2} ⊂ A and 2 ∈ A 2 true ⊂ B No! true ∈ B and {true} ⊂ B 3 {2, 3} ⊆ A ∪ B Yes! A ∪ B = {1, 2, 3, true, false} 4 2 ∈ A ∩ B No! A ∩ B = {} 5 2 ∈ A− {1, 3, 5} Yes! A− {1, 3, 5} = {2} 6 {1, 4} ⊆ A− B No! A− B = {1, 2, 3} 7 ∅ ∩ B = ∅ Yes! ∅ = {}, the empty set Tuple Notation Tuple Notation A tuple is an ordered list of n elements. (1, 2, 3, 4, 5) (Melbourne,Sydney ,Canberra) Two tuples are equal if they have the same elements in the same order. (1, 2, 3) 6= (2, 3, 1) (i.e., the order does matter!) The same element can be in a tuple twice. (Monday, Monday, Tuesday, Wednesday, Thursday, Friday, Friday) is a tuple. Ordered pairs are special cases of tuples. Cartesian Product of Sets Cartesian Product of Sets Cartesian Product of Sets Cartesian Product of Sets The Cartesian product operation takes an ordered list of sets, and returns a set of tuples. Cartesian product D1 × ...× Dn is the set of all possible combinations of values from the sets D1, ...,Dn. It contains all the tuples with the first element from the first set, the second element from the second set, ... For example, A× B = {(a, b) | a ∈ A and b ∈ B}. If A = {2, 3} and B = {Clubs,Diamonds,Hearts,Spades} Then A× B = {(2,Clubs), (2,Diamonds), (2,Hearts), (2,Spades), (3,Clubs), (3,Diamonds), (3,Hearts), (3,Spades)}. (2,Clubs) ∈ A× B, (Spades, 3) /∈ A× B, (4,Hearts) /∈ A× B {(3,Clubs), (3,Diamonds), (3,Hearts), (3,Spades)} ⊆ A× B Relation Notation Relation Notation Relation Notation A relation is a subset of a Cartesian product of sets. Example Let X = {Canberra,Paris,Tokyo,Kyoto}, and Y = {Australia,France, Japan} Let R = {(a, b)|a ∈ X , b ∈ Y and a is a city in b}. It is easy to see that R is a relation R ⊆ X × Y . (Canberra,Australia) ∈ R, (Paris,France) ∈ R but (Tokyo,France) 6∈ R, (France, Japan) 6∈ R Relation Notation A relation is a subset of a Cartesian product of sets. Example Let Z = {...,−1, 0, 1, 2, ...}, the set of all integers Let R = {(x , y) | x ∈ Z, y ∈ Z and x < y}. It is easy to see that R is a relation. R ⊆ Z× Z. (0, 1) ∈ R, (−4,−2) ∈ R but (0, 0) 6∈ R, (100,−2) 6∈ R.