4 - Relations

Summary

Introduction

This chapter will introduce a far-reaching generalization of the concept of a function. Its definition will reflect the fact that it could be implemented on a computer by a list with two columns, one column with entries from one set, and the other column with entries from a second set. This is a simple example of a relational database.

The idea of a cartesian product of two sets introduced in Chapter 3 is a very powerful one, and will enable us to considerably extend the range of applications we can model.

Example 4.1 In a Modula-2 program, several procedures Proc_1, Proc_2, Proc_3, …, are defined. In the definition of Proc_1, there are calls to both Proc_2 and Proc_1 itself. In Proc_2, there are calls to Proc_1 and Proc_3. In Proc_3, there are calls to Proc_2, and Proc_5, and so on. It is required to find the exact dependency of each procedure on any others, both directly and indirectly.

If we can tabulate the direct dependencies, then we can find all of the indirect ones too, by chasing through chains of direct calls. To find the effect of a call of any procedure, we merely need to create a list or database of pairs of procedure names, listing (Proc_i, Proc_j) whenever Proc_i calls Proc_j. The list is as in Figure 4.1.