In this paper, dense families of relation schemes are introduced. We characterize minimal keys of relation schemes in terms of dense families. Note that, the dense families of database relations were introduced by Jarvinen [6]. We prove that the set of all minimal keys of a relation scheme s= (U, F) is the transversal hypergraphs of a hypergraph D– {?}, where Dis any s-dense family. We give a necessary and sufficient condition for an abitrary family to be s-dense family. We also present some dense families of relation schemes. Furthermore, in this paper, we also study antikeys by means of dense families. We present connections between antikeys and a dense family of relation schemes. Finally, we study the time complexity of the problem finding antikeys.




Armstrong, W.W. (1974), Dependency structure of database relationship, Information Processing 74, North-Holland Pub. Co., pp. 580-583.

Berge, C. (1989), Hypergraphs: combinatorics of finite sets, North - Holland, Amsterdam.

Demetrovis, J. (1979), On the equivalence of candidate keys with Sperner systems, Acta Cybernetica vol 4, pp. 247-252.

Demetrovics, J. and Thi, V.D. (1987), Keys, antikeys and prime attributes, Annales Univ. Sci. Budapest Sect. Comp., vol 8, pp. 35-52.

Demetrovics, J. and Thi, V.D. (1999), Describing candidate keys by hypergraphs, Computers and Artificial Intelligence, vol 18, pp. 191-207.

Jarvinen, J. (2001), Dense families and key functions of databaserelation instances, In: Freivalds R. (Ed.), Fundamentals of Computation Theory, Proceedings of the 13th International Symposium, Lecture Notes in Computer Science 2138, Springer-Verlag, Heidelberg, pp. 184-192.

Thi, V.D. (1986), Minimal keys and antikeys, Acta Cybernetica, vol 7, pp.61-371.

Thi, V.D. and Son, N.H. (2004), Some problems related to keys and the Boyce-Codd normal form, Acta Cybernetica, vol 16, pp. 473-483.


Download data is not yet available.