maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2023-3-192-201mais-1798Research ArticleTheory of DataОбобщенные типизированные зависимости включения с неопределенными значениями в базах данныхGeneralization of typed include dependencies with null values in databaseshttps://orcid.org/0000-0002-0576-2149ЗыкинСергей ВладимировичZykinSergey V.szykin@mail.ruИнститут математики им. С.Л. Соболева СО РАНРоссияSobolev institute of mathematics SB RASRussian Federation202317092023303192201Copyright © Зыкин С.В., 20232023Зыкин С.В.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/1798

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

The paper discusses a new type of dependency in databases, which is a generalization of inclusion dependencies. Traditionally, such dependencies are used in practice to ensure referential integrity. In this case, the restriction is established only between a pair of relations, the first of which is called the main, the second is external. In practice, referential integrity often needs to be established for a larger number of relations, where several main and several external relations participate in the same constraint. Such a structure corresponds to an ultragraph. The paper provides a rationale for generalized inclusion dependencies that take into account the presence of null values in external relations. Based on the study of the properties of typed dependencies, a system of axioms is obtained, for which consistency (soundness) and completeness are proved.

база данныхзависимости включенияаксиоматиканеопределенные значенияdatabaseinclusion dependenciesaxiomaticsnull valuesРабота выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0016.The research was funded in accordance with the state task of the IM SB RAS, project 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.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.R. Fagin and M. Y. Vardi, “Armstrong databases for functional and inclusion dependencies,” Information Processing Letters, vol. 16, no. 1, pp. 13–19, 1983.R. Fagin and M. Y. Vardi, “Armstrong databases for functional and inclusion dependencies,” Information Processing Letters, vol. 16, no. 1, pp. 13–19, 1983.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, 1983, pp. 264–277.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, 1983, pp. 264–277.S. S. Cosmadakis, P. C. Kanellakis, and M. Y. Vardi, “Polynomial-time implication problems for unary inclusion dependencies,” Association for Computing Machinery, vol. 37, no. 1, pp. 15–46, 1990.S. S. Cosmadakis, P. C. Kanellakis, and M. Y. Vardi, “Polynomial-time implication problems for unary inclusion dependencies,” Association for Computing Machinery, vol. 37, no. 1, pp. 15–46, 1990.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.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.C. Beeri, R. Fagin, D. Maier, and Y. M., “On the Desirability of Acyclic Database Schemes,” Association for Computing Machinery, vol. 30, no. 3, pp. 479–513, 1990.C. Beeri, R. Fagin, D. Maier, and Y. M., “On the Desirability of Acyclic Database Schemes,” Association for Computing Machinery, vol. 30, no. 3, pp. 479–513, 1990.R. Missaoui and R. Godin, “The Implication Problem for Inclusion Dependencies: A Graph Approach,” ACM SIGMOD Record, vol. 19, no. 1, pp. 36–40, 1990.R. Missaoui and R. Godin, “The Implication Problem for Inclusion Dependencies: A Graph Approach,” ACM SIGMOD Record, vol. 19, no. 1, pp. 36–40, 1990.M. Hannula and S. Link, “On the Interaction of Functional and Inclusion Dependencies with Independence Atoms,” in Database Systems for Advanced Applications, 2018, pp. 353–369.M. Hannula and S. Link, “On the Interaction of Functional and Inclusion Dependencies with Independence Atoms,” in Database Systems for Advanced Applications, 2018, pp. 353–369.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.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.D. S. Johnson and A. Klug, “Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies,” Journal Computer and System Sciences, vol. 28, no. 1, pp. 167–189, 1984.D. S. Johnson and A. Klug, “Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies,” Journal Computer and System Sciences, vol. 28, no. 1, pp. 167–189, 1984.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.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.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.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.M. T. G'omez-L'opez, R. M. Gasca, and J. M. P'erez-'Alvarez, “Compliance validation and diagnosis of business data constraints in business processes,” Information Systems, vol. 48, pp. 26–43, 2015.M. T. G'omez-L'opez, R. M. Gasca, and J. M. P'erez-'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.S. Ma, W. Fan, and L. Bravo, “Extending inclusion dependencies with conditions,” Theoretical Computer Science, vol. 515, pp. 64–95, 2014.J. Visser, “Coupled Transformation of Schemas, Documents, Queries, and Constraints,” Electronic Notes in Theoretical Computer Science, vol. 200, no. 3, pp. 3–23, 2008.J. Visser, “Coupled Transformation of Schemas, Documents, Queries, and Constraints,” Electronic Notes in Theoretical Computer Science, vol. 200, no. 3, pp. 3–23, 2008.J. Garmany, J. Walker, and T. Clark, Logical Database Design Principles. Auerbach Publications, 1980.J. Garmany, J. Walker, and T. Clark, Logical Database Design Principles. Auerbach Publications, 1980.S. Lopes, J.-M. Petit, and F. Toumani, “Discovering interesting inclusion dependencies: application to logical database tuning,” Information Systems, vol. 27, no. 1, pp. 1–19, 2002.S. Lopes, J.-M. Petit, and F. Toumani, “Discovering interesting inclusion dependencies: application to logical database tuning,” Information Systems, vol. 27, no. 1, pp. 1–19, 2002.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.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.M. Levene and G. Loizou, “Null Inclusion Dependencies in Relational Databases,” Information and Computation, vol. 136, no. 2, pp. 67–108, 1997.M. Levene and G. Loizou, “Null Inclusion Dependencies in Relational Databases,” Information and Computation, vol. 136, no. 2, pp. 67–108, 1997.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.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.H. K"ohler and S. Link, “Inclusion Dependencies Reloaded,” in Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, New York, NY, USA, 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, New York, NY, USA, 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.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.S. V. Zykin, “Domains of functional dependences in databases,” Trudy Instituta Matematiki i Mekhaniki UrO RAN, vol. 22, no. 3, pp. 117–129, 2016.S. V. Zykin, “Domains of functional dependences in databases,” Trudy Instituta Matematiki i Mekhaniki UrO RAN, vol. 22, no. 3, pp. 117–129, 2016.

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