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

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

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

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

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

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

2 5 ОКТ 2012

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

005053787

005053787

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

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

Официальные оппоненты: Долгов Александр Иванович,

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

Левицкий Борис Ефимович,

кандидат физико-математических наук, доцент, Кубанский Государственный университет (г. Краснодар), проректор по информатизации

Ведущая организация: Федеральное государственное автономное

учреждение «Государственный научно-

исследовательский институт информационных технологий и телекоммуникаций» «Информика» (г. Москва)

Защита состоится «/£}> 2012 г. в /V" часов на заседании

диссертационного совета Д212.208 24 при Южном федеральном университете по адресу: 347928, г. Таганрог, Ростовская область, ул. Чехова, 2, корп. «И», к. 347.

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

Автореферат разослан 2012 г.

"7"'

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Объектом исследований являются методы и средства интеграции данных в распределенных сетях ТСРЛР.

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

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

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

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

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

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

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

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

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

Методы исследования. При проведении исследований были использованы

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

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

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

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

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

Datalog — наиболее известный логический язык запросов, является подмножеством логического языка программирования Prolog.

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

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

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

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

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

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

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

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

конференциях: на Х1У-ХУШ всероссийской научно-методической конференции «Телематика» (2007-11, г. С.-Петербург), на Х1У-ХУ1 конференции представителей региональных научно-образовательных сетей «Ие1агп» (200709, г. Нижний Новгород), на международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе ГГ+БЕ» (200810, г. Гурзуф), международной научно-технической конференции МВУС (2009, с. Дивноморское).

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

научных изданиях, в составе которых 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 страницы основного текста, 38 рисунков, 7 таблиц, список используемой литературы из 75 источников, 17 страниц приложений.

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

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

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

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

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

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

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

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

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

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

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

поддерживают обработку рекурсивных запросов.

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

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

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

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

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

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

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

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

Обращение

studdb:Lectfon{course,group, lector} <?c.?g,?l)

H

studdb. Lection {title, course, group, lector}

(?t?c,?g,?l)

Известные внедрения программь предикаты

studdb:Lection{course,group.lecUd .lector} (?c,?g,?id,?I)

на момен

stutkJb.LecHonfcourse, group, lector} <?c,?g,?l)

Добавленные

позже

предикаты

studdb:Lerfron{t]tie.coufs«,sroup,hour5jector} (?t,?o,?g,?h,?l)

Рис. 1: Использование ПИА

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

Описанный метод

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

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

Метод непосредственного выполнения запросов позволяет получить ответ на запрос, представленный в виде выражения РА и программ РИ, распараллеливая операции

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

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

. тттт _ E(s{P,D).Q)*S(Q) информации из ИД может быть оценено как -V(D)-+L\D) , где

V{D) - пропускная способность канала до ИД D, L(D) - задержка канала, S{Q) -селективность запроса, s(PJ3) — размер данных представления, соответствующих предикату Р в ИД D, E(s,Q) - оценка размера представления Q, учитывающая операции проекции и добавления. Считается, что проекция

атрибутов Ai сохраняет часть информации объемом

а операция

добавления атрибута А добавляет к ответу порцию размером 5(Л)*с(Л), где с(К) - количество строк в отношении Я, А(Л)- множество атрибутов отношения Л, — размер отношения Я.

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

запроса к ИД.

Для оптимизации путей доступа к данным предлагается использовать оптимизированный метод, построенный на базе концепции ГО. Данный метод позволяет гибко обрабатывать сбои при обращениям к ИД и выполнять контролируемую параллельную обработку операций извлечения информации. Исполнение запросов выполняется в несколько шагов: 1) составление плана доступа к данным (ПДД); 2) оптимизация ПДД; 3) создание плана выполнения запроса на основе ПДД; 4) выполнение запроса согласно плану.

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

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

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

операциям UNION, ПУ текущей ГО увеличивается на единицу.

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

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

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

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

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

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

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

Рис.2: Алгоритм унификации предикатов

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

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

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

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

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

его из рассмотрения путем удаления первой дуги цикла Ь. По полученному

гипйте:дгапсфагеп1:(?а,?Ь) сотрргес^ед^Ь, "Василий Иванов")

5={(7у_2,?Ь_1%),(?Ь_1,7Ь_1%), (?х_2,?а_1%),(а_1,7а_1%)}, 0=

гипУте:дгапс)рагеп1:{?х,?у) рагепЦ?х,?г) рагеп1(?г,?у)

Рис. 3: Пример фрагмента графа МСЮ нециклическому участку графа построить выражение инициализации.

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

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

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

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

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

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

_Al=INIT_EXPRESSION;

PRED=_A1 where false;

i=0;

while(i++<mln && _A1 MINUS PRED IS NOT NULL){ PRED=_A1;

_Al=STEP_EXPRESSION UNION PRED;

}

Рис. 7. Программа, соответствующая циклической конструкции на графе

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

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

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

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

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

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

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

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

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

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

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

Производительность, ответов в секунду

0,3 0,25 02 0,15 0,1 0,05 0

DISGO, оптимизированный метод выполнения DISGO, метод непосредственного выполнения Oracle

Рис. 9. Производительность СИД DISGO в распределенной сети

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

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

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

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

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

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

// //

// //

// Г/

// //

1 / /1

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Пыхалов A.B., Букатов A.A. Концепции построения и основные алгоритмы системы интеграции данных DISGO //Вестник компьютерных и информационных технологий, №10, Москва, 2010, С. 49-55

2. Букатов A.A., Пыхалов A.B. Обработка и оптимизация запросов в системе интеграции данных DISGO //Информатизация образования и науки, №1(9), Москва, 2011, С. 22-34

3. Пыхалов A.B. Свидетельство о государственной регистрации программ для ЭВМ № 2010610407 «Система интеграции данных DISGO, основанная на логике предикатов, версия 0.1 (DISGO v. 0.1)» // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 2010

4. Пыхалов A.B. Свидетельство о государственной регистрации программ для ЭВМ № 2010610573 «Подсистема компиляции запросов системы интеграции данных DISGO, версия 0.1 (DISGO Compiler v. 0.1)» // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 2011

5. Букатов A.A., Пыхалов A.B. Интеграция множества БД с использованием глобальной онтологии //Приложение к журналу «Открытое образование»: Материалы XXXV Международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT + S&E'08»,Украина, Крым, Гурзуф, 2008, С. 133-135

6. Пыхалов A.B. Назначение и основные возможности системы интеграции данных DISGO //Приложение к журналу «Открытое образование»: Материалы XXXVI Международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе IT + S&E'09». Осенняя сессия. Украина, Крым, Ялта-Гурзуф, 2009, С. 23-24

7. Пыхалов A.B. Задача интеграции данных в глобальной телекоммуникационной сети //Приложение к журналу «Открытое образование»: Материалы XXXVII Международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе, Украина, Крым, Ялта-Гурзуф, 2010, С. 180-181

8. Пыхалов A.B. Обнаружение и обработка рекурсии в запросах в системе

интеграции данных DISGOZ/Материалы XV всероссийской научно-методической конференция Телематика- 2008, Санкт-Петербург, 2008, С. 84-85

9. Пыхалов A.B. Расширения Datalog'a, использующиеся в системе интеграции данных DISGO //Материалы XVI всероссийской научно-методической конференции Телематика-2009, Санкт-Петербург, 2009, С. 162-163

10. Пыхалов A.B. Обработка запросов в системе интеграции данных DISGO //Материалы XVII всероссийской научно-методической конференции Телематика-2010, Санкт-Петербург, 2010, С. 289-290

11. Пыхалов A.B. Особенности языка запросов системы интеграции данных DISGO //Шестнадцатая конференция представителей региональных научно-образовательных сетей "RELARN-2009", сборник тезисов докладов, Москва -Санкт-Петербург, 2009, С.150-152

