Pedagogical Derivation of All Irredundant Dependency Sets for Relational Databases

Abstract

Abstract. This paper introduces a pedagogical method for the derivation of all irredundant dependency sets (IDSs) (and a minimal cover (MC) of the dependency set for relational databases. The paper utilizes an established equivalence between relational database functional dependencies (FDs) and a fragment of switching algebra that is typically built of Horn clauses. Therefore, the paper proposes the employment of various tools of switching theory in the domain of relational databases. In particular, the paper obtains the IDSs and MC of a database dependency set by employing a Variable-Entered Cover Table (VECT) to construct a presence or Petrick Function (PF). The proposed procedure is presented in detail and demonstrated via two illustrative examples. The traditional database approach, adopted by almost all textbooks on relational databases and based on the heuristic application of inference axioms, does not decide whether there is a unique IDS or multiple ones, and does not produce multiple IDSs when these exist. The present procedure, however, produces all (or, at least, as many as required) IDSs, and decides which among them are minimal covers. The present procedure is validated via Karnaugh maps and directed graphs. The paper demonstrates that the current covering problem is of exponential complexity and hence intractable. However, this complexity issue is not of much concern for the current pedagogical application to relational databases.