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-документа, экземпляры объектов – отдельным элементам, а понятия – атрибутам элементов. С другой точки зрения объекты соответствуют реляционным отношениям, экземпляры объектов – кортежам отношений, а понятия – атрибутам отношений.
Если с точки зрения XML позиция элемента это ключ естественный, то чисто с реляционной точки зрения он видится как ключ суррогатный. В разработанной модели данных этот ключ называется кодом экземпляра объекта.
Для описания связей понятий с объектами, а также связей между объектами вводится ещё одна структура – отображение. Отображение включает схему дерева объектов и дерево экземпляров. Дерево объектов соответствует схеме ХML-документа и может быть описано с помощью языка Relax NG [4], а дерево экземпляров – множеству ХML-документов, удовлетворяющих этой схеме.
Базу данных предлагается моделировать как совокупность деревьев информационных объектов с горизонтальными связями и со специфичным для каждого объекта набором понятий.
Для идентификации отображений, объектов и понятий предлагается использовать уникальные в пределах базы данных короткие коды. Относительно этих кодов определяются ограничения целостности и операции.
Так как задачей является построение логической структуры с возможностью переструктуризации, то и иерархические связи, и горизонтальные связи реализуются только на основе значений понятий, таким образом, все связи являются информационными.
В код экземпляра помимо первичного позиционного ключа объекта, включаются также внешние ключи, ссылающиеся на экземпляры-предки данного экземпляра.
Используемый иерархический позиционный первичный ключ определяет уникальность экземпляра не только в пределах родительского экземпляра, но и в пределах любого экземпляра-предка. Используя метод редукции ключа, можно получить доступ к любому предку данного экземпляра объекта. Поэтому, несмотря на избыточность данных, данный ключ является наиболее предпочтительным, так как позволяет реализовать и поддерживать иерархические связи автоматически.
Горизонтальные связи реализуются пользователем с помощью механизмов пользовательских потенциальных и внешних ключей объектов.
В модели данных предусматриваются ограничения целостности: ограничения типов и понятий, ограничения объектов и ограничения базы данных. Ограничения целостности могут быть описаны с помощью языка Schematron [5]. Благодаря выбранной структуре кодов экземпляров, правила целостности сущностей и правила ссылочной целостности для иерархических связей поддерживаются автоматически.
В модели данных предлагается поддерживать не только спецификационные операции, но и навигационные операции манипулирования данными, так как они предоставляют большую гибкость и свободу в реализации конкретных задач. Навигационные операции соответствуют низкоуровневым операциям модели DOM [6] с некоторыми расширениями. Спецификационные операции соответствуют реляционной алгебре с расширением операций на деревья объектов. Спецификационные операции могут быть описаны с помощью языка XQuery [9].
В данной работе рассматриваются задачи логической переструктуризации дерева с горизонтальными связями в разработанной модели данных – задача представления горизонтальных связей в виде логических иерархических, задача инвертирования иерархии.
В реляционной алгебре выделяются две операции, связанные с созданием новых структур – это операции произведения и соединения. Результатом этих операций в общем случае является некоторое вычисляемое виртуальное отношение. Однако если на уровне модели такое отношение является виртуальным, то на физическом уровне всё равно создаются кортежи этого виртуального отношения.
Конкретной задачей работы является реализация операций произведения и соединения без создания дополнительных физических записей только на основе хранимых объектов и экземпляров. Для построения логических структур, не соответствующих структуре хранимого дерева, в данной работе предлагаются механизмы ссылочных и виртуальных объектов.
В разработанной модели главной структурой является дерево объектов, соответственно, операции реляционной алгебры, выполняющиеся над отношениями, распространяются на деревья объектов. Спецификационные операции, в том числе операции произведения и соединения, предлагается выполнять в рамках отображения.
2. Произведение
В реляционной алгебре операция произведения возвращает отношение, кортежи которого являются сцеплением кортежей первого и второго операндов.
Операцию произведения с помощью реляционной алгебры можно записать так: A TIMES B
Ссылочные объекты являются механизмом переструктуризации хранимого дерева, они ссылаются только на экземпляры, реально существующие в базе данных. В общем случае при описании ссылочного объекта необходимо задать выражение для получения следующего кода экземпляра относительно текущего экземпляра, направления перемещения и родительского экземпляра. Выражение записывается на языке программирования M [10, 11].
Текущий экземпляр определяется переменными qqo (код текущего объекта) и qqc (код текущего экземпляра), переменная qorder определяет текущее направление перемещения (-1 – к предыдущему экземпляру, 1 – к следующему экземпляру, 0 – остаться на данном экземпляре).
Рассмотрим реализацию операции произведения объектов A и B с помощью ссылочных объектов.
Для этого создаётся отображение, в котором объект А объявляется хранимым, объект B помещается под объект А и объявляется ссылочным, задаётся выражение для получения следующего кода экземпляра относительно текущего экземпляра, имеющее следующий вид:
$Select(qorder=0:qqc, 1:$$Ord(qorder, qqo, qqc, «»))
Данное выражение и использует реализованную в модели функцию навигации по дереву экземпляров объектов $$Ord для определения кода экземпляра и подразумевает обход всех экземпляров объекта B.
Для описания отображения используется формальный синтаксис Relax NG, изменённый с учётом структурных компонентов разработанной модели. Отображение объявляется элементов view. Объекты, из которых состоит дерево, объявляются элементом оbj. Вложенность элементов obj соответствует расположению объектов в иерархии дерева. Понятия объявляются элементом woc. Понятия объявляются в пределах объявления объекта, которому они принадлежат. Для рассмотренного примера объявление отображения будет выглядеть следующим образом:
<view code=»pr_ref»>
<obj code=»a»>
<woc code=»sname»/>
<obj code=»b» type=»ref»>
<woc code=»pname»/>
<ref>
<expr>$Select(qorder=0:qqc, 1:$$Ord(qorder, qqo, qqc, «»))</expr>
</ref>
</obj>
</obj>
</view>
Здесь указано, что объект B в отображении имеет тип ref (ссылочный), кроме того, в элементе ref/expr объекта задано выражение для получения следующего кода экземпляра.
В примере для каждого экземпляра объекта А в дерево экземпляров отображения будут выводиться все экземпляры объекта B, то есть будет реализована операция произведения.
Операцию произведения с использованием ссылочных объектов можно описать следующим выражением XQuery:
let $base := doc(«base.xml»)
for $a in $base//a
return
<a>
{$a/(*|@*)}
{
for $b in $base//b
return {$b}
}
</a>
Дополнительно, для упрощения записи для ссылочных объектов вместо выражения для получения следующего кода экземпляра в предлагаемой модели вводится список переходов. Выражение для получения следующего кода экземпляра будет построено автоматически на основании списка переходов. Подробно списки переходов будут рассмотрены при обсуждении операции соединения, здесь же следует отметить, что в качестве списка переходов может быть указан код самого ссылочного объекта, в этом случае будут выводиться все экземпляры объекта.
Для данного примера, если в списке переходов указать код объекта B, то для каждого экземпляра объекта А будут выводиться все экземпляры объекта B.
<view code=»pr_ref»>
<obj code=»a»>
<woc code=»sname»/>
<obj code=»b» type=»ref»>
<woc code=»pname»/>
<ref ref=»b»/>
</obj>
</obj>
</view>
Здесь в элементе 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 – значение понятия.
Код экземпляра виртуального объекта может быть сформирован любым образом, удобным для пользователя.
Рассмотрим реализацию операции произведения для объектов А и В с использованием виртуального объекта.
Для этого создаётся объект АВ и отображение, в котором объект АB объявляется виртуальным. Далее для объекта АВ задаётся операция gOrder для получения следующего кода экземпляра и значений понятий экземпляра (рис. 5) и записывается вызов этой операции в свойствах объекта.
<view code=»pr_virt»>
<obj code=»ab» type=»virt»>
<woc code=»sname»/>
<woc code=»pname»/>
<ref>
<expr>$$gOrder(qorder, qqo, qqc, «», .values)</expr>
</ref>
</obj>
</view>
Здесь указано, что объект 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 } |
| Операция получения следующего кода экземпляра и значений понятий |
Операция gOrder возвращает коды экземпляров, которые являются сцеплением кодов экземпляров объектов А и В, первые два символа кода экземпляра определяются кодом экземпляра объекта А, последние два символа – кодом экземпляра объекта В. Значения понятий берутся из соответствующих экземпляров объектов-операндов. Таким образом, операция gOrder моделирует операцию произведения.
Операцию произведения с использованием виртуальных объектов можно описать следующим выражением XQuery:
let $base := doc(«base.xml»)
for $a in $base//a
for $b in $base//b
return
<ab code=»{concat($a/@code, $b/@code)}»>
{ $a/(*|@*[name() != «code»]) }
{ $b/(*|@*[name() != «code»]) }
</ab>
Так как экземпляры виртуальных объектов не являются хранимыми, для них запрещены операции создания экземпляров, коррекции значений и удаления экземпляров. Однако эти операции могут быть реализованы пользователем в триггерном действии вместо операции.
Подытожим сказанное о ссылочных и виртуальных объектах. Ссылочные объекты ссылаются на объекты, реально существующие в базе данных, для них операции манипулирования поддерживаются системой. Экземпляры виртуальных объектов не существуют в базе, а создаются пользователем, соответственно, операции манипулирования виртуальным объектом также должны определяться пользователем.
Так как код экземпляра ссылочного объекта есть код экземпляра хранимого объекта, то к такому ссылочному объекту можно достраивать потомков этого хранимого объекта. Для того чтобы достроить потомков к виртуальному объекту необходимо использовать ссылочные объекты и задавать для них операцию получения следующего кода экземпляра.
Соединение
В реляционной алгебре операция соединения (Q-соединения) возвращает отношение, кортежи которого являются сцеплением кортежей первого и второго отношений и удовлетворяют некоторому условию.
Эта операция может быть определена на основе операции произведения и выборки следующим образом:
A TIMES B WHERE X Q Y, где
А, В – деревья экземпляров;
X – понятие объекта А;
Y – понятие объекта B;
Q – оператор сравнения.
В предлагаемой модели операция произведения может быть реализована с использованием ссылочных или виртуальных объектов. Условие может быть задано для каждого объекта в дереве объектов либо в выражении для получения следующего кода экземпляра (для ссылочного объекта) или в операции gOrder (для виртуального объекта).
В реляционной алгебре если оператор Q является оператором равенства «=», то такое соединение называется равно-соединением. Результирующее отношение будет включать два атрибута, значения которых в каждом картеже равны. Если исключить один из этих атрибутов, то такое соединение будет называться естественным. Формально эту операцию можно записать следующим образом:
A JOIN B º A TIMES B WHERE X = Y {ALL BUT X}
В предлагаемой модели перечень понятий каждого объекта задаётся в дерева объектов отображения, кроме того, операция проекции может осуществляться в рамках отображения.
Для упрощения записи операции равно-соединения или естественного соединения с помощью ссылочных объектов в предлагаемой модели вводится список переходов. Список переходов – это список объектов, для которых текущий объект используется как ссылочный. Связь устанавливается через равные значения понятий текущего объекта и объектов списка. На основании списка переходов автоматически строится выражение для получения следующего кода экземпляра.
С помощью синтаксиса XML список переходов можно определить следующим образом:
<obj code=»Obj» type=»ref»>
<ref ref=»Obj1″>
<woc code=»Woc011″ ref=»Woc11″/>
<woc code=»Woc01m» ref=»Woc1m»/>
</ref>
<ref ref=»Objn»>
<woc code=»Woc0n1″ ref=»Wocn1″/>
<woc code=»Woc0nk» ref=»Wocnk»/>
</ref>
</obj>
Здесь:
Obji – код объекта, для которого текущий объект может быть ссылочным;
Woc0ij – понятие текущего объекта, по значениям которого осуществляется связь;
Wocij – соответствующее понятие объекта Obji, по значениям которого осуществляется связь.
Если код понятия текущего объекта и объекта Obji совпадает, то код понятия объекта Obji может быть опущен.
Если А – множество экземпляров текущего объекта, то список переходов может быть описан следующим выражением реляционной алгебры:
A REF Obji = (Obji TIMES A WHERE Woc0i1=Woci1 AND … AND Woc0im=Wocim) {ALL BUT Obji}
Тогда операция соединения определяется на основании списка переходов и операции произведения:
Obji JOIN A = Obji TIMES (A REF Obji)
Рассмотрим пример, пусть имеются объекты А и В, в которых пользовательскими потенциальными ключами являются понятия S и P соответственно, и объект АВ, который в реляционном смысле является ассоциацией объектов А и В. Объект АВ содержит пользовательские внешние ключи – S и P, ссылающиеся на соответствующие понятия объектов А и В. То есть, между объектом А и объектом АB, а также между объектом B и объектом АВ реализованы горизонтальные связи.
Для реализации операции соединения в отображении объект АВ объявляется хранимым, объекты А и B помещаются под объект АВ как дочерние и объявляются ссылочными. Для объекта А задаётся список переходов AB:S, для объекта B – список переходов AB:P, соответственно, реализуются операции соединения AB JOIN A и AB JOIN B.
<view code=»join_ref»>
<obj code=»ab»>
<woc code=»s»/>
<woc code=»p»/>
<obj code=»a» type=»ref»>
<woc code=»s»/>
<ref ref=»ab»>
<woc code=»s»/>
</ref>
</obj>
<obj code=»b» type=»ref»>
<woc code=»p»/>
<ref ref=»ab»>
<woc code=»p»/>
</ref>
</obj>
</obj>
</view>
Здесь указано, что объекты A и B в отображении имеет тип ref (ссылочный), кроме того, с помощью элемента ref заданы списки переходов для объектов.
Операцию соединения с использованием ссылочных объектов можно описать следующим выражением XQuery:
let $base := doc(«base.xml»)
for $ab in $base//ab
return
<ab>
{$ab/(*|@*)}
{
for $a in $base//a
where $ab/@s = $a/@s
return $a
}
{
for $b in $base//b
where $ab/@p = $b/@p
return $b
}
</ab>
Таким образом, с помощью ссылочных объектов горизонтальные связи представляются как логические иерархические связи. Очевидно, такое представление является более наглядным и интуитивно понятным для пользователя.
Собственно иерархические связи по кодам экземпляров в предлагаемой модели также представляют собой реализацию операций соединения между экземплярами родительского объекта (A) и экземплярами дочернего объекта (B) A JOIN B.
Такие операции выполняются системой автоматически на основании структуры отображения
<view code=»tree»>
<obj code=»a»>
<obj code=»b»/>
</obj>
</view>
и могут быть описаны с помощью следующего выражения XQuery:
let $base := doc(«base.xml»)
for $a in $base//a
return
<a>
{$a/(*|@*)}
{
for $b in $base//b
where substring($b/@code, 1, $len) = $a/@code
return $b
}
</a>
Здесь $len – длина кода экземпляра объекта A, функция substring выделяет из кода экземпляра объекта B значение внешнего ключа, ссылающегося на код экземпляра объекта А.
С помощью ссылочных объектов также предлагается решать задачу инвертирования иерархии по кодам экземпляров. В качестве списка переходов для ссылочных объектов может быть указан код объекта-предка для данного объекта. В этом случае связь осуществляется по кодам экземпляров, и в дерево экземпляров попадут те экземпляры объекта, которые являются потомками для экземпляра объекта-предка. Код экземпляра объекта-предка определяется по родительскому для ссылочного объекта объекту в отображении. Если в отображении нет родительского объекта для ссылочного или этот родительский объект в отображении не входит в подсхему базы данных, включающую ссылочный объект, то в дерево экземпляров попадут все экземпляры ссылочного объекта. Если в качестве кода объекта-предка указан код самого ссылочного объекта, то в дерево экземпляров попадёт только один экземпляр для каждого экземпляра объекта-предка.
Дополним предыдущий пример объектом С, дочерним для объекта В, и рассмотрим два варианта инвертирования иерархии.
В обоих случаях в отображение помещается объект С как хранимый, под него помещается объект B, который объявляется ссылочным. В списке переходов в первом случае указывается объект А, во втором – объект В.
| <view code=»invert1″> <obj code=»c»> <obj code=»b» type=»ref»> <ref ref=»a»/> </obj> </obj> </view> | <view code=»invert2″> <obj code=»c»> <obj code=»b» type=»ref»> <ref ref=»b»/> </obj> </obj> </view> |
Для первого случая код экземпляра объекта А (объект-предок) содержится в коде экземпляра объекта С (родительский объект в отображении), в данном случае это код равен А. Соответственно, в дерево экземпляров попадут дочерние для А:A экземпляры объекта В – AА и АВ.
Для второго случая код экземпляра объекта В (объект-предок) содержится в коде экземпляра объекта С (родительский объект в отображении), в данном случае это коды АА и АВ. Соответственно, в дерево экземпляров попадут «дочерний» для B:АА экземпляр объекта В, то есть, сам экземпляр AА, а также «дочерний» для B:АB экземпляр объекта В – AB.
Таким образом, в первом случае фактически реализуется операция:
C JOIN A JOIN B {ALL BUT A},
а во втором случае операция:
C JOIN B JOIN B {ALL BUT B} º C JOIN B
С использование XQuery эти операции могут быть описаны следующим образом.
Для первого случая:
let $base := doc(«base.xml»)
for $c in $base//c
return
<c>
{$c/(*|@*)}
{
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
}
</c>
Для второго случая:
let $base := doc(«base.xml»)
for $c in $base//c
return
<c>
{$c/(*|@*)}
{
for $b in $base//b
where $b/@code = substring($c/@code, 1, $len_b)
return $b
}
</c>
4. Заключение
В разработанной модели данных с помощью предложенных механизмов ссылочных и виртуальных объектов реализуются операции произведения и соединения без создания дополнительных структур хранения, решается задача представления горизонтальных связей как логических иерархических, задача инвертирования иерархии.
Ссылочные объекты ссылаются на экземпляры объектов, реально существующие в базе данных, при этом операции манипулирования экземплярами ссылочных объектов поддерживаются системой. Виртуальные объекты позволяют создавать виртуальные деревья объектов. Операции манипулирования экземплярами должны реализовываться пользователем. Виртуальные объекты предоставляют большую свободу и гибкость, однако большинство задач может быть решено с использованием ссылочных объектов.
Предложенная модель данных является основой разработанного инструмента для построения и использования информационных систем qWORD-XML [10]. Благодаря реализованной модели данных, а также унификации хранения, обработки и представления данных, инструмент qWORD-XML представляет собой удобную среду для быстрой и простой разработки, простого сопровождения и использования информационных систем.
С помощью инструмента qWORD-XML были разработаны Автоматизированная информационно-аналитическая система по проблемам инвалидности и инвалидов (АИС МСЭ) и Информационно-аналитическая система органов социальной защиты населения субъекта федерации (АИС «Соцзащита»).
Литература
- Тимофеев Д.В. Использование платформы XML для описания расширенной реляционной модели данных RM/T
- Кодд Э.Ф. Расширение реляционной модели для лучшего отражения семантики.
- Extensible Markup Language (XML) 1.0.
- Relax NG.
- The Schematron
- Document Object Model (DOM).
- XML Path Language (XPath) Version 1.0.
- XML Path Language (XPath) 2.0.
- XQuery 1.0: An XML Query Language.
- Гессе С., Кирстен В. Введение в язык программирования М. – СПб: АОЗТ «СП. АРМ», 1996 – 280с.
- Кирстен В. От ANS MUMPS к ISO M. – СПб: СП.АРМ, 1995 – 277с.
- Долженков А., Тимофеев Д. Семантический инструмент построения баз данных. «Открытые системы», №01/2006
Читайте также: Кардиохирургия, ангиография, МИС qMS и другие успехи: министр Мурашко высоко оценил работу СОКБ №1
21 сентября / 2015
Автор: Дмитрий Тимофеев