Module #21 - Relations University of Florida Dept. of Computer & Information Science & Engineering COT 3100 Applications of Discrete Structures Dr. Michael P. Frank Slides for a Course Based on the Text Discrete Mathematics & Its Applications (5th Edition) by Kenneth H. Rosen 10/3/2015 (c)2001-2003, Michael P. Frank 1 Module #21 - Relations Module #21: Relations Rosen 5th ed., ch. 7 ~35 slides (in progress), ~2 lectures 10/3/2015 (c)2001-2003, Michael P. Frank 2 Module #21 - Relations Binary Relations • Let A, B be any sets. A binary relation R from A to B, written (with signature) R:A×B, or R:A,B, is (can be identified with) a subset of the set A×B. – E.g., let < : N↔N :≡ {(n,m) | n < m} • The notation a R b or aRb means that (a,b)R. – E.g., a < b means (a,b) < • If aRb we may say “a is related to b (by relation R)”, – or just “a relates to b (under relation R)”. • A binary relation R corresponds to a predicate function PR:A×B→{T,F} defined over the 2 sets A,B; – e.g., predicate “eats” :≡ {(a,b)| organism a eats food b} 10/3/2015 (c)2001-2003, Michael P. Frank 3 Module #21 - Relations Complementary Relations • Let R:A,B be any binary relation. • Then, R:A×B, the complement of R, is the binary relation defined by R :≡ {(a,b) | (a,b)R} = (A×B) − R • Note this is just R if the universe of discourse is U = A×B; thus the name complement. • Note the complement of R is R. Example: < = {(a,b) | (a,b)<} = {(a,b) | ¬a<b} = ≥ 10/3/2015 (c)2001-2003, Michael P. Frank 4 Module #21 - Relations Inverse Relations • Any binary relation R:A×B has an inverse relation R−1:B×A, defined by R−1 :≡ {(b,a) | (a,b)R}. E.g., <−1 = {(b,a) | a<b} = {(b,a) | b>a} = >. • E.g., if R:People→Foods is defined by a R b a eats b, then: b R−1 a b is eaten by a. (Passive voice.) 10/3/2015 (c)2001-2003, Michael P. Frank 5 Module #21 - Relations Relations on a Set • A (binary) relation from a set A to itself is called a relation on the set A. • E.g., the “<” relation from earlier was defined as a relation on the set N of natural numbers. • The (binary) identity relation IA on a set A is the set {(a,a)|aA}. 10/3/2015 (c)2001-2003, Michael P. Frank 6 Module #21 - Relations Reflexivity • A relation R on A is reflexive if aA, aRa. – E.g., the relation ≥ :≡ {(a,b) | a≥b} is reflexive. • A relation R is irreflexive iff its complementary relation R is reflexive. – Example: < is irreflexive, because ≥ is reflexive. – Note “irreflexive” does NOT mean “not reflexive”! • For example: the relation “likes” between people is not reflexive, but it is not irreflexive either. – Since not everyone likes themselves, but not everyone dislikes themselves either! 10/3/2015 (c)2001-2003, Michael P. Frank 7 Module #21 - Relations Symmetry & Antisymmetry • A binary relation R on A is symmetric iff R = R−1, that is, if (a,b)R ↔ (b,a)R. – E.g., = (equality) is symmetric. < is not. – “is married to” is symmetric, “likes” is not. • A binary relation R is antisymmetric if a≠b, (a,b)R → (b,a)R. – Examples: < is antisymmetric, “likes” is not. – Exercise: prove this definition of antisymmetric is equivalent to the statement that RR−1 IA. 10/3/2015 (c)2001-2003, Michael P. Frank 8 Module #21 - Relations Transitivity • A relation R is transitive iff (for all a,b,c) (a,b)R (b,c)R → (a,c)R. • A relation is intransitive iff it is not transitive. • Some examples: – “is an ancestor of” is transitive. – “likes” between people is intransitive. – “is located within 1 mile of” is… ? 10/3/2015 (c)2001-2003, Michael P. Frank 9 Module #21 - Relations Totality • A relation R:A×B is total if for every aA, there is at least one bB such that (a,b)R. • If R is not total, then it is called strictly partial. • A partial relation is a relation that might be strictly partial. (Or, it might be total.) – In other words, all relations are considered “partial.” 10/3/2015 (c)2001-2003, Michael P. Frank 10 Module #21 - Relations Functionality • A relation R:A×B is functional if, for any aA, there is at most 1 bB such that (a,b)R. – “R is functional” aA: ¬b1≠b2B: aRb1 aRb2. – Iff R is functional, then it corresponds to a partial function R:A→B • where R(a)=b aRb; e.g. • R is – E.g., The relation aRb :≡ “a + b = 0” yields the function −(a) = b. antifunctional if its inverse relation R−1 is functional. – Note: A functional relation (partial function) that is also antifunctional is an invertible partial function. • R is a total function R:A→B if it is both functional and total, that is, for any aA, there is exactly 1 b such that (a,b)R. I.e., aA: ¬!b: aRb. – If R is functional but not total, then it is a strictly partial function. – Exercise: Show that iff R is functional and antifunctional, and both it and its inverse are total, then it is a bijective function. 10/3/2015 (c)2001-2003, Michael P. Frank 11 Module #21 - Relations Lambda Notation • The lambda calculus is a formal mathematical language for defining and operating on functions. – It is the mathematical foundation of a number of functional (recursive function-based) programming languages, such as LISP and ML. • It is based on lambda notation, in which “λa: f(a)” is a way to denote the function f without ever assigning it a specific symbol. – E.g., (λx. 3x2+2x) is a name for the function f:R→R where f(x)=3x2+2x. • Lambda notation and the “such that” operator “” can also be used to compose an expression for the function that corresponds to any given functional relation. – Let R:A×B be any functional relation on A,B. – Then the expression (λa: b aRb) denotes the function f:A→B where f(a) = b iff aRb. • E.g., If I write: f :≡ (λa: b a+b = 0), this is one way of defining the function f(a)=−a. 10/3/2015 (c)2001-2003, Michael P. Frank 12 Module #21 - Relations Composite Relations • Let R:A×B, and S:B×C. Then the composite SR of R and S is defined as: SR = {(a,c) | b: aRb bSc} • Note that function composition fg is an example. • Exer.: Prove that R:A×A is transitive iff RR = R. • The nth power Rn of a relation R on a set A can be defined recursively by: R0 :≡ IA ; Rn+1 :≡ RnR for all n≥0. – Negative powers of R can also be defined if desired, by R−n :≡ (R−1)n. 10/3/2015 (c)2001-2003, Michael P. Frank 13 Module #21 - Relations §7.2: n-ary Relations • An n-ary relation R on sets A1,…,An, written (with signature) R:A1×…×An or R:A1,…,An, is simply a subset R A1× … × An. • The sets Ai are called the domains of R. • The degree of R is n. • R is functional in the domain Ai if it contains at most one n-tuple (…, ai ,…) for any value ai within domain Ai. 10/3/2015 (c)2001-2003, Michael P. Frank 14 Module #21 - Relations Relational Databases • A relational database is essentially just an n-ary relation R. • A domain Ai is a primary key for the database if the relation R is functional in Ai. • A composite key for the database is a set of domains {Ai, Aj, …} such that R contains at most 1 n-tuple (…,ai,…,aj,…) for each composite value (ai, aj,…)Ai×Aj×… 10/3/2015 (c)2001-2003, Michael P. Frank 15 Module #21 - Relations Selection Operators • Let A be any n-ary domain A=A1×…×An, and let C:A→{T,F} be any condition (predicate) on elements (n-tuples) of A. • Then, the selection operator sC is the operator that maps any (n-ary) relation R on A to the n-ary relation of all n-tuples from R that satisfy C. – I.e., RA, sC(R) = {aR | sC(a) = T} 10/3/2015 (c)2001-2003, Michael P. Frank 16 Module #21 - Relations Selection Operator Example • Suppose we have a domain A = StudentName × Standing × SocSecNos • Suppose we define a certain condition on A, UpperLevel(name,standing,ssn) :≡ [(standing = junior) (standing = senior)] • Then, sUpperLevel is the selection operator that takes any relation R on A (database of students) and produces a relation consisting of just the upperlevel classes (juniors and seniors). 10/3/2015 (c)2001-2003, Michael P. Frank 17 Module #21 - Relations Projection Operators • Let A = A1×…×An be any n-ary domain, and let {ik}=(i1,…,im) be a sequence of indices all falling in the range 1 to n, – That is, where 1 ≤ ik ≤ n for all 1 ≤ k ≤ m. • Then the projection operator on n-tuples is defined by: P{ i k } : A Ai1 Ai m P{ i k } ( a1 ,..., a n ) ( a i1 ,..., a i m ) 10/3/2015 (c)2001-2003, Michael P. Frank 18 Module #21 - Relations Projection Example • Suppose we have a ternary (3-ary) domain Cars=Model×Year×Color. (note n=3). • Consider the index sequence {ik}= 1,3. (m=2) • Then the projection P{i }simply maps each tuple k (a1,a2,a3) = (model,year,color) to its image: ( a i1 , a i 2 ) ( a1 , a 3 ) ( model , color ) • This operator can be usefully applied to a whole relation RCars (a database of cars) to obtain a list of the model/color combinations available. 10/3/2015 (c)2001-2003, Michael P. Frank 19 Module #21 - Relations Join Operator • Puts two relations together to form a sort of combined relation. • If the tuple (A,B) appears in R1, and the tuple (B,C) appears in R2, then the tuple (A,B,C) appears in the join J(R1,R2). – A, B, and C here can also be sequences of elements (across multiple fields), not just single elements. 10/3/2015 (c)2001-2003, Michael P. Frank 20 Module #21 - Relations Join Example • Suppose R1 is a teaching assignment table, relating Professors to Courses. • Suppose R2 is a room assignment table relating Courses to Rooms,Times. • Then J(R1,R2) is like your class schedule, listing (professor,course,room,time). 10/3/2015 (c)2001-2003, Michael P. Frank 21 Module #21 - Relations §7.3: Representing Relations • Some ways to represent n-ary relations: – With an explicit list or table of its tuples. – With a function from the domain to {T,F}. • Or with an algorithm for computing this function. • Some special ways to represent binary relations: – With a zero-one matrix. – With a directed graph. 10/3/2015 (c)2001-2003, Michael P. Frank 22 Module #21 - Relations Using Zero-One Matrices • To represent a binary relation R:A×B by an |A|×|B| 0-1 matrix MR = [mij], let mij = 1 iff (ai,bj)R. • E.g., Suppose Joe likes Susan and Mary, Fred likes Mary, and Mark likes Sally. • Then the 0-1 matrix Susan Mary Sally representation Joe 1 0 1 of the relation Fred 0 1 0 Likes:Boys×Girls relation is: 0 Mark 0 1 10/3/2015 (c)2001-2003, Michael P. Frank 23 Module #21 - Relations Zero-One Reflexive, Symmetric • Terms: Reflexive, non-reflexive, irreflexive, symmetric, asymmetric, and antisymmetric. – These relation characteristics are very easy to recognize by inspection of the zero-one matrix. 1 1 any thing any- thing 1 1 0 0 anything any- thing 0 0 Reflexive: Irreflexive: all 1’s on diagonal all 0’s on diagonal 10/3/2015 1 1 0 0 Symmetric: all identical across diagonal (c)2001-2003, Michael P. Frank 1 0 0 0 0 1 Antisymmetric: all 1’s are across from 0’s 24 Module #21 - Relations Using Directed Graphs • A directed graph or digraph G=(VG,EG) is a set VG of vertices (nodes) with a set EGVG×VG of edges (arcs,links). Visually represented using dots for nodes, and arrows for edges. Notice that a relation R:A×B can be represented as a graph GR=(VG=AB, EG=R). Matrix representation MR: Joe Fred Mark 10/3/2015 Susan 1 0 0 Mary 1 1 0 Sally 0 0 1 Graph rep. GR: (c)2001-2003, Michael P. Frank Edge set EG (blue arrows) Joe Fred Mark Susan Mary Sally Node set VG (black dots) 25 Module #21 - Relations Digraph Reflexive, Symmetric It is extremely easy to recognize the reflexive/irreflexive/ symmetric/antisymmetric properties by graph inspection. Reflexive: Every node has a self-loop Irreflexive: No node links to itself These are asymmetric & non-antisymmetric 10/3/2015 Symmetric: Every link is bidirectional Antisymmetric: No link is bidirectional These are non-reflexive & non-irreflexive (c)2001-2003, Michael P. Frank 26 Module #21 - Relations §7.4: Closures of Relations • For any property X, the “X closure” of a set A is defined as the “smallest” superset of A that has the given property. • The reflexive closure of a relation R on A is obtained by adding (a,a) to R for each aA. I.e., it is R IA • The symmetric closure of R is obtained by adding (b,a) to R for each (a,b) in R. I.e., it is R R−1 • The transitive closure or connectivity relation of R is obtained by repeatedly adding (a,c) to R for each (a,b),(b,c) in R. – I.e., it is R * R n Z 10/3/2015 n (c)2001-2003, Michael P. Frank 27 Module #21 - Relations Paths in Digraphs/Binary Relations • A path of length n from node a to b in the directed graph G (or the binary relation R) is a sequence (a,x1), (x1,x2), …, (xn−1,b) of n ordered pairs in EG (or R). – An empty sequence of edges is considered a path of length 0 from a to a. – If any path from a to b exists, then we say that a is connected to b. (“You can get there from here.”) • A path of length n≥1 from a to itself is called a circuit or a cycle. • Note that there exists a path of length n from a to b in R if and only if (a,b)Rn. 10/3/2015 (c)2001-2003, Michael P. Frank 28 Module #21 - Relations Simple Transitive Closure Alg. A procedure to compute R* with 0-1 matrices. procedure transClosure(MR:rank-n 0-1 mat.) A := B := MR; for i := 2 to n begin A := A⊙MR; B := B A {join} {note A represents Ri, B represents end R } return B {Alg. takes Θ(n4) time} i i j 1 10/3/2015 (c)2001-2003, Michael P. Frank 29 Module #21 - Relations A Faster Transitive Closure Alg. procedure transClosure(MR:rank-n 0-1 mat.) A := MR; for i := 1 to log2 n begin 2 1 A := A⊙(A+In); {A represents R i } j 1 end return A {Alg. takes only Θ(n3 log n) time!} i 1 10/3/2015 (c)2001-2003, Michael P. Frank 30 Module #21 - Relations Roy-Warshall Algorithm • Uses only Θ(n3) operations! Procedure Warshall(MR : rank-n 0-1 matrix) W := MR for k := 1 to n for i := 1 to n for j := 1 to n wij := wij (wik wkj) return W {this represents R*} wij = 1 means there is a path from i to j going only through nodes ≤k 10/3/2015 (c)2001-2003, Michael P. Frank 31 Module #21 - Relations §7.5: Equivalence Relations • An equivalence relation (e.r.) on a set A is simply any binary relation on A that is reflexive, symmetric, and transitive. – E.g., = itself is an equivalence relation. – For any function f:A→B, the relation “have the same f value”, or =f :≡ {(a1,a2) | f(a1)=f(a2)} is an equivalence relation, • e.g., let m=“mother of” then =m = “have the same mother” is an e.r. 10/3/2015 (c)2001-2003, Michael P. Frank 32 Module #21 - Relations Equivalence Relation Examples • “Strings a and b are the same length.” • “Integers a and b have the same absolute value.” • “Real numbers a and b have the same fractional part.” (i.e., a − b Z) • “Integers a and b have the same residue modulo m.” (for a given m>1) 10/3/2015 (c)2001-2003, Michael P. Frank 33 Module #21 - Relations Equivalence Classes • Let R be any equiv. rel. on a set A. • The equivalence class of a, [a]R :≡ { b | aRb } (optional subscript R) – It is the set of all elements of A that are “equivalent” to a according to the eq.rel. R. – Each such b (including a itself) is called a representative of [a]R. • Since f(a)=[a]R is a function of a, any equivalence relation R can be defined using aRb :≡ “a and b have the same f value”, given f. 10/3/2015 (c)2001-2003, Michael P. Frank 34 Module #21 - Relations Equivalence Class Examples • “Strings a and b are the same length.” – [a] = the set of all strings of the same length as a. • “Integers a and b have the same absolute value.” – [a] = the set {a, −a} • “Real numbers a and b have the same fractional part (i.e., a − b Z).” – [a] = the set {…, a−2, a−1, a, a+1, a+2, …} • “Integers a and b have the same residue modulo m.” (for a given m>1) – [a] = the set {…, a−2m, a−m, a, a+m, a+2m, …} 10/3/2015 (c)2001-2003, Michael P. Frank 35 Module #21 - Relations Partitions • A partition of a set A is the set of all the equivalence classes {A1, A2, … } for some equivalence relation on A. – The Ai’s are all disjoint and their union = A. • They “partition” the set into pieces. Within each piece, all members of that set are equivalent to each other. 10/3/2015 (c)2001-2003, Michael P. Frank 36 Module #21 - Relations §7.6: Partial Orderings • A relation R on A is called a partial ordering or partial order iff it is reflexive, antisymmetric, and transitive. – We often use a symbol looking something like ≼ (or analogous shapes) for such relations. – Examples: ≤, ≥ on real numbers, , on sets. – Another example: the divides relation | on Z+. • Note it is not necessarily the case that either a≼b or b≼a. • A set A together with a partial order ≼ on A is called a partially ordered set or poset and is denoted (A, ≼). 10/3/2015 (c)2001-2003, Michael P. Frank 37 Module #21 - Relations Posets as Noncyclical Digraphs • There is a one-to-one correspondence between posets and the reflexive+transitive closures of noncyclical digraphs. – Noncyclical: Containing no directed cycles. • Example: consider the poset ({0,…,10},|) – Its minimal digraph: 10/3/2015 1 2 3 5 7 4 6 9 10 (c)2001-2003, Michael P. Frank 8 0 38 Module #21 - Relations More to come… • More slides on partial orderings to be added in the future… 10/3/2015 (c)2001-2003, Michael P. Frank 39

Descargar
# Slides for Rosen, 5th edition - Computer Science