Разработка теоретических основ анализа процессов доступа к базам данных распределенных автоматизированных систем

Плутенко, Андрей Долиевич

Математическое моделирование, численные методы и комплексы программ

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

доктора технических наук: Плутенко, Андрей Долиевич
город: Благовещенск
год: 2004
специальность ВАК РФ: 05.13.18

Диссертация по информатике, вычислительной технике и управлению на тему «Разработка теоретических основ анализа процессов доступа к базам данных распределенных автоматизированных систем»

Автореферат диссертации по теме "Разработка теоретических основ анализа процессов доступа к базам данных распределенных автоматизированных систем"

На правах рукописи

ПЛУТЕНКО Андрей Долиевич

РАЗРАБОТКА ТЕОРЕТИЧЕСКИХ ОСНОВ

АНАЛИЗА ПРОЦЕССОВ ДОСТУПА К БАЗАМ ДАННЫХ РАСПРЕДЕЛЕННЫХ АВТОМАТИЗИРОВАННЫХ СИСТЕМ

05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени доктора технических наук

Благовещенск

2004

Работа выполнена в Амурском государственном университете (г.Благовещенск)

Научный консультант

- доктор технических наук Юрий Александрович Григорьев

Официальные оппоненты: - доктор физико-математических наук

Евгений Алексеевич Нурминский

заседании диссертационного совета Д 005.007.01 в Институте автоматики и процессов управления Дальневосточного отделения РАН по адресу: 690041, г. Владивосток, ул. Радио, 5

С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления Дальневосточного отделения РАН.

Автореферат разослан « 4 » октября 2004 г.

- доктор технических наук Сергей Петрович Сущенко

- доктор технических наук Чье Ен Ун

Ведущая организация: - Институт систем энергетики

им. Л.А. Мелентьева СО РАН (г. Иркутск)

Защита диссертации состоится « 12 » ноября 2004 г. в

часов на

И.о. ученого секретаря диссертационного совета

г 005-4

<Р9ГМв

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Ошибки, допущенные на ранних стадиях проектирования и обнаруженные на поздних стадиях жизненного цикла системы, требуют на их исправление по оценкам научных источников средств, соизмеримых со стоимостью разработки системы. Анализ производительности также важен при выборе готового программно-аппаратного обеспечения, масштабировании существующих систем и их адаптации. Однако в связи с высокой сложностью современных вычислительных систем проектировщику очень трудно проанализировать показатели качества разрабатываемой системы (особенно временные характеристики). В то же время попытка интуитивно выбрать вариант интеграции разнородных продуктов и параметры проектируемой системы может привести к существенной потере производительности на этапе эксплуатации и большим затратам на доработку вычислительной системы. Поэтому разработка теоретических методов, позволяющих прогнозировать показатели качества распределенных вычислительных систем, а также доведение этих методов до возможности практического использования является актуальной задачей.

Здесь нельзя ограничиться разработкой некоторых частных методов, необходимо предложить новый класс математических моделей, позволяющих оценивать различные объемно-временные характеристики выполнения сложных запросов, которые могут включать и элементарные условия, и соединения нескольких отношений. Эти модели должны учитывать

пвДОМДОМКМВУюЬанкых, а так-БНМНОТЕКА (

ГУЩ

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

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

Задачи исследования. Поставленная цель достигается путем решения ряда взаимосвязанных основных задач диссертационной работы, состоящих в следующем:

- разработка математического аппарата анализа времени выполнения запросов к базе данных с учетом их декомпозиции на подзапросы и соединения промежуточных таблиц;

- разработка аналитических методов оценки характеристик производительности вычислительных сетей, учитывающих параметры распределенной базы данных и выполняемых в сети запросов и транзакций;

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

- применение полученных результатов при решении практических задач.

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

Научная новизна результатов исследования состоит в следующем.

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

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

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

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

5. Получено функциональное уравнение относительно преобразования Лап-ласа-Стилтьеса функции распределения времени передачи кадра по шине локальной вычислительной сети, учитывающее вероятностные характеристики выполняемых в сети запросов. Найдено преобразование Лапласа-Стилтьеса функции распределения времени выполнения транзакции в сети, учитывающее особенности процесса передачи данных между рабочей станцией и сервером базы данных и параметры объемов данных, передаваемых по сети при выполнении запросов транзакций.

6. Доказана теорема о средней незаконченной работе в СМО МЕ/0/1 с неординарным потоком и произвольной, не допускающей прерывания обработки дисциплиной обслуживания, которая позволила использовать законы сохранения СМО при получении выражения для средней скорости передачи данных по шине ЛВС при обработке какой-либо транзакции, запускаемой с рабочей станции.

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

В диссертации представлены методические рекомендации по использованию разработанного комплекса для моделирования различных процессов доступа к базам данных: модели сервера базы данных, модели сервера приложений, а также доступа по технологиям Intranet/Internet: из CGI- или API-программ и из Java-апплетов и компонентов ActiveX. КСАМ позволяет учесть наличие разных способов доступа к базам данных в одной сети и характерные особенности перечисленных выше моделей и технологий. В работе выполнен анализ адекватности моделирования распределенных систем обработки данных с помощью КСАМ.

Часть исследований проводилась по заданию Министерства образования Российской Федерации и была включена в основные направления научно-исследовательских работ Амурского государственного университета в 1985-2003 годах. В рамках работ по данному научному направлению защищена диссертация на соискание ученой степени кандидата технических наук.

Разработанный математический аппарат, комплекс КСАМ и методические рекомендации были применены при решении ряда практических задач, в частности, при разработке глобальной системы абонентского обслуживания в рамках сети Билайн GSM, поддерживаемой АО "Вымпелком", и модернизации распределенной системы учета и анализа товарооборота, которая эксплуатируется в ряде филиалов крупных торговых компаний Москвы (фирм "ВЕСКО+М").

Отдельные результаты исследований используются в учебном процессе Амурского государственного университета в дисциплинах "Организация баз дан-

ных", в курсовом и дипломном проектировании студентов специальности 220200 "Автоматизированные системы обработки информации и управления".

Апробация работы. Основные результаты диссертации были представлены и обсуждены на следующих конференциях, совещаниях и симпозиумах: научно-практическом семинаре "Применение баз данных" (Пенза, 1997), симпозиуме "Научное и научно-техническое обеспечение экономического и социального развития Дальневосточного региона" (Комсомольск-на-Амуре, 1999), республиканской научно-исследовательской конференции'"Измерения, автоматизация и моделирование в промышленных и научных исследованиях" (Бийск, 2000), международной научно-технической конференции "Информационные системы и технологии" (Новосибирск, 2000), 2-й Всероссийской научно-технической конференции с иностранным участием "Энергетика: управление, качество и эффективность использования энергоресурсов" (Благовещенск, 2000), 6-й международной конференции "Качество и использование электрической энергии" (Краков, 2001), 6-й международной восточно-европейской конференции (АОВК) "Прогресс в базах данных и информационных системах" (Братислава, 2002), П-й международной научно-практической конференции "Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем" (Новочеркасск, 2004), международной научной конференции "Интеллектуализация обработки информации И0И-2004" (Алушта, 2004).

Публикации и личный вклад автора. По материалам диссертации опубликованы 38 печатных работ, в том числе 3 монографии [1-3]. В работах, опубликованных в соавторстве, автору принадлежат следующие научные и практические результаты: в работах [1,3, 6, 8,28,29-32] - постановка задачи, методы и основные алгоритмы решения и доказательства теорем; в работах [5,9-11,15,17,21,23, 26] - разработка основных теоретических положений организации распределенных систем обработки данных; в работах [2, 7,20,22,24, 25] - постановка задачи и формализация функционирования вычислительных сетей; в работах [12, 20, 3338] - организация, методы и алгоритмы функционирования программного комплекса анализа моделей доступа к распределенньм базам данных.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложений. Она изложена на 350 страницах машинописного текста, включая 80 рисунков, список литературы из 166 наименований и приложения на 18 страницах.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе выполнена классификация моделей доступа к базам данных. Рассмотрены следующие модели: модель файлового сервера, модель сервера базы данных, модель сервера приложений, модели доступа к базам данных в Intranet/Internet по технологиям CGI, API, ASP, из Java-апплетов и компонентов ActiveX, а также модель доступа к данным в системах с объектными архитектурами CORBA и DCOM. Выявлены преимущества и недостатки указанных моделей. Сделан вывод, что перед проектировщиком автоматизированной системы (АС) стоит непростая задача выбора приемлемой модели доступа к базе данных. Важность этой задачи обусловлена тем, что модель доступа к базе данных выбирается на начальных этапах проектирования АС и она определяет архитектуру будущей системы, которую очень трудно изменить на поздних этапах разработки. Поэтому важно иметь математические методы анализа показателей качества различных моделей доступа к базам данных, помогающие проектировщику выработать концепции разрабатываемой автоматизированной системы.

эффективности либо основаны на результатах натурных экспериментов (система !щшгу и др.), либо позволяют решать частные задачи (сравнение и выбор метода построения индекса, оптимизация запросов, организация выполнения транзакций и т. д.), либо обеспечивают оценку показателей качества функционирования АС при упрощенных предпосылках (модель 2RC, синтез WMS и др.). Ни один из данных методов не позволяет рассчитать временные характеристики выполнения запросов и загрузки устройств на ранних этапах проектирования распределенной АС с учетом параметров концептуальной схемы базы данных, спецификаций разрабатываемых программ, архитектуры будущей системы, наполнения базы данных. Эта задача решается в следующих главах диссертации.

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

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

Пусть - множество атрибутов таблицы (отношения) которые входят в

условие (предикат) подзапроса, В общем случае на атрибуты в

условии поиска накладываются ограничения, которые могут изменяться при разных обращениях к запросу. а^ - атрибут из множества Ац Т. е. А1 = По •

определению Лемма 1 позволяет найти ПЛС времени чтения

блоков индексов по тем атрибутам из А¡, для которых при выполнении подзапроса используются индексы. Лемма 2 позволяет получить ПЛС времени чтения блоков таблицы с записями, удовлетворяющими условию поиска Гг Теорема 1 доказывает выражение для ПЛС времени обработки подзапроса.

Лемма 1. Преобразование Лапласа-Стилтъеса времени чтения блоков нижнего уровня по всем используемым в подзапросе ¡2, индексам таблицы Л,-равно:

(1)

здесь N1 - множество тех атрибутов из А^ для которых при выполнении подзапроса Qi используются индексы; («) - ПЛС времени чтения одного блока нижнего уровня индекса по атрибуту ау, - производящая функция числа читаемых блоков индекса по атрибуту ау.

Ниже приведены выражения для производящей функции ^(г). Пусть

где - те значения атрибута которые удовлетворяют соответствующему

элементарному условию по в предикате Если после упорядочивания множество элементов домена атрибута образуют последователь-

ность смежных значении, то к

ш тл V

где Рд 0 = ^(0), рук= £ ~~

(3)

,к> 1, = 1^(1-2)), /=(*- 11 тёМд

- производящая функция числа записей в таблице - вероятность,

что атрибут какого-нибудь кортежа (записи) таблицы принимает значение

- максимальное число записей в блоке нижнего уровня

т=1

индекса по атрибуту

В противном случае, чтобы получить выражение для 91}{£), необходимо

