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

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

ДЯТЧИНА Дарья Васильевна

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

Специальность 05.13.11 - Математическое и программное

обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

3 П яня 2014

005544627

Воронеж-2013

005544627

Работа выполнена в технический университет».

ФГБОУ ВПО «Липецкий государственный

Научный руководитель: Погодаев Анатолий Кирьянович,

доктор технических наук, профессор, ФГБОУ ВПО «Липецкий государственный технический университет», заведующий кафедрой прикладной математики

Официальные оппоненты: Малыш Владимир Николаевич,

доктор технических наук, профессор, ФГБОУ ВПО «Липецкий государственный педагогический университет», заведующий кафедрой электроники коммуникаций и компьютерных технологий

Сапегии Сергей Владимирович,

кандидат технических наук, ФГБОУ ВПО «Воронежский государственный университет», доцент кафедры программирования и информационных технологий

Ведущая организация: ФГБОУ ВПО «Тамбовский

государственный технический

университет»

Защита диссертации состоится «03» марта 2014 г. в 11:00 на заседании диссертационного совета Д 212.037.01 ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский проспект, 14, конференц-зал.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «27» декабря 2013 г.

Ученый секретарь уШ Барабанов Владимир Федорович

диссертационного совета

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

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

Существует множество подходов к минимизации времени получения требуемой информации из базы данных, основанных на оптимизации запросов: логической и семантической. Эти подходы основаны на внутреннем преобразовании запросов, изменении последовательности выполнения операций реляционной алгебры. Мало исследованной является возможность оптимизации запросов в базах данных, содержащих дублируемую информацию. Содержание дубликатов информации позволяет строить различные запросы для получения одной и той же информации, причем время их выполнения может сильно варьироваться. Одним из способов контролируемого хранения и применения дублируемой информации является использование материализованных представлений. Материализованные представления, впервые появившиеся в СУБД Oracle, являются таблицами базы данных, хранящими результаты выполнения запросов. Целостность данных в таблицах материализованных представлений поддерживается периодической синхронизацией или использованием инструментов триггеров.

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

Тематика диссертационной работы соответствует научному направлению ФГБОУ ВПО «Липецкий государственный технический университет» «Алгебраические методы прикладной математики и информатики в моделировании и управлении сложными распределенными системами».

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

Для достижения поставленной цели необходимо решить следующие задачи:

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

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

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

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

- применить разработанное программное обеспечение для реализации задачи сокращения времени выполнения наиболее критических запросов единой информационной системы ЛГТУ (ЕИС ЛГТУ). •

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

Тематика работы соответствует п. 3 «Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем» и п. 4 «Системы управления базами данных и знаний» паспорта специальности 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей».

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

• графовая модель базы данных, отличающаяся представлением структуры базы данных с материализованными представлениями в виде графа и позволяющая определять альтернативные маршруты выполнения запросов;

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

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

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

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

Компоненты математического и программного обеспечения прошли государственную регистрацию в Отраслевом фонде алгоритмов и программ и ФГБУ «Федеральный институт промышленной собственности».

Работа выполнялась при финансовой поддержке грантов РФФИ: «Оптимизация запросов на основе анализа альтернативных маршрутов соединения таблиц базы данных» (проект №06-07-89150_а); «Алгоритмическое обеспечение интегрированных баз данных с минимизацией времени обработки и извлечения информации» (проект №13-07-97519_р_центр_а).

Реализация и внедрение результатов работы. Разработанный программный комплекс внедрен в ФГБОУ ВПО «Липецкий государственный технический университет» при модернизации ЕИС ЛГТУ. Применение созданного специального программного обеспечения позволило сократить время выполнения запросов за счет алгоритма повышения эффективности выполнения запросов, основанного на выборе эффективного маршрута среди множества альтернативных, созданных с помощью механизма перезаписи запроса таким образом, чтобы в нем использовались материализованные представления. Теоретические результаты диссертационной работы используются в учебном процессе ФГБОУ ВПО ЛГТУ при чтении спецкурсов, при выполнении дипломных и курсовых проектов.

