SOME RESULTS ABOUT NORMAL FORMS FOR FUNCTIONAL DEPENDENCY IN THE RELATIONAL DATAMODEL

In this paper we present some characterizations of relation schemes in second normal form (2NF), third normal form (3NF) and Boyce-Codd norm al form (BCNF). It is known [6] that the set of minimal keys of a rela tion scheme is a Sperner system (an antichain) and for an arbitrary Sp erner system there exists a relation scheme the set of minimal keys of which is exactly the given Sperner system. We investigate families of 2NF, 3NF and BCNF relation schemes where the sets of minimal keys are given Sperner systems. We give characterizations of these families. T he minimal Armstrong relation has been investigated in the literature [3, 7, 11, 15, 18]. This paper gives new bounds on the size of minimal Armstrong relations for relation schemes. We show that given a relati on scheme s such that the set of minimal keys is the Sperner system K, the number of antikeys (maximal nonkeys) of K is polynomial in the nu mber of attributes iff so is the size of minimal Armstrong relation of s. We give a new characterization of relations and relation schemes t hat are uniquely determined by their minimal keys. From this character ization we give a polynomial-time algorithm deciding whether an arbitr ary relation is uniquely determined by its set of all minimal keys. We present a new polynomial-time algorithm testing BCNF property of a gi ven relation scheme.