Рис. 5.10.: Иерархическая рекурсия. Пример в табличной форме (см. 5.4.3)
Построения в данном примере укладываются с точностью до наименований в схему абстрактных построений в терминах «Узлы – КодУ – КодУ-Предок»: эти термины заменяются на «Подразделения
– МнемоП – МнемоП-Выше».
5.5. Сетевая рекурсия
5.5.1. Абстрактная схема
Напомним, что связь класса сущностей с самим собой называется рекурсивной (иногда такую связь называют «рыболовным крючком»). Рекурсивная связь типа многие-ко-многим (0 : : : 1 : 0 : : : 1) называется сетевой.
Сетевая рекурсия определяет связь типа предок/потомок между узлами сети. В сети предок может иметь много потомков и, наоборот, потомок может иметь много предков. Узел сети может выступать
в роли и предка, и потомка.
Для детализации (разрешения) связи многие-ко-многим (0 : : : 1 : 0 : : : 1) необходимо создать новый класс сущностей, содержащий ссылки на предка и потомка в связи предок/потомок. Такой класс в общем случае называется классом ассоциативных сущностей. Если класс ассоциативных сущностей не имеет собственных дополнительных атрибутов, то он называется именующим, так как каждый экземпляр класса «именует» связь предок/потомок путем ссылок на них.
Таким образом, первичный ключ класса сущностей, представляющих узлы сети, должен дважды мигрировать в класс ассоциативных сущностей. В этом классе мигрировавшие ключи в совокупности должны образовывать составной первичный ключ. Поэтому устанавливаемые связи будут неполностью идентифицирующими.
Атрибуты не могут появляться дважды в одном классе сущностей под одним и тем же именем. Поэтому атрибуты мигрировавшего ключа обязательно должны получить имя роли.
Построим абстрактные диаграммы (рис. 5.11, 5.12), реализующие сетевую рекурсию в реляционной модели, и приведем пример в табличной форме (рис. 5.13).
Рис. 5.11.: Сетевая рекурсия. Абстрактная презентационная диаграмма
Примечание. Здесь в силу симметрии связи указывается ее наименование, а не наименования ролей
Граф, описываемый приведенной схемой, является ориентированным (упоминание об этом для краткости терминологии мы будем опускать), и потому для обозначения связи между узлами используется термин «дуга».
Рис. 5.12.: Сетевая рекурсия. Абстрактная ключевая диаграмма
Примечание. При изображении родительских и дочерних классов удобно по возможности придерживаться следующего правила: изображать родительский класс слева, а дочерний справа, так как родительский класс не зависит от дочернего, а дочерний зависит от родительского
Рис. 5.13.: Сетевая рекурсия. Пример в табличной форме (см. рис. 5.12)
Примечание. Дуга, связывающая узлы, ориентирована от одного узла к другому, тогда как «ребро», связывающее узлы, ориентации не имеет
Как прийти к подобным построениям? Пусть, как и в случае иерархической рекурсии, есть некоторое множество узлов, определяемых кодом узла КодУ и некоторыми атрибутами:
Узлы(КодУ, Атрибуты) primary key(КодУ)
Подчеркнем, что пока это множество узлов, а не их сеть. Каждый узел в сети может иметь много предков и много потомков. Поэтому ясно, что расширение атрибутов узла ссылками на предков и (или) потомков невозможно. Но как можно образовать связь между узлами, то есть, как можно описать дугу, идущую из одного узла в другой? Очевидно, парой ссылок (КодУ-Из, КодУ-На). Из этих элементарных соображений и возникает класс ассоциативных (в данном случае именующих) сущностей Дуги:
Дуги(КодУ-Из, КодУ-На) primary key(КодУ-Из, КодУ-На)
foreign key(КодУ-Из) references Узлы(КодУ) foreign key(КодУ-На) references Узлы(КодУ)
Ключом здесь будет пара ссылок на узлы, так что узлы в одном направлении могут соединяться не более чем одной дугой.