maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2022-3-210-227mais-1713Research ArticleDiscrete Mathematics in Relation to Computer ScienceТестирование зависимостей и правил вывода в базах данныхTesting Dependencies and Inference Rules in Databaseshttps://orcid.org/0000-0002-0576-2149ЗыкинСергей ВладимировичZykinSergey V.szykin@mail.ruИнститут математики им. С. Л. Соболева СО РАНРоссияSobolev institute of mathematics SB RASRussian Federation202225092022293210227Copyright © Зыкин С.В., 20222022Зыкин С.В.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/1713

Процесс тестирования зависимостей и правил вывода может быть использован в двух направлениях. Во-первых, тестирование позволяет проверить гипотезы относительно неизвестных правил вывода. Основная цель при этом поиск реализации отношения - контрпримера, который удовлетворяет исходным зависимостям и противоречит следствию. Найденный контрпример опровергает гипотезу, отсутствие контрпримера позволяет приступить к поиску обобщения правила и условий его выполнимости (logically imply). Тестирование не может служить доказательством выполнимости правил вывода, поскольку процесс обобщения требует поиска универсальных условий выводимости для каждого правила, что невозможно запрограммировать, поскольку даже вид этих условий неизвестен. Во-вторых, при проектировании конкретной базы данных может потребоваться проверка выполнимости правила, для которого отсутствует теоретическое обоснование. Такая ситуация может проявиться при наличии аномалий в суперключе. Решение этой проблемы основывается на использовании правил вывода зависимостей соединения. Для этих зависимостей пока не найдена полная система правил (аксиом). В данной статье рассматривается: 1) методика проведения тестирования правил вывода на примере зависимостей соединения, 2) предложена схема алгоритма тестирования, 3) рассмотрены некоторые гипотезы, для которых отсутствуют контрпримеры и правила вывода, 4) предложен пример использования тестирования при поиске корректной декомпозиции суперключа.

The process of testing dependencies and inference rules can be used in two ways. First, testing allows verification hypotheses about unknown inference rules. The main goal, in this case, is to search for the relation - a counterexample that illustrates the feasibility of the initial dependencies and contradicts the consequence. The found counterexample refutes the hypothesis, the absence of a counterexample allows searching for a generalization of the rule and conditions for its feasibility (logically imply). Testing cannot be used as a proof of the feasibility of inference rules, since the process of generalization requires the search for universal inference conditions for each rule, which cannot be programmed, since even the form of these conditions is unknown. Secondly, when designing a particular database, it may be necessary to test the feasibility of a rule for which there is no theoretical justification. Such a situation can take place in the presence of anomalies in the superkey. The solution to this problem is based on using join dependency inference rules. For these dependencies, a complete system of rules (axioms) has not yet been found. This paper discusses: 1) a technique for testing inference rules using the example of join dependencies, 2) a scheme of a testing algorithm is proposed, 3) some hypotheses are considered for which there are no counterexamples and inference rules, 4) an example of using testing when searching for a correct decomposition of a superkey is proposed.

