Rambler's Top100

(c)2009-2017 openinfotech.ru

СУБД HyTech

Пресса о СУБД


Выдержки из книги
"Теоретические основы проектирования оптимальных структур распределенных баз данных."
В.В.Кульба, С.С.Ковалевский, С.А.Косяченко, В.О.Сиротюк.
Российская Академия Наук. Синтег. Москва - 1999.

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

В настоящее время выделяются три основных группы методов доступа к БД пользователей (табл.7.3.1). Анализ показывает, что одной из причин низкой реактивности наиболее распространенных СУБД является физическая организация структур данных с использованием В-деревьев (В+, В*, Trie и т.д.).

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

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

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

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

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

Альтернативным методом организации данных являются инвертированные списки. Центральным элементом при данной организации является ассоциатор, связывающий значения ключей со списками внутрисистемных номеров записи информационного файла. При таком подходе для каждого значения ключа всегда известно число записей-целей ему соответствующих. При этом процедура преобразования исходной информации состоит в формировании матрицы всех записей по каждому из полей записей БД. Каждая запись сопровождается порядковым номером соответствующего поля в записи БД. Для каждого поля формируется список, представляющий собой матрицу из i,j элементов, каждый из которых является парой "значение/внутрисистемный номер". Здесь "значение" - значение заданного поля, выбранное из записи под номером "внутрисистемный номер". Очевидно, что никакие две записи в такой таблице не могут иметь одинаковый внутрисистемный номер.

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

    - число столбцов J по возможности близко к числу рядов I, значение элемента V(i,j) в любом столбце меньше либо равно значению элемента V(i+1,j) в этом столбце,

    - если значение элемента V(i,j) оказалось равно значению элемента V(i+1,j), то внутрисистемный номер элемента V(i,j) строго меньше внутрисистемного элемента V(i+1,j),

    - значение последнего элемента любого j-го столбца V(i,j) меньше либо равно значению первого элемента (j+1) - го столбца V(1,j+1),

    - если значение m-го элемента j-го столбца оказалось равным значению 1-го элемента (j+1)-го столбца, то внутрисистемный номер элемента V(m,j) строго меньше внутрисистемного номера элемента V(1,j+1).

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

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

Для анализа эффективности различных методов доступа введем необходимые обозначения:

    NR- длина последовательного файла в блоках,

    EBF- коэффициент полезного блокирования,

    NDLK-[NR/EBF]- число блоков в файле,

    SBA- время доступа к блоку при последовательном доступе,

    RBA- время доступа к блоку при произвольном доступе,

    NM- число записей в БД,

    NTR- число записей-целей запроса,

    K- коэффициент блокирования.

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

где ri= R(поиск в индексе1) + R (поиск в индексе2 ) + R ( поиск в списке указателей доступа ),

индекс1 - индекс типов элемента,

индекс2 - индекс значения элементов.

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

где i - общее число атомарных запросов, а

Если воспользоваться таким достоинством инвертированных списков как быстрое исполнение логического отрицания (в В-деревьях для этого потребуется совершить обход дерева в противоположном направлении), то в случае, если ri >= NM/2 можно легко оптимизировать алгоритм обработки запросов. При этом число обращений к БД можно определить следующим образом:

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

Таблица 7.3.1. Верхняя и нижняя оценки времени поиска для B-деревьев
Тип приложения Время поиска (k - коэффициент блокирования)
  Нижняя оценка Верхняя оценка
Получить уникальную 2 * RBA RBA*Logk+1((NR+1)/2)
Получить все NR(1 + 1/(2k))RBA NR(1+1/k)RBA

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

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

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

Рассмотрим выполнение операции Join по новой технологии (на примере двух таблиц) - косвенный метод.

Связь между таблицами, как известно, осуществляется через значение связующего ключа. Для соединения двух таблиц из ассоциатора вырезаются значения связующего ключа с адресом записей-целей, содержащей эти значения в обеих таблицах. Суть операции соединения заключается в следующем: получить все связи "адрес записи-цели таблицы1 <-> адрес записи-цели таблицы2". Таким образом, результатом операции Join будут являться список всех пар "адрес-адрес". Это позволяет добиться следующих результатов:

    - поиск ведется в ассоциаторе без обращения к таблицам,

    - время поиска не зависит от длин записей и длины связующих ключей,

    - время поиска практически не зависит от числа записей-целей и от числа записей в обеих таблицах БД,

    - результатом поиска являются: пары связок "адрес-адрес" и их число.

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

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

Имея такую возможность мы приходим к выводу о том, что в стандарте ANSI-89 основной конструкцией языка является конструкция: «Select… From… Where».

Из описанной выше технологии становится очевидным, что выполнение SQL запроса косвенным методом "делает" первое ключевое слово «Select…» - "избыточным" и поэтому в реализации SQL HyTech сделано значительное "смягчение" и необходимой является только конструкция «From… Where».

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

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

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

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

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

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

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

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

После того как размеры дифференциального файла станут значительными (не рекомендуется чтобы размеры ДФ превышали 25-40% от размеров БД) администратором вносятся все изменения в базу в удобный момент (в пакетном режиме).

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

СУБД HyTech - это совокупность программных средств, предназначенных для создания, ведения и использования реляционных баз данных большого и сверхбольшого объемов. СУБД HyTech версии 3.0 реализована для архитектуры клиент-сервер и функционирует на нескольких платформах (Windows NT 4.x, Novell 4.x, Solaris 2.x).

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

СУБД HyTech версии 3.0 состоит из двух основных частей: собственно SQL сервера и клиентской части. Сервер является частью соответствующей ОС и предназначен для ведения реляционных баз данных и обслуживания приложений клиентов. Приложения могут выполняться как на рабочих станциях, так и машине самого SQL сервера. Для связи клиентов с сервером поддерживаются несколько видов протоколов (поименованные каналы, стек TCP/IP, IPX/SPX).

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

Основным языком взаимодействия клиентской части с SQL сервером является язык SQL, дополненный процедурным расширением. SQL СУБД HyTech версии 3.0 удовлетворяет Entry уровню рабочего варианта стандарта SQL-93. Обеспечивается поддержка национальных алфавитов, статического и динамического контроля вводимых данных, ссылочной целостности, хранимых процедур и триггеров. Для обмена данными с другими СУБД и приложениями предлагается использовать ODBC драйвер.

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

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

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

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

Рисунок 7.3.1. Структура программного обеспечения SQL сервера

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

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

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

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

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

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

В-пятых, резко повышается уровень сохранности данных и устойчивости СУБД к отказам, так как потери данных при возможных сбоях питания и ПО могут затронуть только журнал изменений.

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

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

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

Во-первых, увеличивается время поиска, осуществляемого в два этапа:

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

    - затем полученное множество записей обновляется данными журнала изменений.

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

Во-вторых, недостатком дифференциальной организации файлов является необходимость периодического переноса изменений из журнала в постоянную часть. По мере накопления изменений в журнале время отклика увеличивается - приходится сканировать все больший объем данных, переносить изменения в постоянную часть и переиндексировать ее. Обычно эта операция выполняется в специально выделенные моменты времени - регламентные часы. В СУБД HyTech версии 3.0 предусмотрены два режима выполнения переноса данных журнала. Либо в административном режиме (как описано выше), либо эта операция выполняется специальным монитором ядра в фоновом режиме - параллельно работе обычных пользователей. В этом случае момент замены старых частей таблицы на новые проходит для них практически незаметно.

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

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

    - высокую эффективность реализации файловых операций и повышение скорости доступа к данным за счет размещения частей БД на разных устройствах;

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

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

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

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

Таблица состоит из нескольких основных частей:

    - описатель таблицы;

    - файлы постоянной части;

    - файлы переменной части таблицы (журнала);

    - файлы управления захватами записей таблицы.

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

Постоянная часть состоит из следующих файлов:

    - область основных данных в сжатой форме;

    - область ассоциатора (таблица адресов записей в постоянной части и индексы ключевых элементов таблицы);

    - файлов, содержащих большие двоичные данные и текстовые поля.

Журнал таблицы состоит из следующих файлов:

    - список признаков выполненных операций (удаление, добавление, модификация);

    - область добавленных и измененных данных в сжатой форме;

    - файлы, содержащие большие двоичные данные и текстовые поля.

Файлы управления захватами записей таблицы включают в себя:

    - общий файл замков;

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

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

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

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

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

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

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

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

    - приближенные числа. Этот тип данных предназначен для хранения вещественных чисел в двоичной системе счисления. Поскольку не все вещественные десятичные числа могут быть точно преобразованы в двоичную систему счисления, возможна потеря точности при выполнении арифметических операций над данными этого типа. Округление производится в большую сторону. Следует избегать сравнения данных этого типа на равенство. Данные этого типа поддерживаются аппаратно и в этом их единственное преимущество. При хранении занимают 4 или 8 байтов, в зависимости от заданной разрядности и точности хранения. Допустимый диапазон чисел, хранимых в поле этого типа, -10308-10-308;

    - дата. Предназначен для хранения дат. Имеет следующие особенности. Хранится и сравнивается как число - порядковый номер дня от начала юлианского периода. При вводе/выводе представляется в виде строк различного вида (например, «21/11/97» или «21 Ноября 1997» и др.). При хранении занимает до 4-х байтов;

    - время. Предназначен для хранения времени суток. Имеет следующие особенности. Хранится и сравнивается как число - число миллисекунд, прошедших от начала суток. При вводе/выводе представляется в виде строк различного вида (типа «13:51:59» или «01:51PM» и др.). При хранении занимает до 4-х байтов;

    - временной штамп. Предназначен для хранения некоего момента в течение заданной даты. По сути, представляется парой «дата - время». При хранении занимает до 8-ми байтов;

    - большой двоичный объект. Предназначен для хранения объемных данных, например, рисунков или музыки. Размер хранимого объекта не должен превышать 2Гбайт. Хранятся только реально записанные данные;

    - большой текст. Предназначен для хранения объемных текстов. Данные не должны содержать управляющих символов. Размер хранимого объекта не должен превышать 2Гбайт. Хранятся только реально записанные данные.

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

Ограничения, налагаемые на размеры таблиц и число записей в них, зависят от используемой операционной системы. Для Windows NT и OS Solaris размеры файлов ограничены 64 разрядной сеткой, а для Novell- 32 битами. Размеры файлов таблиц также должны вписываться в эти ограничения. В общем случае, даже если размеры файлов таблиц укладываются в ограничения, накладываемые ОС, СУБД предполагает следующие пороговые значения:

    - число записей в одной таблице - не более 268 млн.;

    - число полей в записи - не более 255;

    - длина записи - не более 128 Кбайт;

    - длина имени поля - не более 42 символов.

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

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

Анализ гистограммы значений числовых полей позволяет, в некоторых случаях, уменьшить число байтов, отводимых для хранения чисел. Например, если поле будет содержать целые числа в диапазоне от 1-255, то для его хранения достаточно одного байта. Кроме того, если поле записи допускает ввод NULL значений и содержит его, место под хранение данных можно не отводить вовсе. Достаточно хранить только признак наличия NULL значения в данном поле. Признак удобно представить в виде бита, а несколько таких признаков упаковывать в байт. Такой подход сводит к минимуму накладные расходы на хранение. Аналогичным способом удобно хранить данные, имеющие битовый тип.

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

Использование описанных выше методов сжатия позволяет, с одной стороны, сократить используемое дисковое пространство (на практике, в 2-3 раза), а с другой стороны, свести к минимуму накладные расходы на упаковку / распаковку данных.

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

Записи таблицы идентифицируются с помощью уникальной группы символов или числа - ключа. Ключом обычно является одно из полей записи. Если список значений ключа уникален, ключ называется уникальным и он может служить для однозначной адресации записей. Иногда в качестве уникального ключа приходится выбирать группу полей, при этом значения каждого из них могут и не быть уникальными. Они становятся уникальными только в совокупности. Такой ключ называется составным. Один из уникальных ключей таблицы, используемый для идентификации записей, называется первичным. В СУБД HyTech имеется суррогатный ключ, являющийся частным случаем уникального. Значения этого ключа присваиваются самой СУБД и всегда только увеличиваются.

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

В СУБД HyTech любые поля записи, кроме больших двоичных объектов и текста, могут быть объявлены ключевыми. Для таких полей строится индекс. Индексы могут быть построены для группы из нескольких полей. Такая совокупность полей называется агрегатом, а ключ - составным. Поля, входящие в агрегат, могут располагаться смежно или перемежаться с другими полями.

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

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

СУБД HyTech можно отнести к классу систем с частично инвертированными файлами, так как она соответствует всем перечисленным ниже признакам:

    - записи располагаются в произвольной последовательности (соответствующей последовательности ввода);

    - первичный индекс отсутствует (нет ключа, в соответствии с которым записи упорядочены в файле данных);

    - для прямой адресации записей используются инвертированные индексы.

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

    - уникальные (или ключи, где значения почти не повторяются);

    - ключи с повторяющимися значениями - повторяющиеся ключи;

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

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

Основной инвертированный список условно разбивается на некоторое количество сегментов равного размера. Число таких сегментов - корень квадратный из числа записей в постоянной части. В оглавление 1-го порядка собираются первые элементы каждого сегмента основного инвертированного списка. Аналогичным образом, в оглавление 2-го порядка собираются первые элементы каждого сегмента оглавления первого порядка. Для создания оглавления 2-го порядка, оглавление 1-го порядка также разбивается на сегменты. Если ключ не является строго уникальным, значения ключа в инвертированном списке будут повторяться (например, значение 7 и 13 на рис.7.3.2).

Если повторов значений много, выгоднее хранить только уникальные значения и счетчики повторов. Для таких повторяющихся ключей инвертированный список устроен сложнее (рис. 7.3). Пары «значение - номер» заменены на пары «значение - адрес в таблице номеров». Хранятся только уникальные значения ключа. В остальном, индекс похож на предыдущий. Для ускорения поиска имеет оглавление, а при большом числе записей строится еще и оглавление 2-го порядка, в которое собираются первые элементы каждого сегмента оглавления первого порядка. Для создания оглавления 2-го порядка, оглавление 1-го порядка также разбивается на сегменты.

Если же число повторов каждого значения очень велико (а, значит, число самих значений мало (не более 2 - 3-х десятков)), целесообразнее строить индекс массового типа. Оглавление такого индекса будет состоять из списка значений ключа, а для каждого значения строится битовая строка, содержащая по одному биту для каждой записи постоянной части. При этом номер бита соответствует номеру записи (см. рис.7.3.4).

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

Рис.7.3.2. Структура индекса для уникального элемента


Рис.7.3.3. Структура индекса для повторяющегося элемента

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

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

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

Размер элемента файла признаков зависит от предельного размера журнала. Чем больше может быть журнал, тем большее число байтов приходится отводить для хранения адреса записи. Предельный размер журнала задается при создании таблицы и зависит от возможностей операционной системы. Для ОС, в которых размер файла ограничен 32 разрядной сеткой, предельный размер журнала предопределен. Это 2Г байта, а значит и адрес записи занимает 4 байта. Если данного ограничения нет, то предельный размер журнала может быть увеличен. Однако чем журнал больше, тем больший объем памяти требуется отводить для хранения адреса записи. Поэтому если задать очень большой размер журнала, а на самом деле использовать его малую часть, файл признаков будет содержать значительное число никому не нужных нулей.

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

При поиске в журнале приходится читать записи из файла с их телами, чтобы проанализировать значения искомых полей. Для уменьшения объема чтения записи в журнале сжаты. Поскольку нельзя сделать никаких предположений относительно диапазона хранимых чисел, используется максимальное число разрядов, заданное при описании полей таблицы. Аналогичным образом, все счетчики и номера записей хранятся в «полном» виде - 4 байта. Текстовые данные и массивы байтов переменной длины сжимаются.

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

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

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

Рис.7.3.4. Структура индекса для массового элемента


Рис. 7.3.5. Структура файлов журнала.

Запись 23 удалена, запись 12 модифицирована дважды, запись 100 добавлена.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В СУБД HyTech используется косвенная материализация результирующих отношений, поэтому результаты поиска в СУБД HyTech имеют следующие особенности:

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

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

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

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

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

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

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

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

Кроме этого, имеются функции, позволяющие выполнить логические операции над результатами атомарного поиска. К таким операциям можно отнести NOT, OR, AND и XOR.

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

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

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

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

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

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

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

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

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

    - полученный вектор пар «адрес - адрес» и является результатом соединения таблиц.

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

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

С учетом перечисленных особенностей сортировки для достижения её максимальной эффективности необходимо выполнять следующие рекомендации:

    - сортировка должна выполнятся только на конечном этапе - доступе к данным;

    - сортировать лучше небольшие результаты, т.е. предварительно сузить результирующее множество;

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

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

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

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

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

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

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

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

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

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