Наши публикации « Компания СП.АРМ

Archive for the ‘Наши публикации’ Category

Использование платформы XML для описания расширенной реляционной модели данных RM/T

Пятница, Август 15th, 2008

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

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

2. Модель данных RM/T
Базовыми семантическими понятиями расширенной реляционной модели данных RM/T явля-ются сущность, свойство, связь, подтип. Связь рассматривается как особый вид сущности.
Сущности имеют типы, которые классифицируются на три категории:
• Характеристические сущности выполняют вспомогательную роль в описание некоторой другой сущности. Существование характеристик зависит от существования описываемых ими сущностей.
• Ассоциативные сущности выполняют вспомогательную роль в обеспечении взаимосвязи других сущностей. Ассоциации представляют связи типа «многие ко многим».
• Стержневые сущности независимы.
Сущности могут иметь свойства, поддерживаются супертипы и подтипы сущностей.
Для идентификации сущностей предметной области используются суррогаты (определяемые системой идентификаторы). Пользователи базы данных могут заставить систему сгенерировать или удалить некоторый суррогат, но они не могут изменять значение суррогата. С введением суррогатов не отменяются ключи, контролируемые пользователями.
Каждому типу сущности соответствует унарное E-отношение (рис. 1). В E-отношении перечисляются суррогаты всех сущностей, которые имеют этот тип и существуют в базе. Свойства типов сущностей представляются P-отношениями (рис. 1).

Рис. 1. E- и P-отношения

Для связи некоторого свойства с типом сущности, а также для связи типов сущностей используются бинарные и тернарные графовые отношения.
RM/T поддерживает определённую атомарную и молекулярную семантику. Атомарная семантика представляется n-мерными отношениями (в крайнем случае, бинарными), которые являются наиболее малыми смысловыми единицами, молекулярная семантика представляется смысловыми единицами большими, чем n-мерные отношения. RM/T поддерживает четыре измерения молекулярной семантики: декартову агрегацию, обобщение, агрегацию покрытия и предшествование событий.
Декартова агрегация – это абстракция, в которой связь между объектами рассматривается как объект более высокого уровня. В RM/T декартова агрегация подразделяется на 3 вида:
1. Агрегация простых свойств, которая образует некоторый тип сущностей.
Совокупность P-отношений для заданного E-отношения составляет молекулярный тип свойств.
2. Агрегация характеристических сущностей, которая образует некоторый тип сущностей.
Характеристическая сущность сама может иметь одну или более характеристических сущностей, ей подчиненных. Характеристические типы сущностей, обеспечивающие описание заданного стержневого типа сущностей, образуют характеристическое дерево.
Совокупность характеристических отношений для заданного E-отношения составляет характеристический молекулярный тип.
В данной работе характеристическую агрегацию предлагается естественным образом описывать и представлять в виде дерева типов сущностей (рис. 2).

Рис. 2. Характеристическая агрегация

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

Рис. 3. Ассоциативная агрегация

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

Рис. 4. Агрегация обобщения

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

Рис. 5. Агрегация покрытия

Вместе с тем агрегацию покрытия также удобно представлять в виде дерева.
Предшествование событий – это абстракция, которая отражает последовательность некоторых типов событий.
Для представления относительного времени возникновения событий в данной работе предлагается использовать упорядочивание данных, которое может быть реализовано, если суррогаты будут нести дополнительную смысловую нагрузку – будут служить для упорядочивания сущностей.
RM/T включает расширяемый каталог, содержащий информацию об отношениях, атрибутах, доменах и существующих связях между ними. Также RM/T предусматривает специальные операторы над именами, множествами и графовыми отношениями.
В целом RM/T вводит молекулярные смысловые единицы, более крупные, чем отдельные n-арные отношения. Эти смысловые единицы более естественны и интуитивно понятны для человека. Однако механизм реализации расширений является низкоуровневым, что делает модель более мощной и гибкой, но вместе с тем более сложной и ориентированной в первую очередь на программистов, а не на пользователей. Большинство деталей расширения должно быть скрыто от основной массы пользователей. Из-за своей сложности RM/T не получила широкого распространения.
Как было отмечено, характеристическая агрегация может быть описана древовидной структурой, а ассоциативная агрегация, обобщение и агрегация покрытия – горизонтальными связями между типами сущностей этих деревьев. В целом для описания молекулярных типов RM/T в данной работе предлагается введение молекулярной структуры – дерева с горизонтальными связями – поверх атомарной структуры – n-мерного отношения. Такое дерево, очевидно, должно быть логическим, что позволит легко решать задачи переструризации дерева. Кроме того, должна поддерживаться возможность представления ассоциативной агрегации, обобщения и агрегации покрытия в виде логических деревьев. Суррогаты должны служить для упорядочивания кортежей отношений.
Логико-математический аппарат иерархической базы данных с горизонтальными связями, в общем случае, существенно сложнее, чем реляционных – последние лишь частный случай первых. Однако с созданием и развитием платформы XML появилась возможность формального описания иерархической модели с горизонтальными связями.

