Регистрация / Вход
Прислать материал

Типизированные зависимости включения с неопределенными значениями

Сведения об участнике
ФИО
Зыкин Владимир Сергеевич
Вуз
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный технический университет»
Тезисы (информация о проекте)
Область наук
Информационные технологии и вычислительные системы
Раздел области наук
Информационные технологии
Тема
Типизированные зависимости включения с неопределенными значениями
Резюме
Неопределенные значения стали актуальной проблемой с момента создания реляционной модели данных. Влияние неопределенностей сказывается на всех видах зависимостей, используемых при работе с базой данных. В полной мере это относится и к зависимостям включения, которые являются теоретической основой ссылочной целостности на данные. В этой работе предлагается решение этой проблемы для типизированных зависимостей включения при наличии неопределенных значений: предложена система аксиом, доказана ее полнота и непротиворечивость. На основе правил вывода разработан алгоритм построения неизбыточного по зависимостям и атрибутам множества типизированных зависимостей включения
Ключевые слова
Зависимости включения, ограничения целостности, атрибуты, реляционные базы данных, неопределенные значения.
Цели и задачи
Цель - обеспечение ссылочной целостности неполных данных.
Задачи:
- построение системы аксиом для зависимостей включения;
- доказательство полноты и надежности разработанной системы;
- разработка алгоритма построения неизбыточного набора зависимостей включения.
Введение

Теоретической основой ссылочных ограничений являются зависимости включения и их взаимодействие с другими видами зависимостей. Проблеме исследования зависимостей включения до сих пор уделяется со стороны исследователей недостаточное внимание, поскольку, с одной стороны, остаются нерешенными некоторые теоретические проблемы. С другой стороны, практика использования БД формулирует новые требования к ссылочным ограничениям целостности.

В данной работе предлагается разработка основ формальной теории для типизированных зависимостей включения при наличии неопределенных значений. Разработанная теория используется для построения не избыточного множества ссылочных ограничений целостности.

Методы и материалы

Методы:

  • Для реализации работоспособной БД используется теория проектирования баз данных;
  • Для формализации описываемой системы используется аппарат математической логики;
  • При доказательстве полноты системы аксиом применяется метод математической индукции.

 

Описание и обсуждение результатов

В ходе работы были формулизованы зависимости включения, построена система аксиом и доказаны ее надежность и полнота.

Был реализован алгоритм удаления избыточных зависимостей включения, сложность которого является полиномиальной 4-го порядка. Данная сложность считается хорошей ввиду того, что большинство реализованных методов имеют экспоненциальную сложность.

 

Используемые источники
1. Ullman J. Principles of database systems// Computer Science Press, 1980. - 379 p.
2. Maier D. The theory of relational databases// Computer Science Press, 1983. - 637 p.
3. Casanova M., Fagin R., Papadimitriou C. 1984. Inclusion Dependencies and Their Interaction with Functional Dependencies. Journal of Computer and System Sciences. № 28(1). P. 29-59.
4. Зыкин В.С. Ссылочная целостность данных в корпоративных информационных системах. Информатика и ее применения, 2015. Т. 9. Вып. 3. С. 119-127.
5. Missaoui R., Godin R. 1990. The Implication Problem for Inclusion Dependencies: A Graph Approach. SIGMOD Record. V 19, № 1. P. 36-40
Information about the project
Surname Name
Vladimir Zykin
Project title
Integrity Constraint of Incomplete Data
Summary of the project
The research gives original solution of the problem for typed inclusion dependencies with null values. Special attention is given to axiom system with it's provements of soundness and completeness. The algorithm of the IND set construction is presented. This set is non-redundant by dependencies and attributes.
Keywords
Inclusion Dependencies, Integrity Constraints, Attributes, Relational Database, NULL-values.