THE INDEPENDENCE OF THE AXIOMATIC SYSTEM OF MULTIVALUED DEPENDENCIES IN RELATION (TABLE) DATABASES
DOI:
https://doi.org/10.15588/1607-3274-2020-1-8Keywords:
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.
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.
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2020 А. В. Пузікова
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
