THE INDEPENDENCE OF THE AXIOMATIC SYSTEM OF MULTIVALUED DEPENDENCIES IN RELATION (TABLE) DATABASES

Authors

  • A. V. Puzikova Volodymyr Vynnychenko Central Ukrainian State Pedagogical University, Kropyvnytskyi, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2020-1-8

Keywords:

Relation databases, multivalued dependencies, axiomatisation of multivalued dependencies, independence of the axiomatic system of multivalued dependencies.

Abstract

Context. The complexity of understanding the concept of multivalued dependencies (when setting out their theoretical foundations, an axiomatic approach is used) in relational (table) databases leads to problems of their modeling, which in turn can cause a violation of data integrity. A partial solution to these issues is facilitated by the search for equivalent axiomatic systems of multivalued dependencies that are minimal in terms of the number and power of their components. This, in turn, requires establishing the equivalence of these axiomatic systems and proving the independence of their elements. 

The object of the study is the axiomatisations of multivalued dependencies.The purpose of the work is to establish the equivalence of two axiomatic systems of multivalued dependencies, one of which is minimal in terms of the number and power of components, and to prove the independence of specified axiomatics. 

Method. Set-theoretic and logical-algebraic methods are used in the construction of proofs. The equivalence of two axiomatic systems of multivalued dependencies is established classically: the relation of syntactic inference is considered and sequences of multivalued dependencies are constructed that are proofs of the rules of each axiomatics from the components of the other. To build proof of independence of the axiomatic system, models of relational schemes are proposed, such that for an axiom or rule whose independence is being proved, it is impossible to construct proof from set of other axioms or rules.

Results. Equivalence of the axiomatisation of multivalued dependencies proposed by a group of scientists Beeri, Fagin and Howard and the Biskup’s axiomatisation of multivalued dependencies has been established. The independence of the Biskup’s axiomatic system is proved in the sense that without loss of completeness it is impossible to remove neither the only axiom nor none of the inference rules.

Conclusions. The independence of the Biskup’s axiomatisation of multivalued dependencies, which has no more in number and power of components than other axiomatic systems of multivalued dependencies, is proved. Using such axiomatic system has advantages in the development of CASE-tools (Computer-Aided Software Engineering Tools), which include the implementation of reducing the relational database schema to the fourth normal form, and also, when manually designing a logical model of a relational database. 

Author Biography

A. V. Puzikova, Volodymyr Vynnychenko Central Ukrainian State Pedagogical University, Kropyvnytskyi

PhD, Senior lecturer of the department of computer science and information technology

References

Fagin R. Multivalued Dependencies and a New Normal Form for Relational Databases, ACM Transactions on Database Systems, 1977, Vol. 2, No. 1, pp. 262–278. DOI: 10.1145/320557.320571

Moody D. Dealing with complexity: a practical method for representing large entity-relationship models, Ph.D. Thesis, Department of Information Systems, University of Melbourne, 2001.

Hartmann S., Link S. On a problem of Fagin concerning multivalued dependencies in relational databases, Theoretical Computer Science, 2006, Vol. 353, pp. 53–62. DOI:10.1016/j.tcs.2005.08.036

Ferrarotti F., Hartmann S., Link S. On the Role of the Complementation Rule for Data Dependencies over Incomplete Relations, Logic, Language, Information and Computation. Lecture Notes in Computer Science. Springer-Verlag Berlin Heidelberg, 2010, Vol. 6188, pp. 136–147. DOI: 10.1007/978-3-642-13824-9_12

Red’ko V. N., Bui D. B., Puzikova A. V. Aksiomatyka bagatoznachnyh zalezhnostej tablychnyh baz danyh, Dopovidi NAN Ukrai’ny, 2015, No. 6, pp. 24–29.

Bui D., Puzikova A. Axiomatics for Multivalued Dependencies in Table Databases: Correctness, Completeness, Completeness Criteria, Theory and Engineering of Complex Systems and Dependability. Series “Advances in Intelligent Systems and Computing”. Springer International Publishing Switzerland, 2015, Vol. 365, pp. 45–55. DOI: 10.1007/978-3-319-19216-1_5

Red’ko V. N., Brona Ju. J., Bui D. B., Poljakov S. A. Reljacijni bazy danyh: tablychni algebry ta SQL-podibni movy. Kyi’v, “Akademperiodyka”, 2001, 198 p.

Beeri C., Fagin R., Howard J. A complete axiomatization for functional and multivalued dependencies, Proceedings of the ACM-SIGMOD Conf. (Toronto, Canada, Aug. 3–5, 1977). ACM: New York, 1977, pp. 47–61. DOI: 10.1145/509404.509414

Biskup J. On the complementation rule for multivalued dependencies in database relations, Acta Informatica, 1978, Vol. 10, No. 3, pp. 297–305. DOI: 10.1007/BF00264322

Zaniolo C. Analysis and design of relational schemata for database systems: Ph.D. dissertation, Tech. Rep. UCLAEng-7769, Dep. Computer Science, Univ. California at Los Angeles, July 1976.

Mendelzon A. O. On axiomatizing multivalued dependencies in relational databases, ACM Transactions on Database Systems, 1979, Vol. 26, No. 1, pp. 37–44. DOI: 10.1007/BF00264322

Lindon R. Zametki po logike. Moscow, Mir, 1968, 128 p.

Sentilles D. A Bridge to Advanced Mathematics. Dover Publications, 2011, 387 p.

Connolly T., Begg C. Database systems. A practical approach to design, implementation and management. Addison-Wesley, 2004, 1424 p.

Bui D. B., Puzikova A. V. Nezalezhnist Aksiomatyky Armstronha ta Alhebra Funktsionalnykh Zalezhnostei, Shtuchnyi Intelekt, 2015, No. 1–2, pp. 121–126.

How to Cite

Puzikova, A. V. (2020). THE INDEPENDENCE OF THE AXIOMATIC SYSTEM OF MULTIVALUED DEPENDENCIES IN RELATION (TABLE) DATABASES. Radio Electronics, Computer Science, Control, (1), 75–81. https://doi.org/10.15588/1607-3274-2020-1-8

Issue

Section

Mathematical and computer modelling