Апробация работы. Теоретические и практические результаты, полученные в процессе исследования, докладывались и обсуждались на международной научной конференции "Современные проблемы прикладной математики и математического моделирования" (Воронеж, 2005), Всероссийской школе-конференции молодых учёных "Управление большими системами" (Самара, 2006; Липецк, 2008, 2012; Уфа, 2013), международной научной конференции «Информационные технологии в современном мире» (Таганрог, 2006), международной научной конференции «Сложные системы управления и менеджмент качества СС8С>М» (Старый Оскол, 2007), 54-ой Всероссийской молодежной научной конференции международного уровня «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» (Москва, 2011).

Публикации. Основные результаты диссертационного исследования опубликованы в 15 научных работах, из них 4 - в рецензируемых изданиях, в которых излагаются основные научные результаты диссертации на соискание ученой степени кандидата наук, [5] - свидетельство о государственной регистрации программы для электронных вычислительных машин. В [1, 6] автором предлагается сопоставление структуры БД с графом и методика поиска оптимального маршрута на графе, представляющем собой сложную структуру базы данных, для оптимизации запросов; в [2, 10, 11] автором разработан алгоритм поиска оптимального маршрута соединения отмеченных вершин на графе свободной структуры, имеющем циклы и тупики, с нагруженными вершинами и дугами для дальнейшего использования в информационных системах предприятий; в [3, 4] разработана и применена система оптимизации времени выполнения запросов к информационной системе «Деканат» ЛГТУ: в [9] модифицирована методика внесения контролируемой избыточности в

структуру базы данных; в [8] применен алгоритм оптимизации запросов на основе поиска минимального маршрута на графе к автоматизированным информационным системам образовательных учреждений; в [7] представлен вывод зависимости между временем чтения таблиц и временем их соединения; в [12, 13] предложена автоматическая система оптимального управления запросами в базах данных.

Структура и объем работы: состоит из введения, четырех глав, заключения, библиографического списка из 103 наименований, 6 приложений.' Основная часть работы изложена на 109 страницах машинописного текста, содержит 28 рисунков и 9 таблиц.

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

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

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

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

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

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

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

Задаче поиска множества различных семантически эквивалентных вариантов выполнения запросов в базах данных с материализованными представлениями и выбора среди них эффективного посвящена данная диссертационная работа.

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

_повышения эффективности

0---------------О) выполнения запросов в БД.

Структура БД

X

л

№

I

О

/

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

выполнения запроса

соответствует множество

т> , тт , „ вершин графа (таблиц БД,

Рисунок 1. Пример графоструктуриой „„„„„ ч

■ „Т, используемых в запросе) и

модели БД с- ,

^ ребер между ними (связей

между таблицами, используемых в условиях запроса) (рис.1). Эти множества

вершин и ребер образуют маршрут выполнения запроса на графе.

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

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

Определение 1. Два запроса называются эквивалентными, если при их выполнении получается семантически эквивалентный результат.

Определение 2. Маршрутом выполнения запроса называется множество таблиц, используемых в запросе.

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

Определение 4. N маршрутов называются альтернативными, если любые два из них попарно являются альтернативными маршрутами.

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

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

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

запроса на материализованные представления, удовлетворяющие необходимым условиям.

Обозначим МУ1ем> - множество материализованных представлений, элементами которого являются таблицы. Таким образом, каждое материализованное представление МУ. из \4View можно описать набором

¡А', Г',Ег/, где г - номер материализованного представления; А' - множество выбираемых атрибутов, входящих в запрос, определяющий /-ое материализованное представление; Т1 - множество таблиц, входящих в запрос, определяющий г'-ое материализованное представление; Е' - множество условий, входящих в запрос, определяющий /,-ое материализованное представление. Общее число М¥. равно 5.

Пусть задан исходный запрос £)={А,Т,Е}, где А - множество выбираемых атрибутов в исходном запросе, элементы которого равны {а^а,...,^ }, п - общее их число; Т- множество таблиц в исходном запросе, элементы которого равны {/,,/.,...,4}, т — общее их число; Е - множество условий в исходном запросе, элементы которого равны {е,,е2...,е;}, к - общее их число. В свою очередь каждая таблица tl содержит множество атрибутов А(г1 )= {а!г}, где г - номер атрибута для / таблицы. Алгоритм поиска полной группы маршрутов представлен на рисунке 2.

Альтернативный запрос Щ[пит_иг] создается в соответствии со следующим правилом: множество таблиц Т'^пит_1и-] = Т'"р и МУ:, где

