Preview

Моделирование и анализ информационных систем

Расширенный поиск

Обобщение правил вывода для зависимостей соединения в базах данных

https://doi.org/10.18255/1818-1015-2020-3-356-365

Полный текст:

Аннотация

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

Об авторе

Сергей Владимирович Зыкин
Институт математики им. С.Л. Соболева, СО РАН
Россия

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

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



Список литературы

1. J. Ullman, Principles of Database Systems. Stanford University: Computer Science Press, 1980.

2. D. Maier, The Theory of Relational Databases. Rockville: Computer Science Press, 1983.

3. S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases: The Logical Level. Addison-Wesley, 1994.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. E. Sciore, "A Complete Axiomatization of Full Join Dependencies”, J. ACM, vol. 29, no. 2, pp. 373-393, 1982. doi: 10.1145/322307.322313.

10. 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.

11. 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.

12. F. Malvestuto, "A Complete Axiomatization of Full Acyclic Join Dependencies”, Inf. Process. Lett., vol. 68, no. 3, pp. 133-139, 1998.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. S. Zykin, "Domains of functional dependences in databases”, Trudy Inst. Mat. i Mekh. UrO RAN, vol. 22, no. 3, pp. 117-129, 2016.


Для цитирования:


Зыкин С.В. Обобщение правил вывода для зависимостей соединения в базах данных. Моделирование и анализ информационных систем. 2020;27(3):356-365. https://doi.org/10.18255/1818-1015-2020-3-356-365

For citation:


Zykin S.V. A Generalization of the Inference Rules for Join Dependencies in Databases. Modeling and Analysis of Information Systems. 2020;27(3):356-365. (In Russ.) https://doi.org/10.18255/1818-1015-2020-3-356-365

Просмотров: 129


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)