maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2017-2-155-167mais-506Research ArticleОригинальные статьиArticlesАнализ типизированных зависимостей включения с неопределенными значениямиAnalysis of Typed Inclusion Dependencies with Null Valueshttps://orcid.org/0000-0002-6492-2464ЗыкинВладимир СергеевичZykinVladimir S.

аспирант

просп. Мира, 11, г. Омск, 644050 Россия

graduate student

11 Mira av., Omsk 644050, Russia

vszykin@mail.ruhttps://orcid.org/0000-0002-0576-2149ЗыкинСергей ВладимировичZykinSergey V.

д-р техн. наук, профессор

ул. Певцова, 13, г. Омск, 644043 Россия

doctor of sciences in technic, professor

13 Pevtsova str., Omsk 644043, Russia

szykin@mail.ruОмский государственный технический университетРоссияOmsk State Technical UniversityRussian FederationИнститут математики им. С.Л. Соболева СО РАНРоссияSobolev Institute of Mathematics SB RASRussian Federation201729042017242155167Copyright © Зыкин В.С., Зыкин С.В., 20172017Зыкин В.С., Зыкин С.В.Zykin V.S., 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/506

Неопределенные значения стали актуальной проблемой с момента создания реляционной модели данных. Влияние неопределенностей сказывается на всех видах зависимостей, используемых при проектировании и эксплуатации базы данных. В полной мере это относится и к зависимостям включения, которые являются теоретической основой ссылочной целостности на данные. Попытки решения указанной проблемы содержат неточности как в постановке задачи, так и в самом ее решении. К постановочным ошибкам можно отнести использование в определении нетипизированных зависимостей включения, что приводит к перестановкам атрибутов, хотя в технологиях баз данных атрибуты идентифицируются по имени, а не по их позиции. Кроме того, связывание зависимостью включения разнородных, пусть даже однотипных, атрибутов является признаком потерянной функциональной зависимости и приводит к взаимодействию нетривиальных зависимостей включения и функциональных зависимостей. Зависимости включения должны определять количественное соотнесение объектов друг с другом, а не значений атрибутов. Неточности в решении указанной проблемы содержатся в формулировках аксиом и доказательстве их свойств, в том числе полноты. В этой статье предлагается оригинальное решение этой проблемы только для типизированных зависимостей включения при наличии неопределенных значений: предложена система аксиом, доказана ее полнота и непротиворечивость. На основе правил вывода разработан алгоритм построения не избыточного множества типизированных зависимостей включения. Доказана корректность этого алгоритма.

Null values have become an urgent problem since the creation of the relational data model. The impact of the uncertainty affects all types of dependencies used in the design and operation of the database. This fully applies to the inclusion dependencies, which are the theoretical basis for referential integrity on the data. Attempts to solve this problem contain inaccuracy in the statement of the problem and its solution. The errors in formulation of the problem can be associated with the use in the definition of untyped inclusion dependencies, which leads to permutations of the attributes, although, the attributes in database technology are identified by name and not by their place. In addition, linking with the use of the inclusion dependencies of heterogeneous attributes, even of the same type, is a sign of lost functional dependencies and leads to interaction of inclusion dependencies and non-trivial functional dependencies. Inaccuracies in the solution of the problem are contained in the statements of axioms and the proof of their properties, including completeness. In this paper we propose an original solution of this problem only for typed inclusion dependencies in the presence of Null values: a new axiom system is proposed, its completeness and soundness are proved. On the basis of inference rules we developed an algorithm for the construction of a not surplus set of typed inclusion dependencies. The correctness of the algorithm is proved.