(не Эе, е е Т' и а, е А"0,) =*) = (А(1,)пА")-{А(1,)пА'), ;

т.ч. А((г)^е ее

ч у.

А" — множество атрибутов в запросе, использующихся в условиях; А! - множество выводимых атрибутов в запросе;

и условий Е\[пит_иг] = Е""[пит_иг] и (е е Е'\Зг б Т"'"[пит_иг], гдеА (I) с: е), где Е'"р[пит_иг] = Е'}[пит_иг]\Е.

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

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

= у- у

Рисунок 2. Алгоритм поиска полной группы маршрутов извлечения

информации

Время выполнения запроса, хранимое в служебной таблице, пересчитывается по формуле (1)

1Х'Л, если к ф у,

—--—, если к = /,

2

где Х'Л - взвешенное среднее время на /-ом шаге (после / выполнений запросов по ¿-ому маршруту) выполнения /'-ого запроса по ¿-ому маршруту, - новое взвешенное среднее время на (1+])-ом шаге выполнения /'-ого запроса по ¿-ому маршруту, У^ - время выполнения /'-ого запроса по ¿-ому маршруту на /-ом шаге, Х]к = — номер маршрута, по которому выполнился /'-ый запрос.

Таблица 1. Служебная таблица

Запрос Альтернативные маршруты Среднее время выполнения (с)

Запрос 1 Маршрут 1

Маршрут П/

Запрос к Маршрут 1

Маршрут щ

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

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

Во время работы алгоритма накапливается статистическая информация о времени выполнения запросов по различным маршрутам. По вероятностном)' алгоритму из служебной таблицы выбирается маршрут выполнения запроса на основе накопленных данных.

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

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

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

Результат выполнения запроса

КЛИЕНТ

БАЗА ДАННЫХ

Время выполнения /ого запроса по)-ому

-<трштп\_

у-ыи маршр

■т 1-ого запроса

ОПТИМИЗАТОР

Множество альтернативных

маршрутов Оля 1-ого запроса

СЛУЖЕБНАЯ ТАБЛИЦА

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

1

ХУ--

(2)

где X, - время выполнения запроса по /-ому маршруту, т - количество альтернативных маршрутов для запроса;

2) отрезок от 0 до 1 делится на части таким образом, чтобы длина каждой из частей была равна значению вероятности выбора каждого из маршрутов;

3) по равномерному закону распределения генерируется случайное вещественное число на отрезке от 0 до 1;

4) определяется, на участок какого маршрута попало случайное число; этот маршрут выбирается для выполнения запроса.

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

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

маршрутов на основе вероятностей производится п-1 раз, а при и-ом поступлении запроса выбирается маршрут, не выполнявшийся дольше других. В качестве п можно выбирать различные значения: 100, 200, 500 т.д.

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

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

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

Поиск альтернативных маршрутов для исходного запросе по разработанному кет ___

алгоритму с

использованием

матвркалнзоваккък

представлений

Внесение в служебную таБлкцу времени выполнения запроса I-1+1

Внесение в служебную таблицу маршрута

Выбор оггтимального маршрута из служебной табтшы

Выполнение запроса по выбракноглу маршруту

Внесение в служебную таблицу нового времени выполнения запроса по выбранному маршруту

Рисунок 4.Структура алгоритма повышения эффективности выполнения

запросов в БД

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

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

Для устранения отмеченных недостатков в работе алгоритм повышения эффективности запросов реализован на прокси-уровнс. Прокси-уровсиь использует прокси-сервер для связи с клиентами и сервером баз данных. Схема взаимодействия .«клиент-сервер» с использованием прокси-ссрвсра представлена на рисунке 5.

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

1) запрос от клиента поступает на прокси-уровснь, где происходит его разбор и сопоставление с запросами, хранящимися в служебной таблице;

2) в случае, если в служебной таблице нет соответствующего -запроса, данный запрос непосредственно передастся серверу баз данных;

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

4) на сервере баз данных запрос выполняется но переданному ему от прокси-сервера маршруту. Результаты выполнения передаются клиенту .

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

Клиемгы

Рисунок 5. Схема взаимодействия «Клиент-Прокси-сервер - Сервер БД»

эффективности запроса, msg 4 - запросы с множеством альтернативных маршрутов их выполнения, data - данные, запрошенные клиентом из БД.

Рисунок 6. Схема функционирования программного обеспечения

В диссертации разработано программное обеспечение «Оптимизатор времени выполнения запросов в базах данных», позволяющее сохранять информацию о запросах, множестве их альтернативных маршрутов и времени выполнения, а также осуществлять приём запросов, выбор из служебной таблицы эффективного маршрута. Программа «Оптимизатор времени выполнения запросов в базах данных» написана на языке программирования С# в среде разработки Visual Studio 2010.

Для интеграции прокси-уровня в имеющуюся схему взаимодействия «клиенты - сервер БД» указывается IP адрес клиентского компьютера, на котором он запускается и порт программы, принимающей клиентов. В самой программе указывается порт, на котором принимаются клиенты. IP адрес сервера БД и порт сервера БД.

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

Диаграмма классов, выполненная по методологии UML и отражающая основные объекты проектированного специализированного программного средства, представлена на рисунке 7.

+ connection

- server_port: int

• client_port: int + ait: int

• scrver_ip: string

- client, server: TcpClient

- thread:Thread +■ req: int

- snd__to_srv, snd_to_c1t:bool •close: bool

-Closed: bool

- sndjo_srv_buf:List<byte(]>

- snd__to_cU_buf: Ust<bytefl>

+ IsConnected(): bool + Close()

+ Cannecttot\(server_ip: string, scrver^port. int, client_port. int. client TcpClient, owner: Proxy Server) -♦-Connect: void (serverjp: string, scrver_port: int, clientjiort: int, client:TcpClient)

- scnd_to_server: void(msg:byte[l)

- convert_requcst: byte[|(msg: siring, number int)

- build_mysql_packet: byte(](msg: string, number int)

- send_to_client: void(msg.byte[])

- check_state() void +Open(): void

+ base_mngml

DBConneclion: SQLiteConnection

+ base_mngmt () + insert_cmd: void (query: string) select__cmd. DataSet (query; string) + get_parentjist: string!,] () + gei_allsjisv. stnngLl (parent_id ml) ■>- get_statistics (). string},] + rernove_config- string!,] (parenljd int)

+ updatc_configs: void (parent Jd. int, id: mt.parent_ mask: strmg,alts_masks stnngU) + update_statisties. void ( data string[,|, chances string!,]) +gel_tnask: string (id: int)

+ProxyServer

+req_list: Requests □ + times :string[,] + q_time:qtimefl '+ q_time__num: int

- struct qtime: struct

- scrvcr_port: int

- client_port: int

- serverjp:string

+ connections :List<connection> -tcpListener: TcpListener

- gartmgeRemover. Thread

- listcnThread: Thread

- stop_proxy: bool

+ get_clients_num()

• col!ect_qucry_timc; void (parent: inlalt:int, time: float)

• replace_request: stringfj (req:string)

- Joad_rcquests (): void

• load_statistics (): void + save_statistics(): void

- stop_proxy ()

+ ProxyScrver (serverjp: string, serverjwrt.mt, client_port:int, qjimejnim: in!)

- garbageSearcher (): void

- l.istcnForClients (): void + Stop () void

+ Start (): void

+-id: int + mask.stnng +chance: double

+ Alternatives (id: int. ma.sk:string, chance: double)

Requests

+id: int + maskstrmg

alts: Alternatives!]

+ Requests ()

Рисунок 7. Общая диаграмма классов для специализированно! о программного обеспечения

В состав программы входят следующие компоненты:

- класс Alternatives описывает множество альтернативных маршрутов выполнения запросов, элементы которого содержат номер маршрута, строку запроса, реализующего этот маршрут, и взвешенное время выполнения'запроса по данному маршруту;

- класс Requests описывает запрос, элементы этого класса содержат номер запроса, текст запроса и множество альтернативных маршрутов выполнения запроса;

- класс basejnngmt описывает служебную таблицу. В этом классе реализованы функции создания служебной таблицы, а также функции по ее заполнению и модификации информации. Структура хранения информации о запросах, альтернативных маршрутах и времени их выполнения в базе данных представлена на рисунке 8;

Requests

РК Jd

parent mask chance

Statistics