определить произведение выражений (3), которые соответствуют участкам смежных значений атрибутов в множестве \теи •

Лемма 2. Преобразование Лапласа-Стилтьеса времени чтения блоков таблицы Щ с записями, удовлетворяющими условию по^О^а имеет вид

где Д (.$) - ПЛС времени чтения одного блока т/ВблуцЫ) - производящая функция числа читаемых блоков таблЛЦы

Если записи, удовлетворяющие условию поиска ^, располагаются в блоках таблицы /?,• последовательно (в соседних строках), то

г,(*)=К№1( I

*=1 /=(*-1)г,+1

здесь определяется выражением

т = *))" = О, (1 -/¡(1- *)),

(5)

(6)

г,— максимальное число записей в блоке таблицы Я/.

В общем случае, если записи, удовлетворяющие условию поиска не располагаются в блоках таблицы последовательно (в соседних строках), то производящую функцию /¡(г) читаемых блоков таблицы ^ можно найти с помощью произведения выражений вида (5), которые соответствуют участкам с последовательным размещением записей в блоках.

В работе определена рекуррентная процедура расчета вероятности (см. (6)) того, что произвольная запись таблицы удовлетворяет условию поиска Вероятность, что запись таблицы Л, удовлетворяет элементарному условию поиска по атрибуту в предикате можно получить с помощью следующего выражения:

здесь вероятности определены выше при описании выражения (6). В частности из (7) следует, что если вероятности щт равны, то

где |Му| - мощность множества Л/^(см. (2)), а - мощность домена D,j.

Элементарные условия по атрибутам |а^ ^ в Fj могут быть связаны различными

логическими условиями: AND, OR и может быть NOT.

Теорема 1. Для преобразования Лапласа-Стилтьеса времени выполнения подзапросф справедливо следующее выражение:

где Nj - множество тех атрибутов й@ для которых при выполнении подзапроса Q, используются индекё^^) — ПЛС времени чтения одного блока нижнего уровня индекса по атр^бУ^У) - производящая функция числа читаемых блоков индекса по атрибуту а определяемая выражением (3); Л СО - ПЛС времени чтения одного блока тОблиЦы) - производящая функция числа читаемых блоков таблиЦы определяемая выражением (5).

Утверждение теоремы 1 следует из формул (1) и (4), являющихся утверждениями лемм 1 и 2, и свойств ПЛС.

Соединение промежуточных таблиц {g,} выполняется попарно в последовательности, определенной при построении оптимального плана. Соединение является рекуррентной математической процедурой: Q'^QxQi^, k = 2,n. Первоначально Q = Q^. Далее без потери общности будем считать, что ¡¡[=к. Будем также полагать, что At = ja^ - это множество всех атрибутов какой-нибудь со-

единяемой таблицы. Для оценки времени соединения таблиц (теоремы 2, 3, 4) на каждом шаге рекуррентной процедуры необходимо выполнить следующие действия:

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

2. Для каждого атрибута соединяемых таблиц определить его домен

Сначала покажем, как указанные выше задачи 1 и 2 решаются для соеди-

1. Производящая функция для числа записей определяется выражением (6), а множество атрибутов совпадает с

2. Представим условие F¡ в виде дизъюнктивной формы. Домен атрибута в таблице определим следующим образом:

а) если атрибут входит во все конъюнкты дизъюнктивной формы, то в этом случае полагаем

- это те значения атрибута а«, которые удовлетворяют элементарному условию по ау в конъюнкте с номером е,

б) иначе домен атрибута оставляем без изменения (как в таблице Если домен атрибута изменился (см. (10)), то необходимо выполнить "нормирование" вероятностей элементов нового домена

ПЧ = №>]т\т и вероятности {щт[

Ут >т'

няемых таблиц которые соответствуют подзапросам:

(10)

Ищк

к=1

Покажем теперь, как

1) найти производящую функцию числа записей в промежуточной таблице

, которая, в свою очередь, может соединяться с таблицей а

также множество атрибутов в таблице Q;

2) определить домены = 1 атрибутов а^, добавленных в таблицу Q в результате соединения, и вероятности ^т) •

Без потери общности будем считать, что соединяются таблицы и т.е. 0.'-=0,\Ъ><0.г, т. к. далее рекуррентно можно положить Ql'.= Q И £?2:=£?4> к = Ъ,п. Рассмотрим общий случай соединения таблиц по нескольким атрибутам. Без потери общности будем считать, что таблицы соединяются соответ-

ственно по атрибутам

В дальнейшем под соединяемыми записями таблиц и 02 будем понимать записи этих таблиц, в которых значения атрибутов связи

{а\\=<1\Щ е0\1>-'а1г=с1\тг еАЛ> {а1\=(17Щ е В2\>->а2* = <*Ыг еА>Л связаны отношением т. е. - условие связи таблиц по атрибутам связи

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

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

Лемма 4 Пусть количества кортежей в разных группах соединяемых записей таблиц) 02 независимы в совокупности. Тогда справедливы следующие утверждения:

1. Производящая функция числа записей вЗ т^лиц^ имеет следующий вид:

где р2^ — 2 ^ ^ — вероятность, что число записей втаблице()2 равно N;

У2(г) - производящая функция числа записей таблицы 0^', — производящая функция числа записей таблицы Ql;

<р - отношение связи таблиц Q^í и по атрибутам связи {яц,...,^,,} и

{а21.....а2!} (=, <, >, Ф или более сложное условие).

Множество атрибутов таблицы Q равно Ад=А1[)А2, где Ау и А2 -множества атрибутов таблиц Оу и 0,2.

2. Для доменов атрибутов связи {йц,...,^,.} и {а21,...,а25}, вошедших в Q, справедливы следующие выражения:

Вероятности появления элементов доменов D^j и в кортежах таблицы Q равны

Домены остальных атрибутов таблицы Q и вероятности появления элементов этих доменов в кортежах Q не изменяются.

В диссертации доказаны леммы 5, 6, 7 и теоремы 2, 3,4, позволяющие найти ПЛС времени соединения ¡2 = 01 |>"'аб2> которое может быть выполнено оптимизатором с помощью одного из следующих методов: с помощью вложенных циклов (N0), посредством сортировки-слияния (8М1), с помощью хешированно-го соединения (Ш). Далее производящие функции К] (г) и У2(г) числа записей в соединяемых таблицах 0\ и ^ определяются формулами (6) и (12). А производящая функция числа записей в таблице - рекуррентной формулой (12).

Теорема 2. Преобразование Латаса-Стилтъеса времени выполнения соединения таблиц Оу и 02 методом ЫЫ имеет вид:

где ^(г), ^С2)' - производящие функции числа записей в таблицах ^

и ¡2 = 21 >< С?2' ^сСО - ПЛС времени сравнения атрибутов связи двух кортежей из Q^ и <22Чу(.т) - ПЛС времени соединения двух кортежей из и

Если используется метод соединения посредством сортировки-слияния 8М1, то сначала таблицы И ¡2г сортируются по атрибутам связи (при необходимости), а затем выполняется их соединение. Предположим, что сортировка выполняется в порядке возрастания атрибута связи и элементы домена этого атрибута также упорядочены в порядке возрастания: здесь

мощность домена , I = 1,2. Также предположим, что сортировка выполняется обычным способом: путем перемещения влево записи внутрь уже упорядоченных записей (пузырьковый способ).

Лемма 5. Пусть число перемещений записей на к-ом шаге не зависит от числа перемещений на предыдущих шагах. Тогда производящая функция числа перемещений при сортировке записей таблицы Q| по атрибуту связи ал имеет вид

здесь Рм - вероятность, что количество записей в таблицеравно N.

Теперь найдем производящую функцию числа сравнений атрибутов связи соединяемых таблиц ¡2] И <22.

Лемма 6. Производящая функция количества сравнений атрибутов связи при соединении та@лиц()2 имеет следующий вид:

здесь /,] = шах т; М,={т\с1Лт<:с1}; £/ = тттахс/(]И; У,(г) - производящая

функция числа записей в таблице (),, 2 = 1,2.

Теорема 3. Преобразование Лапласа-Стилтъеса времени £м выполнения соединения таб^^Щ методом БЫТ имеет вид:

«=[Яц(ВД)] • [Я21(ВД)1 • • ^(ВД), (18)

- производящая функция числа перемещений при сортировке записей таблицы по атрибуту связи а,, определяемая выражением (16), 1 = 1,2; Е(г) -производящая функция количества сравнений атрибутов связи при соединении таблиц и определяемая выражением (17); Уд(г) - производящая функция числа записей в таблице = ><]б2'' ^гСО - ПЛС времени перемещения двух кортежей при сортировке таблиц ^ и — ПЛСвремени сравнения ат-

рибутов связи двух кортежей из и 2г> —ПЛСвремени соединения двух

кортежей из б) к

Рассмотрим теперь метод хешированного соединения Ш. Лемма 7. Справедливы следующие утверждения: 1. Производящая функция числа записеЩ^^в } =Ааблице^.)име-ет вид:

здесь К, (г) — производящая функция числа записей в таблице К1={т\ Ъ{с1Лт ) = ./}; й - хеш-функция, которая возвращает номер раздела; АЛт - элемент домеЕ^ атрибута связи таблицы Qr

2. Домен атрибута свящргаблицы Q¡J включает следующие элементы.

Вероятности появления элементов доменов в кортежах таблиЦ^равны

здесь в правей - ЦмчОсти -Домены остальных атрибутов таблицы вошедших из Q¡, и вероятности появления элементов этих доменов в кортежах Qy не изменяются.

Теорема 4. Преобразование Лапласа-Стилтъеса времени выполнения соединения таб@цц Q■методом.HJ имеет вид:

где г - число разделов; - это ПЛС времени соединения таблиц и

()г], выполненного методом ЫЫ или SMJ. Формулы дл^яОпределяются

выражениями (15) или (18). Производящие функции числа записей соединяемых табчиц (^^^и £?2:=бг./> а также домены атрибутов связи определяются

выражениям^) и (20), ] = \,г.

На основании приведенных выше результатов в работе получено ПЛС времени выполнения исходного запроса.

Теорема 5. Преобразование Лапласа-Стилтъеса времени выполнения исходного запроса имеет следующий вид:

где 7}($)- ПЛС времени выполнения подзапроса Q¡l которое определяется выражением (9); Ч^^Д«) - ПЛС времени у -го соединения промежуточных таблиц, которое определяется одним из выражений (15), (18) и (22) (тип соединения назначается оптимизатором для каждого]-го соединения); п - число подзапросов.

