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

РГВ од

., , Санкт-Петербургский государственный университет

1 ]1 *} ч 11 'I ■ м Л

На правах рукописи

Новиков Борис Асенович

Методы и средства организации хранения в системах Паз данных нового поколения

05.13.17 - Теоретические основы информатики

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

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

Работа выполнена в Санкт-Петербургском государственном университете.

Официальные оппоненты:

• член-корреспондент РАН, доктор физико-математических наук, профессор В.П. Иванннков

• доктор технических наук, профессор P.A. Полуэктов

• доктор физико-математических наук С.Н. Баранов

Ведущее предприятие — Институт проблем информатики Российской академии ваук

Защита диссертации состоится в i С час. 30 мин. на заседании специализированного совета Д 063.57.52 по защите диссертаций на соискание ученой степени доктора физико-математических наук при Санкт-Петербургском государственном университете по адресу: 198904 Санкт-Петербург, Старый Петергоф, Библиотечная ил. 2.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского университета по адресу:

199034, Санкт-Петербург, Университетская набережная, 7/9.

Автореферат разослан

Ученый секретарь специализированного совета

Д.А. Кубенский

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

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

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

Такие средства (системы хранения) обычно реализуются как часть системы управления базамп данных, например [15], но пногда рассматриваются и как самостоятельные системы [5, 3, 6], а также более поздние работы [11, 12] н другие.

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

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

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

может использоваться как испытательный стенд для:

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

« реализации управления данными в новых приложениях, для которых традиционные системы недостаточно эффективны.

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

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

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

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

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

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

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

Апробация работы. Результаты работы докладывались на всесоюзных конференциях по системам баз данных и знаний, рабочих семинарах Московской и Киевской секции группы по обработке данных Ассоциации Вычислительной техники (ACM SIGMOD), на двухстороннем Итальяно-российском рабочем семинаре по перспективными системам баз дапных, на семинарах по проекту СИНТЕЗ в институте Проблем Информатики РАН и др.

Переносимость прототипа системы хранения проверена реализацией на трех различных архитектурах ЭВМ под управлением семп операционных систем.

Публикации. По теме диссертации опубликовано 14 работ, которые отражают ее основное содержание.

Структура я объем работы. Диссертация состоит из 6 глав (в той числе введения и заключения), разбитых на 12 разделов, и списка использованной литературы. Объем работы - 124 стр., включая 15 страниц списка использованной литературы, насчитывающего 123 наименований.

Содержание работы

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

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

Как правило, объектно-ориентированные модели предоставляют развитые навигационные средства поиска данных, требующие эффективной реализации указателей на уровне среды хранения [12].

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

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

Важная особенность, отличающая систему хранения ог других си-

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

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

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

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

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

менем доступа к данным а обычной оперативной памяти.

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

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

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

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

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

Одним из основных требований к реализации системы хранения является возможность переноса в другие операционные среды. Фактически система хранения реализована на различных архитектурах ЭВМ и под управлением существенно различных операционных систем, в том числе ОС ЕС, VM/CMS, различные варианты Uuix, а также OS/2 и MS DOS.

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

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

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

Третья глава посвящена описанию основного внешнего программного интерфейса системы хранения.

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

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

Основными требованиями к системе хранения сложных объектов являются:

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

2. Возможность параллельного доступа к любым объектам.

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

4. Расширяемость системы, т.е. возможность включения новых алгорифмов в структур данных.

Раздел 3.2 определяет модель сложных объектов, принятую в системе хранения.

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

Наиболее существенными особенностями описываемой ниже структуры хранения являются:

♦ органичное включение системы вторичных индексов

• возможность построения множества из элементов неоднородной структуры.

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

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

10

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

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

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

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

Система хранения обеспечивает построение следующих типов вторичных индексов:

• упорядоченный по значениям ключа, рассматриваемого как байтовая строка;

• индекс для поиска по множественным ключам, пепользующпй метод кодирования наложением [9];

• многомерный (пространственный) индекс для точечных объектов (клеточный файл);

« пространственный индекс для протяженных объектов (например, 11-деревья пли С-деревья [7|);

• индекс для поддержки унифнкационных операций.

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

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

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

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

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

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

Для всех типов описаний определены два вида представления: внешнее и внутреннее. Внешнее представление всегда является "текстовым"

12

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

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

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

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

• главные файлы, в которых хранятся короткие объекты н служебные записи длинных;

• файлы данных для длинпых скалярных значений;

• файлы индексов.

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

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

• Для организации доступа к составным объектам и скалярным значениям в оперативной памяти строятся таблицы сканирования, иногда

называемые курсорами.

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

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

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

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

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

Пусть N есть общее количество индексированных записей, через V обозначепо количество различных значений индексных термов. Пусть 6 и В суть соответственно количество записей в блоке индекса и количество записей в листе индекса. Пусть каждая пз N записей имеет т ключей, а в запросе задано <\ различных значений ключа. Тогда ожидаемое количество обращений к диску составит

ц * log(т *Щ + (д*т* И/У

-1 )/В.

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

Вариант блочного кодирования наложением с кратными индексами использует

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

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

Аналогичные оценки получены для пндекснрования с учетом временных привязок значений данных.

Глава 4 посвящена методам реализации ядра системы хранения, обеспечивающего выполнение низкоуровневых функций системы. Цен- _ тральную часть любой системы хранения составляют методы доступа, рассматр51ваемые в разделе 4.1.

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

Основными характеристиками, по которым оцениваются методы доступа, являются:

• среднее (пли наихудшее) количество обращений к внешней памяти при поиске или при обновлении,

• коэффициент использования выделенной дпсковой памяти,

й также зависимость этих характеристик от таких параметров, как размер файла, соотношение количества операций поиска и обновления. '

Затраты времена процессора в размеры необходимой оперативной памяти обычно считаются менее существенными.

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

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

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

Раздел 4.2 посвящен анализу требований к файловым системам и описанию особенностей файловой системы, реализованной в рамках en- , стемы хранения.

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

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

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

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

В разделе 4.3 описываются функция службы управления буферизацией системы хранения. '

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

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

При обслуживании буферов ключевым вопросом является выбор стратегии замещения. В зависимости от характера использования данных наиболее оптимальными могут быть различные алгоритмы: LRU, MRU, CLOCK И другие, которые могут использоваться как самостоятельно, так и в качестве внутренних в более сложных алгоритмах, таких как Hot Set, DBMIN, GCLOCK, рассмотренных в [4]. В спуж-

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

В главе 5 описывается использование системы хранения в составе различных экспериментальных исследовательских системах.

Раздел 5.1 описывает среду хранения программного макета машины баз данных, разработанного в 1987-1988 гг. в ИПИАН СССР. В соответствующем интерфейсе системы хранения реализованы базовые операции для поддержки реляционной алгебры. Управление средой хранения реализуется с помощью сообщений, передаваемых средствами синхронизация процессов операционной системы (1Шх).

В этом разделе рассматривается представление нормализованных и иерархических отношений, определенных в программном макете машины баз данных и использованное в системе интеграции неоднородных баз данных п знании ¡2].

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

Структура данных поддерживает иерархические отношения, снабжаемые вторичными индексами.

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

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

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

Реализация структуры хранения графических объектов ориентирована на быструю выборку объектов по ключам при относительно большом времени обновления.

В раздел 5.3 рассматриваются методы представления объектов языка описания, спецификации и программирования в интероперабельной среде неоднородных информационных ресурсов СИНТЕЗ [1, 8) в терминах модели сложных объектов и содержатся сравнительный анализ различных вариантов такого представления.

Основными элементами представления в базе метаданных системы СИНТЕЗ являются фреймы [1|, представляющие собой (частично) са-моопределеняые иерархические структуры, возможно, связанные взаимными ссылками. Различные типы фреймов и варианты их использована« для описания информационных ресурсов несущественны для среды хранения, однако способность фреймов языка СИНТЕЗ выступать в качестве объектов в смысле объектно-ориентированных моделей баз данных влияет на их представление, так как при хранении классов объектов может быть существенна кластеризация.

Большое разнообразие необходимых структур данных языка СИНТЕЗ и методов их обработки не позволяет; выбрать единую стратегию их представления в среде хранения.

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

19

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

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

Время доступа к отдельному объекту в этом случае будет больше, чём в случае одноуровневого хранилища, и количество обращений к диску составит

М(1 + 1о6^),

где через Ь обозначена емкость блока индекса, а через N - общее количество объектов в базе данных.

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

(М-1)(1 + 1об1ЛГ) + п/В

обращений к диску, где через п обозначено количество объектов в классе и через В - число объектов в одном блоке диска, поскольку в данном случае возможно (и эффективно) применение последовательного просмотра.

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

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

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

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

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

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

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

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

1. Предложена концепция сложных объектов системы хранения и разработан интерфейс манипулирования сложными объектами.

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

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

4. Спроектирован и реализован мобильный прототип системы хранения для перспективных систем баз данных и знаний.

5. При реализации структур данных системы хранения использованы современные высокоэффективные методы доступа.

6. Создана среда для проведения исследований по методам представления данных в среде хранения.

7. Разработаны н реализованы специализированные интерфейсы системы хранения для нескольких приложений в экспериментальных системах.

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

Литература

[lj Л.А. Калиниченко. Синтез: язык определения, проектирования и программирования интероперабельных сред неоднородных информационных ресурсов. Москва, 1991.- 101 с.

[2] Л.А. Калиниченко. Методы и средства интеграции неоднородных, баз данных. М.: Наука. Главная редакция физико-математической литературы, 1983.- 423 с.

[3¡ М. Catey, D. DeWitt, J. Richardson, and Б. Shekita. Object and file management in the EXODUS extensible database system. In Proc. 12 conf. VLDB, pages 91-100, 1986.

[4] H.-T. Chou and D. DeWitt. An evaluation of buffer management strategies for relational database systems. In Proc. It conf. VLDB, pages 127-141, 1985.

[5] H.-T. Chou, D. DeWitt, R. Katz, and A. Chig. Design and implementation of the Wisconsin Storage System. Software—Practice and Experience, 15(10):315-344, 1985.

[6] U. Deppisch, H.-D. Paul, and H.-J. Schek. A storage system for complex objects. In Int. workshop on object-oriented database systems, pages 183-195, 1986.

[7] O. Giinter. Efficient architectures for geometric data management, volume 337 of Led. Notes in Сотр. Set. Springer-Verlag, 1989.

23

[8] L, Kalinichenko. The interoperable environment of heterogeneous information resources: a generalization perspective. In Proc. of the First International Workshop on the Interoperability in Multidatabase systems, pages 196-199, Kyoto, April 1991.

(9] A. Kent, R. Sacks-Davies, and K. Ramamohanarao. A superimposed coding scheme based on multiple block descriptor files for indexing very large databases. In Proc. 14 con/. VLDB, pages'351-359, 1988.

[10) S. Khoshafian, M. Franklin, and M. Carey. Storage management for persistent complex objects. Inf. Syst., 15(3):303~320, 1990.

[11) C. Lamb, G. Landis, J. Orenstein, and D. Weinreb. The ObjectStore Database System. Communications of the ACM, 34(10):50-63, 1991.

[12) J. E. B. Moss. Design of the Mneme persistent object store. ACM Trans. Inf. Syst., 8(2):103-139, 1990.

[13} M. Ramakrishna and P. Larson. File organization using composite perfect hashing. ACM Trans, on Database Systems, 14(2):231~264, 1989.

[14] R. Snodgrass and I. Akn. A Taxonomy of Time in Databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 236 -246. 1985.

[15] M. Stonebraker. The design of the POSTGRES storage system. In Proc. 13 conf. VLDB, pages 289 -300, 1987.

Работы автора по теме диссертации

[1] Б.А. Новиков. Реализация сложных объектов в системе хранения. УСиМ, № 7, 1991.- С. 46-52.

[2) H. Dombrowska, I. Kaprizkina, В. Novikov. Representation and analysis of the SYNTHESIS data structures in the storage system. In Proc. of the workshop on advances in databases and information systems — ADD IS'93. Moscow, 1993. P. 60-68.

[31 Б.А. Новиков. Индексирование во временных базах данных. Труды рабочего семинара: Перспективы развития систем баз данных и информационных систем. М.: ИПИ РАН, 1993.- С. 69-74.

(4| В.А. Новиков. Система хранения данных для СУБД нового поко- . ления. Разработка, внедрение и использование баз данных и баз знаний. Межотрасл. конф. - Ростов на Дону, 1988 - С. 39-42.

[5] Б.А. Новиков. Структура системы хранения в программном макете машины баз данных. Системы баз данных и знаний. Секция 2: Обще сист. программные средства СУБД и СУБЗ. Тез. докл. 4 всесоюз. конф. - Калинин, 1989.- С. 27-28.

[6] Г.Р. Домбровская, Б.А. Новиков. Индексирование сложных динамических объектов во временных базах данных и знаний. Тезисы докл. 3 междунар. научно-техн. конф. "Программное обеспечение ЭВМ". Секция 5: СУБД. Тверь, 1990.- С. 16-18.

25

(7) Б.А. Новиков. Средства физической организации для поддержки новых моделей данных. Прогр. обесп. новых информационных технологий. Всесоюз. научно-техн. семинар,- Тверь, 1991,- С. 136-137.

[8] Б.А.Новиков. Системы хранения баз данных и знаний. 5 всесоюз. конф. "Системы баз данных и знаний", Львов, 1991.- 29 с.

[9j Б:А. Новиков. Системы хранения баз данных и знаний. Программирование.- 1993, № 2.- С. 3-30.

[10) Б.А. Новиков. Программный макет машины баз данных. Внутрен- . ние структуры данных... Справочный материал. 2700560.0001601 90 06. М.: ИПИ АН, 1988,- 66 с.

[11) Б.А. Новиков.. Программный макет машины баз данных. Система хранения данных и управления буферной памятью. Описание программы. 2700560.00016-01 13 06. М.: ИПИ АН, 1988,- 45 с.

[12) Г.Р. Домбровская, Ю.А. Нестеренко, Б.А. Новиков. Исследование, и разработка методов и средств хранения данных (знаний) для систем управления и машин баз данных (баз знаний), (заключительный отчет), Л.: ЛГУ, 1990, № Гос. per. 01890086701,- 72 с.

[13) Г.Р. Домбровская, Ю.А. Нестеренко, Б.А. Новиков. Система интеграции неоднородных баз данных. Внутренние структуры данных... Справочный материал. 2700560.00016-01 90 06. М.: ИПИ АН, 1990.- 62 с.

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

26