maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2020-3-356-365mais-1354Research ArticleDiscrete Mathematics in Relation to Computer ScienceОбобщение правил вывода для зависимостей соединения в базах данныхA Generalization of the Inference Rules for Join Dependencies in Databaseshttps://orcid.org/0000-0002-0576-2149ЗыкинСергей ВладимировичZykinSergey V.

Ведущий научный сотрудник, доктор технических наук.

Пр. ак. Коптюга, 4, Новосибирск, 630090

Leading researcher, Doctor of Science.

4 Acad. Koptyug avenue, Novosibirsk, 630090

szykin@mail.ruИнститут математики им. С.Л. Соболева, СО РАНРоссияSobolev Institute of Mathematics, SB RASRussian Federation202020092020273356365Copyright © Зыкин С.В., 20202020Зыкин С.В.Zykin S.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1354

В работе рассматривается обобщение правил вывода зависимостей соединения, которые используются при проектировании схемы базы данных, удовлетворяющей требованиям пятой нормальной формы. В предшествующих работах, посвященных данной проблематике, делаются попытки построить системы аксиом таких зависимостей, основанных на правилах вывода. Однако, если обоснование непротиворечивости (надежности) полученных аксиом не вызывает затруднений, то доказательство полноты в общем случае не получило удовлетворительного решения. Прежде всего, это связано с ограниченностью самих правил вывода. В данной работе акцентировано внимание на двух оригинальных системах аксиом, представленных в работах Sciore и Malvestuto. Для зависимостей включения получена система правил, которая обобщает существующие системы и при этом имеет меньше ограничений. В работе представлено доказательство выводимости известных систем аксиом из представленных правил вывода. Кроме того, приводится доказательство непротиворечивости (надежности) этих правил. Вопрос о полноте формальной системы, основанной на представленных правилах, не нашел положительного решения. В заключение отмечена теоретическая и практическая значимость правил вывода для зависимостей соединения.

In this paper a generalisation of the inference rules of the join dependencies that are used in the design of database schemas that meets the requirements of the fifth normal form is considered. In the previous works devoted to this problem, attempts to construct systems of the axioms of such dependencies based on inference rules are made. However, while the justification for the consistency (soundness) of the obtained axioms does not cause difficulties, the proof of completeness in general has not been satisfactorily resolved. First of all, this is due to the limitations of the inference rules themselves. This work focuses on two original axiom systems presented in the works of Sciore and Malvestuto. For the inclusion dependencies a system of rules that generalises existing systems and has fewer restrictions has been obtained. The paper presents a proof of the derivability of known systems of axioms from the presented inference rules. In addition, evidence of the consistency (soundness) of these rules is provided. The question of the completeness of the formal system based on the presented rules did not find a positive solution. In conclusion, the theoretical and practical significance of the inference rules for the join dependencies is noted.