Доказательство теоремы 5 следует из свойств ПЛС и теорем 1 - 4. В отличие от существующих подходов с помощью преобразования (23) можно оценивать не только математическое ожидание времени выполнения запросов, но и моменты более высоких порядков.

В третьей главе диссертации разработан метод анализа локальных вычислительных сетей (ЛВС), основанный на законах сохранения для СМО и учитывает важные особенности функционирования современных ЛВС: работу сетевых адаптеров станций, квитирование данных, характеристики объемов данных, передаваемых по сети в процессе выполнения 8рЬ-запросов к распределенной базе данных, а также предложены оценки для глобальных и магистральных сетей передачи данных.

Выполнена формализация процесса передачи данных по ЛВС при выполнении 8рЬ-заироса в архитектуре "клиент-сервер" и на ее основе разработана математическая модель функционирования ЛВС. Эта модель представляет собой замкнутую сеть массового обслуживания (СеМО).

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

где - скорость чтения кадров из ОП в буфер СА z-й рабочей станции, /лф) -

скорость передачи кадров по шине сети.

Показано, что если СА сервера и рабочей станции имеют разные скорости передачи данных, то возможна ситуация, когда после передачи очередного кадра с сервера на рабочую станцию сервер будет ожидать квитанцию от рабочей станции. Дана оценка вероятности данной ситуации:

где ¡1 = mil\(цс>Цф1), flc -скорость чтения кадров из оперативной памяти в буфер СА сервера; - скорость передачи кадров по шине сети на i-Ю рабочую станцию; nt - скорость передачи кадров из буфера СА i-й рабочей станции в оперативную память; - количество буферов сетевого адаптера рабочей станции. Определены механизмы учета вероятностей (24) и (25) при оценке параметров модели.

В работе получено функциональное уравнение относительно ПЛС времени передачи кадра по шине ЛВС, учитывающее вероятностные характеристики числа операторов SQL, выполняемых при обращении к какой-либо транзакции, объема данных, передаваемых на сервер и обратно при обработке операторов SQL, и позволяющее определить начальные моменты времени передачи кадра по шине: L U i I

П T.PvGjk(Wk (ф,4 (S)) ■ vk (Dk (Ф? (s)))) =

*=ij=i

здесь Ф,(у) - ПЛС времени передачи кадра по шине ЛВС; рг/ - вероятность обращения/-й рабочей станции ку-й транзакции, 1 = 1,ЛТ, _/ = 1,Л/; - производящая функция (ПФ) числа SQL-запросов типа Ок, выполняемых при обраще-

нии

ку-й j =ч]раНдаквИи; i Щф - ПФ объема данных, передаваемых

на сервер при обработке 8рЬ-запрсса ; - ПФ числа кортежей в результирующей таблице после выполнения на сервере соединений всех подзапросов запроса ; - ПФ длины кортежа результирующей таблицы; Ь - макси-

мальный объем данных в одном кадре; - сумма длин заголовков кадра и пакета, <»($) - ПЛС времени передачи одного байга по глине сети (если это время по-

стоянно; то со($) = е с, С - производительность передачи данных по шине сети).

Доказано выражение для ПЛС времени выполнения какой-либо транзакции,

запускаемой сй рабочей станции: I м

здесь - ПЛС времени ожидания в очереди и передачи кадра по шине сети; A,(i) - ПЛС времени передачи кадра из (в) буфера ОП в (из) буфер СА /-й рабочей станции по шине компьютера; - ПЛС времени выполнения запроса SQL £-го типа сервером СУБД; ) - ПЛС времени передачи кадра из (в) буфера ОП в (из) буфер СА сервера по шине компьютера; qc - вероятность, что после завершения передачи очередного кадра на йо рабочую станцию буфер СА сервера еще не заполнен и передатчик СА вынужден простаивать; H,(s) - ПЛС времени ожидания сервером квитанции от /-й рабочей станции (среднее время h ожидания квитанции определяется выражением ht = —).

Из (27) получено выражение для среднего времени передачи всех входных и выходных данных какой-либо транзакции, запускаемой с 1-й рабочей станции:

(d - rw, XI - Чо, + ?сД(5)) + ЧН,(*)Ас(*)))Ш)))

(27)

Показано, что для того, чтобы воспользоваться формулой (28), необходимо определить величину Т (среднее время ожидания в очереди и передачи кадра по шине сети). В диссертации рассмотрены два способа оценки : с помощью замкнутой СеМО и разомкнутой СМО.

Для разомкнутой СМО возникает проблема, связанная с вычислением средней величины незаконченной работы V для группового входного потока. Для решения этой задачи в диссертации была доказана следующая теорема.

Теорема 6 Средняя незаконченная работа и в системе массового обслу-живанияМ/й/! с неординарным (групповым) потоком и произвольной дисциплиной обслуживания, не допускающей прерывания обработки, равна

где Л - интенсивность группового потока (например, транзакций); у1 - математическое ожидание числа заявок (например, кадров) в группе; у2 - вторая производная производящей функции числа заявок в группе в точке 2 = 1; (р^ - математическое ожидание времени обслуживания заявкф% - второй начальный момент времени обслуживания заявки.

На основании закона сохранения для СМО и теоремы 6 было получено выражение для средней скорости передачи данных кадрами максимальной длины при обработке какой-либо транзакции, запускаемой с рабочей станции:

здесь - интенсивность обращений /-й рабочей станции к транзакциям;

- среднее число кадров,

N j N L U _

л=ЕЛ. Г1=тХЛХ2>!,GAH(p»kn+Pvtn)

л(=1 и

передаваемых по сети в процессе обработки некоторой транзакции, запускаемой с рабочей станции; - загрузка шины ЛВС; - среднее время переда-

чи кадра по шине ЛВС при обработке какой-либо транзакции, инициированной с рабочей станции.

Показано, что дисциплины передачи данных по шинам Ethernet и Token Ring сохраняют работу и не допускают прерывания передачи кадров. Это позволило использовать при анализе сетей выражение (30). В диссертации рассмотрены особенности функционирования глобальных и магистральных сетей передачи данных Х.25, Frame Relay, FDDI, ATM, обеспечивающих связь между несколькими ЛВС, и получены некоторые оценки.

В четвертой главе разработаны схема базы данных, база знаний, машина вывода и пользовательский интерфейс комплекса инструментальных средств анализа моделей доступа к базам данных распределенных систем обработки данных (КСАМ), даны методические рекомендации по использованию КСАМ и приведены результаты измерений и вычислительных экспериментов, подтверждающих адекватность разработанных методов. Среда разработки комплекса - Oracle и Developer/2000. КСАМ включает взаимосвязанные подсистемы, обеспечивающие описание:

1) концептуального проекта распределенной системы обработки данных (РСОД) (концептуальной (инфологической) схемы базы данных РСОД и наполнения базы данных (прогнозируемого числа записей в таблицах и мощностей атрибутов; запросов (SQL-операторов) и транзакций РСОД, которые могут обращаться к другим транзакциям распределенной системы);

2) архитектуры РСОД (топологии и характеристик узлов и сетей из реестров результатов тестов ТРС и параметров сетей; распределения таблиц (с учетом тиражирования) и транзакций по узлам РСОД; интенсивностей обращений рабочих

станций к транзакциям).

На рис. 1 представлена реализованная в КСАМ схема организации связей между компонентами проектируемой распределенной системы.

Запросы Концептуальный

проект

Рис. 1. Реализованная в КСАМ схема организации связей между компонентами РСОД

Здесь сплошными стрелками показаны связи типа "обращение к", а пунктирные линии изображают связи типа "входят, размещаются в". Так запросы (операторы SQL) входят в состав транзакций (2), при выполнении которых операторы SQL обращаются к таблицам базы данных (1). Описания таблиц базы данных, запросов и транзакций образуют концептуальный проект (КП) РСОД. При проектировании стремятся, чтобы концептуальный проект не зависел от реализации, то есть от архитектуры будущей РСОД (комплекса технических средств, общесистемных пакетов и др.). После выбора КТС, ОС, СУБД выполняется распределение таблиц базы данных и транзакций по узлам распределенной системы (стрелки 3, 4, 5, 6). Таблицы хранятся на серверах базы данных, а транзакции могут размещаться на рабочих станциях, серверах приложений, Web-серверах, сер-

верах базы данных (хранимые процедуры). Стрелки 7, 8, 9 обозначают обращения транзакций к таблицам базы данных. Следует отметить, что серверы приложений и Web-серверы могут отсутствовать или располагаться в тех же узлах, что и серверы базы данных.

В рамках КСАМ созданы реестры с описанием параметров различных типов сетей, а также с результатами тестов, проведенных по спецификациям международной организации Transactional Processing Performance Council (TPC) для разных серверов и суперсерверов (более 20 фирм: Sun, Compaq, HP, Digital, IBM и т.д.), СУБД (Oracle, Informix, Sybase, MS SQL Server и т. д.), сетевых ОС (различных версий UNIX, Windows NT 4.0 и т. д.) и серверов приложений (Tuxedo, TopEnd и т. д.).

На основе описания параметров РСОД комплекс анализирует характеристики производительности и выявляет "узкие места" распределенной системы. КСАМ рассчитывает для каждого варианта архитектуры следующие показатели:

а) загрузки узлов (процессоров или дисков станций) и их составляющие по запросам к БД и по транзакциям;

б) загрузки сетей (шин ЛВС или каналов глобальных и магистральных сетей передачи данных) и их составляющие по запросам к БД и по транзакциям;

в) время выполнения отдельных транзакций РСОД и их составляющие по узлам, по сетям, по запросам к БД, по транзакциям;

г) время реакции РСОД на запрос клиента;

д) числа блоков базы данных, которые обрабатываются при выполнении запросов к базе данных РСОД.

В работе показано, что КСАМ является аналитической, статической, с неопределенными данными и с множеством дополняющих друг друга источников знаний экспертной системой (ЭС). Такие ЭС часто называют доопределяющими. Эти системы решают задачи интерпретации исходных данных и диагностики вариантов решений. Для экспертных систем характерно наличие базы данных, базы знаний, машины вывода, механизма объяснений и развитого пользовательского интерфейса.

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

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

2. Хранение реестров конфигураций узлов и каналов, а также результатов тестирования этих конфигураций по спецификациям ТРС-С, опубликованных международной организацией Transactional Processing Performance Council.

3. Обеспечение хранения и ведения составляющих загрузок устройств и времени выполнения транзакций; эти составляющие используются для поддержки механизма объяснений экспертной системы, т. е. для выделения запросов, транзакций, узлов и сетей, которые могут являться потенциальными "узкими местами" проектируемой распределенной системы.

4. Поддержка целостности (непротиворечивости) базы данных КСАМ.

Эти задачи удалось решить путем выделения требуемых сущностей ER-диаграммы и организации связей между ними.

