Основные модели данных: иерархическая, сетевая, реляционная

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


Оглавление статьи[Показать]


 

Иерархическая модель

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

Продукт IMS (Information Management System) фирмы IBM, считающийся первой промышленной СУБД, реализует именно иерархическую модель.

Разработанная в 1966 году, эта СУБД до сих пор эксплуатируется на новейших мэйнфреймах серии Z, обеспечивая высокую производительность обработки порядка сотни тысяч транзакций в секунду.

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

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

Последний пункт важен: без использования XML-схемы (XML schema) или описания типов DTD (Data Type Definition) документ XML относится к неполно структурированным моделям данных, рассматриваемым в следующей главе.

Если взглянуть на структуру XML-документа, то иерархия элементов данных становится видна, что называется, невооружённым глазом.

 

<?xml version="1.0"?>
<sales>
     <orders>
          <order>
          <num>S01</num>
          <date>2014-02-20</date>
          <client>
               <name>Пирожки 000</name>
               <address>yn. Благодатная 235</address> <phone>322-223-322</phone>
          </client>
          <items>
               <product>
                     <name>MyKa</name>
                      <quantity>50</quantity>
                      <units>Kr</units>
                      <price>45</price>
              </product>
              <product>
                     <name>Дрожжи</name>
                     <quantity>300</quantity>
                     <units>r</units>
                     <price>80</price>
              </product>
         </items>
     </order>
     <order>
          <num>S02</num>
          <date>2014-02-21</date>
          <client>
               <name>Пирожки 000</name>
               <address>ул. Благодатная 235</address> <phone>322-223-322</phone>
         </client>
         <items>
              <product>
                   <name>MyKa</name>
                   <quantity>70</quantity>
                   <units>Kr</units>
                   <price>40</price>
              </product>
              <product>
                   <name>Дрожжи</name>
                   <quantity>500</quantity>
                   <units>r</units>
                   <price>75</price>
              </product>
          </items>/code>
     </order>
    </orders>
</sales>


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

 

Преимуществом такой структуры является возможность выполнения поисковых запросов без соединений. Например, чтобы выбрать все заказы клиента «Пирожки ООО», в которых он покупал муку в количестве более 50 кг, язык XPath[1] позволяет сделать в программе следующее:

 

