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

Алгебра A отходит от оригинальной алгебры Кодда еще в одном отношении: она включает явную операцию транзитивного замыкания >TCLOSE<. Чтобы объяснить, как работает операция, рассмотрим отношение MM (рис. 1). Это отношение является примером того, что иногда называют диграфовым отношением, поскольку его можно представить как направленный граф.

MM     MAJOR_P# : P#    MINOR_P# : P#
-------------------------------------
       P1               P2
       P1               P3
       P2               P3
       P2               P4
       P3               P5
       P4               P6

Рис. 1 Отношение MM

Из интуитивных соображений иногда удобнее преобразовать направленный граф (рис. 2) в виде числой иерархии с возможно повторяющимися узлами (рис. 3). Конечно, эти два графа информационно эквивалентны.

Рис. 2 Граф отношения MM

Рис. 3 Граф отношения MM в виде иерархии

Поскольку MM является бинарным отношением, к нему можно применить операцию транзитивного замыкания. Операция описывается следующим образом:

• Пусть r - это бинарное отношение с атрибутами X и Y одного и того же типа T. Тогда транзитивное замыкание r (>TCLOSE< r) - это отношение r+ с тем же заголовком, что у r, и телом, являющимся надмножеством тела r, определяемым следующим образом: Кортеж

{ < X, T, x >, <Y, Y, y> }

входит в r+ том и только в том случае, когда он входит в r или существует последовательность значений z1, z2, …, zn (все типа T) таких, что кортежи

{ < X, T, x >, < Y, T, z1 > }

{ < X, T, z1 >, < Y, T, z2 > }

         ……………………

{ < X, T, zn >, < Y, T, y > }

все входят в r. Другими словами кортеж "(x, y)" входит в результат, только если существует путь в графе из узла x в узел y. Вот результат транзитивного замыкания отношения MM (рис. 4).

MAJOR_P# : P#   MINOR_P# : P#
-----------------------------
P1              P2
P1              P3
P2              P3
P2              P4
P3              P5
P4              P6
P1              P4
P1              P5
P1              P6
P2              P5
P2              P6

Рис. 4 Транзитивное замыкание MM

Назад | Содержание