Организация хранения данных и выполнения запросов в динамической информационной модели DIM (стр. 3 из 4)

Таблица ClassInheritance описывает связи классов по наследованию (родительский - дочерний) и представляет собой ориентированный граф с определенными компонентами для каждого типа классов. При этом родительский и дочерние классы определяются через IdParentClass и IdChildClass, а тип группы TypeGroup определяет тип параметра дочернего класса.

Таблица ClassInclusion описывает связи включения классов (включающий - включаемый). Параметр IdInclusionClass определяет идентификатор класса связи между включающим классом IdInclud- ingClass и включенным классом IdIncludedClass (если IdInclusionClass=0, то определяется простое включение объектов включаемого класса в объекты включающего класса). Параметр TypeInclusion определяет тип отношения между включающим и включаемым классом:

0 - многие ко многим;

1 - многие к одному;

2 - один ко многим;

3 - один к одному.

Таблица ClassInteraction описывает классы взаимодействия, определяющие взаимодействие потока объектов класса IdWhat от объекта класса IdFrom к объекту класса IdTo.

Для описания отношения включения объектов используется одна из таблиц ObjInclu- sion_IdIncluding_IdIncluded_IdInclusion или ObjInclusion_IdIncluding_IdIncluded. Они представляют собой ациклический ориентированный граф с навешанными на дуги параметрами вхождения включаемого объекта во включающий. Параметр IdIncludingObject задает включающий объект класса Id- Including из названия таблицы. Параметр IdIncludedObject задает включаемый объект класса IdIn- cluded из названия таблицы. Параметр IdInclusionObject задает объект связи между включающим и включенным объектами класса IdInclusion из названия таблицы.

Таблица ObjInheritance_IdParent_IdChild, где IdParent и IdChild - идентификаторы классов, для каждого объекта IdChildObject класса IdChild из названия таблицы задает объект IdParentObject класса IdParent из названия таблицы.

Таблицы ClassHistory, ParameterHistory и ObjHistory_IdClass описывают динамические связи классов, объектов, параметров соответственно (предшественники - наследники), определяют время преобразования (классов, объектов, параметров) и представляют собой ациклические ориентированные графы.

Таблица ObjInteraction_IdF_IdT_IdW_IdH описывает взаимодействия объектов и дает представление ориентированного графа с потоками (объектов IdWhat, IdInteraction), навешанными на дуги, идущими из объектов IdFrom в объект IdTo.

4.Алгоритм выполнения запроса

Ведущую роль в алгоритме играет схема слоев классов запроса, описанная в [4] (см. рис. 7). Напомним [6], что ODQL-запрос (запрос нижнего уровня) состоит из фраз:

• select, определяющей выборку данных запроса;

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

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

• links, определяющей связи классов;

• where, ограничивающей условиями на данные разных классов.

Упрощенный язык SODQL-запросов (верхнего уровня) опускает фразу links и может не содержать фразы from. В этом случае базовый класс определяется по первому данному фразы select, а все остальные данные ODQL-запроса получаются при построении схемы слоев. Схема слоев определяется алгоритмом, приведенным в [4] по классам данных фразы select и связям этих классов друг с другом последовательно, начиная от базового класса. При этом строятся фразы from и links, фиксирующие порядок классов и связей в схеме слоев. Поэтому можно считать, что схема слоев запроса записана в получаемом или преобразованном ODQL-запросе.

Рис. 7. Схема слоев (представлены 2 слоя: верхний с базовым классом и следующий)

Идея алгоритма выполнения запроса [5] состоит в том, что для каждого класса, участвующего в запросе, создается индекс-выборка [5]. Затем, двигаясь по схеме слоев [4] от слоя с максимальным уровнем к нулевому (к базовому классу), мы устанавливаем индекс-выборки отношений классов [5].

Реализация индекс-выборок с помощью динамической памяти невозможна, так как ее указатели должны быть связаны с узлами индексных деревьев, находящихся во внешней памяти. Поэтому для реализации индекс-выборки класса используются поля таблицы объектов класса: Mark (для пометки объекта), NextldObject с внешним индексом к этой же таблице (для организации списка индекс- выборки), а также поле MarkList записи класса в таблице Class (для пометки списка индекс выборки). Для реализации индекс-выборки отношения объектов классов в таблице связи объектов этих классов используются связанные с ней внешние индексы на соответствующие объекты таблиц объектов обоих классов, что дает возможность организовать алгоритм коррекции индекс-выборок классов.

Алгоритм использования индекс-выборок связан с начальным установлением индекс-выборок классов по фразе for запроса [6], [5]. Затем при движении по схеме слоев классов от самого нижнего слоя к самому верхнему (базовому классу запроса) по индекс-выборкам отношений более нижнего в схеме класса со связанным с ним более верхним классом схемы корректируется индекс-выборка последнего класса. Трудоемкость этого алгоритма, как показано в [5], минимально возможная (эвристически).

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

Сделаем еще 2 замечания.

1. Этап коррекции индекс-выборок классов мы можем начинать только от тех классов, находящихся в нижних слоях схемы, которые содержат не все помеченные объекты. Для этого используется пометка списка MarkList индекс-выборки класса (ее значение, согласно [5], равно 1).

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

5.Примеры

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

Запрос 1. Для каждой Шины, отвечающей группе «Диагональные шины», определить стандарт, название, обозначение, модель и показатели с их нормами (см. рис. 8).

Рис. 8. Схема слоев запроса 1

На языке SODQL запрос выглядит следующим образом:

for ТехнологическаяГруппа = 'Диагональныешины'

select НаименованиеШины, ОбозначениеШины, МодельШины,

НаименованиеСтандарта, НаименованиеПоказателя, НижняяНорма, ВерхняяНорма После преобразования запроса в язык нижнего уровня ODQL получим: for НаименованиеТехнологическойГруппы = 'Диагональные шины' select НаименованиеШины, ОбозначениеШины, МодельШины,

НаименованиеСтандарта, НаименованиеПоказателя, НижняяНорма, ВерхняяНорма from Шина, Стандарт Ст, Показатель Пок, НормыПродукции Норм,

ТехнологическиеГруппы ТГ links ТГ contains Шина, Ст parent Шина, Ст contains (Норм) Пок Выполнение этого запроса определяется следующими действиями:

1. Проводим начальную установку индекс-выборки для класса Технологические группы по ограничениям фразы for. При этом используем внутреннее включение для определения всех групп, вложенных в группу, заданную условием фразы for. Для остальных классов Шина, Стандарт, Показатели, Нормы продукции устанавливаем пометку MarkList всех выбранных объектов.

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

3. Начинаем обход схемы слоев с базового класса Шина. Выбираем по очереди его помеченные объекты.

4. Для текущего выбранного объекта класса Шина выбираем значения полей НаименованиеШины, ОбозначениеШины, МодельШины и заносим в текущий буфер.

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

6. Для текущего объекта класса Шина выбираем его родительский объект в классе Стандарт. Так как класс Стандарт имеет внутреннее наследование, то по этому отношению помечается также вся иерархия родительских объектов этого класса.

7. Выбираем текущий объект класса Стандарт.

8. Выбираем следующие классы, связанные отношением фразы links. Это классы Показатели, НормыПродукции.

9. Для текущего объекта класса Стандарт помечаем все объекты связанных с ним объектов этих классов и выводим в текущий буфер Наименование Стандарта.

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

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