3. Платформа XML
XML (Extensible Markup Language) [2] – стандарт, который определяет синтаксис, позволяющий создавать собственные языки разметки документов. XML не содержит готового набора элемен-тов разметки (тегов), а описывает правила создания собственных тегов.
Главным достоинством XML является отделение друг от друга структурной разметки, форма-тирующей (визуального представления) разметки и семантики разметки. Следует отметить, что XML как таковой не предписывает какой-либо конкретный смысл применяемой разметке. Се-мантику разметки определяют использующие документы XML приложения.
Структура XML-документов
Главной конструкцией языка XML является XML-документ. Основными структурными едини-цами XML-документа являются элементы и атрибуты. XML-документ представляет собой на-бор вложенных друг в друга элементов, обладающих атрибутами. Элементы иерархически ор-ганизуют информацию, содержащуюся в документе. Элементы упорядочены, соответственно, существует определённый порядок обхода документа, для атрибутов порядок следования не имеет значения. Иерархическая организация информации в XML описывается древовидной структурой (рис. 6).

Рис. 6. XML-документ и дерево элементов

Таким образом, согласно спецификации XML, структура XML-документа представляет собой дерево упорядоченных элементов c атрибутами, такая структура соответствует основной пред-ложенной структуре модели данных RM/T и позволяет промоделировать предшествование со-бытий.
Описание структуры и ограничений целостности
Схема документа – это формальное описание структуры документа и семантических ограниче-ний, накладываемых на содержащиеся в документе данные. Знание схемы XML-документа по-зволяет относить его к определённому классу.
Все языки описания схем можно разбить на две группы: основанные на грамматике (DTD, XML Schema, RELAX NG [3]) и основанные на правилах (Schematron [4]).
Языки, основанные на грамматике, сосредотачиваются на явном объявлении схемы документа и определяют закрытую модель содержания XML-документа, что означает невозможность до-бавления в XML-документ новых элементов без их предварительного определения в схеме. Та-кие языки позволяют описывать древовидную структуру XML-документа.
Языки, основанные на правилах, сосредотачиваются на проверке допустимости конкретных до-кументов и определяют открытую модель содержания XML-документа. Каждое правило пред-ставляет собой ограничение целостности, выраженное языком XPath. С помощью правил мож-но обеспечить проверку допустимости ограничений, которые невозможно объявить в языках, основанных на грамматике. Такие языки позволяют описывать горизонтальные связи между элементами XML-документа и ограничения целостности.
Совместное использование языков, основанных на грамматике, и языков, основанных на прави-лах, позволяет описывать древовидные структуры с горизонтальными связями, то есть, струк-туры модели RM/T.
Операции с XML-документами
Объектная модель документа DOM (Document Object Model) [5] обеспечивает объектное пред-ставление XML-документов. Структура документа моделируется как дерево узлов-объектов различных типов (всего 12). Модель также включает полный набор низкоуровневых операций с узлами, то есть описывает функционально полную модель данных XML. Однако следует отме-тить, что, так как операции низкоуровневые, DOM предназначена, прежде всего, для програм-мистов.
Для более высокоуровневого манипулирования XML-данными в платформе XML используются языки XPath [6, 7] и XQuery [8].
Язык XPath предназначен для адресации отдельных частей XML-документа. Основу языка со-ставляют выражения различных типов, особо выделяются выражения пути – пути выборки. Пу-ти выборки позволяют выбирать в XML-документе последовательность узлов в соответствии с разнообразными критериями.
Язык запросов XQuery предназначен для извлечения информации из любых участков XML-документа и оформления ее в виде элементов XML-документа. Для поиска информации в XML-документе в XQuery используются выражения XPath.
По сравнению с XPath одних из основных дополнений, предусмотренных в XQuery, является способность формировать новые узлы. Поэтому в XQuery определяется такое понятие как кон-структор узлов. Конструктор узлов – это выражение, которое создает и добавляет к дереву до-кумента новые узлы.
Запрос к XML-документу записывается в виде выражения относительно переменных, которые принимают значения отобранных узлов, и содержит конструктор узлов, в котором используют-ся эти переменные.
Следует отметить, что язык Query предназначен только для чтения данных, поэтому для обнов-ления необходимо использовать DOM либо создавать собственные высокоуровневые средства на основе DOM.
Преобразование структуры XML-документа
Для преобразования структуры XML-документа используется язык XSLT [9, 10]. Таблица сти-лей, по которой идет преобразование, содержит правила, состоящие из двух частей: образцов для отбора узлов, предназначенных для преобразования, и шаблонов для построения преобра-зованных узлов. Результат преобразования может стать новым самостоятельным документом.
Модель данных XML
Из вышесказанного следует, что на основе языков платформы XML может быть построена мо-дель данных. Структурой данных этой модели является дерево элементов с горизонтальными связями, задаваемое базовой спецификацией XML, языками описания схем Relax NG, Schematron, элементы дерева упорядочены. Ограничения целостности задаются с помощью языков Relax NG, Schematron. Операции осуществляются с использованием DOM, XPath и XQuery. Преобразование структуры XML-документа осуществляется с использование XSLT.
И эта модель данных позволяет описать предложенную интерпретацию модели RM/T.
4. Расширенная модель данных

