Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Базы данных: проектирование

Моделирование универсальных структур

Некоторые модели базы данных требуют использования сложноорганизованных структур, к которым относятся универсальные структуры: иерархические, квазиструктурироваиных данных, мультиязычные. Эти структуры существенно облегчают работу с некоторыми специфическими данными, по зачастую приводят к денормализации модели базы данных, снижая показатели эффективности ее обработки. Эти проблемы баз данных требуют от разработчика очень ответственного подхода к использованию соответствующих структур.

Моделирование иерархических структур

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

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

Иногда термин "иерархическая структура" определяют альтернативными формулировками, каждая из которых характеризует определенные особенности конструкции:

  • — конструкция данных, в которой экземпляры объектов связаны по принципу родитель-потомок;
  • - взаимосвязь экземпляров объектов, отражающая соподчинение одного экземпляра относительно другого;

взаимосвязь экземпляров объектов, отражающая структурное описание объекта;

— многоуровневая форма организации объектов со строгой соотнесенностью объектов нижнего уровня определенному объекту верхнего уровня.

При описании иерархий используется термин "степень вершин" количество ребер, связанных с исходной вершиной (узел). Также применяются дополнительные термины, описывающие отдельные составляющие иерархической структуры:

  • а) степень узла — количество деревьев, которое может быть построено на основании дочерних узлов (потомки);
  • б) корневой узел (корень) — узел дерева, не имеющий связей с родительскими узлами;
  • в) концевой узел (лист) — узел дерева со степенью 0, обозначающий, что на дочернем уровне не имеется никаких узлов;
  • г) узел ветвления — неконцевой узел, содержащий один или несколько дочерних узлов;
  • д) уровень узла — порядковый номер строки размещения узла, начиная отсчет от корневого узла, который обладает номером уровня "О".

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


  • 1. Дерево — иерархическая структура, предполагающая строго ориентированный граф, не содержащий пересечений.
  • 2. Сеть — иерархическая структура, позволяющая содержать пересечения ребер, обеспечивая связь между узлами типа М:М.

Основным представлением иерархии является "Дерево" (рис. 4.39) с реализацией ряда принципов его построения:

  • 1) каждый потомок связан только с одним родителем;
  • 2) на первом уровне представлен только один узел, от которого выстраиваются все остальные узлы;
  • 3) каждая структура, отходящая не от корневого узла, может быть представлена самостоятельной структурой иерархии.

image250

Рис. 4.39. Древовидное представление иерархической структуры


При построении иерархической структуры в теории графов выделяются следующие виды:

  • а) двоичное (бинарное) неориентированное дерево — каждый узел может иметь не более трех дочерних узлов (потомков);
  • б) двоичное (бинарное) ориентированное дерево — каждый узел может иметь не более двух дочерних узлов (потомков);
  • в) Л^-арнос неориентированное дерево — каждый узел может иметь не более N + 1 дочерних узлов (потомков);
  • г) ЛГ-арное ориентированное дерево — каждый узел может иметь не более N дочерних узлов (потомков).

Одним из примеров организации иерархической структуры вида "Дерево" является административная карта государства, например Германии, Франции, России и т.д. (рис. 4.40). При рассмотрении административного деления государства существует четко направленная вложенность более мелких регионов в более крупные.

На представленной административной карте Германии явно видна такая следующая вложенность.

  • 1. Германия
  • 1. Нижняя Саксония
  • 1. Бремен
  • 2. Ганновер
  • 3. ...

  • 2. image251Саксония-Анхальт
  • 1. Магдебург
  • 2. Лейпциг
  • 3. ...
  • 3. Северная Рейн-Вестфалия 1. ...
  • 4. Бранденбург
  • 1. Берлин
  • 2. Потсдам
  • 3. ...
  • 5. Бавария
  • 1. ...
  • 6. ...

Пшбу



НИДЕРЛАНДЫ,Фрлйоу Дортмунд
©X
Эрфурт,на-Маннс ВЕРАМИ,Потсдам,0 Лейн ції і




■ерхтеегялен

армшп-Партікнрхси

Рис. 4.40. Пример области применения иерархической структуры

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

Лучшим примером такой организации иерархии может быть представление структуры учебной дисциплины (рис. 4.41), где имеются уровни иерархической структуры (пример): Дисциплина, Раздел, Тема, Вопрос.

image252

Рис. 4.41. Пример иерархической структуры


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

Дополнительными примерами организации иерархической структуры вида "Дерево" могут являться: структура разделов прайс-листа, структура библиотеки, где но определенным правилам размещаются литературные произведения; структуры компьютерной и оргтехники, обеспечивая удобный доступ к отдельным элементам при организации обслуживания и ремонта; организационная структура предприятия; классификации различных объектов, обеспечивая их распределение в соответствии с определенными классификационными признаками.

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

Сетевая структура практически полностью идентична иерархической структуре вида "Дерево" (рис. 4.42), но позволяет хранить данные, используя возможность множества родителей для одного потомка. Данная организация достаточно громоздкая и не оптимальная, поскольку требует от разработчика достаточно большого программирования контроля работы с элементами иерархии.

Иерархическая структура вида "Сеть" создается на основе следующих принципов:

  • а) каждый узел может быть связан со множеством потомков и множеством родителей;
  • б) на корневом уровне может размещаться множество узлов.

image253

Рис. 4.42. Сетевое представление иерархической структуры


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

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

Если рассмотреть иерархическую структуры вида "Сеть" в виде стандартной иерархической структуры типа "Дерево", то видно, что хранение информации о структуре требует дублирования элементов (рис. 4.43). Причем количество продублированных элементов будет равно количеству необходимых связей с данным элементом.

image254

Рис. 4.43. Древовидное представление сетевой структуры


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

Представление иерархической структуры вида "Сеть" позволяет говорить об идентичности принципов построения и обработки по отношению к иерархической структуре "Дерево".

Учитывая уникальный характер рассматриваемой структуры, нельзя не упомянуть о еще одном важном факте, определяющем возможность при- мснения иерархической структуры, — все узлы должны иметь некоторое обобщение, т.е. данные, на которые ссылаются узлы структуры (это относится и к "Дереву", и к "Сети"), должны отражать некоторую общую суть предметной области. Например, "Область", "Край", "Округ" и т.д. могут быть обобщены единым термином "Административная единица".

Основным применением иерархической структуры вида "Сеть" является описание какого-либо процесса, предполагающего некоторую последовательность действий с возможными ветвлениями, возвратами и перескакиваниями (рис. 4.44). Для примера можно взять графы технологического процесса, например сборки какого-либо сложного изделия. Такой граф предполагает возможные различные пути выполнения операции сборки с выходом на единый конечный результат (изделие).

image255

Рис. 4.44. Пример представления сетевой структуры


Другим примером может являться взаимодействие категорий товаров в рамках прайс-листа. В данном случае различные подкатегории одних категорий могут являться подкатегориями для других подкатегорий. Если представить каждую подкатегорию в виде определенной направленной иерархии "Дерево", то задачи построения системы взаимодействия подкатегорий приведут к построению иерархии "Сеть".

Другими примерами иерархической структуры "Сеть" можно назвать:

  • а) структура подчиненности сотрудников организации на уровне должностей и организационной структуры предприятия;
  • б) структура взаимосвязи симптоматики болезней человека, где различные симптомы болезней, ввиду развития болезни, могут вызывать (порождать) новые симптомы побочных болезней;
  • в) структура учебной дисциплины, где разделы могут быть представлены во множестве различных дисциплин, формируя знания в рамках одной определенной компетенции.

В основном иерархические структуры основываются на следующих принципах (рис. 4.45).

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

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

image256

Рис. 4.45. Базовые принципы построения иерархической структуры


Говоря о расширении иерархической структуры, предполагают, что в структуре могут появиться новые уровни, или иерархия из вида "Дерево" преобразуется в вид "Сеть", что, естественно, приведет к полной реорганизации структуры данных. Примерами такой организации могут быть следующие элементы предметных областей:

  • а) таможенный классификатор типов грузов;
  • б) структурное деление специализаций в образовательных учреждениях (данный вариант иерархической структуры уникален для каждого учебного заведения, и, в отдельных случаях, с течением времени может изменяться);
  • в) организационная структура предприятия (данный вариант иерархической структуры уникален для каждой организации).

Для лучшего понимания особенностей построения иерархической структуры при классическом подходе немного отвлечемся от рассматриваемого примера и возьмем структуру, получаемую при организации описания учебной группы в образовательном учреждении[1] (рис. 4.46).

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

image257

Рис. 4.46. Классическая модель иерархической структуры


Поскольку вес уровни, кроме последнего, представлены стандартными (неизменными, наращиваемыми) классификаторами, то их можно представить в виде модели иерархической последовательности классификаторов. Такая организация иерархической структуры является наиболее простой и очевидной, когда моделируется база данных. Но данная структура неудобна и имеет ряд недостатков:

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

Теперь вернемся к рассматриваемой предметной области — электронный магазин. В этой предметной области есть две иерархические структуры: административное деление адреса организации или физического лица и структура прайс-листа в виде разделения категорий товаров. Для примера будем рассматривать структуру категорий прайс-листа (рис. 4.47).

image258

Рис. 4.47. Представление структуры прайс-листа в классическом варианте


Применяя классическую структуру иерархии, стоит задуматься о правильности описания атрибутов в сущностях, и как следствие, в таблицах базы данных. При этом необходимо помнить не только о типах хранимых данных, но и о возможности хранения значений NULL, возможных триггерных действиях. Конечно, большинство принимаемых решений по описанию атрибутов основывается на реальной предметной области. Особенно это касается функциональных атрибутов (табл. 4.20). Но для внешних ключей и связей между сущностями определяются правила, не зависящие от предметных областей и ориентированные на работу в СУБД.

Таблица 4.20

Описание свойств сущностей структуры

Сущность

NULL

Кардинальность

Триггер

Категория

11одкатегория 1-го уровня — 0:ЛГ *

11одкатегория 1 -го уровня

"ИДФ Категории" — да (если присутствует на всех категориях)

I [одкатегория 2-го уровня — 0:ЛГ '

Каскадное изменение Установка NULL при удалении

11одкатегория 2-го уровня

"ИДФ подкатегории 1-го уровня" — нет

Товары — 0:N

Каскадное изменение Запрет удаления

Товары

"ИДФ подкатегории 2-го уровня" — нет

Каскадное изменение Запрет удаления



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

Могут ли отсутствовать данные на родительских уровнях? — Если могут, то при описании связей рассматривается возможность существования записей в дочерних таблицах при одновременном отсутствии записей в родительских таблицах, что приводит к указанию возможности хранения значения NULL для внешних ключей рассматриваемых сущностей.

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

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

Предположим, что прайс-лист содержит три уровня иерархии и представляется строгим деревом. В этом случае модель будет представлена, как се смоделировали в процессе построения модели базы данных. Однако, потребность в размещении товаров не только в отношении последнего уровня иерархии, а также для любого уровня, приведет к необходимости в структуре сущности "Товары" указывать три внешних ключа (рис. 4.48).

image259

Рис. 4.48. Модель категоризации товаров


Такая организация модели требует указания для всех внешних ключей, кроме первого уровня, возможности храпения пустых значений. В том числе наблюдается дублирование связей. С одной стороны, всю структуру категоризации можно получить через последовательные связи подкатегорий, а с другой — через внешние ключи. К тому же наблюдается возможное нарушение целостности данных, которое может возникнуть при заполнении сущности "Товары". Состав значений внешних ключей категоризации товара может отличаться от структуры, формируемой связями между сущностями подкатегорий. Также есть аномалия обновления, не позволяющая добавить товары в разные категории.

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

  • - наличие "мусора" (пустые записи) в таблицах-классификаторах на соответствующих уровнях;
  • — необходимость дополнительной обработки получаемых при выборке данных с целью исключения пустых данных и связывания данных разных уровней.

Решение этих проблем кроется в разрыве связей между уровнями иерархической структуры и создании сущности-связки, содержащей все элементы взаимодействия, в данном случае, категорий и подкатегорий товаров. В этом случае функциональная сущность "Товар" будет связываться с сущность-связкой (рис. 4.49).

image260

Рис. 4.49. Модель иерархической структуры на основе сущности-связки


Как очевидно из представленной новой модели, фактической иерархической структуры между названными ранее уровнями не существует, что приводит к необходимости обеспечения структуры на уровне программного кода, существенно усложняя процессы обработки данных. Тем не менее, представленное решение снимает проблему дублирования данных и хранения "мусора" в таблицах-классификаторах.

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

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

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

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

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

Одной из ключевых особенностей является, в целях обеспечения уникальности записей в таблице-структуре, необходимость использовать уникальный индекс на базе комплекса полей — внешних ключей структуры. В конечном счете получается модель иерархической структуры, которая отвечает всем требованиям целостности структуры и обеспечения максимально эффективной обработки данных.

Описывая подобную структуру, необходимо дополнить таблицу характеристик колонкой описания индексов (табл. 4.21). Но, зная, что в СУБД на первичные ключи кластерные уникальные индексы создаются автоматически, рассматривать их не будем.

Таблица 4.21

Описание свойств структуры на основе сущности-связки

Сущность

NULL

Кардинальность

Триггер

Индекс

Категория

Структура — (0,1 ):N

Подкатегория 1-го уровня

Структура — 1 :ЛГ




Сущность

NULL

Кардинальность

Триггер

Индекс

Подкатегория 2-го уровня

Структура — 1 :ЛГ

Структура

Внешние ключи — да/ нет (в зависимости от условий предметной области)

Категория — 0:ЛГ 11одкатегория 1 -го уровня —

  • 0:ЛГ
  • 11одкатегория 2-го уровня —
  • 0:ЛГ

Товары — (0,1 ):N

Категория,

подкатегория

  • 1- го уровня, подкатегория
  • 2- го уровня — каскадное изменение При удалении — в зависимости

от условий

предметной

области

Составной:

  • — категория
  • — подкатегория
  • 1- го уровня
  • — подкатегория
  • 2- го уровня

Товары

"ИДФ структуры" — нет

Структура — 1 :jV

Каскадное изменение Запрет удаления


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

В случае с функциональной сущностью, которая содержит внешний ключ от сущности-структуры, решение о возможности существования значения NULL у внешнего ключа основывается на решении вопроса возможности описания объекта, представляемого сущностью, вне принятой структуры.

Необходимо обратить внимание на тот факт, что триггерное действие в соответствии с условиями возможности хранения значения NULL может быть различным — установление NULL, каскадное удаление (ограничивается условиями триггера по связи "Структура" — "Функциональная сущность"), запрет удаления.

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

Для такой организации иерархической структуры используется родительскодочерняя модель структуры (модель с двойной связью), где все элементы представляются линейным классификатором, а сама структура


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

Рассматривая классификатор элементов, нужно определить основной фактор их использования — уникальность существования каждого элемента в иерархии, обобщенность описания каждого элемента, специфичность элементов на каждом узле иерархии. В соответствии с правилами, определенными по данному фактору, иерархия может быть представлена несколькими вариантами (рис. 4.50).

image261

Рис. 4.50. Модель иерархической структуры с двойной связью


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

В случае уникальности описания отдельных элементов иерархической структуры в зависимости от их размещения в структуре необходимо использовать несколько скорректированную модель (рис. 4.51), где сущность описания будет связываться с сущностью-структурой.

image262

Рис. 4.51. Модель иерархической структуры с описанием отдельного

элемента структуры


Наряду с особенностями построения сущностей возникает необходимость использовать индекс на совокупность внешних ключей (родительский и дочерний). С одной стороны, такой индекс полезен для увеличения скорости обработки таблицы иерархической структуры. С другой стороны, индекс дает возможность определить дополнительное правило к обработке структуры невозможность хранения одинаковых комбинаций внешних ключей (рис. 4.52).

image263

Рис. 4.52. Модель иерархической структуры с добавлением уровня

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

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

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

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

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

может быть связана с сущностью-структурой ("Структура") либо с сущностью-классификатором ("Элементы структуры"). В соответствии с принятым решением рассматриваются различные варианты описания кардинальности связей и возможности хранения пустых значений.

Независимо от выбранного принципа построения иерархии в данной модели все решения по описанным здесь характеристикам принимаются на основе анализа предметной области. Например, при учете структуры компьютерного оборудования и его характеристик возможны варианты, когда планируется приобретение оборудования с определенными характеристиками, но фактически в иерархию до момента приобретения соответствующий узел не будет добавлен. В результате данная ситуация может привести к необходимости хранить описания, не привязанные к узлам иерархии, с последующей увязкой с добавленным узлом(-ами). В этом случае для атрибута "ИДФ связи" в сущности "Описание узлов" возможно хранение пустых значений (NULL), а также установление кардинальности 0:N или 0:1.

В отношении индексов стоит также проанализировать предметную область и ответить на вопрос: возможно ли хранение связки "Родитель" — "Потомок" несколько раз с одинаковыми значениями? Если невозможно, то индекс будет составной и уникальный. Если же такая ситуация возможна, то индекс будет только составной (рис. 4.53).

image264

Рис. 4.53. Использование уровня в качестве обычного атрибута


Как очевидно из представленных ранее вариантов модели иерархической структуры, основными сущностями являются: сущность-классификатор, где описываются характеристики элементов иерархии, и сущность- структура, где описывается непосредственная организация иерархической структуры. Данный подход позволяет существенно сократить дублирование данных и отделить сами элементы иерархии от их описаний и структуры иерархии. Естественно, что организация иерархии через сущность с числовыми атрибутами позволяет совместно с применением технологий индексирования максимально повысить скорость обработки всей структура.

При этом, в модели предполагается наличие двух связей между сущностями, одна из которых указывает на родительский элемент, а другая — па дочерний. Этот метод организации связи потребует, при выполнении выборок, создавать дубликаты (клоны) таблицы-классификатора. Дополнительно возникает серьезная проблема с возможностями обработки иерархии, которая заключается в том, что при получении списка всех дочерних элементов до самого нижнего уровня требуется сложная обработка на уровне программного кода приложения. Решением данной проблемы является добавление еще одного атрибута — "Уровня вложенности".


Описание характеристик модели е двойной связью

Сущность

NULL

Кардинальность

Триггер

Индекс

Элементы структуры

Иерархия (Родитель) — 0:Ы Иерархия (Потомок) — 0:^ Описание узлов — 0:ЛГ

Уровни иерархии

-

Иерархия — 0:ДГ

-

-

Структура

Родитель — Да (для первого уровня иерархии)

Потомок — Нет

Элементы структуры (Родитель) — 1:ДГ

Элементы структуры (Потомок) — 1:М

Уровни иерархии — 1:ЛГ Описание — узлов — 0:ЛГ

Каскадное изменение по связи с элементами структуры

Каскадное удаление по связи с элементами структуры

Запрет изменения по связи с уровнями иерархии

Запрет удаления по связи с уровнями иерархии

Составной:

  • — родитель
  • — потомок

Описание узлов

ИДФ связи — Пет

Иерархия — 1:М

Каскадное изменение Каскадное удаление

ИДФ элемента — Нет

Элементы структуры — 1:ЛГ

Каскадное изменение Каскадное удалегIне




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

Этот атрибут дает возможность при выполнении запроса выборки совместно с атрибутом "Уровень иерархии" отсортировать элементы иерархии в нужной последовательности, что существенно сократит обработку на уровне приложения.

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

 
Рис. 4.54. Модель структуры с одной рекурсивной связью

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



При такой организации элементы иерархического объекта могут быть представлены в линейном классификаторе, а с сущностью-структурой организовывается одна связь, обозначающая идентификацию элемента на уровне соответствующей связи родитель-потомок.

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

При рассмотрении данной модели иерархической структуры сложность в описании характеристик составляет рекурсивная связь (табл. 4.23). Ее наличие требует от СУБД использования дополнительных механизмов (клонирование), чтобы обеспечить целостность данных, что, естественно, снижает скорость обработки хранимых данных.

В описании характеристик стоит отметить особенность хранения пустого значения для атрибута "Родитель", который является внешним ключом. Принцип храпения данных в подобной модели предполагает, что используется связь между двумя атрибутами внутри одной сущности (рекурсивная связь) и некоторые СУБД не предполагают возможности хранения пустого значения для внешнего ключа. К тому же в целях единообразия обработки данных по атрибуту "Родительский" в качестве родителя самого верхнего уровня закладывается пустая запись с незначащими значениями.

Таблица 4.23

Описание свойств структуры с рекурсивной связью

Сущ

ность

NULL

Карди нал ьность

Триггер

Индекс

Эле

менты

струк

туры

Иерархия — 0:ЛГ

Струк

тура

Элемент структуры — Нет

Элемент структуры — 1:1

Каскадное изменение Каскадное удаление (по условиям предметной области)

По необходимости

Родительский — Да (Нет- при наличии базовой записи)

Родительский — 0:ЛГ

Каскадное изменение Запрет удаления Собственный триггер по операции удаления



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

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

image266

Рис. 4.55. Модель структуры с двойной рекурсивной связью


Представленная ранее модель обладает одним очень существенным недостатком — база данных, построенная по данной модели, не позволит без дополнительного программирования получить иерархическую структуру размерности больше одного уровня. Этот недостаток может быть исправлен с помощью построения структуры, содержащей две рекурсивные связи. Конечно, данная организация хранения иерархических данных приводит к большой избыточности данных, но это компенсируется гибкостью получения иерархической структуры из базы данных.

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

Представленная модель иерархии позволяет хранить стандартную организацию дерева (с одной рекурсивной связью) и "продвинутую" модель (с организацией всех связей, включая сетевую организацию иерархии). При этом количество уровней вложенности является неограниченным. В случае использования классификатора уровней их количество ограничивается размером классификатора. Если классификатор уровней не использовать, то количество уровней в иерархии ограничивается только возможностями отображения дерева в клиентском приложении.

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

Чтобы избежать этой проблемы, в сущности-структуре используется атрибут "Номер вложенности", обозначающий количество дуг, которое необходимо использовать для достижения элемента-потомка, отталкиваясь от элемента-родителя. В результате такой операции модель иерархии приобретает двойное свойство сортировки и группировки но атрибутам "Номер уровня" и "Номер вложенности", существующих независимо друг от друга, но одновременно дополняющих друг друга при выполнении выборки иерархической структуры.

Представленная модель иерархии обладает дополнительным свойством обеспечения целостности данных: невозможность выполнить операцию удаления родительских узлов без удаления всех дочерних узлов. Данное свойство в других моделях иерархии не могло быть обеспечено ввиду того, что их реализация основывалась на хранении только одного уровня вложенности потомка относительно родителя. Создавая избыточность данных и обеспечивая двойную рекурсивную связь, мы проектируем наиболее развитую иерархическую структуру (табл. 4.24).

При работе с данной организацией иерархической структуры требуется достаточно ответственно подойти к реализации двойной рекурсивной связи. Наличие обеих связей большинством СУБД воспринимается как запрет на удаление элементов, что может привести к сложностям при выполнении данной операции. К тому же многие СУБД производят удаление записей без учета их вложенности в рамках одной сущности, поэтому зачастую при выполнении удаления возникает ошибка удаления, которая может быть исправлена снижением уровня контроля целостности данных (убрать рекурсивные связи, оставив атрибуты) либо написанием собственных триггерных операций.

В данной организации модели иерархии стоит особо выделить атрибут "Потомок", одним из свойств которого является невозможность хранения пустого значения (принцип хранения данных — однозначное соответствие родителя и потомка), но для модели допускается такой вариант. Обусловлено это тем, что для обеспечения целостности данных предполагается связь родитель-потомок элемента самого с собой. Для того, чтобы избежать проблем при добавлении данных, необходимо представить триггерное действие по добавлению данных, которое, при отсутствии явно указанного потомка, внесет значение первичного ключа в колонку "Потомок".

Таблица 4.24

Описание свойств структуры с двойной рекурсивной связью

Сущность

NULL

Кардинальность

Триггер

Индекс

Эле

Менты структуры

Структура — 0:ЛГ

Структура

Элементы структуры — Нет

Элементы структуры — 1:1

Каскадное изменение Каскадное удаление (по условиям предметной области)

Родительский — Да (Нет — при наличии базовой записи)

Родительский — 0 :ЛГ

Каскадное изменение Каскадное удаление

Уникальный по комплексу атрибутов (Родительский; Дочерний)

Дочерний — Да

Дочерний — 1:ЛГ

Каскадное изменение Запрет удаления Триггер на добавление по установке значения

Триггер на удаление



Также необходимо, чтобы по сцепке "Родитель-Потомок" существовал уникальный индекс, поскольку контроль значений на уровне ключей в данной модели не предусматривается. Наличие такого индекса даст возможность хранить правильно организованную (без дублирования) иерархию. К тому же может возникнуть необходимость создания уникального индекса в сцепке внешних ключей по рекурсивным связям с внешними ключами на функциональную сущность (элементы).

Одной из реализаций базы данных с иерархической структурой является использование типа XML (рис. 4.56), который преследует своей целью представить комплекс сведений в виде дерева, направленного на представление в интернет-приложении с возможностью выполнения асинхронного процесса обработки данных. Этот вариант представления данных удобен

для работы пользователя с уеЬ-ресурсами, но совершенно неприемлем с точки зрения применимости для управления данными, поскольку требует создания дублируемости и избыточности данных.

 
Рис. 4.56. Пример представления адреса

Схематично ХМЬ-схема данных может быть представлена в достаточно привычном для разработчика баз данных виде, где будут описаны взаимосвязи между объектами данных и характеристики каждого объекта. Однако если реализовать эту модель в виде кода разметки ХМБ-страиицы, то станет видно, что часть информации пропадает или дублируется, а программное приложение, обрабатывающее такую структуру, должно быть достаточно сильно ориентировано на рассматриваемую структуру данных, поскольку механизма метаданных в СУБД для ХМБ-схемы не предусматривается.



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

Использование специализированного типа данных в структуре базы данных даст возможность интегрировать XML-разметку в структуру базы данных, а наличие специализированного языка обработки XML-данных — сделать выборку в реляционной базе данных но условиям к данным XML- формата (рис. 4.57). Это позволяет при выборке данных сразу получить необходимую разметку интернет-страницы в необходимом оформлении и не потребует какого-либо дополнительного программирования обработки выборки из базы данных.

Тем не менее, подход с использованием формата XML имеет некоторые недостатки, одним из которых является то, что данные хранятся в текстовом
виде и тип данных "XML" является потомком тина данных "Text", нс предполагающего наличия развитого механизма обработки. К тому же для обработки данных, хранимых в формате XML, необходимо использовать специальные расширения или специфические функции языков в СУБД. Все это накладывает особые ограничения на использование данного подхода.

image268

Рис. 4.57. Пример сущности с атрибутом типа XML


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

В качестве примера можно взять данные клиента (табл. 4.25), где адрес будет представляться иерархической структурой, при предположении следующей связки: "Страна" — "Регион" — "Город" — "Улица" — "Дом/Корпус" — "Квартира". Как очевидно из представленной таблицы, для каждого клиента указывается собственный набор ХМL-данных, описывающих место проживания человека. В данном примере проиллюстрирована ситуация, когда ряд данных (страна, регион, город и т.д.) может быть продублирован своими значениями, что может привести к существенным ограничениям целостности данных и не позволит качественно провести обработку и выборку необходимых данных.

Учитывая особенность того, что пользователь может ввести, например, название страны различными вариантами: "Россия" или "РОССИЯ", что рассматривается как различные экземпляры, выбрать всех людей, проживающих в стране "Россия", будет невозможно, поскольку проживающие в стране "РОССИЯ" могу не попасть в результат выборки. Эта проблема решается в реляционных базах данных, но на уровне XML-данных такая проблема неразрешима.

Таблица 4.25

Примеры представления данных адреса в формате XML

№ п/п

Клиент

Адрес

1

Иванов И. И.

<Country id=“PocciiH”>

<Province id=“Центральный округ”>

<City id=“MocKBa”>

<Street>Рязанский npocneicr</Street> <Home>91 </Home>

< App>68< /App>

</City>

</Province>

</Country>



Окончание табл. 4.25

№ п/п

Клиент

Адрес

2

ООО "Электроника"

<Country id=“Poccnn”>

<Province id=uЦентральный округ”>

<City id=“MocKBa”>

<Street>Рязанский npocncKT</Strcct> <Hoine>64</Home>

< App> 12</App>

</City>

</Province>

</Country>

3

Сидоров С. С.

-



Тем не менее, в случае необходимости представления некоторой информации в виде XML-формата на страницах интернет-приложения и реализации заполнения XML-колонки на базе классификаторов реляционной базы данных, учитывая создание дублированности данных, можно говорить о применимости данной технологии организации иерархической взаимосвязи между элементами данных.

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

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

В результате нормализации отношения (сущности) "Клиент", где присутствовал добавленный но результатам анализа предметной области атрибут "Адрес доставки" (рис. 4.58), между клиентом и адресом формируется связь многие — ко — многим, нормализованная в отдельную сущность- связку, связанную с заказами, которые имеют функциональную зависимость с клиентом. При, казалось бы, избыточном наборе связей в этой модели говорить о какой-либо связи, что она лишняя, будет неверным. Связь между сущностью-связкой "Адрес доставки" и сущностью "Заказы" необходима, чтобы зафиксировать единственный выбор клиента адреса доставки конкретного заказа. В то же время, чтобы иметь возможность видеть перечень адресов, которые клиент определил в качестве допустимых для доставки заказов, необходима сущность-связка "Адреса доставки" с установлением соответствующих связей.

Ранее было сказано, что адрес должен формироваться из классификаторов, к которым можно отнести: "Страна", "Регион", "Город", "Улица".

Возможно, целесообразно еще добавление классификатора "Тип улицы", но это может усложнить процесс формирования адреса, поэтому будем считать, что тип улицы будет размещен в классификаторе улиц, включенном в название улицы. Данные но номерам дома, корпуса, квартиры/офиса являются числовыми с неопределенным набором значений, что говорит в пользу их использования в качестве атрибутов простых типов.

image269

Рис. 4.58. Нормализованное отношение, содержащее адрес доставки


Рассматривая связку "Страна" — "Регион" — "Город" — "Улица", можно сказать, что первые три элемента являются структурными компонентами административного деления государства и обладают идентичным набором атрибутов. Это приводит к мысли о том, что к тому же, учитывая их иерархическую связь, их нужно представить иерархической структурой. Классификатор "Улица", с одной стороны, ввиду его отличного смыслового наполнения относительно других рассматриваемых классификаторов адреса, нецелесообразно включать в состав формируемой иерархической структуры, но, с другой стороны, функциональная зависимость улиц только от уровня "Город" требует отслеживания функциональной зависимости от листового элемента иерархической структуры. В связи с этими противоречиями можно использовать два варианта представления классификатора "Улицы", состоящего из трех атрибутов — "Почтовый индекс", "Тип улицы" и "Название улицы".

Использование классификатора "Улицы" в отдельной сущности

(рис. 4.59). Этот вариант наиболее логичный, предполагающий отделение смыслово несвязанного классификатора в отдельную сущность.

Разделив адрес на структурные элементы, улицу, представляемую классификатором, связанным с городом, но правилам нормализации выделяют в отдельную сущность. Между ней и исходной сущностью устанавливается идентифицирующая связь один — ко — многим.

image270

Рис. 4.59. Выделение улицы в отдельную сущность


Использование иерархического представления. При использовании второго варианта применения классификатора "Улицы" возможно его добавление к иерархической структуре, связывающей страну, регион и город (рис. 4.60). Поскольку количество уровней иерархической структуры не фиксированное (например, для России вложенность административного деления регионов отличается от размера вложенности административного деления Германии), то целесообразно использовать модель иерархической структуры с рекурсивной связью. Учитывая, что в обработке будет необходимо регулярно получать сведения по всей структуре иерархии от листового элемента до всех его родительских компонентов, а также делать выборки, не включающие определенные уровни (например, последний уровень, относящийся к классификатору улиц), для организации модели структуры стоит использовать двойную рекурсивную связь.

image271

Рис. 4.60. Модель иерархического представления адреса


В результате всех процедур нормализации и построения иерархической структуры в модели представления адреса введена сущность "Структура административного деления", предполагающая уровень детализации до улицы. Важно отметить один элемент, который отличается от всех ранее представленных вариантов использования. Это ключевой элемент "ИДФ структуры элемента (родительский)". Данный атрибут, представляясь внешним ключом, обладает свойством возможности хранения пустого значения "NULL". При том, что внешние ключи, по умолчанию, не должны разрешать хранение пустых значений, в данном случае это обосновано. Одной из реализаций иерархических структур является возможность ссылки на пустой экземпляр структуры. Сделать это можно с помощью установки свойства возможности использования пустого значения для внешнего ключа, определяющего родительский элемент (узел).

Также в модели была выделена отдельная сущность для идентификации уровней. Поскольку разные уровни иерархии могут представляться одинаковым названием уровня (например, регион) или элементы, находящиеся на одном уровне иерархии, могут иметь различные наименования уровней (например, город, поселок и т.д.), то выделение отдельного классификатора "Типы уровней административного деления" позволяет определить соответствующий тип. Однако такое выделение больше полезно для корректной организации интерфейса пользователя, но, тем не менее, иногда может применяться для отчетов, где нужно корректно назвать соответствующий элемент иерархической структуры.

Важно еще обратить внимание на сущность "Улицы". Оттуда был убран атрибут "Название улицы", поскольку при включении этого элемента в иерархическую структуру название улицы будет, как и другие элементы структуры, храниться в линейном классификаторе "Элементы административного деления". Сама сущность все равно необходима в связи с тем, что отдельные атрибуты ("Почтовый индекс" и "Тип улицы") имеют отношение только к листовому элементу дерева, т.е. к улицам. Внесение улицы в иерархическую структуру позволило избавиться от необходимости постоянного контроля закрепления улицы за городом, а не каким-либо другим элементом структуры.

  • [1] Выбор другой предметной области для данного примера обусловлен более явным представлением особенностей организации структуры. При дальнейшем рассмотрении мы вернемся к исходной предметной обла
 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы