автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Метод анализа процессов доступа к базам данных с учетом вложенных коррелированных подзапросов и операций агрегирования

Введение

Глава 1. Модели анализа процессов доступа к базам данных

1.1. Классификация моделей доступа к базам данных

1.1.1. Модель файлового сервера доступа к данным пример

1.1.2. Модель сервера базы данных доступа к данным

1.1.3. Модель сервера приложений доступа к данным

1.1.4. Модель доступа к данным в Intranet/Internet по технологии CGI и API

1.1.5. Модель доступа к данным в Intranet/Internet из Java-апплетов и ActiveX

1.1.6. Модель доступа к данным в системах с архитектурами CORBA и DCOM

1.2. Анализ существующих методов оценки показателей качества обработки запросов к базе данных

1.2.1. Использование систем массового обслуживания

1.2.2. Калибруемые аналитические модели

1.2.3. Стоимостные модели

1.2.4. Методы анализа процессов доступа к базам данных, основанные на знаниях

1.3. Организация оптимизации выполнения запросов к базе данных

ВЫВОДЫ

Глава 2. Метод оценки времени выполнения запросов с учётом вложенных коррелированных подзапросов и операций агрегирования атрибутов

2.1. Преобразование SQL-запроса с вложенными коррелированными подзапросами и операциями агрегирования

2.2. Некоторые свойства преобразования Лапласа-Стилтьеса и производящей функции

2.3. Оценка времени выполнения исходного запроса с несколькими уровнями вложенности подзапросов при наличии операций агрегирования

2.4. Оценка времени выполнения запроса с несколькими уровнями вложенности подзапросов после преобразования дерева операций в альтернативный план

2.5. Сравнение времени выполнения запроса для исходного и альтернативного плана

ВЫВОДЫ

Глава 3. Доработка комплекса инструментальных средств анализа моделей доступа к базам данных распределённых систем обработки данных

3.1. Структура КС AM

3.2. Схема базы данных КС AM

3.3. Организация базы знаний КС AM

3.4. Машина вывода

3.5. Доработка КСАМ

ВЫВОДЫ

Глава 4. Моделирование модулей «Контингент» и «Факультет военного обучения» автоматизированной системы МГТУ им. Н.Э. Баумана с учётом запросов к базе данных

4.1. Моделирование информационной системы «Контингент»

4.1.1. Назначение и структура системы «Контингент»

4.1.2. Результаты моделирования системы «Контингент»

4.2. Моделирование информационной системы «Факультет военного обучения»

4.2.1. Назначение и структура системы «Факультет военного обучения»

4.2.2. Результаты моделирования системы «Факультет военного обучения»

ВЫВОДЫ

Актуальность темы. В настоящее время в различных информационных системах используются системы управления базами данных, поддерживающие реляционную модель данных. Здесь для описания и манипулирования данными применяется стандартный язык SQL, который относится к классу непроцедурных языков. SQL-запрос, поступивший на сервер базы, подвергается оптимизации с целью уменьшения времени его выполнения. Суть оптимизации состоит в генерации нескольких альтернативных планов реализации запроса и выборе плана с наименьшей стоимостью, которая пропорциональна времени выполнения запроса. В теории реляционных баз данных наибольшее внимание уделяется построению оптимальных планов для класса запросов, включающих операции соединения таблиц или имеющих конструкции, которые можно свести к соединению. В теории по существу не рассматривается важный класс запросов с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования. В публикациях в основном анализируются запросы с одним коррелированным подзапросом и необоснованно утверждается, что для них оптимальным является план с группированием значений атрибута связи. При этом расчёт стоимости и сравнение альтернативных планов не выполняется. Это привело к тому, что во многих СУБД (Oracle, DB2 и др.) для реализации запросов из указанного класса используются планы на основе операции группирования. Однако, анализ показывает, что эти планы являются оптимальными только в некоторой области изменения параметров запросов и наполнения базы данных. То есть часто для реализации запроса в СУБД выбирается неоптимальный план. Поэтому задача генерации альтернативных планов выполнения запросов с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования, оценки стоимости планов и построения областей их предпочтительного использования является актуальной.

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

Цель работы. Целью работы является разработка метода анализа и оценки процессов доступа к базам данных для различных планов выполнения запросов с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования, а также моделирование информационных систем с учётом особенностей обработки запросов к базам данных.

В работе решаются следующие задачи:

1. Разработка метода преобразования исходного плана выполнения реляционных операций в альтернативный план для запросов из рассматриваемого класса.

2. Разработка метода оценки временных характеристик выполнения указанных планов и построение областей их предпочтительного использования для подкласса запросов.

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

4. Моделирование с помощью пакета КСАМ конкретных информационных систем с учётом запросов к базам данных и их подзапросов, а также выработка рекомендаций для устранения потенциальных «узких мест» в этих проектируемых системах.

Объект исследования. Объектом исследования являются оптимизаторы запросов, обеспечивающие выбор плана с наименьшей стоимостью для реализации запроса к реляционной базе данных.

Предмет исследования. Предметом исследования является процесс выбора рационального плана выполнения запроса с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования

Научная новизна. В работе получены следующие новые научные результаты:

1. На основе законов реляционной алгебры разработан метод преобразования исходного плана выполнения запроса с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования в альтернативный план с операциями группирования значений атрибутов связи.

2. Доказана рекуррентная формула, позволяющая получить производящую функцию числа записей базы данных, обработанных при выполнении запроса в соответствии с исходным планом. Доказана формула для преобразования Лапласа-Стилтьеса времени выполнения запроса в случае применения исходного плана.

3. Доказана формула для производящей функции числа записей, обработанных при выполнении SQL-запроса, обеспечивающего группирование значений атрибута связи. На её основе получена производящая функция числа записей базы данных, обработанных при выполнении запроса в соответствии с альтернативным планом, а также преобразование Лапласа-Стилтьеса времени выполнения запроса в случае применения этого плана.

4. Получены математические ожидания времени выполнения запроса для исходного и альтернативного плана. Для определённого подкласса запросов выполнено сравнение этих математических ожиданий для различных случаев и построены области преимущественного использования этих планов.

Методы исследования. Исследования проводились на основе комплексного использования теории множеств, теории вероятности, теории реляционных баз данных, теории графов, теории экспертных систем.

Практическая ценность полученных результатов. Полученные научные результаты были использованы для доработки экспертной системы КСАМ, обеспечивающей расчёт характеристик производительности проектируемых информационных систем по описанию таблиц базы данных и её наполнения, запросов и транзакций приложений, топологии сети и виртуальных каналов, параметров сетей и станций. Были переработаны фреймы экспертной системы, позволяющие учесть особенности обработки запросов с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования. КСАМ обеспечивает проведение модельных экспериментов с учётом описания запросов к базам данных и их подзапросов с целью выработки рекомендаций при проектировании информационных систем.

Внедрение результатов исследований. Доработанная экспертная система КСАМ была использована при моделировании модулей «Контингент» и «Факультет военного обучения» автоматизированной системы МГТУ им. Н.Э. Баумана на этапе их проектирования. Для каждого модуля выполнен анализ его нагрузочной способности и влияния наполнения базы данных. По результатам моделирования выработаны рекомендации по устранению потенциальных «узких мест» проектируемых систем. В частности, накопление агрегированных данных с помощью триггеров СУБД и хранение этих данных в соответствующих таблицах базы данных позволяет снизить загрузку сервера модуля «Контингент» почти в 200 раз. А небольшие изменения схемы базы данных и перепрограммирование трёх критичных запросов приводит к уменьшению загрузки сервера системы «Факультет военного обучения» в 300 раз. Рекомендации были использованы при проектировании указанных модулей.

Публикации по теме. По материалам работы опубликовано 5 печатных работ.

Апробация работы. Материалы работы были изложены автором на следующих конференциях и семинарах:

1. НТС кафедры ИУ-5 МГТУ им. Н.Э. Баумана, М., 2006.

2. Международный научный симпозиум «Образование через науку» МГТУ им. Н.Э. Баумана, М., 2005

Структура диссертационной работы. В первой главе «Модели анализа процессов доступа к базам данных» выполнен обзор моделей доступа к данным: файловый сервер, сервер базы данных, сервер приложений, доступ по технологиям Intranet/Internet и в системах с объектной архитектурой. Проанализированы различные подходы к оценке показателей качества обработки запросов к базе данных, которые используются при выборе оптимального плана выполнения запроса в среде СУБД и моделировании систем на основе баз данных: модели массового обслуживания, калибруемые аналитические модели, стоимостные модели, модели, основанные на знаниях. Выявлены их преимущества и недостатки. Показано, что для операций агрегирования атрибутов при выполнении вложенных коррелированных подзапросов такие оценки показателей качества отсутствуют. Проанализированы различные приёмы построения альтернативных оптимальных логических планов выполнения запросов к базе данных. Показано, что они хорошо проработаны для запросов, где выполняется соединение таблиц или применяются конструкции, которые можно представить в виде операций соединения. Отмечается, что стратегия построения оптимального плана существенно усложняется, если исходный запрос включает многоуровневые коррелированные подзапросы и функции агрегирования атрибутов.