PK id

times

Рисунок 8. Структура хранения информации о запросах

- класс Connection устанавливает соединение типа «Клиент - Прокси-сервер - Сервер БД», в этом классе реализованы функции установки соединения с сервером баз данных и клиентскими приложениями, взаимной передачи сообщений (в том числе запросов) по установленным соединениям;

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

5—четвертой_главе рассматривается практическое применение

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

В ЕИС ЛГТУ были созданы материализованные представления Mview 1, Mvievv_ 2, ..., Mview_n, которые могут быть использованы для оптимизации запросов с альтернативными маршрутами их выполнения. Проведены испытания оптимизации ряда запросов, для которых были найдены полные группы альтернативных маршрутов.

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

При выполнении запроса по маршруту исходного варианта 100 раз общее время равно 217,9 е., а по алгоритму разработанной системы оптимизации общее время составляет 62,3 е., что в 3,5 раза быстрее, чем по исходному варианту.

Таблица 2. Время выполнения запроса для различных вариантов

Число выполнений Варианты

Оптимизированный Исходный

10 6,3 21,7

20 12,5 43,5

30 18,8 65,2

40 25 86,98

50 31,3 108,6

60 37,5 130,4

70 43,8 152,1

80 50,8 173,8

90 56,3 195,6

100 62.5 217,3

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

Для анализа системы оптимизации проведены испытания выпопнения исходного запроса 100 раз для каждого варианта: разработанный алгоритм схемы оптимизации, альтернативные маршруты (М1, М2, МЗ) и исходный вариант. По результатам испытаний построены графики для каждого варианта выполнения запроса, представленные на рисунке 10.

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

В данном примере время исходного запроса меньше, чем время альтернативного маршрута МЗ при использовании материализованного представления. Это показывает, что не всегда использование маршрутов выполнения запросов с материализованными представлениями будет эффективнее, чем маршрутов без материализованных представлений.

Разработанное программное обеспечение было применено к ЕИС ФГБОУ ВПО «Липецкий государственный технический университет», что позволило повысить эффективность автоматизированных процессов обработки информации за счет оптимизации запросов, связанных с контролем и анализом учебного процесса.

-Ф-ЭЦаОШШЛ

ирв

25239(32288

Рисунок 9. Время выполнения запроса

Рисунок 10. Время выполнения для различных вариантов выполнения запроса

И шктючении диссертации сформулированы основные научные и практические результаты диссертационного исследования

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

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

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

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

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

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

5. Разработано и зарегистрировано программное обеспечение «Оптимизатор времени выполнения запросов в базах данных», реализуемо« на прокси-уровне

6. Разработанное программное обеспечение было использовано для реализации задачи сокращения времени наиболее критических запросов в Г. И С ЛГТУ, используемой в учебном процессе ФГБОУ ВПО «Липецкий государственный технический у ниверситет».

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

Публикации в изданиях, рекомендованных ВАК РФ

ir ^ЯТЧИНа' Д'В- Альтернативные соединения таблиц баз данных IТекст! /А.К. Погодаев, А.Ю. Муравейко, Д.В. Дятчина // Системы управл яя и

информационных технологий.-2005.-№5(22).-С 99-102 > Р Ле"ИЯ и

2. Дятчина, Д.В. Метод оптимизации запросов на основе альтернат™™™ соединения таблиц баз данных для информационный íZrZ

системы ттаив ^°Г0ДаеВ' А.Ю. Муравейко, Д.В. Дятчина // МашТн^е Г системы приводов и детали машин. - 2006. -Спец. вып - С 331 337

L, Дятчина' Д-В. Применение алгоритма оптимизация запросов на основе внесения контролируемой избыточности в базах данных [Текст] /Д В Дятчина // Вести высших учебных заведений Черноземья. - 2012 - №4 - С 48 51

машин

ГСексЛТ пВ" °ПТПМИЗттат°Р °РеМеШ выпо™е™я запросов в базах данных Пекст] /А.К. Погодаев, Д.В. Дятчина // М.: ФГБУ ФИПС - 20П Госрегистрация № 2013661250 от 03.12.2013.

Статьи и материалы научных конФеретгнй

,6ЯпппДЯТЧИНа' Д'В' Алг°Ри™ альтернативного соединения для оптимизации запросов в реляционных системах [Текст] /А.К. Погодаев, 1ю м Гв еГо Д.В. Дятчина // Вести высших учебных заведений Черноземья. - 2006-ад

7. Дятчина, Д-В. Оптимизация в информационных системах образовательных Убеждений на основе альтернаты*«ний^

ппо^п "°Г°ДаеВ' А'Ю- Муравейко, Д.В. Дятчина // Компьютерные у«б£ые программы и инновации. - 2006. - №9. - С 94-98 верные у «оные

8. Качура (Дятчина), Д.В. Вывод зависимости мевду временем чтения

—й 722: НХ С°еДИНеННЯ ДЛЯ --на™

ГТекст! /А К ""Ф^4"0™"* СИСТ£МаХ общеобразовательных учреждений 1екст] /А.К. Погодаев, А.Ю. Муравейко, Д.В. Качура Дятчина //Компьютерные учебные про1раммы и инновации. -2008,- № П С 149 1 "б V. Дятчина, Д.В. Алгоритм оптимизации альтернативных сое-ш„ен„й таблиц реляционной базы данных в управлении" оргаГацГ"

