ON THE DENSE FAMILIES IN THE RELATIONAL DATAMODEL

Abstract

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.

 

https://doi.org/10.29037/ajstd.162
PDF

References

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.

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Copyright (c) 2017 Vu Duc Thy, Nguyen Hoang Son

Downloads

Download data is not yet available.