Транзитивное замыкание отношений
Введем понятие транзитивного замыкания, связанное с бинарными отношениями, которое понадобится в дальнейшем.
Определение 11. Пусть отношение
задано на декартовом квадрате
некоторого множества
.
Транзитивным замыканием отношения
называется новое отношение
, состоящее из кортежей
, для которых выполняется:
либо кортеж ,
либо найдется конечная последовательность элементов , такая, что все кортежи принадлежат отношению .
Очевидно, что
.
Пример 7. Пусть множество
представляет собой следующее множество деталей и конструкций:
= {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось}
причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением
("непосредственно используется в") и состоит из следующих кортежей:
Конструкция
Где используется
|
| Болт |
Двигатель |
| Болт |
Колесо |
| Гайка |
Двигатель |
| Гайка |
Колесо |
| Двигатель |
Автомобиль |
| Колесо |
Автомобиль |
| Ось |
Колесо |
Таблица 5 Отношение R
Транзитивное замыкание
состоит из кортежей (добавленные кортежи помечены серым цветом):
Конструкция
Где используется
| Болт |
Двигатель |
| Болт |
Колесо |
| Гайка |
Двигатель |
| Гайка |
Колесо |
| Двигатель |
Автомобиль |
| Колесо |
Автомобиль |
| Ось |
Колесо |
| Болт |
Автомобиль |
| Гайка |
Автомобиль |
| Ось |
Автомобиль |
Таблица 6 Транзитивное замыкание отношения R
Очевидный смысл замыкания
состоит в описании включения деталей друг в друга не только непосредственно, а через использование их в промежуточных деталях, например, болт используется в автомобиле, т.к. он используется в двигателе, а двигатель используется в автомобиле.
