Тимофеев Д.В.
Санкт-Петербургский институт информатики и автоматизации РАН
В данной работе рассматривается реализация реляционных операций произведения и соедине-ния без создания дополнительных структур хранения и использование этих операций для логи-ческой переструктуризации иерархической структуры с горизонтальными связями – представ-ления горизонтальных связей как логических иерархических, инвертирования иерархии – в мо-дели данных, которая является интерпретацией расширенной реляционной модели данных RM/T.
1. Введение
В работе [1] была предложена интерпретация расширенной реляционной модели данных RM/T [2]. Согласно этой интерпретации молекулярные типы RM/T могут быть описаны структурой дерева с горизонтальными связями, дерево должно быть логическим, что позволит легко решать задачи переструктуризации дерева. Для такой структуры должна поддерживаться возможность представления горизонтальных связей в виде логических деревьев. Суррогаты 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] была предложена интерпретация расширенной реляционной модели данных RM/T [2]. Согласно этой интерпретации молекулярные типы RM/T могут быть описаны структурой дерева с горизонтальными связями, дерево должно быть логическим, что позволит легко решать задачи переструктуризации дерева. Для такой структуры должна поддерживаться возможность представления горизонтальных связей в виде логических деревьев. Суррогаты 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).
Для описания связей понятий с объектами, а также связей между объектами вводится ещё одна структура – отображение. Отображение включает схему дерева объектов и дерево экземпляров. Дерево объектов соответствует схеме ХML-документа и может быть описано с помощью языка Relax NG [4], а дерево экземпляров – множеству ХML-документов, удовлетворяющих этой схеме.
Базу данных предлагается моделировать как совокупность деревьев информационных объектов с горизонтальными связями и со специфичным для каждого объекта набором понятий.
Для идентификации отображений, объектов и понятий предлагается использовать уникальные в пределах базы данных короткие коды. Относительно этих кодов определяются ограничения це-лостности и операции.
Так как задачей является построение логической структуры с возможностью переструктуризации, то и иерархические связи, и горизонтальные связи реализуются только на основе значений понятий, таким образом, все связи являются информационными.
В код экземпляра помимо первичного позиционного ключа объекта, включаются также внешние ключи, ссылающиеся на экземпляры-предки данного экземпляра (рис. 2).
Рис. 2. Реализация иерархических связей
Используемый иерархический позиционный первичный ключ определяет уникальность экземпляра не только в пределах родительского экземпляра, но и в пределах любого экземпляра-предка. Используя метод редукции ключа, можно получить доступ к любому предку данного экземпляра объекта. Поэтому, несмотря на избыточность данных, данный ключ является наиболее предпочтительным, так как позволяет реализовать и поддерживать иерархические связи автоматически.
Горизонтальные связи реализуются пользователем с помощью механизмов пользовательских потенциальных и внешних ключей объектов.
В модели данных предусматриваются ограничения целостности: ограничения типов и понятий, ограничения объектов и ограничения базы данных. Ограничения целостности могут быть описаны с помощью языка Schematron [5]. Благодаря выбранной структуре кодов экземпляров, правила целостности сущностей и правила ссылочной целостности для иерархических связей поддерживаются автоматически.
В модели данных предлагается поддерживать не только спецификационные операции, но и навигационные операции манипулирования данными, так как они предоставляют большую гибкость и свободу в реализации конкретных задач. Навигационные операции соответствуют низкоуровневым операциям модели DOM [6] с некоторыми расширениями. Спецификационные операции соответствуют реляционной алгебре с расширением операций на деревья объектов. Спецификационные операции могут быть описаны с помощью языка XQuery [9].
В данной работе рассматриваются задачи логической переструктуризации дерева с горизонтальными связями в разработанной модели данных – задача представления горизонтальных связей в виде логических иерархических, задача инвертирования иерархии.
В реляционной алгебре выделяются две операции, связанные с созданием новых структур – это операции произведения и соединения. Результатом этих операций в общем случае является не-которое вычисляемое виртуальное отношение. Однако если на уровне модели такое отношение является виртуальным, то на физическом уровне всё равно создаются кортежи этого виртуаль-ного отношения.
Конкретной задачей работы является реализация операций произведения и соединения без соз-дания дополнительных физических записей только на основе хранимых объектов и экземпля-ров. Для построения логических структур, не соответствующих структуре хранимого дерева, в данной работе предлагаются механизмы ссылочных и виртуальных объектов.
В разработанной модели главной структурой является дерево объектов, соответственно, опера-ции реляционной алгебры, выполняющиеся над отношениями, распространяются на деревья объектов. Спецификационные операции, в том числе операции произведения и соединения, предлагается выполнять в рамках отображения.
Горизонтальные связи реализуются пользователем с помощью механизмов пользовательских потенциальных и внешних ключей объектов.
В модели данных предусматриваются ограничения целостности: ограничения типов и понятий, ограничения объектов и ограничения базы данных. Ограничения целостности могут быть описаны с помощью языка Schematron [5]. Благодаря выбранной структуре кодов экземпляров, правила целостности сущностей и правила ссылочной целостности для иерархических связей поддерживаются автоматически.
В модели данных предлагается поддерживать не только спецификационные операции, но и навигационные операции манипулирования данными, так как они предоставляют большую гибкость и свободу в реализации конкретных задач. Навигационные операции соответствуют низкоуровневым операциям модели DOM [6] с некоторыми расширениями. Спецификационные операции соответствуют реляционной алгебре с расширением операций на деревья объектов. Спецификационные операции могут быть описаны с помощью языка XQuery [9].
В данной работе рассматриваются задачи логической переструктуризации дерева с горизонтальными связями в разработанной модели данных – задача представления горизонтальных связей в виде логических иерархических, задача инвертирования иерархии.
В реляционной алгебре выделяются две операции, связанные с созданием новых структур – это операции произведения и соединения. Результатом этих операций в общем случае является не-которое вычисляемое виртуальное отношение. Однако если на уровне модели такое отношение является виртуальным, то на физическом уровне всё равно создаются кортежи этого виртуаль-ного отношения.
Конкретной задачей работы является реализация операций произведения и соединения без соз-дания дополнительных физических записей только на основе хранимых объектов и экземпля-ров. Для построения логических структур, не соответствующих структуре хранимого дерева, в данной работе предлагаются механизмы ссылочных и виртуальных объектов.
В разработанной модели главной структурой является дерево объектов, соответственно, опера-ции реляционной алгебры, выполняющиеся над отношениями, распространяются на деревья объектов. Спецификационные операции, в том числе операции произведения и соединения, предлагается выполнять в рамках отображения.
2. Произведение
В реляционной алгебре операция произведения возвращает отношение, кортежи которого яв-ляются сцеплением кортежей первого и второго операндов.
Операцию произведения с помощью реляционной алгебры можно записать так: A TIMES B
Ссылочные объекты являются механизмом переструктуризации хранимого дерева, они ссыла-ются только на экземпляры, реально существующие в базе данных. В общем случае при описа-нии ссылочного объекта необходимо задать выражение для получения следующего кода экзем-пляра относительно текущего экземпляра, направления перемещения и родительского экземп-ляра. Выражение записывается на языке программирования M [10, 11].
Текущий экземпляр определяется переменными qqo (код текущего объекта) и qqc (код текуще-го экземпляра), переменная qorder определяет текущее направление перемещения (-1 – к пре-дыдущему экземпляру, 1 – к следующему экземпляру, 0 – остаться на данном экземпляре).
Рассмотрим реализацию операции произведения объектов A и B с помощью ссылочных объек-тов (рис. 3).
Ссылочные объекты являются механизмом переструктуризации хранимого дерева, они ссыла-ются только на экземпляры, реально существующие в базе данных. В общем случае при описа-нии ссылочного объекта необходимо задать выражение для получения следующего кода экзем-пляра относительно текущего экземпляра, направления перемещения и родительского экземп-ляра. Выражение записывается на языке программирования M [10, 11].
Текущий экземпляр определяется переменными qqo (код текущего объекта) и qqc (код текуще-го экземпляра), переменная qorder определяет текущее направление перемещения (-1 – к пре-дыдущему экземпляру, 1 – к следующему экземпляру, 0 – остаться на данном экземпляре).
Рассмотрим реализацию операции произведения объектов A и B с помощью ссылочных объек-тов (рис. 3).
Рис. 3 Произведение с помощью ссылочных объектов
Для этого создаётся отображение, в котором объект А объявляется хранимым, объект B поме-щается под объект А и объявляется ссылочным, задаётся выражение для получения следующе-го кода экземпляра относительно текущего экземпляра, имеющее следующий вид:
$Select(qorder=0:qqc, 1:$$Ord(qorder, qqo, qqc, “”))
Данное выражение и использует реализованную в модели функцию навигации по дереву экзем-пляров объектов $$Ord для определения кода экземпляра и подразумевает обход всех экземпля-ров объекта B.
Для описания отображения используется формальный синтаксис Relax NG, изменённый с учё-том структурных компонентов разработанной модели. Отображение объявляется элементов view. Объекты, из которых состоит дерево, объявляются элементом оbj. Вложенность элемен-тов obj соответствует расположению объектов в иерархии дерева. Понятия объявляются эле-ментом woc. Понятия объявляются в пределах объявления объекта, которому они принадлежат. Для рассмотренного примера объявление отображения будет выглядеть следующим образом:
$Select(qorder=0:qqc, 1:$$Ord(qorder, qqo, qqc, “”)) Здесь указано, что объект B в отображении имеет тип ref (ссылочный), кроме того, в элементе ref/expr объекта задано выражение для получения следующего кода экземпляра.
В примере для каждого экземпляра объекта А в дерево экземпляров отображения будут выво-диться все экземпляры объекта B, то есть будет реализована операция произведения.
Операцию произведения с использованием ссылочных объектов можно описать следующим выражением XQuery:
let $base := doc(”base.xml”)
for $a in $base//a
return
{
for $b in $base//b
return
}
Дополнительно, для упрощения записи для ссылочных объектов вместо выражения для получе-ния следующего кода экземпляра в предлагаемой модели вводится список переходов. Выраже-ние для получения следующего кода экземпляра будет построено автоматически на основании списка переходов. Подробно списки переходов будут рассмотрены при обсуждении операции соединения, здесь же следует отметить, что в качестве списка переходов может быть указан код самого ссылочного объекта, в этом случае будут выводиться все экземпляры объекта.
Для данного примера, если в списке переходов указать код объекта B, то для каждого экземпля-ра объекта А будут выводиться все экземпляры объекта B.
Здесь в элементе ref объекта B задан список переходов – код объекта B.
Так как ссылочные объекты ссылаются на хранимые экземпляры, для них допустимы операции коррекции значений, создания и удаления экземпляров.
Виртуальные объекты являются механизмом построения виртуальных деревьев объектов. Вир-туальные объекты используются для представления данных как существующих, так и не суще-ствующих в базе данных. В отличие от ссылочных объектов поведение виртуальных объектов полностью определяется пользователем.
Для виртуального объекта пользователю необходимо определить операцию для получения сле-дующего кода экземпляра относительно текущего экземпляра, направления перемещения и ро-дительского экземпляра. Операция также должна возвращать значения понятий для полученно-го экземпляра. Операция реализуется на языке программирования M [10, 11].
Операция имеет следующий вид:
СodeRes = $$gOrder(Order, Obj, Code, Сode0,.Values)
Параметры операции:
Order – направление перемещения по экземплярам (-1, 1, 0);
Obj – код виртуального объекта;
Code – текущий код экземпляра виртуального объекта;
Code0 – код экземпляра объекта-родителя.
Значение, возвращаемое операцией:
CodeRes – следующий/предыдущий код экземпляра виртуального объекта относительно на-правления перемещения, текущего кода экземпляра и текущего кода экземпляра объекта-родителя. Если операция возвращает “”, то происходит переход к следующему коду экземпляра объекта-родителя.
Все значения понятий должны быть записаны в массив следующего вида:
Values(Woc)=Value
Здесь:
Woc – код понятия;
Value – значение понятия.
Код экземпляра виртуального объекта может быть сформирован любым образом, удобным для пользователя.
Рассмотрим реализацию операции произведения для объектов А и В с использованием вирту-ального объекта (рис. 4).
$Select(qorder=0:qqc, 1:$$Ord(qorder, qqo, qqc, “”))
Данное выражение и использует реализованную в модели функцию навигации по дереву экзем-пляров объектов $$Ord для определения кода экземпляра и подразумевает обход всех экземпля-ров объекта B.
Для описания отображения используется формальный синтаксис Relax NG, изменённый с учё-том структурных компонентов разработанной модели. Отображение объявляется элементов view. Объекты, из которых состоит дерево, объявляются элементом оbj. Вложенность элемен-тов obj соответствует расположению объектов в иерархии дерева. Понятия объявляются эле-ментом woc. Понятия объявляются в пределах объявления объекта, которому они принадлежат. Для рассмотренного примера объявление отображения будет выглядеть следующим образом:
$Select(qorder=0:qqc, 1:$$Ord(qorder, qqo, qqc, “”)) Здесь указано, что объект B в отображении имеет тип ref (ссылочный), кроме того, в элементе ref/expr объекта задано выражение для получения следующего кода экземпляра.
В примере для каждого экземпляра объекта А в дерево экземпляров отображения будут выво-диться все экземпляры объекта B, то есть будет реализована операция произведения.
Операцию произведения с использованием ссылочных объектов можно описать следующим выражением XQuery:
let $base := doc(”base.xml”)
for $a in $base//a
return
{
for $b in $base//b
return
}
Дополнительно, для упрощения записи для ссылочных объектов вместо выражения для получе-ния следующего кода экземпляра в предлагаемой модели вводится список переходов. Выраже-ние для получения следующего кода экземпляра будет построено автоматически на основании списка переходов. Подробно списки переходов будут рассмотрены при обсуждении операции соединения, здесь же следует отметить, что в качестве списка переходов может быть указан код самого ссылочного объекта, в этом случае будут выводиться все экземпляры объекта.
Для данного примера, если в списке переходов указать код объекта B, то для каждого экземпля-ра объекта А будут выводиться все экземпляры объекта B.
Здесь в элементе ref объекта B задан список переходов – код объекта B.
Так как ссылочные объекты ссылаются на хранимые экземпляры, для них допустимы операции коррекции значений, создания и удаления экземпляров.
Виртуальные объекты являются механизмом построения виртуальных деревьев объектов. Вир-туальные объекты используются для представления данных как существующих, так и не суще-ствующих в базе данных. В отличие от ссылочных объектов поведение виртуальных объектов полностью определяется пользователем.
Для виртуального объекта пользователю необходимо определить операцию для получения сле-дующего кода экземпляра относительно текущего экземпляра, направления перемещения и ро-дительского экземпляра. Операция также должна возвращать значения понятий для полученно-го экземпляра. Операция реализуется на языке программирования M [10, 11].
Операция имеет следующий вид:
СodeRes = $$gOrder(Order, Obj, Code, Сode0,.Values)
Параметры операции:
Order – направление перемещения по экземплярам (-1, 1, 0);
Obj – код виртуального объекта;
Code – текущий код экземпляра виртуального объекта;
Code0 – код экземпляра объекта-родителя.
Значение, возвращаемое операцией:
CodeRes – следующий/предыдущий код экземпляра виртуального объекта относительно на-правления перемещения, текущего кода экземпляра и текущего кода экземпляра объекта-родителя. Если операция возвращает “”, то происходит переход к следующему коду экземпляра объекта-родителя.
Все значения понятий должны быть записаны в массив следующего вида:
Values(Woc)=Value
Здесь:
Woc – код понятия;
Value – значение понятия.
Код экземпляра виртуального объекта может быть сформирован любым образом, удобным для пользователя.
Рассмотрим реализацию операции произведения для объектов А и В с использованием вирту-ального объекта (рис. 4).
Рис. 4. Произведение с помощью виртуальных объектов
Для этого создаётся объект АВ и отображение, в котором объект АB объявляется виртуальным. Далее для объекта АВ задаётся операция gOrder для получения следующего кода экземпляра и значений понятий экземпляра (рис. 5) и записывается вызов этой операции в свойствах объекта.
$$gOrder(qorder, qqo, qqc, “”, .values) Здесь указано, что объект B в отображении имеет тип virt (виртуальный), кроме того, в элемен-те ref/expr объекта задан вызов операции для получения следующего кода экземпляров и значе-ний понятий.
Для данного примера операция gOrder будет иметь следующий вид:
gOrder(order, obj, code, code0, .Values)
{
kill Values(”SName”), Values(”PName”)
new codeA, codeB
set codeA = $extract(code, 1, 2)
set codeB = $extract(code, 3, 4)
$$gOrder(qorder, qqo, qqc, “”, .values) Здесь указано, что объект B в отображении имеет тип virt (виртуальный), кроме того, в элемен-те ref/expr объекта задан вызов операции для получения следующего кода экземпляров и значе-ний понятий.
Для данного примера операция gOrder будет иметь следующий вид:
gOrder(order, obj, code, code0, .Values)
{
kill Values(”SName”), Values(”PName”)
new codeA, codeB
set codeA = $extract(code, 1, 2)
set codeB = $extract(code, 3, 4)
if order ‘= 0 {
set codeB = $$Ord(order, “B”, codeB, “”)
if codeB = “” {
set codeA = $$Ord(order, “A”, codeA, “”)
if codeA’=”" set codeB = $$Ord(order, “B”, codeB,”")
}
else if codeA = “” set codeA = $$Ord(order, “A”, codeA,”")
}
if codeA ‘= “”, codeB ‘= “” {
set Values(”SName”) = $$Get(”A”, “SName”, codeA)
set Values(”PName”) = $$Get(”B”, “PName”, codeB)
}
quit codeA_codeB
}
Рис. 5. Операция получения следующего кода экземпляра и значений понятий
Операция gOrder возвращает коды экземпляров, которые являются сцеплением кодов экземпля-ров объектов А и В, первые два символа кода экземпляра определяются кодом экземпляра объ-екта А, последние два символа – кодом экземпляра объекта В. Значения понятий берутся из со-ответствующих экземпляров объектов-операндов. Таким образом, операция gOrder моделирует операцию произведения.
Операцию произведения с использованием виртуальных объектов можно описать следующим выражением XQuery:
let $base := doc(”base.xml”)
for $a in $base//a
for $b in $base//b
return
{ $a/(*|@*[name() != "code"]) }
{ $b/(*|@*[name() != "code"]) }
Так как экземпляры виртуальных объектов не являются хранимыми, для них запрещены опера-ции создания экземпляров, коррекции значений и удаления экземпляров. Однако эти операции могут быть реализованы пользователем в триггерном действии вместо операции.
Подытожим сказанное о ссылочных и виртуальных объектах. Ссылочные объекты ссылаются на объекты, реально существующие в базе данных, для них операции манипулирования под-держиваются системой. Экземпляры виртуальных объектов не существуют в базе, а создаются пользователем, соответственно, операции манипулирования виртуальным объектом также должны определяться пользователем.
Так как код экземпляра ссылочного объекта есть код экземпляра хранимого объекта, то к тако-му ссылочному объекту можно достраивать потомков этого хранимого объекта. Для того чтобы достроить потомков к виртуальному объекту необходимо использовать ссылочные объекты и задавать для них операцию получения следующего кода экземпляра.
Соединение
В реляционной алгебре операция соединения (?-соединения) возвращает отношение, кортежи которого являются сцеплением кортежей первого и второго отношений и удовлетворяют неко-торому условию.
Эта операция может быть определена на основе операции произведения и выборки следующим образом:
A TIMES B WHERE X ? Y, где
А, В – деревья экземпляров;
X – понятие объекта А;
Y – понятие объекта B;
? – оператор сравнения.
В предлагаемой модели операция произведения может быть реализована с использованием ссылочных или виртуальных объектов. Условие может быть задано для каждого объекта в де-реве объектов либо в выражении для получения следующего кода экземпляра (для ссылочного объекта) или в операции gOrder (для виртуального объекта).
В реляционной алгебре если оператор ? является оператором равенства «=», то такое соедине-ние называется равно-соединением. Результирующее отношение будет включать два атрибута, значения которых в каждом картеже равны. Если исключить один из этих атрибутов, то такое соединение будет называться естественным. Формально эту операцию можно записать сле-дующим образом:
A JOIN B ? A TIMES B WHERE X = Y
В предлагаемой модели перечень понятий каждого объекта задаётся в дерева объектов отобра-жения, кроме того, операция проекции может осуществляться в рамках отображения.
Для упрощения записи операции равно-соединения или естественного соединения с помощью ссылочных объектов в предлагаемой модели вводится список переходов. Список переходов – это список объектов, для которых текущий объект используется как ссылочный. Связь устанав-ливается через равные значения понятий текущего объекта и объектов списка. На основании списка переходов автоматически строится выражение для получения следующего кода экземп-ляра.
С помощью синтаксиса XML список переходов можно определить следующим образом:
Здесь:
Obji – код объекта, для которого текущий объект может быть ссылочным;
Woc0ij – понятие текущего объекта, по значениям которого осуществляется связь;
Wocij – соответствующее понятие объекта Obji, по значениям которого осуществляется связь.
Если код понятия текущего объекта и объекта Obji совпадает, то код понятия объекта Obji мо-жет быть опущен.
Если А – множество экземпляров текущего объекта, то список переходов может быть описан следующим выражением реляционной алгебры:
A REF Obji = (Obji TIMES A WHERE Woc0i1=Woci1 AND … AND Woc0im=Wocim)
Тогда операция соединения определяется на основании списка переходов и операции произве-дения:
Obji JOIN A = Obji TIMES (A REF Obji)
Рассмотрим пример, пусть имеются объекты А и В, в которых пользовательскими потенциаль-ными ключами являются понятия S и P соответственно, и объект АВ, который в реляционном смысле является ассоциацией объектов А и В. Объект АВ содержит пользовательские внешние ключи – S и P, ссылающиеся на соответствующие понятия объектов А и В. То есть, между объ-ектом А и объектом АB, а также между объектом B и объектом АВ реализованы горизонталь-ные связи (рис. 6).
Операцию произведения с использованием виртуальных объектов можно описать следующим выражением XQuery:
let $base := doc(”base.xml”)
for $a in $base//a
for $b in $base//b
return
{ $a/(*|@*[name() != "code"]) }
{ $b/(*|@*[name() != "code"]) }
Так как экземпляры виртуальных объектов не являются хранимыми, для них запрещены опера-ции создания экземпляров, коррекции значений и удаления экземпляров. Однако эти операции могут быть реализованы пользователем в триггерном действии вместо операции.
Подытожим сказанное о ссылочных и виртуальных объектах. Ссылочные объекты ссылаются на объекты, реально существующие в базе данных, для них операции манипулирования под-держиваются системой. Экземпляры виртуальных объектов не существуют в базе, а создаются пользователем, соответственно, операции манипулирования виртуальным объектом также должны определяться пользователем.
Так как код экземпляра ссылочного объекта есть код экземпляра хранимого объекта, то к тако-му ссылочному объекту можно достраивать потомков этого хранимого объекта. Для того чтобы достроить потомков к виртуальному объекту необходимо использовать ссылочные объекты и задавать для них операцию получения следующего кода экземпляра.
Соединение
В реляционной алгебре операция соединения (?-соединения) возвращает отношение, кортежи которого являются сцеплением кортежей первого и второго отношений и удовлетворяют неко-торому условию.
Эта операция может быть определена на основе операции произведения и выборки следующим образом:
A TIMES B WHERE X ? Y, где
А, В – деревья экземпляров;
X – понятие объекта А;
Y – понятие объекта B;
? – оператор сравнения.
В предлагаемой модели операция произведения может быть реализована с использованием ссылочных или виртуальных объектов. Условие может быть задано для каждого объекта в де-реве объектов либо в выражении для получения следующего кода экземпляра (для ссылочного объекта) или в операции gOrder (для виртуального объекта).
В реляционной алгебре если оператор ? является оператором равенства «=», то такое соедине-ние называется равно-соединением. Результирующее отношение будет включать два атрибута, значения которых в каждом картеже равны. Если исключить один из этих атрибутов, то такое соединение будет называться естественным. Формально эту операцию можно записать сле-дующим образом:
A JOIN B ? A TIMES B WHERE X = Y
В предлагаемой модели перечень понятий каждого объекта задаётся в дерева объектов отобра-жения, кроме того, операция проекции может осуществляться в рамках отображения.
Для упрощения записи операции равно-соединения или естественного соединения с помощью ссылочных объектов в предлагаемой модели вводится список переходов. Список переходов – это список объектов, для которых текущий объект используется как ссылочный. Связь устанав-ливается через равные значения понятий текущего объекта и объектов списка. На основании списка переходов автоматически строится выражение для получения следующего кода экземп-ляра.
С помощью синтаксиса XML список переходов можно определить следующим образом:
Здесь:
Obji – код объекта, для которого текущий объект может быть ссылочным;
Woc0ij – понятие текущего объекта, по значениям которого осуществляется связь;
Wocij – соответствующее понятие объекта Obji, по значениям которого осуществляется связь.
Если код понятия текущего объекта и объекта Obji совпадает, то код понятия объекта Obji мо-жет быть опущен.
Если А – множество экземпляров текущего объекта, то список переходов может быть описан следующим выражением реляционной алгебры:
A REF Obji = (Obji TIMES A WHERE Woc0i1=Woci1 AND … AND Woc0im=Wocim)
Тогда операция соединения определяется на основании списка переходов и операции произве-дения:
Obji JOIN A = Obji TIMES (A REF Obji)
Рассмотрим пример, пусть имеются объекты А и В, в которых пользовательскими потенциаль-ными ключами являются понятия S и P соответственно, и объект АВ, который в реляционном смысле является ассоциацией объектов А и В. Объект АВ содержит пользовательские внешние ключи – S и P, ссылающиеся на соответствующие понятия объектов А и В. То есть, между объ-ектом А и объектом АB, а также между объектом B и объектом АВ реализованы горизонталь-ные связи (рис. 6).
Рис. 6. Соединение с помощью ссылочных объектов
Для реализации операции соединения в отображении объект АВ объявляется хранимым, объек-ты А и B помещаются под объект АВ как дочерние и объявляются ссылочными. Для объекта А задаётся список переходов AB:S, для объекта B – список переходов AB:P, соответственно, реа-лизуются операции соединения AB JOIN A и AB JOIN B.
Здесь указано, что объекты A и B в отображении имеет тип ref (ссылочный), кроме того, с по-мощью элемента ref заданы списки переходов для объектов.
Операцию соединения с использованием ссылочных объектов можно описать следующим вы-ражением XQuery:
let $base := doc(”base.xml”)
for $ab in $base//ab
return
Здесь указано, что объекты A и B в отображении имеет тип ref (ссылочный), кроме того, с по-мощью элемента ref заданы списки переходов для объектов.
Операцию соединения с использованием ссылочных объектов можно описать следующим вы-ражением XQuery:
let $base := doc(”base.xml”)
for $ab in $base//ab
return
{
for $a in $base//a
where $ab/@s = $a/@s
return $a
}
{
for $b in $base//b
where $ab/@p = $b/@p
return $b
}
Таким образом, с помощью ссылочных объектов горизонтальные связи представляются как ло-гические иерархические связи. Очевидно, такое представление является более наглядным и ин-туитивно понятным для пользователя.
Собственно иерархические связи по кодам экземпляров в предлагаемой модели также пред-ставляют собой реализацию операций соединения между экземплярами родительского объекта (A) и экземплярами дочернего объекта (B) (рис. 7): A JOIN B.
Рис. 7. Реализация иерархических связей
Такие операции выполняются системой автоматически на основании структуры отображения
и могут быть описаны с помощью следующего выражения XQuery:
let $base := doc(”base.xml”)
for $a in $base//a
return
{
for $b in $base//b
where substring($b/@code, 1, $len) = $a/@code
return $b
}
Здесь $len – длина кода экземпляра объекта A, функция substring выделяет из кода экземпляра объекта B значение внешнего ключа, ссылающегося на код экземпляра объекта А.
С помощью ссылочных объектов также предлагается решать задачу инвертирования иерархии по кодам экземпляров. В качестве списка переходов для ссылочных объектов может быть ука-зан код объекта-предка для данного объекта. В этом случае связь осуществляется по кодам эк-земпляров, и в дерево экземпляров попадут те экземпляры объекта, которые являются потомка-ми для экземпляра объекта-предка. Код экземпляра объекта-предка определяется по родитель-скому для ссылочного объекта объекту в отображении. Если в отображении нет родительского объекта для ссылочного или этот родительский объект в отображении не входит в подсхему ба-зы данных, включающую ссылочный объект, то в дерево экземпляров попадут все экземпляры ссылочного объекта. Если в качестве кода объекта-предка указан код самого ссылочного объек-та, то в дерево экземпляров попадёт только один экземпляр для каждого экземпляра объекта-предка.
Дополним предыдущий пример объектом С, дочерним для объекта В, и рассмотрим два вариан-та инвертирования иерархии (рис. 8).
Рис. 8. Инвертирование иерархии
В обоих случаях в отображение помещается объект С как хранимый, под него помещается объ-ект B, который объявляется ссылочным. В списке переходов в первом случае указывается объ-ект А, во втором – объект В.
Для первого случая код экземпляра объекта А (объект-предок) содержится в коде экземпляра объекта С (родительский объект в отображении), в данном случае это код равен А. Соответст-венно, в дерево экземпляров попадут дочерние для А:A экземпляры объекта В – AА и АВ.
Для второго случая код экземпляра объекта В (объект-предок) содержится в коде экземпляра объекта С (родительский объект в отображении), в данном случае это коды АА и АВ. Соответ-ственно, в дерево экземпляров попадут «дочерний» для B:АА экземпляр объекта В, то есть, сам экземпляр AА, а также «дочерний» для B:АB экземпляр объекта В – AB.
Таким образом, в первом случае фактически реализуется операция:
C JOIN A JOIN B ,
а во втором случае операция:
C JOIN B JOIN B ? C JOIN B
С использование XQuery эти операции могут быть описаны следующим образом.
Для первого случая:
let $base := doc(”base.xml”)
for $c in $base//c
return
{
for $a in $base//a
for $b in $base//b
where $a/@code = substring($c/@code, 1, $len_a) and
substring($b/@code, 1, $len_a) = $a/@code
return $b
}
Для второго случая:
let $base := doc(”base.xml”)
for $c in $base//c
return
let $base := doc(”base.xml”)
for $c in $base//c
return
{
for $b in $base//b
where $b/@code = substring($c/@code, 1, $len_b)
return $b
}
4. Заключение
В разработанной модели данных с помощью предложенных механизмов ссылочных и виртуальных объектов реализуются операции произведения и соединения без создания дополнительных структур хранения, решается задача представления горизонтальных связей как логических иерархических, задача инвертирования иерархии.
Ссылочные объекты ссылаются на экземпляры объектов, реально существующие в базе данных, при этом операции манипулирования экземплярами ссылочных объектов поддерживаются сис-темой. Виртуальные объекты позволяют создавать виртуальные деревья объектов. Операции манипулирования экземплярами должны реализовываться пользователем. Виртуальные объек-ты предоставляют большую свободу и гибкость, однако большинство задач может быть решено с использованием ссылочных объектов.
Предложенная модель данных является основой разработанного инструмента для построения и использования информационных систем qWORD-XML [10]. Благодаря реализованной модели данных, а также унификации хранения, обработки и представления данных, инструмент qWORD-XML представляет собой удобную среду для быстрой и простой разработки, простого сопровождения и использования информационных систем.
С помощью инструмента qWORD-XML были разработаны Автоматизированная информацион-но-аналитическая система по проблемам инвалидности и инвалидов (АИС МСЭ) и Информаци-онно-аналитическая система органов социальной защиты населения субъекта федерации (АИС «Соцзащита»).
В разработанной модели данных с помощью предложенных механизмов ссылочных и виртуальных объектов реализуются операции произведения и соединения без создания дополнительных структур хранения, решается задача представления горизонтальных связей как логических иерархических, задача инвертирования иерархии.
Ссылочные объекты ссылаются на экземпляры объектов, реально существующие в базе данных, при этом операции манипулирования экземплярами ссылочных объектов поддерживаются сис-темой. Виртуальные объекты позволяют создавать виртуальные деревья объектов. Операции манипулирования экземплярами должны реализовываться пользователем. Виртуальные объек-ты предоставляют большую свободу и гибкость, однако большинство задач может быть решено с использованием ссылочных объектов.
Предложенная модель данных является основой разработанного инструмента для построения и использования информационных систем qWORD-XML [10]. Благодаря реализованной модели данных, а также унификации хранения, обработки и представления данных, инструмент 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 Долженков А., Тимофеев Д. Семантический инструмент построения баз данных. «Открытые системы», №01/2006
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 Долженков А., Тимофеев Д. Семантический инструмент построения баз данных. «Открытые системы», №01/2006