12. Пыхалов A.B. Обзор системы интеграции данных DISGO //Материалы международной научно-технической конференции МВУС-2009, Издательство технологического института ЮФУ, Таганрог, 2009, С.73-76

13. Букатов A.A., Лазарева С.А., Муратова Г.В., Пыхалов A.B. и др. Заключительный отчет по проекту № 5278 «Разработка методов, технологий и программных средств построения распределенной инфраструктуры образовательных и научных информационных ресурсов университета федерального уровня», № гос. регистрации НИР 01.2009.56224 // Южный Федеральный Университет, 2010 г.

14. Букатов A.A., Лазарева С.А., Муратова Г.В., Пыхалов A.B. и др. Заключительный отчет по НИР «Разработка и программная реализация проекта развития прототипных версий программных средств построения распределенной инфраструктуры образовательных и научных информационных ресурсов университета федерального уровня. Опытная эксплуатация разработанных средств», № гос. регистрации НИР 01.2011.56016 // Южный Федеральный Университет, 2012 г.

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

Подписано в печать 3.10.12 Формат 60x84 7«. Бумага офсетная. Печать офсетная. Усл.печ.л.1,0. Уч.-издл. 1,0. Тираж 110. Заказ № 2514.

Отпечатано в типографии ЮФУ. 344090, г. Ростов-на-Дону, пр. Стачки, 200/1. Тел. 247-80-51

ВВЕДЕНИЕ.

1. ЗАДАЧА ИНТЕГРАЦИИ ДАННЫХ И ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ИНТЕГРАЦИИ ДАННЫХ.

1.1. Различные подходы к интеграции данных: GAV, LAV, GLAV.

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

1.3. Методы обработки и оптимизации запросов в СИД.

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

1.3.2. Методы обработки и оптимизации запросов в распределенных СУБД

1.3.3. Методы борьбы с устаревшей статистикой в СИД.

1.3.4. Методы обработки запросов в Oracle Heterogeneous Services.

1.3.5. Методы обработки и оптимизации запросов в СИД SIMS.

1.3.6. Методы обработки запросов в СИД TSEMMIS.

1.3.7. Методы обработки и оптимизации запросов в СИД Information

Manifold.

1.3.8 . Методы обработки запросов в Р2Р СИД.

1.4. Методы работы с неполными и противоречивыми данными.

1.4.1. Формальная модель для интеграции данных Multiplex.

1.4.2. Методы разрешения противоречий в СИД Fusionplex.

1.5. Постановка общей научной задачи и частные задачи исследования.

1.6. Выводы по главе 1.

2. МЕТОДЫ ОБРАБОТКИ И ОПТИМИЗАЦИИ ЗАПРОСОВ В РАСПРЕДЕЛЕННОЙ СЕТИ.

2.1. Краткое описание предлагаемых методов и реализующих их средств.

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

2.2.1. Используемая модель данных.

2.2.2. Подход к построению отображений между глобальной схемой и локальными схемами.

2.3. Методы обработки и оптимизации запросов.

2.3.1. Общий алгоритм выполнения запросов.

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

2.3.3. Оптимизированный метод выполнения запросов.

2.4. Выводы по главе 2.

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

3.1. Построение графа взаимосвязанности выражений.

3.1.1. Алгоритм унификации предикатов в СИД DISGO.

3.2. Алгоритмы генерации выражений РА.

3.2.1. Алгоритм генерации выражений РА для нерекурсивных программ.

3.2.2. Алгоритм генерации выражений РА для рекурсивных программ.

3.3. Алгоритм генерации SQL по выражениям РА.

3.4. Алгоритмы оптимизации запросов.

3.4.1. Алгоритм оптимизации запросов на основе правил.

3.4.2. Алгоритмы сбора и обработки статистики.

3.5. Корректность предлагаемых алгоритмов.

3.6. Выводы по главе 3.

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

4.1. Общее описание СИД DISGO.

4.1.1. Архитектура СИД DISGO.

