Chapter 09 - Relations

Relations

Relationships between elements of more than two sets arise in many contexts. These relationships can be represented by -ary relations, which are collections of -tuples. Such relations are the basis of the relational data model, the most common way to store information in computer databases.

Relations and Their Properties

The most direct way to express a relationship between elements of two sets is to use ordered pairs made up of two related elements. For this reason, sets of ordered pairs are called binary relations.

• Definition: Let and be sets. A binary relation from to is a subset of .

In other words, a binary relation from to is a set of ordered pairs, where the first element of each ordered pair comes from and the second element comes from . We use the notation to denote that and to denote that .

• Definition: A relation on a set is a relation from to .

Functions as Relations

If is a relation from to such that every element in is the first element of exactly one ordered pair of then a function can be defined with as its graph. A relation can be used to express a one-to-many relationship between the elements of the sets and , where an element of may be related to more than one element of .

A function represents a relation where exactly one element of is related to each element of . Relations are a generalization of graphs of functions; they can be used to express a much wider class of relationships between sets.

Properties of Relations

In some relations an element is always related to itself. For instance, let be the relation on the set of all people consisting of pairs where and have the same mother and the same father. Then for every person .

• Definition: A relation on a set is called reflexive if for every element .

Using quantifiers we see that the relation on the set is reflexive if where the universe of discourse is the set of all elements in .

• Definition: A relation on a set is called symmetric if whenever for all A relation on a set such that for all if and then is called antisymmetric.

Using quantifiers, we see that the relation on the set is symmetric if . Similarly, the relation on the set is antisymmetric if .

• Definition: A relation on a set is called transitive if whenever and then for all .

Using quantifiers we see that the relation on a set is transitive if we have .

Combining Relations

Because relations from to are subsets of two relations from to can be combined in any way two sets can be combined.

• Definition: Let be a relation from a set to a set and a relation from to a set . The composite of and is the relation consisting of ordered pairs where and for which there exists an element such that and . We denote the composite of and by .

The powers of a relation can be recursively defined from the definition of a composite of two relations.

• Definition: Let be a relation on the set . The powers are defined recursively by and .

• Theorem: The relation on a set is transitive if and only if for .

-ary Relations and Their Applications

We will study relationships among elements from more than two sets in this section. These relationships are called -ary relations.

• Definition: Let be sets. An -ary relation on these sets is a subset of . The sets are called the domains of the relation, and is called its degree.

Databases and Relations

The time required to manipulate information in a database depends on how this information is stored. Because of the importance of these operations, various methods for representing databases have been developed. We will discuss one of these methods, called the relational data model, based on the concept of a relation.

A database consists of records, which are -tuples, made up of fields. The fields are the entries of the -tuples. Relations used to represent databases are also called tables.

A domain of an -ary relation is called a primary key when the value of the -tuple from this domain determines the -tuple. That is, a domain is a primary key when no two -tuples in the relation have the same value from this domain.

Records are often added to or deleted from databases. Because of this, the property that a domain is a primary key is time-dependent. Consequently, a primary key should be chosen that remains one whenever the database is changed. The current collection of n-tuples in a relation is called the extension of the relation. The more permanent part of a database, including the name and attributes of the database, is called its intension. When selecting a primary key, the goal should be to select a key that can serve as a primary key for all possible extensions of the database.

Combinations of domains can also uniquely identify n-tuples in an -ary relation. When the values of a set of domains determine an -tuple in a relation, the Cartesian product of these domains is called a composite key.

Operations on -ary Relations

There are a variety of operations on n-ary relations that can be used to form new -ary relations. Applied together, these operations can answer queries on databases that ask for all -tuples that satisfy certain conditions.

• Definition: Let be an -ary relation and a condition that elements in may satisfy. Then the selection operator maps the -ary relation to the -ary relation of all -tuples from that satisfy the condition .

Projections are used to form new -ary relations by deleting the same fields in every record of the relation.

• Definition: The projection where , maps the -tuple () to the -tuple (), where .

• Definition: Let be a relation of degree and a relation of degree . The join where and is a relation of degree that consists of all -tuples where the -tuple belongs to and the -tuple belongs to .

Representing Relations

In this section, all relations we study will be binary relations.

Representing Relations Using Matrices

A relation between finite sets can be represented using a zero–one matrix. Suppose that is a relation from to . The relation can be represented by the matrix where Recalling the definition of the transpose of a matrix, we see that is symmetric if and only if that is, if is a symmetric matrix.

Representing Relations Using Digraphs

There is another important way of representing a relation using a pictorial representation. Each element of the set is represented by a point, and each ordered pair is represented using an arc with its direction indicated by an arrow.

• Definition: A directed graph, or digraph, consists of a set of vertices (or nodes) together with a set of ordered pairs of elements of called edges (or arcs). The vertex is called the initial vertex of the edge and the vertex is called the terminal vertex of this edge.

An edge of the form is represented using an arc from the vertex a back to itself. Such an edge is called a loop.

Closures of Relations

