Functional Dependency

In the context of relational databases, a FunctionalDependency is a relationship between two sets of attributes in relation. The determinant is a set of attributes which, when their values are known, fully determine the values of the dependent set. In other words, given a relation, and given the values of a set of determinant attributes, you could look up tuples (rows) in the relation with matching determinant values, and they should all have the same set of values for the attributes of the dependent set. (You might find zero, one, or many matching tuples.)

A CandidateKey is a special case of a determinant which determines all attributes of a relation.

Although not part of the fundamental RelationalModel, functional dependencies are useful in query optimization and to help reason about database schema normalization.

Example: Given a version of the good 'ol Employee relation (EmployeeID, EmployeeName?, DepartmentName?), EmployeeID would typically be a CandidateKey. Thus we can say that this FunctionalDependency holds:

  [EmployeeID] -> [EmployeeID, EmployeeName?, DepartmentName?]

Assume further a Department relation (DepartmentName?, DirectorEmployeeID), with FD [DepartmentName?] -> [DepartmentName?, DirectorEmployeeID]. There are rules by which FDs can be derived for the results of queries. A very simple case is the natural join, which preserves all FDs. In SQL:

  SELECT * FROM Employeee NATURAL JOIN Department;

This yields a relation (in this case; SQL queries don't always produce relations) in which both FDs hold:

  [EmployeeID] -> [EmployeeID, EmployeeName?, DepartmentName?]
  [DepartmentName?] -> [DepartmentName?, DirectorEmployeeID]

Using rules developed by various researchers, e.g. HughDarwen, one can combine the members of such a family of FDs to derive new ones. In this case, for instance, we can also determine that this FD holds in the result relation:

  [EmployeeID, DepartmentName?] -> [EmployeeID, EmployeeName?, DepartmentName?, DirectoryEmployeeID]

This particular FD identifies a candidate key, [EmployeeID, DepartmentName?], because the dependent set includes all attributes of the relation. This illustrates (briefly, with some hand-waving) how FDs can be used to infer keys of derived relations.