4.1.2. Схема взаимодействия прикладных программ с СИД DISGO.

4.2. Экспериментальный анализ производительности работы СИД DISGO, реализующей предложенные алгоритмы и методы.

4.2.1. Анализ производительности СИД DISGO в локальной сети.

4.2.2. Анализ производительности СИД DISGO в распределенной сети.

4.2.3. Результаты анализа работы представленных средств.

4.3. Практическое использование предложенных методов и средств.

4.4. Выводы по главе 4.

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

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

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

Актуальность применения систем интеграции данных для объединения информации множества источников данных в глобальной сети определяется ростом количества информации в Интернете. Основную часть этой информации составляют данные глубинного web'a [1]. Он представляет из себя данные, получаемые из различных баз данных, доступных в Интернете посредством Web-форм. Подобная информация недостаточно эффективно индексируется поисковыми системами [2]. В 2001 году объем Deep Web оценивался в 7,500 терабайт [1], в 2003 - уже в 91,850 терабайт [3]. Задача поиска нужных данных в таком объеме информации представляет значительную сложность. Одним из способов ее решения является использование систем интеграции данных [4]. При этом источники, отражающие данные одной предметной области, подключаются к системе интеграции данных посредством медиаторов (специальных программных модулей для доступа к источникам данных). Задача интеграции данных упрощается, если система обращается непосредственно к СУБД. В этом случае система интеграции данных взаимодействует с распространенными реляционными СУБД (количество которых составляет около десятка - IBM DB2 [5], Ingres [6], Microsoft SQL Server [7], MySQL [8], Oracle DBMS [9], PostgreSQL [10], Sybase Adaptive Server [11] и др.), и для взаимодействия использует SQL.

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

Современные коммерческие средства интеграции данных обычно нацелены на решение второй задачи. Помимо средств интеграции данных для достижения сходных целей используются средства интеграции приложений (в частности, сервисные шины ESB (enterprise service bus), например, OpenESB [12] или Apache ServiceMix [13]), позволяющие унифицировать форматы сообщений, которыми обмениваются приложения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация результатов работы. Результаты работы докладывались и обсуждались на всероссийских и международных научно-техничесикх конференциях: на Х1У-ХУШ всероссийской научно-методической конференции «Телематика» (2007-11, г. С.-Петербург), на Х1У-ХУ1 конференции представителей региональных научно-образовательных сетей «Яект» (200709, г. Нижний Новгород), на международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе 1Т+8Е» (200810, г Гурзуф), международной научно-технической конференции МВУС (2009, с. Дивноморское).

Основные научные результаты диссертации опубликованы в 14 научных изданиях, в составе которых 2 статьи в журналах, рекомендованных ВАК для публикации результатов диссертаций [17][18] общим объемом 18 с. (авторские 66%), 2 свидетельства об официальной регистрации программы для ЭВМ [19],[20] и 8 тезисов в сборниках тезисов международных и всероссийских конференций [21] [22] [4] [23] [24] [25] [26] [27] общим объемом 18 с. (авторские 94%), 2 отчета по НИР [28] [29] общим объемом 231 с. (авторские 12%).

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

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

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

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

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

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

4.4. Выводы по главе 4

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

Указанные результаты опубликованы в журналах, рекомендованных ВАК для публикации результатов диссертаций [17] [18] и в сборниках тезисов международных и всероссийских конференций [21 ][22] [4] [23] [24] [25] [26] [27]. При этом, в работах, выполненных в соавторстве, автору принадлежат следующие результаты:

В [17] разработаны основные принципы построения СИД, основанной на использовании специального логического языка, ориентированного на решение задач интеграции данных.

В [18] предложены методы оптимизации запросов к распределенной совокупности ИД и методы обработки запросов в условиях временной недоступности отдельных ИД.

В [21] сформированы основные требования к СИД, предназначенным для интеграции данных в ГТС и использующим онтологии.

1. Bergman M.K. The Deep Web: Surfacing Hidden Value //The Journal of Electronic Publishing, Volume 7, 1.sue 1, 2001, http://dx.doi.org/10.3998/3336451.0007.104

