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

/V . оп - к .....• О

I/ / ' V' ^ / ' ' "

ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Антонов Дмитрий Михайлович

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

Диссертация на соискание ученой степени кандидата технических наук

специальность 05.11.16 - Информационно-измерительные системы

Научный руководитель: доктор технических наук,

доцент Ильин А. А.

Тула 1999

ВВЕДЕНИЕ..................................................................................................4

1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ ОБРАБОТКИ ИНФОРМАЦИИ В РИИС.........................................................................11

1.1. Классификация и основные свойства РИИС..............................11

1.2. Параметры РИИС, влияющие на время выполнения удаленных запросов............................................................................17

1.3. Классификация запросов в РИИС...............................................23

1.4. Сравнительная характеристика способов оптимизации удаленных запросов в РИИС........................................................27

1.5. Постанова задачи исследования..................................................33

1.6. Выводы...........................................................................................35

2. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ВЫПОЛНЕНИЯ ЗАПРОСА В РИИС......................................................36

2.1. Требования к математической модели РИИС............................36

2.2. Определение параметров модели на основе измерений...........44

2.3. Стратегии выполнения соединений распределенных

файлов в РИИС..............................................................................48

2.4. Построение и реализация графа выполнения запроса..............54

2.5. Точность оценок селективности простых предикатов при произвольном распределении записей в файлах РИИС...........57

2.6. Выводы...........................................................................................66

3. СИНТАКСИЧЕСКАЯ ОПТИМИЗАЦИЯ УДАЛЕННЫХ ЗАПРОСОВ В РИИС.................................................................................67

3.1. Предварительная подготовка к повышению эффективности выполнения запросов.............................................................67

3.2. Логическая оптимизация выражений структурированного языка запросов..........................................................................69

3.3. Оптимизация запросов с изменением порядка реляционных операций.................................................................................74

3.4. Оптимизация запросов с вложенными подзапросами и запросами с соединениями...........................................................78

3.5. Алгоритм преобразования выражений запросов в выражения РА с синтаксической оптимизацией................................86

3.6. Выводы...........................................................................................96

4. ИССЛЕДОВАНИЕ ПРОГРАММНО-ТЕХНИЧЕСКОГО КОМПЛЕКСА ОБРАБОТКИ УДАЛЕННЫХ ЗАПРОСОВ......................97

4.1. Выбор СУБД позволяющей обрабатывать территориаль-но-распределенные базы данных................................................97

4.2. Экспериментальные исследования методов оптимизации запросов в РИИС.........................................................................102

4.3. Описание комплекса программ реализации удаленных запросов в ТРСБД........................................................................114

4.4. Реализация удаленного доступа в сети Relcom.......................117

4.5. Выводы.........................................................................................122

ЗАКЛЮЧЕНИЕ........................................................................................123

СПИСОК ЛИТЕРАТУРЫ.......................................................................125

ПРИЛОЖЕНИЕ........................................................................................134

П1. Фрагменты программ ведения базы метаданных.....................134

П2. Фрагменты программ реализации удаленных запросов в сети Relcom..............................................................................................143

ПЗ. Фрагменты программ реализации основных операций предварительной обработки запросов..................................................154

П4. Структура таблиц базы метаданных распределенной системы...........................................................................................................158

П5. Технико-экономическая эффективность внедрения результатов работы.....................................................................................161

ВВЕДЕНИЕ

Актуальность темы. Современный этап развития информационно-измерительных систем различного назначения характеризуется широким применением высокопроизводительных электронно-вычислительных машин, как средства обработки измерительной информации. Возрастание сложности задач в таких системах привело к тому, что, во-первых, системы обработки данных характеризуются большими объемами перерабатываемой информации, во вторых, такая обработка приобретает все более и более распределенный характер и, в-третьих, создаются базы данных измерительной информации [1, 2, 3, 4]. Главным фактором, стимулирующим развитие распределенных информационно-измерительных систем (РИИС) является то, что такие системы позволяют обеспечить доступ к большим объемам информации и большим вычислительным мощностям широкому кругу территориально разобщенных пользователей измерительной информации [2,

5].

В настоящее время появилось достаточно много территориально-рас-пределенных информационных систем регионального значения с мало изменяющимися во времени параметрами (множество узлов, их производительность, пропускная способность каналов связи между узлами, множество файлов баз данных с известной структурой, множество видов запросов к базам данных и т. п.). Такие системы характеризуются большим числом локальных узлов и значительным объемом данных, хранимых и обрабатываемых в узлах [3, 6, 7, 8]. Эффективное использование информации в подобных системах является нетривиальной задачей и возможно лишь при учете конкретных параметров системы, оцениваемых на основе современных информационно-измерительных технологий. Работами в области распределенной обработки и хранения данных занимались Кузнецов С.Д., Калини-ченко Л.А., Киселев В.Д., Селинжер П.Г., Шварц М., Мартин Д., Дейт К.Д.

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

Объединение измерительных комплексов при помощи средств связи позволило получить информационную систему, обладающую качественно новыми возможностями по использованию информационных массивов и оперативной информации, хранящейся и обрабатываемой в различных измерительных узлах системы, а также возможностью организации распределенной обработки данных для решения особо сложных задач управления на различных узлах сети. Создание и успешное использование указанных систем связано с необходимостью проработки и оценки ряда сложных технических решений по оптимальной организации функционирования запросов в сетях ЭВМ и их компонентов, поэтому вопросы построения методологических основ количественной оценки и оптимизации временных характеристик систем обработки и хранения данных на базе распределенных систем ЭВМ приобретают важное значение [9, 10, 11]. Низкая производительность РИИС при работе с измерительной информацией большого объема, связанна с трудностью эффективной реализации высокоуровневых операций манипулирования данными и независимых путей доступа к структурам хранения информации, что выдвигает в число наиболее актуальных проблем РИИС проблему оптимизации выполнения сложных поисковых запросов [2, 3, 12, 13, 14].

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

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

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

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

В соответствии с поставленной целью автором решены следующие задачи:

- исследованы и проанализированы временные характеристики выполнения соединения удаленных файлов в РИИС;

- на основании исследований методов предварительной подготовки запросов и статистики измерений разработан метод предварительной декомпозиции выражения запросов для их последующей обработки на локальных узлах РИИС;

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

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

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

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

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

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

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

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

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

- разработке программной реализация предложенных методов оптимизации, проведении экспериментальных измерений, подтверждающих эффективность выполнения распределенных запросов в РИИС;

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

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

- на основе результатов измерений сформулированы основные требования, предъявляемые к построению выражений запросов в РИИС;

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

Реализация результатов диссертационной работы. Прикладные результаты диссертационной работы внедрены в рамках работ по НИИОКР "Построение территориально-распределенной системы баз данных Тульского региона", выполненной фондом "Дисплей" по х/д № 96-7, в научно-производственном хозрасчетном центре "Экология и охрана труда" при построении территориально-распределенной системы мониторинга окружающей среды, а также в информационную технологию обработки распределенной статистической информации в ЗАО "Спецтехника" по договору № 504. Теоретические результаты работы внедрены в учебных курсах "Базы данных ЭВМ", "Деловые системы ПО" и "Системы искусственного интеллекта" на кафедре ЭВМ Тульского государственного университета.

Апробация работы. Основные положения диссертационной работы докладывались на следующих конференциях и семинарах: 1. XIV научная сессия, посвященная Дню Радио (г. Тула, 1997 г.), 2. Межвузовская научно-техническая конференция (г. Москва, МГИЭТ, 1997 г.), 3. Всероссийская научно-техническая конференция "Биотехнические, медицинские и экологические системы и комплексы" (г. Рязань, 1996 г.), 4. XI межвузовская научно-техническая конференция ТВАИУ (г. Тула, ТВАИУ, 1997 г.), 5. Меж-

вузовская научно-техническая конференция (г. Москва, МГИЭТ, 1998 г.), 6. Научно-техническая конференция "Современное телевидение" (г. Москва, 1998 г.). 7. XV научная сессия, посвященная Дню Радио (г. Тула, 1998 г.) 8. XI международная научная конференция "Математические методы в химии и технологиях", (г. Москва, 1998 г.), 9. Научно-практические конференции профессорско-преподавательского состава ТулГУ (г. Тула, 1997-99 г.г.).

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

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

Первый раздел является вводным. В нём проанализированы основные свойства и параметры распределенных информационно-измерительных систем, влияющие на скорость обработки информации; сформулированы основные требования предъявляемые к РИИС; исследованы особенности функционирования систем при обработке распределенных запросов; рассмотрены существующие методы оптимизации выполнения запросов. Сделан вывод о том, что для снижения затрат на передачу данных необходимо оптимизировать непосредственно выражение запроса и методику выполнения запроса с учетом необходимых перемещений данных.

Во втором разделе рассмотрены этапы обработки запроса в распределенной системе; описана общая стратегия трансляции запроса, ее фазы и их задачи; исследованы способы соединения удаленных отношений в распределенных отношений. Исследована методика измерения параметров РИИС (производительность локальных узлов и пропускная способность каналов связи). Разработан метод определения узла для обработки запроса на основе оценки мощности результирующего отношения и методы определения степени селективности предикатов при равномерном и произвольном распределении записей в таблицах на основе статистической информации.

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

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

В заключении сформулированы основные результаты и выводы работы.

В приложении приводятся фрагменты программ ведения базы метаданных РИИС, реализации алгоритмов оптимизации выражений запросов, измерения их параметров и обеспечения удаленного доступа в сети Relcom. Приводится структура таблиц базы метаданных РИИС, а также копии актов внедрения результатов диссертации в промышленность и в учебный процесс.

-111. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ ОБРАБОТКИ

ИНФОРМАЦИИ В РИИС

1.1. Классификация и основные свойства РИИС

Под распределенной информационно-измерительной системой (РИИС) понимается совокупность территориально-разнесенных измерительных комплексов, объединенных с помощью каналов передачи данных в единую систему, предназначенную для удовлетворения потребностей пользователей удаленных узлов в измерительной информации. Обобщенная структура РИИС приведена на рис. 1.1.

Ри