База знаний КСАМ организована в виде фреймов. Фрейм представляет собой совокупность слотов, описывающих свойства концептуального объекта (концепта). Связь между фреймами КСАМ определяется последовательностью выполнения SQL-запросов транзакций и связями транзакций между собой, а также последовательностью используемых при этом ресурсов вычислительной сети. Машина вывода КСАМ обеспечивает заполнение фреймов данными из базы данных, организует их динамическое связывание и выполняет расчеты временных показателей проектируемой РСОД. На рис. 2 представлен граф связи фреймов базы знаний КСАМ. Этот граф изображен в виде диаграммы потоков данных (ДПД). Здесь функции А1-А14 обозначают фреймы базы знаний, а хранилища D1-D3 -некоторые совокупности сущностей базы данных КСАМ.

Фрейм "Процесс" является корневым. После его активизации соответствующая LISP-процедура анализирует транзакции, к которым обращаются узлы РСОД. Транзакции могут содержать SQL-запросы к распределенной базе данных

А11

Сост времени транз по »лох I -транзакциям.;

А14

Сост »ремени »ыл транз по каналам .

Рис 2 Граф связи фреймов базы знаний КСАМ

и обращения к другим транзакциям. Для очередного SQL-запроса активизируется фрейм "SQL". После подстановки в слот имени запроса запускается соответствующая процедура-демон IF-ADDED, которая выполняет декомпозицию запроса на подзапросы и заполняет слоты данного фрейма, используемые в следующих дочерних фреймах. Каждый подзапрос связан с таблицей, указанной в запросе. Связь между однородными фреймами "SQL" определяется последовательностью выполнения SQL-запросов транзакций и связями транзакций между собой.

Далее активизируется фрейм "Виртуальный канал". При подстановке в слот типа LIST имен таблиц запроса запускается процедура-демон, которая на основании информации из базы данных КСАМ определяет виртуальные каналы для каждого подзапроса. Виртуальный канал (ВК) представляет собой путь от исходного узла, где выполняется исходный SQL-запрос, до узла, где хранится таблица, связанная с подзапросом. Для каждого ВК активизируются фреймы "Узел" и "Канал". Для начального и конечного узла ВК накапливается загрузка узла и оценивается время выполнения курсора и подзапроса на основании данных, полученных от фреймов "Виртуальный канал" и "SQL". С помощью дочерних фреймов "Составляющие загрузки узла по транзакциям" и "Составляющие загрузки узла по запросам" сохраняются составляющие загрузки узлов в БД КСАМ.

Для всех каналов, вошедших в ВК, фрейм "Канал" накапливает загрузку канала и оценивает время передачи на основании данных, полученных от фреймов "Виртуальный канал" и "SQL". Дочерние фреймы "Составляющие загрузки канала по транзакциям" и "Составляющие загрузки канала по запросам" сохраняют составляющие загрузки каналов в БД КСАМ. Фрейм "Время выполнения транзакции", который является дочерним по отношению к фреймам "Узел" и "Канал", оценивает время выполнения текущей транзакции и с помощью своих дочерних фреймов All, A12, А13, А14 сохраняет составляющие этого времени в БД КСАМ.

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

ли реализованы арифметические операции с нечеткими числами. Как уже упоминалось, в КСАМ используется трапециевидная форма представления нечеткого числа, которая характеризуется четырьмя числами (Rl, R2, R3, R4). В этом случае операции над нечеткими числами А и В можно свести к операциям над элементами (А1, А2, A3, А4) и (В1, В2, ВЗ, В4) этих нечетких чисел. Пусть С=А0В, где 0 -знак арифметической операции. Тогда, аппроксимируя С трапециевидным нечетким числом, получим

(Cl, С2, СЗ, С4)= (А1°В1, А2°В2, АЗ°ВЗ, А4°В4) - для операций +, (CI, С2, €3, С4)= (А1°В4, А2°ВЗ, АЗ°В2, А4°В1) - для операции /.

Причем для операций + и - получаем точную функцию принадлежности. Приведенная выше процедура аппроксимации позволяет оценить нечеткие значения выходных характеристик за один прогон модели.

Механизм пополнения знаний определяется правилами ведения реестров КСАМ с описанием параметров различных типов сетей, а также с результатами тестов, проведенных по спецификациям международной организации Transactional Processing Performance Council (TPC) для разных серверов и суперсерверов. Реестры хранятся в базе данных КСАМ и могут также пополняться на основе результатов измерений. Пользовательский интерфейс КСАМ включает 14 входных и выходных форм, каждая из которых имеет головное окно, где отображаются объекты описаний и связи между ними, и вспомогательные окна, где выводятся дополнительные свойства этих объектов.

В диссертации разработаны методические рекомендации по использованию комплекса КСАМ для моделирования различных процессов доступа к базам данных: модели сервера базы данных, модели сервера приложений, а также доступа по технологиям Intranet/Internet: из CGI- или API-программ и из Java-апплетов и компонентов ActiveX. Например, при моделировании доступа к распределенным данным из CGI- или API-программ учитывается чтение HTML-формы с Web-сервера, передача имени и параметров CGI- или API-программы на сервер, выполнение SQL-операторов, закодированных в программе, передача обратно на ра-

бочую станцию нового HTML-документа с результатами поиска. Аналогично учитываются особенности других способов доступа к базам данных. Комплекс КСАМ позволяет учесть наличие разных способов доступа к базам данных в одной сети и характерные особенности перечисленных выше моделей и технологий.

В работе выполнен анализ адекватности моделирования распределенных систем обработки данных с помощью КСАМ. Были промоделированы четыре конфигурации, соответствующие модели сервера приложений доступа к базе данных. В этих конфигурациях в качестве сервера базы данных использовались следующие станции: Ultra Enterprise 150 с ОС Solaris и СУБД Sybase-1, Ultra Enterprise 6000 с ОС Solaris и СУБД Sybase на 20 процессоров, Compaq ProLiant 2500 с ОС Windows NT и СУБД MS SQL Server, Compaq ProLiant 5000 с ОС Windows NT и СУБД MS SQL Server на 4 процессора. При моделировании количество терминалов было соответственно равно 1160,15360,2360 и 6500. Для каждой конфигурации моделировалось выполнение 5 транзакций, алгоритмы которых соответствовали спецификациям ТРС-С на уровне SQL-операторов. Результаты моделирования сравнивались с результатами тестирования соответствующих конфигураций, опубликованными международной организацией Transactional Processing Performance Council. Для 20 (4x5) проанализированных транзакций погрешность моделирования распределилась следующим образом: меньше 30% - 10 транзакций, от 30 до 60% - 7 транзакций, больше 100% — 3 транзакции. Относительно большая погрешность моделирования для последних 3 транзакций была связана с перегрузкой серверов базы данных для 3-й и 4-й конфигураций (их загрузка была равна 0,81 и 0,92). Таким образом, получаемую при использовании КСАМ погрешность моделирования можно считать удовлетворительной для случая, когда загрузки ресурсов системы не превышают критических значений. При этом следует учесть, что КСАМ применяется в основном на ранних этапах проектирования, когда стремятся спрогнозировать и устранить потенциальные "узкие места", т. е. не допустить превышения загрузок устройств их критических значений.

В пятой главе приведены результаты использования разработанных методов и системы КСАМ в процессе проектирования глобальной системы абонентского

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

При разработке глобальной системы абонентского обслуживания в рамках сети Билайн GSM были проанализированы три архитектурных решения на базе оборудования компаний Compaq (вариант 1), Hewlett Packard (вариант 2) и Sun&IBM (вариант 3) с целью выбора лучшей конфигурации. Каждый вариант включал следующие структурные элементы: сервер базы данных, телекоммуникационный сервер, серверы приложений, терминалы и коммуникационное оборудование.

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

В диссертации приведены результаты анализа АС "СКЛАД" фирмы "ВЕСКО+М", реализованной на базе архитектуры "клиент-сервер". Клиентские рабочие станции и сервер базы данных объединены в локальную вычислительную сеть. ЛВС построена на базе сети Ethernet на витой паре и коаксиальном кабеле. Концентраторы Ethernet соединены между собой с помощью коаксиального кабеля R58, в то время как конечные рабочие станции и сервер подключены через сетевые адаптеры к концентраторам на 8 и 24 порта с помощью витой пары 5-й категории. Печать отчетов осуществляется на принтере через ЛВС, как на сетевой ресурс. Сервер базы данных АС "СКЛАД" установлен на сервере Compaq ProLiant 3000.

АС "СКЛАД" состоит из комплекса прикладных программ, а также сервера управления базами данных СУБД Centura (GUPTA) SQLBase версии 6.x. На рабо-

чих станциях выполняются прикладные программы (транзакции), которые выступают в роли клиентов системы управления базами данных. СУБД ведет базу данных и выполняет запросы клиентов. Операционная система (ОС) рабочих станций

- MS Windows 95/98, а ОС сервера - MS Windows NT 4.0. Для работы АС "СКЛАД" на каждом клиенте установлен продукт Centura Deployment - системные библиотеки и программы Centura, а также CRPE - Crystal Reports Print Engine

- модули, необходимые для исполнения отчетов. Взаимодействие между CRPE и сервером СУБД осуществляется через ODBC (Open Database Connectivity - интерфейс взаимодействия с базами данных).

Было установлено, что при числе пользователей больше 25 система работала неустойчиво, время доступа превышало установленные пределы.

Был промоделирован базовый вариант анализируемой АС. С помощью КС AM были определены составляющие загрузок сервера (p«0,0108N, N - число рабочих станций) и шины ЛВС (p«0,0128N) по транзакциям. Из построенных графиков выяснено, что "узким местом" системы является транзакция "Загрузка дня" (загрузка сведений об операциях, совершенных с товарами на различных территориях, в центральную базу данных). В третьей главе диссертации было показано, что критическое значение загрузки шины сети Ethernet равно примерно 0,3. Также известно, что критическое значение загрузки узла сети равно 0,6. Было получено, что "узким местом" аппаратной части базового варианта АС является шина сети Ethernet 10 Мбит/с, т. к. для сети критическое число рабочих станций равно N(0,3)=24, а для сервера - N(0,6)=56. Для устранения "узкого места" АС рассматривались два варианта: 1) переход на сеть 100 Мбит/с, 2) оптимизация транзакции "Загрузка дня" (перемещение таблиц загрузок и данной транзакции в виде хранимой процедуры на другой сервер, тиражирование данных из таблиц загрузок на основной сервер в ночное время, в интервале от 0 до 8 часов).

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

сертации результатов моделирования был сделан вывод, что оптимизация только одной транзакции "Загрузка дня" позволяет увеличить нагрузочную способность системы с 24 до 42 клиентов, а переход на сеть 100 Мбит/с - до 56 пользователей. Причем при переходе с сети 10 Мбит/с на сеть 100 Мбит/с "узким местом" становится сервер базы данных.

