Содержание к диссертации
Введение 7
Глава 1. Современные концепции организации доступа к базам данных распределенных автоматизированных систем 17
1.1. Классификация моделей доступа к базам данных 17
1.1.1. Модель файлового сервера доступа к данным 17
1.1.2. Модель сервера базы данных доступа к данным 19
1.1.3. Модель сервера приложений доступа к данным 20
1.1.4. Модель доступа к данным в Intranet/Internet по технологии CGIhAPI 24
1.1.5. Модель доступа к данным в Intranet/Internet по технологии ASP 26
1.1.6. Модель доступа к данным в Intranet/Internet из Java-апплетов и ActiveX 27
1.1.7. Модель доступа к данным в системах с архитектурами CORBAhDCOM 30
1.1.8. Анализ моделей доступа к базам данных 33
1.2. Анализ современных методов организации доступа к распределенным базам данных и моделей оценки их эффективности 42
1.3. Разработка концепций комплекса инструментальных средств анализа моделей доступа к базам данных распределенных автоматизированных систем 55
Глава 2. Разработка теоретических основ анализа показателей качества моделей доступа к распределенным базам данных на ранних этапах проектирования систем обработки данных 76
2.1. Организация обработки запросов SQL 77
2.2. Разработка алгоритма синтеза оптимальной схемы базы данных 87
2.3. Оценка времени выполнения запросов SQL 95
2.3.1. Оценка времени обработки подзапросов 99
2.3.2. Вывод рекуррентной формулы производящей функции числа кортежей соединяемых таблиц 105
2.3.3. Оценка времени выполнения соединения таблиц 121
2.3.3.1. Метод соединения с помощью вложенных циклов NLJ 121
2.3.3.2. Метод соединения посредством сортировки-слияния SMJ 123
2.3.3.3. Метод хешированного соединения Щ 130
Глава 3. Разработка математических моделей анализа методов доступа к компьютерным сетям передачи данных 133
3.1. Анализ методов доступа к локальным вычислительным сетям 133
3.1.1. Формализация процесса функционирования локальных вычислительных сетей передачи данных 133
3.1.2. Определение параметров модели 139
3.1.3. Определение начальных моментов времени передачи кадра по шине ЛВС 151
3.1.4. Закон сохранения для одноканальных СМО 160
3.1.5. Анализ времени выполнения транзакции в ЛВС с помощью замкнутой сети массового обслуживания 162
3.1.6. Анализ времени выполнения транзакции в ЛВС с помощью разомкнутой СМО 173
3.1.7. Оценка средней скорости передачи данных транзакции по шине Ethernet 181
3.1.8. Оценка средней скорости передачи данных транзакции по кольцу Token Ring 189
3.2. Анализ методов доступа к глобальным сетям 193
3.2.1. Анализ функционирования сети Х.25 194
3.2.2. Оценка времени передачи пакета в сети Х.25 199
3.2.3. Анализ функционирования сети Frame Relay 201
3.2.4. Оценка времени передачи пакета в сети Frame Relay 205
3.3. Анализ методов доступа к магистральным сетям 210
3.3.1. Анализ функционирования сети FDDI 211
3.3.2. Анализ функционирования сети ATM 212
Глава 4. Комплекс инструментальных средств анализа моделей доступа к базам данных распределенных систем обработки данных 215
4.1. Разработка концепций КС AM 216
4.2. Структура КСАМ 226
4.3. Схема базы данных КСАМ 229
4.4. Организация базы знаний КСАМ 235
4.5. Машина вывода 237
4.6. Пользовательский интерфейс КСАМ 240
4.6.1. Описание концептуальной схемы базы данных 240
4.6.2. Описание запросов и транзакций 241
4.6.3. Описание архитектуры проектируемой РСОД 242
4.6.4. Распределение таблиц базы данных и транзакций по узлам РСОД 243
4.6.5. Описание обращений к транзакциям из узлов 245
4.6.6. Описание обращений к транзакциям из транзакций 245
4.6.7. Справочник конфигураций узлов 246
4.6.8. Справочник конфигураций сетей 247
4.6.9. Загрузка узлов 248
4.6.10. Загрузка сетей 249
4.6.11. Время выполнения транзакций 250
4.7. Схема представления моделей доступа к базам данных в КСАМ 252
4.7.1. Описание модели сервера базы данных 252
4.7.2. Описание модели сервера приложений 253
4.7.3. Описание доступа к базе данных из CGI- или API-программы 254
4.7.4. Описание доступа к базе данных из Java-апплетов или компонентов ActiveX 255
4.8. Анализ адекватности моделирования РСОД с помощью КСАМ 257
Глава 5. Использование комплекса инструментальных средств анализа моделей доступа к базам данных распределенных систем обработки данных 262
5.1. Исследование глобальной системы абонентского обслуживания сети Билайн GSM 262
5.1.1. Требования к проектируемой системе 262
5.1.2. Описание предметной области 264
5.1.3. Описание структуры автоматизированной системы 267
5.1.4. Описание моделируемых вариантов комплекса программно-технических средств 268
5.1.5. Схема базы данных системы абонентского обслуживания 274
5.1.6. Описание транзакций системы 280
5.1.7. Методика моделирования системы абонентского обслуживания 285
5.1.8. Результаты моделирования работы системы .. 291
5.1.9. Анализ результатов моделирования 298
5.2. Исследование автоматизированной системы фирмы "ВЕСКО+М" 301
5.2.1. Архитектура автоматизированной системы фирмы "ВЕСКО+М" 301
5.2.2. Схема базы данных автоматизированной системы и состав анализируемых транзакций 3 04
5.2.3. Сбор и анализ статистик автоматизированной системы 311
Основные результаты работы 317
Литература 319
Приложение 1 336
Приложение 2 345
Введение к работе
Актуальность проблемы. Разнообразие аппаратно-программных комплексов (АПК), используемых при разработке автоматизированных систем, привело к появлению различных моделей доступа к базам данных в рамках архитектуры "клиент-сервер". Перед проектировщиком распределенной системы возникает непростая задача выбора приемлемого варианта, зависящего от множества факторов: архитектуры будущей системы, спецификаций разрабатываемых запросов и транзакций, схемы базы данных и ее наполнения. В то же время разработчику трудно интуитивно оценить влияние этих параметров на характеристики проектируемой системы. Поэтому разработка теоретических методов, позволяющих прогнозировать показатели качества системы в зависимости от механизма доступа к базе данных и перечисленных выше факторов, а также доведение этих методов до возможности практического использования является актуальной задачей.
К сожалению, применение традиционных теоретических методов не всегда приводит к решению подобных задач. Например, попытки использования теории массового обслуживания для исследования серверов баз данных не приводят к желаемым результатам. Это связано с проблемой выделения ресурсов (обслуживающих аппаратов) и оценки их параметров (входных потоков, времени обслуживания, дисциплин обслуживания очередей).
В работах ряда авторов для оценки времени выполнения запросов к базам данных предлагается использовать калибровочную модель, представляющую собой определенную базу данных, набор запросов, а также АПК, на котором выполняются калибрующие эксперименты. Но такая модель очень дорога; получаемые по результатам натурных экспериментов аналитические выражения справедливы только для данной конфигурации АПК (и то в некоторой степени); эти выражения не отражают особенностей выполнения сложных запросов к базе данных.
Поэтому разработка теоретических основ анализа современных механизмов доступа к распределенным базам данных и связанных с ними процессов, позволяющих преодолеть многие недостатки традиционных методов, является важной проблемой. Здесь нельзя ограничиться разработкой некоторых частных методов, необходимо предложить новый класс математических моделей, позволяющих оценивать различные объемно-временные характеристики выполнения сложных запросов, которые могут включать и элементарные условия, и соединения нескольких отношений. Эти модели должны учитывать параметры схемы базы данных, а также случайный характер параметров запросов и наполнения базы данных. Важно, чтобы модели позволяли рассчитывать не только характеристики времени выполнения запросов, но и исходные данные для систем массового обслуживания, которые часто используются на практике при анализе сетей передачи данных.
Целью диссертационной работы является разработка теоретических основ анализа процессов доступа к базам данных, учитывающих особенности выполнения запросов к распределенным данным, и реализация полученных результатов в виде инструментальных программных средств.
Задачи исследования. Поставленная цель достигается путем решения ряда взаимосвязанных основных задач диссертационной работы, состоящих в следующем:
разработка математического аппарата анализа времени выполнения запросов к базе данных с учетом их декомпозиции на подзапросы и соединения промежуточных таблиц;
разработка аналитических методов оценки характеристик производительности вычислительных сетей, учитывающих параметры распределенной базы данных и выполняемых в сети запросов и транзакций;
разработка на основе теоретических исследований комплекса инструментальных средств анализа моделей доступа к базам данных распределен ных систем обработки данных (КСАМ), относящегося к классу экспертных систем;
применение полученных результатов при решении практических задач.
Методы исследований. Исследования проводились на основе комплексного использования методов теории вероятностей, теории массового обслуживания, параметрической статистики, теории реляционных баз данных, теории экспертных систем, теории нечетких множеств.
Научная новизна результатов исследования состоит в следующем.
1. Получено преобразование Лапласа-Стилтьеса функций распределения времени выполнения запроса к распределенным базам данных с учетом его декомпозиции на подзапросы.
2. Получены производящие функций числа кортежей соединяемых таблиц для различных условий соединений, учитывающие, что при соединении базовых и/или промежуточных таблиц случайным образом меняется число записей в результирующей таблице, а также множество атрибутов, состав доменов и распределение вероятностей появления элементов доменов в кортежах соединения.
3. Получены преобразования Лапласа-Стилтьеса функций распределений времени выполнения соединений таблиц распределенных баз данных с использованием различных методов: с помощью вложенных циклов, посредством сортировки-слияния и хешированного соединения, а также времени выполнения исходного запроса.
4. Разработан метод анализа функционирования локальных вычислительных сетей, учитывающий работу сетевых адаптеров и квитирование передаваемых данных. Получены выражения для определения вероятностных характеристик передатчика сетевого адаптера, а также определены механизмы учета этих характеристик при оценке параметров модели функционирования локальной вычислительной сети.
5. Получено функциональное уравнение относительно преобразования Лапласа-Стилтьеса функции распределения времени передачи кадра по шине локальной вычислительной сети, учитывающее вероятностные характеристики выполняемых в сети SQL-запросов. Найдено преобразование Лапласа-Стилтьеса функции распределения времени выполнения транзакции в сети, учитывающее особенности процесса передачи данных между рабочей станцией и сервером базы данных и параметры объемов данных, передаваемых по сети при выполнении запросов транзакций.
6. Доказана теорема о средней незаконченной работе в СМО Mg/G/1 с неординарным потоком и произвольной, не допускающей прерывания обработки дисциплиной обслуживания, которая позволила использовать законы сохранения СМО при получении выражения для средней скорости передачи данных по шине ЛВС при обработке какой-либо транзакции, запускаемой с рабочей станции.
Практическая ценность и внедерение результатов работы. Для практического использования полученных в диссертации результатов разработан Комплекс инструментальных Средств Анализа Моделей доступа к базам данных распределенных систем обработки данных (КСАМ). КСАМ по описанию запросов и транзакций приложений, таблиц базы данных, топологии сети, виртуальных каналов, параметров сетей и станций обеспечивает расчет характеристик производительности проектируемых распределенных систем обработки данных и их составляющих элементов, позволяющих выявлять "узкие места" систем. Исходные данные КСАМ можно задавать в виде нечетких чисел.
В диссертации представлены методические рекомендации по использованию разработанного комплекса для моделирования различных процессов доступа к базам данных: модели сервера базы данных, модели сервера приложений, а также доступа по технологиям Intranet/Internet: из CGI- или API-программ и из Java-апплетов и компонентов ActiveX. КСАМ позволяет учесть наличие разных способов доступа к базам данных в одной сети и характерные особенности перечисленных выше моделей и технологий. В работе выполнен анализ адекватности моделирования распределенных систем обработки данных с помощью КСАМ. М) Проводимые исследования включались в основные направления науч но-исследовательских работ Амурского государственного университета в 1985-2003 годах.
Разработанный математический аппарат, комплекс КСАМ и методические рекомендации были применены при решении ряда практических задач, в частности, при разработке глобальной системы абонентского обслуживания в рамках сети Билайн GSM, поддерживаемой АО "Вымпелком", и модернизации распределенной системы учета и анализа товарооборота, которая эксплуатируется в ряде нескольких филиалов крупных торговых компаний Москвы (фирм "ВЕСКО+М").
Отдельные результаты исследовании используются в учебном процессе Амурского государственного университета в дисциплинах "Организация баз данных" в курсовом и дипломном проектировании специальности 220200 "Автоматизированные системы обработки информации и управления". Апробация работы. Основные результаты диссертации были представлены и обсуждены на следующих конференциях, совещаниях и симпозиумах: научно-практическом семинаре "Применение баз данных" (Пенза, 1997), симпозиуме "Научное и научно-техническое обеспечение экономического и соци- JK ального развития Дальневосточного региона" (Комсомольск-на-Амуре, 1999), республиканской научно-исследовательской конференции "Измерения, автоматизация и моделирование в промышленных и научных исследованиях" (БТИ. Бийск, 2000), международной научно-технической конференции "Информационные системы и технологии" (Новосибирск, 2000), 2-й всероссийской научно-технической конференции с иностранным участием "Энергетика: управление, качество и эффективность использования энерго ресурсов" (Благовещенск, 2000), 6-й международной конференции "Качество и использование электрической энергии" (Краков, 2001), 6-й международной восточно-европейской конференции (ADBIS) "Прогресс в базах данных и информационных системах" (Братислава, 2002), международной научной конференции "Интеллектуализация обработки информации ИОИ-2004" (Алушта, 2004).
В первой главе - выполнена классификация моделей доступа к базам данных. Рассмотрены следующие модели: модель файлового сервера, модель сервера базы данных, модель сервера приложений, модели доступа к базам данных в Intranet/Internet по технологиям CGI, API, ASP, из Java-апплетов и компонентов ActiveX, а также модель доступа к данным в системах с объектными архитектурами CORBA и DCOM. Выявлены преимущества и недостатки указанных моделей. Сделан вывод, что перед проектировщиком автоматизированной системы (АС) стоит непростая задача выбора приемлемой модели доступа к базе данных. Важность этой задачи обусловлена тем, что модель доступа к базе данных выбирается на начальных этапах проектирования АС, и она определяет архитектуру будущей системы, которую очень трудно изменить на поздних этапах разработки. Поэтому важно иметь математические методы анализа показателей качества различных моделей доступа к базам данных, помогающие проектировщику выработать концепции разрабатываемой автоматизированной системы.
Выполнен критический анализ научных публикаций, связанных с темой диссертации, по следующим разделам: 1) оптимизация запросов; 2) организация выполнения запросов; 3) соединение таблиц в процессе обработки запроса; 4) организация выполнения транзакций; 5) анализ и выбор индекса; 6) анализ схемы базы данных; 7) использование памяти; 8) исследования на натурных моделях; 9) репликация данных и дублирование компонентов АС; 10) анализ сетей передачи данных. На основании анализа сделан вывод, что предлагаемые методы оценки эффективности либо основаны на результатах натурных экспериментов (система Inquery и др.), либо позволяют решать частные задачи (сравнение и выбор метода построения индекса, оптимизация запросов, организация выполнения транзакций и т. д.), либо обеспечивают оценку показателей качества функционирования АС при упрощенных предпосылках (модель 2RC, синтез WMS и др.). Ни один из данных методов не позволяет рассчитать временные характеристики выполнения запросов и загрузки устройств на ранних этапах проектирования распределенной АС с учетом параметров концептуальной схемы базы данных, спецификаций разрабатываемых программ, архитектуры будущей системы, наполнения базы данных.
Во второй главе - разработан новый математический аппарат, позволяющий получать преобразование Лапласа-Стилтьеса (ПЛС) функции распределения времени выполнения запроса к базе данных с учетом его декомпозиции на подзапросы и выбираемых оптимизатором запросов методов соединения промежуточных таблиц.
Доказаны леммы и теорема, позволяющие получать ПЛС функции распределения времени обработки подзапроса.
Определена рекуррентная процедура расчета вероятности того, что произвольная запись таблицы базы данных удовлетворяет заданному условию поиска.
Доказаны леммы и теоремы позволяющие найти ПЛС времени соединения таблиц базы данных, которое может быть выполнено оптимизатором с помощью одного из следующих методов: с помощью вложенных циклов (NLJ), посредством сортировки-слияния (SMJ), с помощью хешированного соединения (HJ).
На основании приведенных выше результатов в работе получено ПЛС времени выполнения исходного запроса.
В третьей главе — разработан метод анализа локальных вычислительных сетей (ЛВС), который основан на законах сохранения для СМО и учиты вает важные особенности функционирования современных ЛВС: работу сетевых адаптеров станций, квитирование данных, характеристики объемов данных, передаваемых по сети в процессе выполнения SQL-запросов к распределенной базе данных, а также предложены оценки для глобальных и ма- гистральных сетей передачи данных.
Выполнена формализация процесса передачи данных по ЛВС при выполнении SQL-запроса в архитектуре "клиент-сервер" и на ее основе разработана математическая модель функционирования ЛВС. Эта модель представляет собой замкнутую сеть массового обслуживания (СеМО) с числом заявок, равным количеству
Получены выражения для оценки параметров модели. При расчете ин- тенсивностей потоков обратной связи разработанной СеМО учитывались характеристики объемов данных, передаваемых по сети в процессе выполнения \ транзакций, включающих операторы языка SQL. Также учитывалось, что по еле завершения передачи очередного кадра буфер сетевого адаптера может быть еще не заполнен и передатчик СА вынужден простаивать, ожидая завершения заполнения буфера СА. Получена оценка вероятности этого события.
Показано, что если СА сервера и рабочей станции имеют разные скорости передачи данных, то возможна ситуация, когда после передачи очередного кадра с сервера на рабочую станцию сервер будет ожидать квитанцию от рабочей станции. Дана оценка вероятности данной ситуации. / Получено функциональное уравнение относительно ПЛС времени пе редачи кадра по шине ЛВС, учитывающее вероятностные характеристики числа операторов SQL, выполняемых при обращении к какой-либо транзакции, объема данных, передаваемых на сервер и обратно при обработке операторов SQL, и позволяющее определить начальные моменты времени передачи кадра по шине. Получено выражение для среднего времени передачи всех входных и выходных данных какой-либо транзакции, запускаемой с рабочей станции. Доказана теорема о средней незаконченной работе в СМО Mg/G/1 с неординарным потоком и произвольной, не допускающей прерывания дисциплиной обслуживания, которая позволила использовать законы сохранения СМО при получении выражения для средней скорости передачи данных по шине ЛВС при обработке какой-либо транзакции.
Рассмотрены особенности функционирования глобальных и магистральных сетей передачи данных Х.25, Frame Relay, FDDI, ATM, обеспечивающих связь между несколькими ЛВС.
В четвертой главе - разработаны схема базы данных, база знаний, машина вывода и пользовательский интерфейс комплекса инструментальных средств анализа моделей доступа к базам данных распределенных систем обработки данных (КСАМ), даны методические рекомендации по использованию КСАМ и приведены результаты измерений и вычислительных экспериментов, подтверждающих адекватность разработанных методов. Среда разработки комплекса — Oracle и Developer/2000. КСАМ включает взаимосвязанные подсистемы, обеспечивающие описание:
1) концептуального проекта распределенной системы обработки данных (РСОД) (концептуальной (инфологической) схемы базы данных РСОД и наполнения базы данных (прогнозируемого числа записей в таблицах и мощностей атрибутов; запросов (SQL-операторов) и транзакций РСОД, которые могут обращаться к другим транзакциям распределенной системы);
2) архитектуры РСОД (топологии и характеристик узлов и сетей из реестров результатов тестов ТРС и параметров сетей; распределения таблиц (с учетом тиражирования) и транзакций по узлам РСОД; интенсивностей обращений рабочих станций к транзакциям).
Разработаны методические рекомендации по использованию комплекса КСАМ для моделирования различных процессов доступа к базам данных: модели сервера базы данных, модели сервера приложений, а также доступа по технологиям Intranet/Internet: из CGI- или API-программ и из Java апплетов и компонентов ActiveX. Например, при моделировании доступа к распределенным данным из CGI- или API-программ учитывается чтение HTML-формы с Web-сервера, передача имени и параметров CGI- или API-программы на сервер, выполнение SQL-операторов, закодированных в программе, передача обратно на рабочую станцию нового HTML-документа с результатами поиска. Аналогично учитываются особенности других способов доступа к базам данных. Комплекс КСАМ позволяет учесть наличие разных способов доступа к базам данных в одной сети и характерные особенности перечисленных выше моделей и технологий.
В работе выполнен анализ адекватности моделирования распределенных систем обработки данных с помощью КСАМ.
В пятой главе - приведены результаты использования разработанных методов и системы КСАМ в процессе проектирования глобальной системы абонентского обслуживания, функционирующей в рамках сети Билайн GSM и поддерживаемой АО "Вымпелком", а также при модернизации распределенной системы учета и анализа товарооборота "Склад", которая эксплуатируется в ряде нескольких филиалов крупных торговых компаний Москвы, в частности в фирме "ВЕСКО+М".
Публикации. По материалам диссертации опубликованы 38 печатных работ, в том числе 3 монографии
Объем работы. Диссертационная работа содержит 350 страниц основного текста, в том числе 80 рисунков и 22 таблицы. Список литературы включает 166 наименований.
