Some Observations on the Minimal Armstrong Relations for Normalised Relation Schemes

Abstract

For functional dependency second normal form (2NF), third normal form (3NF) and Boyse-Codd normal form (BCNF) which were introduced by E.F. Codd have been widely investigated both theoretically and practically. It is known [6] that a set of minimal keys of a relation scheme is a Sperner system (sometimes it is called an antichain) and for an arbitrary Sperner system there exists a relation scheme the set of minimal keys of which is exactly this Sperner system. This paper gives new necessary and sufficient conditions for an arbitrary relation scheme is in 2NF, 3NF, BCNF and its set of minimal keys is a given Sperner system. Based on these characterizations we present some new estimations for the size of minimal Armstrong relations for 3NF and BCNF relation schemes. We show that given a Sperner system K and BCNF relation scheme s a set of minimal keys of which is K, the number of antikeys (maximal nonkeys) of K is polynomial in the number of attributes iff so is the size of minimal Armstrong relation of s.