Во второй главе «Метод оценки времени выполнения запросов с учётом вложенных коррелированных подзапросов и операций агрегирования атрибутов» определён класс запросов с многоуровневыми коррелированными подзапросами и операциями агрегирования. Построено дерево выражений реляционной алгебры (исходный план) по результатам частичной трансляции описания исходного запроса рассматриваемого класса. Выполнено преобразование исходного дерева в альтернативный план выполнения запроса путём ввода операции группирования значений атрибутов связи. На основании законов реляционной алгебры доказана эквивалентность исходного и альтернативного плана выполнения запроса с точки зрения результатов поиска данных. Доказана рекуррентная формула для производящей функции (ПФ) числа записей, обработанных на / -ом уровне вложенности и ниже для каждой записи / -1 -го уровня. На её основе получена ПФ числа записей базы данных, обработанных при выполнении запроса в соответствии с исходным планом. Доказана рекуррентная формула для преобразования Лапласа-Стилтьеса (ПЛС) времени обработки записей / -го уровня вложенности и ниже для каждой записи / -1 -го уровня. С её помощью получено ПЛС времени выполнения запроса в случае применения исходного плана. Доказана формула для производящей функции числа записей, обработанных при выполнении /-го SQL-запроса, обеспечивающего группирование значений атрибута связи на /-ом уровне вложенности. На её основе получена ПФ числа записей базы данных, обработанных при выполнении запроса в соответствии с альтернативным планом. Доказана формула для ПЛС времени выполнения /-го SQL-запроса. На её основе получено ПЛС времени выполнения запроса в случае применения альтернативного плана. Получены математические ожидания времени выполнения запроса для исходного и альтернативного плана. Для определённого подкласса запросов выполнено сравнение этих математических ожиданий для различных случаев. Выделены области преимущественного использования каждого из рассматриваемых планов.

В третьей главе «Доработка комплекса инструментальных средств анализа моделей доступа к базам данных распределённых систем обработки данных» проанализирована функциональная структура Комплекса инструментальных Средств Анализа Моделей доступа к базам данных распределённых систем обработки данных (КСАМ), обеспечивающего моделирование информационных систем (ИС) с учётом конфигураций узлов (станций) и сетей, параметров схемы базы данных проектируемой ИС, характеристик наполнения БД, спецификаций транзакций на уровне SQL-операторов, параметров распределения таблиц БД и транзакций по узлам ИС. Выполнен анализ схемы базы данных КСАМ, предназначенной для хранения исходных данных и результатов моделирования и используемой для доработки этой экспертной системы. Проанализирована база знаний (БЗ) КСАМ и машина вывода, осуществляющая навигацию по этой БЗ с целью анализа описания проектируемой ИС, оценки её характеристик производительности и выявления «узких мест». Выполнена доработка базы знаний КСАМ, позволяющая моделировать выполнение запросов с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования. Разработан алгоритм, обеспечивающий выбор плана с наименьшей стоимостью в процессе моделирования.

В четвёртой главе «Моделирование модулей «Контингент» и «Факультет военного обучения» автоматизированной системы МГТУ им. Н.Э. Баумана с учётом запросов к базе данных» выполнен анализ структуры, схемы базы данных и SQL-запросов для каждого из проектируемых модулей «Контингент» и «Факультет военного обучения». Описаны процедуры ввода этих параметров в экспертную систему КСАМ. По результатам моделирования выполнен анализ нагрузочной способности и влияния наполнения базы данных для каждого модуля. Предложены рекомендации по устранению потенциальных «узких мест» разрабатываемых модулей.

ВЫВОДЫ

1. Выполнен анализ структуры, схемы базы данных и SQL-запросов системы «Контингент». Многие запросы включают несколько таблиц, которые соответствуют подзапросам, а также операции группирования и агрегирования. Эти параметры системы были описаны в среде экспертной системы КСАМ.

2. С помощью КСАМ выполнен анализ нагрузочной способности системы «Контингент» при увеличении числа рабочих станций с 1000 до 3000. Здесь «узким местом» является Сервер БД, его загрузка увеличивается с 0.2 до 0.6. Были предложены следующие рекомендации:

А. Загрузка Сервера БД почти равномерно распределена по 5 транзакциям, которые предназначены для получения различных списков. При реализации соответствующего запроса происходит соединение 4 таблиц.

Если агрегированные данные (число студентов) не определять каждый раз, а хранить их в записях таблиц Faculty (факультет), Department (кафедра), Group (группа), Student (студент) и использовать триггеры СУБД, то загрузку Сервера БД можно уменьшить почти в 200 раз, что позволяет увеличить нагрузочную способность сервера или расширить его функциональные возможности.

Б. Использование коммутатора здесь оправдано, т.к. применение входной сети на концентраторах привело бы к снижению максимального числа рабочих станций с 3000 до 2000.

В. Почти вся загрузка Канала 1 приходится на транзакцию «Студенты в приказе». Анализ соответствующего запроса показывает, что при его выполнении из базы данных читаются и передаются на рабочую станцию значения атрибутов 5 записей таблиц, включённых в запрос. Но в одной из таблиц (Orderstudent) имеется поле attributes длиной 200 Кбайтов, передача которого и вызывает большую загрузку Канала 1. Уменьшение длины этого поля до 20 Кбайтов позволяет снизить загрузку Канала 1 в 10 раз.

