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

884607369

ПАРХОМЕНКО ДМИТРИЙ КОНСТАНТИНОВИЧ

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МЕТОДОВ И КОМПЛЕКСОВ ПРОГРАММ ОБРАБОТКИ ПОЛУ СТРУКТУРИРОВАННЫХ ДАННЫХ НА ОСНОВЕ ТЕОРИИ ГРАФОВ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Ставрополь-2010 2 2 И10/1 2010

004607369

Работа выполнена в ГОУ ВПО «Северо-Кавказский государственный технический университет» на кафедре информационных систем и технологий

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

Маликов Андрей Валерьевич Официальные оппоненты: доктор технических наук, профессор

Кандаурова Наталья Владимировна кандидат технических наук, доцент Росенко Александр Петрович

Ведущая организация: Южно-Российский государственный технический

Защита состоится 16 июля 2010 г. в 1400 часов на заседании диссертационного совета Д 212.245.09 в Северо-Кавказском государственном техническом университете по адресу: 355028, г. Ставрополь, пр. Кулакова 2, ауд. 305.

С диссертацией можно ознакомиться в библиотеке Северо-Кавказского государственного технического университета; с авторефератом - на сайте www.ncstu.ru.

Автореферат разослан « И » _2010 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 355000, Ставропольский край, г. Ставрополь, пр. Кулакова 2, Северо-Кавказский государственный технический университет.

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

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

университет (Новочеркасский политехнический институт), ГОМТУ (НПИ), г. Новочеркасск

к.ф.-м.н., доцент

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

Актуальность работы. В настоящее время, с постоянно возрастающими объемами хранимых, обрабатываемых и передаваемых данных, сложность создания информационных систем (ИС) растет по экспоненциальному закону. Под ИС следует понимать специализированные технические объекты, являющиеся совокупностью технических и программных средств (согласно ГОСТ 27.001-95). Такие системы характеризуются, в первую очередь, тем, что связаны с определенной и достаточно обширной областью человеческой деятельности, в которой имеют место интенсивные информационные потоки и сложные правила взаимодействия между ее объектами. Физическая и логическая структура подобных объектов часто, представлена иерархией зависимых друг от друга слоев, каждый из которых представляет собой некую совокупность компонентов и предоставляет, вышележащему слою определенную функциональность. Такая структура призвана снизить общую связность системы и по возможности абстрагировать ее компоненты друг от друга.

Развитие средств связи, в особенности сети Интернет, делает актуальной задачу обработки данных с нечеткой либо часто меняющейся во времени.... структурой. Такие данные принято называть полу/структурированными. В последнее десятилетие в области полуструктурированных данных ведутся активные исследования, связанные, в частности, с популяризацией языка разметки XML и других подмножеств языка SGML, использующихся для создания документов в Интернете. Важной особенностью полуструктурированных данных является их исторически сложившаяся иерархичная форма представления. Известным решением в области управления данными в формате XML является XML-СУБД Sedna (ИСП РАН, Кузнецов С.Д.).

В контексте функционирования информационной системы полуструктурированные данные обладают особой спецификой. Хранилище данных системы зачастую представлено реляционной СУБД, поэтому появляется необходимость эффективного управления иерархическими данными в реляционном виде. Известные работы в данной области принадлежат J. Celko, Т. Grust, V. Tropashko, J. Roy, R, Kumar, A.B. Маликову и др. рольшой вклад в развитие идей интеграции иерархических данных с реляционными СУБД вносят корпорации Oracle, Microsoft и др,....

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

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

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

Объект исследования - вычислительные структуры хранения, передачи и обработки полуструктурированных данных.

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

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

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

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

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

3. Разработаны методы взаимного отображения объектно-ориентированных структур в иерархические.

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

Основные положения, выносимые на защиту. В работе получены и выносятся на Защиту следующие основные положения:

1. Комплекс математических методов обработки данных, представленных ациклическими ориентированными графами.

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

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

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

Научная новизна полученных результатов:

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

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

3. Разработанные методы взаимного отображения объектно-ориентированных структур в иерархическое представление данных позволяют адаптировать типовое решение (pattern) отображения метаданных для использования в информационных системах обработки полуструктурированных данных.

Практическая ценность работы заключается:

