### Some computational problems related to normal forms

#### Abstract

We give a new characterization of the relations and the relation scheme that are uniquely determined by their minimal keys. It is known that these relations and the relation schemes are in the BCNF class. From this characterization we give a polynomial time algorithm deciding whether an arbitrary relation is uniquely determined by its set of all minimal keys. In the rest if this paper some new bounds of the size of minimal Armstrong relations for BCNF relation scheme are given. 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.

#### Full Text:

PDF (Tiếng Việt)DOI: https://doi.org/10.15625/1813-9663/13/1/7983

*Journal of Computer Science and Cybernetics *ISSN: 1813-9663**Published by Vietnam Academy of Science and Technology**