3. В среде КСАМ выполнен анализ влияния наполнения базы данных системы «Контингент» (число записей таблиц было увеличено в 10 раз). Загрузка Сервера БД равномерно распределена по 5 транзакциям, которые выполняют чтение различных списков. При реализации каждого из этих запросов выполняется соединение 4 таблиц. Хотя число блоков, обработанных в процессе соединения, возросло с 400 до 4000 (т.е. в 10 раз), загрузка сервера увеличилась с 0.2 до 0.4 (т.е. только в 2 раза). Это объясняется тем, что число дисков, на которых хранится база данных, возросло в 5 раз (процент заполнения диска зафиксирован на уровне 30%). Распределение данных по разным дискам особенно важно для таблицы Student, так как основная доля соединяемых записей читается из этой таблицы.

4. Выполнен анализ структуры, схемы базы данных и SQL-запросов ИС ФВО. Наиболее критичные запросы включают несколько таблиц, которые соответствуют подзапросам, а также операции группирования и агрегирования. Эти параметры ИС ФВО были описаны в среде экспертной системы КСАМ.

5. С помощью КСАМ выполнен анализ нагрузочной способности ИС ФВО при увеличении числа рабочих станций с 200 до 600. Здесь «узким местом» является Сервер БД, его загрузка увеличивается с 0.3 до 0.9. Были предложены следующие рекомендации:

A. Удалить таблицу GroupStudent из запросов и включить в таблицу Student индексированный атрибут GroupID.

Б. Хранить число студентов в каждой записи таблицы Group (поле StudentNumber), для поддержки агрегированных данных использовать триггеры СУБД.

B. Изменить следующие запросы:

ВК.Список групп - поиск осуществлять в одной таблице Group,

ВК.Список студентов - соединять 4 таблицы, при этом на соединяемые записи таблицы Student накладывается условие s.GroupID = @GroupID,

НУК.Список студентов - поиск осуществлять в одной таблице Student, в запросе наложить условие s.GroupID = @GroupID.

Реализация указанных рекомендаций позволяет сократить число читаемых блоков почти в 300 раз и во столько же раз уменьшить загрузку Сервера БД.

6. В среде КСАМ выполнен анализ влияния наполнения базы данных ИС ФВО (число записей в таблицах GroupStudent, Student и StudentMark было увеличено в 3 раза). При росте числа записей количество блоков, обработанных при выполнении критичных запросов ВК.Список групп, ВК.Список Студентов, НУК.Список Студентов увеличилось с 1600 до 4800 на каждый запрос, т.е. в 3 раза. Во столько же раз возросла загрузка Сервера БД: с 0.3 до 0.9. Это свидетельствует о том, что при изменении наполнения таблиц количество дисков, где хранится база данных, осталось прежним (процент заполнения одного диска был принят равным 50). Для рассматриваемого случая было рекомендовано снизить долю заполнения диска базы данных до 25%.

ЗАКЛЮЧЕНИЕ

1. Разработан новый метод оценки и выбора планов реализации запросов с вложенными коррелированными подзапросами и операциями агрегирования, и на его основе определены процедурные знания, позволяющие учитывать этот класс запросов при моделировании информационных систем.

2. Разработан метод преобразования исходного плана выполнения произвольного запроса из рассматриваемого класса в альтернативный план, что позволяет выбирать план с наименьшим временем реализации. Доказана эквивалентность этих логических планов с точки зрения конечных результатов поиска данных. Показано, что рассмотренные планы имеют несколько физических реализаций.

3. Доказана рекуррентная формула, позволяющая получить производящую функцию числа записей базы данных, обработанных при выполнении запроса в соответствии с исходным планом. Доказана формула для преобразования Лапласа-Стилтьеса времени выполнения запроса в случае применения исходного плана.

4. Доказана формула для производящей функции числа записей, обработанных при выполнении SQL-запроса, обеспечивающего группирование значений атрибута связи. На её основе получена производящая функция числа записей базы данных, обработанных при выполнении запроса в соответствии с альтернативным планом, а также преобразование Лапласа-Стилтьеса времени выполнения запроса в случае применения этого плана.

5. Для исходного и альтернативного плана выполнено сравнение математических ожиданий времени выполнения запроса из определённого подкласса для различных случаев и построены области преимущественного использования этих планов. Разработан алгоритм, обеспечивающий выбор плана с наименьшей стоимостью.

6. Полученные результаты были использованы для доработки экспертной системы КСАМ, обеспечивающей расчёт характеристик производительности проектируемых информационных систем с учётом особенностей обработки запросов с многоуровневыми вложенными коррелированными подзапросами и операциями агрегирования.

7. Доработанная экспертная система КСАМ была использована при моделировании модулей «Контингент» и «Факультет военного обучения» автоматизированной системы МГТУ им. Н.Э. Баумана на этапе их проектирования с целью выявления и устранения потенциальных «узких мест». Проведённый анализ показал, что накопление агрегированных данных с помощью триггеров СУБД и хранение этих данных в соответствующих таблицах базы данных позволяет снизить загрузку сервера модуля «Контингент» почти в 200 раз. А изменения схемы базы данных и перепрограммирование трёх критичных запросов приводит к уменьшению загрузки сервера системы «Факультет военного обучения» в 300 раз.

