СП.АРМ

В работе [1] была предложена интерпретация расширенной реляционной модели данных RM/T [2]. Согласно этой интерпретации молекулярные типы RM/T могут быть описаны структурой дерева с горизонтальными связями, дерево должно быть логическим, что позволит легко решать задачи переструктуризации дерева. Для такой структуры должна поддерживаться возможность представления горизонтальных связей в виде логических деревьев. Суррогаты должны служить для упорядочивания кортежей. Также было предложено использовать для описания этой интерпретации модели данных RM/T модель данных XML, наконец, было представлено краткое описание разработанной расширенной модели данных, основанной на модели данных RM/T, для описания которой используется модель данных XML.
В разработанной расширенной модели данных иерархическая модель данных в варианте XML наложена как вторичная поверх реляционной. Это позволяет сохранить строгость реляционной модели и привнести в неё дополнительные преимущества иерархической модели, а также использовать для описания модели как реляционную алгебру, так и языки и стандарты платформы XML: XML [3], Relax NG [4], Schematron [5], DOM [6], XPath [7, 8], XQuery [9].
Основными структурными компонентами разработанной модели данных являются понятие, объект, экземпляр объекта, код экземпляра объекта, отображение.
Объекты соответствуют типам элементов XML-документа, экземпляры объектов – отдельным элементам, а понятия – атрибутам элементов. С другой точки зрения объекты соответствуют реляционным отношениям, экземпляры объектов – кортежам отношений, а понятия – атрибутам отношений (рис. 1).

Рис 1. Структурные компоненты модели данных

Если с точки зрения XML позиция элемента это ключ естественный, то чисто с реляционной точки зрения он видится как ключ суррогатный. В разработанной модели данных этот ключ называется кодом экземпляра объекта.
Для описания связей понятий с объектами, а также связей между объектами вводится ещё одна структура – отображение. Отображение включает схему дерева объектов и дерево экземпляров. Дерево объектов соответствует схеме ХML-документа и может быть описано с помощью языка Relax NG [4], а дерево экземпляров – множеству ХML-документов, удовлетворяющих этой схеме.
Базу данных предлагается моделировать как совокупность деревьев информационных объектов с горизонтальными связями и со специфичным для каждого объекта набором понятий.
Значения понятий могут быть структурированными и неструктурированными. Под структури-рованным значением понимается последовательность слов, разделённых пробелами. Неструк-турированное значение – это многострочный текст или последовательность байтов, которая может интерпретироваться как изображение, звук, видео.
Для идентификации отображений, объектов и понятий предлагается использовать уникальные в пределах базы данных короткие коды. Относительно этих кодов определяются ограничения це-лостности и операции.
Так как задачей является построение логической структуры с возможностью переструктуризации, то и иерархические связи, и горизонтальные связи реализуются только на основе значений понятий, таким образом, все связи являются информационными.
В код экземпляра помимо первичного позиционного ключа объекта, включаются также внешние ключи, ссылающиеся на экземпляры-предки данного экземпляра (рис. 2).

Рис. 2. Реализация иерархических связей

