История SQL. 2. Программист-навигатор

Начало: 1. Необходимая предыстория.

Сетевые базы данных интересно рассмотреть подробнее, потому что обычно они опускаются как пережиток былого. Вместе с иерархическими базами данных (например, Information Management System, разработанная IBM) cетевые БД принадлежат к классу навигационных баз данных.

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

Рассмотрим простую вариацию на тему bill of materials (ведомость материалов; кстати, довольно типичный пример использования ранних СУБД). Есть ассортимент деталей, каждая из которых принадлежит определенному классу. При этом некоторые детали могут собираться из других деталей. Традиционная ныне ER-диаграмма выглядит следующим образом:

А вот как аналогичная БД выглядит на диаграмме Бахмана:

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

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

Например, найдем первую запись о классе, входящую в набор всех классов:

FIND FIRST CLASS WITHIN ALL_CLASSES

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

GET

Набор устроен так, что можно перебирать (обычно в цикле) в определенном порядке дочерние записи, входящие в этот набор (FETCH — это FIND и сразу GET):

FETCH NEXT CLASS WITHIN ALL_CLASSES

От текущей записи можно по стрелке «провалиться» к дочерней:

FETCH NEXT PART WITHIN CLASS_PART

А можно от дочерней записи подняться к родительской:

FETCH OWNER WITHIN CLASS_PART

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

...
SET DONE TO FAILURE.
DISPLAY "Class number: >" NO ADVANCING.
ACCEPT CLASS_ID.
FETCH FIRST CLASS WITHIN ALL_CLASSES USING CLASS_ID
AT END
    DISPLAY "Class not found"
    SET DONE TO SUCCESS.
IF DONE IS FAILURE
    DISPLAY "Parts for class number ", CLASS_ID, ":".
PERFORM UNTIL DONE IS SUCCESS
    FETCH NEXT PART WITHIN CLASS_PART
    AT END
        SET DONE TO SUCCESS
    END-FIND
    IF DONE IS FAILURE
        DISPLAY PART_ID
    END-IF
END-PERFORM.
...

По каким-то не очень понятным соображениям сетевые СУБД не поддерживают наборы, в который один и тот же тип записей входит два раза. Поэтому для реализации иерархии деталей приходится использовать вспомогательную таблицу COMPONENT. Ее связывают с PART два набора: PART_USES определяет компоненты, из которых состоит деталь, а PART_USED_ON показывает деталь, соответствующую компоненте.

Приведу еще один фрагмент программы, выводящей список деталей, непосредственно используемых для сборки данной. В отличие от предыдущего, он написан в традиционной для того времени манере с оператором GO TO (против которой в 1968 году выступил Эдсгер Дейкстра в своей статье Go To Statement Considered Harmful).

...
    DISPLAY "Part number: >" NO ADVANCING.
    ACCEPT PART_ID.
    FETCH FIRST PART WITHIN ALL_PARTS USING PART_ID
    AT END
        DISPLAY "Part not found"
        GO TO ALL-DONE.
    DISPLAY "Parts used on part number ", PART_ID, ":".
COMPONENT-LOOP.    
    FIND NEXT COMPONENT WITHIN PART_USES
    AT END
        GO TO ALL-DONE.
    FETCH OWNER WITHIN PART_USED_ON RETAINING PART_USES.
    DISPLAY PART_ID.
    GO TO COMPONENT-LOOP.
ALL-DONE.
...

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

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

Подведем некоторые итоги:

• Данные в сетевой БД упорядочены: всегда есть первая запись и список следующих (а при желании и предыдущих).
• В БД хранятся не только данные, но и связи между ними (наборы). Наборы — существенный и обязательный объект, т. к. от записи к записи можно перемещаться, только если они объединены набором.
• Навигационная БД предполагает исключительно процедурный стиль программирования — разработчик сам определяет алгоритм получения интересующих его данных в рамках существующих в БД связей; изменятся связи — перестанут работать программы.

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

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

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

Продолжение следует: 3. Реляционная алгебра.

( Почитать и посмотреть )