Abstract
Certain sentences about relations are of special practical and theoretical interest for relational databases. For historical reasons, such sentences are usually called dependencies. The first dependency introduced and studied was the functional dependency, or FD, due to Codd [Co]. As an example, consider the relation in Figure 1.1, with three columns: EMP (which represents employees), DEPT (which represents departments), and MGR (which represents managers). The relation in Figure 1.1 obeys the FD "DEPT-MGR", which is read "DEPT determines MGR". This means that whenever two tuples (that is, rows) agree in the DEPT column, then they necessarily agree also in the MGR column. The relation in Figure 1.2 does not obey this FD, since, for example, the first and fourth tuples agree in the DEPT column but not in the MGR column. FDs (and some of the other dependencies we will discuss) are of interest in database normalization. For example, assume that the database obeys the FD DEPT-MGR as a constraint (that is, that it is decreed to be always the case that two employees in the same department necessarily have the same manager). Then it might be better to store the data not in one relation, as in Figure 1.1, but rather in two relations, as in Figure 1.3: one relation that relates employees to departments, and one relation that relates departments to managers. For more information, see Codd [Co] or Fagin [Fa2].