Такой иерархический позиционный первичный ключ определяет уникальность экземпляра не только в пределах родительского экземпляра, но и в пределах любого экземпляра-предка. Используя метод редукции ключа, можно получить доступ к любому предку данного экземпляра объекта. Поэтому, несмотря на избыточность данных, такой ключ является наиболее предпочтительным, он позволяет реализовать и поддерживать иерархические связи автоматически.
Горизонтальные связи реализуются пользователем с помощью механизмов пользовательских потенциальных и внешних ключей объектов.
В модели данных предусматриваются ограничения целостности: ограничения типов и понятий, ограничения объектов и ограничения базы данных. Ограничения целостности могут быть описаны с помощью языка Schematron [5]. Благодаря выбранной структуре кодов экземпляров, правила целостности сущностей и правила ссылочной целостности для иерархических связей поддерживаются автоматически.
В модели данных предлагается поддерживать не только спецификационные операции, но и навигационные операции манипулирования данными, так как они предоставляют большую гибкость и свободу в реализации конкретных задач. Навигационные операции соответствуют низкоуровневым операциям модели DOM [6] с некоторыми расширениями. Спецификационные операции соответствуют реляционной алгебре с расширением операций на деревья объектов. Спецификационные операции могут быть описаны с помощью языка XQuery [9].
В данной работе предлагается реализация физического уровня для системы, поддерживающей предложенную модель данных. Определяются структуры хранения и методы доступа к данным, выбирается способ реализации, с помощью которого осуществляется разработка.
Иерархической организации данных свойственно дублирование информации и соответственно избыточность данных. Такое дублирование должно адекватно отражаться в модели данных. Дублирование информации позволяет отказаться от реализации горизонтальных связей между отдельными деревьями и непосредственно использовать значения. Вместе с тем с точки зрения физического уровня необходимо минимизировать количество хранимой информации. В работе предлагается механизм устранения избыточности данных на физическом уровне.

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

Рис. 3. Индекс

Индекс по нескольким атрибутам таблицы называется составным. Индекс на комбинации атри-бутов F1, F2 … Fn (в указанном порядке) может также использоваться в качестве таких индек-сов: только на одном атрибуте F1, на комбинации атрибутов F1, F2, на комбинации атрибутов F1, F2, F3 и т.д. Для индексации атрибута F2 потребуется создание дополнительного индекса.
Для повышения скорости доступа к данным используют кластеризацию. Основная идея класте-ризации заключает в том, что необходимо обеспечить хранение логически связанных записей в непосредственной близости друг от друга. Различают внутритабличную кластеризацию, т.е. кластеризацию, применяемую в пределах одной таблицы, и межтабличную кластеризацию, т.е. кластеризацию, применяемую больше чем к одной таблице.
При использовании кластеризации записи хранятся в кластерном индексе, записи упорядочены по значениям кластерного ключа. Некластерный (обычный) индекс в этом случае содержит вместо указателя на запись значение кластерного ключа (рис. 4) Если кластерный индекс не уникален, то к индексируемым значениям добавляется суррогатная (т.е. генерируемая систе-мой) «добавка», которая делает их уникальными. Эта добавка скрыта от пользователя.

Рис. 4. Кластерный индекс

В предложенной модели экземпляры объектов должны быть логически упорядочены по значе-ниям позиционного первичного ключа, поэтому имеет смысл хранить их в такой же последова-тельности. Для этого создается кластерный индекс по позиционному ключу – коду экземпляра.
Рассмотрим, как осуществляется наложение иерархии в предложенной модели данных. Допус-тим, имеется следующая иерархическая структура, выраженная языком XML:
Необходимо представить эту структуру в реляционной модели. Для этого предлагается вариант, показанный рис. 5.

Рис. 5. Наложение иерархии

Здесь для кодирования позиций вместо десятичных цифр предлагается использовать латинские буквы. Использование букв вместо цифр связано с тем, что с помощью одного цифрового сим-вола можно закодировать только 10 записей, а с помощью буквенного символа – 52.
Корневая таблица имеет простой первичный ключ, а каждая дочерняя таблица – составной пер-вичный ключ. Внешние ключи входят в состав первичного ключа и ссылаются на первичные ключи всех таблиц-предков данной таблицы. Составной позиционный первичный ключ опреде-ляет уникальность записи в пределах любой записи-предка. Поэтому, несмотря на избыточ-ность, предлагается именно такой вариант наложения иерархии.
Для выбранного варианта наложения иерархии индексация показана на рис. 6.

Рис. 6. Индексация

