Transcript A,B

INF385T: Information Modeling
Introduction to Unit 2: The Relational Model
Sets, Tuples, and Relations:
Foundations for Relational Model
Slides for October 4
Karen M. Wickett
School of Information
University of Texas at Austin
Fall 2016
Slides based on Rosen Discrete Mathematics 6th editon,
some slides use material from slide set by Michael P. Frank 2003) with adaptations by Mingfu Li (2006).
1
Agenda
• Sets
• Set operations
• Functions
• Relations and their properties
– n-ary relations and their applications
2
Basic notions: set, element [1]
• Definition of set:
– A set is an unordered collection (group) of zero or more objects.
Curly braces are used to represent sets: {a, b, c}
• Definition of element:
– The objects in a set are called elements or members of the set.
– A set is said to contain its elements.
– a  {a, b, c} is read “a is an element of {a, b, c}”
• Key ideas
– Sets are unordered: {a, b, c} = {a, c, b} = {b, a, c}
– Repetitions in a set description are irrelevant: {a, a, b} = {a, b}
– Naming variations are irrelevant. If x=y then {x, y} = {x}= {y}
3
Basic notions: set, element [2]
• Some common confusions pre-empted…
– Elements of sets may be themselves sets: {1, 2, {1}}
• And in particular we note: 1  {1}  {{1}}
– Those are three different things,
• 1 is the number 1, (and it is not a set)
• {1} is a set, with one element: the number 1.
• {{1}} is a set, with one element {1}, which is a set with one
element, the number 1.
• Also, remember the use/mention distinction…
• 1 is a number, “1” is a numeral, “x” is a variable, etc.
• If x=y then {x, y} = {x}= {y}, yes.
• But {“x”, “y”} is a set of two variables, regardless of their value.
– and therefore {“x”, “y”}  {x, y} or {x} or {y} or {“x”} or {“y”} …
or 6.
– Even if x=y …. or x=6.
4
Basic notation for sets: {}s, , {x | P(x)}
•
•
•
•
A, B, C, are variables that refer to arbitrary sets.
“” is used in expressions like “a  B” to say “a is an element of B”.
Two (initial) ways of defining sets
– List: listing all of its elements in curly braces:
• {a, b, c} is the set of whatever 3 objects are denoted by a, b, c.
– Rule
• Informal: “S is the set of all odd numbers”
• Formal: Set builder notation:
– General form: {x | P(x)}
• This is read “the set of all x such that P(x)”
• “P(x)” is an open sentence, usually with x unbound in “P”.
• {x | P(x)} defines the set of all things x such that satisfy the open sentence P(x)
Examples:
• {x | x is an odd number }
… the set of all odd numbers
• {x | x+1 = x*2}
… the set containing just the number 1
• {x | (y)(Lxy) }
… The set of everything that loves something.
Notes:
- sometimes we allow ourselves some informality: “x is an odd number” is not
in any formal formal language.
All additional notation and terminology is defined from these primitives and the constructs of first
order logic.
5
Notational variation (heads up)
•
•
•
•
Set notation: “”;
Teller: “”
Set notation: “”;
Teller: “”
Set notation: “”
Teller: “&”
Set notation: “A,B:…”
– Teller: (s )(t)…” with the domain of quantification understood as restricted
to sets.
• NB, these are equivalent
– a  A and ~(aA)
– A≠ A and ~(A=A)
6
Set Equality
Definition of Set Equality:
Two sets are equal if and only if they have the same elements.
That is, if A and B are sets
then A and B are equal if and only if (x)(xA  xB).
We write A=B if A and B are equal sets.
Formally: A,B: A=B  (x: xA  xB)
– We read that formula this way:
“for all sets A and all sets B, A is identical with B if and only if for
everything x, x is an element of A if and only if x is an element of B”.
– NB it does not matter how the set is defined or denoted.
• For example: The set {1, 2, 3, 4} =
{x | x is an integer where x>0 and x<5 } =
{x | x is a positive integer whose square is >0 and <25}
7
Subset
• Definition of subset:
– The set A is said to be a subset of B if and only if every element of A is also
an element of B.
– We use the notation A B to indicate that A is a subset of B.
– Formal definition:
A,B: AB  x (xA  xB)
To be read: for all sets A and B, A is a subset of B if and only if for
everything x, if x is an element of A then x is an element of B.
-is an element of vs. -is a subset of
(you must be clear about this!)
Let A= {1,2,3,{4},5}
1  A?
{1}  A?
1  A?
{1}  A
4  A?
4  A?
{4}  A?
{4}  A?
8
More terminology: supersets, proper subsets
• Supersets:
– Whenever A is a subset of B one may also say B is a superset of A
(written “AB”).
• Proper (or strict subsets)
– A B (“A is a proper subset of B”) means that A  B but ~(B  A).
– In other words A is a subset of B, but A and B are not identical.
– In still other words, while every element of A is an element of B, there is
some element of B which is not an element of A.
Some equivalent formal definitions of 
• A,B: AB  (x) (xA  xB) & ~(x)(xB  xA)
or
• A,B: AB  (AB) & ~(x) (xB  xA)
or
• A,B: AB  (AB) & (x)[(xB & ~(xA)]
or
• A,B: AB  (AB) & ~(BA)
9
Some theorems about subsets
•
 is reflexive.
S: SS
Every set is a subset of itself
•
 is transitive
S,T,U: (S  T & T  U)  (S  U)
If S is a subset of T and T a subset of U then S is a subset of U
[NB: the parallel statements for  would not be true. This shows that  and  are very
different]
•
 is antisymmetric
S,T: (ST & TS)  S=T
– A set S and a set T are subsets of each other if and only if they are identical
•
S,T: (x)(xS & ST)  x T))
If x is an element of S and S is a subset of T then x is an element of T
•
S,T: ~(SS)
No set is a proper subset of itself
You can prove these by reasoning with first order logic from the definitions given so far.
But each one should seem true intuitively after some reflection.
10
The Empty Set
•
•
 (“null”, “the empty set”) is the unique set that contains no elements whatsoever.