1. Григорьев Ю.А. Информационная система сопровождения жизненного цикла разработки распределенных систем обработки данных // Вестник МГТУ. Приборостроение - 1999. - № 2. - С.37-45.

2. Григорьев Ю.А. Разработка научных основ проектирования архитектуры распределенных информационных систем обработки данных: Дисс. докт. техн. наук: 05.13.06. / МГТУ им. Н.Э. Баумана (М.).-1996.-234 с.

3. Григорьев Ю.А., Плутенко А.Д. Жизненный цикл проектирования распределенных баз данных. Благовещенск: Изд-во АмГУ, 1999. -265 с.

4. Григорьев Ю.А., Плутенко А.Д. Теоретические основы анализа процессов доступа к распределённым базам данных. Новосибирск: Наука, 2002. - 222 с.

5. Джексон П. Введение в экспертные системы: Уч.пос. М.: Издательский дом «Вильяме», 2001. - 624 с.

6. Дунаев С. Доступ к базам данных и техника работы в сети. Практические примеры современного программирования. М.: Диалог-МИФИ, 1999.-416 с.

7. Дэйт К. Дж. Введение в системы баз данных. Киев: Диалектика, 1998.-784 с.

8. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979. - 600 с.

9. Попов Э.В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ. М.: Наука. Гл. ред. физ.-мат. лит., 1987. - 288 с.

10. Тельнов Ю. Интеллектуальные информационные системы в экономике: Учебное пособие. -М.: СИНТЕГ, 1998.-216 с.

11. Трахтенгерц Э. Компьютерная поддержка принятия решений: Научно-практическое издание. М.: СИНТЕГ, 1998. - 376 с.

12. Ульман Д. Д., Уидом Д. Введение в системы баз данных. М.: Лори, 2000.-374 с.

13. Представление и использование знаний / X. Уэно, Т. Кояма, Т. Окамото и др.; Под ред. X. Уэно, М. Исидзука М.:Мир, 1989. - 220 с.

14. Харрингтон Д. Проектирование объектно-ориентированных баз данных. М.: ДМК Пресс, 2001. - 272 с.

15. Цикритзис Д., Лоховски Ф. Модели Данных. М.: Финансы и статистика, 1985. - 344 с.

16. Эйзенберг Э., Мелтон Д. SQL: 1999. ранее известный, как SQL3 // Открытые системы (М.).- 1999. №1. - С.52-57.

17. Delis A., Roussopoulos N. Performance and scalability of client-server database architectures // Proceedings of 18th International Conference on VLDB. Vancouver, 1992. - P. 610-623.

18. Du W., Krishnamurthy R., Shan M-C. Query Optimization in a Heterogeneous DBMS //Proceedings of 18th International Conference on VLDB. Vancouver, 1992. - P. 277-291.

19. Gardarin G., Gruser J.-R., Tang Z.-H. A cost-based selection of path expression processing algorithms in object-oriented databases //Proceedings of 22nd International Conference on VLDB. Bombay, 1996.-P. 390-401.

20. Gardarin G., Sha F., Tang Z.-H. Calibrating the query optimizer cost model of IRO-DB, an objectoriented federated database system // Proceedings of 22nd International Conference on VLDB. Bombay, 1996. - P. 378-389.

21. Бурдаков A.B. Модели и методы анализа вычислительных систем с архитектурой брокера объектных запросов: Дисс. канд. техн. наук: 05.13.15. / МГТУ им. Н.Э. Баумана М., 2002. - 196 с.

22. Гребенников Н.А. Метод поиска оптимального плана выполнения запросов к базам данных на основе нисходящей стратегии: Дисс. канд. техн. наук: 05.13.17. / МГТУ им. Н.Э. Баумана М., 2004. - 183 с.

23. Graefe G. Query evaluation techniques for large databases // ACM Computing Surveys (N.Y.).-1993. Vol. 25, N. 2. - P. 73-170.

24. Harris E.P., Ramamohanarao K. Join algorithm costs revisited //VLDB Journal. (Heidelberg).- 1996. Vol. 5, N. 1. - P. 64-84.

25. Mishra P., Eich M. H. Join processing in relational databases // ACM Computing Surveys. ( N.Y.).-1992. Vol. 24, N. 1. - P. 64-113.

26. Shapiro L. Join Processing in Database Systems with Large Main Memories // ACM Transactions on Database Systems ( N.Y.).-1986. Vol. 11, N. 3. -P. 239-264.

27. Безкоровайный M.M., Костогрызов А.И., Львов В. М. Инструменталь-но-моделирующий комплекс для оценки качества функционирования информационных систем «КОК». М.:СИНТЕГ, 2000. - 116 с.