2. Madhavan J., Ко D., Kot L. et. al. Google's Deep Web Crawl //Proceedings of the VLDB Endowment, Volume 1, Issue 2, 2008, C. 1241-1252

3. Lyman P., Varian H.T. How Much Information? // http://www.sims.berkeley.edu/how-much-info-2003, 2003

4. IBM DB2 Software // http://www-01.ibm.com/software/data/db2/, 2011

5. Ingres Database: Open Source Database Ingres: //http://www.ingres.com/products/ingres-database.php, 2011

6. Microsoft SQL Server 2008 R2 | Database Management System // http://www.microsoft.com/sqlserver/en/us/default.aspx, 2011

7. MySQL :: The world's most popular open source database: // http://www.mysql.com/, 2011

8. Oracle Database // http://www.oracle.com/us/products/database/index.html, 2011

9. PostgreSQL: The world's most advanced open source database // http://www.postgresql.org/, 2011

10. Adaptive Server Enterprise Relational Database Management System (RDBMS) Software Solution Sybase Inc: //http://www. sybase.com/products/databasemanagement/adaptiveserverenteфrise, 2011

11. OpenESB, The Open Source ESB for SOA & Integration // https://openesb.dev.java.net/, 2010

12. Apache ServiceMix, the Agile Open Source ESB ~ Home: // http://servicemix.apache.org/home.html, 2011

13. Duschka O.M., Genesereth M.R., Levy A.Y. Recursive Query Plans for Data Integration//Journal of Logic Programming, Volume 43, Issue 1, 2000, C.49-73

14. Levy A.Y. The Information Manifold Approach to Data Integration //IEEE Intelligent Systems, Volume 13, Number 5, 1998, C. 12-16

15. Motro A., Multiplex: A formal model for multidatabases and its implem entation // Technical Report ISSE-TR-95-103, Department of Information and Software Engineering, George Mason University, 1999

16. Пыхалов A.B., Букатов A.A. Концепции построения и основные алгоритмы системы интеграции данных DISGO //Вестник компьютерных и информационных технологий, NolO, Москва, 2010, С. 49-55

17. Букатов А.А., Пыхалов А.В. Обработка и оптимизация запросов в системе интеграции данных DISGO //Информатизация образования и науки, No 1(9), Москва, 2011, С. 22-34

18. Пыхалов A.B. Обнаружение и обработка рекурсии в запросах в системе интеграции данных DISGO //Материалы XV всероссийской научно-методической конференция Телематика- 2008, Санкт-Петербург, 2008, С. 84-85

19. Пыхалов A.B. Расширения Datalog'a, использующиеся в системе интеграции данных DISGO //Материалы XVI всероссийской научно-методической конференции Телематика-2009, Санкт-Петербург, 2009, С. 162-163

20. Пыхалов A.B. Обработка запросов в системе интеграции данных DISGO //Материалы XVII всероссийской научно-методической конференции Телематика-2010, Санкт-Петербург, 2010, С. 289-290

21. Пыхалов A.B. Особенности языка запросов системы интеграции данных DISGO //Шестнадцатая конференция представителей региональных научно-образовательных сетей "RELARN-2009", сборник тезисов докладов, Москва -Санкт-Петербург, 2009, С. 150-152

22. Пыхалов A.B. Обзор системы интеграции данных DISGO //Материалы международной научно-технической конференции МВУС-2009, Издательство технологического института ЮФУ, Таганрог, 2009, С.73-76

23. Halevy A., Rajaraman A., Ordille J. Data Integration: The Teenage Years // Proceedings of the 32nd international conference on Very large data bases, VLDB Endowment, Seoul, Korea, 2006, C. 9-16

24. Oracle Data Integrator //http://www.oracle.com/technetwork/middleware/data-integrator/overview/ ,2011

25. Shvaiko P., Euzenat J. A Survey of Schema-based Matching Approaches // Journal on Data Semantics, Vol.4, Springer, 2005, C. 146-171