/Д.В. Дятчина, А.Ю. Муравейко // Управление большими системами: сборник трудов I Всероссийской школы-семинара молодых ученых. - Выпуск 14. -Воронеж: ВГАСУ. - 2006. - С.63-68.

10. Дятчина, Д.В. Алгоритм оптимизации на графе для анализа альтернативных соединений реляционных таблиц [Текст] /А.Ю. Муравейко, Д.В. Дятчина. А.К. Погодаев // Информационные технологии в современном мире:материалы международной научной конференции. -Часть 2 - Таганрог, 2006. - С.78-80.

11. Дятчина, Д.В. Оптимизация альтернативных соединений в запросах реляционных информационных систем на основе теории графов [Текст] /А.Ю. Муравейко, Д.В. Дятчина, А.К. Погодаев . // Сложные системы управления и менеджмент качества CCSQM'2007: сборник трудов Международной научной конференции. - Старый Оскол: ООО «ТНТ». - 2007-С. 90-93.

12. Качура (Дятчина), Д.В. Динамическая оптимизация запросов реляционных информационных систем на основе альтернативных соединений [Текст] /А.Ю. Муравейко, Д.В. Качура (Дятчина), А.К. Погодаев // Управление большими системами: сборник научных трудов V Всероссийская школа-семинар молодых ученых»: Сборник трудов.- Т. 2 - Липецк: ЛГТУ. - 2008-С. 95-102.

13. Дятчина, Д.В. Алгоритм оптимального управления запросами в базах данных с альтернативными маршрутами соединения таблиц [Текст] /Д.В. Дягчина, А.К. Погодаев // Управление большими системами: сборник научных трудов IX Всероссийской школы-конференции молодых ученых. -Т. 1. - Тамбов-Липецк: Изд-во Першина Р.В. - 2012. - С.35-37.

14. Дятчина, Д.В. Автоматическая система оптимального управления запросами в базах данных с альтернативными маршрутами соединения таблиц [Текст] /Д.В. Дятчина, А.К. Погодаев //Управление большими системами: сборник научных трудов X Всероссийской школы-конференции молодых ученых. - Т. 3. - Уфа: УГАТУ. - 2013.- С.175-178.

15. Дятчина, Д.В. Оптимизация запросов [Текст] / Д.В. Дятчина, А.К. Погодаев, Е.С. Попова. - М.: ОФАП - 2011. Госрегистрация № 50201150664 от 11.05.2011.

Подписано в печать 27.12.2013. Формат 60 х 84 1/16. Бумага офсетная. Усл. печ. л. 1,0 Тираж 100 экз. Заказ № . Издательство Липецкого государственного технического университета. Полшрафическое подразделение Издательства ЛГТУ. 398600 Липецк, ул. Московская, 30.

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

Специальность 05.13.11-Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

ДЯТЧИНА Дарья Васильевна

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

Научный руководитель -доктор технических наук, профессор А.К. Погодаев

Липецк-2013

ОГЛАВЛЕНИЕ

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

1. ОБЩЕЕ ПРЕДСТАВЛЕНИЕ О БАЗАХ ДАННЫХ И ПОДХОДАХ К ОПТИМИЗАЦИИ ЗАПРОСОВ.........................................................12