28. Костогрызов А.И., Липаев В.В. Сертификация функционирования автоматизированных информационных систем. М.: Изд-во «Вооружение. Политика. Конверсия», 1996. - 280 с.

29. Kostogryzov A.I. Models for Information System Operation Quality Investigation. // Proceedings First International Workshop MALOPD. Moscow, 1999.-P. 20-31.

30. Плутенко А.Д. Разработка теоретических основ анализа процессов доступа к базам данных распределённых автоматизированных систем: Дисс. докт. техн. наук: 05.13.18. / Институт автоматики и процессов управления ДВО РАН. Владивосток, 2004. - 305 с.

31. Когаловский М.Р. Перспективные технологии информационных систем. М.: ДМК Пресс; Компания АйТи, 2003. - 288 с.

32. Шаша Д., Бонне Ф. Оптимизация баз данных: принципы, практика, решение проблем. М.: КУДИЦ-ОБРАЗ, 2004. - 432 с.

33. Гарсиа-Молина Г., Ульман Дж., Уидом Дж. Системы баз данных. Полный курс. М.: Издательский дом «Вильяме», 2003. - 1088 с.

34. Кёниг Д., Штойян Д. Методы теории массового обслуживания. М.: Радио и связь, 1981. - 128 с.

35. Приоритетные системы обслуживания / Б.В. Гнеденко, Э.А. Даниелян, Б.Н. Дмитров и др. М.: Изд-во МГУ, 1973. - 448 с.

36. Ладыженский Г.М. Системы управления базами данных коротко о главном // Системы управления базами данных (М.).- 1995. - № 2. -С.125-142.

37. Ладыженский Г.М. Системы управления базами данных коротко о главном // Системы управления базами данных (М.).- 1995. - № 3. -С.128-136.

38. Дунаев С.Б. INTRANET-технологии. М.: Диалог-МИФИ, 1997. - 288 с.

39. Чеппел Д. Технологии ActiveX и OLE. М.: Издательский отдел «Русская Редакция» ТОО «Channel Trading Ltd», 1997. - 320 с.

40. Амстронг Т. ActiveX: создание Web-приложений. Киев: Издательская группа BHV, 1998.-592 с.

41. Саймон А.Р. Стратегические технологии баз данных: менеджмент на 2000 год. М.: Финансы и статистика, 1999. - 479 с.

42. Хилайер С., Мизик Д. Программирование Active Server Pages. М.: Издательский отдел «Русская Редакция» ТОО «Channel Trading Ltd», 1999.-296 с.

43. Java 1.1. Энциклопедия пользователя / М. Моррисон, Д. Эблан, М. Аферган и др. Киев: Изд-во «ДиаСофт», 1998.- 784 с.

44. Дэвис С. Р. Программирование на Microsoft Visual Java++. М.: Издательский отдел «Русская Редакция» ТОО «Channel Trading Ltd», 1997. -376 с.

45. Кузнецов С.Д. Стандарты языка реляционных баз данных SQL: краткий обзор // Системы управления базами данных (М.).- 1996. № 2. - С.6-36.

46. Oracle 7.3. Пособие разработчика / JI. Сингх и др. Киев: Издательство «ДиаСофт», 1997. - 736 с.

47. Ричарде М. Oracle 7.3. Энциклопедия пользователя. Киев: Издательство «ДиаСофт», 1997. - 832 с.

48. Ладыженский Г.М. Tuxedo System: разработка систем клиент-сервер (часть 1) // Системы управления базами данных (М.).- 1996. № 1. - С. 87-101.

49. Ладыженский Г.М. Tuxedo System: разработка систем клиент-сервер (часть 2) // Системы управления базами данных (М.).- 1996. № 2. - С. 94-106.

50. Бабушкин М., Иваненко С., Коростелев В. Web-сервер в действии. -СПб: Питер, 1997. 272 с.

51. Франк A. HTML и CGI //LAN MAGAZINE: Русское издание (М.).-1996.-Том2, №7. С.43-51.

52. Калиниченко Л.А., Когаловский М.Р. Стандарты OMG: Язык определения интерфейсов IDL в архитектуре COBRA // Системы управления базами данных (М.).- 1996. № 2. - С. 115-129.

53. Philip Gile. Магические возможности технологии ORB // Компьютеруик

54. М.). 1997. - № 3. - С.28-29.

55. Маклаков С.В. BPwin и ERwin. CASE-средства разработки информационных систем. М.: ДИАЛОГ-МИФИ, 1999. - 256 с.

56. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. СПб: Изд-во «Питер», 1999. - 672 с.

57. Авен О.И., Турин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. - 464 с.

58. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.-432 с.

59. Сигнор Р., Стегман М.О. Использование ODBC для доступа к базам данных. М.: БИНОМ; НАУЧНАЯ КНИГА. - 384 с.

60. Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. М.: Изд-во МГУ, 1984. - 240 с.