На основе предложенного подхода разработана расширенная реляционная модель данных, в которой иерархическая модель данных в варианте XML наложена как вторичная поверх реляционной. Это позволяет сохранить строгость реляционной модели и привнести в неё дополнительные преимущества иерархической модели, а также использовать для описания модели как реляционную алгебру, так и языки платформы XML: XML, Relax NG, Schematron, XPath, XQuery.
Основными структурными компонентами разработанной модели данных являются понятие, объект, экземпляр объекта, код экземпляра объекта, отображение.
Объекты соответствуют типам элементов XML-документа, экземпляры объектов – отдельным элементам, а понятия – атрибутам элементов. С другой точки зрения объекты соответствуют реляционным отношениям, экземпляры объектов – кортежам отношений, а понятия – атрибутам отношений (рис. 6).

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

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

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

5. Заключение
В данной работе предложена новая интерпретация расширенной реляционной модели данных RM/T. Согласно этой интерпретации молекулярные типы RM/T могут быть описаны молекулярной структурой – деревом с горизонтальными связями, которое накладывается поверх атомарной структуры – n-мерного отношения. Такое дерево является логическим, что позволяет легко решать задачи реструризации дерева. Поддерживается возможность представления ассоциативной агрегации, обобщения и агрегации покрытия в виде логических деревьев. Суррогаты служат для упорядочивания кортежей отношений.
Для описания этой интерпретации модели данных RM/T предложено использовать модель данных XML. Представляется краткое описание разработанной расширенной модели данных, основанной на модели данных RM/T, для описания которой используется модель данных XML.
Предложенная модель данных является основой разработанного инструмента для построения и использования информационных систем qWORD-XML [11]. Благодаря реализованной модели данных, а также унификации хранения, обработки и представления данных, инструмент qWORD-XML представляет собой удобную среду для быстрой и простой разработки, простого сопровождения и использования информационных систем.
С помощью инструмента qWORD-XML были разработаны Автоматизированная информацион-но-аналитическая система по проблемам инвалидности и инвалидов (АИС МСЭ) и Информаци-онно-аналитическая система органов социальной защиты населения субъекта федерации (АИС «Соцзащита»).

