maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2024-1-78-89mais-1839Research ArticleTheory of DataМинимальное покрытие обобщенных типизированных зависимостей включения в базах данныхMinimal coverage of generalized typed inclusion dependencies in databaseshttps://orcid.org/0000-0002-0576-2149ЗыкинСергей ВладимировичZykinSergey V.szykin@mail.ruИнститут математики им. С.Л. Соболева СО РАНРоссияSobolev institute of mathematics SB RASRussian Federation2024280320243117889Copyright © Зыкин С.В., 20242024Зыкин С.В.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/1839

В статье рассматривается теория и алгоритмы, необходимые для построения минимального покрытия обобщенных типизированных зависимостей включения. Традиционно аппарат построения минимальных покрытий используется для всех видов зависимостей с целью получения не избыточного и непротиворечивого проекта базы данных. Обобщенные зависимости включения соответствуют ссылочным ограничениям целостности, когда в одном ограничении участвуют несколько главных и несколько внешних отношений, что соответствует ребру ультраграфа. В предыдущей работе на основе исследования свойств зависимостей представлена система аксиом с доказательством непротиворечивости и полноты. В данной работе проведены исследования замыканий для обобщенных типизированных зависимостей включения. Разработан алгоритм построения замыканий, доказана его корректность. Полученные результаты далее используются для разработки алгоритма построения минимального покрытия. В конце статьи представлены примеры, которые демонстрируют работу алгоритмов.

The paper discusses the theory and algorithms necessary to construct a minimal covering of generalized typed inclusion dependencies. Traditionally, the construction of minimal covering is used for all types of dependencies in order to obtain a non-redundant and consistent database design. Generalized inclusion dependencies correspond to referential integrity constraints, when several main and several external relations are involved in one constraint, which corresponds to an ultragraph edge. In previous work, based on a study of the properties of dependencies, a system of axioms was presented with proof of consistency and completeness. In this work, the closures were studied for generalized typed inclusion dependencies. An algorithm for constructing closures has been developed and its correctness has been proven. The results obtained are further used to develop an algorithm for constructing a minimal covering. At the end of the article, examples are presented that demonstrate the operation of the algorithms.