1. В создании программного комплекса по автоматизации ведения учебных планов, программ дисциплин, созданного для экспертной оценки качества деятельности вузов в рамках государственного контракта №П802 от 25.11.2008 (ресурс http://tutorials.ncstu.nQ.

2. В разработке программных компонент взаимодействия с базой данных Интернет-портала поддержки патептно-лицензионной деятельности в государственном научно-образовательном секторе и организациях, образующих национальную нанотехнологическую сеть по Ставропольскому краю в рамках государственного контракта № 2008-3-3.2-15 (ресурс http://nns.ncstu.ru).

3. В разработке программных компонент «Виртуального кабинета преподавателя» в рамках Образовательного Интернет-портала СевКавГТУ, пользователями которого являются более 550 средних учебных заведений (в рамках договора с Министерством образования Ставропольского края) и высших учебных заведений Ставропольского края (ресурс http://live.ncstu.ru).

Основные проведенные теоретические и экспериментальные исследования выполнены в рамках исполнения государственного контракта №П479 Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг., в рамках реализации мероприятия №1.2.1 «Проведение научных исследований научными группами под руководством докторов наук» по проекту «Разработка теоретических основ функционирования систем управления полуструктурированными данными».

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

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

Реализация и внедрение результатов работы. Полученные в диссертационной работе результаты реализованы и внедрены:

1. Более чем в 550 школах Ставропольского края (ресурс http://live.ncstu.ru).

2. В Северо-Кавказском государственном техническом университете г.-Ставрополя и его филиалах в городах Пятигорске, Кисловодске, Невинномысске, Георгиевске.

: ,! 3. В рамках исполнения обязательств по государственному контракту №П802 от 25.11.2008 г. программные средства переданы заказчику -Федеральному агентству по образованию, г. , Москва. Результаты внедрены: Московский авиационный институт (государственный технический университет) «МАИ», г. Москва; Таганрогский технологический институт федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет», г.Таганрог; Южно-Российский государственный университет экономики и сервиса, г. Шахты; Северо-Кавказский гуманитарно-технический институт, г. Ставрополь. ...-:■

4. В рамках исполнения государственного контракта по проекту №2008-3-3.2-15, разработаны программные компоненты и предоставлен доступ заказчику к специализированному интернет-порталу (ресурс http://nns.ncstu.ru) - Федеральное агентство по науке и инновациям, г, Москва.

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

1. 7th WSEAS International Conference on ARTIFICIAL INTELLIGENCE, KNOWLEDGE ENGINEERING and DATA BASES (AIKED'08), University of Cambridge, Cambridge, UK, February 20-22, 2008.

2. 8th WSEAS International Conference on ARTIFICIAL INTELLIGENCE, KNOWLEDGE ENGINEERING and DATA BASES (AIKED'08), University of Cambridge, Cambridge, UK, February 21-23, 2009.

3. Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технологиях: международная научная конференция. Ставрополь-Кисловодск, 2009.

Публикации. По теме диссертации автором опубликовано 8 печатных работ, в том числе 1 статья в журнале из перечня ВАК РФ; 2 статьи в зарубежных изданиях, проиндексированные ISI, ACM, Scopus, INSPEC; 1 свидетельство об официальной регистрации программы для ЭВМ.

Структура и объем диссертации.

Материал основной части диссертационной работы изложен на 139 страницах машинописного текста. Диссертация состоит из введения, четырех

/

глав, заключения, списка литературы из 123 наименований, 17 рисунков, 15 таблиц и 2 приложений.

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

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

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

1. Нередко, значительная часть данных обладает нечеткой либо часто меняющейся во времени структурой.

2. Существует потребность в повышении эффективности обработки полуструктурированных данных, о чем свидетельствует ряд научных работ в этой области и наличие новых технологий, например, расширение функций управления XML-документами и новый тип данных для управления иерархиями в Microsoft SQL Server 2008.

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

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

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

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

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

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

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

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

1. Методы преобразования данных.

2. Методы извлечения данных.

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

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

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

Введем ациклический ориентированный граф сущностей предметной области D(E,L), где Е - множество сущностей предметной области, L -множество связей между сущностями предметной области.

Определим множество ключевых значений предметной области Vk, состоящее из элементов vk, таких что vk = (key, е, values), где key - ключевое значение, идентифицирующее вершину vk, ее. Е — ссылка на сущность предметной области, к которой принадлежит данное ключевое значение. valuesсУ, -подмножество атомарных значений атрибутов, связанных с данным ключевым значением, Va - множество всех значений атрибутов предметной области.

Определим несвязный ациклический ориентированный граф ключевых значений предметной области V{Vt,Lk), где Vk - множество ключевых значений, - множество связей между значениями. Граф V(Vk,Lk)

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

Введем понятие вапидности подграфа данных, определяемое как соответствие его структуры структуре графа сущностей предметной области. Понятие валидности подразделяется на строгую и нестрогую. Строгая валидность определяется значением предиката validS(x), такого что validS:{Vu,h)->B, где Ушк - подграф графа V; ß = {0,l); хе{Ут1,}, такой что validS(x) = 1, если для каждой дуги / = (v,,v2) графа х, в графе D существует одна дуга /' = (е„е2); Ге L; еиеге Е, такая, 4TOv,.e = e,;v2.e = e2. В случае отсутствия /', vahdS(x) = 0. Нестрогая валидность или просто валидность определяется значением предиката valid: {Fmft} -> В, где У„ф - подграф К;Я = {0,1); xe{Vs:lh), такой что valid(x) = l, если для каждой дуги. / = (v,,Vj) графа х, в графе D вершина е2 достижима из вершины еп где vve = el,v1.e--e1, е,,е2е Е. Если е2 не ДОСТИЖИма ИЗ е,, ТО valid (х) = 0.

Операцией объединения графов будем называть бинарную операцию алгебры Dma вида Union(A,B) или в сокращенном виде Ли В, где A(VA,LAy,VA с Vk\LA си BiVH,L„)-,VH сУу - валидные ориентированные

ациклические связные графы, являющиеся подграфами графа У. Тогда результирующий граф R(Vr,Lr) будет получен следующим образом:

R = Ли В = (К., и VB,LA и Ln)

Операция объединения подграфов обладает свойствами ассоциативности, коммутативности и идемпотентности.

Операцией слияния графов будем называть бинарную операцию алгебры Dma вида Merger^(A,B) или в сокращенном виде В, где

А(Уа, £,);Va с Vt;I, с Lk и B(Vb,Lb)\Vb с Vk\L„ с. V„ - валидные ориентированные ациклические связные графы, являющиеся подграфами графа У, причем Тха =((v„f,)|»,e V„vhe У„) - множество дуг, образованных вершинами графов А и В. Тогда результирующий граф R будет получен следующим образом:

R = AWTjit В = (ЛиВ) + Т4М

Граф R образуется в результате применения операций объединения двух подграфов а и В с добавлением множества Тлв новых дуг (используется операция +) вида е = (vo,vj таких, что ТАВ q У.х Ув , каждая из которых попарно инцидентна вершинам vu и vh обоих подграфов. Вершины v,,и vi, будем называть опорными.

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

Операцией модификации графа будем называть бинарную операцию типа Alter(A,B), или в сокращенном виде А^В, где А и В - валидные связные подграфы графа V. Граф А будем называть модифицирующим, а граф В - модифицируемым. Результатом операции модификации графа будем называть такой граф R, содержащий все дуги и вершины

модифицируемого графа В, где значения атрибутов сущностей предметной области вершин В меняются согласно значениям атрибутов вершин модифицирующего графа А :

где и Ц - модифицированные множества вершин и дуг графа В.

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

Операцией удаления графя будем называть бинарную операцию Ое1е<е(А,В) или в сокращенном виде А-В, где А(К„1,) и ,Л„) - валидные ориентированные ациклические графы. Результатом операции удаления будем считать такой граф Д(Кк,£я) = А-В, где Ун с Ул и <= . Из множества узлов графа А исключается подмножество вершин, заданное Уи, а из множества ьА удаляются дуги, образованные удаляемыми вершинами.

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

Операцией выборки графа будем называть унарную операцию алгебры йта вида 5е/ес(,4 А(А) или в сокращенном виде А, где Л(УА,1.,у,Ул сУк\ЬА с - связный подграф графа V, уь - опорная вершина, а множество Р содержит предикаты для выборки данных из А.

Результатом операции -<„,, А для подграфа А будем называть связный валидный граф я, сформированный из вершин и дуг графа А, согласно заранее заданному предикату. Здесь непустое множество Р = ...,/,}, и > 0, где / = (е,С), ее Е — сущность предметной области, С - предикат, используемый для отбора вершин в результирующий граф-выборку.

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

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

1. Описание состава логических компонентов ИС.

2. Определение структуры логических компонентов ИС.

3. Описание правил взаимодействия логических компонентов ИС.

Для .рещения вышеозначенных задач разработана . математическая

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

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

Подобную структуру слоев возможно описать ориентированной сетью щиЛ„4), где = {/,„.,...,/А„,...,/ } - множество слоев системы, /,„. - слой источника данных, /,„„ - слой объектной модели приложения, /(„ - слой визуального представления данных, с £/я,х £(о), - множество зависимостей одного слоя от другого. Таким образом, в общем случае имеем:

Назначим каждой вершине в пути из истока в сток натуральное число ^ = где х - порядковый номер вершины в пути, 0<х<|£/и),|. Число у

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

Слой визуального представления р,- Уровень слоя: 3

Слой объектной модели Уровень слоя: 2

| т

Спой источника данных ■.. Уровень слоя: 1

•>/ с

Рисунок 1 - Структура слоев системы

На каждом слое /е £ системы данные представляются в виде ациклического ориентированного графа К, - подграфа V. В то же самое время, на разных слоях, программная реализация способа хранения данных может отличаться сообразно выбранной программной технологии реализации слоя. Обобщенное представление данных в виде ациклического ориентированного графа в каждом слое будем называть концептуальным, а конкретное представление данных, которое зависит от способа реализации слоя - программно-зависимым. С целью передачи конкретного подграфа между слоями должна существовать некоторая сетевая среда передачи, что обуславливает необходимость определения представления данных в момент их передачи между слоями. Такое представление данных будем называть транспортным.

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

у"/* у"/' у-ч/л'ч .

1 = {к„ до, Л?")

Здесь - граф ключевых значений предметной

области, являющийся подграфом графа К, множество операций О, сО, Тп Тп

такие, что М, =Г,(А",) и К, = Т,(М,), где граф м, - программно-зависимое представление данных системы в слое под номером /, Т, - будем называть преобразованием данных из концептуального в программно-зависимое представление. Соответственно 7J - обратное преобразование, 7'/'", Г/"', Г/'™", 7"/'""" -транспортныепреобразования.

Пару элементов .С = OLJK^J.tZ^J )), будем называть слоем доступа к данным, где KdJ = TAm(KiUJ - программно-зависимое представление данных в слое объектной модели приложения, - T.t.JKjJ,) - концептуальное представление данных в слое объектной модели. Приведем алгоритмы преобразований Т^ и Г(„„, отвечающие за трансформацию данных из концептуального представления в виде орграфа в объектно-ориентированную структуру данных и обратно.

Определим множество Г[Ь,„ абстрактных типов данных (АТД) сущностей предметной области.

Определим множество Тт как множество простых типов данных языка Л/ар, ,:E-*Tckal.

Определим множество Рт имен свойств (properties) АТД TtUm.

Определим множество Pmt значений свойств АТД.

Определим множество свойств объектов, где свойство — это пара имени свойства и его значения: Р = {(n,v)|ne /;,„„,,:v<= Pml).

Определим множество Rmm. = {п,,и2,...,п,„) имен ссылок на объекты АТД в памяти.

Определим множество объектов АТД в памяти Orh, ={о\о ~ (key,values)} где key — идентификатор объекта, values сР- множество свойств.

Определим множество С = {(е,с)\се Гс(,„,,ее Е), определяющее связь иерархии наследования АТД с сущностью предметной области.

Здесь каждый АТД - это совокупность имени АТД, имен свойств и имен ссылок: c = (name,pnames,rnames), где name- ИМЯ АТД, имена свойств pnames с Pmr, имена ссылок на объекты АТД mamescR,,,,,,,,.

Определим функцию Mapr: Tdan --> Е, которая каждому классу языка программирования в исходном коде программной системы ставит в соответствие сущность предметной области.

Определим функцию Шра:Рт ~>А, которая каждому имени свойства АТД ставит в соответствие атрибут сущности предметной области, где А -множество атрибутов сущностей предметной области.

Определим функцию, которая каждой сущности предметной области ее Е ставит в соответствие АТД се Tlhm. В том случае, если одной сущности предметной области соответствует несколько АТД, объединенных иерархией

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

Определим функцию \к>рр : А , которая каждому атрибуту ае А

сущности предметной области ставит в соответствие имя свойства АТД

Определим функцию GeiClass : 0„() -> , которая для объекта в памяти определяет его АТД.

Определим функцию CreateObject : ТЛа, -> , которая создает в динамической памяти объект ое 0„,,у по его АТД се 7'l(iiu.

Определим функцию Link : 0Л: х 0„,в Яо(1(, которая связывает два объекта в памяти, сопоставляя им дугу во множестве ссылок графа À',(J.

Пусть граф — программно-зависимое представление

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

1. Сформировать множество Vlim :={vl,...,v„);»j = |oil(1/|: для каждого

объекта о, е ; 1 < / < п создать вершину v, :

v,.key := orkey ; v,.e := Mapr(GetClass(o: )) vrvalues := {(a,value)|(«,v)6 o,.values да = Л/л/)„(/г)л value = v}

2. Для каждой пары r = (o,o')e взять из множества такие элементы v и v', что o.kcy = v.key и o'.key = v'.key, и сформировать из них следующий подграф путем применения операции слияния графов:

А', = ({v},0)ö,„y,({v'},0)

3. Объединить все получившиеся подграфы К, с помощью операции и объединения подграфов: = [J АГ .

Метод преобразования из концептуального представления в программно-зависимое представление определяется следующей последовательностью операций. Для = Tim!(C,КЛип) имеем:

1. В орграфе Kibl,(Vilmli,Lhm), для каждого ключевого значения ve Vilim преДметной области необходимо получить информацию о его АТД, создать соответствующий объект и инициализировать его поля значениями атрибутов сущности предметной области. Итак, для каждого v е :

1.1. Если существует такая пара (с,г) во множестве С, что v,.е = е, то АТД classe ТсЫ, будущего объекта принять как class = с. В случае отсутствия такой пары, АТД будущего объекта принять как

class = Мар^х^.е).

1.2. Создать объект о,еОо/у АТД class, инкапсулирующий в себе ключевое значение предметной области:

о, = CrealeObjecl(class),

1.3. Инициализировать множество values значений свойств объекта значениями атрибутов предметной области ключевого значения v,, используя функцию Map., для отображения:

о.key := v, .key

orvalues:= {(n,v)\(a,value)e vrva!ues.\n.= Mapp(a)л v:= value) Каждой паре («,v), где n — имя свойства, v - значение свойства, сопоставляется пара (a,value), где а - атрибут сущности предметной области, value - значение атрибута сущности предметной области. Имени свойства присваивается имя, полученное с помощью функции отображения для атрибута я, а значение копируется из value в v. Идентификационный ключ key копируется из v во вновь созданный объект о,, для однозначного сопоставления этих двух вершин. 2. Для каждой дуги (v,v')e Л,,„, взять объекты о и о', которые соответствуют этим вершинам по идентификационному ключу, и создать дугу в RollJ, показывающую связь между объектами:

ое О^ Л о.key = v.key о е л о.key = v.key

V= Л*, £<"*(<>.о')}

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

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

Оценим прирост эффективности обработки полуструктурированных

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

j

помощью аддитивного комплексного критерия: К = где Л, - частный

«=|

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

Определим набор частных показателей эффективности: I. Быстродействие Р компонентов ИС. Характеризуется числом обработанных записей полуструктурированного источника данных в единицу времени. Формальная совместимость математической модели и методов, описанных в данной работе, с методом материализованного пути для доступа

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

2. Корректность функционирования ИС, характеризующаяся числом D программных дефектов ИС обработки полуструктурировапных данных на 1000 строк исходно кода. Согласно исследованиям, проведенным Gordon и Beiman, применение моделирования на раннем этапе построения ИС сокращает число дефектов в среднем на 65%.

3. Расход памяти ИС обработки полуструктурированных данных, характеризующийся объемом исходного кода. Оценивается метрикой SLOC (Source lines of code - количество строк исходного кода). Согласно исследованиям, проведенным D. Barry, T. Stanienda, применение подхода отображения метаданных (metadata mapping) в среднем снижает объем исходного кода доступа к данным до 4 раз.

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

1. Os Р„ < Р,х 1,5, где Р - экспериментально зафиксированное среднее быстродействие ИС с применением модели материализованного пути. Было определено, что экспериментальная оценка быстродействия находится на уровне 66% от пропускной способности дисковой подсистемы. За основу взяты результаты замеров быстродействия, проведенные Маликовым А.В, Гулевским Ю.В, Пархоменко Д.К. На практике получено значение /' = 12000 обработанных записей в секунду. Номинальное значение быстродействия, полученное экспериментально Рн = 1300.

2. 0<Ц,<1000. Согласно исследованиям IBM, в среднем число дефектов на 1000 строк кода колеблется от 20 до 250. Примем номинальное значение числа дефектов как среднее значение этого диапазона D„ = 135 дефектов на 1000 строк кода.

3- 0<s,......=J„=10000 sloe, где S,„, = номинальное (оно же

максимальное) экспериментально полученное значение объема исходного кода доступа к данным.

• Весовые коэффициенты аддитивного критерия примем равными о-,,=0,55, ü-t) = 0,3, as = 0,15. В таблице 1 приведем расчетные значения комплексного показателя для системы с номинальными показателями, ORM решения Doctrine и подхода, описанного в настоящей диссертационной работе. На рисунке 2 представлена диаграмма сравнения значений эффективности для вышеописанных случаев.

Таблица 1. Значения комплексных критериев эффективности.

С равнозначными весовыми коэфф и циентами а,, = 0,33,uru = 0,33, ац =0,33. С неравнозначными весовыми коэффициентами «,. = 0,55, «„ = 0,3, as = 0,15

Номинальные показатели К=0,3 1 К=0,30

Doctrine ORM К=0,67 К=0,59

Предложенный подход К=0,80 К=0,77

0.9 0,8 0,7 0.6 0,5 0.4 0,3 0,2 0,1 0

я С назначенными S» "" ï весовыми

коэффициентами

s Без весовых коэффициентов

Номинальные показатели

Doctrine ORM Подход, описанный в работе

Рисунок 2 - Значения комплексного показателя эффективности

Основываясь на значениях комплексного показателя эффективности для взвешенных частных критериев, можно сделать вывод о том, что подход, представленный в диссертационной работе, позволяет повысить эффективность обработки полуструктурированных данных на 157% по сравнению с номинальными показателями и на 30% по сравнению с ORM решением Doctrine.

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

Программный комплекс состоит из следующих территориально распределенных компонентов:

1. Локальный модуль сбора данных.

2. Специализированный интернет-портал.

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

Вуз 1

j i'Mo/iynb'i j | сбора < Ждаимых,/

Вуз 2

,Шдуль\

сбора \даниы>

Вуз 3

Учебные планы. УМК. программы дисциплин

Интернет портал

Отчетность Статистика Эксперты Эксперты

Рисунок 3 - Схема работы программного комплекса

Модуль сбора данных логически разделен на 4 слоя:

1. Слой источника данных. Слой источника данных представляет собой реляционную базу данных с дополнительными надстройками управления полуструктурированнымн данными. Логика манипуляции данными представлена слоем хранимых процедур, реализующих расширенную алгебру Dma. В качестве СУБД используется Microsoft SQL Server 2005 Express Edition.

2. Слой объектной модели приложения реализован в виде нескольких .NET сборок (assembly). Эти сборки входят в поставку приложения.

3. Слой доступа к данным также реализован в виде нескольких .NET сборок, которые входят в состав приложения.

4. Слой визуального представления данных реализован в виде визуальных форм оконного приложения для операционных систем семейства Microsoft Windows, построенных на основе технологии WinForms 2.0 библиотеки Microsoft ,NET Framework.

Схема распределения слоев приложения показана на рисунке 4.

Слой объектной модели

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

Локальная копия модуля на рабочей станции

^¿.»--Сетевая среда

Слой доступа к данным

Слой источника данных

у

)

Реляционная БД с иерархической

структурой и слоем хранимых процедур

Рисунок 4 - Схема распределения слоев приложения

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

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

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

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

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

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

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

(Федеральное агентство по образованию МОиН РФ) по оценке качества программ дисциплин и учебно-методических комплексов.

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

Статьи, опубликованные в периодических научных изданиях, рекомендованных ВАК РФ:

1. Пархоменко, Д.К. Проецирование иерархических структур реляционных данных в объектную модель приложения [текст] / Маликов А.В., Пархоменко Д.К., Гулевский Ю.В. // Известия высших учебных заведений. Северо-Кавказский регион. Технические науки, выпуск 3. - Новочеркасск, 2009. - С. 19-25.

Статьи в сборниках по итогам проведения международных и всероссийских научных конференции:

2. Parkhomenko, D. Mathematical model for storing and effective processing of directed graphs in sem¡structured data management systems [текст] / Malikov A., Gulévsky Y., Parkhomenko D. // Proceedings of the 7th WSEAS International Conference on ARTIFICIAL INTELLIGENCE, KNOLEDGE ENGINEERING and DATA BASES (AIKED'08), University of Cambridge, Cambridge, UK, February 20-22, 2008. - P. 541-548.

3. Parkhomenko D. Hierarchical data management in relational systems [текст]/Malikov A., Gulevsky Y., Parkhomenko D. // Proceedings of the 8 th WSEAS International Conference on ARTIFICIAL INTELLIGENCE, KNOLEDGE ENGINEERING and DATA BASES (AIKED'09), University of Cambridge, Cambridge, UK, February 21-23, 2009. - P. 191-196.

4. Пархоменко Д.К. Предпосылки введения алгебры для формализации операций над иерархическими данными [текст] // Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технологиях: международная научная конференция. Ставрополь-Кисловодск, 2009. - С. 88-89.

Свидетельства о государственной регистрации программы для

ЭВМ:

5. Пархоменко Д.К., Маликов А.В., Гулевский Ю.В. «Система управления полуструктурированными данными: BiZone», свидетельство об официальной регистрации программы для ЭВМ №2009612196. Зарегистрировано в Реестре программ для ЭВМ 29.04.2009 г.

Депонированные работы:

6. Пархоменко Д. К. Алгебра орграфов для моделирования иерархических данных [текст]. СевКавГТУ. - Ставрополь, 2009. - 21с. - Рус. - Деп. В ВИНИТИ 15.10.09, №627-В 2009.

7. Пархоменко Д.К. Анализ процесса создания корпоративных приложений [текст]. СевКавГТУ. - Ставрополь, 2009. - 22с. - Рус. - Деп. В ВИНИТИ 15.10.09, №628-В 2009.

8. Пархоменко Д.К. Математическая модель программной системы, основанной на иерархических данных [текст]. СевКавГТУ. -Ставрополь, 2009. - 10с,-Рус.-Деп. В ВИНИТИ 15.10.09, №626-В 2009.

Вклад автора

В [1] автором предложена схема взаимодействия слоев модели ИС обработки полуструктурироваиных данных; описана работа слоя доступа к данным и слоя объектной модели приложения.

В [2] автором проведены эксперименты по сравнительной оценке эффективности обработки полуструктурированных данных в реляционной

БД.

В [3] автором предложена методика оптимизации иерархической структуры для эффективного моделирования полуструктурированных данных в реляционной БД.

В [5] автором реализованы алгоритмы отображения метаданных для создания единообразного преобразования данных между объектно-ориентированной моделью и иерархическим представлением.

Печатается в авторской редакции

Подписано в печать 11.06.2010 Формат 60x84 1/16 Усл. печ. л. - 1,5 Уч.-изд. л,-1 Бумага офсетная. Печать офсетная. Заказ №184 Тираж 100 экз. ГОУ ВПО «Северо-Кавказский государственный технический университет» 355028, г. Ставрополь, пр. Кулакова, 2

Издательство Северо-Кавказского государственного технического университета Отпечатано в типографии СевКавГТУ

ВВЕДЕНИЕ.

1. ОБЗОР ЛИТЕРАТУРЫ.

1.1 Обработка полу структурированных данных.

1.1.1 OEM модель.

1.1.2 Модель TAX.

1.1.3 Модель XAL.

1.2 Информационные системы обработки данных.

1.3 Математические модели представления полу структурированных данных в памяти ЭВМ.

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

1.5 Типовые решения объектно-реляционного согласования интерфейсов (ORM-системы).

1.6 Требования к программным комплексам обработки полуструктурированных данных.

1.7 Постановка задачи.

Выводы.

2. КОМПЛЕКС МАТЕМАТИЧЕСКИХ МЕТОДОВ ОБРАБОТКИ ДАННЫХ, ПРЕДСТАВЛЕННЫХ АЦИКЛИЧЕСКИМИ ОРГРАФАМИ

2.1 Определения.

2.2 Операция объединения графов.

2.3 Операция слияния графов.

2.4 Операция выборки графа.

2.5 Операция модификации графа.

2.6 Операция удаления графа.

Выводы.

3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ИНФОРМАЦИОННОЙ СИСТЕМЫ

ОБРАБОТКИ ПОЛУСТРУКТУРИРОВАННЫХ ДАННЫХ.

3.1 Слой источника данных.

3.2 Слой объектной модели приложения.

3.3 Слой визуального представления данных.:.

3.4 Методы взаимного отображения объектно-ориентированных структур в иерархическое представление данных.

3.4.1 Слой доступа к данным.

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

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

3.5 Оценка прироста эффективности обработки полу структурированных данных.

Выводы.

4. ПРОГРАММНЫЙ КОМПЛЕКС ОБРАБОТКИ

ПОЛУ СТРУКТУРИРОВАННЫХ ДАННЫХ.

4.1 Функциональность и структура программного комплекса.

4.2 Реализация слоя объектной модели приложения.

4.3 Реализация слоя доступа к данным.

4.4 Реализация слоя визуального представления данных.

4.5 Адаптация и применение типового решения доступа к данным.

4.6 Анализ характеристик программного комплекса.

Выводы.

В настоящее время, с постоянно возрастающими объемами хранимых, обрабатываемых и передаваемых данных, сложность создания информационных систем (ИС) растет по экспоненциальному закону [120]. С учетом современных требований ко времени и качеству обработки разнородной информации, функционирование достаточно крупной организации немыслимо без автоматизации ее деятельности'.

Автоматизация деятельности организации осуществляется с использованием информационных систем обработки данных, под которыми будем понимать специализированные технические объекты, являющиеся совокупностью технических и программных средств (согласно ГОСТ 27.00195) [73]. Такие системы характеризуются, в первую очередь, тем, что связаны с определенной и достаточно обширной областью человеческой деятельности, в которой имеют место интенсивные информационные потоки и сложные правила взаимодействия между ее объектами. Физическая и логическая структура подобных объектов часто представлена иерархией зависимых друг от друга слоев, каждый из которых представляет собой некую совокупность компонентов и предоставляет вышележащему слою определенную функциональность. Такая структура призвана снизить общую связность системы и по возможности абстрагировать ее компоненты друг от друга.

Развитие средств связи и коммуникации, в особенности сети Интернет, делает актуальной задачу обработки данных с нечеткой либо часто меняющейся во времени структурой. Такие данные принято называть полуструктурированными [105]. В последнее десятилетие' в области полуструктурированных данных ведутся активные исследования, связанные, в частности, с популяризацией языка разметки XML[113, 122] и других подмножеств языка SGML [33], использующихся для создания документов в

Интернете. Важной особенностью полу структурированных данных является 4 их исторически сложившаяся иерархичная форма представления. Известным решением в области управления данными в формате XML является XML-СУБД Sedna (ИСП РАН, Кузнецов С.Д.) [16].

В контексте функционирования информационной системы полуструктурированные данные обладают особой спецификой. Хранилище данных системы зачастую представлено реляционной СУБД [74], поэтому появляется необходимость эффективного управления иерархическими данными в реляционном виде. Известные работы в данной области принадлежат J. Celko, Т. Grust, V. Tropashko, J. Roy, R. Kumar, A.B. Маликову и др. [45, 57, 91] Большой вклад в развитие идей интеграции иерархических данных с реляционными СУБД вносят корпорации Oracle, Microsoft и др.

Анализ литературных источников показал возможность повышения эффективности обработки полуструктурированных данных по ряду показателей, используя специальные методы математического моделирования [23,45,85]. Применение результатов подобного моделирования на ранних этапах проектирования ИС позволяет предотвращать дефекты, вместо их исправления [85].

На данный момент существует потребность в эффективной обработке полуструктурированных данных, подтверждаемая большим количеством научных и технических статей, описывающих различнее аспекты этого процесса [27, 57, 58, 81, 114, 115, 117]. В этой связи, необходим набор правил и спецификаций для создания систем такого рода, в которых бы формально описывалась функциональность, общая для любой системы, оперирующей полуструктурированными данными. Для решения этой задачи предлагается создание формального описания информационной системы обработки иерархических данных в виде математической модели, описывающей состав, структуру и правила взаимодействия компонентов системы между собой. В результате анализа открытых отечественных и зарубежных литературных источников, не было выявлено единой целостной математической модели ИС обработки полуструктурированных данных. 5

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

Объектом исследования являются вычислительные структуры хранения, передачи и обработки полуструктурированных данных.

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

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

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

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

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

3. Разработаны методы взаимного отображения объектно-ориентированных структур в иерархические.

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

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

2. Впервые разработана математическая модель, описывающая состав, 1 структуру и правила взаимодействия логических компонентов информационной системы обработки полуструктурированных данных, использование которой позволяет типизировать процессы построения, функционирования, рефакторинга системы, что по сравнению с известными аналогами приводит к увеличению суммарной эффективности системы более чем на 30%.

3. Разработанные методы взаимного отображения объектно-ориентированных структур в иерархическое представление данных позволяют адаптировать типовое решение (pattern) отображения метаданных для использования в информационных системах обработки полу структурированных данных.

На защиту выносятся:

1. Комплекс математических методов обработки данных, представленных ациклическими ориентированными графами.

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

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

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

Практическая ценность работы заключается:

1. В создании программного комплекса по автоматизации ведения учебных планов, программ дисциплин, созданного для экспертной оценки качества деятельности вузов в рамках государственного контракта №П802 от 25.11.2008 (ресурс http://tutorials.ncstu.ru).

2. В разработке программных компонент взаимодействия с базой данных Интернет-портала поддержки патентно-лицензионной деятельности в государственном научно-образовательном секторе и организациях, образующих национальную нанотехнологическую сеть по Ставропольскому краю в рамках государственного контракта № 2008-3-3.2-15 (ресурс http://nns.ncstu.ru ).

3. В разработке программных компонент «Виртуального кабинета преподавателя» в рамках Образовательного Интернет-портала СевКавГТУ, пользователями которого являются более 550 средних учебных заведений (в рамках договора с Министерством образования Ставропольского края) и высших учебных заведений Ставропольского края (ресурс http://live.ncstu.ru).

Основные проведенные теоретические и экспериментальные исследования выполнены в рамках исполнения государственного контракта № П479 Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг., в рамках реализации мероприятия №1.2.1 «Проведение научных исследований научными группами под руководством докторов наук» по проекту «Разработка теоретических основ функционирования систем управления полу структурированными данными».

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

Реализация и внедрение результатов работы. Полученные в диссертационной работе результаты реализованы и внедрены:

1. Более чем в 550 школах Ставропольского края (ресурс http://live.ncstu.ru).

2. В Северо-Кавказском государственном техническом университете г. Ставрополя и его филиалах в городах Пятигорске, Кисловодске, Невинномысске, Георгиевске.

3. В рамках исполнения обязательств по государственному контракту №П802 от 25.11.2008 г. программные средства переданы заказчику-Федеральному агентству по образованию, г. Москва. Результаты внедрены: Московский авиационный институт (государственный технический университет) «МАИ», г. Москва; Таганрогский технологический институт федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет», г. Таганрог; ГОУ ВПО «Южно-Российский государственный университет экономики и сервиса», г. Шахты; Северо-Кавказский гуманитарно-технический институт, г. Ставрополь.

4. В рамках исполнения государственного контракта по проекту №2008-3-3.2-15, разработаны программные компоненты и предоставлен доступ заказчику к специализированному Интернет-порталу (ресурс http://nns.ncstu.ru) - Федеральное агентство по науке и инновациям, г. Москва.

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

1. 7th WSEAS International Conference on ARTIFICIAL INTELLIGENCE, KNOWLEDGE ENGINEERING and DATA BASES (AIKED'08), University of Cambridge, Cambridge, UK, February 20-22, 2008.

2. 8th WSEAS International Conference on ARTIFICIAL INTELLIGENCE, KNOWLEDGE ENGINEERING and DATA BASES (AIKED'08), University of Cambridge, Cambridge, UK, February 21-23, 2009.

3. Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технологиях: международная научная конференция. Ставрополь-Кисловодск, 2009.

Публикации. По теме диссертации автором опубликовано 8 печатных работ, в том числе 1 статья в журнале из перечня ВАК РФ; 2 статьи на английском языке, проиндексированные ISI, ACM, Scopus, INSPEC; 1 свидетельство об официальной регистрации программы для ЭВМ [98].

Материал основной части диссертационной работы изложен на 139 страницах машинописного текста. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 123 наименований, 17 рисунков, 15 таблиц и 2 приложений.

Выводы

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

1. Выбор технологии создания программного комплекса обработки полуструктурированных данных. В качестве такой технологии выбрана среда разработки Microsoft Visual Studio 2008, платформа .NET Framework 3.5 и язык программирования С#.

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

123 модификация модели материализованного пути, разработанная специалистами СевКавГТУ [45].

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

• Отображение метаданных (metadata mapping)

• Преобразователь данных (data mapper)

• Единица работы (unit of work)

• Коллекция объектов (identity map)

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

ЗАКЛЮЧЕНИЕ

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

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

1. Abteboul S. The Lorel Query Language for Semistructured Data Text. / S. Abteboul, D. Quass D, J. McHugh, J. Widom, L. Wiener // International Journal on Digital Libraries. 1997.

2. Ambler S. The Object-Relational Impedance Mismatch Electronic resource. / S. Ambler. URL: http://www.agiledata.org/ (дата обращения 10.04.09).

3. Ambler S. Mapping Objects to Relational Databases: O/R Mapping In Detail Electornic resource. / S. Ambler. URL: http://www.agiledata.org/ (дата обращения 10.04.09). • '

4. Barreto J. SQL Server 2008 Hierarchies and HierarchylD Electornic resource. / J. Barreto. URL: http://blogs.technet.com/009/03/24/sql-server-2008-hierarchies-and-hierarchyid.aspx (дата обращения 10.04.09).

5. Barry D. Solving the Java Object Storage Problem Text. / D. Barry, T. Stanienda // IEEE Computer. 1998.

6. Buneman P. Semistructured data / P. Buneman // Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. 1997.-P. 117-121. - ISBN 0-89791-910-6.

7. Celko J. SQL for Smarties Text. / J. Celko. Morgan-Kaufmann, 2005. ISBN 978-0-12-369379-2.

8. Celko J. Trees and Hierarchies Text. / J. Celko. Morgan-Kaufmann,I2004. ISBN 978-1-55860-920-4.

9. Claybrook B. Oltp: Online Transaction Processing Sstems Text. / B. Claybrook / John Wiley & Sons Inc, 1992. 384 p. - ISBN 978-0471556688.

10. Cluet S. The New YATL: Design and Specifications Text.: working draft / S. Cluet, S. Jacqmin, J. Simeon // IGMOD Conference. 2000.

11. DeMarco T. Management Can Make Quality Impossible Text. / T. De-Marco // Cutter IT Summit. Boston, 1999.

12. Deutsch A., Fernandez M., Florescu D., Levy A., Suciu D. A query language'for XML Text. / A. Deutsch, M. Fernandez // An International World Wide Web Conference. 1999.

13. Dyche J. The CRM Handbook: A Business Guide to Customer Relationship Management Text. / J. Dyche. Addison-Wesley Professional 336 p.-ISBN 978-0201730623.

14. Eckerson W. Three Tier Client/Server Architecture: Achieving

15. Scalability, Performance, and Efficiency in Client Server Applications Text. / W.1 / Eckerson. Open Information Systems. -1995. №10.

16. Elliott J. Harnessing Hibernate Text. / J. Elliott, T. O'Brien, R. Fowler. O'Reilly Media, 2008. 384 p. - ISBN 978-0596517724.

17. Fomichev A. Sedna: A Native XML DBMS Text. /А. Fomichev, M. Grinev, S. Kuznetsov. Springer Berlin. ISBN 978-3-540-31198-0.

18. Frasincar F. XAL: an Algebra for XML Query Optimization Text. / F. Frasincar, G. Houben, C. Pau // Proceedings of the thirteenth. Australasian Conference on Database Technologies. 2002. - P. 49-56.

19. Gamma E. Design Patterns: Elements of Reusable Object-Oriented Software Text. / E. Gamma, R. Helm, R. Johnson, J. Vlissides. Addison-Wesley, 1995.-ISBN 0-201-63361-2.

20. Garcia-Molina H. Database Systems: The Complete Book Text. / H. Garcia-Molina, J. Ullman, J. Widom .Prentice Hall, 2001. 1525 p.

21. Glover A. Stop writing so much code! Electronic resource. URL: http://www.ibm.com/developerworks/edu/j-dw-java-lessismore-i.html (дата обращения 10.04.09). . ■

22. Goldman R. DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases Text. /R. Goldman, J. Widom // Proceedings ofi * . '• 1 tthe Twenty-Third International Conference on Very Large Data Bases. 1997.

23. Goldman R. XML Query Language (XQL) Text. / R. Goldman, J. Widom // The W3C Query Languages Workshop. Boston, 1998.

24. Gordon S. Rapid Prototyping and Software Quality: Lessons from Industry Text. / S. Gordon, J. Bieman. Department of Computer Science : technical report. Colorado State University, 1991.

25. Hambrick J. Persistence in the Enterprise: A Guide to Persistence Technologies Text. / J. Hambrick, K. Brown. IBM Press, 2008. 464 p.

26. Harbart J. X-Query: A universal query interface for XML Text. / J. Harbart // Software AG.

27. Hashimi S. Pro Service-Oriented Smart Clients with .NET 2.0 Text. / S. Hashimi, S. Steffan //Apress, 2005. 344 p. - ISBN 978-1590595510.

28. Hillyer M. Managing Hierarchical Data in MySQL Electronic resource. URL: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html (дата обращения 10.04.09).

29. IEEE Std 1008-1987. Standard for Software Unit Testing.

30. IEEE Std 1028-1997. Standard for Software Reviews.

31. IEEE Std 1061-1998. Standard for a Software Quality Metrics Methodology.

32. IEEE Std 730-2002. Standard for Software Quality Assurance Plans. 2002 : б.н.

33. IEEE Std 829-1998. Standard for Software Test Documentation.

34. ISO 8879:1986. Information processing Text and office systems -Standard Generalized Markup Language (SGML). International Organization for Standardization, 1986.

35. ISO/IEC 9075:2008 Standard. Information technology Database languages - SQL.

36. ISO-9001. Quality Management Systems Requirements.

37. ISO-9126. Software engineering Product Quality.

38. Jagadish H. TAX: a Tree Algebra for XML Text. / H. Jagadish, L. Lakshmanan, D. Srivastava // Proceedings of the International Workshop on Data Bases and Programming Languages . Frascati, 2001. P. 149-164.

39. Jeroen P. Integral Warehouse Management: The Next Generation in Transparency, Collaboration and Warehouse Management Systems Text. / P. Jeroen. Management Outlook, 2007. 252 p. - ISBN 978-1419668760.

40. Capers J. Programming Productivity Text. / J. Capers. McGraw-Hill, 1986.-ISBN: 100070328112.

41. Capers J. Software Defect-Removal Efficiency Text. / J. Capers. IEEE Computer, 1996.

42. Kanter J. Understanding Thin Client/Server Computing Text. / J. Kan-ter. Microsoft Press, 1997. 256 p. - ISBN 978-1572317444.

43. Khan M. Five Reasons for using an ORM Tool Electornic resource. / M. Khan. Alachisoft. URL : http://www.alachisoft.com/articles/orm.html (дата обращения 10.04.09).

44. Kuate P. NHibernate in Action Text. / P. Kuate, C. Bauer, G. King, T. Harris. Manning Publications, 2009. 400 p. - ISBN 978-1932394924.

45. Lee C. ADO.NET Entity Framework Unleashed Text. / C. Lee. Sams, 2010. 600 p. - ISBN 978-0672330742.

46. McAffer J. Eclipse Rich Client Platform / J. McAffer. Addison-Wesley Professional, 2010. 552 p. - ISBN 978-0321603784.

47. McHugh J. Lore: A Database Management System for Semistructured Data Text. / J. McHugh, S. Abiteboul, R. Goldman R, D. Quass, J. Widom. SIG-MOD Record, 1997.

48. Meade J. The Human Resources Software Handbook: Evaluating Technology Solutions for Your Organization Text. / J. Meade. Pfeiffer, 2002. 400 p. -ISBN 978-0787962517.

49. Mehta P. Pro LINQ Object Relational Mapping in C# 2008 Text. / P. Mehta. Apress, 2008. 408 p. - ISBN 978-1590599655.

50. Meyer H. Manufacturing Execution Systems (MES): Optimal Design, Planning, and Deployment Text. / H. Meyer, F. Fuchs, K. Thiel.' McGraw-Hill Professional, 2009. 274 p. - ISBN 978-0071623834.

51. Papakonstantinou Y. Object Exchange Across Heterogeneous Information Sources Text. / Y. Papakonstantinou, H. Garcia-Molina, J. Widom // Eleventh International Conference on Data Engineering (ICDE 1995), 1995.

52. Robie J. Quilt: an XML query language Text. /J. Robie, D. Chamber-lin, D. Florescu. Software AG, 2000.

53. Shull F. What We Have Learned About Fighting Defects / F. Shull // Eighth IEEE International Symposium on Software Metrics, 2002. P. 242-258.

54. Snyder M. Working with Microsoft Dynamics CRM 3.0 Text. / M. Snyder. Microsoft Press. 464 p. - ISBN 978-0735622593.

55. Transact SQL Reference. Hierarchyid Electornic resource. URL: http://technet.microsoft.com/en-us/library/bb677290.aspx (дата обращения 10.04.09).

56. Tropashko V. Nested Intervals Tree Encoding with Continued Fractions Electronic resource. URL: http://arxiv.org/ (дата обращения 10.04.09).

57. Tulder G. Storing Hierarchical Data in a Database Electronic resource. URL: http://articles.sitepoint.com/article/hierarchical-data-database (дата обращения 10.04.09).

58. Wage J. Doctrine ORM for PHP Text. / J. Wage, R. Borschel, G. Blanco. Sensio SA, 201.0. 552 p. - ISBN 978-2918390268.

59. Wallace Т., Kremzar M. ERP: Making It Happen: The Implementers' Guide to Success with Enterprise Resource Planning Text. / T. Wallace, M. Kremzar//Wiley, 2001.

60. Wheeler D. Counting Source Lines of Code (SLOC) Electronic resource. URL: http://www.dwheeler.com/sloc/ (дата обращения 10.04.09).

61. Whitehead M. Implementing SugarCRM: A step-by-step guide to using this powerful Open Source application in your business Text. / M. Whitehead. Packt Publishing, 2006. 328 p. - ISBN 978-1904811688.

62. Wienberg G. Quality Software Management: Systems Thinking Text. / G. Wienberg. Dorset House Publishing Company, 1991. ISBN: 0932633226.

63. Агуров П. C#: Разработка компонентов в MS Visual Studio Текст. / П. Агуров. СПб. : БХВ-Петербург, 2008. - 480 с. - ISBN 978-5-9775-0295-5.

64. Архангельский А.В. Канторовская теория множеств Текст. / А.В. Архангельский. М.: Изд-во МГУ, 1988.

65. Белов В.В. Теория графов Текст. / В.В. Белов. М.: Высшая школа, 1976.

66. Белоусов А.И. Дискретная математика Текст. / А. И. Белоусов. -М.: Издательство МГТУ им. Н.Э. Баумана, 2001.

67. Бердж К. Теория графов и ее применение Текст. / К. Бердж. М.: ИЛ, 1962.

68. Виейра Р. Программирование баз данных Microsoft SQL Server 2005 Текст. / Р. Виейра. М. : «Диалектика», 2007. - 832 с.'

69. Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах Текст. / В.А. Галкина. М.: Гелиос АРВ, 2003.

70. Гандерлой М. Освоение Microsoft SQL Server 2005 Текст. / М. Гандерлой, Д. Джорден, Д. Чанц. М. : «Диалектика», 2007. - 1104 с.

71. Горбатов В.А. Фундаментальные основы дискретной математики Текст. / В.А. Горбатов. М. : Наука. Физматлит, 1999.

72. ГОСТ 27.001-95. Система стандартов "Надежность в технике". Основные положения. 1997.

73. Дейт К. Введение в системы баз данных Текст.'/ К. Дейт. М. : Вильяме, 2001. - ISBN 5-8459-0138-3.

74. Зыков А.А. Основы теории графов Текст. / А.А. Зыков. М. : Наука, 1987.

75. Исследования по прикладной теории графов : сборник статей Текст. Новосибирск : АН СССР, Сибирское отделение, 1986.

76. Кантор Г. Труды по теории множеств Текст. / Г. Кантор. М. : Наука, 1990.

77. Кристофидес Н. Теория графов. Алгоритмичёский подход Текст. / Н. Кристофидес. М. : Мир, 1978.

78. Кузнецов М. MySQL на примерах Текст. / М. Кузнецов, И. Симдянов. СПб. : БХВ-Петербург, 2007. - 592 с. - ISBN 978-5-9775-0066-1.

79. Кузнецов О.П. Дискретная математика для инженера Текст. / О.П. Кузнецов. СПб. : Издательство "Лань", 2004. - ISBN 5-8114-0570-7.

80. Леонов Ю.А. Представление иерархических структур данных в реляционных СУБД Текст. / Ю.А. Леонов // BC/NW. 2003. - № 1.

81. Луни К., Брила Б. Oracle 10g. Настольная книга администратора баз данных Текст. / К. Луни, Б. Брила. Лори, 2009. 750 с. ' '

82. Маззулло Д., Уитли П. SAP R/3 для каждого. Пошаговые инструкции, практические рекомендации, советы и подсказки Текст. / Д. Маззулло, П. Уитли. Днепропетровск : Баланс Бизнес Букс, 2008.

83. Майника Э. Алгоритмы оптимизации на сетях и графах Текст. / Э.М. Майника. М. : Мир, 1981.

84. Макконнелл С. Совершенный код Текст. / С. Макконнелл. -СПб. : Издательство "Русская редакция", 2007. 896 с. - ISBN: 5-75020064-7.

85. Маликов А. В. Математическая модель хранения и эффективной обработки орграфов, представленных в машинном виде Текст. / А.В. Маликов, Ю.В. Гулевский // Известия вузов. Северо-Кавказский регион. Технические науки. Новочеркасск, 2007. №60.

86. Маликов А. В., Лидовской К. В. Расширение реляционной алгебры для декларативных языков запросов к нормализованным на основе операций выборки и соединения базам данных Текст. / А.В. Маликов, К.В. Лидовской

87. Известия вузов. Северо-Кавказский регион. Технические науки. Новочеркасск, 2005.-С. 9-10.

88. Маликов А. В. Использование нормализованных на основе операций выборки и соединения реляционных баз данных в корпоративных автоматизированных системах управления Текст. / А.В. Маликов // Известия СевКавГТУ. Ставрополь : СевкавГТУ, 2005. - №4.

89. Маликов А. В. Методика проектирования реляционных баз данных на основе операций, отличных от проекции и соединения Текст. / А.В. Маликов // Известия вузов. Северо-Кавказский регион. Технические науки, 2003.-С. 7-111.

90. Маликов А. В. Ориентированные графы в реляционных базах данных Текст. / А.В. Маликов // Доклады Томского государственного университета систем управления и радиоэлектроники, 2008. №2. ч.2. - С. 102-106.

91. Маликов А. В. Проектирование реляционных баз данных на основе операций выборки и соединения. Исследование их свойств: монография под ред. д.т.н. проф. Чефранова А.Г. Ставрополь : СевКавГТУ, 2001.

92. Маликов А.В. Разработка синтаксиса ' и- алгоритма функционирования инструкций манипулирования данными реляционных баз данных Текст. / А.В. Маликов // Известия вузов. Северо-Кавказский регион. Технические науки, 2003. С. 12-17.

93. Маликов А.В. Реализация инструкций запросов к реляционным базам данных Текст. / А.В. Маликов // Известия вузов. Приборостроение. -М., 2005. №9. - С.7-12.

94. Маликов А. В. Управление иерархическими данными в реляционных базах данных Текст. / А.В. Маликов // Известия вузов. Северо-Кавказский регион. Технические науки. Новочеркасск, 2009. №2. -С. 3-8.

95. Маликов А. В. К вопросу обеспечения "функционирования реляционных баз данных, нормализованных на основе операций, выборки и соединения Текст. / А.В. Маликов, К.В. Лидовской // Безопасность информационных технологий. М., 2005. - №3. - С. 62-67.

96. Маликов А. В. Математическая модель задачи оптимизации поиска информации на графах. Методы ее решения Текст. / А.В. Маликов, К.В. Лидовской // Известия СевКавГТУ. Ставрополь : СевКавГТУ, 2007. -№21.

97. Маликов А.В., Пархоменко Д.К., Гулевский Ю.В. Система управления полуструктурированными данными: BiZone, свидетельство об официальной регистрации программы для ЭВМ №2009612196 от 29.04.2009 г.

98. Математическое и программное обеспечение задач дискретной оптимизации: сборник научных трудов, отв. ред. И.В. Сергиенко. Киев: ИК, 1989.

99. Нечепуренко М.И., Попков В.К. Алгоритмы и программы решения задач на графах и сетях Текст./ М.И. Нечепуренко, В.К. Попков. АН СССР, Сибирское отделение. Новосибирск: Наука. Сибирское отделение, 1990.

100. Новиков Ф.А. Дискретная математика для программистов Текст. / Ф.А. Новиков. СПб. : Питер, 2002. - 304 с. - ISBN 5-272-00183-4.

101. Олифер В. Г. Компьютерные сети. Принципы, технологии, протоколы Текст.: учебник для вузов / В.Г. Олифер, Н.А. Олифер. -СПб ■: Питер, 2007. 960 с. - ISBN 5-469-00504-6.

102. Ope О. Теория графов Текст. / О. Ope. -М. : Наука, 1980.

103. Орлов С. Организация ЭВМ и систем Текст. / С. Орлов, Б. Циль-кер. СПб.: Питер, 2007. - ISBN 5-94723-759-8.

104. Палей Д. Моделирование квазиструктурированных данных Электронный ресурс. // Открытые системы, 2002. URL: http://www.osp.ru/os/2002/09/181940/ (дата обращения 10.04.09).'

105. Пархоменко Д.К. Алгебра орграфов для моделирования иерархических данных Текст. СевКавГТУ. Ставрополь, 2009. 21 с. -Деп. В ВИНИТИ 15.10.09, №627-В 2009.

106. Пархоменко Д.К. Анализ процесса создания корпоративных приложений Текст. СевКавГТУ. Ставрополь, 2009. 22с. -Деп. В ВИНИТИ 15.10.09, №628-В 2009.

107. Пархоменко Д.К. Математическая модель программной системы, основанной на иерархических данных Текст. СевКавГТУ. Ставрополь, 2009. 10 с. -Деп. В ВИНИТИ 15.10.09, №626-В 2009.

108. Питеркин С. В. Точно вовремя для России. Практика применения ERP-систем Текст./ С.В. Питеркин, Н.А. Оладов, Д.В. Исаев. М. : Адьпина Паблишерз, 2010. - ISBN 978-5-9614-1157-7.

109. Рихтер Д. CLR via С#. Программирование на платформе Microsoft .NET Framework 2.0 на языке С# Текст. / Д. Рихтер. СПб. : Питер, 2007. -656 с. - ISBN: 978-5-91180-303-2.

110. Рязанцева Н. 1С:Предприятие. Секреты программирования Текст. / Н. Рязанцева Н., Д. Рязанцев. -СПб. : БХВ-Петербург, 2005. 352 с. - ISBN 5-94157-416-9. '

111. Сергеев А. П. HTML и XML. Профессиональная работа Текст. / А.П. Сергеев. М. : Диалектика, 2004. - 880 с. - ISBN 5-8459-0676-8.

112. Стадник М. Иерархические структуры данных и Doctrine Электронный ресурс. URL: http://mikliailstadnik.com/hierarchical-data-structures-and-doctrine (дата обращения 10.04.09).

113. Стадник М. Иерархические структуры данных и производительность Электронный ресурс. URL: http://rnikhailstadnik.com/hierarchical-data-structures-and-performance (дата обращения 10.04.09).

114. Танненбаум Э. Современные операционные системы Текст. / Э. Танненбаум. СПб. : Питер, 2004. - ISBN 5-318-00299-4.

115. Тарасов С. Иерархические структуры и деревья в SQL Текст. / С. Тарасов // Мир ПК, 2007. № 3.

116. Уолтере P. SQL Server 2008: ускоренный курс длй профессионалов Текст. / Р. Уолтере, М. Коулс. -М. : «Вильяме», 2008. 768 с. - ISBN 978-58459-1481-1.

117. Уорсли Д. PostgreSQL. Для профессионалов Текст. / Д. Уорсли, Д. Дрейк. СПб. : Питер, 2003. - 496 с. - ISBN: 5-94723-337-1.

118. Фаулер М. Архитектура корпоративных программных приложений Текст. / М. Фаулер. М. : Вильяме, 2004. - ISBN 5-8459-0579-6.

119. Фридл Д. Регулярные выражения Текст. / Д. Фридл. СПб. : Питер, 2003. - ISBN 5-272-00331-4.

120. Хантер Д. XML. Базовый курс Текст. / Д. Хйнтер, Д. Рафтер. М. : Вильяме, 2009. - 1344 с. - ISBN 978-5-8459-1533-7

121. Хемраджани А. Гибкая разработка приложений на Java с помощью Spring, Hibernate и Eclipse Текст. / А. Хемраджани. М. : Вильяме, 2008. -352 с. - ISBN 978-5-8459-1375-3.