база данныхзависимости включенияаксиоматиканеопределенные значенияdatabaseinclusion dependencesaxiomaticNULL valuesReferencesUllman J., Principles of database systems, Computer Science Press, Stanford University, 1980, 379 pp.Ullman J., Principles of database systems, Computer Science Press, Stanford University, 1980, 379 pp.Maier D., The theory of relational databases, Computer Science Press, Rockville, 1983, 637 pp.Maier D., The theory of relational databases, Computer Science Press, Rockville, 1983, 637 pp.Casanova M., Fagin R., Papadimitriou C., “Inclusion Dependencies and Their Interaction with Functional Dependencies”, Journal of Computer and System Sciences, 28:1 (1984), 29–59.Casanova M., Fagin R., Papadimitriou C., “Inclusion Dependencies and Their Interaction with Functional Dependencies”, Journal of Computer and System Sciences, 28:1 (1984), 29–59.Chandra A. K., Vardi M. Y., “The Implication Problem for Functional and Inclusion Dependencies is Undecidable”, SIAM Journal on Computing, 14:3 (1985), 671–677.Chandra A. K., Vardi M. Y., “The Implication Problem for Functional and Inclusion Dependencies is Undecidable”, SIAM Journal on Computing, 14:3 (1985), 671–677.Fagin R., Vardi M. Y., “Armstrong databases for functional and inclusion dependencies”, Information Processing Letters, 16:1 (1983), 13–19.Fagin R., Vardi M. Y., “Armstrong databases for functional and inclusion dependencies”, Information Processing Letters, 16:1 (1983), 13–19.Kanellakis P. C., Cosmadakis S. S., Vardi M. Y., “Unary inclusion dependencies have polynomial time inference problems”, Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC ’83) (New York, USA, 1983), 1983, 264–277.Kanellakis P. C., Cosmadakis S. S., Vardi M. Y., “Unary inclusion dependencies have polynomial time inference problems”, Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC ’83) (New York, USA, 1983), 1983, 264–277.Cosmadakis S. S., Kanellakis P. C., Vardi M. Y., “Polynomial-time implication problems for unary inclusion dependencies”, J. ACM, 37:1 (1990), 15–46.Cosmadakis S. S., Kanellakis P. C., Vardi M. Y., “Polynomial-time implication problems for unary inclusion dependencies”, J. ACM, 37:1 (1990), 15–46.Levene M., Vincent M. W., “Justification for Inclusion Dependency Normal Form”, IEEE Transactions on Knowledge and Data Engineering, 12:2 (2000), 281–291.Levene M., Vincent M. W., “Justification for Inclusion Dependency Normal Form”, IEEE Transactions on Knowledge and Data Engineering, 12:2 (2000), 281–291.Beeri C., Fagin R., Maier D., Yannakakis M., “On the Desirability of Acyclic Database Schemes”, ACM, 38:3 (1983), 479–513.Beeri C., Fagin R., Maier D., Yannakakis M., “On the Desirability of Acyclic Database Schemes”, ACM, 38:3 (1983), 479–513.Missaoui R., Godin R., “The Implication Problem for Inclusion Dependencies: A Graph Approach”, SIGMOD Record, 19:1 (1990), 36–40.Missaoui R., Godin R., “The Implication Problem for Inclusion Dependencies: A Graph Approach”, SIGMOD Record, 19:1 (1990), 36–40.Зыкин В.С., “Ссылочная целостность данных в корпоративных информационных системах”, Информатика и ее применения, 9:3 (2015), 119–127; [Zykin V. S., “Ssylochnaya tselostnost dannykh v korporativnykh informatsionnykh sistemakh”, Informatika i ee primeneniya, 9:3 (2015), 119–127, (in Russian).]Зыкин В.С., “Ссылочная целостность данных в корпоративных информационных системах”, Информатика и ее применения, 9:3 (2015), 119–127; [Zykin V. S., “Ssylochnaya tselostnost dannykh v korporativnykh informatsionnykh sistemakh”, Informatika i ee primeneniya, 9:3 (2015), 119–127, (in Russian).]Biskup J., Dublish P., “Objects in Relational Database Schemes with Functional, Inclusion and Exclusion Dependencies”, Theoretical Informatics and Applications, 27 (1993), 183– 219.Biskup J., Dublish P., “Objects in Relational Database Schemes with Functional, Inclusion and Exclusion Dependencies”, Theoretical Informatics and Applications, 27 (1993), 183– 219.Johnson D. S., Klug A., “Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies”, Computer and System Sciences, 28 (1984), 167–189.Johnson D. S., Klug A., “Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies”, Computer and System Sciences, 28 (1984), 167–189.Marchi F. D., Lopes S., Petit J. M., “Efficient Algorithms for Mining Inclusion Dependencies”, Advances in Database Technology - EDBT 2002 (Prague, Czech Republic, 2002), 2002, 199–214.Marchi F. D., Lopes S., Petit J. M., “Efficient Algorithms for Mining Inclusion Dependencies”, Advances in Database Technology - EDBT 2002 (Prague, Czech Republic, 2002), 2002, 199–214.Ma S, Fan W, Bravo L., “Extending inclusion dependencies with conditions”, Theoretical Computer Science, 515 (2014), 64–95.Ma S, Fan W, Bravo L., “Extending inclusion dependencies with conditions”, Theoretical Computer Science, 515 (2014), 64–95.Bauckmann J., Abedjan Z., Leser U., MuЁller H., Naumann F., “Discovering conditional inclusion dependencies”, 21st ACM international conference on Information and knowledge management (CIKM ’12) (ACM, New York, NY, USA), 2012, 2094–2098.Bauckmann J., Abedjan Z., Leser U., MuЁller H., Naumann F., “Discovering conditional inclusion dependencies”, 21st ACM international conference on Information and knowledge management (CIKM ’12) (ACM, New York, NY, USA), 2012, 2094–2098.Goґmez-Loґpez F. T., Gasca R. M., Peґrez-Aґlvarez J. M., “Compliance validation and diagnosis of business data constraints in business processes”, Information Systems, 48 (2015), 26–43.Goґmez-Loґpez F. T., Gasca R. M., Peґrez-Aґlvarez J. M., “Compliance validation and diagnosis of business data constraints in business processes”, Information Systems, 48 (2015), 26–43.Visser J., “Coupled Transformation of Schemas, Documents, Queries, and Constraints”, Electronic Notes in Theoretical Computer Science, 200:3 (2008), 3–23.Visser J., “Coupled Transformation of Schemas, Documents, Queries, and Constraints”, Electronic Notes in Theoretical Computer Science, 200:3 (2008), 3–23.Garmany J., Walker J., Clark T., Logical Database Design Principles, CRC Press, Auerbach Publications, New York, NY, USA, 2005, 69 pp.Garmany J., Walker J., Clark T., Logical Database Design Principles, CRC Press, Auerbach Publications, New York, NY, USA, 2005, 69 pp.Lopes S., Petit J.M., Toumani F., “Discovering interesting inclusion dependencies: application to logical database tuning”, Information Systems, 27:1 (2002), 1–19.Lopes S., Petit J.M., Toumani F., “Discovering interesting inclusion dependencies: application to logical database tuning”, Information Systems, 27:1 (2002), 1–19.Levene M., Loizou G., “Null Inclusion Dependencies in Relational Databases”, Information and Computation, 136:2 (1997), 67–108.Levene M., Loizou G., “Null Inclusion Dependencies in Relational Databases”, Information and Computation, 136:2 (1997), 67–108.Levene M., Loizou G., “The additivity problem for data dependencies in incomplete relational databases”, Semantics in Databases, Lecture Notes in Computer Science., 189, Springer-Verlag Berlin Heidelberg, 1998, 136–169.Levene M., Loizou G., “The additivity problem for data dependencies in incomplete relational databases”, Semantics in Databases, Lecture Notes in Computer Science., 189, Springer-Verlag Berlin Heidelberg, 1998, 136–169.KoЁhler H., Link S., “Inclusion Dependencies Reloaded”, The 24th ACM International on Conference on Information and Knowledge Management (CIKM ’15) (ACM, New York, NY, USA), 2015, 1361–1370.KoЁhler H., Link S., “Inclusion Dependencies Reloaded”, The 24th ACM International on Conference on Information and Knowledge Management (CIKM ’15) (ACM, New York, NY, USA), 2015, 1361–1370.

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