Authors: Catriel BEERI, Philip A. Bernstein
Tags: 1979, conceptual modeling
Problems related to functional dependencies and the algorithmic design of relational schemas are examined. Specifically, the following results are presented: (1) a tree model of derivations of functional dependencies from other functional dependencies; (2) a linear-time algorithm to test if a functional dependency is in the closure of a set of functional dependencies; (3) a quadratic-time implementation of Bernstein’s third normal form schema synthesis algorithm. Furthermore, it is shown that most interesting algorithmic questions about Boyce-Codd normal form and keys are NP-complete and are therefore probably not amenable to fast algorithmic solutions.Read the full paper here: https://dl.acm.org/doi/10.1145/320434.320436
