Discrete math with computers_3

10.4. PROPERTIES OF RELATIONS		233
	Sam	Anna

Joan

Jeanne

Figure 10.5: The IsChildOf Relation

10.4.4Antisymmetric Relations

An antisymmetric relation is one where for all distinct values a and b, it is never the case that both aRb and bRa.

Example 42. The less-than relation (<) is antisymmetric, because it cannot be true that x < y and also y < x.

Example 43. The family relation IsChildOf is antisymmetric; if x is a child of y, than y must be the parent—not the child—of x. For example, suppose the IsChildOf relation contains the following ordered pairs (Figure 10.5):

{(Joan, Sam), (Jeanne, Sam), (Joan, Anna), (Jeanne, Anna)}

Notice that this relation never has both a pair (x, y) and also a pair (y, x).

The antisymmetric property is defined formally as follows:

Definition 40. A binary relation R :: A × A is antisymmetric if

x, y A. xRy yRx → x = y.

The graph of an antisymmetric relation may contain some cycles; for example the relation R = {(1, 2), (2, 3), (3, 1)} has a cycle from 1 to 2 to 3 and back to 1, and the relation R2 = {(1, 1)} has a trivial cycle containing just 1. However, if an antisymmetric relation does have a cycle, then the length of the cycle cannot be 2, although it may be 1, or greater than 2. In other words, this graph will have no cycles of length 2, but it can have cycles of any other length.

Example 44. Given the set A = {1, 2, 3}, the relation

R :: A × A = {(1, 2), (2, 1), (2, 3), (3, 1)}

is not anti-symmetric because both (1, 2) and (2, 1) appear in the set of ordered pairs.

234	CHAPTER 10.	RELATIONS
Example 45. Given the set A = {1, 2, 3}, the relation
	R :: A × A = {(1, 1), (1, 2), (2, 3), (3, 1)}
is anti-symmetric.
Example 46. Given the set A = {1, 2, 3, 4}, and R1, R2, R3		:: A × A, the
relations	R1 = {(1, 2), (2, 3), (4, 1)}

and

R2 = {(1, 1), (2, 2)}

are both antisymmetric, but

R3 = {(1, 3), (3, 1), (2, 3), (3, 2)}

is not antisymmetric.

If a relation R :: A × A is antisymmetric, both of the following statements must be true:

x, y A. x = y → ¬(xRy yRx)

x, y A. x = y → ¬xRy ¬yRx

Both propositions say that for two distinct elements of the domain, the graph diagram of R contains at most one arrow connecting them.

Example 47. Suppose that we were misanthropic and thought people didn’t treat each other well in general. When told that a Helps b and b Helps a, we might retort that a and b must therefore be the same person! We could express this gloomy view of the world as

x, y WorldPopulation. x Helps y y Helps x → x = y.

The software tools define the following functions, which determine whether a finite binary relation is symmetric or antisymmetric:

isSymmetric, isAntisymmetric ::

(Eq a, Show a) => Digraph a -> Bool

Exercise 8. First work out whether the relations in the following expressions are symmetric and whether they are antisymmetric, and then check your conclusions by evaluating the expressions with Haskell:

isSymmetric ([1,2,3],[(1,2),(2,3)]) isSymmetric ([1,2],[(2,2),(1,1)]) isAntisymmetric ([1,2,3],[(2,1),(1,2)]) isAntisymmetric ([1,2,3],[(1,2),(2,3),(3,1)])

10.4. PROPERTIES OF RELATIONS

235

Exercise 9. Which of the following relations are symmetric? Antisymmetric?

(a)The empty binary relation over a set with four nodes;

(b)The = relation;

(c)The ≤ relation;

(d)The < relation.

10.4.5Transitive Relations

If x, y, and z are three people, and you know that x is a sister of y and y is a sister of z, then x must also be a sister of z. Similarly, if you know that x < y and also that y < z, it must also be the case that x < z. Relations that have this property are called transitive relations.

Definition 41. A binary relation R :: A × B is transitive if

x, y, z A. xRy yRz → xRz.