A computer network has data centers in Boston, Chicago, Denver, Detroit, New York, and San Diego. There are direct, one-way telephone lines from Boston to Chicago, from Boston to Detroit, from Chicago to Detroit, from Detroit to Denver, and from New York to San Diego.

Let be the relation containing if there is a telephone line from the data center in to that in . How can we determine if there is some (possibly indirect) link composed of one or more telephone lines from one center to another? Because not all links are direct, such as the link from Boston to Denver that goes through Detroit, cannot be used directly to answer this. In the language of relations, is not transitive, so it does not contain all the pairs that can be linked. As we will show in this section, we can find all pairs of data centers that have a link by constructing a transitive relation containing such that is a subset of every transitive relation containing . Here, is the smallest transitive relation that contains . This relation is called the transitive closure of .

Different Types of Closures

If is a relation on a set it may or may not have some property such as reflexivity, symmetry, or transitivity. When does not enjoy property we would like to find the smallest relation on with property that contains .

• Definition: If is a relation on a set then the closure of with respect to if it exists, is the relation on with property that contains and is a subset of every subset of containing with property .

Paths in Directed Graphs

We will see that representing relations by directed graphs helps in the construction of transitive closures. A path in a directed graph is obtained by traversing along edges (in the same direction as indicated by the arrow on the edge).

• Definition: A path from to in the directed graph is a sequence of edges in where is a nonnegative integer, and and that is, a sequence of edges where the terminal vertex of an edge is the same as the initial vertex in the next edge in the path. This path is denoted by and has length . We view the empty set of edges as a path of length zero from to . A path of length that begins and ends at the same vertex is called a circuit or cycle.

A path in a directed graph can pass through a vertex more than once. Moreover, an edge in a directed graph can occur more than once in a path.

• Theorem: Let be a relation on a set . There is a path of length where is a positive integer, from to if and only if .

Transitive Closures

We now show that finding the transitive closure of a relation is equivalent to determining which pairs of vertices in the associated directed graph are connected by a path.

• Definition: Let be a relation on a set . The connectivity relation consists of the pairs such that there is a path of length at least one from to in .

Because consists of the pairs such that there is a path of length from to it follows that is the union of all the sets . In other words, The connectivity relation is useful in many models.

• Theorem: The transitive closure of a relation equals the connectivity relation .

Now that we know that the transitive closure equals the connectivity relation, we turn our attention to the problem of computing this relation. We do not need to examine arbitrarily long paths to determine whether there is a path between two vertices in a finite directed graph.

• Lemma: Let be a set with elements, and let be a relation on . If there is a path of length at least one in from to then there is such a path with length not exceeding . Moreover, when if there is a path of length at least one in from to then there is such a path with length not exceeding .

• Theorem: Let be the zero–one matrix of the relation on a set with elements. Then the zero–one matrix of the transitive closure is Now let’s look at the naive algorithm for computing the transitive closures

• Algorithm: A Procedure for Computing the Transitive Closure. procedure ( : zero–one matrix) for to return is the zero–one matrix for

The next section describes a more efficient algorithm for finding transitive closures.

Warshall’s Algorithm

Warshall’s algorithm is an efficient method for computing the transitive closure of a relation. Algorithm above can find the transitive closure of a relation on a set with elements using bit operations. However, the transitive closure can be found by Warshall’s algorithm using only bit operations.

Suppose that is a relation on a set with elements. Let be an arbitrary listing of these elements. The concept of the interior vertices of a path is used in Warshall’s algorithm. If is a path, its interior vertices are that is, all the vertices of the path that occur somewhere other than as the first and last vertices in the path.

• Lemma: Let be the zero–one matrix that has a in its th position if and only if there is a path from to with interior vertices from the set . Then whenever and are positive integers not exceeding .

• Algorithm: Warshall Algorithm. procedure ( zero–one matrix) for to for to for to return is

Equivalence Relations

In this section we will study relations with a particular combination of properties that allows them to be used to relate objects that are similar in some way.

• Definition: A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.

• Definition: Two elements and that are related by an equivalence relation are called equivalent. The notation is often used to denote that and are equivalent elements with respect to a particular equivalence relation.

Equivalence Classes

Let be the set of all students in your school who graduated from high school. Consider the relation on that consists of all pairs where and graduated from the same high school. Given a student we can form the set of all students equivalent to with respect to . This set consists of all students who graduated from the same high school as did. This subset of is called an equivalence class of the relation.

• Definition: Let be an equivalence relation on a set . The set of all elements that are related to an element a of is called the equivalence class of . The equivalence class of with respect to is denoted by . When only one relation is under consideration, we can delete the subscript and write for this equivalence class.

In other words, if is an equivalence relation on a set the equivalence class of the element is . If then b is called a representative of this equivalence class.

Equivalence Classes and Partitions

Let be a relation on the set . Theorem below shows that the equivalence classes of two elements of are either identical or disjoint.

• Theorem: Let be an equivalence relation on a set . These statements for elements and of are equivalent:

  • .
  • .
  • .