1.1. Общее представление информационных систем..................12

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

1.2.1. Логическая оптимизация запросов.......................................17

1.2.2. Семантическая оптимизация запросов.................................20

1.2.3. Денормализация баз данных..................................................23

1.2.4. Современные подходы к оптимизации запросов................28

1.2.5. Материализованные представления.....................................30

1.3. Методы оценивания времени выполнения запросов.............33

Выводы..............................................................................38

2. ОПТИМИЗАЦИЯ ЗАПРОСОВ С АЛЬТЕРНАТИВНЫМИ МАРШРУТАМИ ИХ ВЫПОЛНЕНИЙ В БАЗАХ ДАННЫХ..........................40

2.1. Альтернативные маршруты выполнения запросов...................40

2.2. Выбор оптимального маршрута..........................................50

2.3. Схема оптимизации запросов с альтернативными маршрутами их

выполнения........................................................................55

Выводы..............................................................................59

3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ОПТИМИЗАЦИИ ЗАПРОСОВ В БАЗАХ ДАННЫХ.......................................................................61

3.1. Общие сведения..............................................................61

3.2. Функциональное назначение..............................................61

3.3. Описание логической структуры программы..........................63

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

3.5. Общее описание работы программного обеспечения...............70

Выводы..............................................................................76

4. РЕАЛИЗАЦИЯ СИСТЕМЫ ОПТИМИЗАЦИИ ЗАПРОСОВ В

АВТОМАТИЗИРОВАННЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ............77

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

4.2. Структура ЕИС ЛГТУ......................................................78

4.3. Состав и структура внутримашинной информационной базы данных..............................................................................79

4.4. Материализованные представления в ЕИС ЛГТУ....................79

4.5. Результаты работы программного и математического обеспечения

........................................................................................85

Выводы..............................................................................97

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

СПИСОК ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ..................................................99

ПРИЛОЖЕНИЕ 1................................................................................................110

ПРИЛОЖЕНИЯ 2................................................................................................113

ПРИЛОЖЕНИЕ 3................................................................................................120

ПРИЛОЖЕНИЕ 4................................................................................................123

ПРИЛОЖЕНИЕ 5................................................................................................124

ПРИЛОЖЕНИЕ 6................................................................................................125

ВВЕДЕНИЕ

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

Существует множество подходов к минимизации времени получения требуемой информации из базы данных, основанных на оптимизации запросов: логической и семантической. Эти подходы основаны на внутреннем преобразовании запросов, изменении последовательности выполнения операций реляционной алгебры. Мало исследованной является возможность оптимизации запросов в базах данных, содержащих дублируемую информацию. Содержание дубликатов информации позволяет строить различные запросы для получения одной и той же информации, причем время их выполнения может сильно варьироваться. Одним из способов контролируемого хранения и применения дублируемой информации является использование материализованных представлений. Материализованные представления, впервые появившиеся в СУБД Oracle, являются таблицами базы данных, хранящими результаты выполнения запросов. Целостность данных в таблицах материализованных представлений поддерживается периодической синхронизацией или использованием инструментов триггеров.

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

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

Тематика диссертационной работы соответствует научному направлению ФГБОУ ВПО «Липецкий государственный технический университет» «Алгебраические методы прикладной математики и информатики в моделировании и управлении сложными распределенными системами».

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

Для достижения поставленной цели необходимо решить следующие задачи:

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

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

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

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

- применить разработанное программное обеспечение для реализации задачи сокращения времени выполнения наиболее критических запросов единой информационной системы ЛГТУ (ЕИС ЛГТУ).

Методы исследования базируются на использовании теории баз

данных, графоструктурного моделирования, математической статистики,

5

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

Тематика работы соответствует п. 3 «Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем» и п. 4 «Системы управления базами данных и знаний» паспорта специальности 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей».

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

• графовая модель базы данных, отличающаяся представлением структуры базы данных с материализованными представлениями в виде графа и позволяющая определять альтернативные маршруты выполнения запросов;

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

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

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

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

маршрутами их выполнения с целью повышения скорости получения информации для быстрого принятия решения.

