Geum.ru
Авторефераты по всем темам  >>  Авторефераты по техническим специальностям

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

ПЫХАЛОВ АЛЕКСАНДР ВЛАДИМИРОВИЧ

МЕТОДЫ И СРЕДСТВА ИНТЕГРАЦИИ НЕЗАВИСИМЫХ БАЗ ДАННЫХ В РАСПРЕДЕЛЕННЫХ СЕТЯХ TCP/IP

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

Ростов-на-Дону 2012 г.

Работа выполнена в Южно-Российском региональном центре информатизации Южного Федерального университета.

Научный консультант: Букатов Александр Алексеевич, кандидат технических наук, доцент, ЮжноРоссийский региональный центр информатизации Южного Федерального университета (г. Ростов-наДону), заместитель директора

Официальные оппоненты: Долгов Александр Иванович, доктор технических наук, профессор, ОАО "Конструкторское бюро по радиоконтролю систем управления, навигации и связи" (г. Ростов-на-Дону), старший научный сотрудник Левицкий Борис Ефимович, кандидат физико-математических наук, доцент, Кубанский Государственный университет (г.

Краснодар), проректор по информатизации

Ведущая организация: Федеральное государственное автономное учреждение Государственный научноисследовательский институт информационных технологий и телекоммуникаций Информика (г.

Москва)

Защита состоится л__ __________ 2012 г. в ____ часов на заседании диссертационного совета Д212.208.24 при Южном федеральном университете по адресу: 347928, г. Таганрог, Ростовская область, ул. Чехова, 2, корп. И, к.

347.

С диссертацией можно ознакомиться в зональной научной библиотеке ЮФУ по адресу: г. Ростов-на-Дону, ул. Пушкинская, 148 и на сайте разослан л__ __________ 2012 г.

Просим Вас прислать отзыв, заверенный печатью учреждения, по адресу:

347928, г. Таганрог, Ростовская область, ГСПА-17А, пер. Некрасовский, 44, Технологический институт Южного федерального университета в г. Таганроге, Ученому секретарю диссертационного совета Д 212.208.24 Кухаренко Анатолию Павловичу.

Ученый секретарь диссертационного совета А.П. Кухаренко кандидат технических наук, доцент

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

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

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

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

1) большое число источников данных;

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

3) высокая вероятность недоступности некоторого числа источников данных;

4) относительно высокая стоимость доступа к источникам данных;

5) контроль над источниками данных осуществляется различными группами администраторов, но при этом существует возможность согласованного администрирования источников данных;

6) отсутствие необходимости (а зачастую и возможности) изменять данные в подсоединенных источниках данных.

Методы обработки и уменьшения времени выполнения запросов к совокупности источников данных в распределенной сети описываются в работах O.Duschka, A.Halevy, A.Motro и других авторов. Однако, им свойственен ряд недостатков, не позволяющий быстро получать релевантные ответы на запросы при интеграции данных в распределенных корпоративных и межкорпоративных сетях, в частности, ориентация на интеграцию нереляционных данных.

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

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

Объектом исследований являются методы и средства интеграции данных в распределенных сетях TCP/IP.

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

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

Частные научные задачи диссертационного исследования:

1) анализ существующих методов и средств интеграции данных;

2) расширение логического языка запросов Datalog1 для его применения в области интеграции данных;

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

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

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

6) выполнение оценки эффективности разработанных методов.

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

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

Наиболее существенные научные положения, выдвигаемые для защиты:

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

2) Сокращение времени выполнения запроса к совокупности реляционных источников данных в распределенной сети достижимо на основе отслеживания зависимостей между операциями извлечения информации из различных Datalog Ч наиболее известный логический язык запросов, является подмножеством логического языка программирования Prolog.

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

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

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

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

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

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

Практическая ценность работы. Разработанный алгоритм трансляции Datalog-подобных программ в язык реляционной алгебры и реляционного исчисления позволяет обрабатывать рекурсивные запросы без постоянного контроля со стороны системы интеграции данных при помощи программы на процедурном языке СУБД. Разработанные методы и средства позволяют сократить время получения ответа на запрос пользователя в условиях возможной недоступности части источников данных в зависимости от характера обрабатываемых запросов на 20%-50%, в 3-4 раза сократить затраты времени прикладных программистов на модернизацию корпоративных информационных систем при добавлении новых источников данных.

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

