ВВЕДЕНИЕ В СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ



         

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


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

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

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

  • либо кортеж
    ,

  • либо найдется конечная последовательность элементов
    , такая, что все кортежи
    принадлежат отношению
    .

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

    .

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

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

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

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

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

    Конструкция

    Где используется

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

    Таблица 5 Отношение R

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

    состоит из кортежей (добавленные кортежи помечены серым цветом):

    Конструкция

    Где используется

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

    Таблица 6 Транзитивное замыкание отношения R

    Очевидный смысл замыкания

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




    Содержание  Назад  Вперед