26. Cruz I., Xiao H. The Role of Ontologies in Data Integration // Journal of Engineering Intelligent Systems, Volume 13, Number 4, 2005, C. 245-252

27. McCann R., AlShebli R., Le Q. et. al. Mapping Maintenance for Data Integration Systems// Proceedings of the 31st international conference on Very large data bases, VLDB Endowment, 2005, C. 1018-1029

28. Srivastava U., Munagala K., Widom J. et. al. Query Optimization over Web Services //Proceedings of the 32nd international conference on Very large data bases, VLDB Endowment, 2006, C. 355-366

29. Garcia-Molina H., Papakonstantinou Y., Quass D. et.al. The TSIMMIS approach to mediation: Data models and Languages //Journal of Intelligent Information Systems, Volume 8, No 2, 1997, C. 117-132

30. Friedman M., Levy A., Millstein T. Navigational Plans For Data Integration //In Proceedings of the National Conference on Artificial Intelligence (AAAI), 1999, C.67-73

31. Дэйт КДж. Введение в системы баз данных. Глава 23. Логические системы управления базами данных //Издание 7, Вильяимс, Москва, 2001

32. W3C. RDF/XML Syntax Specification (Revised) // http://www.w3.org/TR/rdf-syntax-grammar/, 2004

33. W3C. OWL Web Ontology Language Reference // http://www.w3.org/TR/owl-ref/, 2004

34. W3C. XQuery 1.0: An XML Query Language (Second Edition) // http://www.w3c.org/TR/xquery/, 2010

35. W3C. SPARQL Query Language for RDF // http://www.w3.org/TR/rdf-sparql-query/, 2008

36. Day R., Ahues-Vasquez J.P., Castro P., et. Al. Oracle Database Heterogeneous Connectivity Administrator's Guide lOg Release 2 (10.2) // http ://download. oracle, com/ docs/cd/B 1930601 /server. 102/b 14232/gencon.htm#sthre £343, 2005

37. Stonebraker M., Aoki M.Mariposa: a wide-area distributed database system //The VLDB Journal, Volume 5 , Issue 1, VLDB Endowment, 1996, C.48-63

38. Motro A., Multiplex: A formal model for multidatabases and its implem entation // Technical Report ISSE-TR-95-103, Department of Information and Software Engineering, George Mason University, 1999

39. Anokhin P., Motro A. Fusionplex: resolution of data inconsistencies in the integration of heterogeneous information sources //Information Fusion, Volume 7, Issue 2, C. 176-196, 2006

40. Papakonstantinou Y., Garcia-Molina H., Widom J. Object exchange across heterogeneous information sources //IEEE International Conference on Data

41. Engineering, C.251-260, 1995

42. Levy A.Y. The Information Manifold Approach to Data Integration //IEEE Intelligent Systems, Volume 13, Number 5,1998, C. 12-16

43. Levy A.Y., Rousset M.-C. CARIN: A Representation Language Combining Horn Rules and Description Logics //Proceedings of 12th European Conference on Artificial Intelligence, 1996, C.323-327

44. MacGregor R.M. A Description Classifier for the Predicate Calculus //Proceedings of the Twelfth National Conference on Artificial Intelligence, (AAAI), 1994, C.213-220

45. Xiao H, Cruz I. Ontology-based Query Rewriting in Peer-to-Peer Networks //Proceedings of the 2nd International Conference on Knowledge Engineering and Decision Support, 2006, C. 11-18

46. W3C. RDF Vocabulary Description Language 1.0: RDF Schema// http://www.w3.org/TR/rdf-schema/, 2004

47. Chen P.P. The Entity-Relationship Model: Toward a Unified View of Data //ACM Transactions on Database Systems, Volume 1, 1976, C.9-36

48. Abadi D.J., Marcus A., Madden S.R.et.al.Scalable Semantic Web Data Management Using Vertical Partitioning // Proceedings of the 33rd international conference on Very large databases, VLDB Endowment, 2007, C. 411-422