база данныхобобщенные зависимости включенияминимальное покрытиеdatabasegeneralized inclusion dependenciesminimal coveringГосзадание ИМ СО РАН, проект No FWNF-2022-0016.State task IM SB RAS, project No. FWNF-2022-0016.ReferencesJ. 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.M. Casanova, R. Fagin, and C. Papadimitriou, “Inclusion dependencies and their interaction with functional dependencies,” Journal of Computer and System Sciences, vol. 28, no. 1, pp. 29–59, 1984.M. Casanova, R. Fagin, and C. Papadimitriou, “Inclusion dependencies and their interaction with functional dependencies,” Journal of Computer and System Sciences, vol. 28, no. 1, pp. 29–59, 1984.A. K. Chandra and M. Y. Vardi, “The Implication Problem for Functional and Inclusion Dependencies is Undecidable,” SIAM Journal on Computing, vol. 14, no. 3, pp. 671–677, 1985, doi: 10.1137/0214049.A. K. Chandra and M. Y. Vardi, “The Implication Problem for Functional and Inclusion Dependencies is Undecidable,” SIAM Journal on Computing, vol. 14, no. 3, pp. 671–677, 1985, doi: 10.1137/0214049.R. Fagin and M. Y. Vardi, “Armstrong databases for functional and inclusion dependencies,” Information Processing Letters, vol. 16, no. 1, pp. 13–19, 1983, doi: 10.1016/0020-0190(83)90005-4.R. Fagin and M. Y. Vardi, “Armstrong databases for functional and inclusion dependencies,” Information Processing Letters, vol. 16, no. 1, pp. 13–19, 1983, doi: 10.1016/0020-0190(83)90005-4.P. M. Kanellakis, R. Cosmadakis, and M. Y. Vardi, “Unary inclusion dependencies have polynomial time inference problems,” in Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC '83), 1983, pp. 264–277, doi: 10.1145/800061.808756.P. M. Kanellakis, R. Cosmadakis, and M. Y. Vardi, “Unary inclusion dependencies have polynomial time inference problems,” in Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC '83), 1983, pp. 264–277, doi: 10.1145/800061.808756.S. S. Cosmadakis, P. C. Kanellakis, and M. Y. Vardi, “Polynomial-time implication problems for unary inclusion dependencies,” ACM, vol. 37, no. 1, pp. 15–46, 1990, doi: 10.1145/78935.78937.S. S. Cosmadakis, P. C. Kanellakis, and M. Y. Vardi, “Polynomial-time implication problems for unary inclusion dependencies,” ACM, vol. 37, no. 1, pp. 15–46, 1990, doi: 10.1145/78935.78937.M. Levene and V. M. W., “Justification for Inclusion Dependency Normal Form,” IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 2, pp. 281–291, 2000, doi: 10.1109/69.842267.M. Levene and V. M. W., “Justification for Inclusion Dependency Normal Form,” IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 2, pp. 281–291, 2000, doi: 10.1109/69.842267.M. Hannula and S. Link, “On the Interaction of Functional and Inclusion Dependencies with Independence Atoms,” in Proceedings of the International Conference on Database Systems for Advanced Applications, 2018, pp. 353–369, doi: 10.1007/978-3-319-91458-9_21.M. Hannula and S. Link, “On the Interaction of Functional and Inclusion Dependencies with Independence Atoms,” in Proceedings of the International Conference on Database Systems for Advanced Applications, 2018, pp. 353–369, doi: 10.1007/978-3-319-91458-9_21.J. Biskup and P. Dublish, “Objects in relational database schemes with functional, inclusion and exclusion dependencies,” in 3rd Symposium on Mathematical Fundamentals of Database and Knowledge Base Systems, 1991, pp. 276–290, doi: 10.1007/3-540-54009-1_20.J. Biskup and P. Dublish, “Objects in relational database schemes with functional, inclusion and exclusion dependencies,” in 3rd Symposium on Mathematical Fundamentals of Database and Knowledge Base Systems, 1991, pp. 276–290, doi: 10.1007/3-540-54009-1_20.F. De Marchi, S. Lopes, and J.-M. Petit, “Efficient Algorithms for Mining Inclusion Dependencies,” in Advances in Database Technology — EDBT 2002, 2002, pp. 464–476, doi: 10.1007/3-540-45876-X_30.F. De Marchi, S. Lopes, and J.-M. Petit, “Efficient Algorithms for Mining Inclusion Dependencies,” in Advances in Database Technology — EDBT 2002, 2002, pp. 464–476, doi: 10.1007/3-540-45876-X_30.J. Bauckmann, Z. Abedjan, H. M"uller, and F. Naumann, “Discovering conditional inclusion dependencies,” in Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012, pp. 2094–2098, doi: 10.1145/2396761.2398580.J. Bauckmann, Z. Abedjan, H. M"uller, and F. Naumann, “Discovering conditional inclusion dependencies,” in Proceedings of the 21st ACM International Conference on Information and Knowledge Management, 2012, pp. 2094–2098, doi: 10.1145/2396761.2398580.M. T. Gomez-Lopez, R. M. Gasca, and J. M. Perez-Alvarez, “Compliance validation and diagnosis of business data constraints in business processes,” Information Systems, vol. 48, pp. 26–43, 2015.M. T. Gomez-Lopez, R. M. Gasca, and J. M. Perez-Alvarez, “Compliance validation and diagnosis of business data constraints in business processes,” Information Systems, vol. 48, pp. 26–43, 2015.S. Ma, W. Fan, and L. Bravo, “Extending inclusion dependencies with conditions,” Theoretical Computer Science, vol. 515, pp. 64–95, 2014, doi: 10.1016/j.tcs.2013.11.002.S. Ma, W. Fan, and L. Bravo, “Extending inclusion dependencies with conditions,” Theoretical Computer Science, vol. 515, pp. 64–95, 2014, doi: 10.1016/j.tcs.2013.11.002.F. Tschirschnitz, T. Papenbrock, and F. Naumann, “Detecting Inclusion Dependencies on Very Many Tables,” ACM Transactions on Database Systems, vol. 42, no. 3, pp. 1–29, 2017, doi: 10.1145/3105959.F. Tschirschnitz, T. Papenbrock, and F. Naumann, “Detecting Inclusion Dependencies on Very Many Tables,” ACM Transactions on Database Systems, vol. 42, no. 3, pp. 1–29, 2017, doi: 10.1145/3105959.Y. Kaminsky, E. Pena, and F. Naumann, “Discovering Similarity Inclusion Dependencies,” Proceedings of the ACM on Management of Data, vol. 1, no. 1, pp. 1–24, 2023, doi: 10.1145/3588929.Y. Kaminsky, E. Pena, and F. Naumann, “Discovering Similarity Inclusion Dependencies,” Proceedings of the ACM on Management of Data, vol. 1, no. 1, pp. 1–24, 2023, doi: 10.1145/3588929.M. Levene and G. Loizou, “Null Inclusion Dependencies in Relational Databases,” Information and Computation, vol. 136, no. 2, pp. 67–108, 1997, doi: 10.1006/inco.1997.2631.M. Levene and G. Loizou, “Null Inclusion Dependencies in Relational Databases,” Information and Computation, vol. 136, no. 2, pp. 67–108, 1997, doi: 10.1006/inco.1997.2631.M. Levene and G. Loizou, “The additivity problem for data dependencies in incomplete relational databases,” in Semantics in Databases, 1998, vol. 1358, pp. 136–169, doi: 10.1007/BFb0035008.M. Levene and G. Loizou, “The additivity problem for data dependencies in incomplete relational databases,” in Semantics in Databases, 1998, vol. 1358, pp. 136–169, doi: 10.1007/BFb0035008.H. K"ohler and S. Link, “Inclusion Dependencies Reloaded,” in Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, 2015, pp. 1361–1370.H. K"ohler and S. Link, “Inclusion Dependencies Reloaded,” in Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, 2015, pp. 1361–1370.V. S. Zykin and S. V. 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. S. Zykin and S. V. 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.S. V. Zykin, “Generalization of typed include dependencies with null values in databases,” Modeling and Analysis of Information Systems, vol. 30, no. 3, pp. 192–201, 2023.S. V. Zykin, “Generalization of typed include dependencies with null values in databases,” Modeling and Analysis of Information Systems, vol. 30, no. 3, pp. 192–201, 2023.

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