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

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

ГЛАДКОВ Максим Владимирович

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

Специальности:

05.13.01 - Системный анализ, управление и обработка информации

05.13.11 -Математическое и программное обеспечение вычислительных машин, комплексов и компьютерны! сетей

Автореферат

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

ПЕНЗА 2005

Работа выполнена на кафедре «Математическое обеспечение и применение ЭВМ» Пензенского государственного университета.

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

Хмелевской Б. Г.

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

Шибанов С. В.

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

Лебедев В. Б.;

кандидат технических наук, доцент Имамутдинов И. Ф.

Ведущая организация - ООО «Научно-производственная фирма

"КРУГ'» (г. Пенза).

Защита диссертации состоится <;< А1 » (Хлу?^^/ 2005 г., в « /У » часов, на заседании диссертационного совета Д 212.186.04 Пензенского государственного университета по адресу: 440026, г. Пенза, ул. Красная, 40, корпус № 1.

С диссертацией можно ознакомиться в библиотеке Пензенского государственного университета.

Автореферат разослан Мо/> 2005 г.

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

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

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

С могунов В. В.

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

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

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

Для решения этой задачи существует несколько подходов:

- использование плоских файлов и ПО для управления ими;

- использование специализированных хранилищ, таких, как Storage от Microsoft;

- использование систем управления базами данных (СУБД).

Первый подход требует разработки ПО для управления плоскими

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

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

РСУБД, как и другие СУБД (иерархические, сетевые и объектные), непосредственно не поддерживает хранение и обработку сложных структур данных, таких, как списки, массивы, деревья, графы, стеки и очереди.

Коллекции объектов и структуры данных являются подмножеством графов, которые, в свою очередь, являются подмножеством мультиграфов и псевдографов. Исследованиям мультиграфов и псевдографов посвящены работы Касьянова В. Н, Евстигнеева В. А., Акимова О. Е.,Харари Ф. (HararyF.), ЗвиллингераД. (ZwШmgerD.).

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

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

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

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

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

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

3. Разработка метода и средств преобразования в РБД фундаментальных структур данных: массивов, списков, стеков, очередей, бинарных и сильно ветвящихся деревьев, графов, а также файловой системы и иерархии компонентов ПО SCADA-систем.

4. Разработка программных инструментальных средств для работы с фундаментальными структурами данных в РБД.

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

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

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

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

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

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

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

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

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

1.Для разработки систем обработки данных созданы программные инструментальные средства: набор хранимых процедур на языке Trans-act-SQL и программные инструментальные средства для создания программ, программных комплексов и пакетов прикладных программ в виде динамически подключаемой библиотеки прикладного программиста, позволяющие ускорить процесс разработки программных средств, предназначенных для обработки сложно структурированных данных в РБД.

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

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

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

- информационная система «Приемная руководителя» внедрена и используется в приемной Губернатора Пензенской области (г. Пенза), что подтверждается соответствующим актом;

- «Система управления несоответствиями программного обеспечения» внедрена в ООО НПФ «КРУГ» (г. Пенза), применяется при разработке ПО АСУТП для предприятий нефтехимической и газовой промышленности, а также для объектов энергообеспечения, что подтверждается соответствующим актом;

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

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

- Международной научно-технической конференции «Проблемы автоматизации и управления в технических системах» (г. Пенза, 2004 г.);

- Международном юбилейном симпозиуме «Актуальные проблемы науки и образования» (г. Пенза, 2004 г.);

- V Международной научно-технической конференции «Новые информационные технологии и системы» (г. Пенза, 2002 г.);

- IV-VII Международных научно-методических конференциях «Университетское образование» (г. Пенза, 2000-2003 гг.).

Основные положения диссертационной работы, выносимые на защиту:

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

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

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

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

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

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

Публикации. По теме диссертации опубликованы 16 печатных работ, в том числе 3 статьи и 13 тезисов докладов.

Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения, списка использованной литературы, включающего 153 наименования, 5 приложений. Содержание диссертации изложено на 228 страницах машинописного текста. В работе 35 рисунков, 38 таблиц, 50 графиков.

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

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

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

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

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

- псевдограф, описываемый пятью конечными

множествами:

V- множество вершин;

Е - множество ребер;

Ту- множество типов вершин; Те - множество типов ребер; О - множество ограничений,

1. V= {vb v2.....v„}, где v, (1 < i < и) - отдельная вершина псевдографа. Каждая вершина v, принадлежит какому-то одному типу вершин Ту из множества типов вершин псевдографа Tv. Принадлежность к типу будем обозначать v,: Ту.

/ = l,ny\ j = l,mv;vieV-, Т$ еТу, (1)

где nv - количество вершин в множестве V;

ту - количество типов вершин в множестве Ту.

2. Тип вершины Ту - это множество атрибутов, описывающих вершину заданного типа:

Т'у = {<Л,:Д>, <A2:D2>,..., <A„:Dn>}, (2)

где Aj- имя атрибута; Dj - домен, которому принадлежит атрибут; п - количество атрибутов в типе вершины Tly,\<j<n. Каждая вершина v* есть множество упорядоченных пар <А,: Value, >, где 1 < i < и; и - количество атрибутов в типе вершин Ту, к которому принадлежит вершина vk; Value, - значение из домена D„ соответствующего атрибуту А, в типе вершины Т^. Кроме атрибутов типа

вершины, каждая вершина имеет один дополнительный атрибут N (идентификатор или номер вершины), который уникально определяет вершину во всем множестве V, не учитывая тип вершины, к которому она принадлежит. Значения номеров вершины берутся из домена D,d- Du состоит из целых положительных ненулевых чисел.

Vjt = {<Л,:Value\>, <Аг:Valuej>,... ,<А„\Valued, <N: Value,d>}. (3)

3. Каждое ребро принадлежит какому-то одному типу ребер из множества типов ребер псевдографа.

Ve;. :Т{\ i = \rTE-, j = Ъщ; е,- еЕ\ Ц <аТЕ, (4)

где пе - количество ребер в множестве Е;

тЕ - количество типов ребер в множестве ТЕ.

4. Каждое ребро е, из множества Е относится к какому-то одному типу ТЕ из множества ТЕ. Тип ребра ТЕ ~ это множество атрибутов, описывающих ребро заданного типа:

Т*Е = {<АгА>, <A2:D2>,<A„:D„>}, (5)

где Aj- имя атрибута; D, - домен, которому принадлежит атрибут;

п - количество атрибутов в типе ребра TlE; 1 <j < п.

Каждое ребро есть множество упорядоченных пар <А,: Value, >, где 1 < i <п;п- количество атрибутов в типе ребра TJE, к которому принадлежит ребро ек; Value, - значение из домена Д, соответствующего атрибуту А, в типе ребра TJE. Кроме атрибутов типа ребра,

каждое ребро имеет два атрибута-ссылки на две вершины. Первый атрибут-ссылка Nbegw указывает на начальную вершину ребра из множества V, а второй атрибут-ссылка Nen¡¡ указывает на конечную вершину ребра из множества V.

ек= {<ЛьValueх>, <А2:Va/ue2>,<А„:Valuen>,

<Nbegm:Valuelcn>, <Nend:Value¡íü>}. (6)

Атрибуты-ссылки Nbegm и Ne„d принадлежат домену Dld, который содержит уникальные номера вершин из множества V.

5. О - множество ограничений, накладываемых на вершины и ребра псевдографа. Ограничения могут быть следующих типов:

- ключи - атрибут или множество атрибутов, уникально идентифицирующих объект (вершину или ребро);

- ограничения по единственному значению, в основном это относится к ключам, но возможны и другие источники ограничений этого типа;

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

- ограничения области значений;

- общие ограничения.

Графическое представление псевдографа приведено на рисунке. а,б. Кружками ' I изображаются вершины, а ромбами ■"^V-' и линиями со стрелками - ребра. Принадлежность вершины к определен-

ному типу вершины и ребра к определенному типу ребер можно обозначить цветом или штриховкой различного вида. На рисунке а представлен псевдограф в разрезе типов вершин и типов ребер, т. е. на нем в качестве вершин-кружков выступают типы вершин, а не сами вершины, а в качестве ребер-ромбов - типы ребер, а не сами ребра. Из рисунка видно, что граф обладает 3 типами вершин и 3 типами ребер. Серые ребра могут связывать только белые вершины (рекурсивная связь). Белые ребра могут связывать черные и белые вершины, а также черные и серые вершины. Черные ребра могут связывать черные вершины с белыми. На рисунке б представлен тот же псевдограф, что и на рисунке а, но здесь он показывает не типы вершин и типы ребер, а сами вершины и ребра, заполненные конкретными данными: 4 вершины и 4 ребра. На рисунке в представлено описание атрибутов типов вершин и типов ребер в нотации UML (Unified Modeling Language), предназначенной для описания объектов.

Пусть R — набор отношений, состоящий из конечного множества реляционных отношений: R = {R\, R2, ... , R„}, где п - количество реляционных отношений.

Модель преобразования нагруженного псевдографа в РМД разбивается на шесть операций:

1) преобразование доменов атрибутов типов вершин и типов ребер в домены РМД;

2) преобразование множества вершин в набор реляционных отношений;

