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

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

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

Мг

003449ЭЭ6

Новосельский Вениамин Борисович

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

05.13.12 - Системы автоматизации проектирования (приборостроение)

АВТОРЕФЕРАТ

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

1 6 СПТ 2009

Санкт-Петербург - 2008 г.

003449996

Работа выполнена на кафедре Информатики и прикладной математики Санкт-Петербургскт о государственного университета информационных технологий, механики и оптики

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

Официальные оппоненты.

Кандидат технических наук, доцент

Павловская Татьяна Александровна

Доктор технических наук, профессор

Гатчин Юрий Арменакович

Кандидат технических наук, доцент

Щупак Юрий Абрамович

Ведущее предприятие ОКБ «Электроавтоматика», г Санкт-Петербург

Защита диссертации состоится « 21 » октября 2008 г. в 15 час 50 минут на заседании диссертационного совета Д212.227 05 при Санкт-Петербургском государственном университете

информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д 49

Автореферат разослан « /У » % 2008 г.

Ученый секретарь

диссертационного совета Д 212 227.05 кандидат технических наук, доцент

[ Поляков В. И.

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

Актуальность темы. Базы данных занимают центральное место в автоматизированных информационно-управляющих системах (АИУС) приборостроения Процесс проектирования некоего прибора или устройства состоит из ряда этапов Каждый этап, помимо обладания собственной локальной информацией, имеет определеш1ые информационные связи с другими этапами Например, такие этапы как проектирование конструктивно-функциональных узлов, моделирование работ ы устройства, построение контролирующих тестов, разделяют общие данные (например, элементную базу устройства, информацию о способах использования и т.п ), т е. каждый этап информационно связан с центральной базой данных, содержащей общие данные

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

От эффективности и качества построения баз данных во многом зависит эффективность разрабатываемых АИУС приборостроения Поэтому разработка САПР РБД является важной и актуальной задачей.

Для достижения высокой производительности распределенных приложений, работающих с базами данных, необходимы эффективные методы проектирования РБД

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

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

Для достижения указанной цели определены следующие задачи исследования:

- рассмотрение и анализ характеристик распределенных систем обработки данных;

- описание и изучение основных задач, входящих в процесс проектирования РБД;

- анализ постановки и исследование зависимостей задач фрагментации БД, размещения фрагментов и формирования стратегий исполнения запросов;

- выбор и обоснование критерия эффективности РБД;

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

- разработка экспертно-исследовательской системь1 и прототипа САПР РБД на основании предложенных алгоритмов

Объект исследования - распределенные базы данных Предметом исследования являются модели и алгоритмы автоматизированной системы, предназначенной для описания методики распределения БД

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

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

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

- Выбран и обоснован критерий эффективности РБД, учитывающий влияние степени использования ресурсов на время ответа на запрос и коэффициент готовности

транзакций. Критерий позволяет проектировщику устанавливать приоритет времени ответа на запрос и коэффициента использования ресурсов,

- Проведено исследование и выявлены зависимости влияния репликации фрагментов БД и физических характеристик ВС на время ответа на запрос с учетом применения внутриоператорного параллелизма;

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

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

Апробация результатов исследования. Основные положения диссертационной работы доложены и обсуждены на IV Межвузовской конференции молодых ученых (г. Санкт-Петербург, 2007 г.), XXXVII научной и учебно-методической конференция СПбГУ ИТМО (г. Санкт-Петербург, 2008 г.), V Межвузовской конференции молодых ученых (г. Санкт-Петербург, 2008 г.), XV Всероссийской научно-методической конференции

«Телематика'2008» (г Санкт-Петербург, 2008 г.).

Публикации. По теме диссертации опубликовано 6 статьей.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, списка использованной литературы из 65 наименований. Общий объем диссертации 114 страниц, включая 17 рисунков и 13 таблиц.

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

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

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

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

До того момента, когда началось изучение распределенных БД, вычислительные сети существовали уже продолжительное время Исторически, задача распределения данных рассматривалась в связи с файлами Вопросами размещения файлов занимались такие ученые как В.В Чу, РГ Кэйси, КД Левин и ХЛ. Морган. Первым, кто указал на различия задач проектирования размещения файлов и БД был М.Ж Аперс.

Далее рассмотрен процесс проектирования РБД. Описываются задачи, которые решаются на этапе проектирования: фрагментация данных и размещение фрагментов

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

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

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

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

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

Проведен обзор работ по данной теме, который показывает, что все задачи обладают свойством №-полноты. Проанализированы описанные методы решения данных задач и указаны их недостатки.

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

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

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

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

^Цк^+Са^У/^тт, 1=1 ./=0

где к - количество узлов ВС; п - количество запросов; -частота возникновения у-го запроса в г-ом узле, Ql] - временной коэффициент у-ого запроса, порожденного в /-ом узле; Жд -коэффициент использования ресурсов при обработке у-го запроса, порожденного в /-ом узле; с{ и са - коэффициенты, определяющие приоритеты времени ответа и готовности транзакций, значения с, и са находятся в интервале [0..1] и определяются проектировщиком.

Временной коэффициент у-ого запроса определяется как Q,J=Tlf/TlJl, те равен отношению времени ответа на запрос, исполненного в РБД, к расчетному времени ответа на запрос, исполненного локально в узле /', при условии наличия в узле всех необходимых фрагментов Коэффициент использования ресурсов равен сумме коэффициентов использования центрального -процессора и внешнего запоминающего устройства узлов, вовлеченных в операцию, и коэффициента использования сетевых ресурсов.

Такой критерий обеспечивает оптимальность решения, но не обеспечивает допустимость, т.к. минимизируется общее время ответа системы в целом Поэтому введено ограничение на максимально допустимое время ответа на запрос в каждом узле-6/ < , где ] = 0 п, £Г - максимально допустимое время ответа на запрос у.

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