61. Иванов Ю.Н., Кочин Ю.Я. Представление и реализация запросов в системах баз данных // Автоматика и телемеханика (М.).- 1996. № 5. -С.178-185.

62. Сиротюк В.О. Модели и методы синтеза оптимальных логических структур и базы метаданных репозитария распределённых баз данных в АСУ // Автоматика и телемеханика (М.).- 1999. № 1. - С.166-179.

63. Липаев В. В. Системное проектирование сложных программных средств для информационных систем. М.: СИНТЕГ, 1999. - 224 с.

64. Мамиконов А.Г., Кульба В.В., Сиротюк В.О. Оптимизация структур данных в АСУ. М.: Наука, 1988. - 234 с.

65. Оптимизация структур распределённых баз данных в АСУ / А.Г. Мамиконов, В.В. Кульба, С.А. Косяченко, Н.А. Ужастов М.: Наука, 1990. -321 с.

66. Модели и методы проектирования распределённых БД (обзор) / С.А. Косяченко, В.В. Кульба, А.Г. Мамиконов, Н.А. Ужастов // АиТ. (М.).1989.-№7.-С.3-58.

67. Григорьев Ю.А., Плутенко А.Д. Об одном алгоритме синтеза схемы реляционной базы данных //Вестник АмГУ (Благовещенск).- 1999. -Выпуск 4. -С.10-12.

68. Григорьев Ю.А., Плутенко А.Д. Оценка времени выполнения запросов к реляционной системе управления базами данных. М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. - 59 с.

69. Искусственный интеллект: Справочник; В 3 кн., М.: Радио и связь.1990. Кн. 1.- Системы общения и экспертные системы - 464 с. Под ред. Э. В. Попова.

70. Искусственный интеллект: Справочник, / Под ред. Д. А. Поспелова; В 3 кн., М.: Радио и связь, 1990. - Кн. 2-Модели и методы: - 304 с.

71. Искусственный интеллект: В 3 кн. Кн. 3. Программные и аппаратные средства: Справочник / Под ред. В.Н. Захарова, В.Ф. Хорошевского. -М.: Радио и связь, 1990. 368 с.

72. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. М.: Знание, 1985. - 32 с. (Новое в жизни, науке, технике. Сер. Математика, кибернетика; № 10).

73. Элти Дж., Кумбс М. Экспертные системы: концепции и примеры. М.: Финансы и статистика, 1987. - 191 с.

74. Уотермен Д. Руководство по экспертным системам. М.: Мир, 1989. -388 с.

75. Герман О.В. Введение в теорию экспертных систем и обработку знаний. Минск.: ДизайнПРО, 1995. - 255 с.

76. Штоян Д. Качественные свойства и оценки стохастических моделей. -М.: Мир, 1979.-268 с.

77. Surajit Chaudhuri, Kyuseok Shim. Optimization of queries with user-defined predicates //ACM Transactions on Database Systems. Jun. 1999. - Vol. 24, No. 2.-P. 177-228.

78. Optimizing Large Join Queries in Mediation Systems /Ramana Yemeni, Chen Li, Jeffrey Ullman, Hector Garcia-Molina. // Stanford University, USA, 1999 (www. link.springer.de, Computer Science, LNCS 1540).

79. Theo Harder, Gunter Sauter, Joachim Thomas. The intrinsic problems of structural heterogeneity and an approach to their solution //The VLDB Journal. 1999. - Vol. 8, Issue 1. - P. 25-43.

80. Roger Weber, Klemens Bohm. Trading Quality for Time with Nearest-Neighbor Search // Institute of Information Systems, Switzerland.- Zurich, 2000 (www.link.springer.de, Computer Science, LNCS 1777).

81. Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis. The GMAP: a versatile tool for physical data independence // The VLDB Journal. 1996. - Vol. 5, Issue 2. - P. 101-118.

82. Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis. Parametric query optimization // The VLDB Journal. 1997. - Vol. 6, Issue 2. -P. 132-151.

83. Michael Steinbrunn, Guido Moerkotte, Alfons Kemper. Heuristic and randomized optimization for the join ordering problem // The VLDB Journal.1997. Vol. 6, Issue 3. - P. 191-208.

84. Gennady Antoshenkov, Mohamed Ziauddin. Query processing and optimization in Oracle Rdb //The VLDB Journal. 1996. - Vol. 5, Issue 4. - P. 229-237.

85. Jia Liang Han. Optimizing relational queries in connection hypergraphs: nested queries, views, and binding propagations //The VLDB Journal.1998.-Vol. 7, Issue 1,-P. 1-11.

86. Raymond T. Ng, Paul Shum. Optimal clip ordering for multi-clip queries // The VLDB Journal. 1998. - Vol. 7, Issue 4. - P. 239-252.

87. Navin Kabra, David J. DeWitt. OPT++ : an object-oriented implementation for extensible database query optimization // The VLDB Journal. 1999. -Vol. 8, Issue l.-P. 55-78.