Здесь созданы кластерные индексы для первичных ключей таблиц. Поскольку первичные клю-чи составные, кластерные индексы также будут составными. В индексации внешних ключей нет необходимости, так как они входят в состав ключа кластерного индекса и находятся в его начале. Напротив, дополнительно проиндексирован атрибут С#, поскольку составной индекс А#B#C# ничего не дает для поиска по значениям C# – они находятся не в начале ключа индек-са, а в его конце. Также создан индекс для неключевого атрибута E таблицы 2.
Идею составных кластерных индексов в данной работе предлагается естественным образом распространить на ключи таблиц. То есть, вместо составного позиционного ключа из несколь-ких атрибутов, предлагается использовать простой (из одного атрибута) позиционный ключ, который является ключом кластерного индекса. В этом случае отпадает необходимость допол-нительно индексировать атрибут С#, так как он войдёт в состав простого ключа.
Таким образом, код экземпляра, который на уровне предлагаемой модели является простым ие-рархическим позиционным первичным ключом, на уровне хранения является ключом составно-го кластерного индекса.
В этом варианте индексации использовалась внутритабличная кластеризация. Межтабличная кластеризация показана на рис. 7.

Рис. 7. Межтабличная кластеризация

Здесь показан кластерный индекс для первичных ключей, принадлежащих разным таблицам. Это позволяет физически хранить записи разных таблиц в связанном виде в последовательно-сти иерархического обхода. При этом имя таблицы необходимо включить в состав ключа ин-декса.
Необходимо также учесть возможную разреженность данных. Пример разреженных данных можно увидеть на рис. 7, в виде обилия незаполненных ячеек. Для разрешения этой ситуации на физическом уровне предлагается хранить записи не как два последовательных списка (один для имен атрибутов в описаниях, другой для значений в данных), а как один упорядоченный список пар имя атрибута – значение, не храня в списке пары, в которых отсутствует значение. Таким образом, имя атрибута предлагается включить в состав ключа индекса.
Оба варианта кластерной индексации, соответствующие рис. 6 и рис. 7, в терминах предложен-ной модели данных представлены на рис. 8.

Рис. 8. Варианты кластерной индексации

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

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

3. Кодирование слов значений
Для устранения избыточности данных на физическом уровне в данной работе предлагается ко-дировать слова структурированных значений суррогатными кодами. Для поддержки кодирова-ния слов значений предлагаются две дополнительные структуры хранения, одна из которых бу-дет связывать слово значения с суррогатным кодом (прямой словарь значений), а другая – сур-рогатный код со словом значения (обратный словарь значений).
Обратный словарь предлагается реализовать как кластерный индекс слов значений, что позво-лит создавать характеристики слов значений. Такая характеристика может представлять собой некий синоним слова значения или обобщающее значение. Ключом кластерного индекса слов значений будет являться суррогатный код слова значения. Прямой словарь предлагается реали-зовать как некластерный индекс слов значений, который ссылается на суррогатные коды слов кластерного индекса (рис. 10).

Рис. 10. Прямой и обратный словари значений

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

Рис. 11. Кодирование слов значений

Как видно из сопоставления рис. 9 и 10 при одновременной индексации значений понятия и ко-дировании слов значений понятий некластерный индекс и прямой словарь могут быть объеди-нены в рамках единой структуры (рис. 12).

Рис. 12. Некластеный индекс и прямой словарь

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

Рис. 13. Словарь значений понятий

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

