Минимальное покрытие обобщенных типизированных зависимостей включения в базах данных

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