реляционные базы данныхзависимости соединенияправила выводатестированиеrelational databasesjoin dependenciesinference rulestestingReferencesJ. 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 (1st. ed.) Addison-Wesley Longman Publishing Co., 1995.S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases: The Logical Level (1st. ed.) Addison-Wesley Longman Publishing Co., 1995.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. doi: 10.1016/0022-0000(84)90075-8.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. doi: 10.1016/0022-0000(84)90075-8.H. Ko¨hler 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. Ko¨hler 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. 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.E. Sciore, “A Complete Axiomatization of Full Join Dependencies”, Journal of the ACM, vol. 29, no. 2, pp. 373-393, 1982. doi: 10.1145/322307.322313.E. Sciore, “A Complete Axiomatization of Full Join Dependencies”, Journal of the ACM, vol. 29, no. 2, pp. 373-393, 1982. doi: 10.1145/322307.322313.S. V. Zykin, “Generalization of Derivation Rules for Join Dependencies in Database”, Automatic Control and Computer Sciences, vol. 55, no. 7, pp. 731-737, 2021. doi: 10.3103/S0146411621070191.S. V. Zykin, “Generalization of Derivation Rules for Join Dependencies in Database”, Automatic Control and Computer Sciences, vol. 55, no. 7, pp. 731-737, 2021. doi: 10.3103/S0146411621070191.D. Maier, A. O. Mendelzon, and Y. Sagiv, “Testing implications of data dependencies”, ACM Transactions on Database Systems, vol. 4, no. 4, pp. 455-469, 1979. doi: 10.1145/320107.320115.D. Maier, A. O. Mendelzon, and Y. Sagiv, “Testing implications of data dependencies”, ACM Transactions on Database Systems, vol. 4, no. 4, pp. 455-469, 1979. doi: 10.1145/320107.320115.D. Maier, Y. Sagiv, and M. Yannakakis, “On the Complexity of Testing Implications of Functional and Join Dependencies”, Journal of the ACM, vol. 28, no. 4, pp. 680-695, 1981. doi: 10.1145/322276.322280.D. Maier, Y. Sagiv, and M. Yannakakis, “On the Complexity of Testing Implications of Functional and Join Dependencies”, Journal of the ACM, vol. 28, no. 4, pp. 680-695, 1981. doi: 10.1145/322276.322280.P. C. Fischer and D. M. Tsou, “Whether a set of multivalued dependencies implies a join dependency is NP-hard”, SIAM Journal on Computing, vol. 12, no. 2, pp. 259-266, 1983. doi: 10.1137/0212015.P. C. Fischer and D. M. Tsou, “Whether a set of multivalued dependencies implies a join dependency is NP-hard”, SIAM Journal on Computing, vol. 12, no. 2, pp. 259-266, 1983. doi: 10.1137/0212015.C. Beeri and M. Vardi, “Formal Systems for Tuple and Equality Generating Dependencies”, SIAM Journal on Computing, vol. 13, no. 1, pp. 76-98, 1984. doi: 10.1137/0213006.C. Beeri and M. Vardi, “Formal Systems for Tuple and Equality Generating Dependencies”, SIAM Journal on Computing, vol. 13, no. 1, pp. 76-98, 1984. doi: 10.1137/0213006.C. Beeri and M. Vardi, “A Proof Procedure for Data Dependencies”, Journal of the ACM, vol. 31, no. 4, pp. 718-741, 1984. doi: 10.1145/1634.1636.C. Beeri and M. Vardi, “A Proof Procedure for Data Dependencies”, Journal of the ACM, vol. 31, no. 4, pp. 718-741, 1984. doi: 10.1145/1634.1636.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.S. Bell and P. Brockhausen, “Discovery of Data Dependencies in Relational Databases”, University of Dortmund, 1995. doi: 10.17877/DE290R-8395.S. Bell and P. Brockhausen, “Discovery of Data Dependencies in Relational Databases”, University of Dortmund, 1995. doi: 10.17877/DE290R-8395.J. Kivinen and H. Mannila, “Approximate inference of functional dependencies from relations”, Theoretical Computer Science, vol. 149, no. 1, pp. 129-149, 1995. doi: 10.1016/0304-3975(95)00028-U.J. Kivinen and H. Mannila, “Approximate inference of functional dependencies from relations”, Theoretical Computer Science, vol. 149, no. 1, pp. 129-149, 1995. doi: 10.1016/0304-3975(95)00028-U.M. W. Vincent and M. Levene, “Restructuring Partitioned Normal Form Relations without Information Loss”, SIAM Journal on Computing, vol. 29, no. 5, pp. 1550-1567, 2000. doi: 10.1137/S0097539797326319.M. W. Vincent and M. Levene, “Restructuring Partitioned Normal Form Relations without Information Loss”, SIAM Journal on Computing, vol. 29, no. 5, pp. 1550-1567, 2000. doi: 10.1137/S0097539797326319.S. V. Zykin, “Formation of Hypercube Representation of Relational Database”, Programming and Computer Software, vol. 32, no. 6, pp. 348-354, 2006. doi: 10.1134/S0361768806060077.S. V. Zykin, “Formation of Hypercube Representation of Relational Database”, Programming and Computer Software, vol. 32, no. 6, pp. 348-354, 2006. doi: 10.1134/S0361768806060077.S. Hartmann, S. Link, and T. Trinh, “Constraint Acquisition You Can Chase but You Cannot Find”, in Conferences in Research and Practice in Information Technology Series, vol. 79, 2008, pp. 59-68.S. Hartmann, S. Link, and T. Trinh, “Constraint Acquisition You Can Chase but You Cannot Find”, in Conferences in Research and Practice in Information Technology Series, vol. 79, 2008, pp. 59-68.F. Marchi, S. Lopes, and J. M. Petit, “Unary and n-ary inclusion dependency discovery in relational databases”, Journal of Intelligent Information Systems, vol. 32, pp. 53-73, 2009. doi: 10.1007/s10844-007-0048-x.F. Marchi, S. Lopes, and J. M. Petit, “Unary and n-ary inclusion dependency discovery in relational databases”, Journal of Intelligent Information Systems, vol. 32, pp. 53-73, 2009. doi: 10.1007/s10844-007-0048-x.X. Hu, M. Qiao, and Y. Tao, “I/O-efficient join dependency testing, Loomis Whitney join, and triangle enumeration”, Journal of Computer and System Sciences, vol. 82, no. 8, pp. 1300-1315, 2016.X. Hu, M. Qiao, and Y. Tao, “I/O-efficient join dependency testing, Loomis Whitney join, and triangle enumeration”, Journal of Computer and System Sciences, vol. 82, no. 8, pp. 1300-1315, 2016.F. M. Malvestuto, “A complete axiomatization of full acyclic join dependencies”, Information Processing Letters, vol. 68, no. 3, pp. 133-139, 1998. doi: 10.1016/S0020-0190(98)00148-3.F. M. Malvestuto, “A complete axiomatization of full acyclic join dependencies”, Information Processing Letters, vol. 68, no. 3, pp. 133-139, 1998. doi: 10.1016/S0020-0190(98)00148-3.

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