Апробация результатов работы. Результаты работы докладывались и обсуждались на всероссийских и международных научно-техничесикх конференциях: на XIV-XVIII всероссийской научно-методической конференции Телематика (2007-11, г. С.-Петербург), на XIV-XVI конференции представителей региональных научно-образовательных сетей Relarn (200709, г. Нижний Новгород), на международной конференции Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT+SE (200810, г. Гурзуф), международной научно-технической конференции МВУС (2009, с. Дивноморское).

Основные научные результаты диссертации опубликованы в научных изданиях, в составе которых 2 статьи в журналах, рекомендованных ВАК для публикации результатов диссертаций [1][2] общим объемом 18 с.

(авторские 66%), 2 свидетельства об официальной регистрации программы для ЭВМ [3][4], 8 тезисов в сборниках тезисов международных и всероссийских конференций [5-12] общим объемом 18 с. (авторские 94%), 2 отчета по НИР общим объемом 231 с. (авторские 12%) [13,14].

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

- в технической документации интегрирующего информационного комплекса в Южно-Российском региональном центре информатизации Южного федерального университета (акт внедрения);

- в технической документации каталога электронных образовательных ресурсов в Тамбовском государственном техническом университете (акт внедрения), а также использованы - в отчете по НИР Разработка методов, технологий и программных средств построения распределенной инфраструктуры образовательных и научных информационных ресурсов университета федерального уровня (20092010 г., № гос. регистрации 01.2009.56224);

- в отчете по НИР Разработка и программная реализация проекта развития прототипных версий программных средств построения распределенной инфраструктуры образовательных и научных информационных ресурсов университета федерального уровня (2011, № гос. регистрации 01.2011.56016).

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

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников и четырёх приложений. Работа содержит 152 страницы основного текста, рисунков, 7 таблиц, список используемой литературы из 75 источников, страниц приложений.

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

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

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

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

Глава начинается с обзора трех основных подходов к заданию отображений между глобальной схемой и совокупностью локальных схем: GAV (Global As View), LAV (Local As View) и GLAV (Global Local As View). Алгоритмы обработки запросов при использовании подходов LAV и GLAV значительно усложняются по сравнению с применяемыми при использовании подхода GAV, поэтому в коммерческих средствах интеграции данных, как правило, используется подход GAV. Далее рассматриваются модели данных (МД) и языки запросов (ЯЗ), используемые в области интеграции данных.

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

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

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

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

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

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

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

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

Во второй главе описываются предлагаемые методы обработки и сокращения времени выполнения запросов в распределенной сети.

Описываемые методы разбиваются на две группы:

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

2) методы обработки запросов, позволяющие проводить параллельное извлечение информации из множества ИД и обрабатывать сбои, возникающие при обращении к ИД.

Первый метод тесно связан с используемой МД и ЯЗ. Предполагается, что схема и данные представляются системой предикатов и правил расширенной версии языка Datalog (DISGO QL), используемой также в качестве ЯЗ.

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

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

Рассмотрим пример на рис. 1. Пусть программа выбирает данные о лекциях, используя ПИА Lection из ПИ studdb с аргументами course, group, lector. Пусть изначально известно два типа ИД. Первый предоставляет информацию о названии предмета, номере курса и группы и имени лектора, а второй - о номере курса, группы, идентификаторе читаемого предмета, имени лектора. Тогда в глобальной схеме возможно описать два ПИА Lection в ПИ studdb и множество отображений каждого из этих ПИА на SQL запрос к известным ИД. При этом программа получит доступ к данным ИД обоих типов. Если в дальнейшем появится еще два типа ИД (предоставляющие информацию только о требуемых параметрах и имеющие дополнительные сведения), то определив два дополнительных ПИА Lection в ПИ studdb и составив необходимые SQL запросы к ИД, новую информацию можно сделать доступной для приложения без его изменения.

Описанный метод определения используемых в запросе ИД не имеет прямых аналогов.

Далее рассматриваются предлагаемые методы обработки запросов.

Метод непосредственного выполнения запросов позволяет получить ответ на запрос, представленный в виде выражения РА и программ РИ, Рис. 1: Использование ПИА распараллеливая операции извлечения информации из ИД и исключая из рассмотрения медленные и недоступные ИД. Этот метод предполагает непосредственный обход дерева операций выражения РА или программы РИ, извлечение информации из ИД и окончательную обработку запроса средствами центральной СУБД. После выявления недоступности некоторого ИД D возможно продолжить выполнение запроса, если отношение R, отображаемое на запрос к ИД D, также отображается на запрос к доступному ИД, или когда обращение к отношению R происходит в операции UNION, второй аргумент которой можно вычислить без обращения к ИД D.

В запросе возможно указать максимально допустимое время ожидания ответа ИД в миллисекундах. Если ожидаемое время извлечения информации больше указанного, ИД не будет опрошен. При этом время извлечения E( s(P, D),Q)S (Q) + L(D) информации из ИД может быть оценено как, где V (D) V(D) - пропускная способность канала до ИД D, L(D) - задержка канала, S(Q) - селективность запроса, s(P,D) Ч размер данных представления, соответствующих предикату P в ИД D, E(s,Q) - оценка размера представления Q, учитывающая операции проекции и добавления. Считается, что проекция s(R)s( Ai) Ai атрибутов сохраняет часть информации объемом, а операция s(A(R)) добавления атрибута A добавляет к ответу порцию размером s(A)*c(R), где c(R) - количество строк в отношении R, A(R)- множество атрибутов отношения R, s(R) Ч размер отношения R.

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

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

Исполнение запросов выполняется в несколько шагов: 1) составление плана доступа к данным (ПДД); 2) оптимизация ПДД; 3) создание плана выполнения запроса на основе ПДД; 4) выполнение запроса согласно плану.

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

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

При обработке дерева операций выражения РА к одной ГО относятся операции выборки информации из отношений различных ИД, соответствующих одному отношению в запросе, и операции выборки информации из отношений, связанных операцией UNION. Обработка дерева операций выражения РА осуществляется сверху вниз, слева направо. По умолчанию для корня дерева создается текущая ГО. Если очередная рассматриваемая вершина дерева соответствует отношению РА, то к текущей ГО добавляются операции по извлечению или преобразованию данных. Если очередная рассматриваемая вершина дерева соответствует операцииям JOIN или MINUS, то происходит генерация двух новых ГО, текущая ГО помечается как зависимая от данных ГО, и новые ГО становятся текущими для всех вершин левого и правого поддерева обрабатываемой вершины соответственно. Если очередная рассматриваемая вершина дерева соответствует операции UNION, то текущая ГО остается прежней и происходит обработка поддеревьев рассматриваемой вершины.

Для ГО вводится специальный атрибут - показатель устойчивости к сбоям (ПУ). Он определяет количество сбоев при выполнении операций группы, допустимое для получения неполного ответа на запрос. ПУ определяется при построении ГО. При создании ГО ее ПУ полагается равным 0. Если очередная рассматриваемая вершина дерева соответствует операции обращения к отношению, которое отображается на n запросов к ИД, к ПУ текущей ГО добавляется значение n-1. При обработке вершин дерева, соответствующих операциям UNION, ПУ текущей ГО увеличивается на единицу.

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

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

Предложенный метод выполнения запросов не имеет аналогов.

В третьей главе описываются предлагаемые алгоритмы обработки запросов, которые представляются программами на расширении ЯЗ Datalog - DISGO QL.

Для представления программы на DISGO QL используется модифицированный граф взаимосвязанности выражений (MCIG), отражающий связь между правилами программы. Использование расширенного определения графа MCIG и модифицированной процедуры унификации дает возможность унифицировать предикаты вне зависимости от результатов процедуры проверки на вхождение и потенциально обрабатывать большее количество запросов (за счет использования множества Q). Граф MCIG представляет собой пятерку (N,E,S,R,Q), где N - вершины графа (соответствуют предикатам программы), E - его дуги (соединяют вершины, соответствующие предикатам, если один предикат можно выразить через другой), S - подстановки, которые необходимо выполнить для перехода по дуге, R - правила (разбиение множества вершин на подмножества в соответствии с принадлежностью правилам программы), Q - дополнительные условия, при которых переход по дуге возможен.

Модифицированный алгоритм унификации предикатов применяется для построения графа MCIG. Он принимает на вход два предиката, которые нужно унифицировать, и определяет возможность унификации. Он также генерирует множество подстановок S и множество условий Q, при которых унификация возможна. Блок-схема данного алгоритма приведена на Рис.2.

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

Основная особенность алгоритма - получение множества Q, в которое добавляются условия на равенство аргументов для пар (функция, функция) и (функция, переменная), если переменная входит в состав аргументов функции.

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

Рис.2: Алгоритм унификации предикатов Пример графа MCIG приведен на рис. 3. Граф состоит из 6 вершин.

Вершины, соответствующие предикатам одного правила, изображены совместно. Вершины, соответствующие предикатам grandparent, соединены дугой, т.к. вместо данного предиката можно подставить его определение. Дуга помечена множествами подстановок S и условий Q, при которых это возможно.

Алгоритм обработки рекурсивных программ принимает на вход 1) граф MCIG, содержащий цикл; 2) цикл, который нужно обработать, а на выходе получает программу РИ, которая явно создает в БД отношение, соответствующее рекурсивно определенному предикату.

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

1) Начать обработку группы циклов, из которой не существует пути к другим группам циклов.

2) Разорвать каждый цикл L группы путем удаления дуги, выходящей из последнего выхода цикла L и принадлежащей циклу L. Если из цикла L нет выхода (что возможно в случае существования циклов-близнецов), исключить его из рассмотрения путем удаления первой дуги цикла L. По полученному Рис. 3: Пример фрагмента графа MCIG нециклическому участку графа построить выражение инициализации.

Рис. 4: Простой цикл на графе MCIG Рис. 6: Группа циклов Рис. 5: Циклы-близнецы 3) Вернуться к начальному состоянию графа. Заменить дуги, ведущие обратно в цикл, на дуги, ведущие к обрабатываемому предикату. По полученному нециклическому участку графа построить выражение перехода.

4) На основе выражений инициализации и перехода составить программу РИ для получения ответа на подзапрос на DISGO QL, соответствующий обрабатываемому циклу графа [Рис.7].

Выражения РА и РИ, получаемые в результате работы данного алгоритма, переводятся в SQL-запросы и программы на процедурном языке СУБД.

Рассмотренный способ обработки Datalog-запросов ближе всего к алгоритмам компиляции программ, предложенным Henschen и Naqvi.

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

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

_A1=INIT_EXPRESSION;

PRED=_A1 where false;

i=0;

while(i++

_A1=STEP_EXPRESSION UNION PRED;

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

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

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

Предложенные методы и алгоритмы реализованы в СИД DISGO. СИД DISGO состоит из четырех подсистем: подсистемы обработки запросов, подсистемы сбора статистики, подсистемы управления и подсистемы доступа к метаданным. Общая структура СИД DISGO и взаимодействие ее модулей отражены на рис. 8. Взаимодействие между модулями отмечено тонкими стрелками, взаимодействие с прикладными программами - толстыми закрашенными стрелками, обращение к данным - толстыми незакрашенными стрелками. Модули подсистемы обработки запросов выделены двойной рамкой, подсистемы сбора статистики - темно-серым, подсистемы управления - белым, подсистемы доступа к метаданным - светло-серым цветом. ИД и центральная БД представлены овалами.

Подсистема обработки запросов взаимодействует с прикладными программами посредством Web-сервиса QS, обрабатывающего их запросы.

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

Рис. 8. Взаимодействие модулей СИД DISGO Сравнение производительности работы СИД DISGO в локальной сети с аналогичной системой, построенной на базе средств Oracle, показало, что при размере ответов до нескольких тысяч записей СИД DISGO имеет сопоставимое быстродействие с СУБД Oracle или в некоторых ситуациях даже превосходит ее на 10-15% при использовании метода непосредственного выполнения запросов и на 20-30% при использовании оптимизированного метода выполнения запросов.

При тестировании работы в СИД DISGO распределенной сети в условиях недоступности некоторых ИД ее производительность оказалась в среднем в раз выше, чем у средств Oracle [Рис. 9].

При недоступности некоторых ИД СИД DISGO не может обработать 100% запросов только при одновременной недоступности 75% ИД и 21-28% запросов при недоступности одиночных ИД. СУБД Oracle не может обработать 100% запросов даже при отсутствии всего одного ИД.

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

Рис. 9. Производительность СИД DISGO в распределенной сети В заключении изложены выводы по основным результатам диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ Основной научный результат работы заключается в решении актуальной научной задачи: разработке методов, обеспечивающих минимизацию времени получения релевантного ответа на запрос к совокупности реляционных источников данных в распределенной сети TCP/IP.

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

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

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

3) расширение языка Datalog (DISGO QL) для описания семантической информации в глобальной схеме данных и составления запросов к ней путем введения предикатов с именованными аргументами;

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Пыхалов А.В., Букатов А.А. Концепции построения и основные алгоритмы системы интеграции данных DISGO //Вестник компьютерных и информационных технологий, №10, Москва, 2010, С. 49-2. Букатов А.А., Пыхалов А.В. Обработка и оптимизация запросов в системе интеграции данных DISGO //Информатизация образования и науки, №1(9), Москва, 2011, С. 22-3. Пыхалов А.В. Свидетельство о государственной регистрации программ для ЭВМ № 2010610407 Система интеграции данных DISGO, основанная на логике предикатов, версия 0.1 (DISGO v. 0.1) // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 204. Пыхалов А.В. Свидетельство о государственной регистрации программ для ЭВМ № 2010610573 Подсистема компиляции запросов системы интеграции данных DISGO, версия 0.1 (DISGO Compiler v. 0.1) // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 205. Букатов А.А., Пыхалов А.В. Интеграция множества БД с использованием глобальной онтологии //Приложение к журналу Открытое образование:

Материалы XXXV Международной конференции Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT + S&E'08,Украина, Крым, Гурзуф, 2008, С. 133-16. Пыхалов А.В. Назначение и основные возможности системы интеграции данных DISGO //Приложение к журналу Открытое образование: Материалы XXXVI Международной конференции Информационные технологии в науке, социологии, экономике и бизнесе IT + S&E'09. Осенняя сессия. Украина, Крым, Ялта-Гурзуф, 2009, С. 23-7. Пыхалов А.В. Задача интеграции данных в глобальной телекоммуникационной сети //Приложение к журналу Открытое образование:

Материалы XXXVII Международной конференции Информационные технологии в науке, социологии, экономике и бизнесе, Украина, Крым, ЯлтаГурзуф, 2010, С. 180-18. Пыхалов А.В. Обнаружение и обработка рекурсии в запросах в системе интеграции данных DISGO//Материалы XV всероссийской научнометодической конференция Телематика- 2008, Санкт-Петербург, 2008, С. 84-9. Пыхалов А.В. Расширения Datalog'а, использующиеся в системе интеграции данных DISGO //Материалы XVI всероссийской научно-методической конференции Телематика-2009, Санкт-Петербург, 2009, С. 162-110. Пыхалов А.В. Обработка запросов в системе интеграции данных DISGO //Материалы XVII всероссийской научно-методической конференции Телематика-2010, Санкт-Петербург, 2010, С. 289-211. Пыхалов А.В. Особенности языка запросов системы интеграции данных DISGO //Шестнадцатая конференция представителей региональных научнообразовательных сетей "RELARN-2009", сборник тезисов докладов, Москва - Санкт-Петербург, 2009, С.150-112. Пыхалов А.В. Обзор системы интеграции данных DISGO //Материалы международной научно-технической конференции МВУС-2009, Издательство технологического института ЮФУ, Таганрог, 2009, С.73-13. Букатов А.А., Лазарева С.А., Муратова Г.В., Пыхалов А.В. и др.

Заключительный отчет по проекту № 5278 Разработка методов, технологий и программных средств построения распределенной инфраструктуры образовательных и научных информационных ресурсов университета федерального уровня, № гос. регистрации НИР 01.2009.56224 // Южный Федеральный Университет, 2010 г.

14. Букатов А.А., Лазарева С.А., Муратова Г.В., Пыхалов А.В. и др.

Заключительный отчет по НИР Разработка и программная реализация проекта развития прототипных версий программных средств построения распределенной инфраструктуры образовательных и научных информационных ресурсов университета федерального уровня. Опытная эксплуатация разработанных средств, № гос. регистрации НИР 01.2011.56016 // Южный Федеральный Университет, 2012 г.

В совместных работах автором получены следующие результаты: в [1] разработаны основные принципы построения СИД, основанной на использовании специального логического языка, ориентированного на решение задач интеграции данных, в [2] предложены методы оптимизации запросов к распределенной совокупности ИД и методы обработки запросов в условиях временной недоступности отдельных ИД, в [5] сформированы основные требования к СИД, предназначенным для интеграции данных в ГТС и использующим онтологии, в [13] предложены алгоритмы перевода запросов, выраженных на Datalog-подобном языке, в выражения реляционной алгебры, в [14] приведены результаты тестирования системы интеграции данных DISGO.

Авторефераты по всем темам  >>  Авторефераты по техническим специальностям