В приложениях приведены описание транзакций автоматизированной системы абонентского обслуживания сети Билайн GSM и материалы, подтверждающие внедрение результатов диссертации.

2. Разработан математический аппарат, позволяющий получать ПЛС функции распределения времени выполнения запроса к базе данных с учетом его декомпозиции на подзапросы и выбираемых оптимизатором запросов методов соединения промежуточных таблиц. В рамках этого аппарата доказаны формулы, которые могут быть использованы для оценки числовых характеристик времени выполнения запросов с учетом чтения блоков индексов и данных, числа кортежей соединяемых таблиц, времени соединения таблиц по методам NLJ, SMJ и HJ.

4. На основе полученных теоре зработан комплекс

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

инструментальных средств анализа моделей доступа к базам данных распределенных систем обработки данных (КСАМ), который по описанию запросов и транзакций приложений, таблиц базы данных, топологии сети, виртуальных каналов, параметров сетей, каналов связи и станций позволяет оценивать характеристики производительности проектируемых распределенных систем с целью выявления и дальнейшего устранения "узких мест". Получены свидетельства об официальной регистрации КСАМ в «Роспатенте».

5. Разработаны методические рекомендации по использовании КСАМ для исследования различных моделей доступа к базам данных: сервера базы данных, сервера приложений, в среде Intranet/Internet по технологиям GGI, API, Java-апплетов и ActiveX.

6. Разработанные в диссертации методы и комплекс КСАМ были применены при решении ряда практических задач.

Список основных публикаций по теме диссертации

Монографии

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

2. Плутенко А.Д., Верхотуров А.Д., Лебухова Н.В. Информационные технологии в решении задач материаловедения. Владивосток: Изд-во «Дальнаука», 2001.-142 с.

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

Другие публикации

4. Плутенко А.Д. Оценка времени выполнения подзапроса к реляционной базе данных // Вычислительные технологии. 2000 . Т.5, № 4. С. 97-103.

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

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

7. Плутенко АД., Остапенко АА Анализ методов управления доступом к локальным вычислительным сетям. Препринт. Благовещенск: изд-во Амурского гос. ун-та, 2001.-52 с.

8. Григорьев ЮА, Плутенко АД. Об одном алгоритме синтеза схемы реляционной базы данных // Вестник Амурского гос. ун-та. 1999. № 4. СЮ - 13.

9. Плутенко АД, Власенко B.C. Оценка времени выполнения соединения отношений методом сортировки-слияния // Вестник Амурского гос. ун-та. 1999. №4. СЛО-13.

10. Григорьев Ю. А., Плутенко А.Д., Бурдаков А. В. Анализ характеристик производительности распределенных систем обработки данных. // Сб. Статей Проблемы построения и эксплуатации систем обработки информации и управления / МГТУ им. Н.Э.Баумана, 2000. С И -17.

11. Григорьев ЮА, Плутенко АД. Оценка времени чтения индексных блоков // Управление в системах: ВестникИрГТУ. Сер. Кибернетика. - Вып. 3.- -2000. С. 54-59.

12. Плутенко АД., Григорьев ЮА, Остапенко АА Программный комплекс анализа моделей доступа к базам данных. // Вестник Амурского гос. ун-та. 2001. №13.С25-26.

13. Плутенко А. Д. Исследование производительности выполнения запросов в секционированных базах данных // Измерения, автоматизация и моделирование в промышленных и научных исследованиях. Сб. докладов / Бийск: БТИ., 2000. С. 33-36.

14. Остапенко АА., Плутенко А.Д. Математические методы анализа локальных вычислительных сетей Ethernet и Token Ring // Докл. конф. молодых ученых, посвященной 10-летию ИВТ СО РАН. Новосибирск, 2000. http:/www.ict.nsc.ru/ws/list_doc.dhtml

15. Григорьев ЮА, Власенко B.C., Плутенко А.Д. Оценка времени выполнения соединения отношений методом вложенных циклов // Докл.междун.научно-техн.конф. «Информационные системы и технологии» // Новосибирск: НГТУ (ЮТИ)., 2000. Т.З. С. 452-455.

16. Плутенко АД. Концепция информационных технологий в электроэнергетике // Энергетика: управление, качество и эффективность использования энергоресурсов. Сб.тр. II Всероссийской научно-технической конференции с иностранным участием. Благовещенск, 2000. - С. 21-24.

17. Григорьев ЮА, Плутенко АД. Оценка времени чтения индексных блоков. // Управление в системах: Вестник ИрГТУ. Сер. Кибернетика. Иркутск: Изд-во ИрГТУ, 2000. - Вып. 3. - С. 54-59.

18. Плутенко АД. Информационное моделирование в системах обработки данных с использованием CASE-системы S-DESIGNER 5.1. // Применеие баз данных. Материалы науч.-практ. семинара / Пенза: ГОТУ, 1997. С. 8-9.

19. Ploutenko A. D. The Conception of a System of Analysis of Models of Access to Distributed Databases // Electrical Power Quality and Utilisation. 6 Intern. Conf Cracow, 2001. Pp. 187-191.

20. Григорьев ЮА, Плутенко АД. Концепции комплекса инструментальных средств анализа моделей доступа к базам данных распределенных систем обработки данных // Информатика и системы управления. № 1,2001. С. 13-23.

21. Бурдаков А.В., Григорьев ЮА, Плутенко АД. Оценка времени выполнения запросов к объектно-ориентированным базам данных. // Информатика и системы управления. 2001. № 2.. - С. 12-23.

22. Плутенко АД. Архитектура современных распределенных СУБД // Григорьев ЮА, Ревунков Г.И. Банки данных. - М.: Изд-во МГТУ им.Н.Э.Баумана, 2002.-С. 164-168.

23. Бурдаков А.В., Григорьев ЮА, Плутенко АД. Анализ времени выполнения запросов к объектно-ориентированным базам данных по алгоритмам прямого и обратного соединения // Конверсия в машиностроении. М.: Информкон-версия,2002. № 1.- С.40-45.

24. Григорьев ЮА, Плутенко А Д. Метод оценки выполнения запросов SQL к реляционным базам данных // Радиоэлектроника. Информатика. Управление. Запорожье, 2002. № 2. С. 62-69.

25. Burdakov A.V., Grigorev YA, Ploutenko AD. On the Estimation of Query Execution Time in Object-Oriented Databases at the Early Design Stages // Advances in Databases and Information Systems: Materials of 6ts East-European Conference, AD-BIS 2002, Vol. 2: Reseach Communications, Bratislava, Slovakia, September 8-11, 2002.-P. 52-64.

26. Соколов Д.Г., Шестаков Б.И., Мельников В.Д., Онишук B.C., Плутенко АД. Эколого-ресурсный банк данных Амурской области // Материалы межд. симпозиума «Человеческое измерение региональных проблем». / Биробиджан, 1992. С. 89-93.

27. Шестаков Б.И., Онишук B.C., Плутенко АД. Опыт разработки ресурсно-экологического банка данных Амурской области // Проблемы экологии Верхнего Приамурья. Сб. науч. трудов /Благовещенск: БГПИ. Вып. II, 1995. С.85-88.

28. Плутенко А.Д., Григорьев ЮА, Бурдаков А.В. Преобразование Лапласа-Стилтьеса времени чтения страниц при выполнении запросов к базам данных. Управление в системах: Вестник ИрГТУ. Сер. Кибернетика. - Иркутск: Изд-во ИрГТУ, 2003. - Вып. 5. - С. 170-177.

29. Гребенников НА Григорьев ЮА, Плутенко А.Д. Анализ размеров пространства поиска оптимальных планов выполнения запросов в СУБД. //Информатика и системы управления. 2004. № 1(7). - С. 3-15.

30. Плутенко АД., Ситников АА Моделирование процесса репликации данных в СУБД методом журнальной синхронизации. // Информатика и системы управления. 2004. № 1(7).- С. 16-26.

31. Плутенко А.Д. Результаты апробации комплекса инструментальных средств анализа моделей доступа к распределенным базам данных. // Вестник Амурск, гос. ун-та. 2004. № 25. - С. 34-38.

32. Плутенко А.Д., Саакян Р.Р. Теория нечетких множеств как ориентирующая основа рассмотрения и разработки общих информационных аспектов в реше-

нии трудноформализуемых задач. // Доклады межд. научн. Конф. "Интеллектуализация обработки информации ИОИ-2004". - Алушта, 2004. - С. 162-165.

33. Григорьев ЮД Плутенко АД, Остапенко АА, Бурдаков А.В. Комплекс инструментальных средств анализа моделей доступа к базам данных распределенных систем обработки данных // Свидетельство об официальной регистрации программы для ЭВМ № 2001611054.20.08.2001.

34. Плутенко АД., Ситников АА Программа тестирования скорости реализации системы журнальной репликации и зависимости ее от объема изменяемых данных, оценка степени замедления выполнения операций по изменению БД при ведении журнала операций. // Свидетельство об официальной регистрации программы для ЭВМ № 2004611740.26.07.2004.

35. Плутенко АД., Ситников АА Библиотека функций расширения СУБД Interbase (UDF - user defined function), предназначенных для поддержки формирования исходной строки SQL в теле триггера при изменении данных таблицы. // Свидетельство об официальной регистрации программы для ЭВМ № 2004611741. 26.07.2004.

36. Плутенко АД., Ситников АА Программа генерации последовательности команд SQL, используемых для инициализации базы данных при моделировании системы репликации по журналу. // Свидетельство об официальной регистрации программы для ЭВМ № 2004611742.26.07.2004.

37. Плутенко А.Д., Ситников А.А. Программа моделирования простой мар-шрутизапии репликационной информации при реализации репликации по журналу для случая нескольких узлов обменивающихся данными. // Свидетельство об официальной регистрации программы для ЭВМ № 2004611743.26.07.2004.

38. Плутенко АД., Ситников АА Моделирование биллинговой системы с использованием комплекса инструментальных средств анализа моделей доступа к распределенным базам данных. // Материалы II межд. науч.-практ. конф. "Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем". - Новочеркасск, 2004. - С.221-227.

Подписано к печати 24.09.2004 г. Типография АмГУ. Формат 60x84/16. Уел печ.л. 2,09, уч.-изд л. 2,1. Тираж 100. Заказ 260 675027, г.Благовещенск, Амурской обл., Игнатьевское шоссе, 21. Лицензия ЛР № 020677 от 11 03.1998 г.

№190 04

РНБ Русский фонд

2005-4 17334

Оглавление автор диссертации — доктора технических наук Плутенко, Андрей Долиевич

Введение.

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

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

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

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

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

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

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

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

Java-апплетов и ActiveX.

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

1.1.8. Анализ моделей доступа к базам данных.

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