88. Daniele Gardy, Laurent Nemirovski.Urn Models and Yao's Formula // La-boratoire PRiSM, Universite de Versailles Saint-Quentin, 1999 (www.link.springer.de, Computer Science, LNCS 1540).

89. T. Catarci, G. Santucci, J. Cardiff. Graphical interaction with heterogeneous databases // The VLDB Journal. 1997. - Vol. 6, Issue 2. - P. 97-120.

90. Gustav Fahl, Tore Risch. Query processing over object views of relational data // The VLDB Journal. 1997. - Vol. 6, Issue 4. - P. 261-281.

91. Gustav Fahl, Tore Risch. Query processing over object views of relational data // The VLDB Journal. 1997. - Vol. 6, Issue 4. - P. 261-281.

92. M. Negri, G. Pelagatti. Distributive join: a new algorithm for joining relations //ACM Transactions on Database Systems. 1991. - Volume 16, No. 4. - P. 655 - 669.

93. Evan P. Harris, Kotagiri Ramamohanarao. Join algorithm costs revisited // The VLDB Journal. 1996. - Vol. 5, Issue 1. - P. 64-84.

94. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu. On applying hash filters to improving the execution of multi-join queries //The VLDB Journal. 1997. -Vol. 6, Issue2.-P. 121-131.

95. Seeking the truth about ad hoc join costs / Laura M. Haas, Michael J. Carey, Miron Livny, Amit Shukla. // The VLDB Journal. 1997. - Vol. 6, Issue 3.- P. 241-256.

96. Zhe Li, Kenneth A. Ross. Fast joins using join indices // The VLDB Journal.- 1999. Vol. 8, Issue 1. - P. 1-24.

97. Functional-join processing /R. Braumandl, J. Claussen, A. Kemper, D. Kossmann. // The VLDB Journal. 2000. - Vol. 8, Issue 3-4. - P. 156-177.

98. ISO 9000:2000 Системы менеджмента качества. Основные положения и словарь.

99. ISO 9001:2000 Системы менеджмента качества. Требования.

100. Репин В.В., Елиферов В.Г. Процессный подход к управлению организацией // Всё о качестве. Отечественные разработки (М.).- 2002. № 18. - С.12-16.

101. Репин В.В., Елиферов В.Г. Основы формирования сети процессов в организации // Всё о качестве. Отечественные разработки (М.).- 2002. -№ 18.-С. 17-29.

102. Репин В.В., Маклаков С.В. ARIS Toolset/BPWin: выбор за аналитиком // Компьютер пресс (М.).- 2002. № 1. - С.26-36.

103. Хамер М., Чампи Дж. Реинжиниринг корпорации: Манифест революции в бизнесе. СПб.: Изд-во СПб ун-та, 1997. - 373 с.

104. Робсон М., Уллах Ф. Практическое руководство по реинжинирингу бизнес-процессов. М.: Изд-во «Аудит», 1997. - 432 с.

105. Шадрин А.Д. Процессный подход. Основы и методика реализации //Все о качестве. Отечественные разработки (М.).- 2002. № 16-17. -С.32-43.

106. Боркус В., Монахова Е. Интеграция: новое решение старых проблем. Часть 2. http://www.pcweek.ru/Year2003/N36/CP1251/DevApp /chaptl.htm.

107. Постреляционная СУБД Cache 5. Объектно-ориентированная разработка приложений / В. Кирстен, М. Ирингер, М. Кюн и др. М.: ООО «Бином-Пресс», 2005. - 416 с.

108. Григорьев Ю.А., Остриков С.П. Выбор оптимального плана выполнения запроса с вложенными коррелированными подзапросами // Информатика и системы управления (Благовещенск).- 2006. №. 1. -С.1-12.

109. Григорьев Ю.А., Остриков С.П., Плутенко А.Д. Моделирование информационной системы "Контингент" // Информатика и системы управления (Благовещенск).-2006. №. 1. - С. 13-26.

110. Григорьев Ю.А., Остриков С.П. Оценка времени выполнения запросов с коррелированными подзапросами и операциями агрегирования.// Вестник МГТУ. Приборостроение. 2006. №1 - С 98-110.

111. Клепиков В.И. Остриков С.П., Использование CALS-технологий в производстве и эксплуатации бортовых систем управления.// Вестник МГТУПриборостроение. 2002. - №1. - С 85-92.

112. Государственное образовательное учреждение высшего профессионального образования

113. Московский государственный технический университетимени Н.Э. Баумана» (МГТУ им. Н.Э. Баумана)105005, г. Москва, 2-я Бауманская ул., д. 5 Теп, (095)263-63-91 Факс (095)267-48-44 E-mail: bauman@bmstu.ru

114. ОКПО 02066434 ОГРН1027739051779 ИНН/КПП 7701002520/770101001на №от

115. УТВЕРЖДАЮ Первый проректор-проректор по научной работе , МГТУ им.Н.Э.Баумана1. Демихов К.Е.1. Т*"---.2006 г.