Example 48. The relation R = {(1, 2), (2, 3), (1, 3)} is transitive because it contains (1, 3), which is required by the presence of (1, 2) and (2, 3).

Example 49. The relation R = {(1, 2), (2, 3)} is not transitive because there are pairs (1, 2) and (2, 3) but there is no pair (1, 3).

The (=) relation is transitive, as is the IsAncestorOf relation.

Example 50. The IsMarriedTo relation is not transitive. It is certainly symmetric, because if x IsMarriedTo y then it must also be the case that y IsMarriedTo x. Suppose, however, that x and y are two married people. Then (x, y) and (y, x)

are both in the relation, so, if it were transitive, then (x, x) would also need to be in the relation. Nobody is married to themself, so this cannot be, and the relation is not transitive.

Example 51. Suppose we are flying from one city to another. The relation FlightTo describes the point-to-point flights that are available: for example, (London, Paris) FlightTo because there is a direct flight from London to Paris. This relation is not transitive, because there are flights from many small cities to London, but those small cities don’t have direct flights to Paris. However, the ReachableByAir relation is transitive. In e ect, the airlines define the FlightTo relation, and the travel agents extend this to the more general ReachableByAir relation, which may involve several connecting flights.

As the previous example suggests, a binary relation R can be extended to make a new binary relation RT , such that R RT and RT is transitive. This often entails adding several new ordered pairs. For example, suppose we have a relation CityMap that defines direct street connections, so that (x, y)

236	CHAPTER 10. RELATIONS

Cathedral Museum

Market

Airport

Figure 10.6: The CityMap Relation

Cathedral Museum

Market

Airport

Figure 10.7: The Transitive CityMap Relation

CityMap if there is a street connecting x directly with y (Figure 10.6). The relation could be defined (for a small city) as

{(Cathedral, Museum), (Museum, Market), (Market, Airport)}.

The CityMap relation is not transitive, because there is a street path from Cathedral to Market, but no street connects them directly. Just adding the pair (Cathedral, Market) is not enough to make the relation transitive; a total of three ordered pairs must be added. These are shown as dashed arrows in Figure 10.7. The new pairs that we added to the relation are

{(Cathedral, Market), (Cathedral, Airport), (Museum, Airport)}.

A transitive relation provides a short cut for every path of length 2 or more. To make a relation transitive, we must continue adding new pairs until the new relation is transitive. This process is called taking the transitive closure of the relation.

The software tools contain a definition of the following function, which determines whether a finite binary relation is transitive:

isTransitive ::

(Eq a, Show a) => Digraph a -> Bool

10.5. RELATIONAL COMPOSITION

237

Exercise 10. Determine by hand whether the following relations are transitive, and then check your conclusion using the computer:

isTransitive ([1,2],[(1,2),(2,1),(2,2)]) isTransitive ([1,2,3],[(1,2)])

Exercise 11. Determine which of the following relations on real numbers are transitive: (=), (=), (<), (≤), (>), (≥).

Exercise 12. Which of the following relations are transitive?

(a)The empty relation;

(b)The IsSiblingOf relation;

(c)An irreflexive relation;

(d)The IsAncestorOf relation.

10.5Relational Composition

We can think of a relation R :: A × B as taking us from a point x A to a point y B, assuming that (x, y) R. Now suppose there is another relation S :: B × C, and suppose that (y, z) S, where z C. Using first R and then S, we get from x to z, via the intermediate point y.

We could define a new relation that describes the e ect of doing first R and then S. This is called the composition of R and S, and the notation for it is

R; S.

Example 52. Suppose that we have a relation Flight over the set City, where (a, b) Flight if there is an airline flight from a to b. There is also a relation BusTrip over City, and (c, d) BusTrip if there is a bus connection from c to d. Now, we are interested in a relation that describes where we can go, starting from a city with an airport. The relation Flight ; BusTrip consists of the set of pairs (x, y) such that you can get from x to y by flying first to some intermediate city y, and then taking the bus from y on to z.

