Введение в системы управления базами данных

Транзитивное замыкание отношений



Транзитивное замыкание отношений

Введем понятие транзитивного замыкания, связанное с бинарными отношениями, которое понадобится в дальнейшем.

Определение 11. Пусть отношение

задано на декартовом квадрате
некоторого множества
. Транзитивным замыканием отношения
называется новое отношение
, состоящее из кортежей
, для которых выполняется:
  • либо кортеж
    ,
  • либо найдется конечная последовательность элементов
    , такая, что все кортежи
    принадлежат отношению
    .

Очевидно, что

.

Пример 7. Пусть множество

представляет собой следующее множество деталей и конструкций:

= {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось}

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

("непосредственно используется в") и состоит из следующих кортежей:









Содержание раздела