There are a number of ways to specify the empty set:
–  = {} = {x | (x≠x)} = {x | x > x } etc.
• But no matter how it is specified there is only one empty set.
• The empty set is a subet of every set, as we show below.
•
Preempting a confusion…
– NB:  ≠ {0} ≠ {}
• {0} contains one element, 0; so it is not empty.
• {}, [or alternatively: {{}}] contains one element, , so it is not empty.
•  is a subset of every set, but it is not an element of every subset.
11
The Empty Set
•
Theorem: The empty set is a subset of every set: S: S [Rosen 2.1-T1(i)]
Sketch for a proof
Recall the definition of subset: S,T: ST =df x (xS  xT)
Let S be  and T be any set whatsoever:  T =df x (x   xT)
Since  is empty that means that (x ) is always false.
Since a conditional with a false antecedent is always true that means that (x   xT)
is always true, regardless of what T is.
Seems fishy? The problem again is the material conditional
[remember (xS  xT) is logically equivalent to ~[(xS) & ~(xT)]
Or colloquially: if S has no elements at all, then every element of S is an element of T in
the logical sense: there is no element of S which fails to be an element of T.
12
Empty Set Drill
•
Let
A = {1,2,3}
B = {1,2,3,}
C = {1,2,3,{}}
[remember: ={}]
– A
– Yes.
– A
– No.
– B
– Yes.
– B
– Yes.
– {}  A
– No
– {}  A
– No
•
•
•
•
•
•
•
{}  B
{}  B
{}  C
{{}}  C
{}  C
C
C
Yes
No
No
Yes
Yes
Yes
No
13
Cardinality (numerical size) of sets. And the power set.
Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer
we say that s is a finite set and that n is the cardinality of S. The cardinality of S is denoted by
|S|.
Given a set S, the power set of S is the set of all subsets of S. The power set of S is denoted
by P(S), sometimes written 2S.
• If a (finite) set has n elements then its power set has 2n elements.
– You can determine this by the fundamental principle of counting.
• Think about that. Can you see why |P(S)| = 2|S| ?
– NB the number of rows in truth table that represents all possible truth value
combinations for some set S of atomic propositions is also 2n!
• Why? Because every row in the truth table can be represented as the set of just
those propositions which are true, how many such sets are there 2n .
• Remember how we used the fundamental principle of counting to determine the
number of rows in a truth table is 2n ? This should help you see why |P(S)| = 2|S| .
•
The growth in the size if the P(S) with respect to S is exponential.
14
Set operations: Union and Intersection
Definition of union:
Let A and B be sets.
The union of the sets A and B, denoted by (AB), is the set that contains those
elements that are either in A or in B or in both.
– Formally, A,B: AB = {x | xA  xB}.
Definition of intersection:
Let A and B be sets.
The intersection of the sets A and B, denoted by AB , is the set that contains those
elements that are in both A and B.
– Formally, A,B: AB = {x | xA  xB}.
Definition of disjointness: Two sets are disjoint if their intersection is the empty set.
– Formally, A,B: A and B are disjoint  AB = .
15
Set operations: Difference and Complement
Definition of difference:
Let A and B be sets. The difference of A and B, denoted by (A-B) is the set
containing those element that are in A but not in B.
The differene of A and B is also called the complement of B with respect to A
– Formally, A,B: A-B = { x | xA  ~(xB)}
The universe of discourse, the domain over which our individual variables range and
which provides all possible elements for our sets, itself is a set, call it U.
Definition of complement:
Let U be the universe of discourse. The complement of the set A, denoted by /A is the
complement of A with respect to U. In other words, the complement of the set A is
U-A.
16
Examples: Union, Intersection, Disjointness, Difference Complements
• Union
– {1,2,3}  {3,4,5} = {1,2,3,4,5}
• Intersection
– {1,2,3}  {3,4,5} = {3}.
• Disjointness
– {1,2} and {4,5} are disjoint
• Difference
– {1,2,3} - {3} = {1,2}
• Complements
– /{5}  {whole numbers} = {all whole numbers except 5}
17
Venn Diagram
AB
A-B
Set A
B-A
AB
Set B
18
Set Identities
Look at each of these. Grasp intuitively that it is true. They may all be easily proved on the bases of their
FOL definitions.
Identity:
A = A = AU
Domination:
AU = U, A = 
Idempotent:
AA = A = AA
Double complement:
//A = A
Commutative:
AB = BA,
AB = BA
Associative:
A(BC)=(AB)C ,
A(BC)=(AB)C
Distributive:
A (BC)= (AB)  (AC) ,
A (BC)= (AB)  (AC)
A  (A  B) = A
A  ( A  B) = A
A  /A = U
A  /A = 
Absorption:
Complement:
19
DeMorgan’s Law for Sets from DeMorgan’s for SL
A. The complement of the union of two sets is identical to the intersection of their complements,
that is: /(AB) = /A/B
– This is simply DeMorgan’s law for SL, applied to the set builder definitions of union,
intersection, and complement.
A proof that /(AB) = /A/B
1) /(AB)
2) /{x | (xA) v (xB) }
defn union
3) {x | ~[(xA) v (xB)] }
defn of complement
4) {x | ~(xA) & ~(xB)] }
DeMorgan’s for SL
5) {x | /(xA) & /(xB)] }
defn of complement
6) /A/B
defn of intersection.
In short
/(AB) = /A/B because ~[(xA) v (xB)]  [~(xA) & ~(xB)] .
by DeMorgan’s for SL
B. The complement of the intersection of two sets is identical to the union of their complements,
that is: /(AB) = /A/B
– Proof is similar to above
[Knock yourself out]
But in short
/(AB) = /A/B because ~[(xA) & (xB)]  [~(xA) v ~(xB)]
by DeMorgan’s for SL
20
Set notation, SL notation
The symbols for set theory echo the SL notation prominent in their definitions…
Let S and T be sets, and S and T the open sentences that define them.
– S = {x | S(x) }
– T = {x | T(x) }
The following are the definitions of the set theoretic expression in SL notation;
compare the shapes of the symbols:
– ST
(x)(Sx  Tx)
– ST
{ x | xS  xT }
(“” is another symbol for conjunction)
– ST
{ x | xS  xT }
– /S
{ x | ~(xS)}
21
Aristototle’s Square, with set notation added
It is useful to see how the A,E,I,O propositions in the Aristotelian square can be expressed with set
notation. The correspondences indicated on the previous slide are in evidence, look closely.
[F and G are sets corresponding to the predicates F and G].
A All F is G
(x)(Fx Gx)
~(x)~(Fx Gx)
~(x)(Fx & ~Gx)
(F/G) =  [or F  G]
E No F is G
(x)(Fx ~Gx)
~(x)~(Fx ~Gx)
~(x)(Fx & Gx)
FG = 
I Some F is G
~(x)(Fx ~Gx)
(x)~(Fx ~Gx)
(x)(Fx & Gx)
FG ≠ 
O Some F is not G
~(x)(Fx Gx)
(x)~(Fx Gx)
(x)(Fx & ~Gx)
(F/G) ≠ 
Clearly this is an FOL interpretation of Aristotle as FG is clearly true when F is empty.
22
n-tuples
These are like sets, except that duplicates and order count.
Definition of n-tuple:
The ordered n-tuple (a1, a2, a3, …. an) is the ordered collection that has a1 as its first
element, a2 as its second element …. and an as its nth element.
Terminology:
Empty sequence, singlets, pairs, triples, quadruples, quintuples, …, n-tuples.
Identity
(a1, a2, a3, …. an) is identical to (b1, b2, b3, …. bn) if and only if
ai = bi for all i= 1 …. n)
In other words, elements must match, in order.
Clarifying
– {2,3} and {3,2} are the same set, but different tuples
– {2,2} and {2} are the same set, but different tuples
You will remember ordered 2-tuples as “ordered pairs” or “cartesian coordinates” in algebra.
They are sometimes written with pointy brackets rather than parentheses. E.g. <1,3,9> .
23
Cartesian Products of Sets
•
•
Finally we have enough concepts in play to define cartesian products.
This notion is extremely important in relational databases.
– It is at the heart of the very idea of a relation, and it is also part of the definition of a
join in the relational algebra (and SQL).
•
Definition cartesian product for two sets: Let A and B be sets. The cartesian product of
A and B, denoted by A x B is the set of the ordered paris (a,b), where aA and bB.
– Formally: AB = {(a, b) | aA  bB }.
• example. {a,b}{1,2} = {(a,1),(a,2),(b,1),(b,2)}
• For finite A, B, |AB|=|A||B|.
• Note that the Cartesian product is not commutative: AB: AB=BA.
•
General definition cartesian product: The cartesian product of the sets A1, A2, A3, …,
An, denoted by A1  A2,  A3, …  An, is the set of ordered n-tuples (a1, a2, a3, …. an) ,
where ai belongs to Ai for i = (1, 2, …, n)
– Formally:
A1  A2 …  Ai = {(a1, a2, a3,…, ai) | aiAi for i = 1,2…i}.
This formula is very important; be sure you understand it.
24
 2.3 Functions: basic concepts
