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

Дерево записей, ключи и навигация по данным

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

Ключевые понятия иерархической модели

Чтобы уверенно ориентироваться в теме, начнём с базовых терминов. Именно на них держится всё дальнейшее описание модели.

Запись — это логически связанная совокупность атрибутов. Запись тоже имеет уникальное имя для обращения из кода, и её можно добавлять, изменять и удалять.

Экземпляр записи — это конкретная запись с конкретными значениями атрибутов.

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

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

Древовидная структура, корневая запись и полный ключ

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

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

Как же тогда однозначно опознать любую запись в дереве? Для этого служит полный ключ.

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

Пример: учёт в спортивном клубе

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

Чтобы автоматизировать учёт, понадобятся три типа записей:

• Спортсмен (код спортсмена, разряд, ФИО);
• Тренер (код тренера, разряд, ФИО);
• Соревнование (код соревнования, дата, название).

Отношения между записями повторяют связи между объектами реального мира. Связь между тренером и спортсменом — это «один-ко-многим»: у одного тренера много подопечных, но у каждого спортсмена тренер один. Поэтому в дереве записи «спортсмен» становятся дочерними по отношению к записи «тренер». Здесь модель работает безупречно.

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

Операции над данными: навигационный подход

Работать с иерархической базой можно с помощью нескольких основных операций:

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

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

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

Целостность связей

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

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

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

Примеры иерархических баз данных из повседневной жизни

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

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

Ещё один пример знаком любому пользователю Windows. Все сведения о состоянии операционной системы на конкретном компьютере хранятся в иерархической базе данных — реестре. Реестр можно и просмотреть, и отредактировать. Для этого достаточно в меню «Пуск» выбрать пункт «Выполнить», ввести название программы regedit — и перед вами откроется иерархическое дерево реестра.

Ограничения и актуальность модели сегодня

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

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

Иерархическая модель всё же не бесполезна. В специальных задачах, где присутствуют исключительно связи «один-ко-многим», она может оказаться вполне удачным выбором — как раз это и подтверждают файловая система и реестр Windows. Общее правило простое: если предметная область естественно ложится в дерево без пересечений, иерархическая модель работает хорошо; как только появляется потребность в отношениях «много-ко-многим», разумнее обратиться к реляционной модели.