3) преобразование множества ребер в набор реляционных отношений;

4) преобразование множества типов вершин в набор реляционных отношений;

5) преобразование множества типов ребер в набор реляционных отношений;

6) преобразование множества ограничений в множество ограничений РМД.

Рассмотрим каждую операцию подробнее. Преобразование доменов: Фй: D° ¿/мд, где еР - множество доменов типов вершин и типов ребер псевдографа; £)рмд - множество доменов РМД; Ф0 - функция отображения D° в //мд.

Обозначения:

Обозначения:

-тип вершины -вершина

псевдографа \у псевдографа

- тип ребра псевдогрэфа - ребро псевдографа

Тип белой вершины (Ту) Атрибут 1: Домен атрибута 1

Атрибут П1: Домен атрибута п»

Тип черной8»РШИНЫ (Ту) Атрибут 1: Домен атрибута 1

Атрибут пг: Домен атрибута пг

Тип серой вершины (Ту*) Атрибут 1: Домен атрибута 1

Атрибут пз: Домен атрибута па

Тип белого ребра {Те) Атрибут 1; Домен атрибута 1

Атрибут гги; Домен атрибута ггь

Тип черного ребра (Гег)_

Атрибут 1: Домен атрибута 1

Атрибут ш Домен атрибута тг

Тип серого ребра (г/)_

Атрибут 1: Домен атрибута 1

Атрибут та: Домен атрибута гпз

в

Графическое представление псевдографа: а - графическое представление типов вершин и типов ребер псевдографа; б - графическое представление псевдографа, наполненного конкретными данными, в - описание типов вершин и ребер псевдографа с использованием иМЬ-нотации

Простые домены (строки, числа, дата, время и т. д.) обычно отображаются прямо в домены РМД: 1>сятр/е 1?т!шр1е- Но в множестве ЕР могут присутствовать сложные домены, которые невозможно отобразить средствами современных СУБД в один из простых доменов РМД. Обычно это домены, где каждое значение домена само является набором (упорядоченным или неупорядоченным) элементов, где каждый элемент состоит из множества атрибутов, принадлежащих простым или сложным доменам. Сложные домены предметной области преобразуются уже не в домены РМД, а в наборы реляционных отношений РМД.

Оссотр1^-> {<N^3,^^^ '

где - первое и одновременно главное отношение сложного

домена; 2 <1<т,т- количество отношений, в которые отображаются атрибуты элементов сложного домена; Я, - отношения, в которые отображаются атрибуты элементов сложного домена; название и домен атрибута соответствующего отношения Л,; 1 <у < т; т - количество атрибутов в отношении Я,.

Преобразование множества вершин: Ф^: V—> Ну, где Фу-функция отображения К в Н у.

Преобразование множества типов вершин: Фту- Ту —> Нту, где Ф/у— функция отображения Ту в Кту.

Эти две операции очень тесно взаимосвязаны. Для отображения вершин в РМД вводится понятие главного отношения вершин, которое обозначается как Л^лега/- Оно имеет следующую структуру:

^епегы = {< Номер_псевдографа:Д^>, < Номер_вершины:Д,,(/>, <Тип:5[/1>р<!>}- ^

В это отношение преобразуются все вершины псевдографа. Для хранения в БД нескольких псевдографов одинаковой структуры в Л^епега/ вводится атрибут Номер псевдографа (Ас), принадлежащий домену в котором для каждой вершины хранится номер псевдографа, которому она принадлежит.

Каждой вершине присваивается суррогатный ключ Номер_ вершины (N1,) из автоматически генерирующего уникальные значения домена Д,«/- Этот домен в реальных СУБД представляется различного рода инкрементными типами. Атрибут Тип принадлежит домену А'¡уре, значениями которого являются целые числа от 1 до п, где и - количество типов вершин в множестве Ту. Типу вершины Ту соответствует значение 1 из домена йу,уре, Ту - 2 и т. д. Каждый тип

вершины Ту из множества 7> отображается в одно отношение. Если Т'у = {<Л|:/?!>, <А2:02>,..., <А:Др>}, то

Ту -> Яу, = <Л2:£>2>,..., <Ап\Вп>). (9)

Атрибут Иу в данном случае является внешним ключом для атрибута Ну из отношения Кукакгы- Атрибуты <А\\Б\>, <А2:02>> ... , <Ап\Оп> будем называть информационными атрибутами вершины и обозначать Аф. В отношении К, хранятся информационные атрибуты только вершин, у которых в отношении Rvgeneюl атрибут Тип принимает значение /.

Отношение Л^сп«™; необходимо для уникальной идентификации каждой вершины вне зависимости от того, какому типу она принадлежит, а в РМД этого можно достичь только использованием главного отношения, в котором хранятся и генерируются уникальные идентификаторы для всех вершин.

Таким образом, множества К и Ту преобразуются в |7>| + 1 отношение РМД.

£4* ={1,2,..., \Ту\}, К^Д^ягга/{<Л/Ь:£У>, <№,</>,

<Тип:Оу1уре>},

Ту-*{Яп{<Му: АЛ <Л,': А'>, <А2х:В2х>,..., <Ап\\Оп\>}, (10) Ы<Л№>, <А\'3\>, <А22:022>,..., <А„22:0„2>),...,

Яуш^у.АЛ <ЛЛАт>, <А2т-.02т>,..., <Аптт-Ошт>}},

где Яу, - отношение, в которое преобразуется /-Й тип вершины Ту; 1 < 1 < т, т - количество типов вершин, т. е. т = \ Ту | - мощность множества Ту, <А^:Ц'> - название и домен атрибута соответствующего отношения Яу,; 1 <_/ < л/; т - количество атрибутов в отношении Лу, и типе вершины Ту.

Преобразование множества ребер: ФЕ: Е —>

где Фя - функция отображения Е в

Преобразование множества типов ребер: Фга: Т[; 8 ть где Ф те - функция отображения ТЕ в

Эти две операции также очень тесно взаимосвязаны. Само преобразование выглядит аналогично преобразованиям Фуи Ф?у.

£->Л£8епега,{<Л^:А</>, <МСП(1\Ои1>,

<Тип:/)%ре>};

Яп^Е-О^МХ1- А2>, <Аг-.022>,..., <Лп22:Д,22>},... ,

ЯеЛ^Е-О^, <АГ:йГ>, <Агт-.02т>,..., <Аптт'.йшт>}}, где Лй - отношение, в которое преобразуется ;-й тип ребра Г/г'; 1 < У < /и; т - количество типов ребер, т. е. т = ¡Т^; <Л/:А7'> - название и домен атрибута соответствующего отношения 1 <у < и/; т - количество атрибутов в отношении ЯЕ, и типе ребра Т,.'.

Преобразование множества ограничений: Ф0: О —> 0РМд,

где Ф0 - функция отображения О в 0РМд;

Ормд - множество ограничений РМД.

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

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

В третьей главе приводятся примеры отображения в РМД фундаментальных структур данных: массивов, списков, стеков, очередей, бинарных и сильно ветвящихся деревьев, графов, а также файловой системы и иерархии компонентов ПО SCADA-систем.

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

Рассмотренные в главе примеры показали простоту и удобство применения модели преобразования нагруженных псевдографов для преобразования в РМД сложных структур данных.

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

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

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

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

В приложении А приводится описание динамически подключаемой библиотеки прикладного программиста и хранимых процедур на языке TRansact-SQL, разработанных для обработки фундаментальных структур данных, преобразованных в РМД и использованных при разработке программы Collection Statistics и других информационных систем, акты о внедрении которых приведены в приложении Д.

Результаты теоретической и экспериментальной оценки

Операция Простое отношение Односвязный список Двусвязный список Циклический односвязный список Циклический двусвязный список Стек Очередь

1 2 1 2 1 2 1 2 1 2 1 2 1 2

Добавление элемента 1 1 3-4 2 3-4 2 4-5 2 5-6 2 3-4 2 4 2

Удаление по значению 1 1 1,5-2 1,1 2 1,1 2-2,5 1,1 2-2,5 1,1 _ _ _ _

Удаление по идентификатору 1 1 1,5-2 2 2 2 2-2,5 2 2-2,5 2 1,5 4 2 4

Поиск по значению 1 1 1 1 1 1 1 1 1 1 __ _ _

Поиск по идентификатору 1 1 1 1 1 1 1 1 1 1 _

Операция Одномерный массив Бинарное дерево (левый/ правый) потомок Бин де (ука на п арное рево затель редка) Сильно ветвящееся дерево (две таблицы) Сильно ветвящееся дерево (указатель на предка) Граф Файловая система

1 2 1 2 1 2 1 2 1 2 1 2 1 2

Добавление элемента _ _ 5 2 4 2 5 1,5 4-5 1,2 2 1 1,5-3 2,5

Удаление по значению _ _ __ _ _ _ _ _ _ _ _ __ _ _

Удаление по идентификатору _ _ 5 2 3 1,2 5 1,2 3 1 1.5 1 4 1,2

Поиск по значению 1 1 1 1 1 1 1 1 1 1 1 1 1,5 1

Поиск по идентификатору _ _ 1 1 1 1 1 1 1 1 1 1 1 1

В приложениях Б и В приводятся трехмерные графики экспериментального тестирования преобразованных в РМД структур данных (коллекций) размером от 500 до 100000 элементов. Каждый трехмерный график представляет собой зависимость среднего времени выполнения операции (добавления, удаления, обновления и поиска элемента(ов)) в каждой из рассмотренных структур данных от количества элементов в коллекции и размера информационных атрибутов элементов коллекции.

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

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

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

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

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

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

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

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

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

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

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

1. Малое и определенное число шагов преобразования.

2. Единый алгоритм преобразования.

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

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

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

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

1. Гладков М. В. Сложные структуры в реляционных базах данных / М. В. Гладков, С. В. Шибанов // Открытые системы. - М.: Изд-во «Открытые системы», 2004. - № 2. - С. 62-67.

2. Гладков М. В. Расширяемая модель данных в информационных системах // Проблемы автоматизации и управления в технических системах: Тр. Междунар. науч.-техн. конф. / Под ред. проф. М. А. Щербакова. - Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2004.-С. 204-206.

3. Гладков М. В. Система несоответствий программного обеспечения // Университетское образование. Тез. докл. VII Междунар. на-уч.-метод. конф. - Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2003.-С. 395-396.

4. Гладков М. В. Отображение фундаментальных структур данных в реляционную модель / М. В. Гладков, С В. Шибанов // Актуальные проблемы науки и образования: Тр. Междунар. юбилейного симпозиума / Под. ред. проф. М. А. Щербакова. - В 2 т. - Пенза: Ин-форм.-издат. центр Пенз. гос. ун-та, 2003. - Т. 2. - С. 443-446.

5. Гладков М. В. Автоконфигурирование приложений 8СЛОЛ КРУГ - 2000 / Л. В. Гурьянов, М. В. Гладков, А. А. Лушников // Проблемы автоматизации и управления в технических системах: Тр. Междунар. науч.-техн. конф. / Под ред. проф. М. А. Щербакова. -Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2004. - С. 228-230.

6. Гладков М. В. Отображение фрактальной структуры электронных учебных курсов в реляционную базу данных / М. В. Гладков, С. В. Шибанов // Проблемы автоматизации и управления в технических системах: Тр. Междунар. науч.-техн. конф. / Под ред. проф. М. А. Щербакова. - Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2004. - С. 320-321.

7. Гладков М. В. Информационная система «Приемная руководителя» / М. В. Гладков, В. А. Свешников, С. В. Шибанов // Телекоммуникации и информатизация образования. - М.: Изд-во «Телекоммуникации и информатизация образования», 2003. - № 2 (март-апрель).-С. 63-71.

8. Гладков М. В. От электронных учебников к программным тренажерам / М. В. Гладков, С. В. Шибанов // Телекоммуникации и информатизация образования. - М.: Изд-во «Телекоммуникации и информатизация образования», 2002. - № 4 (июль-август). - С. 49-56.

9. Гладков М. В. Проблема разработки программных тренажеров и способы ее решения / С. В. Шибанов, М. В. Гладков // Новые информационные технологии и системы: Тр. V Междунар. науч.-техн. конф. -Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2002. - С. 161-162.

10. Гладков М. В. Проблемы построения программных тренажеров / С. В. Шибанов, М. В. Гладков // Университетское образование: Тез. докл. VI Междунар. науч.-метод. конф. - Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2002. - С. 60-62.

11. Средства оценки качества тестовых заданий для оболочки автоматизированной обучающей системы / С. В. Шибанов, Б. Г. Хме-левской, М. В. Гладков, В. В. Чернова // Университетское образование: Тез. докл. VI Междунар. науч.-метод. конф. - Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2002. - С. 62-63.

12. Средства проектирования учебных курсов для оболочки автоматизированной обучающей системы / С. В. Шибанов, Б. Г. Хмелев-ской, М. В. Гладков, Д. А. Быков // Университетское образование: Тез. докл. VI Междунар. науч.-метод. конф. - Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2002. - С. 64-65.

13. Средства проектирования контрольных тестов для оболочки автоматизированной обучающей системы / С. В. Шибанов, Б. Г. Хме-левской, М. В. Гладков, А. М. Чернов // Университетское образование: Тез. докл. VI Междунар. науч.-метод. конф. - Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2002. - С. 65-66.

14. Гладков М. В. Реализация демонстрационных примеров в АОС по курсу «Компьютерная графика» / М. В. Гладков, Д. В. Абдулов // Гуманитарные науки в системе высшего образования: Тез. докл. студенческой межвуз. науч. конф. - Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2001. - С. 334-335.

15. Гладков М. В. Автоматизация разработки обучающих систем / С. В. Шибанов, М. В. Гладков, Д. В. Абдулов // Университетское образование: Тез. докл. V Междунар. науч.-метод. конф. - Пенза: Ин-форм.-издат. центр Пенз. гос. ун-та, 2001. - С. 111-112.

16. Реализация средств тестирования обучаемых в АОС по курсу «Компьютерная графика» /СВ. Шибанов, К. С. Горбачевский, М. В. Гладков, Д. В. Абдулов, Н. А. Моисеева // Университетское образование: Тез. докл. IV Междунар. науч.-метод. конф. - Пенза: Информ.-издат. центр Пенз. гос. ун-та, 2000. - С. 62-65.

Гладков Максим Владимирович

Методы и средства обработки информации в реляционных базах данных

Специальности:

05.13.01 - Системный анализ, управление и обработка информации

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Редактор Т. Н. Судовчихина Технический редактор Н. А. Вьялкова Корректор Н. А. Сидельникова Компьютерная верстка Р. Б. Бердниковой

ИД №06494 от 26.12.01 Сдано в производство 28.02.05. Формат 60x84^/16. Бумага писчая. Печать офсетная. Усл. печ. л. 1,16. Заказ 122. Тираж 100.

Издательство Пензенского государственного университета. 440026, Пенза, Красная, 40.

05. /<2 - 05. Í3

2IS

Введение.

Глава 1. Анализ моделей и методов хранения и обработки сложноструктурированных данных во внешней памяти. 1.1 Проблема хранения сложно-структурированных данных программных

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

Все цифровые устройства, от суперкомпьютеров до кофеварки, требуют разработки программного обеспечения (ПО). ПО сегодня применяется в АСУТП и АСУП, обработке гео-информации, аналитической обработке данных реального времени (OLAP), оперативной обработке транзакций (OLTP), поддержке принятия решений (DSS), обучающих системах [6], различной офисной финансовой и бухгалтерской деятельности, а также в развлекательной индустрии (игры, фильмы, музыка) и т.д.

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

Внутри программного обеспечения информация представляется в виде сложно-структурированных данных: объектов, коллекций объектов, всевозможных связей между ними, а также в виде сложных структур -массивов, списков, деревьев и т.д. Таким образом, на современном этапе развития программной индустрии, актуальной является задача обработки в долговременной памяти объектов, коллекций объектов, связей между ними и структур данных [134].

Для решения этой задачи существует несколько подходов:

- использование плоских файлов и ПО для управления ими;

- использование специализированных хранилищ, таких как Storage от Microsoft;

- использование систем управления базами данных (СУБД).

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

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

Коллекции объектов и структуры данных являются подмножеством графов, которые, в свою очередь, являются подмножеством мультиграфов (графов с кратными ребрами) и псевдографов (мультиграфов с петлями). Исследованиям мультиграфов и псевдографов посвящены работы Касьянова В.Н. [20], Евстигнеева В.А. [20], Акимова О.Е. [3], Харари Ф. (Harary F.) [1], Звиллингера Д. (Zwillinger D.) [2].

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

Каждый атрибут характеризуется именем атрибута и доменом, к которому принадлежит атрибут. Домен - определяемый пользователем тип данных. Каждый атрибут можно определить только на одном домене. Под доменом понимаются как простые, скалярные типы данных, такие как числа, строки символов, даты и время, так и сложные типы данных (сложные домены), такие как массивы, множества, списки, деревья, которые в свою очередь содержат элементы, состоящие из множества атрибутов [15].

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

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

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

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

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

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

3. Разработка метода и средств преобразования в РБД фундаментальных структур данных: массивов, списков, стеков, очередей, бинарных и сильно ветвящихся деревьев, графов, - а также файловой системы и иерархии компонентов ПО SCADA-систем.

4. Разработка программных инструментальных средств для работы с фундаментальными структурами данных в РБД.

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

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

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

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

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

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

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

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

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

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

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

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

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

- информационная система «Приемная руководителя» внедрена и используется в приемной Губернатора Пензенской области (г. Пенза), что подтверждается соответствующим актом [149];

- «Система управления несоответствиями программного обеспечения» внедрена в ООО НПФ «КРУГ» (г. Пенза), применяется при разработке ПО АСУТП для предприятий нефтехимической и газовой промышленности, а также для объектов энергообеспечения, что подтверждается соответствующим актом [147, 152];

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

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

7. Основные результаты работы были использованы на практике и внедрены: в администрации Губернатора Пензенской области (г. Пенза) при разработке информационной системы «Приемная руководителя»; в ООО НПФ «КРУГ» (г. Пенза) при разработке «Система управления несоответствиями программного обеспечения»; в районном электротеплосетевом предприятии Городищенского района Пензенской области (г. Городище) при разработке информационной системы «Формирование правил оплаты, учет и анализ платежей потребителей электроэнергии». Кроме того, результаты диссертационной работы используются в разрабатываемой в данный момент «Системе управления учебным процессом кафедры». Данная система разрабатывается на кафедре «Математическое обеспечение и применение ЭВМ» Пензенского государственного университета. Исследования над этим проектом и результаты выполнения работы периодически докладывались на различных научных конференциях и симпозиумах [138, 139, 140, 141, 142, 143, 144, 145, 146].

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

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

1. Малое и определенное число шагов преобразования.

2. Единый алгоритм преобразования.

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

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

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

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

1. Увеличение числа отображенных в РБД коллекций.

2. Расширение понятия домена в реляционных СУБД, как это предлагает Дж. Дейт.[15]

3. Использование модели псевдографов в качестве промежуточного представления предметной области как при использовании модели сущность-связь, так и семантической объектной модели.[26]

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

5. Преобразование в РБД не только структуры объектов предметной области, но и операций манипулирования этими объектами.

149

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

1. Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

2. Zwillinger, D. (Ed.). CR С Standard Mathematical Tables and Formulae, 31st ed. Boca Raton, FL: CRC Press, 2003.

3. Акимов O.E. Дискретная математика: логика, группы, графы. 2-е изд., дополн. М.: Лаборатория Базовых Знаний, 2001. - 367 е.: ил.

4. Андреев Е.Б., Куцевич Н.А., Синенко О.В. SCADA системы: взгляд изнутри. - М.: Издательство «РТСофт», 2004. - 176 е.: ил.

5. Баркер, Скотт, Ф. Профессиональное программирование в Microsoft Access2002.: Пер. с англ. М.: Издательский дом «Вильяме», 2002. - 992 с. : ил. -Парал. тит. англ.

6. Башмаков А.И., Башмаков И.А. Разработка компьютерных и обучающих систем. М.: Информационно-издательский дом «Филинъ», 2003. - 616 с.

7. Беннет Д., Маконин С., Мейфилд В.В. и др. Visual С++ 5.0. Руководство разработчика.: Пер. с англ. К.; М.; СПб: Диалектика, 1998. - 768 с. : ил. -Парал. тит. англ.

8. Вейскас Д. Эффективная работа с Microsoft Access 97 СПб: ЗАО «Издательство «Питер», 1999. - 976 е.: ил.

9. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. М.: Мир, 1989. -360 е., ил.

10. Влиссидес, Джон. Применение шаблонов проектирования. Дополнительные штрихи. : Пер. с англ. М.: Издательский дом «Вильяме»,2003. 144 е.: ил. - Парал. тит. англ.

11. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб: Питер, 2000. - 384 е.: ил.

12. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб: Питер, 2001. - 368 е.: ил. (Серия «Библиотека программиста»).

13. Гарсиа М.Ф., Рединг Дж., Уолен Э., ДеЛюк С.A. Microsoft SQL Server 2000.

14. Справочник администратора. / Пер. с англ. М.: Издательство ЭКОМ, 2002. -976 е.: ил.

15. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. -М.: Мир, 1998. 703 е., ил.

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

17. Дмитриева М.В., Кубенский А.А. Турбо Паскаль и Турбо Си: Построение и обработка структур данных: Учеб. пособие. СПб.: Издательство С.-Петербургского университета, 1996. - 192 с.

18. Дунаев Сергей. Доступ к базам данных и техника работы в сети. Практические приемы современного программирования. М.: ДИАЛОГ-МИФИ, 1999.-416 с.

19. Искусственный интеллект. В 3-х кн. Кн. 2. Модели и методы: Справочник/ Под ред. Д.А. Поспелова - М.: Радио и связь, 1990. - 304 е.: ил.

20. Калиниченко JI.A. Методы и средства интеграции неоднородных баз данных./ Под ред. JI.H. Королева. М.: Наука. Главная редакция физико-математической литературы, 1983. - 424 с.

21. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. - 1104 е.: ил.

22. Кнут, Дональд, Эрвин. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ.: Уч. пос. М.: Издательский дом «Вильяме», 2000. - 720 е.: ил. - Парал. тит. англ.

23. Кнут, Дональд, Эрвин. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд.: Пер. с англ.: Уч. пос. М.: Издательский дом «Вильяме», 2000. - 832 е.: ил. - Парал. тит. англ.

24. Кнут, Дональд, Эрвин. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер. с англ.: Уч. пос. М.: Издательский дом «Вильяме», 2000. - 832 е.: ил. - Парал. тит. англ.

25. Коннолли Томас, Бегг Каролин, Страчан Анна. Базы данных: проектирование, реализация и сопровождение. Теория и практика, 2-е изд.: Пер.с англ.: Уч. пос. М.: Издательский дом «Вильяме», 2000. - 1120 е.: ил. -Парал. тит. англ.

26. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы и анализ / Пер. с англ. под ред. А. Шеня. М: МЦНМО, 2002. - 960 е.: 263 ил.

27. Крёнке Д. Теория и практика построения баз данных. Классика Computer Science. 8-е изд. СПб.: Питер, 2003. - 800 е.: ил.

28. Ласло Майкл. Вычислительная геометрия и компьютерная графика на С++: Пер. с англ. М.: «Издательство БИНОМ», 1997. - 304 е.: ил.

29. Лафоре Р. Объектно-ориентированное программирование в С++. Классика Computer Science. 4-е изд. СПб.: Питер, 2003. - 928 е.: ил.

30. Мейерс С. Эффективное использование STL. Библиотека программиста. СПб.: Питер, 2002. 224 е.: ил.

31. Скляров В.А. Язык С++ и объектно-ориентированное программирование. -Мн.: Выш. шк., 1997. 478 с.

32. Седжвик Роберт. Фундаментальные алгоритмы на С. Анализ/Структуры данных/Сортировка/Поиск/Алгоритмы на графах: Пер. с англ./Роберт Седжвик.- СПб: ООО «ДиаСофтЮП», 2003. 1136 с.

33. Страуструп Б. Язык программирования С++, 3-е изд./Пер. с англ. — СПб.; М.: «Невский Диалект» «Издательство БИНОМ», 1999. - 991 с. ил.

34. Ульман Дж. Основы систем баз данных / Пер. с англ. М.Р. Когаловского и В.В. Когутовского; Под ред. М.Р. Когаловского. М.: Финансы и статистика, 1983.-334 с. ил.

35. Ульман Джеффри Д., Уидом Дженнифер. Введение в системы баз данных.- Пер. с англ. М.: Издательство «Лори», 2000. - 376 е., ил.

36. Фаулер М. Рефакторинг: улучшение существующего кода. Пер. с англ. -СПб: Символ-Плюс, 2003.-432 е., ил.

37. Хансен Гэри, Хансен Джеймс. Базы данных: разработка и управление: Пер. с англ. М.: ЗАО «Издательство БИНОМ», 1999. - 704 е.: ил.

38. Atkinson Malcolm et al. The Object-Oriented Database System Manifesto. //Proc. First International Conference on Deductive and Object-Oriented Databases,

39. Kyoto, Japan (1989). New York, N.Y.: Elsevier Science (1990).

40. Bagui Sikha. Achievements and Weaknesses of Object-Oriented Databases. //Journal of Object Technology (JOT), vol. 2, no. 4, July-August 2003. -p. 29-41.

41. Celko Joe. A Look at SQL Trees. //DBMS, 1996, March. http://www.dbmsmag. com/9603d06.html

42. Celko Joe. Trees in SQL. //DBMS, 1996, April. http://www.intelligententerprise. com/001020/celko.jhtml

43. Celko Joe. Nontraditional Databases. //DBMS, 1996, May. http://www. dbmsmag. com/9605d06 .html.

44. Chamberlin Donald. Anatomy of an Object-Relational Database. //DB2 Magazine, Winter 1996, Vol. 1, No. 1.

45. Codd E.F. Extending the Database Relational Model to Capture More Meaning. //ACM Transactions on Database Systems, Vol. 4, # 4, December 1979. p. 397-434.

46. Darwen Hugh, Date С J. The Third Manifesto. //SIGMOD Record, Vol. 24, No.1, March 1995.-p. 39-49.

47. Eisenberg Andrew, Melton Jim. Standards In Practice. //SIGMOD Record, Vol.27, No.3, September 1998.

48. Graefe Goetz. Dynamic Query Evaluation Plans: Some course corrections? //Bulletin of the Technical Committee on Data Engineering, June 2000, Vol. 23, No.2, IEEE Computer Society.

49. Kim Won. Object-Oriented Databases: Definition and Research Directions //IEEE Trans. Data and Knowledge Eng.- 2, N 3.- 1990.- p. 327-341.

50. Kim Won. On Three Major Holes in Data Warehousing Today. //Journal of Object Technology (JOT), vol.1, no. 4, September-October 2002 p. 39-47.

51. Kim Won. A Retrospection on Niche Database Technologies. //Journal of Object Technology (JOT), vol. 2, no. 2, March-April 2003.- p. 35-42.

52. Kimball Ralph. Help for Hierarchies. //DBMS, 1998, September. http://www.dbmsmag.com/9809d05.html.

53. Silbershatz Avi, Zdonik Stan. Database Systems Breacking Out of the Box. //SIGMOD Record, v.26, no.3, September 1997.

54. Smith John Miles, Smith Diana C.P. Database Abstractions: Aggregation and Generalization. //ACM Transactions on Database Systems, Vol. 2, No. 2, June 1977-p. 105-133.

55. Stonebraker Michael et al. Third Generation Database System Manifesto //ACM SIGMOD Record 19, 3 (September 1990).

56. Андреев A.M., Березкин Д.В., Кантонистов Ю.А. Среда и хранилище: ООБД. //Мир ПК, 1998, №4.- С.74.

57. Андреев A.M., Березкин Д.В., Кантонистов Ю.А. Выбор СУБД для построения информационных систем корпоративного уровня на основе объектной парадигмы. //СУБД, 1998, №4-5.- С. 2.

58. Андреев Арк., Березкин Дмитрий, Самарев Роман. Внутренний мир объектно-ориентированных СУБД. //Открытые системы, 2001, №3- С. 47-57.

59. Барон Г.Г. Параллельные архитектуры серверов баз данных. //СУБД, 1995, №2. С. 32-44.

60. Беренсон X., Бернштейн Ф., Грэй Д., Мелтон Д., О'Нил Э., О'Нил П. Критика уровней изолированности в стандарте ANSI SQL. //СУБД, 1996, №2.-С. 45.

61. Бич Д. К объектным базам данных. //Открытые системы, 1994, №4- С. 50.

62. Блынский Л.Г., Курганов В.Ю. Моделирование иерархических структур в реляционных базах данных. //Приборы и системы. Управление, контроль, диагностика. 2003, № 9 С. 1-5.

63. Бодягин Иван. Автоинкременты и все, все, все. //RSDN Magazine, 2004, №1.-С. 38, 49,71,88,94.

64. Брюхов Д.О., Задорожный В.И., Калиниченко Л.А., Курошев М.Ю., Шумилов С.С. Интероперабельные информационные системы: архитектуры и технологии. //СУБД, 1995, №4.- С. 45.

65. Веселов Валерий, Долженков Анатолий. Семантическое сравнение реляционных и XML-языков. //Открытые системы, 2001, № 2 С. 60-64.

66. Веселов Валерий, Долженков Анатолий. Опыт построения XML-СУБД. //Открытые системы, 2002, № 6 С. 50.

67. Вьюкова Н.И., Галатенко Н.И. Информационная безопасность систем управления базами данных. //СУБД, 1996, №1- С. 29-54.

68. Голосов А.О. Аномалии в реляционных базах данных. //СУБД, 1996, №3.-С. 23.

69. Горохов Дмитрий, Чернов Владимир. Методы организации хранения данных в СУБД. //Открытые системы, 2003, №3.- С. 64.

70. Грачев А. Объектно-реляционная СУБД Informix Universal Server. //СУБД, 1998, №1-2,-С.13.

71. Грей Джим. Управление данными: Прошлое, Настоящее и Будущее. //СУБД, 1998, №3- С. 71.

72. Грибачев Константин. Тонкие базы данных и инструменты для их разработки в Delphi и С++ Builder. //КомпьютерПресс, 2003, №7 С. 175.

73. Григорьев Евгений. Представления идентифицируемых сложных объектов в реляционной базе данных. //Открытые системы, 2000, № 1-2 — С. 79.

74. Гринев Максим. Системы управления полуструктурированными данными //Открытые системы, 1999, №5-6 С. 9.

75. Гринев Максим, Кузнецов Сергей, Фомичев Андрей. Особенности СУБД Sedna. //Открытые системы, 2004, №8 С. 36-43.

76. Девитт Д., Грэй Д. Параллельные системы баз данных: будущее высоко эффективных систем баз данных. //СУБД, 1995, №2 С. 8-31.

77. Зильбершатц Ави, Стоунбрейкер Майк, Ульман Джефф. Базы данных: достижения и перспективы на пороге 21-го столетия. //СУБД, 1996, №3- С. 103.

78. Зиндер Е.З. Проектирование баз данных: новые требования, новые подходы. //СУБД, 1996, №3.- С. 10.

79. Зиндер Е. СУБД и действительно большие системы. //СУБД, 1997, №4-С.61.

80. Зиндер Е.З. Введение в экспертное оценивание информационных систем и СУБД. //СУБД, 1998, №4-5.- С. 5.

81. Калиниченко Б.О. Асинхронное тиражирование данных в гетерогенных средах. //СУБД, 1996, №3.- С. 118.

82. Калиниченко Л.А. Стандарт систем управления объектными базами данных ODMG-93: краткий обзор и оценка состояния. //СУБД, 1996, №1.- С.46.

83. Калиниченко Л.А., Когаловский М.Р. Стандарты OMG: Язык определения интерфейсов IDL в архитектуре CORBA. //СУБД, 1996, №2,- С. 115.

84. Ким Е.К., Шабаев И.Г., Бычков В.А. Проектирование трехмерных баз данных в СУБД uniVerse. //СУБД, 1996, №3.- С. 66.

85. Ким Вон. Технология объектно-ориентированных баз данных. //Открытые системы, 1994, №4 С. 30.

86. Ким Вон, Гарза Жорж Ф., Грэхэм Брюс. Пути развития объектно-реляционных технологий баз данных. //СУБД, 1996, №4.- С. 36.

87. Кимбалл Ральф. Манипулируя «родителями». //Enterprise Partner, № 20, 30 октября 2001.-С. 32-33.

88. Когаловский М.Р. Абстракции и модели в системах баз данных. //СУБД, 1998, №4-5,-С. 7.

89. Козленко Лилия. Введение в управление транзакциями: Часть 1. //Открытые системы, 2002, №4- С. 67.

90. Козленко Лилия. Введение в управление транзакциями: Часть 2. //Открытые системы, 2002, №5.- С. 58.

91. Козленко Лилия. Введение в управление транзакциями: Часть 3. //Открытые системы, 2002, №11- С. 62-65.

92. Хаф-Козленко Лилия. Введение в управление транзакциями: Часть 4. //Открытые системы, 2003, №2.- С. 59.

93. Козловский Александр. Объектные СУБД: ситуация смены парадигмы. //BYTE/РОССИЯ, 2000, №8.- С. 16-29.

94. Коржов В. Базы данных идут в тираж: Обзор известных механизмов тиражирования и их доступность в SQL Server 7.0. //СУБД, 1998, №3.- С. 60.

95. Кролик Юрий. Jasmine первая полномасштабная ОСУБД. //BYTE/РОССИЯ, 2000, №1.- С. 89-92.

96. Кузнецов С.Д. Направления исследований в области управления базами данных: краткий обзор. //СУБД, 1995, №1- С. 10.

97. Кузнецов С.Д. Введение в СУБД: Часть 1. //СУБД, 1995, №1.- С. 5.

98. Кузнецов С.Д. Введение в СУБД: Часть 2. //СУБД, 1995, №2.- С. 5.

99. Кузнецов С.Д. Введение в СУБД: Часть 3. //СУБД, 1995, №3.- С. 5.

100. Кузнецов С.Д. Введение в СУБД: Часть 4. //СУБД, 1995, №4.- С. 5.

101. Кузнецов С.Д. Введение в СУБД: Часть 5. //СУБД, 1996, №1.- С. 5.

102. Кузнецов С.Д. Введение в СУБД: Часть 6. //СУБД, 1996, №2.- С. 130.

103. Кузнецов С.Д. Операционные системы для управления базами данных. //СУБД, 1996, №3.-С. 95.

104. Кузнецов Семен. Проблема качества баз данных для САПР. //Открытые системы, 2004, №6.- С.78.

105. Лаврентьева Т.Г., Шабаев И.Г. UNIVERSE Развитие реляционных стандартов. //СУБД 1995, №2.- С. 17.

106. Ладыженский Г.М. Системы управления базами данных коротко о главном: Часть 1. //СУБД, 1995, №1,- С. 6.

107. Ладыженский Г.М. Системы управления базами данных коротко о главном: Часть 2. //СУБД, 1995, №2.- С. 6.

108. Лашманов А.В. ORACLE история, состояние и перспективы. //СУБД 1995, №1.-С. 12.

109. Липаев Владимир. Анализ качества баз данных. //Открытые системы, 2002, №3.- С. 54-57.

110. Маслов Д.В. Модель баз данных для хранения и обработки упорядоченных данных в АСУТП и экономических приложениях. //Промышленные АСУ и контроллеры, 2003, №12 С. 42-46.

111. Медников А.Ю., Соловьев А.Ю. Объектно-ориентированные базы данных сегодня или завтра? //Открытые системы, 1994, №4 С.21.

112. Михеенков М.Н. Порождение уникальных идентификаторов записей вбазах данных. //СУБД, 1995, №1.- С. 15.

113. Никитина Галина. SQL Server и кластеры. //СУБД 1998, №3.- С.65.

114. Палей Дмитрий. Моделирование квазиструктурированных данных. //Открытые системы, 2002, № 9 С. 57.

115. Пржиялковский В. Новые одежды знакомых СУБД: Объектная реальность, данная нам. //СУБД, 1997, №4.- С. 88.

116. Пржиялковский В.В. Абстракции в проектировании БД. //СУБД, 1998, №1-2,-С. 90.

117. Программисты следующего десятилетия. //Открытые системы, 2001, №12 -С. 60-73.

118. Рузинкевич М., Цикоцки А. Определение и выполнение потоков транзакций: Часть 1. //СУБД, 1995, №2.-С.18.

119. Рузинкевич М., Цикоцки А. Определение и выполнение потоков транзакций: Часть 2. //СУБД, 1995, №4.- С.18.

120. Рябенко Максим. Проектирование каталога. //Открытые системы, 2002, № 2.-С. 70-72.

121. Сахаров А.А. Принципы проектирования и использования многомерных баз данных (на примере Oracle Express Server). //СУБД, 1996, №3- С.44.

122. Синягов С.А. Построение и репроектирование баз данных. Интеграция инструментов и интерфейсов. //СУБД, 1996, №3- С.60.

123. Стоунбрейкер Михаэл. Объектно-реляционные системы баз данных. //Открытые системы, 1994, №4- С. 43.

124. Стулов Александр. Особенности построения информационных хранилищ. //Открытые системы, 2003, №4 С. 76.

125. Тендер Анатолий. БД хранилище объектов, http://www.podgoretsky.com/ cgi-bin/dlcounter/npscnt?file=http://podgoretsky.com/ftp/Docs/Delphi/Tenser/6.zip& fileid=Tenser6.

126. Тенцер Анатолий. Естественные ключи против искусственных ключей. http://www.ibase.ru/devinfo/NaturalKeysVersusAtrificialKeysByTentser.html 129.Чаудхари С. Методы оптимизации запросов в реляционных системах. //СУБД, 1998, №3.-С. 22.

127. Чен Петер Пин-Шен. Модель "сущность-связь" шаг к единому представлению о данных. //СУБД, 1995, №3 - С. 271.

128. Черняк Леонид. Навстречу системам хранения неструктурированных данных. //Открытые системы, 2004, №3- С.40.

129. Чикало О. В. Применение SQLBench для тестирования серверной части клиент-серверных приложений. //СУБД, 1996, №3.- С.77.

130. Шаргин А. Использование WTL. По адресу http://www.rsdn.ru/ в разделе Статьи\>УТЬ\Использование WTL.

131. Шринивасан В., Чанг Д.Т. Долговременное хранение объектов в объектно-ориентированных приложениях. //Открытые системы, 1999, №3.- С. 8.

132. Шуленин A. Microsoft SQL Server 7.0. Обзор новой функциональности. //СУБД, 1998, №3.-С. 6.

133. Шуленин А. Процессор запросов Microsoft SQL Server: О некоторых стратегиях оптимизатора при построении сложных, параллельных и распределенных планов. //СУБД, 1998, №3- С. 37.

134. Эйзенберг Эндрю, Мелтон Джим. SQL: 1999, ранее известный как SQL3. //Открытые системы, 1999, №1.-С. 52.

135. Гладков М.В., Абдулов Д.В. Реализация демонстрационных примеров в АОС по курсу «Компьютерной графики». //Тез. докл. Студенческоймежвузовской научной конф. «Гуманитарные науки в системе высшего образования». Пенза, ПТУ, 2001.- С. 334-335.

136. Шибанов С.В., Гладков М.В., Абдулов Д.В. Автоматизация разработки обучающих систем. //Тез. докл. V междунар. научно-методической конф. «Университетское образование». Пенза, ПГУ, 2001.- С. 111-112.

137. Шибанов С.В., Гладков М.В. Проблемы построения программных тренажеров. //Тез. докл. VI междунар. научно-методической конф. «Университетское образование». Пенза, ПГУ, 2002.- С. 60-62.

138. Гладков М.В., Шибанов С.В., От электронных учебников к программным тренажерам. //Телекоммуникации и информатизация образования, 2002, №4 (июль-август).- С. 49-56.

139. Гладков М.В. Система несоответствий программного обеспечения. //Тез. докл. VII междунар. научно-методической конф. «Университетское образование». Пенза, ПГУ, 2003.- С. 395-396.

140. Гладков М.В., Свешников В.А., Шибанов С.В. Информационная система «Приемная руководителя». //Телекоммуникации и информатизация образования, 2003, №2 (март-апрель).- С. 63-71.

141. Гладков М.В. Шибанов С.В. Сложные структуры в реляционных базах данных. //Открытые системы, 2004, №2 С. 62-67.