• Theorem: Let be an equivalence relation on a set . Then the equivalence classes of form a partition of . Conversely, given a partition of the set there is an equivalence relation that has the sets as its equivalence classes.

Partial Orderings

We often use relations to order some or all of the elements of sets. For instance, we order words using the relation containing pairs of words where comes before in the dictionary. When we add all of the pairs of the form to these relations, we obtain a relation that is reflexive, antisymmetric, and transitive. These are properties that characterize relations used to order the elements of sets.

• Definition: A relation on a set is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set together with a partial ordering is called a partially ordered set, or poset, and is denoted by . Members of are called elements of the poset.

In different posets different symbols such as and are used for a partial ordering. However, we need a symbol that we can use when we discuss the ordering relation in an arbitrary poset. Customarily, the notation is used to denote that in an arbitrary poset . This notation is used because the less than or equal to relation on the set of real numbers is the most familiar example of a partial ordering and the symbol is similar to the symbol.

The notation denotes that but . Also, we say ” is less than ” or ” is greater than ” if . When and are elements of the poset it is not necessary that either or .

• Definition: The elements and of a poset are called comparable if either or . When and are elements of such that neither nor and are called incomparable.

The adjective “partial” is used to describe partial orderings because pairs of elements may be incomparable. When every two elements in the set are comparable, the relation is called a total ordering.

• Definition: If is a poset and every two elements of are comparable, is called a totally ordered or linearly ordered set, and is called a total order or a linear order. A totally ordered set is also called a chain.

• Definition: is a well-ordered set if it is a poset such that is a total ordering and every nonempty subset of has a least element.

Here is the important theorem that we should prove.

• Theorem: The Principle of Well-Ordered Induction Suppose that is a well-ordered set. Then is true for all if Inductive Step: For every if is true for all with then is true.

  Proof: Suppose it is not the case that is true for all . Then there is an element such that is false. Consequently, the set is false is nonempty. Because is well-ordered, has a least element . By the choice of as a least element of we know that is true for all with . This implies by the inductive step is true. This contradiction shows that must be true for all .

Maximal and Minimal Elements

In general, we can represent a finite poset using this procedure:

• Start with the directed graph for this relation. Because a partial ordering is reflexive, a loop is present at every vertex . Remove these loops.
• Next, remove all edges that must be in the partial ordering because of the presence of other edges and transitivity. That is, remove all edges for which there is an element such that and .
• Finally, arrange each edge so that its initial vertex is below its terminal vertex. Remove all the arrows on the directed edges, because all edges point “upward” toward their terminal vertex.

These steps are well defined, and only a finite number of steps need to be carried out for a finite poset. The resulting diagram is called the Hasse diagram of .

Let be a poset. We say that an element covers an element if and there is no element such that . The set of pairs such that covers is called the covering relation of .

From the description of the Hasse diagram of a poset, we see that the edges in the Hasse diagram of are upwardly pointing edges corresponding to the pairs in the covering relation of . Furthermore, we can recover a poset from its covering relation, because it is the reflexive transitive closure of its covering relation. This tells us that we can construct a partial ordering from its Hasse diagram.

Elements of posets that have certain extremal properties are important for many applications. An element of a poset is called maximal if it is not less than any element of the poset. That is, is maximal (greatest element) in the poset if there is no such that . Similarly, an element of a poset is called minimal if it is not greater than any element of the poset. That is, is minimal (least element) if there is no element such that .

Maximal and minimal elements are easy to spot using a Hasse diagram. They are the “top” and “bottom” elements in the diagram.

Sometimes it is possible to find an element that is greater than or equal to all the elements in a subset of a poset . If is an element of such that for all elements then is called an upper bound of . Likewise, there may be an element less than or equal to all the elements in . If is an element of such that for all elements then is called a lower bound of .

The element is called the least upper bound of the subset if is an upper bound that is less than every other upper bound of . That is, is the least upper bound of if whenever and whenever is an upper bound of . Similarly, the element is called the greatest lower bound of if is a lower bound of and whenever is a lower bound of . The greatest lower bound and least upper bound of a subset are denoted by and respectively.

Lattices

A partially ordered set in which every pair of elements has both a least upper bound and a greatest lower bound is called a lattice. Lattices have many special properties. Furthermore, lattices are used in many different applications such as models of information flow and play an important role in Boolean algebra.

Topological Sorting: Suppose that a project is made up of 20 different tasks. Some tasks can be completed only after others have been finished. How can an order be found for these tasks? To model this problem we set up a partial order on the set of tasks so that if and only if and are tasks where cannot be started until has been completed. To produce a schedule for the project, we need to produce an order for all tasks that is compatible with this partial order.

We begin with a definition. A total ordering is said to be compatible with the partial ordering if a whenever . Constructing a compatible total ordering from a partial ordering is called topological sorting.

• Lemma: Every finite nonempty poset has at least one minimal element.

We will use this lemma to form an algorithm for this task.

• Algorithm: Topological Sorting. procedure (: finite poset) while minimal element of such an element exists by Lemma return is a compatible total ordering of