Организация хранения данных и выполнения запросов в динамической информационной модели DIM (стр. 4 из 4)
12. Так как результат отвечает всем условиям запроса, то он переносится в буфер вывода, а текущий буфер очищается.
13. Выбираем следующий помеченный объект класса Шина. Если он есть, то делаем его текущим и переходим к п. 6.
14. Если его нет, то выполнение запроса завершено. Результаты запроса находятся в буфере вывода.
Запрос 2. Для продукции, входящей в группу «Диагональные шины», определить наименование, обозначение, модель, стандарт и значение одного из показателей, по которому определен брак (см. рис. 9).
Рис. 9. Схема слоев запроса 2
Заметим, что для записи во фразе where условия запроса «значение одного из показателей, по которому определен брак» надо не только определить условие на данные объектов классов Нормы, ПоказателиПаспорта, соответствующие объекту класса Показатели, но и указать, что условие выполняется, если найдется такой показатель. Это требует проверки условия до тех пор, пока не найдется такой показатель. Поэтому в запросе вводится конструкция введения квантора exist: where exist (Показатель) with
ВерхняяНорма < ЗначениеВПаспорте | ЗначениеВПаспорте < НижняяНорма
В общем случае конструкция фразы where, добавляемая в языки запросов ODQL и SODQL выгладит следующим образом:
where... exist(<список объектов, для которых определяется выполнение условия >) with <условие для данных, связанных с данными списка>
Условие where считается выполненным, если найдется такой вычисляемый в запросе список объектов запроса, для которых условие with выполняется. В этом случае проверка условия для других объектов, определяющих этот список данных, отменяется. Условие считается невыполненным, если ни для какого вычисляемого в запросе списка объектов оно не выполняется.
Аналогично квантору exist вводится квантор all:
where... а11(<список объектов, для которых определяется выполнение условия>) with <условие для данных, связанных с данными списка>
В этом случае условие where считается выполненным, если для любого вычисляемого в запросе списка объектов запроса условие with выполняется, и считается невыполненным, если найдется такой вычисляемый в запросе список объектов, для которого оно не выполняется. Нетрудно видеть, что эти действия соответствуют алгебре предикатов.
В списке фразы select выбора данных по умолчанию определяется квантор all, согласно которому выбираются данные всех объектов, для которых выполнено условие запроса. Если же требуется вывод только тех данных, для которых выполняется условие запроса, то для выбора данных употребляется квантор exist. Эта конструкция добавляется в языки запросов.
В рассматриваемом примере во фразе select для выбора только того Показателя, для которого выполняется условие, записывается квантор exist:
select... exist (НаименованиеПоказателя)
На языке SODQL запрос выглядит следующим образом:
for НаименованиеТехнологическойГруппы = 'Диагональные шины',
ДатаВыпуска = 01.01.2010 : 31.12.2010
select НаименованиеШины, ОбозначениеШины, МодельШины, НаименованиеСтандарта, exist (НаименованиеПоказателя), ЗначениеВПаспорте, НижняяНорма, ВерхняяНорма
where exist (Показатели) with ВерхняяНорма < ЗначениеВПаспорте | ЗначениеВПаспорте < Ниж- няяНорма
Учитывая, что в схеме класс Показатели входит в две цепочки, идущие от базового класса Шина, необходимо составить два коррелированных подзапроса для этого класса и соединить их пересечением. После преобразования запроса в язык нижнего уровня ODQL получим: for НаименованиеТехнологическойГруппы = 'Диагональные шины',
ДатаВыпуска = 01.01.2010 : 31.12.2010
select НаименованиеШины, ОбозначениеШины, МодельШины,
НомерПартии, НаименованиеСтандарта, exist (НаименованиеПоказателя), ЗначениеВПаспорте, НижняяНорма, ВерхняяНорма
from Шина, ТехнологическаяГруппа ТГ, Паспорт Пас, Стандарт Ст,
(select object from Показатели Пк, ПоказательПаспорта ПокПас links Пас contains (ПокПас) Пк) intersection
(select object from Показатели Пк, Нормы Норма links Ст contains (Норм) Пк)
Пок
links ТГ contains Шина, Шина parent Пас, Ст parent Шина,
Пас contains (ПокПас) Пок, Ст contains (Норм) Пок where exist (Пок) with ВерхняяНорма < ЗначениеВПаспорте |
ЗначениеВПаспорте < НижняяНорма
Выполнение этого запроса определяется следующими действиями:
1. Выбираем все объекты, отвечающие ограничению из for для классов Технологические группы и Паспорт. При этом для класса Технологические группы используем внутреннее включение для определения всех групп, вложенных в группу, которая задана условием фразы for. Для остальных классов Шина, Стандарт, Показатели, Показатель Паспорта, Нормы продукции устанавливаем пометку MarkList всех выбранных объектов.
2. Приступаем к коррекции пометок объектов классов. По фразе links определяем связанный с этим классом отношением включения включающий класс Шина. Идем снизу вверх от объектов классов Технологические группы и Паспорт к объектам класса Шина и помечаем те, которые связаны с уже помеченными объектами, то есть отвечающими обоим условиям из фразы for. На этом этап коррекции заканчивается.
3. Начинаем обход схемы слоев с базового класса Шина. Выбираем по очереди его помеченные объекты.
4. Для текущего выбранного объекта класса Шина выбираем значения полей НаименованиеШины, ОбозначениеШины, МодельШины и заносим в буфер 1.
5. Для текущего помеченного объекта класса Шина по следующей связи фразы links выбираем связанные с ним объекты класса Паспорт.
6. Для текущего помеченного объекта класса Шина по следующей связи фразы links выбираем связанный с ним объект класса Стандарт.
7. Выбираем текущий объект класса Стандарт. Для текущего выбранного объекта класса Стандарт выбираем значения поля НаименованиеСтандарта и заносим в буфер 1.
8. Выбираем текущий объект класса Паспорт. Если его нет, то очищаем буфер 1, выбираем следующий текущий объект класса Шина и, если он есть, переходим к п. 4, а если его нет, то завершаем выполнение алгоритма.
9. Следующие части фразы links связывают с текущим объектом класса Паспорт объекты подмножества Пок класса Показатели и с текущим объектом Стандарт также объекты подмножества Пок класса Показатели. Поэтому образуем по первому коррелированному подзапросу подмножество, используя алгоритм коррекции, а затем, используя алгоритм коррекции для второго подзапроса, и получаем пересечение подмножеств двух коррелированных подзапросов Пок.
10. По следующей связи фразы links выбираем связанные с текущим объектом класса Паспорт объекты множества Пок класса Показатели и класса ПоказательПаспорта и делаем их текущими. Если их нет, то очищаем буфер 1 и переходим к п. 8.
11. Заносим для этих объектов в буфер 2 значения полей НаименованиеПоказателя, ЗначениеВПаспорте.
12. Используя последнюю связь фразы links между классами Стандарт и подмножеством Пок класса Показатели, по текущим объектам классов Стандарт, Показатели ищем объект класса Нормы Продукции. Так как он есть, то заносим в буфер 2 его поля НижняяНорма, ВерхняяНорма.
13. По значениям буфера 2 проверяем условие фразы where. Если оно не выполнено, то очищаем буфер 2, выбираем текущими следующие объекты классов Показатели, Показатель Паспорта и переходим к п.11.
14. Если условие выполнено, то переносим буферы 1 и 2 в буфер вывода, очищаем их и переходим к п. 8.
Рассмотренные примеры демонстрируют возможность разработки алгоритма третьего этапа по тексту ODQL-запроса с введением стека для получения всех результатов запроса (см. [5]). Анализ показывает, что трудоемкость этого этапа соответствует оценке 9(тк), где m - количество классов запроса, а k - ожидаемое количество результирующих кортежей запроса.
6.Заключение
Введенная организация данных с помощью метауровня описания сущностей DIM позволяет не только осуществить доступ к данным и манипуляции с ними, но и реализовать динамику данных и типов. К тому же, организация внешних индексов некоторых таблиц метауровня реализует введенные для вычисления запросов индекс-выборки классов и отношений классов DIM. Это приводит не только к удобному, эффективному способу конструирования запросов, но и достаточно эффективному способу вычисления запросов. Конечно, по сравнению с реляционной организацией данных время вычисления запросов несколько увеличится, но по порядку вычислительной сложности запросы не будут менее эффективны. К тому же подход DIM позволяет создать качества баз данных, которые не имели реляционные СУБД. За новые качества надо платить. Для получения коэффициента ухудшения времени выполнения запросов в настоящее время проводится статистическое исследование для разных платформ реализации.
Список литературы
1. Писаренко, Д. С., Рублев, В. С. Концепции взаимодействия Динамической информационной модели DIM [Текст] / Д. С. Писаренко, В. С. Рублев // Актуальные проблемы математики и информатики. - Ярославль : Яр- ГУ, 2007. - С. 75-80.
2. Писаренко, Д. С., Рублев, В. С. Объектная СУБД Динамическая информационная модель DIM и ее основные концепции [Текст] / Д. С. Писаренко, В. С. Рублев // Моделирование и анализ информационных систем - 2009. - Т. 16, № 1. - С. 62-91.
3. Писаренко, Д. С., Рублев, В. С. Синтез аппарата взаимодействий системы управления базами данных DIM [Текст] / Д. С. Писаренко, В. С. Рублев // Материалы XVII международной школы-семинара «Синтез и сложность управляющих систем» имени академика О. Б. Лупанова. - Новосибирск : изд. ИМ СО РАН, 2008. - С. 130-135.
4. Рублев, В. С. Запросная полнота языка ODQL динамической информационной модели DIM [Текст] /
В.С. Рублев // Ярославский педагогический вестник. Естественные науки. - 2011. - № 1. - С. 69-75.
5.Рублев, В. С. Организация выполнения объектных запросов в динамической информационной модели DIM [Текст] / В. С. Рублев // Моделирование и анализ информационных систем. - 2011. - Т. 18, № 2. - С. 39-51.
6. Рублев, В. С. Язык объектных запросов динамической информационной модели DIM [Текст] / В. С. Рублев // Моделирование и анализ информационных систем. - 2010. - Т. 17, № 3. - С. 144-161.
7. Сивцов, А. Шесть компонентов успешных проектов на примере DW/BV. Корпоративные базы данных - 2011 [Текст] / А. Сивцов // Материалы 16-й ежегодной технической конференции. - 2011. - CitForum.ru
8. Gray J. Data Management: Past, Prezent and Future // IEEE Computer 1996, October. V.29, no 10.
9.Gray J., Liu D.T., Nieto-Santisteban M., Szalay A., Dewitt D.J., Heber G. Sientific Data Management in the Coming Deacade // SIGMOD Recjrd 2005, December. V. 34, no 4.
10. Jarke M., Koch J., Query Optimization in Database Systems // Computing Surveys 1984, June. Vol. 16, No. 2.
11. Silbershatz A., Zdonik S. Database Systems Breaking Out of the Box // ACM Computing Surveys 1996, December. V.28, no 4.
12. Stonebraker M. My Top 10 Assertions About Data Warehouses // BLOG@CACM, August 26, 2010.