49. Chaudhuri S. An Overview of Query Optimization in Relational Systems //Proceedings of 1998 ACM PODS, ACM, New York, 1998, C. 34-43

50. Mannino M.V. Statistical Profile Estimation in Database Systems //ACM Computing Surveys, Volume 20, Number 3, 1988, C. 191-221

51. Bernstein P.A., Goodman N., Wong E. et. al., Query processing in a System for Distributed Databases(SDD- 1) //ACM Transactions on Database Systems, Volume 6, Number 4, pp. 602-625, 1981

52. Ewen S., Kache H., Markl V. Progressive Query Optimization for Federated

53. Queries // Proceedings of the 10th international conference on Advances in Database Technology, Springer-Verlag, Berlin, 2006, C.847-864

54. Wei C.-P, Olivia R., Sheng L. et. al. Fuzzy Statistics Estimation in Supporting Multidatabase Query Optimization //Electronic Commerce Research, Volume 2, Number 3, Springer, 2002, C.287-316

55. Wiegelmann J., Chaliha M., Zeitoun S. et. al. Oracle Database Gateway for VSAM User's Guide llg Release 1(11.1) // http://download.oracle.com/docs/cd/B2835901/gateways. 11 l/b31054/cgettingstarte d.htm#il005734, 2007

56. Microsoft Open Database Connectivity (ODBC) // http://msdn.microsoft.com/en-us/library/ms710252%28v=vs.85%29.aspx , 2011

57. Microsoft OLE DB // http://msdn.microsoft.com/en-us/library/ms722784%28v=vs.85%29.aspx, 2011

58. Levy A.Y, Rajaraman A., Ordille J.J. Querying Heterogeneous Information Sources Using Source Descriptions //Proceedings of the 22th International Conference on Very Large Data Bases, VLDB Endowment, 1996, C.251-262

59. Levy A.Y., Rajaraman A., Ordille J.J. Query-answering algorithms for information agents //Proceedings of the thirteenth national conference on Artificial Intelligence, Vol.1, AAAI Press, 1996, C. 40-47

60. Sickel S. A Search Technique for Clause Interconnectivity Graphs //IEEE Transactions On Computers, Volume c-25, Number 8, 1976, C.823-835

61. Apt K.R., Pellegrini A. Why the Occur-check is Not a Problem //Proceedings of the 4th International Symposium on Programming Language Implementation and Logic Programming, Springer-Verlag, London, 1992, C.69-86

62. Bancilhon F., Maier D., Sagiv Y. et. al. Magic sets and other strange ways to implement logic programs //Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems,, ACM, New York, 1985, C.l-15

63. Cumbo С., Faber W., Greco G., Leonel N. Enhancing the Magic-Set Method for Disjunctive Datalog Programs //In proceedings of 20th international conference on Logic Programming, Volume 3132/2004, Springer, 2004, C.371-385

64. Walker A., Backchain iteration: Towards a practical inference method that is simple enough to be proved terminating, sound, and complete //Journal of Automated Reasoning, Volume 11, Number 1, Springer, 1993, C.l-22

65. Henschen L.J., Naqvi S.A. On Compiling Queries in Recursive First-Order Databases //Journal of the ACM, Volume 31, Issue 1, ACM, 1984, C.47-85

66. Дэйт К.Дж. Введение в системы баз данных. Глава 6. Реляционная алгебра //Издание 7, Вильяимс, Москва, 2001

67. Официальный сайт проекта WireShark // http://www.wireshark.org/, 2010

68. Kyte Т. The fastest way of creating a huge table.// http ://asktom. oracle, com/pls/asktom/f?p=100:ll:0::::PllQUESTIONJD:1132417600346069010, 2008

69. Deutsch P. RFC 1952. GZIP file format specification version 4.3 // http ://tools. ietf. org/html/rfc 1952,1996

70. The Stanford-IBM Manager of Multiple Information Sources (TSIMMIS)// http://infolab.stanford.edu/tsimmis/, 2012

