WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

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

МЕТОДЫ И СРЕДСТВА ИНТЕГРАЦИИ

НЕЗАВИСИМЫХ БАЗ ДАННЫХ В РАСПРЕДЕЛЕННЫХ

СЕТЯХ TCP/IP

05.13.11 – Программное и математическое обеспечение вычислительных

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

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

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

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

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

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

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

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

Москва)

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

347.

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

Автореферат разослан «» 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» (2007г. Нижний Новгород), на международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе IT+SE» (2008г. Гурзуф), международной научно-технической конференции МВУС (2009, с. Дивноморское).

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

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

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

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

в технической документации каталога электронных образовательных ресурсов в Тамбовском государственном техническом университете (акт внедрения), а также использованы в отчете по НИР «Разработка методов, технологий и программных средств построения распределенной инфраструктуры образовательных и научных информационных ресурсов университета федерального уровня (2009г., № гос. регистрации 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 запросы к ИД, новую информацию можно сделать доступной для приложения без его изменения.

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

В запросе возможно указать максимально допустимое время ожидания ответа ИД в миллисекундах. Если ожидаемое время извлечения информации больше указанного, ИД не будет опрошен. При этом время извлечения V(D) - пропускная способность канала до ИД D, L(D) - задержка канала, S(Q) селективность запроса, s(P,D) — размер данных представления, соответствующих предикату P в ИД D, E(s,Q) - оценка размера представления Q, учитывающая операции проекции и добавления. Считается, что проекция добавления атрибута 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, в которое добавляются условия на равенство аргументов для пар (функция, функция) и (функция, переменная), если переменная входит в состав аргументов функции.

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

Пример графа MCIG приведен на рис. 3. Граф состоит из 6 вершин.

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

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

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

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

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

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

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

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

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

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

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

_A1=INIT_EXPRESSION;

PRED=_A1 where false;

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

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

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

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

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

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

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

Сравнение производительности работы СИД 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)» // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 4. Пыхалов А.В. Свидетельство о государственной регистрации программ для ЭВМ № 2010610573 «Подсистема компиляции запросов системы интеграции данных DISGO, версия 0.1 (DISGO Compiler v. 0.1)» // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 5. Букатов А.А., Пыхалов А.В. Интеграция множества БД с использованием глобальной онтологии //Приложение к журналу «Открытое образование»:

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

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

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

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

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

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



 


Похожие работы:

«Аленин Артём Алефтинович РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ СКРЫТОЙ ПЕРЕДАЧИ ИНФОРМАЦИИ В АУДИОФАЙЛАХ Специальность: 05.13.15 Вычислительные машины, комплексы и компьютерные сети АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Самара – 2011 Работа выполнена на кафедре информатики и вычислительной техники Федерального государственного образовательного бюджетного учреждения высшего профессионального образования Поволжский государственный...»

«Пономарёв Иван Николаевич МАТЕМАТИЧЕСКИЙ АППАРАТ И ПРОГРАММНЫЕ СРЕДСТВА КОНЦЕПТУАЛЬНОГО ПРОЕКТИРОВАНИЯ Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2007 Работа выполнена на кафедре концептуального анализа и проектирования Московского физико-технического института (государственного университета). Научный руководитель : доктор...»

«БРЕДНИХИНА Анна Юрьевна РАЗРАБОТКА СРЕДСТВ ГЕОМЕТРИЧЕСКОГО МОДЕЛИРОВАНИЯ И НАУЧНОЙ ВИЗУАЛИЗАЦИИ ДЛЯ ПОДДЕРЖКИ ОБУЧЕНИЯ И ИССЛЕДОВАНИЙ В ОБЛАСТИ КРИСТАЛЛОГРАФИИ 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Новосибирск – 2009 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования Новосибирский государственный университет...»

«Бобровский Дмитрий Игоревич ЗАДАЧА ОПТИМАЛЬНОГО УПРАВЛЕНИЯ ДЛЯ БИЛИНЕЙНЫХ ДИНАМИЧЕСКИХ СИСТЕМ С ТЕРМИНАЛЬНЫМ КВАДРАТИЧНЫМ ФУНКЦИОНАЛОМ Специальность – 05.13.01 Системный анализ, управление и обработка информации АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2010 Работа выполнена в отделе прикладных проблем оптимизации Учреждения Российской Академии Наук Вычислительный Центр имени А.А. Дородницына. Научный руководитель :...»

