Развитие логических моделей данных

А.Е.Васильев

От редактора раздела

Будучи не со всем согласен в этой статье, я написал заметку "Не сравнивайте несравнимое!", которую рекомендую прочитать после прочтения основной статьи.

Сергей Кузнецов

Классификация логических моделей данных

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

Различают четыре логические модели данных:

• иерархические;
• сетевые;
• реляционные;
• многомерные.

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

• навигационные модели данных с адресными указателями на данные;

ссылочная модель данных с именами (идентификаторами) данных.

К навигационным моделям данных относятся иерархическая, сетевая и многомерная логические модели, к ссылочной модели данных – реляционная модель.

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

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

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

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

В 1970 году Э.Ф.Кодд теоретически обосновал, что более универсальным решением в области баз данных является ссылочная модель: "Реляционная модель предоставляет средства описания данных на основе только их естественной структуры, т.е. без потребности введения какой-либо дополнительной структуры для целей машинного представления" [1].

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

Однако теоретическая модель Э.Ф.Кодда обладает явной неполнотой – в связи с отсутствием в её составе какого-либо механизма поиска данных для целей последующего чтения, за исключением механизма, основанного на полном переборе данных в базе. При достаточно большом (или малом, с точки зрения современного состояния) количестве данных в реляционную базу в обязательном порядке включается тот или иной механизм поиска, т.е. дополнительная структура, отсутствие потребности в которой было декларировано Э.Ф.Коддом.

Эффективность ссылочной модели данных

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

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

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

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

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

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

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

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

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

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

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

Эффективность навигационной модели данных

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

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

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

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

K произв. = M ссыл. / M навиг. + N ссыл. / N навиг.,

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

Учитывая приведенные выше оценки, можно видеть, что разрыв в производительности ссылочной и реляционной баз данных на этапах записи и чтения данных может составить от 12 до 15 раз.

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

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

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

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

Конечная цель развития логических моделей данных

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

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

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

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

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

Единственный недостаток классической многомерной модели данных – "взрывной" рост ячеек многомерного пространства при увеличении числа измерений и количества координат в составе измерений. Объем многомерного пространства при этом возрастает по экспоненте. Количество ячеек, заполненных NULL-значениями, на порядки превышает количество ячеек, заполненных реальными данными. С целью сжатия многомерного пространства используется прием, реализованный в навигационной модели данных – адресные указатели, связывающие в том или ином порядке ячейки со значимыми данными. Сжатое многомерное пространство, в свою очередь, требует замены механизма поиска, основанного на однократных перемещениях вдоль осей измерений, на механизм поиска, основанный на иерархических структурах.

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

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

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

Литература:

1. E.F. Codd. A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, Volume 13, Number 6, June, 1970.
Перевод на русский язык: Е.Ф. Кодд. Реляционная модель данных для больших совместно используемых банков данных.

2. С.Д. Кузнецов. Методы сортировки и поиска. ИСП РАН, Центр информационных технологий.

---

См. заметку С. Кузнецова "Не сравнивайте несравнимое!"