Литература:
1 Кодд Э.Ф. Расширение реляционной модели для лучшего отражения семантики. http://www.osp.ru/dbms/1996/05/163.htm
2 Extensible Markup Language (XML) 1.0. http://www.w3.org/TR/REC-xml/
3 Relax NG. http://relaxng.org/
4 The Schematron. http://xml.ascc.net/resource/schematron/
5 Document Object Model (DOM). http://www.w3.org/DOM/
6 XML Path Language (XPath) Version 1.0. http://www.w3.org/TR/xpath
7 XML Path Language (XPath) 2.0. http://www.w3.org/TR/xpath20/
8 XQuery 1.0: An XML Query Language. http://www.w3.org/TR/xquery/
9 XSL Transformations (XSLT) Version 1.0. http://www.w3.org/TR/xslt
10 XSL Transformations (XSLT) Version 2.0. http://www.w3.org/TR/xslt20/
11 Долженков А., Тимофеев Д. Семантический инструмент построения баз данных. «Открытые системы», №01/2006

Posted in Наши публикации | No Comments »

Реализация физического уровня для интерпретации расширенной реляционной модели RM/T

Понедельник, Июль 28th, 2008

Тимофеев Д.В.

Санкт-Петербургский институт информатики и автоматизации РАН

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

1. Введение

