328
Relations, Functions, and Matrices
Your company has developed a program for use on a small parallel processing
machine. According to the technical documentation, the program executes processes
P1, P2, and P3 in parallel; these processes all need results from process P4, so they
must wait for Process P4 to complete execution before they begin. Processes P7 and
P10 execute in parallel but must wait until processes P1, P2, and P3 have finished.
Process P4 requires results from P5 and P6 before it can begin execution. P5 and
P6 execute in parallel. Processes P8 and P11 execute in parallel, but P8 must wait
for Process P7 to complete and P11 must wait for process P10 to complete. Process
P9 must wait for results from P8 and P11. You have been assigned to convert the
software for use on a single processor machine.
Question: In what order should the processes be executed?
Here various pairs of processes are related to one another by a “prerequisite”
relation. This is a special case of a binary relation, a relationship between pairs of
elements within a set. We will study the various properties of binary relations in
Section 5.1. One type of binary relation is called a partial ordering; elements related by a partial ordering can be represented graphically. Another type of binary
relation is an equivalence relation; elements related by an equivalence relation can
be grouped into classes.
A topological sort extends a partial ordering to a total ordering. For a partial ordering of prerequisite tasks, a corresponding total ordering identifies the
sequential order in which the tasks would have to be done, which is the solution
to the parallel processing conversion problem. Topological sorting is presented in
Section 5.2.
A generalization of a binary relation forms the basis for relational databases,
considered in Section 5.3. Using operations of restrict, project, and join on the
relations in a database, we can make various queries of the database.
A function is a special kind of binary relation. Functions, as well as relations,
describe a number of real-world situations. Functions can also have special properties, as discussed in Section 5.4. Order of magnitude, presented in Section 5.5,
provides a way to compare the growth rate of two functions and is useful in the
analysis of algorithms. A simple function called the modulo function has a surprising number of applications, ranging from encryption algorithms for computer
security to the basis for artistic design patterns. Some of these applications are
mentioned in Section 5.6.
In Section 5.7, we consider matrices and develop an arithmetic for manipulating them. Matrices provide a mechanism for solving systems of linear equations.
We will later use matrices to represent relations and graphs.
S e c t I o n 5 . 1 Rel ations
Binary Relations
If we learn that two people, Henrietta and Horace, are related, we understand that
there is some family connection between them—that (Henrietta, Horace) stands
out from other ordered pairs of people because there is a relationship (cousins, sister and brother, or whatever) that Henrietta and Horace satisfy. The mathematical
Relations, Functions, and Matrices
Your company has developed a program for use on a small parallel processing
machine. According to the technical documentation, the program executes processes
P1, P2, and P3 in parallel; these processes all need results from process P4, so they
must wait for Process P4 to complete execution before they begin. Processes P7 and
P10 execute in parallel but must wait until processes P1, P2, and P3 have finished.
Process P4 requires results from P5 and P6 before it can begin execution. P5 and
P6 execute in parallel. Processes P8 and P11 execute in parallel, but P8 must wait
for Process P7 to complete and P11 must wait for process P10 to complete. Process
P9 must wait for results from P8 and P11. You have been assigned to convert the
software for use on a single processor machine.
Question: In what order should the processes be executed?
Here various pairs of processes are related to one another by a “prerequisite”
relation. This is a special case of a binary relation, a relationship between pairs of
elements within a set. We will study the various properties of binary relations in
Section 5.1. One type of binary relation is called a partial ordering; elements related by a partial ordering can be represented graphically. Another type of binary
relation is an equivalence relation; elements related by an equivalence relation can
be grouped into classes.
A topological sort extends a partial ordering to a total ordering. For a partial ordering of prerequisite tasks, a corresponding total ordering identifies the
sequential order in which the tasks would have to be done, which is the solution
to the parallel processing conversion problem. Topological sorting is presented in
Section 5.2.
A generalization of a binary relation forms the basis for relational databases,
considered in Section 5.3. Using operations of restrict, project, and join on the
relations in a database, we can make various queries of the database.
A function is a special kind of binary relation. Functions, as well as relations,
describe a number of real-world situations. Functions can also have special properties, as discussed in Section 5.4. Order of magnitude, presented in Section 5.5,
provides a way to compare the growth rate of two functions and is useful in the
analysis of algorithms. A simple function called the modulo function has a surprising number of applications, ranging from encryption algorithms for computer
security to the basis for artistic design patterns. Some of these applications are
mentioned in Section 5.6.
In Section 5.7, we consider matrices and develop an arithmetic for manipulating them. Matrices provide a mechanism for solving systems of linear equations.
We will later use matrices to represent relations and graphs.
S e c t I o n 5 . 1 Rel ations
Binary Relations
If we learn that two people, Henrietta and Horace, are related, we understand that
there is some family connection between them—that (Henrietta, Horace) stands
out from other ordered pairs of people because there is a relationship (cousins, sister and brother, or whatever) that Henrietta and Horace satisfy. The mathematical