The use of a semicolon (;) as the operator for relational composition is common, but not completely standard. Many older mathematics books omit the relational composition operator, using RS to mean the relational composition of R and S. Computer scientists often prefer to make all operators explicit. The use of a semicolon is intended to suggest sequencing: just as statement1 ; statement2 in an imperative programming language means ‘First execute statement1 and then execute statement2 ’, the relational composition R; S means ‘First apply the relation R and then apply the relation S’.

Relational composition is defined formally as follows.

238		CHAPTER 10. RELATIONS
	Paris	Birmingham

London

Figure 10.8: The Route1; Route1 Relation

Definition 42. Let R1 :: A × B be a relation from set A to set B, and R2 :: B × C be a relation from set B to set C. Their relational composition is defined as follows:

R1; R2	::	A × C
R1; R2	=	{(a, c) | a A c C ( b B. (a, b) R1 (b, c) R2)}

The definition just says formally that R1; R2 consists of all the pairs (a, c), such that there is an intermediate connecting point b. This means that (a, b) R1 and (b, c) R2.

Example 53. When we compose two relations, any two links between a and b in the first relation and b and c in the second produce a new link between a and c. Suppose we have a relation Route1 linking Paris and London and Route2 linking London and Birmingham. The composition of Route1 and Route2 yields a new route relation which shows that it is possible to travel taking first Route1 and then Route2, starting from Paris and ending at Birmingham (Figure 10.8). In our diagram, the arcs are of three di erent patterns because they belong to three separate relations.

Sometimes it is useful to compose a relation with itself. A common situation is to start with a relation like Flight, which represents trips consisting of just one flight, starting from one city and ending in another one. The composition Flight; Flight describes all the trips that can be made using exactly two connecting flights.

Another example arises in databases, where queries often cause the database to derive new information from the facts already available. If the system can predict the requirements of some common queries, then some of this new information can be represented as facts, represented as a new relation, speeding up the execution of future queries.

Suppose that we need to know whether a, who died of a hereditary disease, was a blood relative of b. This could mean calculating all of the descendants of a, then checking to see whether b is among them. It might be better to save some of the work done (space permitting) in calculating the descendants of a,

10.5. RELATIONAL COMPOSITION

239

4

1

2

3

Figure 10.9: The R1; R1 Relation

so that when we need to know whether a was a blood relative of c, some of the work need not be repeated.

As an example, when determining whether Joseph and Jane are blood relations, we discover that Joseph IsBloodRelationOf Sarah, Sarah IsBloodRelationOf Jane, and Jane IsBloodRelationOf Joel. During this process, we add the newly discovered fact to the database: Joseph IsBloodRelationOf Jane. Now, when we have a query asking whether Joseph is a blood relation of Joel, the new link represents the two links between Joseph and Jane. This reduces the number of links to be traversed.

In creating the composition of two relations, we look for arcs in the first relation that have terminal nodes matching the starting nodes of arcs in the second relation. This operation requires that we systematically check all arcs in R1 against all arcs in R2.

Example 54. Let’s calculate a relational composition by hand. Let

R1 = {(1, 2), (2, 3), (3, 4)}.

The composition R1; R1 is worked out by deducing all the ordered pairs that correspond to an application of R1 followed by an application of R1.

First we find all the ordered pairs of the form (1, x). R1 has only one ordered pair starting with 1; this is (1, 2). This means the first application of R1 goes from 1 to 2, and the (2, 3) pair means that the second application goes to 3. Therefore the composition R1; R1 should contain a pair (1, 3). Next, consider what happens starting with 2: the (2, 3) pair goes from 2 to 3, and looking at all the available pairs {(1, 2), (2, 3), (3, 4)} shows that 3 then goes to 4. Finally, we see what happens when we start with 3: the first application of R1 goes from 3 to 4, but there is no pair of the form (4, x). This means that there cannot be any pair of the form (3, x) in the composition R1; R1. The result of all these comparisons is R1; R1 = {(1, 3), (2, 4)} (Figure 10.9). In our diagram, the new relation is indicated by arrows with dashes.