71. ПРИМЕР ОПИСАНИЯ ОТОБРАЖЕНИЙ МЕЖДУ СХЕМАМИ ДАННЫХ ИСТОЧНИКОВ ДАННЫХ ПРИ ИСПОЛЬЗОВАНИИ РАЗЛИЧНЫХ ПОДХОДОВ К ОПИСАНИЮ ОТОБРАЖЕНИЙ

72. Для ИД А отображение выражается следующим образом: Lecture(NAME,LECTOR,HOURS,COURSE,SPEC) :

73. Subj ectGlobal(NAME,LECTOR,LID,HOURS,COURSE,«lecture»,1. SPEC);

74. Для ИД В определяется следующее отображение: Subject(NAME, LID, HOURS, TYPE):

75. Subj ectGlobal(NAME,LECTOR,LID,HOURS,COURSE,TYPE,SPEC)r

76. Subject(NAME,LID,HOURS,TYPE),Tutors(LID, LECTOR, SD) => SubjectGlobal(NAME,LECTOR,HOURS,COURSE,TYPE,SPEC)

77. СИНТАКСИС РАСШИРЕНИЯ ЯЗЫКА ЗАПРОСОВ ВКГАЬОв БКСЮ С>Ь

78. Часть формального определения грамматики расширения языка запросов Datalog DISGO QL приведена на рис. 1. Query:= (Preamble)? Body Body:=predicateSequence predicateSequence:=predicate(, predicate)*

79. Preamble:="Preamble" "{" (QueryOptions)? (namespacesDefs)? mustDef";" (rulesDefs1..M^/p mjm

80. Рис. 1. Синтаксис предлагаемого расширения языка Datalog (DISGO QL)

81. ОПИСАНИЕ СХЕМ ДАННЫХ И ОТОБРАЖЕНИЙ, ИСПОЛЬЗУЕМЫХ В ЭКСПЕРИМЕНТАХ ПО ОЦЕНКЕ ПРОИЗВОДИТЕЛЬНОСТИ СИД DISGO

82. Рис. 4. Схема данных узла LP

83. Рис. 6. Предикат publications :publications {title,area,year journal,publisher, firstpage,lastpage}(?t,?a,?y,?j,?p,?f,?l)1. ИД Запросlucky publisher select distinct name "journal" ,site "site" from journals

84. Рис. 11 Неявное определение предиката publications-authors

85. АКТ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ КАНДИДАТСКОЙ ДИССЕРТАЦИОННОЙ РАБОТЫ ПЫХАЛОВА АЛЕКСАНДРА ВЛАДИМИРОВИЧА В ТАМБОВСКОМ ГОСУДАРСТВЕННОМ ТЕХНИЧЕСКОМ УНИВЕРСИТЕТЕ

86. АКТ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ КАНДИДАТСКОЙ ДИССЕРТАЦИОННОЙ РАБОТЫ ПЫХАЛОВА АЛЕКСАНДРА ВЛАДИМИРОВИЧА В ЮЖНО-РОССИЙСКОМ РЕГИОНАЛЬНОМ ЦЕНТРЕ ИНФОРМАТИЗАЦИИ ЮЖНОГО ФЕДЕРАЛЬНОГО УНИВЕРСИТЕТА1. МИНОБРНАУКИ РОССИИ

87. Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный Федеральный Университет»

88. ЮЖНО-РОССИЙСКИЙ РЕГИОНАЛЬНЫЙ ЦЕНТР »ФОРМАТИЗАЦИИ344090, г.Ростов-на-Дону, пр.Стачки 200/1, корп 2Тел: (863) 219-97-10, Факс: (863) 219-97-11fé

89. Председатель комиссии-Члены комиссии:

90. Г.В. Муратова А Лазарева Б.Л. Крукиер А.H Березовский

91. Владимировича «Методы и средства интеграции независимых баз данных в распределенных сетях

92. Председатель комиссии. Члены комиссии: