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

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

Алгебра 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

|

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

---

---