The calculation in Example 54 is straightforward and tedious—well suited for computers. The software tools define a function relationalComposition

240	CHAPTER 10. RELATIONS

that implements this calculation: it defines a new relation giving two existing ones, by working out all the ordered pairs in their relational composition.

relationalComposition ::

(Eq a, Show a, Eq b, Show b, Eq c, Show c) => Set (a,b) -> Set (b,c) -> Set (a,c)

Exercise 13. First work out by hand the ordered pairs in the following relational compositions, and then check your results using the computer:

relationalComposition [(1,2),(2,3)] [(3,4)] relationalComposition [(1,2)] [(1,3)]

Exercise 14. (a) Find the composition of the following relations:

{(Alice, Bernard), (Carol, Daniel)} and {(Bernard, Carol)}.

(b){(a, b), (aa, bb)} and {(b, c), (cc, bb)}

(c)R; R, where the relation R is defined as

R= {(1, 2), (2, 3), (3, 4), (4, 1)}.

(d){(1, 2)} and {(3, 4)}

(e)The empty set and any other relation.

10.6Powers of Relations

As we saw in the previous section, the composition Flight; Flight defines the relation describing all possible trips that consist of two connected flights. More generally, we might want to define a relation defining all possible trips that consist of n connected flights, where n is a natural number. This is called the nth power of the relation. For a relation R, the nth power is the composition R; R; · · · ; R, where R appears n times, and its notation is Rn. Notice in particular that R2 = R; R, and R1 = R. It is also convenient to define R0 to be the identity relation.

When a relation R is composed with itself n times, producing Rn, a path of length n in R from a to b causes there to be a single link (a, b) in the power relation Rn.

Suppose that we have to calculate the relationships between several people in our database, and that the original facts are these (Figure 10.10):

Andrew	IsParentOf	Beth
Beth	IsParentOf	Ian
Beth	IsParentOf	Joanna
Ian	IsParentOf	William

William IsParentOf Tina

10.6. POWERS OF RELATIONS

241

Tina

William

Andrew

Joanna

Beth	Ian

Figure 10.10: The IsParentOf Relation

Tina William

Andrew

Joanna

Beth	Ian

Figure 10.11: The Relation IsParentOf 2

Now, we will calculate the powers of this relation. The 0th power is just the identity relation, and the first power IsParentOf 1 is simply the IsParentOf relation. The higher powers will tell us the grandparents, great grandparents, and great great grandparents. You should expect to see that each of the new relations IsParentOf 2, IsParentOf 3, and IsParentOf 4 connect up the starting and ending points of a path 2, 3, and 4 arcs long within the original IsParentOf relation. In the following diagrams, the arrows with dashes indicate relations defined as a power, while all other arrows belong to the IsParentOf relation.

If we compose the IsParentOf relation with itself (i.e., IsParentOf 2), we have the grandparent relation (Figure 10.11):

Andrew	IsGrandParentOf	Ian
Andrew	IsGrandParentOf	Joanna
Beth	IsGrandParentOf	William

Ian IsGrandParentOf Tina

242	CHAPTER 10. RELATIONS

Tina

William

Andrew

Joanna

Beth Ian

Figure 10.12: The IsParentOf 3 Relation

Tina

William

Andrew

Joanna

Beth

Ian

Figure 10.13: The IsParentOf 4 Relation

Now if we compose the IsGrandParentOf relation with the original relation, we obtain the great grand parent relation (Figure 10.12):

Andrew IsGreatGrandParentOf William

Beth IsGreatGrandParentOf Tina

Figure 10.13 shows the composition of the IsGreatGrandParentOf relation with IsParentOf ; thus we have just calculated the fourth power of the IsParentOf relation.

Andrew IsGreatGreatGrandParentOf Tina

We will now give the formal definition of relational powers. The definition is recursive, because we have to define the meaning of Rn for all n. The base case of the recursion will be R0, which is just the identity relation (it’s like taking zero flights from a city, which leaves you where you started). The recursive case defines Rn+1 using the value of Rn.