PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Four. Relations and FunctionsSet theory provides a formal foundation for studying objects that are interesting and useful in computer applications. When objects of several sets are related, we use more complex sets called relations and functions to model their relationships. For example, the student body and the academic departments in a college are related through the “Majors” relationship, relating each student to the student’s current major(s). In another example, the set of students and the set of classes offered in a given semester, are related based on the classes taken by each student.In this chapter, we will first study the formal definitions and properties of relations. We will then study a restricted type of relations known as functions.4.1. Relations4.1.1. Notations and DefinitionsDefinition. A relation R defined over sets A and B is a (i.e. any) subset of A B, that is, R A B. Such a relation is a binary relation; the degree of R is 2.For each element (a, b) R of a binary relation R, we also write it as aRb. Example. Let A = {Adam, John, Smith} be a set of students and B = {Art, History, mathematics} be a set of departments. A relation, Student-major, showing the students and their major(s) could be Student-major = {(Adam, History), (Adam, Mathematics), (John, Art), (Smith, History)}.4-1, © Dr. S. LangA binary relation R can be conveniently depicted by a directed graph, in which each pair (a, b) R corresponds to a directed edge from vertex a to vertex b.Example. The following digraph represents the Student-major relation defined in the preceding example (p. 2-1).More generally, A relation can be defined over n sets, n 2.Definition. An n-ary relation R over sets A1, A2, …, An , n 2, is a subset of the cartesian product , that is, R . The degree of R is n.Example. Consider the purchase of a new car, which frequently involves a buyer, a salesperson, a new car, and a trade-in. Thus, a car purchase is a relation of degree 4, because it can be considered as a subset of B S N T, where B, S, N, and T stand for, respectively, the sets of buyers, salespersons, new cars, and trade-ins.AdamJohnSmithArtHistoryMathematicsniiA1niiA14-2, © Dr. S. LangWe note here that a (finite) relation of any degree n can be conveniently represented by a (two-dimensional) table of n columns, in which the rows of the table represent the tuples of the relation. For example, a car sales table as described by the preceding example could be depicted as follows:In fact, the now popular relational database systems have their origin rooted in the theories and properties of relations as studied in set theory, supplemented with implementation techniques.4.1.2. Properties and Manipulations of Binary RelationsBinary relations receive the most thorough studies because their simplicity, and because that they form the basis for studying relations of higher degrees. We will consider the following definitions and notations for binary relations.Definition. Let R A B and S B C denote two relations. The composition of R and S, denoted R S, is a binary relation over A and C defined as follows: R S = {(a, c)| a A and c C, and there exists b B such that aRb and bSc}.Buyer Salesperson New Car Trade-inJ. Smith Mr. No-nonsense Toyota Tacoma Jeep Cherokee4-3, © Dr. S. LangExample. Let A = {a, b, c}, B = {1, 2}, and C = {p, q, r}. Define the relationsR = {(a, 1), (a, 2), (b, 1), (c, 2)}, and S = {(1, p), (1, q), (2, r)}.Then R S = {(a, p), (a, q), (a, r), (b, p), (b, q), (c, r)}.The composition of two binary relations R A B and S B C can also be conveniently depicted by “composing” the digraphs corresponding to R and S. That is, there is a directed edge between x A and y C in R S iff there is a directed path of length 2 connecting vertex x, via a vertex z B, to vertex y, in the composed digraph.Example. Two digraphs depicting R and S, and one digraph for R S of the preceding example:Note that the digraph for the composition relation R S is the “composition” of the two digraphs corresponding to, respectively, the relations R and S.The following theorems summarize simple properties satisfied by relation compositions.abc12pqrR SR Sabcpqr4-4, © Dr. S. LangTheorem. Let R A B, S B C, and T C D denote three binary relations. Then relation compositions satisfy the following associative law:(R S ) T = R (S T ). Proof: We first note that both sides of the equation define a relation over A D. We also note the following:(R S ) T = {(a, d)| a A and d D, and for some c C, (a, c) R S and cTd}, by the definition of T .Since (a, c) R S means aRb and bSc for some b B, by definition of R S, the relation (R S ) T consists of pairs (a, d) A D such that for some b B and some c C, aRb, bSc and cTd. Similarly, by the definition of R ,R (S T ) = {(a, d)| a A and d D, and for some b B, aRb and (b, d) S T}.Since (b, d) S T means bSc and cTd for some c C; thus, the relation R (S T) also consists of pairs (a, d) A D such that for some b B and some c C, aRb, bSc and cTd. Thus, (R S ) T = R (S T ), and the theorem is proved.Example. Define 3 relations over A = {1, 2, 3}: R = {(1,2), (1,3)}, S = {(2,1), (3,2)}, and T = {(1,1), (2,3)}. Then, R S = {(1,1), (1,2)}, S T = {(2,1), (3,3)}, (R S ) T = {(1,1), (1,3)} = R (S T).4-5, © Dr. S. LangTheorem. Let R A B, S B C, and T B C denote 3 binary relations. Then(1) R (S T) = (R S) (R T);(2) R (S T) (R S) (R T). (In general, the two sides of (2) are not equal.)Proof: (1) R (S T) = {(a, c)| a A and c C, and for some b B, aRb and (b, c) S T}, definition of = {(a, c)| a A and c …
View Full Document
Unlocking...