Links

Tools

Export citation

Search in Google Scholar

Pedagogical Derivation of All Irredundant Dependency Sets for Relational Databases

Journal article published in 2016 by Ali Muhammad Ali Rushdi, Omar Mohammed Ba-Rukab
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

Abstract

This paper introduces a pedagogical method for the derivation of all irredundant dependencysets (IDSs) (and a minimal cover (MC) of the dependency set for relational databases. The paper utilizesan established equivalence between relational database functional dependencies (FDs) and a fragment ofswitching algebra that is typically built of Horn clauses. Therefore, the paper proposes the employmentof various tools of switching theory in the domain of relational databases. In particular, the paper obtainsthe IDSs and MC of a database dependency set by employing a Variable-Entered Cover Table (VECT) toconstruct a presence or Petrick Function (PF). The proposed procedure is presented in detail anddemonstrated via two illustrative examples. The traditional database approach, adopted by almost alltextbooks on relational databases and based on the heuristic application of inference axioms, does notdecide whether there is a unique IDS or multiple ones, and does not produce multiple IDSs when theseexist. The present procedure, however, produces all (or, at least, as many as required) IDSs, and decideswhich among them are minimal covers. The present procedure is validated via Karnaugh maps anddirected graphs. The paper demonstrates that the current covering problem is of exponential complexityand hence intractable. However, this complexity issue is not of much concern for the current pedagogicalapplication to relational databases.Keywords. Switching Algebra, Relational Databases, Irredundant Dependency Set, IrredundantDisjunctive Form, Variable-Entered Cover Table, Functional Dependency, Minimal Cover.