реляционные базы данныхзависимости соединенияправила выводаrelational databasesjoin dependenciesinference rulesРабота выполнена при поддержке программы фундаментальных научных исследований СО РАН № I.5.1., проект № 0314-2019-0020The work was supported by the program of fundamental scientific researches of the SB RAS № I.5.I., project № 03142019-0020ReferencesJ. Ullman, Principles of Database Systems. Stanford University: Computer Science Press, 1980.J. Ullman, Principles of Database Systems. Stanford University: Computer Science Press, 1980.D. Maier, The Theory of Relational Databases. Rockville: Computer Science Press, 1983.D. Maier, The Theory of Relational Databases. Rockville: Computer Science Press, 1983.S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases: The Logical Level. Addison-Wesley, 1994.S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases: The Logical Level. Addison-Wesley, 1994.M. Casanova, R. Fagin, and C. Papadimitriou, "Inclusion dependencies and their interaction with functional dependencies”, J. Comput. Syst. Sci., vol. 28, no. 1, pp. 29-59, 1984. doi: 10.1016/0022-0000(84)90075-8.M. Casanova, R. Fagin, and C. Papadimitriou, "Inclusion dependencies and their interaction with functional dependencies”, J. Comput. Syst. Sci., vol. 28, no. 1, pp. 29-59, 1984. doi: 10.1016/0022-0000(84)90075-8.M. Levene and M. Vincent, "Justification for inclusion dependency normal form”, IEEE Trans. Knowl. Data Eng., vol. 12, no. 2, pp. 281-291, 2000. doi: 10.1109/69.842267.M. Levene and M. Vincent, "Justification for inclusion dependency normal form”, IEEE Trans. Knowl. Data Eng., vol. 12, no. 2, pp. 281-291, 2000. doi: 10.1109/69.842267.H. Kohler and S. Link, "Inclusion dependencies reloaded”, in The 24th ACM International on Conference on Information and Knowledge Management (CIKM ’15), 2015, pp. 1361-1370. doi: 10.1145/2806416.2806539.H. Kohler and S. Link, "Inclusion dependencies reloaded”, in The 24th ACM International on Conference on Information and Knowledge Management (CIKM ’15), 2015, pp. 1361-1370. doi: 10.1145/2806416.2806539.V. Zykin and S. Zykin, "Analysis of Typed Inclusion Dependences with Null Values”, Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 638-646, 2018. doi: 10.3103/S0146411618070258.V. Zykin and S. Zykin, "Analysis of Typed Inclusion Dependences with Null Values”, Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 638-646, 2018. doi: 10.3103/S0146411618070258.J. Rissanen, "Theory of relations for databases - a tutorial survey”, in Mathematical Foundations of Computer Science 1978, J. Winkowski, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 1978, pp. 536-551.J. Rissanen, "Theory of relations for databases - a tutorial survey”, in Mathematical Foundations of Computer Science 1978, J. Winkowski, Ed., Berlin, Heidelberg: Springer Berlin Heidelberg, 1978, pp. 536-551.E. Sciore, "A Complete Axiomatization of Full Join Dependencies”, J. ACM, vol. 29, no. 2, pp. 373-393, 1982. doi: 10.1145/322307.322313.E. Sciore, "A Complete Axiomatization of Full Join Dependencies”, J. ACM, vol. 29, no. 2, pp. 373-393, 1982. doi: 10.1145/322307.322313.C. Beeri and M. Vardi, "Formal systems for join dependencies”, Theoretical Computer Science, vol. 38, pp. 99-116, 1985. doi: 10.1016/0304-3975(85)90212-9.C. Beeri and M. Vardi, "Formal systems for join dependencies”, Theoretical Computer Science, vol. 38, pp. 99-116, 1985. doi: 10.1016/0304-3975(85)90212-9.M. Gyssens, "On the complexity of join dependencies”, ACM Transactions on Database Systems, vol. 11, no. 1, pp. 81-108, 1986. doi: 10.1145/5236.5237.M. Gyssens, "On the complexity of join dependencies”, ACM Transactions on Database Systems, vol. 11, no. 1, pp. 81-108, 1986. doi: 10.1145/5236.5237.F. Malvestuto, "A Complete Axiomatization of Full Acyclic Join Dependencies”, Inf. Process. Lett., vol. 68, no. 3, pp. 133-139, 1998.F. Malvestuto, "A Complete Axiomatization of Full Acyclic Join Dependencies”, Inf. Process. Lett., vol. 68, no. 3, pp. 133-139, 1998.I. Duntsch and S. Mikulas, "Cylindric structures and dependencies in relational databases”, Theoretical Computer Science, vol. 269, pp. 451-468, 2001. doi: 10.1016/S0304-3975(01)00016-0.I. Duntsch and S. Mikulas, "Cylindric structures and dependencies in relational databases”, Theoretical Computer Science, vol. 269, pp. 451-468, 2001. doi: 10.1016/S0304-3975(01)00016-0.S. Hartmann, H. Kohler, and S. Link, "Full hierarchical dependencies in fixed and undetermined universes”, Annals of Mathematics and Artificial Intelligence, vol. 50, pp. 195-226, 2007. doi: 10.1007/s10472-007-9067-0.S. Hartmann, H. Kohler, and S. Link, "Full hierarchical dependencies in fixed and undetermined universes”, Annals of Mathematics and Artificial Intelligence, vol. 50, pp. 195-226, 2007. doi: 10.1007/s10472-007-9067-0.J. Biskup and S. Link, "Appropriate inferences of data dependencies in relational databases”, Annals of Mathematics and Artificial Intelligence, vol. 63, no. 3-4, pp. 213-255, 2011.J. Biskup and S. Link, "Appropriate inferences of data dependencies in relational databases”, Annals of Mathematics and Artificial Intelligence, vol. 63, no. 3-4, pp. 213-255, 2011.M. Hannula and J. Kontinen, "A finite axiomatization of conditional independence and inclusion dependencies”, Information and Computation, vol. 249, pp. 121-137, 2016. doi: 10.1016/j.ic.2016.04.001.M. Hannula and J. Kontinen, "A finite axiomatization of conditional independence and inclusion dependencies”, Information and Computation, vol. 249, pp. 121-137, 2016. doi: 10.1016/j.ic.2016.04.001.J. Baixeries, "A Formal Context for Acyclic Join Dependencies”, Lecture Notes in Computer Science, vol. 10352, pp. 563-572, 2017. doi: 10.1007/978-3-319-60438-1-55.J. Baixeries, "A Formal Context for Acyclic Join Dependencies”, Lecture Notes in Computer Science, vol. 10352, pp. 563-572, 2017. doi: 10.1007/978-3-319-60438-1-55.S. Zykin, "Domains of functional dependences in databases”, Trudy Inst. Mat. i Mekh. UrO RAN, vol. 22, no. 3, pp. 117-129, 2016.S. Zykin, "Domains of functional dependences in databases”, Trudy Inst. Mat. i Mekh. UrO RAN, vol. 22, no. 3, pp. 117-129, 2016.

The authors declare that there are no conflicts of interest present.