Анализ типизированных зависимостей включения с неопределенными значениями
https://doi.org/10.18255/1818-1015-2017-2-155-167
Аннотация
Неопределенные значения стали актуальной проблемой с момента создания реляционной модели данных. Влияние неопределенностей сказывается на всех видах зависимостей, используемых при проектировании и эксплуатации базы данных. В полной мере это относится и к зависимостям включения, которые являются теоретической основой ссылочной целостности на данные. Попытки решения указанной проблемы содержат неточности как в постановке задачи, так и в самом ее решении. К постановочным ошибкам можно отнести использование в определении нетипизированных зависимостей включения, что приводит к перестановкам атрибутов, хотя в технологиях баз данных атрибуты идентифицируются по имени, а не по их позиции. Кроме того, связывание зависимостью включения разнородных, пусть даже однотипных, атрибутов является признаком потерянной функциональной зависимости и приводит к взаимодействию нетривиальных зависимостей включения и функциональных зависимостей. Зависимости включения должны определять количественное соотнесение объектов друг с другом, а не значений атрибутов. Неточности в решении указанной проблемы содержатся в формулировках аксиом и доказательстве их свойств, в том числе полноты. В этой статье предлагается оригинальное решение этой проблемы только для типизированных зависимостей включения при наличии неопределенных значений: предложена система аксиом, доказана ее полнота и непротиворечивость. На основе правил вывода разработан алгоритм построения не избыточного множества типизированных зависимостей включения. Доказана корректность этого алгоритма.
Об авторах
Владимир Сергеевич Зыкин
Омский государственный технический университет
Россия
Россия
аспирант
просп. Мира, 11, г. Омск, 644050 Россия
Сергей Владимирович Зыкин
Институт математики им. С.Л. Соболева СО РАН
Россия
Россия
д-р техн. наук, профессор
ул. Певцова, 13, г. Омск, 644043 Россия
Список литературы
1. Ullman J., Principles of database systems, Computer Science Press, Stanford University, 1980, 379 pp.
2. Maier D., The theory of relational databases, Computer Science Press, Rockville, 1983, 637 pp.
3. 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.
4. 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.
5. Fagin R., Vardi M. Y., “Armstrong databases for functional and inclusion dependencies”, Information Processing Letters, 16:1 (1983), 13–19.
6. 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.
7. Cosmadakis S. S., Kanellakis P. C., Vardi M. Y., “Polynomial-time implication problems for unary inclusion dependencies”, J. ACM, 37:1 (1990), 15–46.
8. Levene M., Vincent M. W., “Justification for Inclusion Dependency Normal Form”, IEEE Transactions on Knowledge and Data Engineering, 12:2 (2000), 281–291.
9. Beeri C., Fagin R., Maier D., Yannakakis M., “On the Desirability of Acyclic Database Schemes”, ACM, 38:3 (1983), 479–513.
10. Missaoui R., Godin R., “The Implication Problem for Inclusion Dependencies: A Graph Approach”, SIGMOD Record, 19:1 (1990), 36–40.
11. Зыкин В.С., “Ссылочная целостность данных в корпоративных информационных системах”, Информатика и ее применения, 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).]
12. Biskup J., Dublish P., “Objects in Relational Database Schemes with Functional, Inclusion and Exclusion Dependencies”, Theoretical Informatics and Applications, 27 (1993), 183– 219.
13. Johnson D. S., Klug A., “Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies”, Computer and System Sciences, 28 (1984), 167–189.
14. 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.
15. Ma S, Fan W, Bravo L., “Extending inclusion dependencies with conditions”, Theoretical Computer Science, 515 (2014), 64–95.
16. 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.
17. 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.
18. Visser J., “Coupled Transformation of Schemas, Documents, Queries, and Constraints”, Electronic Notes in Theoretical Computer Science, 200:3 (2008), 3–23.
19. Garmany J., Walker J., Clark T., Logical Database Design Principles, CRC Press, Auerbach Publications, New York, NY, USA, 2005, 69 pp.
20. Lopes S., Petit J.M., Toumani F., “Discovering interesting inclusion dependencies: application to logical database tuning”, Information Systems, 27:1 (2002), 1–19.
21. Levene M., Loizou G., “Null Inclusion Dependencies in Relational Databases”, Information and Computation, 136:2 (1997), 67–108.
22. 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.
23. 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.
Рецензия
Для цитирования:
Зыкин В.С., Зыкин С.В. Анализ типизированных зависимостей включения с неопределенными значениями. Моделирование и анализ информационных систем. 2017;24(2):155-167. https://doi.org/10.18255/1818-1015-2017-2-155-167
For citation:
Zykin V.S., Zykin S.V. Analysis of Typed Inclusion Dependencies with Null Values. Modeling and Analysis of Information Systems. 2017;24(2):155-167. (In Russ.) https://doi.org/10.18255/1818-1015-2017-2-155-167
Просмотров: 12291
Послать статью по эл. почте 