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

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

1

Полтавцева Мария Анатольевна

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

Специальность 05 13 01 - Системный анализ, управление и обработка информации (в промышленности)

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

□□317 1309

003171309

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

/

Полтавцева Мария Анатольевна

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

Специальность 05 13 01 - Системный анализ, управление и обработка информации (в промышленности)

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

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

Научный руководитель

Доктор технических наук, профессор, Григорьев Вадим Алексеевич

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

Семенов Николай Александрович

Кандидат технических наук Орлов Юрий Петрович

Ведущая организация

ОАО «Редкинское опытно-конструкторское бюро автоматики»

Защита состоится 27 июня 2008 г в 14-00 на заседании диссертационного совета Д 212 262 04 в Тверском государственном техническом университете по адресу 170026, г Тверь, наб Аф Никитина, 22 в аудитории 212

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

Автореферат размещен на сайте ТГТУ, адрес http //www tstu n.i'r.ew_struct/phd/2706200S zip Автореферат разослан 24 utaJ 2008 г

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

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

ФилатоваН Н

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

Актуальность проблемы

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

Особое место занимает так называемая нормативно-справочная информация, или основные данные (master data) словари, справочники и классификаторы описываюшие ключевые понятия бизнеса (объекты и субъекты деятельности компании или организации) От их точности и согласованности зависит функционирование практически всех бизнес приложении и аналитических систем Например, американские компании ежегодно тратят ботыде 600 мчрд долт па обеспечение качества данных и, по оценкам Gartner, к 2010г бочее 70% компаний из списка Fortune 1000 реализуют программы по управлению основными данными как часть корпоративной стратегии управления информацией

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

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

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

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

1 Анализ и систематизация основных методов структурирования информации, предлагаемой дтя хранения в речяционной СУБД Выбор методов структурирования для исследования

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

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

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

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

2 Исследовать задачи хранения классифицированной и иерархически организованной информации в реляционных серверах и возможности взаимного отражения соответствующих схем

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

4 Использовать полученные результаты для предложения рациональных схем хранения графов и сетей

5 Объединить выбранные методы и схемы в методику принятия решений и обработки информации при отображении структурированной информации в реляционные схемы

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

Методы исследования включают

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

2 Аналитико-экспериментальные методы - вычислительный эксперимент в виде имитационного моделирования на ЭВМ объектов и задач исследования

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

Научная новизна Соискателем получены следующие ре{ультаты, имеющие научную новизну

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

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

3 Предложены новые алюритмы хранения информации, представленной в виде графов и сетей Схему хранения предлагается создавать на основе алгоритма представления графа в виде леса деревьев с независимой и сквозной нумирацией на основе метода вложенных множеств

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

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

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

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

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

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

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

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

корпоративных информационных систем Они могут быть также использованы разработчиками СУБД - реляционных, XML, объектных

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

Апробация работы Работа докладывалась на XVII Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании», Пенза, май 2006т, XX Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании», Пенза, декабрь 2007г, юбилейной научно-практической конференции ТГТУ "Региональная система профессионального технического образования", Тверь, ТГТУ, декабрь 2007г

Публикации Основные положения диссертации опубликованы в 8-ми печатных работах, в том числе 2 статья в журнале из перечня ВАК

Структура и объемы работы. Диссертационная работа состоит из введения, четырех глав, заключения, двух приложений и списка литературы Общий объем диссертации 181 страница, в том числе 61 рисунка, 19 таблиц, список литературы из 127 наименований

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

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

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

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

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

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

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

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

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

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

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

процедуру нормализации Реляционная модель не поддерживает сколь-нибудь развитую семантику межобъектных отношений Поэтому на данном этапе происходит искажение модели прикладного домена, и появляется несоответствие между моделью предметной области и моделью данных (тн "mismatching impedance")

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

Структуры данных

"Простые данные

Числа Символы итд

Записи

Записи

Записи с вариантами

X

Массивы

Векторы Массивы Множества Таблицы Строки

т

Списки Деревья Ц Графы |

Стеки Очереди Деки Слиски Деревья | Графы |

Рисунок 1 Классификация структур данных в соответствии с используемой схемой хранения

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

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

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

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

Деревья используются дтя описания наиболее часто встречающейся в семантических моделях структуры - иерархии При работе с деревьями возникает четко очерченный круг задач, выполняющихся с разной частотой в зависимости от приложения в делом Приложение по работе с деревьями Г в том числе моделирование в РСУБД) должно предоставлять возможность работы со всеми из них, с той или иной эффективностью в зависимости от задачи в целом добавить/удалить узел дерева, найти узел внутри дерева, определить, является ли данный элемент терминальным (листом), определить, на каком уровне иерархии находится заданный элемент, подсчитать количество всех потомков у данного элемента, получить список всех потомков какого-нибудь элемента, при этом с разными условиями например, только терминальных, или, находящихся только на определенном уровне или всех потомков заданного элемента, у которых нет детей, получить всех предков данного элемента Распространенная задача - "выполнение заданной операции Р с каждым элементом дерева" Здесь Р рассматривается как параметр более общей задачи посещения всех узлов, или, как это обычно называют обход дерева В том или ином виде операция обхода дерева присутствует во всех задачах, работающих с деревьями

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

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

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

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

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

