Map derivation of the closures for dependency and attribute sets and all candidate keys for a relational database

Abstract EN

There is an established equivalence between relational database functional dependencies (FDs) and a fragment of switching algebra that is typically built of Horn clauses.

This equivalence pertains to both concepts and procedures of the FD database domain and the switching-algebraic domain.

In particular, three notable problems of database analysis and design, namely, the derivation of the closure for any dependency set, the derivation of the closure for any subset of the set of attributes, and the derivation of all candidate keys, can be identified as a computation of the complete sum (disjunction of all prime implicants) of a switching function.

This paper tackles each of these three problems as a complete-sum derivation problem via a powerful manual algorithm employing the variable-entered Karnaugh map.

This map has a pictorial (albeit semialgebraic) nature, and it doubles the variable-handling capacity of the conventional Karnaugh map.

The algorithm is presented in detail and demonstrated via relatively-large illustrative examples.

The merits of this algorithm was discussed in comparison with the traditional approach based on the iterative application of rules of inference.

As an offshoot, the paper also includes enhancements of the traditional approach via ideas borrowed from switching algebra.