В работе [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. Реализация иерархических связей

2. Индексация

Наложение иерархии предполагает, что имеется возможность эффективной выборки записей в последовательности иерархического обхода. В данной работе предлагается задачу быстрого по-иска записей решать с помощью индексов, а задачу быстрого чтения записей с помощью кла-стерных индексов.
Индекс в общем случае представляет собой структуру, каждый элемент которой состоит из двух полей: ключа индекса и указателя на запись индексируемой таблицы (рис. 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 словарь значений понятия входит в состав некла-стерного индекса понятия при индексации и в состав прямого словаря понятия при кодирова-нии слов значений.
Для любого понятия может быть указано, что оно может принимать значения только из своего словаря значений. Кроме того, для понятия может быть указано, что оно может принимать зна-чения только из словаря значений некоторого другого понятия, при этом не важно, является ли такой словарь формируемым или предопределённым. В этом случае словарь значений пред-ставляет собой домен.
Возможность формирования словаря в процессе работы пользователей позволяет править мно-жество значений и их характеристики не непосредственно в словаре, а в рамках некоторого вы-сокоуровневого справочного отображения, доступного не только администратору базы данных, но и привилегированным пользователям.

4. Реализация физического уровня

Существует два возможных направления реализации физического уровня и системы в целом:
реализация с нуля;
реализация на основе какой-либо СУБД.
В первом варианте можно получить свободу и гибкость в принятии проектных решений, но при этом разработка потребует гораздо больше времени и усилий, кроме того, многие возможности существующих СУБД придётся реализовывать, по сути, заново.
Во втором варианте можно получить развитые возможности СУБД, например механизм управ-ления транзакциями, средства защиты данных, на разработку которых были затрачены значи-тельные усилия. Однако, если строить систему как надстройку над какой-либо 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’ в значительной степени ускоряют разработку приложений, однако, при эксплуатации информационной системы в качестве сервера можно использовать любую из систем.

5. Структуры хранения

На основании предложенного похода реализуются основные структуры хранения:
• кластерный индекс кодов экземпляров;
• некластерный индекс слов значений, прямой словарь значений, множество слов значений;
• обратный словарь значений.
Кластерный индекс без кодирования слов значений имеет следующий вид:
^Q(«ClInd»,Obj,Code,Woc)=Value
Value=Word1_» «_Word2_…_Wordn
Здесь Obj – код объекта, Сode – код экземпляра объекта, Woc – код понятия, Value – значение понятия экземпляра объекта, которое является списком слов (Word), разделённых пробелами.
Кластерный индекс с кодированием слов значений:
^Q(«ClInd»,Obj,Code,Woc)=ValueCode
ValueCode=Word1Code_» «_Word2Code_…_WordnCode
Здесь ValueCode – список кодов слов значения, WordiCode – код слова значения Wordi.
Множество слов значений, прямой словарь значений, некластерный индекс слов значений реа-лизуются в рамках единой структуры.
Множество слов значений:
^Q(«Woc»,Woc,Word)=»"
Прямой словарь значений:
^Q(«Woc»,Woc,Word)=WordCode
Некластерный индекс:
^Q(«Woc»,Woc,Word,Obj,Code)=WordNumber
Здесь WordNumber – номер слова в значение.
Соответственно, при одновременной индексации слов значений и кодировании слов значений получается следующая структура:
^Q(«Woc»,Woc,Word)=WordCode
^Q(«Woc»,Woc,Word,Obj,Code)=WordNumber
Обратный словарь значений имеет следующий вид:
^Q(«CWoc»,Woc,WordCode)=Word
Если для слов значений определены характеристики, то в обратный словарь добавляются новые узлы:
^Q(«CWoc»,Woc,WordCode,CharactNum)=CharactValue
Здесь CharactNum – номер характеристики, CharactValue – значение характеристики.
Соответственно, общая структура обратного словаря с характеристиками имеет следующий вид:
^Q(«CWoc»,Woc,WordCode)=Word
^Q(«CWoc»,Woc,WordCode,CharactNum)=CharactValue

6. Заключение

В качестве средства для реализации физического уровня предлагается использовать M-системы.
Для быстрого чтения экземпляров в последовательности иерархического обхода, необходимо обеспечить их хранение в непосредственной близости друг от друга. Для этого в данной работе предлагается в качестве основной структуры хранения использовать кластерный индекс кодов экземпляров. В кластерном индексе экземпляры каждого объекта хранятся в порядке кодов эк-земпляров вместе с данными экземпляров. Таким образом, код экземпляра на уровне хранения является ключом кластерного индекса.
Для быстрого поиска требуемых экземпляров реализуются некластерные индексы, которые ссылаются на коды экземпляров кластерного индекса.
Для устранения избыточности, свойственной иерархической организации данных, на физиче-ском уровне предлагается выполнять кодирование слов структурированных значений понятий суррогатными кодами. Для поддержки кодирование слов значений создаются дополнительные структуры хранения – прямой и обратный словари. Обратный словарь реализуется как кластер-ный индекс слов значений, что позволяет создавать характеристики слов значений. Ключом кластерного индекса является суррогатный код слова значения. Прямой словарь реализуется как некластерный индекс слов значений.
На основании предложенного подхода разработан инструмент для построения и использования информационных систем qWORD-XML [15]. Благодаря реализованной модели данных, а также унификации хранения, обработки и представления данных, инструмент qWORD-XML пред-ставляет собой удобную среду для быстрой и простой разработки, простого сопровождения и использования информационных систем.
С помощью инструмента qWORD-XML были разработаны Автоматизированная информацион-но-аналитическая система по проблемам инвалидности и инвалидов (АИС МСЭ) и Информаци-онно-аналитическая система органов социальной защиты населения субъекта федерации (АИС «Соцзащита»).

Литература:
1 Тимофеев Д.В. Использование платформы XML для описания расширенной реляционной модели данных RM/T
2 Кодд Э.Ф. Расширение реляционной модели для лучшего отражения семантики. http://www.osp.ru/dbms/1996/05/163.htm
3 Extensible Markup Language (XML) 1.0. http://www.w3.org/TR/REC-xml/
4 Relax NG. http://relaxng.org/
5 The Schematron. http://xml.ascc.net/resource/schematron/
6 Document Object Model (DOM). http://www.w3.org/DOM/
7 XML Path Language (XPath) Version 1.0. http://www.w3.org/TR/xpath
8 XML Path Language (XPath) 2.0. http://www.w3.org/TR/xpath20/
9 XQuery 1.0: An XML Query Language. http://www.w3.org/TR/xquery/
10 Гессе С., Кирстен В. Введение в язык программирования М. – СПб: АОЗТ «СП. АРМ», 1996 – 280с.
11 Кирстен В. От ANS MUMPS к ISO M. – СПб: СП.АРМ, 1995 – 277с.
12 Кирстен В и др. Постреляционная СУБД Cache 5: объектно-ориентированная разработка приложений. 2-е изд., перераб. и дополн. – М.: ООО «Бином-Пресс», 2005. – 416 с.
13 http://www.intersystems.ru/cache/index.html
14 http://www.sanchez-gtm.com/
15 Долженков А., Тимофеев Д. Семантический инструмент построения баз данных. «Открытые системы», №01/2006

Posted in Наши публикации | No Comments »