•
•
The concept of a function is widely used in describing information modeling systems.
Although a function is a kind of relation, many authors take up this more specific notion first.
•
Definition of function:
Let A and B be non-empty sets.
A function f from A to B is an assignment of exactly one element of B to each element
of A.
We write f(a) = b if b is the unique element of B assigned by the function f to the
element a of A .
If f is a function from A to B we write f:AB.
•
Functions are also called mappings or transformations.
– NB the features that make the assignment a function:
(i) every element of A gets assigned an element from B and
(ii) no element of A gets assigned more than one element from B.
– And NB what is not specified:
e.g., (i) that every element of B get assigned;
(ii) that no two elements of A are assigned the same element from B.
(But these are possible further restrictions).
25
Functions: basic concepts
•
If f is a function from A to B
we say that A is the domain of f
and B is the codomain of f.
•
If f(a)=b, we say that b is the image of a and a is a preimage of b.
•
The range of f is the set of all images of elements of A.
•
If f is a function from A to B we say that f maps A to B.
Key thing to notice:
the range of a function f:AB is the set of the elements in the domain that are actually
assigned by f to elements in A.
So the range may be a proper subset of the codomain.
26
Functions: Kinds
•
Some more standard terminology.
•
One-to-one, or injective functions
– No codomain element is assigned to two domain elements.
• A function f is said to be one-to-one, or injective, if and only if f(a) = f(b) implies
a=b for all a and b in the domain of f.
•
Onto or surjective functions
– Every codomain element is assigned to some domain element.
(i.e. is the image of some element of the domain).
• A function f from A to B is called onto if and only if for every element bB there
is an element bB with f(a)=b.
•
One-to-one correspondence, or bijective functions
– No codomain element is assigned to two domain elements, and every codomain
element is assigned to some domain element.
i.e., an exact pairing, both ways.
• The function f is a one-to-one correspondence if and only if it is both one-to-one
and onto.
27
Inverse function, composition of function
Definition of inverse function:
Let f be a one-to-one correspondence from the set A to the set B.
The inverse function of f is the function that assigns to an element b, belonging to B the
unique element a in a such that f(a) = b.
The inverse function of f is denoted by f -1.
Hence f -1(b) = a when f(a) = b.
Barring polygamy and assuming complete heteronormativity (i.e., assuming one-to-one
corresondence), husband_of and wife_of are inverse functions
Definition of composition:
Let g be a function from the set a to the set b and let f be a function from the set B to the
set C.
The composition of the functions f and g denoted by f o g
is defined by (f o g)(a) = f(g(a))
28
8.2 n-ary Relations
One of the reasons we study sets, tuples, and relations is because the the relational model (relational
databases) is based on the concept of an n-ary relation. But without logic, sets, and tuples, we
would not be in a position to say just what that notion is.
But now we are…
Definition of n-ary relation:
Let A1, A2, …, An be sets.
An n-ary relation on these sets is a subset of A1 x A2 x …, x An (a cartesian product).
– The sets A1, A2, …., An are called the domains of the relation,
– n is called its degree.
So…
• relations are subsets of cartesian products
• … which means a relation is a set of tuples.
• ... and an n-ary relation is a set of n-tuples
The relational databases are called relational because their fundamental data management construct
is the relation … sets of tuples
29