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

не

«\

^ .' • , и 1

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи Капризкипа Ирина Юрьевна

СЛОЖНЫЕ ОБЪЕКТЫ В СИСТЕМЕ ХРАНЕНИЯ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических паук

Научный руководитель: к.ф.-м.н. Б.А. Новиков

Санкт-Петербург 1993

Работа выполнена на кафедре исследования операций м&те-маткко-механического факультета Санкт-Петербургского государственного университета

Научный

руководитель: кандидат физико-математических наук, Новиков Борис Асенович

Официальные

оппоненты: доктор физико-математических наук, Баранов Сергей Николаевич

кандидат физико-математических наук, Новиков Федор Александрович

Ведущая

организация: Институт проблем информатики РАН

Защита состоится \ £ ¡.Я 1993 года в /У ча-

сов яа заседании специализированного совета К 063.57.54 по присуждению ученой степени кандидата физико- математических паук в Санкт-Петербургском государственном университете по адресу: 198904, г.Саякт-Петербург, Петродворец, Библиотечная площадь, 2, математико-механический факультет СПбГУ, зал заседаний Учепого Совета.

С диссертацией можно ознакомиться в научной библиотеке университета (г.Санкт-Петербург, Университетская набережная, д.7/9).

Автореферат разослал и/У " 1993 г.

Ученый секретарь

спепиализированного совета А.А.Кубенский

1 Общая характеристика работы

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

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

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

Методы исследования. При решении поставленных задач использовались методологические подходы, характерные для работ по моделированию баз данных, созданию объектно-

ориентированных моделей данных. Реализация интерфейса выполнена на языке программирования С. Отладка проводилась в нескольких операционных системах.

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

Практическая ценность. Практическая ценность работы определяется использованием ее результатов в проект« "СИНТЕЗ", ориентированном на создание интероперабельной среды неоднородных информационных ресурсов.

Апробация работы. Основные.результаты диссертации докладывались па 4 всесоюзной конференции "Системы баз данных и знаний" 1989г., на рабочих семинарах по проекту "СИНТЕЗ" в июне 1992 и марте 1993 годов, на сешшарах лаборатории исследования операций. По теме диссертации опубликованы работы

тя

Структура и объем работы. Диссертация состоит из 6 глав, в том числе введения и заключения. Объем диссертации составляет 65 машинописных листов, список литературы содержит 42 наименования.

2 Краткое содержание работы

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

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

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

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

начинается с 0. Множество любого типа может быть пустым.

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

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

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

Неопределенный сложный объект в структуре составного объекта выполняет роль "держателя места" и обеспечивает возможность хранения неоднородных объектов в качестве элементов одного множества (или значений одного атрибута). Он может появляться только в качестве элемента составного объекта и не допускается на верхнем уровне.

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

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

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

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

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

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

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

Функции интерфейса можно разделить на несколько групп:

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

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

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

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

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

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

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

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

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

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

ела, строки, символы и т.л.). Набор скалярных типов меняется от модели к модели.

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

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

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

Для оптимизации запросов можпо дополнительно использовать вторичные ключи.

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

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

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

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

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

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

3 Основные результаты

Основными результатами диссертации являются:

• Разработка модели данных системы хранения

• Определение синтаксиса, основных структур данных

• Разработка и реализация функций интерфейса

• Анализ выразительной силы модели данных

4 Публикации

[1] Домбровская Г.Р., Капризкина И.Ю., Нестереихо Ю.А., Новиков Б.А;.Исследование и разработка методов и средств хранения данных (знаний) для систем интеграции неоднородных информационных ресурсов, (заключительный отчет).- СПб.: СПбГУ, 1992.-помер Гос. регистрации 920004018.

[2] Капризкина И.Ю. Интерпретатор SQL для СУБД ТРИАЛА. Системы баз данных и знаний//секция 4/ Тез. докл. 4 всесоюз. конф.-Калинин.- 1989.-c.8-9.