Г=и(1-—']/Ги + 1 + Г|,

I я)!У д/

где (2 - общее количество читаемых данных; 5 - скорость чтения единицы данных в ¿-том узле, п - количество узлов, на которых размещены данные; Л - скорость передачи единицы данных по сети; Р - время передачи запроса от /-го узла до узла к, А - соотношение скоростей локального и сетевого чтения (11=Д8).

На рис. 1 показан график зависимости сокращения времени исполнения оператора от соотношения скоростей локального чтения и передачи по сети при чтении 1Мб данных.

Рис 1 Сокращение времени исполнения оператора

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

04 03

-*-1у1ел расч I 2 узла, раст

02 . ■

I 1 У1РЛ Экс

—2у?ла зьс

01

00

001 021 041 061 081

соотношение скорости локального чтения к скорости удаленного чтения

Рис 2 Расчетное и экспериментальное сокращение времени исполнения оператора

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

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

1 всем узлам отсылается сообщение «подготовка к подтверждению транзакции»,

2 от всех узлов получается ответ «готов к подтверждению транзакции»,

3 всем узлам отсылается сообщение «подтвердить транзакцию»;

4. от всех узлов получается ответ «транзакция подтверждена»

В работе Ж.М. Йохансона, С.Т. Марча и Ж Д. Науманна получена следующая аналитическая формула времени обновления

где Su - время передачи запроса от узла-источника транзакции t до z-го узла; Rjt - время передачи ответа от узла j до узла-источника транзакции t, п - число узлов, на которых размещены фрагменты. Stl включает время на передачу и задержки в сети, Rlt состоит из задержки от t до j, времени обработки на узле г, времени передачи ответа от узла /

Для простоты можно положить, что время передачи запроса до всех узлов одинаково и сообщения отсылаются и обрабатываются узлами параллельно, тогда время обновления Tu^A*Su+3*RJ t

Также описано применение двух техник соединения отношений в реляционной БД, позволяющее сократить время ответа, semi-join (неполное соединение) и double-pipelined hash-join (двойное конвейерное хэш-соединение)

Техника semi-join может применяться при соединении отношений, находящихся на разных узлах Пусть отношение А находится в узле 1 и отношение В находится в узле 2 Идея semi-join состоит в отправке на узел 2 колонок отношения А, по которым осуществляется соединение, нахождение и отправка на узел 1 только тех записей из В, которые удовлетворяют условию соединения Как правило, техника semi-join позволяет получить выигрыш в случае, когда отношение В содержит «тяжелые» колонки, например мультимедийную информацию

Идея double-pipelined hash-join состоит в формировании двух хэш-таблиц На и НЬ, изначально хэш-таблицы пусты Записи из А и В обрабатываются по одной в каждый момент времени. Для записи из А в НЬ ищутся соответствующие ей записи, после чего запись из А и найденные записи из В возвращаются как результаты соединения и запись из А помещается в хэш-таблицу На Далее берется запись из В и обрабатывается аналогичным образом.

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

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

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

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

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

На основании зависимости этапов проектирования предложено применение вложенных ГА. В разработанном методе для каждой хромосомы из сформированного поколения схем

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

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

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

Определение 1 Простым предикатом называется предикат (А у \)/), где А - атрибут отношения II,-у е {=,*,>,>,<,<}, \уеВОМ(А), йОМ(А) - домен значений А.

Определение 2. Пусть X множество простых предикатов X] х„ определенных на отношении Л Множество У(Х) минтермов у1 ут, связанных с X, определяется как у,=л(х]и-х}), х}еХ, т.е. состоит из предикатов, каждый из которых образован конъюнкцией всех простых предикатов х, в натуральной или отрицательной форме.

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

Определение 3 Разбиением множества А называется множество непересекающихся, непустых подмножеств А„ объединение которых совпадает с множеством А, те щ=>А,пА]=0, иА}=А.

На основании того, что набор минтермов У(Х) обладает свойствами полноты и достаточности, а для групп атрибутов эти свойства очевидны исходя из определения, описанная

фрагментация обладает свойствами полноты и восстанавливаемости.

Схема размещения описывается матрицей Б, строками которой являются узлы ВС, а столбцами - сформированный набор фрагментов. Единица в ячейке матрицы означает наличие фрагмента г в узле ] Структура матрицы приведена в таблице 1.

Таблица 1 Пример кодирования схемы фрагментации и размещения

Узлы \ фрагменты Отношение 1 Отношение 2

Атрибуты Предикаты Атрибуты Предикаты

Атр1 Атр2 Пред1 Пред2 Атр1 Атр2 Пред1 Пред2

Узел! 1 0 1 1 0 1 0 1

Узел2 0 1 1 0 1 1 1 0

Для удовлетворения свойства полноты схемы размещения в каждом столбце должна быть хотя бы одна единица Каждому атрибуту и предикату назначено значение мощности: для атрибутов мощность определена на основании типа данных, для предикатов - селективности. На основании мощности определяется количество возвращаемых запросом данных.

Бинарная матрица D формирует хромосому фрагментации и размещения. Популяция внешнего ГА составлена из матриц D, операция скрещивания между двумя особями осуществляется построчно.

При исполнении реляционного запроса необходимо принять следующие решения:

1. В какой последовательности производить операции соединения,

2. В каком узле производить операцию соединения,

3. Применять ж технику semi-join при соединении;

4. Применять ли технику double-pipelined hash join при соединении,

5. Какие узлы, имеющие необходимые фрагменты, использовать при внутриоператорном параллелизме

Способ кодирования стратегии исполнения запроса поясним на примере запроса, в котором используется три фрагмента и два соединения.

1 Сначала выполняется первая операция соединения, затем вторая Ген 12,

2. Первое соединение производится в узле 0, второе - в узле 1. Ген 01,

3. Для первой операции соединения применяется semi-join, для второй - не применяется Ген 10;

4 Double-pipelined hash join не применяется при первом соединении, применяется во втором. Ген: 01,

5. Оператор чтения первого фрагмента исполняется на узле 2, дополнительно в чтение вовлечены узлы 1 и 0 Чтение второго фрагмента производится только на узле 0. Оператор чтения третьего фрагмента исполняется на узлах 1 и 3. Ген 210 0 13.

Итоговый код хромосомы приведен в таблице 2.

Таблица 2 Пример хромосомы стратегии исполнения

запроса

Соединение Чтение фрагментов

Фрагмент 1 Фрагмент 2 Фрагмент 3

12 01 10 01 210 0 13

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

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

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

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

Четвертая глава посвящена вопросам практической реализации и применения разработанного алгоритма

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

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

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

исполнения запросов с соответствующими значениями критерия эффективности.

Применение результатов диссертационной работы при проектировании РБД медицинской системы, разрабатываемой в ООО «ВейвАксесс», подтверждено актом внедрения.

ЗАКЛЮЧЕНИЕ

Основные результаты работы состоят в следующем

1. Проанализированы этапы, входящие в процесс проектирования РБД;

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

3. Выбран и обоснован критерий эффективности РБД, позволяющий проектировщику устанавливать приоритеты времени ответа на запросы и коэффициента готовности транзакций;

4 Описана архитектура РБД, учитывающая возможности параллельного исполнения операторов,

5 Исследовано влияние репликации фрагментов БД и физических характеристик ВС на время ответа на запрос с учетом параллельного исполнения,

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

7 Разработанная экспертно-исследовательская система, реализующая предложенный алгоритм, является прототипом САПР РБД

Основные положения диссертации опубликованы в следующих работах.

1 Новосельский В.Б Проблемы и задачи автоматизированного проектирования распределенных баз данных // Научно-технический вестник СПбГУ ИТМО Исследования в области

информационных технологий Труды молодых ученых. -СПб: СПбГУ ИТМО. - 2007. - вып. 39 - с. 157-163.

2. Новосельский В.Б., Павловская Т А Выбор и обоснование критерия эффективности при проектировании распределенных баз данных // Научно-технический вестник СПбГУ ИТМО, 2008. Принято в печать

3 Новосельский В.Б. Применение генетических алгоритмов при проектировании распределенных баз данных // Научно-технический вестник СПбГУ ИТМО, 2008 Принято в печать

4 Новосельский В.Б Решение задачи распределения реляционной базы данных // Журнал научных публикаций аспирантов и докторантов - 2008. - N5. - с 158-160, ISSN 1991-3087

5. Новосельский В Б. Метод автоматизации проектирования распределенной реляционной базы данных // Программные продукты и системы. - 2008. - N3. - с 45-48

6 Метод проектирования процесса распределения реляционной базы данных / В.Б. Новосельский // Изв вузов. Приборостроение"- 2008. - Т. 51. - № 7. - с. 39-42.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул , 14 Тел (812)233 46 69

Тираж 100 экз

ВВЕДЕНИЕ.

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

1.1 Характеристики распределенных систем.

1.1.1 Прозрачность.

1.1.2 Открытость.

1.1.3 Гибкость.

1.1.4 Масштабируемость.

1.2 Концепции программных решений.

1.3 Распределенные базы данных.

1.3.1 Разновидности распределенных СУБД.

1.4 Проектирование базы данных.

1.4.1 Моделирование локальных представлений.

1.4.2 Объединение локальных моделей.

1.4.3 Средства автоматизированного проектирования.

1.5 Построение модели данных.

1.5.1 Иерархическая модель.

1.5.2 Сетевая модель.

1.5.3 Реляционная модель.

1.5.4 Модель «Сущность-связь».

1.5.5 Многомерная модель данных.

1.5.6 Объектно-ориентированная модель.

1.6 Объектные базы данных.

1.7 Проектирование распределенных БД.

1.7.1 Проектирование распределенных ООБД.

1.7.2 Терминология.

1.8 Фрагментация данных.

1.9 Размещение данных.

1.10 Репроекгирование и материализация.

1.11 Обзор и анализ существующих работ.

1.11.1 Фрагментаг(ия.

1.11.2 Размещение.

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

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

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

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

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

Для достижения указанной цели определены следующие задачи исследования:

- рассмотрение и анализ характеристик распределенных систем обработки данных;

- описание и изучение основных задач, входящих в процесс проектирования РБД;

- анализ постановки и исследование зависимостей задач фрагментации БД, размещения фрагментов и формирования стратегий исполнения запросов;

- выбор и обоснование критерия эффективности РБД;

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

- разработка прикладных программ на основании предложенных алгоритмов.

Объект исследования - распределенные базы данных. Предметом исследования являются модели и алгоритмы автоматизированной системы, предназначенной для описания методики распределения БД.

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

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

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

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

- Проведено исследование и выявлены зависимости влияния репликации фрагментов БД и физических характеристик ВС на время ответа на запрос с учетом применения внутриоператорного параллелизма;

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

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

Апробация результатов исследования. Основные положения диссертационной работы доложены и обсуждены на IV Межвузовской конференции молодых учёных (г. Санкт-Петербург, 2007 г.), XXXVII научной и учебно-методической конференция СПбГУ ИТМО (г. Санкт-Петербург, 2008 г.), V Межвузовской конференции молодых учёных (г. Санкт-Петербург, 2008 г.), XV Всероссийской научно-методической конференции «Телематика'2008» (г. Санкт-Петербург, 2008 г.).

Публикации. По теме диссертации опубликовано 6 статьей.

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

Заключение

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

1. Проанализированы этапы, входящие в процесс проектирования РБД;

2. Сформулирована задача проектирования РБД, учитывающая взаимосвязь фрагментации данных, размещения фрагментов и стратегии исполнения запросов и оценена ее сложность;

3. Выбран и обоснован критерий эффективности РБД, позволяющий проектировщику устанавливать приоритеты времени ответа на запросы и коэффициента готовности транзакций;

4. Описана архитектура РБД, учитывающая возможности параллельного исполнения операторов;

5. Исследовано влияние репликации фрагментов БД п физических характеристик ВС на время ответа на запрос с учетом параллельного исполнения;

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

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

1. Стеен М., Тенебаум Э. Распределенные системы. Принципы и парадигмы // СПб: Питер, 2003. 880 с.

2. Швецов В.И., Визгунов А.Н., Мееров И.Б. Базы данных // Нижний Новгород: Издательство Нижегородского госуниверситета, 2004. — 271 с.

3. Цегелик Г.Г. Системы распределенных баз данных // Львов: Свит, 1990. 166,1. с.

4. Дейт К.Д. Введение в системы баз данных: Пер. с англ. 6-е изд. // Диалектика, 1998.- 846 с.

5. Garcia-Molina Н., Lindsay В. Research directions for distributed databases // SIGMOD Rec. 1990. - Vol. 19, N4. - 98-103. - ISSN 0163-5808.

6. Роб П., Коронел К. Системы баз данных: проектирование, реализация и управление. 5-е издание. // СПб: БХВ-Петербург, 2004. 1040 с.

7. Багуи С. Объектно-ориентированные базы данных: достижения и проблемы // Открытые системы. 2004. - №3.

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

9. Новосельский В.Б. Проблемы и задачи автоматизированного проектирования распределенных баз данных // Научно-технический вестник СПбГУ ИТМО. 2007. - №39. - с. 157-163. - ISSN 1819-222Х.

10. Cattell R. The Object Data Standart: ODMG 3.0 // San Francisco, USA: Morgan Kaufmann Publishers Inc., 2000. 280 p.

11. Eisenberg A., Melton J. SQL 1999, formely known as SQL 3 // ACM SIGMOD international conference on Management of data. 1999. - pp. 131-138.

12. Meghini C., Thanos C. The complexity of operations on a fragmented relation // ACM Transactions on Database Systems. 1991. - Vol. 16,1. N1.-pp. 56-87.

13. Baiao F., Mattoso M., Zaverucha G. A Distribution Design Methodology for Object DBMS // Distributed and Parallel Databases. 2004. - N16. -pp. 45-90.

14. Ceri S., Pelagatti G. Distributed databases principles and systems // McGraw-Hill, Inc., 1984. 393 p.

15. Navathe S., Ra M. Vertical partitioning for database design: a graphical algorithm // SIGMOD Rcc. 1989. - Vol. 18, N2. - pp. 440-450. - ISSN 0163-5808.

16. Бурков B.H., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными системами // М.: Спнтег, 2001. 124 с.

17. Materialization of Redesigned Distributed Relational Databases: Technical Report / Hong Kong University of Science & Technology; Karlapalem K., Navathe S.B. Hong Kong, 1994. - 44 p. - HKUST-CS94-14.

18. Stepwise Redesign of Distributed Relational Databases: Technical Report / Hong Kong University of Science & Technology; Kazerouni L., Karlapalem K. Hong Kong, 1997. - 28 p. - HKUST-CS97-12.

19. Karlapalem K., Navathe S.B., Ammar M. Optimal redesign policies to support dynamic processing of applications on a distributed relational database system // Information Systems. 1996. - Vol. 21, N4. - pp. 353-367. - ISSN 0306-4379.

20. Apers P.M.G. Data allocation in distributed database systems // ACM Transactions on Database Systems. 1988. - Vol. 13, N3. - pp. 263-304.

21. Бабанова Н.И. Разработка и оптимизация моделей и алгоритмов автоматизированного проектирования локальных и распределенных баз данных : Автореф. дис. . канд. техн. наук : 05.13.12 // Владикавказ: 2000. 23 с.

22. Baiao F., Mattoso М. A Mixed Fragmentation Algorithm for Distributed Object Oriented Databases // The Ninth International Conference on Computing Information. Winnipeg, Canada. 1998. - pp. 141-148.

23. Navathe S., Karlapalem K., Ra M. A Mixed Fragmentation Methodology for Initial Distributed Database Design // Journal of Computer and Software Engineering. 1995. - Vol. 3, N4.

24. Navathe S., Ceri S., Weiderhold G., et al. Vertical Partitioning Algorithms for Database Design // ACM Transactions on Database Systems. 1984. - Vol. 9, N4. - pp. 680-710.

25. Ma H., Schewe K.-D., Wang Q. A heuristic approach to cost-efficient derived horizontal fragmentation of complex value databases // Eighteenth conference on Australasian database. Ballarat, Australia. — 2007. pp. 103-111.

26. Horizontal Class Partitioning for Queries in Object-Oriented Databases: / Hong Kong University of Science & Technology: Bellatreche L., Karlapalem K., Basak G.K. Hong Kong, 1998. - 27 p. - HKUST-CS98-6.

27. Ahmad I., Karlapalem K., Kwok Y.K., et al. Evolutionary Algorithms for Allocating Data in Distributed Database Systems // Distributed and Parallel Databases.-2002.-Vol. ll,Nl.-pp. 5-32.

28. Hababeh Ismail O., Ramachandran M., Bo wring N. A high-performance computing method for data allocation in distributed database systems //

29. Journal of Supercomputing. 2007. - Vol. 39, N1. - pp. 3-18. - ISSN 0920-8542.

30. Graham J.M. Theoretical properties of two problems of distribution of interrelated data // 44th annual Southeast regional conference. Melbourne, Florida. 2006. - pp. 395-398.

31. Ozsu Т., Valduriez P. Principles of Distributed Database Systems: 2nd Edition // Englewood Cliff, NJ: Prentice-Hall, 1999. 666 p.

32. Ziane M., Zait M., Hong H.Q. Parallelism and query optimization // International Journal of Computer Science and Engineering. 1995. -Vol. 10, Nl.-pp. 50-56.

33. Михайлов М.Ю. Моделирование размещения данных при проектировании распределенных баз данных : автореферат дис. . кандидата экономических наук : 08.00.13 // Москва: 1991. 18 с.

34. Новосельский В.Б. Решение задачи распределения реляционной базы данных // Журнал научных публикаций аспирантов и докторантов. -2008. -N5.-с. 158-160.-ISSN 1991-3087.

35. March S.T., Rho S. Allocating Data and Operations to Nodes in Distributed Database Design // IEEE Transactions on Knowledge and Data Engineering. 1995. - Vol. 7, N2. - pp. 305-317. - ISSN 10414347.

36. Johansson J.M., March S.T., Naumann J.D. Modeling Network Latency and Parallel Processing in Distributed Database Design // Decision Sciences Journal. 2003. - Vol. 34, N4. - pp. 677-706.

37. Tamhankar A.M., Ram S. Database fragmentation and allocation: an integrated methodology and case study // IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans. 1998. - Vol. 28, N3,-pp. 288-305.

38. Shah A., Ghosal D. Trade-offs between response times and availability in a distributed database // 4th workshop on ACM SIGOPS European workshop. Bologna, Italy. 1990. - pp. 1-4.

39. Cook J.H., Groner L.H. Analytic response time model for distributed systems // APL 90: for the future. Copenhagen, Denmark. 1990. - pp. 81-101.

40. Kossmann D. The state of the art in distributed query processing // ACM Computing Surveys. 2000. - Vol. 32, N4. - pp. 422-469. - ISSN 03600300.

41. Новосельский В.Б., Павловская Т.А. Выбор и обоснование критерия эффективности при проектировании распределенных баз данных // Научно-технический вестник СПбГУ ИТМО. 2008. - принято в печать.

42. Evrendilek С., Dogac A., Nural S., et al. Multidatabase .Query Optimization // Distributed and Parallel Databases. 1997. - Vol. 5, N1. -pp. 77-114.

43. Brunie L., Kosch H. Control strategies for complex relational query processing in shared nothing systems // SIGMOD Rec. 1996. - Vol. 25, N3. - pp. 34-39. - ISSN 0163-5808.

44. Hong W. Exploiting Inter-Operation Parallelism in XPRS // ACM SIGMOD International Conference on Management of Data. USA. -1992.-pp. 19-28.

45. Lanzelotte R.S.G., Valduriez P., Zait M. Industrial-Strength Parallel Query Optimization: Issues and Lessons // Information Systems. 1994. -Vol. 19, N4. - pp. 311-330. - ISSN 0306-4379.

46. Johansson J.M., March S.T., Naumann J.D. The effects of parallel processing on update response time in distributed database design // Twenty first international conference on Information systems. Brisbane, Queensland, Australia. -2000. pp. 187-196.

47. Bernstein P.A., Chiu D.-M.W. Using Semi-Joins to Solve Relational Queries // Journal of the ACM. 1981. - Vol. 28, N1. - pp. 25-40. -ISSN 0004-5411.

48. Ives Z.G., Florescu D., Friedman M., et al. An adaptive query execution system for data integration // ACM SIGMOD international conference on Management of data. Philadelphia, Pennsylvania. United States. 1999. -pp. 299-310.

49. Hammer M., Niamir B. A heuristic approach to attribute partitioning // ACM SIGMOD international conference on Management of data. Boston, Massachusetts. 1979. - pp. 93-101.

50. Bernstein P.A., Goodman N., Wong E., et al. Query processing in a system for distributed databases (SDD-1) // ACM Transactions on Database Systems. 1981. - Vol. 6, N4. - pp. 602-625. - ISSN 03625915.

51. Джонс Д.К. Методы проектирования: пер. с англ. 2-е изд., доп. // М.: 1986.-326 с.

52. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации // Информационные технологии. 1999. -№1. - с. 2-7. - ISSN 1994-0408.

53. Bennett К., Ferris М.С., Ioannidis Y.E. A Genetic Algorithm for Database Query Optimization // Fourth International Conference on Genetic Algorithms. San Mateo, CA. 1991. - pp. 400-407.

54. Corcoran A.L., Hale J. A genetic algorithm for fragment allocation in a distributed database system // ACM symposium on Applied computing. Phoenix, Arizona, United States. 1994 - pp. 247-250.

55. Rho S., March S.T. A nested genetic algorithm for distributed database design // Twenty-Seventh Hawaii International Conference on System Sciences, Information Systems: Decision Support and Knowledge-Based Systems. Wailea, HI, USA. 1994. - pp. 33-42.

56. Wang J.-C., Horng J.-Т., Hsu Y.-M., et al. A genetic algorithm for set query optimization in distributed database systems // IEEE International Conference on Systems, Man, and Cybernetics. 1996. - pp. 1977-1982.

57. Rho S., March S.T. Optimizing distributed join queries: A genetic algorithm approach // Annals of Operations Research. 1997. - Vol. 71, NO. - pp. 199-228.

58. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence // MIT Press, 1992. 228 p.

59. Whitley D. An Overview of Evolutionary Algorithms: Practical Issues and Common Pitfalls // Journal of Information and Software Technology. -2001.-Vol. 43, N4.-pp. 817-831.

60. Новосельский В.Б. Применение генетических алгоритмов при проектировании распределенных баз данных // Научно-технический вестник СПбГУ ИТМО. 2008. - Принято в печать.

61. Новосельский В.Б. Метод проектирования процесса распределения реляционной базы данных // Изв. вузов. Приборостроение. 2008. -Т. 51, №7.-с. 39-42.

62. Ceri S., Negri М., Pelagatti G. Horizontal data partitioning in database design // ACM SIGMOD international conference on Management of data. Orlando, Florida. 1982. - pp. 128-136.

63. Ma H., Schewe K.-D., Wang Q. A heuristic approach to cost-efficient fragmentation and allocation of complex value databases // 17th Australasian Database Conference. Hobart, Australia. 2006. - pp. 183192.

64. Transaction Processing Performance Council (TPC). TPC Benchmark™ -Standard Specification, Revision 5.9.// 2007. 130 p.

65. Новосельский В.Б. Метод автоматизации проектирования распределенной реляционной базы данных // Программные продукты и системы. 2008. - №3. - с. 45-48.