Работа выполнялась при финансовой поддержке грантов РФФИ: «Оптимизация запросов на основе анализа альтернативных маршрутов соединения таблиц базы данных» (проект №06-07-89150_а); «Алгоритмическое обеспечение интегрированных баз данных с минимизацией времени обработки и извлечения информации» (проект №13-07-97519_р_центр_а).

Реализация и внедрение результатов работы. Разработанный программный комплекс внедрен в ФГБОУ ВПО «Липецкий государственный технический университет» при модернизации ЕИС ЛГТУ. Применение созданного специального программного обеспечения позволило сократить время выполнения запросов за счет алгоритма повышения эффективности выполнения запросов, основанного на выборе эффективного маршрута среди множества альтернативных, созданных с помощью механизма перезаписи запроса таким образом, чтобы в нем использовались материализованные представления. Подтверждено регистрацией библиотеки программ в Роспатент и актом о внедрении. Теоретические результаты диссертационной работы используются в учебном процессе ФГБОУ ВПО ЛГТУ при чтении спецкурсов, при выполнении дипломных и курсовых проектов.

Апробация работы. Теоретические и практические результаты,

полученные в процессе исследования, докладывались и обсуждались на

международной научной конференции "Современные проблемы прикладной

математики и математического моделирования" (Воронеж, 2005),

Всероссийской школе-конференции молодых учёных "Управление большими

системами" (Самара, 2006; Липецк, 2008, 2012; Уфа, 2013), международной

научной конференции «Информационные технологии в современном мире»

(Таганрог, 2006), международной научной конференции «Сложные системы

управления и менеджмент качества СС8рМ» (Старый Оскол, 2007), 54-ой

Всероссийской молодежной научной конференции международного уровня

7

«Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» (Москва, 2011).

Публикации. Основные результаты диссертационного исследования опубликованы в 19 научных работах, из них 4 - в рецензируемых изданиях, в которых излагаются основные научные результаты диссертации на соискание ученой степени кандидата наук, [22] - свидетельство на программу для электронных вычислительных машин, базу данных, топологию интегральных микросхем. Самые значимые работы приведены в автореферате. В [59, 61] автором предлагается сопоставление структуры БД с графом и методика поиска оптимального маршрута на графе, представляющем собой сложную-структуру базы данных, для оптимизации запросов; в [62, 46, 50] автором разработан алгоритм поиска оптимального маршрута соединения отмеченных вершин на графе свободной структуры, имеющем циклы и тупики, с нагруженными вершинами и дугами для дальнейшего использования в информационных системах предприятий; в [66] разработана и применена система оптимизации времени выполнения запросов к информационной системе «Деканат» ЛГТУ; в [18] модифицирована методика внесения контролируемой избыточности в структуру базы данных; в [47] применен алгоритм оптимизации запросов на основе поиска минимального маршрута на графе к автоматизированным информационным системам образовательных учреждений; в [42] представлен вывод зависимости между временем чтения таблиц и временем их соединения; в [21, 48] предложена автоматическая система оптимального управления запросами в базах данных.

Структура и объем работы: состоит из введения, четырех глав, заключения, библиографического списка из 103 наименований, 6 приложений. Основная часть работы изложена на 109 страницах машинописного текста, содержит 28 рисунков и 9 таблиц.

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

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

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

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

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

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

Рассмотренные подходы оптимизации запросов основаны на

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

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

Денормализованная структура базы данных содержит дубликаты

информации в разных таблицах, что позволяет создавать различные запросы

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

9

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

Задаче поиска множества различных семантически эквивалентных вариантов выполнения запросов в базах данных с материализованными представлениями и выбора среди них эффективного посвящена данная диссертационная работа.

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

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

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

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

изменении объема хранимой информации в таблицах базы данных.

10

Разработанная схема является универсальной для оптимизации времени выполнения запросов в базах данных с альтернативными маршрутами соединения и может быть применена для любой базы с материализованными представлениями.

В третьей главе описывается программное обеспечение «Оптимизатор времени выполнения запросов в базах данных», представляющее собой прокси-уровень, позволяющее осуществлять взаимодействие СУБД и клиентских приложений через прокси-сервер, а также сохранять информацию о запросах, множестве альтернативных маршрутов их выполнения и времени выполнения по каждому из них, для дальнейшего использования в оптимизации запросов, а также осуществ