Node

РК J Node Id int

FK< ParonlKi J NwtoDau in« СПзг(10)

Рисунок 2 Схема хранении иерархии со1ласно модели списка смежных вершин

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

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

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

Таблица 1 Сравнение схем хранения

Матрица смежности [Метод вложеппйть множести - ~ " Метод '

Определение терминальности узла : HtaSaaFe Г '.j

Лист явчяется терминальным если у нею нет ни одного потомка Описание "С

~ЭС (С parent = "Узел Ю") ~3D(D parent = "Узел ID"j Релядиогшос выражение"

Select С ID From Tree where No Exibt С parent = ID Select D ID From Tree where No Exist D parent = ID Запись на языкгаапросов

C-3C ID(C Parent=C ID)(C) 0-3D ID(D Pareit~D ID)(,D) ^j iCpitUii'' ЫОКПС7" - . алгебрьГ -г , г Г

Считывание табт С в память Считывание табл D в память - Операции с цискш~""" ,

и,=м2 U2-=Mi Число операций с-диском

^ М7 Матрица смелности выгодней в л =-=--раз U, М] Результат - -

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

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

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

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

ТаЫе Nodes

РК NodelD

NorteData

ТаЫэ Ribs

РК IPRtt?

HS1 FK2 IDMocielr IDNodeOut RjbData

Рисунок 3 Схема хранения графа списком узлов и списком ребер

В этом случае Ш СШ и 1Ц_1п соответствующие обозначениям входящих и исходящих вершин по матрице соответствуют ГО_е1 соответствующих узлов графа в основной таблице с данными (рисунок 3)

Случаи хранения графа с использованием связного (списочного) представления сводится к хранению структуры, напоминающей нелинейный разветвленный список Получаемая структура имеет два типа элементов (элемент графа - ссылка) и (ссылка-ссылка) Тем не менее, полученная структура нелинейным разветвленным списком не является, так как в ней могут наличествовать петли и обратно направленные связи (рисунок 4)

Li

6 ^

W

Рисунок 4 Представление графа нелинейным списком

Связи 13->В и Б->С не соответствуют представлению в виде дерева и не соответствуют теории нелинейных разветвленных списков

Реляционная схема хранения приведена на рисунке 5 Основные данные (элементы списка) хранятся в таблице «Граф» Связанная таблица «Граф элементы графа» используется совместно с основной для отдельного хранения элементов, отсутствующих в случае сочетаний ссылка-ссылка Поле «Туре» имеет бинарное значение 0-ссылка-элемент, 1-ссылка-ссылка

Граф

РК (а

РК1 Туре 10 М<1 10

| Граф эпесгаитч графа ->|рк il.Dji.i~

¡0^1

Рисунок 5 Схема хранения графа в виде нечинейного списка

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

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

МашТаЫе ЭесопйТаЫе

РК РК ГОЫойе 1ИХ££ РКРК1 РК.РК2 РКРКЗ юс мм ЮРагеШ Шйее

РК1 ГОРэгеШ

Рисунок 6 Схема хранения графа в виде леса деревьев по методу матрицы

смежности

Во втором случае, согласно методу вложенных множеств (МВМ) каждому элементу иерархии в зависимости 01 его места в ней присваиваются два числовых значения левое и правое Каждое дерево, входящее в граф, получает эти значения независимо от структуры самого графа (рисунок 7)

Рисунок 7 Независимая нумерация поддеревьев графа

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

- ТЗиисКта РК1 ю РЫойа

Рисунок 8 Схема хранение графа в виде леса деревьев по методу вложенных множеств

Логично использовать для всех деревьев графа единую, сквозную

Рисунок 9 Сквозная нумерация поддеревьев графа

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

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

Результаты проведенною сравнения представлены в сводной таблице Выделены наилучшие варианты хранения на каждом лапе (таблица 2)

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

Таблица 2 Сравнение схем хранения графов

Метод Списки ребер и вершин Лес деревьев и метод матрицы смежности Лес дер и метод вл мн (независ нумерация) Лес дер н метод вд мн (сквозная нумерация)

Добавление вершины U,=l U2= М3+1 U3=M3A1 U4=M3+1

Удаление вершины и,=1+2+М2 U2=- М^2*М3 +1 и -2*Мз U4=2*M3

Добавление дуги U,=l U2= Мз+Мз +1 U3=2'"M, U4=2*M3

Удаление дуги Url U;=М^М3 U4~ 2*Mj+2

Опредет смежности вершин и,=м2 U3=-M3 U4=M3

Определ инцидентности \ зла к ребру и-=м2 и2=о и,=о и4=о

Выделение вершин с только входными дугами и,=М|+М2 U;=M, li3=M3 U4=M3

Выделение вершин с. только выходными дугами UI-MkMZ и2=Мз Ь'з=Мз ЬГ4=М3

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

Рисунок 10 Диаграмма движения документа

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

определенного типа (например, проекту приказа или опубликованному приказу), нахождение пути документа определенного типа

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

Рисунок 11 Представление графа движения документа в виде леса деревьев

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

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

1 Проанализированы существующие способы структурирования информации и классифицированы по существующим методам хранения в реляционных СУБД, построена обобщенная классификация, которая может быть использована для выбора реляционных схем хранения

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

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

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

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

Дерево 4

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

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

7 Проведена экспериментальная проверка адекватности и состоятельности алгоритмов и методик

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОТРАЖЕНЫ В СЛЕДУЮЩИХ ПУБЛИКАЦИЯХ

1 ПолтавцеваМА Программные реализации схем представления структурированных данных в реляционной базе данных // Международный журнал "Программные продукты и системы" №1, - Тверь, 2008 - С 20-22

2 ПолтавцеваМА Сравнение методов вспомогательной таблицы и матрицы смежности при хранении иерархий в РСУБД // Сборник статей XIV Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образования»(МК-81-94)-Пенза, 2004 -С 394-396,

3 Потгавцева М А Хранение и обработка классификаторов и классифицированной информации // Вестник Тверского государственного технического университета Научный журнал Вып 7 - Тверь ТГТУ, 2005 -С 143-144,

4 ПолтавцеваМА Хранение иерархических структур в РСУБД -описание Паттерна проектирования // Сборник статей XVI Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социотогии и образовании» -Пенза, 2005 -С 423-426,

5 Полтавцева М А Применение методов хранения связанных иерархий к представтению сетевых структур в РСУБД // Сборник статей XVII Международной научно-технической конференции «Математические методы и информационные технотогии в экономике, социологии и образовании» -Пенза, 2006 -С 209-212,

6 Полтавцева М А Применение реляционных схем хранения слабоструктурированных данных в задачах автоматизации управленческой деятельности /'/' Становтение и развитие системы управления в России Сборник научных статей Вып 1 -Сыктывкар КРАГСиУ, 2007 -С 112-116,

7 Полтавцева М А Хранение в реляционной базе данных полустатпческих структур данных и списочных структур И Вестник Тверского государственного технического университета Научный журнал Вып 10 -Тверь ТГТУ, 2007 -С 239-241,

8 Полтавцева М А Использование алгоритма обхода графа в глубину при хранении графов в реляционной базе данных в виде леса деревьев // Сборник статей XX Международной научно-технической конференции «Математические методы и информационные техночопш в экономике, социологии и образовании» - Пенза, 2007 -С 265-267

Подписано в печать 21 05 08 Заказ № 51 Тираж 100 экз Физ печ л 1,0 Типография Тверского государственного технического университета 170026, г Тверь, наб А Никитина, 22

Введение.

Глава 1 Использование структурированной информации в информационных системах.

1.1 Системы библиотечного учета.

1.2 Системы геометрического моделирования.

1.2.1 Системы геометрического моделирования составных объектов.

1.2.2 Системы геометрического моделирования в САПР.

1.3 Специализированные задачи по предметным областям.

1.3.1 Системы экологического моделирования.

1.3.2 Системы автоматизированного делопроизводства.

1.4 Существующие схемы хранения структурированных сданных.

1.4.1 Хранение деревьев.

1.4.2 Хранение графов.

1.5 Выводы по первой главе.

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

2.1 Классификация структур данных.

2.2 2.2 Статические структуры данных.

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

2.4 Полу статические структуры данных.

2.5 Динамические структуры данных.

2.5.1 Списки.

2.5.2 Графы.

2.5.3 Деревья.

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

2.7 Выводы по второй главе.

Глава 3 Хранение сложных структур данных в РСУБД.

3.1 Особенности реляционных БД и структура данных в информационных системах .".

3.2 Хранение динамических списков в РСУБД.

3.2.1 Списки (линейные, мультисписки).

3.2.2 Нелинейные разветвленные списки.

3.3 Хранение деревьев в РСУБД.

3.4 Хранение графов в РСУБД.

3.4.1 Традиционное представление графов.

3.4.2 Представление графов в виде леса связанных деревьев.

3.5 Анализ способов представления графов.

3.6 Методика отображения семантической модели в логическую модель данных

3.7 Выводы по третьей главе.

Глава 4 Диаграмма движения приказа в организации.

4.1 Описание диаграммы движения приказа в организации.

4.1.1 Диаграмма движения приказа.

4.1.2 Определение задач по работе с диаграммой.

4.2 Представление диаграммы движения документа в виде ориентированного нагруженного графа и выбор схемы хранения.

4.2.1 Представление диаграммы движения документа в виде ориентированного нагруженного графа.

4.2.2 Выбор схемы хранения.

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

4.3.1 Описание представления диаграммы.

4.3.2 Реализация задач для представления в виде списка узлов и ребер.

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

4.4.1 Описание представления диаграммы.

4.4.2 Реализация задач для схемы хранения диаграммы движения документа в виде леса деревьев.

4.5 Сравнительный анализ результатов реализации.

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

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

Для хранения информации с развитием компьютерной техники применятся базы данных. Каждая из них построена на основании той или иной модели данных, определяющий способ формализации информации. С 80гг двадцатого века и по сей день наиболее широко используемой и единственной, имеющей математический аппарат для описания операций (реляционную алгебру и реляционное исчисление) является реляционная модель данных, предложенная Ф. Коддом [48, 49].

Реляционная модель данных обладает при всех достоинствах одним существенным недостатком: она является плоской [58]. Все данные в ней хранятся в виде связанных таблиц. Это вызывает существенные трудности при хранении в реляционной базе данных боле сложных структур: деревьев, графов [116].

Существует два традиционных метода хранения деревьев в РБД:

1. При помощи матрицы смежности [50]

2. При помощи матрицы смежности и вспомогательной таблицы [69]

Оба они произошли из традиционного представления деревьев [65]. Еще один метод был предложен Дж. Селко [3]. Автор разработал метод хранения деревьев на основе вложенных множеств, фактически использовав обход дерева в глубину для нумерации вершин дерева и применения этой нумерации в построении запросов к

БД.

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

Цель:

Создание наборов типовых решений для хранения в РСУБД сложных структур данных.

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

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

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

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

4. Практическая реализация представления разработанных структур в РСУБД.

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

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

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

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

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

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

1. Проведено сравнение существующих методов хранения деревьев в РСУБД и предложена методика выбора оптимальной схемы хранения в зависимости от исходной задачи.

2. Проведено исследование возможного представления дерева в РСБД со вспомогательной нумерацией на основании обхода дерева в ширину.

3. Разработаны схемы представления графов в РСУБД как на основании традиционных методик представления, так и представления в виде леса деревьев.

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

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

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

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

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

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

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

3.7 Выводы по третьей главе

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

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

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

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

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

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

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

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

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

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

Глава 4 Диаграмма движения приказа в организации 4.1 Описание диаграммы движения приказа в организации

4.1.1 Диаграмма движения приказа

Задача хранения диаграммы движения документов на примере диаграммы движения приказа. В типовом виде она может выглядеть так, как приведено на рисунке 4.1.

Рисунок 4.1 - Типовая диаграмма движения приказа в организации.

На диаграмме присутствуют:

Разработчика приказа - сотрудник, как правило специалист службы ДОУ (документационного обеспечения управления), которому поручается разработка документа.

Директор организации - лицо, уполномоченное подписывать приказ. Как правило, это руководитель организации.

Начальники подразделений (1 и 2) - начальники структурных подразделений, в обязанности которых входит доведение приказа до сотрудников и контроль его исполнения.

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

Каждый блок - элемент диаграммы связан с одним или несколькими другими блоками через движение рассматриваемого документа. Каждая связь представляет собой передачу конкретной бумаги:

Проекта приказа - передается от разработчика к начальнику и обратно, если проект нуждается в разработке.

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

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

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

4.1.2 Определение задач по работе с диаграммой

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

1. Добавление и удаление участника (сотрудника) - аналогично добавлению и удалению вершины графа.

2. Добавление и удаление пути документа — аналогично добавлению и удалению дуги в граф.

3. Определить, передается ли документ между двумя сотрудниками или конкретно от одного сотрудника к другому. Аналогично проверки смежности вершин(ы) и дуги.

4. Определить, кому передается документ от конкретного сотрудника. Соответствует определению всех смежных вершин по исходящим дугам.

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

6. Определить, кто имеет доступ к документу определенного типа (например, проекту приказа или опубликованному приказу). Фактически соответствует выборке вершин смежных с определенным типом ребер.

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

8. Найти путь документа определенного типа. Соответствует поиску подграфа по определенному признаку.

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

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

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

4.2 Представление диаграммы движения документа в виде ориентированного нагруженного графа и выбор схемы хранения

4.2.1 Представление диаграммы движения документа в виде ориентированного нагруженного графа

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

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

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

4.2.2 Выбор схемы хранения

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

Рисунок 4.2 - Графовое представление диаграммы

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

1. Добавление и удаление участника (сотрудника) - аналогично добавлению и удалению вершины графа;

2. Добавление и удаление пути документа - аналогично добавлению и удалению дуги в граф;

3. Определить, передается ли документ между двумя сотрудниками или конкретно от одного сотрудника к другому. Аналогично проверки смежности вершин(ы) и дуги;

4. Определить, кому передается документ от конкретного сотрудника. Соответствует определению всех смежных вершин по исходящим Дугам;

5. Определить, от кого передается документ конкретному сотруднику. Соответствует определению всех смежных вершин по входящим дугам;v

6. Определить, кто имеет доступ к документу определенного типа (например, проекту приказа или опубликованному приказу). Фактически соответствует выборке вершин смежных с определенным типом ребер;

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

8. Найти путь документа определенного типа. Соответствует поиску подграфа по определенному признаку;

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

Далее, согласно методике, определим преобладание задач первого и второго типа. Проанализируем информацию о диаграмме:

- Диаграмма строится в учебных целях и будет храниться в БД.

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

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

Так как задачи изучения хранимых диаграмм выполняются студентами в период обучения значительно чаще задач модификации (примерно в соотношении 5/2), выбор схемы хранения сводится к схемам 1,3, 4, т.е. списком вершин и списком ребер и в виде леса деревьев со сквозной и независимой нумерациями.

Далее, согласно методике, определим наличие задач, требующих обращения ко всем спискам узлов предшествующих или следующих за данным, далее, чем непосредственно (задачи типа 2(a)). К таким вопросам можно отнести выделенную задачу под номером 9. Так как задача типа 2 (а) наличествует, следовательно, схема хранения в виде списка вершин и списка ребер должна быть исключена.

Выбор схемы хранения сводится к выбору между схемами 3 и 4: представлением в виде леса деревьев на основании метода вложенных множеств со сквозной или независимой нумерацией. Мною предлагается использовать схему хранения со сквозной нумерацией, как более удобную для описания графа в целом.

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

4.3 Схема хранения в виде списка узлов и ребер 4.3.1 Описание представления диаграммы

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

Схема хранения представлена на рисунке 4.3.

TNode

РК N ID

NName NData

9 TRib

РК R ID

- FK1 FK2 N In ID NOutID RData RName

Рисунок 4.3 - Представление диаграммы движения документов в виде списка вершин и списка ребер.

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

Заключение

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

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

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

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

5. Представления статически структур в РСУБД однозначны и широко применяются. Реализация нескольких типовых операции с ними дана в приложении 1.

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

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

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

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

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

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

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

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

14. Число дисковых операций для независимой нумерации будет меньше, чем для сквозной, так как параметр М3 (число элементов поддерева) согласно исследованию меньше параметра Mi; (общее число элементов графа). Таким образом, схема с несвязанной нумерацией является1 более эффективной по этому критерию. Алгоритмические операции для; этого способа хранения используются: только в задачах поиска пути графа и их применение отчасти компенсируется; готовым опорным деревом графа, являющимся первым поддеревом в соответствии; с-предложенным алгоритмом разбиения.

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

16. Разработанное средство «Система построения диаграмм движения документов» на основании проведенного и описанного в третьей главе теоретического исследования отвечает требованиям поставленной задачи и применимо в учебном процессе факультета Управления и Социологии Тверского государственного университета, о чем свидетельствует акт внедрения разработки подписанный деканом факультет ФУС от 15:02.08.

1. Матьяш В.А., Путилов В.А., Фильчаков В.В. , Щёкин С.В. Структуры и алгоритмы обработки данных Апатиты, КФ ПетрГУ, 2000. - 80 с.

2. Далека В.Д., Деревянко А.С., Кравец О.Г., Л.Е.Тимановская «Модели и структуры данных» Учебное пособие ХарьковгХГПУ, 2000. 241 с.

3. Celko Joe. A Look at SQL Trees. //DBMS, March 1996. C.27 36.

4. Структуры данных для представления графов // http://www.algolib.narod.ru/

5. Графы. Основные алгоритмы // http://rain.ifmo.ru/cat/view.php /vis/graph-general

6. Черняк И.Н ЗАО «Виадук-Телеком» // http://www.viaduk.com

7. Учебный курс: Администратор «АС Библиотека 3» http://librarian.fio.ru

8. В.А. Гаврилова, Е.И. Боброва Научная библиотека культурно-образовательный центр (Кемеровский государственный университет культуры и искусств, к 35-летию) // «Библиотечная жизнь Кузбасса» Вып.2(48)-2005.-.-С.25-27.

9. Правительство РФ, Подпрограмма «Информатизация» // http://www.programs-gov.ru/ext/10/content. htm.

10. Артамонов Е.И., Высотин О.В., Разумовский А.И., Макаров A.M., Шурупов А.А. Объемное геометрическое моделирование орбитального комплекса "МИР" // http://lab 18.ipu.rssi.ru/default.htm

11. Трехмерная модель // http://www.novek.ru

12. Липатов А.Н. Опыт разработки и внедрения интегрированной САПР электроавтоматики Снежинск // http://labl8.ipu.rssi.ru/ projects/conf2005

13. Гранин В.Ю., Балушок К.Б., Спиридонов С.В., Паладийчук А.В. Подсистема геометричесого моделирования учебно промышленной САПР технологических процессов - Харьков, Украина // http://users.kpi.kharkov.ua

14. Болотов В.П., Сатаев А.Г.и Фрисман Е.Я. Компьютерная система оценки экологический ситуации в регионе // http://vm.msun.ru

15. Прохоров А. Я могу работать в современном офисе Интернет-университет информационных технологий ИНТУИТ.ру, 2005.

16. Пахчанян А. Технологии электронного документооборота // Открытые системы, №10 2002.

17. Описание СЭД «Ефрат» // http://www.evfrat.ru

18. Описание СЭД «Директум» // http://www.directum.ru

19. Полтавцева М.А. Применение реляционных схем хранения слабоструктурированных данных в задачах автоматизации управленческой деятельности // «Становление и развитие системы управления в Росиии» вып.1 -Сыктывкар: КРАГСиУ, 2007. С. 112-116

20. Кириллов В.В. Основы проектирования реляционных баз данных // Санкт-Петербургский Государственный институт точной механики и оптики (технический университет) Кафедра вычислительной техники // http ://www.citforum .ru/database/ dbguide/index. shtm 1

21. Кузнецов С. Д. Основы современных баз данных // Центр Информационных Технологий // http://ods.com.ua/win/rus/ db/osbd/contents.htm

22. Гвоздев А. Архитектура и функциональные возможности объектно-реляционной СУБД Illustra // Redlab http://ods.com.ua/ win/rus/db/kbd96/59.htm

23. Тихонова А.Н Информационные системы в образовании и научных исследованиях. Системный анализ // Под общей редакцией проф., ГОУ «Технопарк инноваций в науке и образовании» М. 2004

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

25. И. Братко Программирование на языке Пролог для искусственного интеллектам. «Мир» 1990.

26. Софт BPMSRU - Business Process Management (BPM) - программы для управления бизнес процессами, процессное управление, автоматизация бизнес-процессов // http://www.bpms.ru

27. Каменева И. Корпоративные информационные системы: технологии и решения // Системы управления базами данных №3 1995.

28. CitCity Деловая газета IT новостей // http://citcity.ru

29. Gary J. Nutt The evolution toward flexible workflow systems» Departament of Computer Science University of Colorado // http://citcity.ru

30. Casati F., Ceri S. Workflow evolution // "Dipartimento di Elettronica e Informazione Politecnico di Milano // http://citcity.ru

31. Ефимова О. Средства workflow в рамках общей концепции управления предприятием // http://www.russianenterprisesolutions.com

32. Кротский С. Концепции построения комплексных информационных систем // http://www.russianenterprisesolutions.com

33. Федосеев А. Автоматизированная система управления бизнес-процессами // http://intalev.com.ua

34. Кузнецов С. Проектирование и разработка корпоративных информационных систем // http://citforum.ru

35. Гавердовский А. Концепция построения систем автоматизации документооборота//БИТ-Петербург 1999-2001. http://www.big.spb.ru

36. Abiteboul S., Buneman P., and Suciu D., Data on the web: From Relations to Semistructured Data and XML // Morgan Kaufman, 1999.

37. Barker R. CASE*Method: Entity Relationship Modelling, // S.I.: Addison-Wesley Publishing Company,- 1990.

38. Bray Т., Paoli J., and (eds) Sperberg McQueen C.M., Extensible Markup Language (XML) 1.0 // W3C Recommendation 2 edition // http://www.w3.org/TR/REC-xml-20001006.

39. Badia A. Conceptual Modeling for Semisrtuctured Data // Third International Conference on Web Information Systems Engineering (Workshops). 2002.

40. Ковалев C.M. Бизнес-процессы, основные стандарты их описания // Справочник экономиста №11 2006.

41. Программы сибирского отделения РАН по приоритетным направлениям развития науки и техники. // http://old.ict.nsc.ru/rus/sci/rep99/3-soranl.htm

42. Halpin Т., Information Modeling and Relational Datadases: from conceptual analysis to logical design // Morgan-Kaufmann, San Francisco, 2001.

43. ISO, Terminology for the Conceptual Schema and Information Base. // ISO Technical Report TR9007, 1982.

44. Date, C.J. Support for the Conceptual Schema: The Relational and Network Approaches // In C.J. Date, Relational Database Writings 1985-1989. Reading, Mass.: Addison-Wesley 1990.

45. Codd, E.F. Normalized Data Base Structure: A Brief Tutorial // Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access; and Control, San Diego, Calif. November 11th-12th, 1971.

46. Date, C.J. Why Relational? // In C.J. Date, Relational Database Writings 1985-1989. Reading, Mass.: Addison-Wesley 1990.

47. Туккель H. И., Шалыто A. A.,SWTCH-тexнoлoгия автоматный подход к созданию программного обеспечения // http://www.21ib.ni/getbook/l 1098.html

48. Donald Е. Knuth The Art of Computer Programming, vol.1. Fundamental Algorithms, Volume 4 A C, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions 2007. - 720 p.

49. Date, C.J. Don't Mix Pointers and Relations! and Don't Mix Pointers and Relations Please! // In C.J.Date, Hugh Darwen, and David McGoveran: Relational Database Writings 1994-1997. Reading, Mass.: Addison-Wesley, 1998.

50. Date, C.J. and Hugh Darwen. Foundation for Object/Relational Databases // The Third Manifesto. Reading, Mass.: Addison-Wesley, 1998.

51. Codd, E.F. Extending the Relational Database Model to Capture More Meaning. // IBM Research Report RJ2599 1979. Republished in ACM Transactions on Database Systems 4(4) 1979.

52. Codd, E.F. The Relational Model for Database Management Version 2.// Reading, Mass.: Addison-Wesley, 1990.

53. Date, C.J. The Extended Relational Model RM/T // In C.J.Date, Relational Database Writings 1991-1994. Reading, Mass.: Addison-Wesley, 1995.

54. Date, C.J. and Hugh Darwen. A Guide to the SQL Standard (4th edition) // Reading, Mass.: Addison-Wesley, 1997.

55. Date C.J. The relational model will stand the test of time // Intelligent Enterprise, June 1, 1999, Volume 2, Number 8 // www.intelligententerprise.com/992206/online 1 .shtml

56. Codd, E.F. Extending the Relational Database Model to Capture More Meaning. // IBM Research Report RJ2599 1979. Republished in ACM Transactions on Database Systems 4(4), December 1979.

57. Codd, E.F. A Data Sublanguage Founded on the Relational Calculus. // IBM Research Report RJ893 1971. Republished in Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access and Control, San Diego, November 1971.

58. Д. Кнут Искусство программирования Т. 1-3. М. «Диалектика -Вильяме» 2007. - 720 с.

59. Codd, E.F. Recent Investigations into Relational Data Base Systems. // IBM Research Report RJ1385 1974. Republished in Proc. 1974 Congress 1974. New York, N.Y.: North-Holland, 1974.

60. Codd, E.F. Relational Database: A Practical Foundation for Productivity. // IBM Research Report RJ3339 1981. Republished in CACM 25(2), February 1982.

61. Stonebraker, Michael. Introduction to Chapter 1 ("The Roots"). // Readings in Database Systems (2nd edition). San Mateo, Calif.: Morgan Kaufmann, 1994.

62. Codd, E.F. A Relational Model of Data for Large Shared Data Banks. // CACM 13(6), June 1970. Republished in Milestones of Research ~ Selected Papers 19581982 (CACM 25th Anniversary Issue), CACM 26(1), 1983.

63. Codd, E.F. Is Your DBMS Really Relational? // Does Your DBMS Run By The Rules? Computerworld 1985; October 21st, 1985

64. Codd, E.F. The Relational Model For Database Management Version 2. Reading, Mass.: Addison-Wesley, 1990.

65. Date, C.J. and Hugh Darwen. Foundation for Object/Relational Databases: The Third Manifesto. Reading, Mass.: Addison-Wesley, 1998.

66. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных СУБД // Тем. изд. "Итоги науки и техники. Вычислительные науки". Т.1.-С. 76-153.

67. Atkinson М., Bansilhon F., DeWitt D., Dittrich К., Maier D., Zdonik S. The Object-Oriented Database System Manifesto // 1st Int. Conf. Deductive and Object-Oriented Databases, Kyoto, Japan, Dec. 4-6, 1989.

68. Кагаловский Абстракции и модели в системах баз данных // СУБД 4-51998/

69. Бойко В.В., Савинков В.М. Проектирование информационной базы автоматизированной системы на основе СУБД. М.: Финансы и статистика. 1982. — 174 с.

70. Вендров A.M. CASE-технологии. Современные методы и средства проектирования информационных систем. М.: Финансы и статистика, 1998. - 176 с.

71. Вейнеров ОМ., Самохвалов Э.Н. Проектирование баз данных САПР. -М.: Высшая школа, 1990.- 144 с.

72. Т. Бадд Объектно-ориентированное программирование в действии // СПб «Питер» // http://www.piter.com/lib/978588782270/oop.phtml

73. Когаловский М.Р. Проблемы терминологии в теории систем баз данных //УСиМ, 6, 1986, С. 85-92.

74. Когаловский М.Р. Архитектура механизмов отображения данных в многоуровневых СУБД // Техника реализации многоуровневых систем управления базами данных. М.: ЦЭ-, МИ АН СССР, 1982, С. 3-19.

75. Когаловский М.Р. Технология баз данных на персональных ЭВМ. М.: Финансы и статистика, 1992. — 224 с.

76. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. -392 с.

77. Михновский С.Д. Автоматизация проектирования баз данных. Общий анализ проблемы // УСиМ, 4, 1981, С. 35-44.177

78. Пржиялговский В.В. Абстракции в проектировании баз данных // СУБД, 1-2 1998. -С. 90-97.

79. Савинков В.М., Вейнеров О.М., Казаров М.С. Основные концепции автоматизации проектирования баз данных //Прикладная информатика. Вып.1. М.: Финансы и статистика, 1982, - С. 30-41.

80. Цикритзис Д., Лоховски Ф. Модели данных // Пер. с англ. М.: Финансы и статистика, 1985. - 344 с.

81. Шрейдер Ю.А., Шаров А.А. Системы и модели. М.: Радио и связь. 1982. - 152 с.

82. ANSI/X3/SPARC Study Group on Data Base Management Systems. Interim Report. FDT Bull. ASM-SIGMOD. v. 7, no. 2 1975, p. 1-140.

83. Chen P.P. The entity-relational model. Toward a unified view of data //A CM TODS, no. 1, 1976, p. 9-36. Есть русский пер.: Питер Пин-Шен Чен. Модель «сущность-связь» шаг к единому представлению данных, //СУБД, 3/1995, С. 137158.

84. Евстигнеев В.А. Применение теории графов в программировании // М. Наука 1985.-352 с.

85. Codd E.F. A relational model of data for large shared data banks//Comm. ACM, v. 13, no. 6, 1970. p. 377-387. Есть русский пер.: Е.Ф. Кодд. Реляционная модель данных для больших совместно используемых банков данных //СУБД, 1/95, С. 145-160.

86. Codd E.F. Relational database: a practical foundation for productivity //Comm. ACM, v. 25, no. 2, 1982, p. 109-117.

87. Concepts and terminology for the conceptual schema and the information base. Ed. by J.J. van Griethuyzen. ISO TC97/SC5/WG3. 1982. Publ. no. 695. - 188 p.

88. Date C.J. An Introduction to Database Systems. Sixth Edition, Addison Wesley, 1995. Есть русский пер.: Крис Дейт. Введение в базы данных. Шестое издание. — Киев: Диалектика, 1998.

89. Kalinichenko L.A. SYNTHESIS: A language for specification, design and programming of the heterogeneous interoperable information resource environments. Russian Academy of Sciences. Institute for Problems of Informatics. Moscow, 1995.

90. Kogalovsky M.R. Some terminological problems of data base systems // Proc. of the Sixth International Seminar on Database Management Systems. Oct. 24-29, 1983, Matrafured, Hungary. Budapest, SZAMALK, 1983, p. 9-16.

91. Langefors B. Infological model and information user views // Inform. Systems, no. 5, 1980, p. 17-32.

92. Langefors B. Information systems // Information Processing-74. Amsterdam: North-Holland. 1974, p. 937-945.

93. Sibley E.H., Hardgrave W.T., Kogalovsky M.R., Makalsky K.I. A conceptual model to support multi-model external views. Data Models and Database Systems. Proc. of the Joint US-USSR Seminar, Austin, Texas. October 25-27, 1979, p. 146-185.

94. Smith J.M. and Smith D.C.P. Database Abstraction: Aggregation and Generalization //ACM TODS, v. 2, no. 2, p. 105-133. Есть русский пер.: Джон М. Смит, Диана К. Смит. Абстракции баз данных.: Агрегация и обобщение. СУБД, 2/96, С. 141-160.

95. Smith J.M. and Smith D.C.P. Database Abstraction: Aggregation //Comm. ACM, v. 20, June 1977, p. 405-413.

96. Sundgren В. An infological approach to data bases. — Stockholm: National Central Bureau of Statistics. 1973. 294 p.

97. Sundgren B. Data base design in theory and practice. Toward an integrated methodology // Proc. of 4th Intern. Conf. on VLDB. West Berlin, 1978, p. 3-16.

98. Ullman J.D. Principles of Database and Knowledge-Base Systems. Volume II: The New Technologies. Computer Science Press, 1989.179

99. Cook S. "BBS style recursion How-To" 1999. // http://evolt.org/article/BBSstylerecursionHowTo/17/3962/evolt.org

100. Fling K. "Four ways to work with hierarchical data" 2000. // http://www.evolt.Org/article/Fourwaystoworkwithhierarchicaldata/17/4047/index.h tml

101. Stih T. "Modeling Hierarchies" 2002. // http://www.codeproject.com/KB/database/modhierarchies.aspx

102. Tulder G. "Storing Hierarchical Data in a Database" 2003. // http://www.sitepoint.com/print/hierarchical-data-database.htm

103. Lepekhin E.'Trees in SQL databases" 2004 // http://www.codeproject.com/KB/database/TreesinSQLdatabases.aspx

104. Hurwitz A. "Depthwise Ordering for Trees in SQL" 2007. http://www.codeproject.com/KB/database/dcpthinSQLdatabases.aspx

105. Celko Joe "SQL for smarties: advanced SQL programming". Amazon 2000.

106. Henderson K. "Guru's Guide to Transact SQL" Addison-Wesley, 2000, 592p. ISBN-13: 978-0201615760

107. Data Modeling and Database Design // Course Technology, 2007, 720p. ISBN: 1423900839

108. David C. Hay Data Model Patterns: Conventions of Thought // Dorset House Publishing, 1995, 268p. ISBN: 0-932633-29-3

109. D. Aioanei, A. Malinaru. General trees persisted in relational databases. // http ://www. codeproj ect.com/cs/database/ persistingtrees. asp

110. Д. Дантеманн Энциклопедия Delphi // http://adept7.narod.ru/library/programming/delphi/d3prolib/index.htm

111. J. Celko. Joe Celko's Trees and Hierarchies in SQL for Smarties. Morgan Kaufmann.

112. P. Ciaccia, D. Maio, and P. Tiberio. A method for hierarchy processing in relational systems // Information Systems, 14(2):93-105, 1989.

113. Д. Кнут, Р. Грэхем, О. Паташник Конкретная математика. Основание информатики (Concrete Mathematics. A Foundation for Computer Science). — M.: Мир; Бином. Лаборатория знаний, 2006. — 703 с.

114. J. Roy. 2003. Using the Node Data Type to Solve Problems with Hierarchies in DB2 Universal Database // http://wwwl06.ibm.com/developerworks/db2/library/techarticle/0302roy/0302roy.html

115. V. Tropashko. Trees in SQL: Nested Sets and Materialized Path. // http://www.dbazine.com/tropashko4.shtml

116. V. Tropashko. Nested Intervals with Farey Fractions. // http://arxiv.org/html/cs.DB/0401014

117. V. Tropashko. Nested Intervals Tree Encoding with Continued Fractions.// http://arxiv.org/pdf/cs.DB/0402051

118. Новиков Д.А. Сетевые структуры и организационные системы. М.: ИЛУ РАН, 2003. 102 с.