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

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

A. V. Puzikova

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. 


Keywords


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

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.


GOST Style Citations


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

2. 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.

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

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

5. Редько В. Н. Аксіоматика багатозначних залежностей табличних баз даних / В. Н. Редько, Д. Б. Буй, А. В. Пузікова // Доповіді НАН України. – 2015. – № 6. – С. 24–29.

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

7. Реляційні бази даних: табличні алгебри та SQL-подібні мови / В. Н. Редько, Ю. Й. Брона, Д. Б. Буй, С. А. Поляков. – Київ : «Академперіодика», 2001. – 198 с.

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

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

10. 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.

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

12. Линдон Р. Заметки по логике / Р. Линдон. – М. : Мир, 1968. – 128 с.

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

14. Коннолли Т. Базы данных: проектирование, реализация и сопровождение. Теория и практика / Т. Коннолли, К. Бегг. – М. : «Вильямс», 2017. – 1440 с.

15. Буй Д. Б. Незалежність аксіоматики Армстронга та алгебра функціональних залежностей / Д. Б. Буй, А. В. Пузікова // Штучний інтелект. – 2015. – № 1–2. – С. 121–126.







Copyright (c) 2020 А. В. Пузікова

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

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.