1.3. Разработка концепций комплекса инструментальных средств (|| анализа моделей доступа к базам данных распределенных автоматизированных систем.

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

2.1. Организация обработки запросов SQL.

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

2.3. Оценка времени выполнения запросов SQL.

2.3.1. Оценка времени обработки подзапросов.

2.3.2. Вывод рекуррентной формулы производящей функции числа кортежей соединяемых таблиц.

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

2.3.3.1. Метод соединения с помощью вложенных циклов NLJ

2.3.3.2. Метод соединения посредством сортировки-слияния

2.3.3.3. Метод хешированного соединения HJ.

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

3.1. Анализ методов доступа к локальным вычислительным сетям

3.1.1. Формализация процесса функционирования локальных вычислительных сетей передачи данных.

3.1.2. Определение параметров модели.

3.1.3. Определение начальных моментов времени передачи кадра по шине ЛВС.

3.1.4. Закон сохранения для одноканальных СМО.

3.1.5. Анализ времени выполнения транзакции в ЛВС с помощью замкнутой сети массового обслуживания.

3.1.6. Анализ времени выполнения транзакции в ЛВС с помощью разомкнутой СМО.

3.1.7. Оценка средней скорости передачи данных транзакции по шине Ethernet.

3.1.8. Оценка средней скорости передачи данных транзакции по кольцу Token Ring.

3.2. Анализ методов доступа к глобальным сетям.

3.2.1. Анализ функционирования сети Х.25.

3.2.2. Оценка времени передачи пакета в сети Х.25.

3.2.3. Анализ функционирования сети Frame Relay.

3.2.4. Оценка времени передачи пакета в сети Frame Relay

3.3. Анализ методов доступа к магистральным сетям.

3.3.1. Анализ функционирования сети FDDI.

3.3.2. Анализ функционирования сети ATM.

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

4.1. Разработка концепций КС AM.

4.2. Структура КСАМ.

4.3. Схема базы данных КСАМ.

4.4. Организация базы знаний КСАМ.

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

4.6. Пользовательский интерфейс КСАМ.

4.6.1. Описание концептуальной схемы базы данных.

4.6.2. Описание запросов и транзакций.

4.6.3. Описание архитектуры проектируемой РСОД.

4.6.4. Распределение таблиц базы данных и транзакций по узлам РСОД.

4.6.5. Описание обращений к транзакциям из узлов.

4.6.6. Описание обращений к транзакциям из транзакций.

4.6.7. Справочник конфигураций узлов.

4.6.8. Справочник конфигураций сетей.

4.6.9. Загрузка узлов.

4.6.10. Загрузка сетей.

4.6.11. Время выполнения транзакций.

4.7. Схема представления моделей доступа к базам данных в КСАМ.

4.7.1. Описание модели сервера базы данных.

4.7.2. Описание модели сервера приложений.

4.7.3. Описание доступа к базе данных из CGI- или API-программы.

4.7.4. Описание доступа к базе данных из Java-апплетов или компонентов ActiveX.

4.8. Анализ адекватности моделирования РСОД с помощью КСАМ

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

5.1. Исследование глобальной системы абонентского обслуживания сети Билайн GSM.

5.1.1. Требования к проектируемой системе.

5.1.2. Описание предметной области.

5.1.3. Описание структуры автоматизированной системы.

5.1.4. Описание моделируемых вариантов комплекса программно-технических средств.

5.1.5. Схема базы данных системы абонентского обслуживания

5.1.6. Описание транзакций системы.

5.1.7. Методика моделирования системы абонентского обслуживания.

5.1.8. Результаты моделирования работы системы.

5.1.9. Анализ результатов моделирования.

5.2. Исследование автоматизированной системы фирмы "ВЕСКО+М".

5.2.1. Архитектура автоматизированной системы фирмы "ВЕСКО+М".

5.2.2. Схема базы данных автоматизированной системы и состав анализируемых транзакций.

5.2.3. Сбор и анализ статистик автоматизированной системы.

Основные результаты работы.

Введение 2004 год, диссертация по информатике, вычислительной технике и управлению, Плутенко, Андрей Долиевич

Актуальность проблемы. Разнообразие аппаратно-программных комплексов (АПК), используемых при разработке автоматизированных систем, привело к появлению различных моделей доступа к базам данных в рамках архитектуры "клиент-сервер". Перед проектировщиком распределенной системы возникает непростая задача выбора приемлемого варианта, зависящего от множества факторов: архитектуры будущей системы, спецификаций разрабатываемых запросов и транзакций, схемы базы данных и ее наполнения. В то же время разработчику трудно интуитивно оценить влияние этих параметров на характеристики проектируемой системы. Поэтому разработка теоретических методов, позволяющих прогнозировать показатели качества системы в зависимости от механизма доступа к базе данных и перечисленных выше факторов, а также доведение этих методов до возможности практического использования является актуальной задачей.

К сожалению, применение традиционных теоретических методов не всегда приводит к решению подобных задач. Например, попытки использования теории массового обслуживания для исследования серверов баз данных не приводят к желаемым результатам. Это связано с проблемой выделения ресурсов (обслуживающих аппаратов) и оценки их параметров (входных потоков, времени обслуживания, дисциплин обслуживания очередей).

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

Поэтому разработка теоретических основ анализа современных механизмов доступа к распределенным базам данных и связанных с ними процессов, позволяющих преодолеть многие недостатки традиционных методов, является важной проблемой. Здесь нельзя ограничиться разработкой некоторых частных методов, необходимо предложить новый класс математических моделей, позволяющих оценивать различные объемно-временные характеристики выполнения сложных запросов, которые могут включать и элементарные условия, и соединения нескольких отношений. Эти модели должны учитывать параметры схемы базы данных, а также случайный характер параметров запросов и наполнения базы данных. Важно, чтобы модели позволяли рассчитывать не только характеристики времени выполнения запросов, но и исходные данные для систем массового обслуживания, которые часто используются на практике при анализе сетей передачи данных.

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

Научная новизна результатов исследования состоит в следующем.

5. Получено функциональное уравнение относительно преобразования Лапласа-Стилтьеса функции распределения времени передачи кадра по шине локальной вычислительной сети, учитывающее вероятностные характеристики выполняемых в сети SQL-запросов. Найдено преобразование Лапласа-Стилтьеса функции распределения времени выполнения транзакции в сети, учитывающее особенности процесса передачи данных между рабочей станцией и сервером базы данных и параметры объемов данных, передаваемых по сети при выполнении запросов транзакций.

6. Доказана теорема о средней незаконченной работе в СМО Mg/G/1 с неординарным потоком и произвольной, не допускающей прерывания обработки дисциплиной обслуживания, которая позволила использовать законы сохранения СМО при получении выражения для средней скорости передачи данных по шине ЛВС при обработке какой-либо транзакции, запускаемой с рабочей станции.

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

В диссертации представлены методические рекомендации по использованию разработанного комплекса для моделирования различных процессов доступа к базам данных: модели сервера базы данных, модели сервера приложений, а также доступа по технологиям Intranet/Internet: из CGI- или API-программ и из 1ауа-апплетов и компонентов ActiveX. КСАМ позволяет учесть наличие разных способов доступа к базам данных в одной сети и характерные особенности перечисленных выше моделей и технологий. В работе выполнен анализ адекватности моделирования распределенных систем обработки данных с помощью КСАМ.

Проводимые исследования включались в основные направления научно-исследовательских работ Амурского государственного университета в 1985-2003 годах.

Разработанный математический аппарат, комплекс КСАМ и методические рекомендации были применены при решении ряда практических задач, в частности, при разработке глобальной системы абонентского обслуживания в рамках сети Билайн GSM, поддерживаемой АО "Вымпелком", и модернизации распределенной системы учета и анализа товарооборота, которая эксплуатируется в ряде нескольких филиалов крупных торговых компаний Москвы (фирм "ВЕСКО+М").

Отдельные результаты исследований используются в учебном процессе Амурского государственного университета в дисциплинах "Организация баз данных" в курсовом и дипломном проектировании специальности 220200 "Автоматизированные системы обработки информации и управления". Апробация работы. Основные результаты диссертации были представлены и обсуждены на следующих конференциях, совещаниях и симпозиумах: научно-практическом семинаре "Применение баз данных" (Пенза, 1997), симпозиуме "Научное и научно-техническое обеспечение экономического и социального развития Дальневосточного региона" (Комсомольск-на-Амуре, 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) концептуального проекта распределенной системы обработки данных (РСОД) (концептуальной (инфо логической) схемы базы данных PC ОД и наполнения базы данных (прогнозируемого числа записей в таблицах и мощностей атрибутов; запросов (SQL-операторов) и транзакций РСОД, которые могут обращаться к другим транзакциям распределенной системы);

Разработаны методические рекомендации по использованию комплекса КСАМ для моделирования различных процессов доступа к базам данных: модели сервера базы данных, модели сервера приложений, а также доступа по технологиям Intranet/Internet: из CGI- или API-программ и из Javaапплетов и компонентов ActiveX. Например, при моделировании доступа к распределенным данным из CGI- или АРГ-программ учитывается чтение I

HTML-формы с Web-cepeepa, передача имени и параметров CGI- или API-программы на сервер, выполнение SQL-операторов, закодированных в программе, передача обратно на рабочую станцию нового HTML-документа с результатами поиска. Аналогично учитываются особенности других способов доступа к базам данных. Комплекс КСАМ позволяет учесть наличие разных способов доступа к базам данных в одной сети и характерные особенности перечисленных выше моделей и технологий.

В работе выполнен анализ адекватности моделирования распределенных систем обработки данных с помощью КСАМ.

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

Публикации. По материалам диссертации опубликованы 38 печатных работ, в том числе 3 монографии

Объем работы. Диссертационная работа содержит 350 страниц основного текста, в том числе 80 рисунков и 22 таблицы. Список литературы включает 166 наименований.

Заключение диссертация на тему "Разработка теоретических основ анализа процессов доступа к базам данных распределенных автоматизированных систем"

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

3. Получено ПЛС функции распределения времени выполнения транзакции в локальной вычислительной сети, учитывающее параметры передачи данных между рабочей станцией и сервером при выполнении запросов к базе данных. Разработан новый метод оценки среднего времени ожидания в очереди и передачи кадра по шине ЛВС, основанный на использовании законов сохранения СМО. Получены оценки показателей производительности для сетей Ethernet, Token Ring, Х.25, Frame Relay, FDDI, ATM, учитывающие особенности соответствующих методов доступа.4. На основе полученных теоретических результатов, разработан комплекс инструментальных средств анализа моделей доступа к базам данных распределенных систем обработки данных (КСАМ), который по описанию запросов и транзакций приложений, таблиц базы данных, топологии сети, виртуальных каналов, параметров сетей, каналов связи и станций позволяет оценивать характеристики производительности проектируемых распределенных систем с целью выявления и дальнейшего устранения "узких мест". Получены свидетельства об официальной регистрации КС AM в Роспатенте.5. Разработаны методические рекомендации по использовании КС AM для исследования различных моделей доступа к базам данных: сервера базы данных, сервера приложений, в среде Intranet/Internet по технологиям GGI, API, Java-апплетов и ActiveX.6. Разработанные в диссертации методы и комплекс КСАМ были применены при решении ряда практических задач.

Библиография Плутенко, Андрей Долиевич, диссертация по теме Математическое моделирование, численные методы и комплексы программ

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

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

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

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

5. Борисов А.Н., Алексеев А.В., Меркурьева Г.В. и др. Обработка нечёткой информации в системах принятия решений .- М.: Радио и связь, 1989.

6. Бурдаков А.В., Григорьев Ю.А., Плутенко А.Д. Анализ времени выполнения запросов к объектно-ориентированным базам данных по алгоритмам прямого и обратного соединения // Конверсия в машиностроении. М.: Информконверсия, 2002. № 1 . - 40-45.

7. Бурдаков А.В., Григорьев Ю.А., Плутенко А.Д. Оценка времени выполнения запросов к объектно-ориентированным базам данных. // Информатика и системы управления. № 2, 2001. 12-23.

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

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

10. Григорьев Ю.А. Разработка научных основ проектирования архитектуры распределенных систем обработки данных: Дисс... д-ра техн. наук. — М.: МГТУ им. Н.Э. Баумана, 1996.

11. Григорьев Ю.А., Остапенко А.А., Плутенко А.Д. Модели анализа процессов передачи данных в компьютерных сетях // Препринт. МГТУ им. Н.Э.Баумана, 2000.

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

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

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

15. Григорьев Ю.А., Плутенко А.Д. Оценка времени чтения индексных блоков // Управление в системах: ВестникИрГТУ. Сер. Кибернетика. — Вып. 3.- 2000. 54-59.

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

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

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

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

20. Дэвис Р. Программирование на Microsoft Visual Java++. — М.: Изд. отдел "Рус. редакция" ТОО "Channel Trading Ltd", 1997.

21. Емельянов СВ., Ларичев О.И. Многокритериальные методы принятия решений. - М.: Знание, 1985. (Новое в жизни, науке, технике. Сер. Математика, кибернетика; № 10). « >t. 22. Иванов Ю.Н., Кочин Ю.Я. Представление и реализация запросов в системах баз данных // Автоматика и телемеханика (М.). - 1996. - № 5. — 178-185.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

42. Парсонс Т., Бар Д. Frame Relay // LAN MAGAZINE/Pyc. изд-е (М.). - 1996.-Т. 2 ,№5. -С . 32-37.

43. Плутенко А.Д. Архитектура современных распределенных СУБД // Григорьев Ю.А., Ревунков Г.И. Банки данных. - М.: Изд-во МГТУ им.НЭ.Баумана, 2002. - 164-168.

44. Плутенко А. Д. Исследование производительности выполнения запросов в секционированных базах данных // Измерения, автоматизация и мо-т, делирование в промышленных и научных исследованиях. Сб. докладов / БТИ. Бийск, 2000. 33-36.

45. Плутенко А.Д. Оценка времени выполнения подзапроса к реляционной базе данных // Вычислительные технологии, 2000 . - Т.5, № 4, с. 97-103.

46. Плутенко А.Д. Результаты апробации комплекса инструментальных средств анализа моделей доступа к распределенным базам данных. // Вестник Амурск, гос. ун-та. 2004. № 25. 34-38.

47. Плутенко А.Д., Верхотуров А.Д., Лебухова Н.В. Информационные технологии в решении задач материаловедения. Владивосток: Изд-во «Даль-наука», 2001.

48. Плутенко А.Д., Власенко B.C. Оценка времени выполнения соединения отношений методом сортировки-слияния // Вестник Амурского гос. унта. 1999. №4. С Ю - 1 3 .

49. Плутенко А.Д., Григорьев Ю.А., Остапенко А.А. Программный комплекс анализа моделей доступа к базам данных. // Вестник Амурского гос. ун-та. 2001. №13.0.25-26.

50. Плутенко А.Д., Остапенко А.А. Анализ методов управления доступом к локальным вычислительным сетям. // Препринт, Благовещенск: изд-во Амурского гос. ун-та, 2001.

51. Плутенко А.Д., Ситников А.А. Моделирование процесса репликации данных в СУБД методом журнальной синхронизации. // Информатика и системы управления. № 1(7), 2004. 16-26.

52. Пьязин К. Выбираем файловый сервер // LAN. Журн. сетевых решений (М.). - 1998. - Т. 4, № 9. - 105-112.

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

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

55. Сигнор Р., Стегман М.О. Использование ODBC для доступа к базам данных. - М.: БИНОМ, Науч. книга,

56. Сингх Л. и др. Oracle 7.3. Пособие разработчика. - Киев: Изд-во "ДиаСофт", 1997.

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

58. Сущенко СП. Оптимизация операционных характеристик сети передачи данных с коммутацией пакетов: Автореферат д и с с . д-ра техн. наук. -Томский гос. ун-т, 1998.

59. Тельнов Ю.Ф. Интеллектуальные информационные системы в экономике. - М.: СИНТЕГ, 1998,

60. Трахтенгерц Э.А. Компьютерная поддержка принятия решений. — М.: СИНТЕГ, 1998.

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

62. Уэно X., Исидзука М. Представление и использование данных — М.: Мир, 1989.

63. Фитцжеральд Проектирование сети Frame Relay // Сети (М.). - 1995.-№10.-С. 79-81.

64. Франк А. Язык разметки гипертекста //LAN MAGAZINE/Pyc. издание (М.). - 1996. - Т. 2, № 6. - 23-30.

65. Франк А. HTML и CGI //LAN MAGAZINE/Pyc. издание (М.). - 1996.-Т. 2, №7. -0 .43-51 .

66. Хелд Г. По скоростной магистрали с ветерком. // LAN. Журн. сетевых решений (М.). - 1999. - Т. 5, № 2. - 64-69.

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

68. Чаппел Л., Хейкс Д. Анализатор локальных сетей NetWare. - М.: Изд-во "ЛОРИ", 1995.

69. Чеппел Д. Технологии ActiveX и OLE. - М.: Изд. отдел "Русская редакция" ТОО "Channel Trading Ltd", 1997.

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

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

72. Юдицкий Одна неисправная плата монополизирует сеть 10Base2 // LAN. Журн. сетевых решений (М.). - 2000. - Т. 6, № 4. - 24-25.

73. Юдицкий С, Борисенко В., Адаскин П. Лучше один раз измерить, чем сто раз гадать. // LAN. Журн. сетевых решений (М.). - 1999. - Т. 5, № 7-8.-С. 63-75.

74. Abbott R. К., Garcia-Molina H, Scheduling real-time transactions: a performance evaluation // ACM Transactions on Database Systems. - Sep. 1992. -Vol. 17, № 3 . - P . 513-560.

75. Abdel-Ghaffar K.A.S., Amr El Abbadi. Optimal disk allocation for partial match queries // ACM Transactions on Database Systems. - Mar. 1993. -Vol. 18, № 1 . - P . 132-156.

76. Ackerman M.S. Augmenting organizational memory: a field study of answer garden // ACM Transactions on Information Systems. - Jul. 1998. - Vol. 16, № 3 . - P . 203-224.

77. Anon, et al. A Measure of Transaction Processing Performance // Datamation. - April 1985 . -№31 (7 ) . - P. 112-118.

78. Antoshenkov G., Ziauddin M. Query processing and optimization in Oracle Rdb // The VLDB Journal. - 1996. - Vol. 5,1. 4. - P. 229-23 7.

79. Becker В., Gschwind S., Ohler Т., Seeger В., Widmayer P. An asymptotically optimal multiversion B-tree // The VLDB Journal. - 1996. - Vol. 5,1. 4. - P . 264-275.

80. Beeri C , Milo T. Schemas for Integration and Translation of Structured and Semi-structured Data // Hebrew University, Tel Aviv University, 1999 (www. link.springer.de, Computer Science, LNCS 1540).

81. Benmohamed L., Meerkov S.M. Feedback control of congestion in packet switching networks: the case of a single congested node // IEEE/ACM Transactions on Networking. - Dec. 1993. - Vol. 1, № 6. - P. 693-708.

82. Bertino E., Bettini C , Ferrari E., Samarati P. An access control model supporting periodicity constraints and temporal reasoning // ACM Transactions on Database Systems. - Sep. 1998. - Vol. 23, № 3. - P. 231-285.

83. Bohm C, Kriegel H.-P. Dynamically Optimizing High-Dimensional Index Structures // University of Munich, 2000 (www.link.springer.de. Computer Science, LNCS 1777). т

84. Cahoon В., McKinley K.S., Lu Z. Evaluating the performance of distributed architectures for information retrieval using a variety of workloads // ACM Transactions on Information Systems. - Jan. 2000. - Vol. 18, № 1, - P. 1-43.

85. Castano S., De Antonellis V., Fugini M.G., Pemici B. Conceptual schema analysis: techniques and applications // ACM Transactions on Database Systems. - Sep. 1998. - Vol. 23, № 3. - P. 286-333.

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

87. Chakravarthy U.S., Grant J., Minker J. Logic-based approach to semantic query optimization // ACM Transactions on Database Systems. - Jun. 1990. -Vol. 15, № 2 . - P . 162-207.

88. Chaudhuri S., Shim K. Optimization of queries with user-defined predicates // ACM Transactions on Database Systems. - Jun. 1999. - Vol. 24, № 2. -P. 177-228.

89. Chen M.-S., Hsiao H.-I, Yu P.S. On applying hash filters to improving the execution of multi-join queries // The VLDB Journal. - 1997. - Vol. 6,1. 2. -P. 121-131.

90. Clarke C.L.A., Cormack G.V. Shortest-substring retrieval and ranking // ACM Transactions on Information Systems. - Jan. 2000. - Vol. 18, № 1, - P. 44-78.

91. Codd E.F. A Relational Model of Data for Large Shared Data Banks // # Communications of the ACM. - June 1970. - № 13 (6). - P. 377-387.

92. Crestani F., Van Rijsbergen C. J. A study of probability kinematics in information retrieval // ACM Transactions on Information Systems. - Jul, 1998, — Vol. 16, № 3 . - P . 225-255.

93. Dey D., Storey V.C., Barron T.M. Improving database design through the analysis of relationships // ACM Transactions on Database Systems, - Dec. 1999. - Vol. 24, № 4. - P. 453-486.

94. Drenick P. E., Smith E. J. Stochastic query optimization in distributed databases // ACM Transactions on Database Systems. - Jun. 1993. - Vol. 18, № 2. - P . 262-288.

95. Elwalid A. I., Mitra D. Effective bandwidth of general Markovian traffic sources and admission control of high speed networks // IEEE/ACM Transactions on Networking. - Jun, 1993, - Vol. 1, № 3. - P. 329-343.

96. Erramilli A., Narayan O., Willinger W. Experimental queueing analysis with long-range dependent packet traffic // IEEE/ACM Transactions on Networking. - Apr. 1996. - Vol. 4, Ко 2. - P. 209-223.

97. Fahl G., Risch T. Query processing over object views of relational data // The VLDB Journal. - 1997. - Vol. 6,1. 4. - P. 261-281. *

98. Formica A., Groger H.D., Missikoff M. An efficient method for checking object-oriented database schema correctness // ACM Transactions on Database Systems. - Sep. 1998. - Vol. 23, № 3. - P. 334-369.

99. Franaszek P. A., Robinson J. Т., Thomasian A. Concurrency control for .MJtj high contention environments // ACM Transactions on Database Systems. - Jun. 1992.-Vol. 17, № 2 . - P . 304-345.

100. Gardy D,, Nemirovski L, Urn Models and Yao's Formula // Labora- toire PRiSM, Universite de Versailles Saint-Quentin, 1999 (www.link.springer.de, Computer Science, LNCS 1540).

101. Graefe G., Cole R.L. Fast algorithms for universal quantification in large databases // ACM Transactions on Database Systems. - Jun. 1995. - Vol. 20, № 2 . - P . 187-236.

102. Greenberg A.G., Srikant R. Computational techniques for accurate performance evaluation of multirate, multihop communication networks // ^ IEEE/ACM Transactions on Networking. - Apr. 1997. - Vol. 5, № 2. -P. 266-277.

103. Gruser J.-R., Raschid L., Zadorozhny V., Zhan T. Learning response time for WebSources using query feedback and application in query optimization // The VLDB Journal. - 2000. - Vol. 9, L 1. - P. 18-37.

104. Haas L. M., Carey M. J., Livny M., Shukla A. Seeking the truth about ad hoc join costs // The VLDB Journal. - 1997. - Vol. 6, L 3. - P. 241-256. м

105. Han J.L. Optimizing relational queries in connection hypergraphs: nested queries, views, and binding propagations // The VLDB Journal. — 1998. -Vol. 7,1. l . - P . 1-11.

106. Harder Т., Reinert J. Access path support for referential integrity in SQL2 // The VLDB Journal. - 1996. - Vol. 5, L 3. - P. 196-214.

107. Harder Т., Sauter G., Thomas J. The intrinsic problems of structural heterogeneity and an approach to their solution // The VLDB Journal. — 1999. — Vol. 8,L l . - P . 25-43.

108. Hawking D., Thistlewaite P. Methods for information server selection // ACM Transactions on Information Systems. - Jan. 1999. - Vol. 17, № 1. -P. 40-76.

109. Jiang H., Elmagarmid A.K. Spatial and temporal content-based access to hypervideo databases // The VLDB Journal. - 1998. - Vol. 7,1. 4. - P. 226-238.

110. Johnson Т., Sasha D. The performance of current B-tree algorithms // ACM Transactions on Database Systems. - Mar. 1993. - Vol. 18, № 1. -P. 51-101.

111. Kabra N., DeWitt D. J. OPT-H-: an object-oriented implementation for extensible database query optimization // The VLDB Journal. - 1999. - Vol. 8, I. l . - P . 55-78.

112. Kaszkiel M., Zobel J., Sacks-Davis R. Efficient passage ranking for document databases // ACM Transactions on Information Systems. - Oct. 1999. -Vol. 17, № 4 . - P . 406-439.

113. Kessler I., Krishna A. On the cost of fairness in ring networks // IEEE/ACM Transactions on Networking. - Jun. 1993. - Vol. 1, № 3. -P. 306-313.

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

115. Krivokapic N., Kemper A., Gudes E, Deadlock detection in distributed database systems: a new algorithm and a comparative performance analysis // The VLDB Journal. - 1999. - Vol. 8,1. 2. - P. 79-100.

116. Leland W.E., Taqqu M.S., Willinger W., Wilson D.V. On the self- similar nature of Ethernet traffic (extended version) // IEEE/ACM Transactions on Networking. - Feb. 1994. - Vol. 2, № 1. - P. 1-15.

117. Li Z., Ross K.A. Fast joins using join indices // The VLDB Journal. - 1999.-Vol. 8, L l . - P . 1-24.

118. Liu M., Ling T.W. A Data Model for Semistructured Data with Partial and Inconsistent Information // Department of Computer Science, University of Regina, Canada (www.link.springer.de, Computer Science, LNCS 1777).

119. Lomet D., Salzberg B. Concurrency and recovery for index trees // The ^ VLDB Journal. - 1997. - Vol. 6,1. 3. - P. 224-240.

120. Matsliach G. Performance analysis of file organizations that use mul- tibucket data leaves with partial expansions // ACM Transactions on Database Sys-tems.-Mar. 1993.-Vol. 18,№ l . - P . 157-180.

121. Mehrotra S., Korth H. F., Silberschatz A. Concurrency control in hierarchical multidatabase systems // The VLDB Journal. - 1997. - Vol. 6,1. 2. - P. 152-172.

122. Mitra D., Morrison J.A. Erlang capacity and uniform approximations for shared unbuffered resources // IEEE/ACM Transactions on Networking. — Dec. 1994. - Vol. 2, № 6. - P. 558-570.

123. Mylopoulos J., Chaudhri V., Plexousakis D., Shrufi A., Topologlou T. ^Щ Building knowledge base management systems // The VLDB Journal. - 1996. — Vol. 5,1. 4 . - P . 238-263.

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

125. Ng R.T., Shum P. Optimal clip ordering for multi-clip queries // The VLDB Journal. - 1998. - Vol. 7, L 4. - P. 239-252.

126. Nicola M., Jarke M. Increasing the Expressiveness of Analytical Performance Models for Replicated Databases // Technical University of Aachen, In-formatik V (Information Systems), 1999 (www.link.springer.de. Computer Science, LNCS 1540).

127. Ooi B.C., Han J., Lu H., Tan K.L. Index nesting - an efficient approach to indexing in object-oriented databases // The VLDB Journal. - 1996. — Vol. 5, 1. 3 . - P . 215-228.

128. Orda A., Rom R., Sidi M. Minimum delay routing in stochastic networks // IEEE/ACM Transactions on Networking. - Apr. 1993. - Vol. 1, № 2. -P. 187-98.

129. Pacitti E., Simon E. Update propagation strategies to improve fresh- iML ness in lazy master replicated databases // The VLDB Journal. - 2000. - Vol, 8,1. 3-4.-P. 305-318.

130. Panagos E., Biliris A. Synchronization and recovery in a client-server storage system // The VLDB Journal. - 1997. - Vol. 6,1. 3. - P. 209-223.

131. Pattavina A., Bruzzi G, Analysis of input and output queueing for non- blocking ATM switches // IEEE/ACM Transactions on Networking. - Jun. 1993. -Vol. 1,№3.-P. 314-328.

132. Paxson V. Empirically derived analytic models of wide-area TCP connections // IEEE/ACM Transactions on Networking. - Aug. 1994. - Vol. 2, № 4. -P. 316-336.

133. Philip Gile. Магические возможности технологии ORB // Компью- ^ теруик. - М., 1997. - № 3. - 28-29.

134. Rahm Е. Empirical performance evaluation of concurrency and coherency control protocols for database sharing systems // ACM Transactions on Database Systems. - Jun. 1993. - Vol. 18, N 2. - P. 333-377.

135. Ramamritham K., Chrysanthis P.K. A taxonomy of correctness criteria in database applications // The VLDB Journal. - 1996. - Vol. 5,1. 1. - P. 85-97.

136. Rubin L, Wu J.C.-H. Analysis of an M/G/l/N queue with vacations and its iterative application to FDDI timed-token rings // IEEE/ACM Transactions on Networking. - Dec. 1995. - Vol. 3, № 6. - P. 842-856.

137. San-qi Li, Chia-lin Hwang. On the convergence of traffic measurement and queueing analysis: a statistical-matching and queueing (SMAQ) tool // IEEE/ACM Transactions on Networking. - Feb. 1997. - Vol. 5, № 1. - P. 95-110.

138. Scheuermann P., Weikum G., Zabback P. Data partitioning and load balancing in parallel disk systems // The VLDB Journal. - 1998. - Vol. 7,1. 1. -P. 48-66.

139. Singhal v., Smith A.J. Analysis of locking behavior in three real database systems // The VLDB Journal. - 1997. - Vol. 6,1. 1. - P. 40-52.

140. Soffer A., Samet H. Integrating symbolic images into a multimedia da- (Щ tabase system using classification and abstraction approaches // The VLDB Journal. - 1998. - Vol. 7,1. 4. - P. 253-274.

141. Steinbrunn M., Moerkotte G., Kemper A. Heuristic and randomized optimization for the join ordering problem // The VLDB Journal. - 1997. - Vol. 6, 1. 3 . - P . 191-208.

142. Teck W. Ng, Chen P.M. Integrating reliable memory in databases // The VLDB Journal. - 1998. - Vol. 7,1. 3. - P. 194-204. , *

143. Traina С Jr., Traina A., Seeger В., Faloutsos C. Slim-Trees: High Performance Metric Trees Minimizing Overlap between Nodes (www. link. springer.de, Computer Science, LNCS 1777),

144. Tsatalos O.G., Solomon M.H., loannidis Y.E. The GMAP: a versatile ^^ ' tool for physical data independence // The VLDB Journal. — 1996. - Vol. 5,1. 2. -P. 101-118.

145. Wald J.A., Sorenson P. G.. Explaining ambiguity in a formal query language // ACM Transactions on Database Systems. - Jun. 1990. - Vol. 15, № 2. -P. 125-161.

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

147. Whang Kyu-Young, Vander-Zanden Brad Т., Taylor H. M. A linear- time probabilistic counting algorithm for database applications // ACM Transactions on Database Systems. - Jun. 1990. - Vol. 15, № 2. - P. 208-229.

148. Willinger W., Taqqu M.S., Sherman R., Wilson D.V. Self-similarity through high-variability: statistical analysis of Ethernet LAN traffic at the source level // IEEE/ACM Transactions on Networking. - Feb. 1997. - Vol. 5, № 1. -P. 71-86.

149. Xu J., Croft W. B. Improving the effectiveness of information retrieval with local context analysis // ACM Transactions on Information Systems. — Jan. 2000. -Vol . 18, № 1. - P . 79-112.

150. Yemeni R., Li C , Ullman J., Garcia-Molina H. Optimizing Large Join Queries in Mediation Systems // Stanford University, USA, 1999 (www. link.springer.de. Computer Science, LNCS 1540).

151. Yu P. S., Leff A., Lee Yann-Hang. On robust transaction routing and load sharing // ACM Transactions on Database Systems. - Sep. 1991. - Vol. 16, № 3 . - P . 476-512.

152. Zobel J., Moffat A., Ramamohanarao K. Inverted files versus signature files for text indexing // ACM Transactions on Database Systems. - Dec. 1998. -Vol. 23, № 4 . - P . 453-490. i.v m

Похожие работы

Информатика, вычислительная техника и управление
05.13.00