var nodes = xmlDoc.SelectNodes(
     ”/sales/orders/order[client/name='Пирожки ООО’ and items/product[name = 'Мука'1/quantity > 50]”);

foreach(node in nodes) {
}

 

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

проектированию. Например, при добавлении оплат потребуется создавать новый тег описаний <payment> и включать их в состав заказов (orders). Однако, один платёж может покрывать более одного заказа и наоборот. Если же у клиента изменился адрес или телефон, то необходимо сделать соответствующие изменения во всех тегах <client>.

Частично, эта проблема решается введением ссылок на элементы XML- документа.

XML- документ

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

var nodes = xmlDoc.SelectNodes(
     ”/sales/orders/order[id client = /sales/clients/client[name = ’Пирожки 000’]/id and items/item[id product = /sales/products/product[name = ’MyKa’]/id and quantity > 50]]”);

foreach(node in nodes) {
}

На XML-документах небольшого размера с сотнями элементов подобные запросы выполняются быстро, но с ростом объёма данных неизбежно возникает необходимость их индексировать. В СУБД, поддерживающих XML хотя бы на уровне типа данных колонки таблицы,       имеется возможность такой индексации. Например, в MS SQL Server вначале строится так называемый первичный XML-индекс, затем несколько вторичных, для которых нужно указывать их специализацию: PATH для запросов типа проверки 

существования элементов, PROPERTY — для извлечения значений элементов и атрибутов или VALUE — для сквозного поиска элементов по значению. Без достаточного понимания таких особенностей физической организации данных хранилище XML начнёт испытывать проблемы с производительностью уже на небольших объёмах.

Описание модели данных: реляционной, иерархической и сетевой

Кроме XML и поддерживающих его СУБД существуют и другие реализации. Наиболее известная отечественная разработка — СУБД ИНЕС, являвшаяся фактически стандартом на советских ЭВМ серии ЕС. К сожалению, эволюция системы прервалась вместе с прекращением выпуска своих ЭВМ, до наших дней этот продукт не дожил.

К иерархическим также можно отнести СУБД на базе подхода MUMPS[2] (в СССР назывался «ДИАМС»), лежащий в основе линейки продуктов InterSystems: от выпущенной в 1970-х годах СУБД ISM (InterSystem M), через OpenM периода 1980-х к СУБД Cache с конца 1990-х и по наше время, реализующей современные подходы к организации иерархий.

Так, например, в MUMPS можно обращаться к значениям полей:

SET ^Автомобиль("Корпус","Дверь","Цвет")="Синий"

Здесь сущность «Автомобиль» представлена в виде дерева, одним из верхних узлов которого является элемент «Корпус», в состав которого, в свою очередь, входит «Дверь», имеющая пока ещё листовой узел «Цвет».

Иерархию несложно динамически расширять как в ширину:

SET ^Автомобиль ("Корпус","Крышка капота")=2

так и в глубину:

SET ^Автомобиль
   ("Корпус","Дверь","Цвет","Отражение")="Матовый"

Общий принцип распознавания лежащей в основе СУБД иерархической модели можно сформулировать так.

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

 

Иерархическая модель: плюсы и минусы

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

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

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

 

Сетевая модель

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

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

В 1975 году конференция CODASYL (Conference of Data System Languages) стандартизовала базовые понятия и формальный язык описания. Широко известной системой, основанной на сетевой модели данных, являлась СУБД IDMS (Integrated Database Management System), использовавшаяся на мэйнфреймах IBM. В настоящее время IDMS принадлежит компании Computer Associates, имеющей неформальный статус «лавки старьёвщика» в мире софтостроения: как правило, все купленные компанией продукты берутся на  сопровождение, но не развиваются, доживая до своего естественного конца.

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

СУБД Raima изначально использовалась, как встроенная с достаточно низкоуровневым API для языка Си. Постепенно, в систему был добавлен интерфейс доступа на SQL, а сама СУБД получила возможность работы в режиме клиент-сервер. По-прежнему Raima используется для транзакционных приложений как лёгкое (lightweight) кросс-платформенное решение.

Напротив, развитие СУБД Кронос пошло в сторону аналитической обработки. Это та область, где преимущества сетевой модели могут быть использованы полнее, а недостатки обойдены более просто. Для объяснений нам все же придётся кратко познакомиться с основными понятиями сетевой модели.

Термин запись соответствует аналогичному понятию структурного типа в традиционных языках программирования: record в Паскаль-подобных или struct в наследниках Си.

Набор данных служит для связывания двух типов записей отношением «один-ко-многим».

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

В СУБД Кронос также реализовано объединение наборов, позволяющее одной записи ссылаться на записи двух и более типов. Такая возможность очень удобна при моделировании. Например, если имеется тип записи «Адрес», который используется записями «Лица» и «Организации», то объединённый набор «Относится к лицу или организации» отобразит все возможные связи.

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

Поясню на упрощённом примере. Связь между двумя таблицами в реляционной модели осуществляется по значениям, соответственно, первичного и внешних ключей. Для выбранной строки подчинённой таблицы берётся значение внешнего ключа, которое затем ищется среди значений первичного ключа главной таблицы. Если таблица отсортирована в физическом порядке следования значений первичного ключа (так называемый кластерный ключ, подробнее см. «Физическая организация памяти»), то строка данных находится в той же области памяти, что и найденное значение. Если нет, то происходит дополнительный поиск связанной со значением первичного ключа строки по её идентификатору (row id).

Организация связей между типами записей в сетевой модели

Рис. 1. Организация связей между типами записей в сетевой модели

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

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

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

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

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

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

 

Сетевая модель: плюсы и минусы

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

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

О недостатках уже было упомянуто:

  • жёсткость задаваемых структур и сложность реструктуризации схем БД.
  • сложная структура управления памятью в транзакционных приложениях с частыми изменениями связей.

 

Реляционная модель

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

Как и положено доминирующей на протяжении десятков лет массово внедрённой парадигме, реляционная модель имеет свой основополагающий миф. Речь, конечно, идёт об известной работе Эдгара Кодда «Реляционная модель данных для больших совместно используемых банков данных», опубликованной в CACM[3] в 1970 году. «Да будет свет!» — сказал Кодд, и появился свет, и начали рождаться реляционные СУБД.

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

Кроме того, Кодд начал свои публикации раньше, в 1969 году, исследовательским отчётом «Derivability, Redundency, and Consistency of Relations Stored in Large Data Banks» в среде ограниченного круга подписчиков. В дальнейшем концепция эволюционировала, известный эксперт в области СУБД Майкл Стоунбрейкер отмечал, что «можно видеть четыре разных версии» модели:

  • версия 1, та самая упомянутая, составляющая основу отраслевого мифа, опубликована в статье в CACM в 1970 г.;

версия 2, определена в статье по поводу Тьюринговской премии в 1981 г.;

  • версия 3, доопределена «дюжиной Кодда» — двенадцатью правилами и оценочной системой в 1985 году;
  • версия 4, определена в опубликованной в 1990 году книге Кодда.

Из сказанного Стоунбрейкером становится понятным, что Кодд, как и положено учёному, в течение десятилетий продолжал исследования, пересматривая свои подходы и концепции. И полнота реализации теории в промышленных СУБД волновала её автора в меньшей степени, потому что «дюжина Кодда» до сих пор является актуальной для оценки соответствия, а последние стандарты SQL полностью не реализованы ни в одном продукте.

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

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

Что же представляет собой отношение с более формальной точки зрения? Обратимся к первоисточнику.

Термин отношение используется в его общепринятом математическом смысле. Для заданных множеств Si, S2, ...., Sn (не обязательно различных) R

является отношением на этих n множествах, если представляет собой множество кортежей степени n, у каждого из которых первый элемент взят из множества S1, второй — из множества S2 и т.д. Мы будем называть Sj j- тым доменом R. Говорят, что такое отношение R имеет степень n. Отношения степени 1 часто называют унарными, степени 2 — бинарными, степени 3 — тернарными и степени n — n-арными.

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

Отношение, как множество кортежей, заданных на доменах

Рис. 2. Отношение, как множество кортежей, заданных на доменах 

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

 

Реляционная модель: плюсы и минусы

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

  • теоретическая основа. Формально определяет базовые понятия модели, язык описания и операции над отношениями;
  • стандартизация. Стандарты SQL-NN (SQL-89, SQL-92, SQL-99 и т д.), имеющие несколько уровней полноты реализации, позволяют создавать приложения, переносимые между СУБД разных поставщиков;
  • полное разделение доступа к данным от способа их физической организации;
  • универсальность. Информационное моделирование сущностей реального мира в виде набора связанных таблиц является достаточно хорошим подходом в большинстве случаев;
  • простота манипуляции данными с точки зрения конечного пользователя;
  • SQL — развитый стандартизованный декларативный язык 4-го поколения.

Недостатки:

  • в общем случае, более низкое быстродействие по сравнению с сетевыми и иерархическими СУБД или другими подходами, обеспечивающими доступ к данным непосредственно на уровне их физической организации, например, индексированные файлы;
  • неполнота реализации стандартов SQL-NN, а также специфические языковые и процедурные расширения СУБД разных поставщиков, осложняющие переносимость приложений (так называемый vendor lock);
  • необходимость учёта некоторых особенностей модели на концептуальном уровне (ключи — идентификаторы сущностей), отсутствующая, например, в сетевой модели.

[1] XPath (от англ. XML Path Language) — язык запросов к элементам XML-документа.


[2]
 MUMPS — Massachusetts General Hospital Utility Multi-Programming System, позднее Multi-User Multi-Programming System, разработка датирована 1966 годом.

[3] CACM - Communications of the ACM, ежемесячный журнал сообщества Association for Computing Machinery (ACM), основанный в 1957 году.

Вас заинтересует / Intresting for you:

Альтернативные модели данных и...
Альтернативные модели данных и... 2868 просмотров Дэйзи ак-Макарова Sun, 09 Sep 2018, 10:39:19
Инструментальная диалоговая си...
Инструментальная диалоговая си... 479 просмотров Ирина Светлова Sun, 24 Mar 2019, 06:01:30
Модели данных и языки запросов
Модели данных и языки запросов 377 просмотров Дэн Wed, 06 Mar 2019, 16:11:35
Перенос корпоративных баз данн...
Перенос корпоративных баз данн... 352 просмотров Дэн Fri, 27 Sep 2019, 07:52:18


Vovan_ST аватар
Vovan_ST ответил в теме #9178 09 сен 2018 10:22
Познавательная статья. Существую ли какие-то гибридные модели данных на основе этих трех основных? Какуе модель данных используют Nosql СУБД? Они же хранят неструктурированные данные...