«ЯКИМЕНКО МАРИАННА ВЛАДИМИРОВНА ИНФОРМАЦИОННО-ИНСТРУМЕНТАРНОЕ ОБЕСПЕЧЕНИЕ ПРОЦЕССА УПРАВЛЕНИЯ РЕГИОНАЛЬНЫМ ТУРИСТСКОРЕКРЕАЦИОННЫМ КОМПЛЕКСОМ Специальность: 05.13.10 – Управление в социальных и экономических системах (экономические наук и) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Ростов-на-Дону - 2008 Диссертация выполнена на кафедре государственного и муниципального права и управления Технологического института Южного федерального...»

«Лемпицкий Виктор Сергеевич МЕТОДЫ ТРЕХМЕРНОЙ РЕКОНСТРУКЦИИ НА ОСНОВЕ РАЗРЕЗОВ НА ГРАФАХ Специальность 05.13.11 ”Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей” АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва 2007 Работа выполнена на кафедре вычислительной математики механикоматематического факультета Московского...»

«Царев Федор Николаевич Методы построения конечных автоматов на основе эволюционных алгоритмов Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург – 2012 г. 2 Работа выполнена на кафедре Компьютерные технологии Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики (НИУ...»

«Кречетова Светлана Юрьевна РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММНОГО КОМПЛЕКСА ДЛЯ РЕШЕНИЯ ЗАДАЧ ГРОЗОВОЙ ПОЖАРООПАСНОСТИ ЛЕСНЫХ МАССИВОВ ГОРНОГО АЛТАЯ 05.13.18 – Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Барнаул, 2007 Работа выполнена на кафедре математического анализа ГОУ ВПО Горно-Алтайский государственный университет Научный руководитель : доктор...»

«Тимановский Алексей Леонидович СВЕРХРАЗРЕШЕНИЕ В СИСТЕМАХ ПАССИВНОГО РАДИОВИДЕНИЯ Специальность 05.13.18 – математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва 2007 Работа выполнена в Учебно-научном центре магнитной томографии и спектроскопии МГУ им. М.В. Ломоносова и на кафедре радиофизики физического факультета МГУ. Научный руководитель : Доктор...»

«Жежерун Андрей Александрович ГЕОМЕТРИЧЕСКИЕ МЕТОДЫ АНАЛИЗА СЛОЖНОГО ПОВЕДЕНИЯ В ДИНАМИЧЕСКИХ МОДЕЛЯХ С НЕГЛАДКИМИ НЕЛИНЕЙНОСТЯМИ Специальность 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Ярославль – 2009 Работа выполнена на кафедре прикладной математики Самарского государственного областного университета (Наяновой) Научный руководитель : доктор...»

«Матвеева Ирина Витальевна ЛИНГВИСТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ УСТРОЙСТВ, ФУНКЦИОНИРУЮЩИХ НА ВОЛНОВЫХ И КВАНТОВЫХ ПРИНЦИПАХ Специальность: 05. 13. 12 – Системы автоматизации проектирования (промышленность) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург – 2011 Работа выполнена в Санкт–Петербургском государственном электротехническом университете “ЛЭТИ” им. В.И. Ульянова (Ленина) Научный...»

«Гильмуллин Ринат Абрекович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ В МНОГОЯЗЫКОВЫХ СИСТЕМАХ ОБРАБОТКИ ДАННЫХ НА ОСНОВЕ АВТОМАТОВ КОНЕЧНЫХ СОСТОЯНИЙ 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Казань – 2009 Работа выполнена на кафедре теоретической кибернетики государственного образовательного учреждения высшего профессионального...»

«ТАТАРЧУК Александр Игоревич БАЙЕСОВСКИЕ МЕТОДЫ ОПОРНЫХ ВЕКТОРОВ ДЛЯ ОБУЧЕНИЯ РАСПОЗНАВАНИЮ ОБРАЗОВ С УПРАВЛЯЕМОЙ СЕЛЕКТИВНОСТЬЮ ОТБОРА ПРИЗНАКОВ Специальность 05.13.17 – Теоретические основы информатики АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва, 2014 Работа выполнена в Федеральном государственном бюджетном учреждении науки Вычислительный центр им. А.А. Дородницына Российской академии наук. Научный руководитель : доктор...»

«Коршиков Сергей Борисович МЕТОД РЕЗУЛЬТАТИВНОГО ИСКАЖЕНИЯ ГЕОМЕТРИЧЕСКИХ ДАННЫХ ДЛЯ ОБЕСПЕЧЕНИЯ БЕЗОПАСНОСТИ ЭЛЕКТРОННЫХ МОДЕЛЕЙ МАШИНОСТРОИТЕЛЬНЫХ ИЗДЕЛИЙ Специальность 05.13.01 Системный анализ, управление и обработка информации (Авиационная и ракетно-космическая техника) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2008 год 2 Работа выполнена на кафедре Прикладная информатика Аэрокосмического факультета Московского авиационного...»

«ПОПКО ЕВГЕНИЙ АЛЕКСАНДРОВИЧ ПРОГРАММНЫЙ КОМПЛЕКС ГЕНЕТИЧЕСКОГО МОДЕЛИРОВАНИЯ ПРОЦЕССОВ ТЕРМОЛЮМИНЕСЦЕНЦИИ В ДИЭЛЕКТРИКАХ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Екатеринбург – 2009 Работа выполнена на кафедре вычислительной техники в ГОУ ВПО Уральский государственный технический университет – УПИ имени первого Президента России Б.Н....»

«Сачкова Елена Федоровна Методы, алгоритмы и программы приближенного решения задачи управления 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей 05.13.01 Системный анализ, управление и обработка информации (технические наук и) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Переславль-Залесский 2009 г....»

«Базилевский Михаил Павлович ПРОГРАММНО-МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ АВТОМАТИЗАЦИИ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА РЕГРЕССИОННЫХ МОДЕЛЕЙ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук Иркутск – 2012 Работа выполнена в ФГБОУ ВПО Иркутский государственный университет путей сообщения доктор технических наук, профессор Научный руководитель : Носков Сергей Иванович...»

«Банников Денис Викторович ОПТИМИЗАЦИОННОЕ ПРОЕКТИРОВАНИЕ ПРОТОЧНЫХ ЧАСТЕЙ ГИДРОТУРБИН И АНАЛИЗ ТЕЧЕНИЯ В НИХ МЕТОДАМИ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ 05.13.18 – математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Новосибирск – 2010 Работа выполнена в Новосибирском государственном университете. Научный руководитель : доктор физико-математических наук, профессор Черный Сергей...»

«Зайцева Татьяна Владимировна ИНСТРУМЕНТАРНО-ТЕХНОЛОГИЧЕСКОЕ УПРАВЛЕНИЕ ПРОЦЕССАМИ ИННОВАЦИОННОГО ВЗАИМОДЕЙСТВИЯ СУБЪЕКТОВ НАУЧНО-ОБРАЗОВАТЕЛЬНОЙ СФЕРЫ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Специальность 05.13.10 Управление в социальных и экономических системах (экономические науки) Ростов-на-Дону 2007 Работа выполнена в ГОУ ВПО Ростовский государственный университет путей сообщения на кафедре Экономика и финансы Научный руководитель...»

«СОРОКИН Юрий Александрович СРАВНИТЕЛЬНЫЙ АНАЛИЗ И РАЗВИТИЕ МЕТОДИКИ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА ПРОЕКТОВ ПРИ ВЫВЕДЕНИИ ИЗ ПОТРЕБЛЕНИЯ ОЗОНОРАЗРУШАЮЩИХ ВЕЩЕСТВ Специальность: 05.13.01 Системный анализ, управление и обработка информации (отрасль: информационные, телекоммуникационные и инновационные технологии) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Дубна, 2010 г. Работа выполнена в Государственном образовательном учреждении высшего...»








 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.