Russia, St. Petersburg, SPIIRAS, grishkov@sparm.com

In the paper the specialized ordered storage structures of information allowing to make performance optimization in object database systems are examined. As the concrete physical realization of such structures in object database systems named Cache’ is considered. The problems of designing complete objects on management of data structures are not disregarded also.

Россия, Санкт-Петербург, СПИИРАН, grishkov@sparm.com

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

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

Любые нединамические объекты, по нашему мнению, можно имитировать разряженными упорядоченными иерархическими структурами (unloaded ordered hierarchical structures) - UOH-структурами. Динамика объектов задается языком управления такими структурами. Рассматривая хранение информации выраженной UOH-структурами мы спускаемся на формально-логический язык представления данных и связей между ними. UOH-структура представляет собой индексированное разряженное дерево с узлами упорядоченными некоторой однозначной функцией сортировки, которая может задаваться для всей UOH-структуры или ее части. Таким образом UOH-структура отличается от обыкновенного дерева не только разряженностью узлов но и заданной упорядоченностью. Формально обозначим UOH-структуру в виде A_z(x₁,..,x_n), где A_z – именованная метка UOH-структуры, а x₁,..,x_n – именованные метки узла. Введем следующие требования к именованной метке: именованная метка не может быть неопределенной или содержать пустое значение. Пусть упорядоченное множество именованных меток однозначно определяет узел UOH-структуры, а множество содержащее одну именованную метку определяет узел нулевого уровня, то есть идентификатор UOH-структуры. Запретим существование одинаковых множеств именованных меток, иначе говоря сделаем множества уникальными и введем однозначную связь между множеством и UOH-структурой. При изменении связей в UOH-структуре одновременно удаляются и (или) порождаются упорядоченное множества именованных меток, в соответствии со свойством однозначной связи. Таким образом UOH-структура приобретает свойство уникальности своих узлов. UOH-структура обязана обладать функциональным типом связи: 1:M или M:1, где M=0,1,2… и единственным иерархическим путем доступа к любому узлу. B UOH-структурах нет зависимых узлов, так удаление какого-либо узла не влечет за собой удаление его потомков. Введем два типа UOH-структур: локальные (local) и глобальные (persistent). Локальные UOH-структуры могут существовать лишь виртуально и не могут храниться физически в БД. Глобальные UOH-структуры напротив существуют только лишь в БД. Локальные и глобальные UOH-структуры по своим свойствам не отличаются друг от друга (все действия которые допустимы с локальными UOH-структурами допустимы и с глобальными), а различны их области существования. Деление UOH-структур на локальные и глобальные продиктовано практикой. Операции над локальными структурами происходят значительно быстрее, поэтому выгоднее выполнять многократные операции над локальными UOH-структурами, a результат записывать в глобальную UOH-структуру.

Определим формальный некоторый набор действий над UOH-структурами. Введем два оператора предназначенные для модификации узлов: Set, Kill. Оператор Set присваивает заданному узлу UOH-структурами значение. В качестве входных аргументов он должен получить именованное множество меток на узел UOH-структуры и значение, которое присвоится этому узлу, который определен этим множеством. Например, запись Set [A(“Предок1” ,”Потомок1” ) ,”Значение”] присваивает узлу (“Предок1”, ”Потомок1”) UOH-структуры на которую ссылается метка A значение = ”Значение”. Важно отметить, что узел дерева, которому присваивается значение не обязан существовать до момента присвоения в силу свойства разряженности UOH-структуры. Оператор Kill удаляет указанный узел UOH-структуры. Если узел заданный в качестве входного аргумента оператора Kill не существовал ранее, то никаких действий не выполняется. Далее введем еще два оператора аналогичных этим двум, но работающих сразу с группой потомков: USet, UKill. Оператор USet копирует всех потомков узла заданного вторым аргументом в подузлы узла заданного первым аргументом. К примеру, USet [A(“Предок1” ,”Потомок1” ), B] копирует B в A(“Предок1” ,”Потомок1”). Оператор UKill удаляет всех потомков указанного узла UOH-структуры. Для эффективного управления UOH-структурами необходимо ввести еще два оператора: Order и Get. Оператор Order возвращает упорядоченное множество именованных меток идентифицирующих следующий (предыдущий) узел UOH-структуры относительно заданного упорядоченного множества именованных меток, а оператор Get проверяет существование упорядоченного множества таких меток.

Рассмотрим практическую реализацию UOH-структур в СУБД Cache’ фирмы Intersystems. СУБД Cache’ хранит UOH-структуры в виде B*- деревьев. B-дерево (balanced), у которого каждый ключ указывает на блок данных, содержащий требуемую запись, называется B*-деревом. B*-дерево наследует все основные свойства B-дерева, в частности сбалансированность. B*-дерево является символьно- упорядоченной структурой. B*-дерево оптимизировано таким образом, что при поиске требуемого узла происходит минимальное обращение к дисковым блокам. Оно делает возможной интеграцию области указателей и области данных. B*-деревья состоят из различных блоков: блока каталога на вершине, одного или нескольких блоков указателей, а также блоков данных, находящихся на нижнем уровне и содержащих хранимую информацию. Прежде чем СУБД Cache’ записывает узел B*-дерева, отдельные индексы объединяются в одну символьную строку, поэтому скорость доступа к узлам не зависит от их вложенности. Сортировка B*-дерева происходит только в момент записи ранее несуществующего узла. B*-деревья в Cache’ имеют высокую степень свободы реорганизации и не имеют областей переполнения. Также Cache’ поддерживает сжатие ключей: имена соседних узлов, имеющих общее начало, сохраняются не целиком а лишь частично. Каждое имя узла сравнивается с предыдущем, длина совпадающей части сохраняется в виде числового значения, и, наконец в виде числовых символов – уникальная часть. Блоки данных на нижнем уровне связаны друг с другом дополнительными указателями, так что последовательные операции с базой данных проводятся в оптимальном режиме, не покидая текущий уровень данных. Для ускорения работы все блоки структуры B*-деревьев сохраняются в многоуровневом кэше в оперативной памяти, как только они прочитаны процессом с диска. Следовательно, при дальнейших попытках доступа к данному B*-дереву исключается повторное обращение к диску, что ведет к дальнейшему росту производительности.

Попытаемся раскрыть некоторые потенциальные возможности UOH-структуры и обсудим проект “qWORD”. Проект “qWORD” реализован в виде одного целостного объекта qWORD по управлению структурами данных. Физически qWORD реализован на языке СУБД Cache’ и поэтому данные хранит в виде глобальных разряженных деревьев с символьной упорядоченностью узлов (частный случай UOH-структуры). Представление данных объекта qWORD можно упрощенно описать в виде деревьев: ^Словарь и ^Таблица№. Знак “^” в именованной метке дерева означает в СУБД Cache’, что это дерево должно хранится в БД. Деревья имеют следующие структуры: ^Таблица№ (‘Код Записи’, ‘Название Атрибута’) = ‘Значение Атрибута’ и ^Словарь(‘Название Атрибута’, ‘Значение Атрибута’, ‘Номер Таблицы’, Код Записи) = "". Один экземпляр такого объекта представляет собой, обычно, совокупность нескольких деревьев ^Таблица№ (их названия отличаются №) и части дерева ^Словарь, которая определяется совокупностью названий атрибутов, включенных в этот экземпляр объекта. Каждое дерево ^Таблица№ определяет массив данных, который можно рассматривать как таблицу со столбцами, именованными названиями имеющихся в этой таблице атрибутов, и строками, именованными кодом записи. Значения дерева ^Таблица№ являются полями этой таблицы и именуются как значения атрибутов. В каждой таблице названия всех столбцов и строк разные. Для любых двух таблиц в пределах одной БД совпадение кодов записей никакой роли не играет, а совпадение части названий атрибутов, напротив, весьма существенна, так как обеспечивает связь между разными таблицами. Связь осуществляется через общие значения атрибутов с одинаковыми названиями. Иногда бывают связаны таблицы из разных экземпляров объектов, что свидетельствует, в этом случае, о связанности этих экземпляров между собой. Связь между таблицами осуществляется с помощью дерева ^Словарь, при условии, что значениями атрибутов являются слова (строки алфавитно-цифровых символов без пробелов). В объекте qWORD существует одно дерево ^Словарь для всей совокупности имеющихся данных. Дерево ^Словарь определяет массив данных, который можно рассматривать как множество словарей атрибутов, по одному на каждое название атрибута. Словарь атрибута можно рассматривать как совокупность отсортированных в алфавитно-цифровом порядке слов (значений соответствующего атрибута), записанных вертикально в столбце. Справа от этих слов приписана одна или несколько пар номер таблицы/код записи. Каждая такая пара это тот "адрес", куда входит это слово. У каждого слова таких "адресов" может быть один или несколько. Два или несколько разных значений одного атрибута будут связаны между собой, если к ним приписаны одинаковые "адреса". Структура словарей и атрибутов самодостаточны - любой из них достаточно для физического представления данных. Такое построение деревьев в объекте qWORD создает ряд преимуществ. Известно, что в реляционной модели часто используется операции сортировки, при которой множество записей рассматривается в алфавитно-цифровом порядке значений одного из атрибутов, участвующего в каждой записи этого множества. Структура дерева ^Словарь такова, что на физическом уровне структуры данных сортировка существует изначально для каждого из атрибутов, что позволяет не только увеличить производительность, но и хранить данные в сжатом виде.

1.Лачинов В.М., Поляков A.O. Информодинамика.

2.Долженков АН Поляков АО Создание промышленных информационных систем на основе M-технологии. Доклады 4 СПб международной конференции “Региональная информатика 95”, СПб, Изд. СПОИСУ, 1995.

3.Cache Development Guide. Version 3.1. Cambridge: Intersystems 1999.

4.Cache ObjectScript Language. Version 3.1. Cambridge: Intersystems 1999.