Существует два возможных направления реализации физического уровня и системы в целом:
реализация с нуля;
реализация на основе какой-либо СУБД.
В первом варианте можно получить свободу и гибкость в принятии проектных решений, но при этом разработка потребует гораздо больше времени и усилий, кроме того, многие возможности существующих СУБД придётся реализовывать, по сути, заново.
Во втором варианте можно получить развитые возможности СУБД, например механизм управ-ления транзакциями, средства защиты данных, на разработку которых были затрачены значи-тельные усилия. Однако, если строить систему как надстройку над какой-либо SQL- или объ-ектной СУБД, то не удастся получить необходимой гибкости в принятии проектных решений и неизбежно возникнут накладные расходы при взаимодействии «опорной» СУБД и надстройки. Эти системы не предоставляют непосредственный доступ к физическим структурам хранения, а предоставляют высокоуровневые SQL-ный или объектный интерфейсы. Так как физические структуры надстраиваемой СУБД не являются ни отношениями, ни объектами, то неизбежны потери в производительности при их представлении отношениями или объектами.
Соответственно, необходим компромиссный вариант, который с одной стороны предоставляет низкоуровневый интерфейс к структурам хранения, а с другой обладает развитыми средствами СУБД.
В данной работе в качестве такого компромиссного варианта предлагается использовать M-системы [10, 11]. Поэтому разрабатываемая система реализуется как надстройку на M-системой.
М – процедурный язык программирования без какой-либо жёсткой парадигмы. В M отсутствует декларирование переменных, единственный тип данных — это строка символов переменной длины. Идея отсутствия деклараций в М естественным образом распространяется и на массивы. Каждая переменная может представлять собой массив с переменным числом измерений, при-чем память занимают лишь те элементы массива, для которых определены значения, т.е. масси-вы являются разреженными. В качестве индексов массива разрешены любые строки символов. Индексы массивов сортируются автоматически. Переменные могут быть локальными (сущест-вующими лишь в оперативные памяти) и глобальными (существующими во внешней памяти). Глобальные переменные в М называются глобалами.
Координация доступа к глобальным переменным в многопользовательской среде осуществля-ется с помощью блокировок, М поддерживает обработку транзакций и сетевое взаимодействие. На этом языке могут быть реализованы все известные модели данных. Вместе с тем следует от-метить, что M-системы – это, прежде всего, средство для разработки СУБД, а не собственно СУБД.
Главным достоинством М-систем является эффективный механизм управления внешней памятью в виде B*-деревьев, которые на логическом уровне представляются через глобалы. Глобалы – хранимые на диске, рассортированные по строковым индексам разреженные массивы произвольной размерности.
^G(Ind1,Ind2,…,IndN)=Value,
где
G – имя глобала;
Ind1, Ind2,…, IndN – индексы;
N – размерность массива;
Value – значение.
Основными преимуществами глобалов, используемыми в данной разработке, являются:
• Сортировка элементов глобалов в момент записи, представляемая на логическом уровне (на уровне глобалов), что непосредственно позволяет использовать глобалы для построения индек-сов;
• Сжатие ключей, что позволяет представлять логически связанные структуры, например, не-кластерный индекс и прямой словарь, совместно, при этом логическая избыточность на физиче-ском уровне устраняется.
В качестве M-систем могут использоваться, система управления базами данных Cache’ от InterSystems Corporation [12, 13] или GT.M от Sanchez Computer Associates [14]. Эти СУБД обладают всеми характеристиками промышленных систем: высокой производительностью, надёжностью, масштабируемостью, открытостью и переносимостью.
Cache’ позиционируется разработчиком как постреляционная СУБД, сочетающая три моде-ли данных и соответственно три доступа к данных: прямой (через глобалы), объектный и SQL-ный. «Постреляционность» реализована с помощью единой архитектуры данных. Она предусматривает единое описание объектов и таблиц, отображаемых непосредственно на многомерные структуры.
Cache’ является коммерческим продуктом и на сегодняшний день наиболее функциональ-ной СУБД на основе М-технологии, к тому же хорошо документированной, в том числе на русском языке.
GT.M имеет открытую архитектуру. Реализация GT.M на x86 Linux является свободно рас-пространяемой вместе с исходными кодами. По своим встроенным инструментальным воз-можностям GT.M уступает Cache’, однако благодаря открытости системы имеется возмож-ность реализации собственных интерфейсов.
Инструментальные средства Cache’ в значительной степени ускоряют разработку приложений, однако, при эксплуатации информационной системы в качестве сервера можно использовать любую из систем.