Хранение сложных структур данных в реляционных базах данных тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Полтавцева, Мария Анатольевна

• Полтавцева, Мария Анатольевна
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Полтавцева, Мария Анатольевна

Введение.

Глава 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.

Список литературы диссертационного исследования кандидат технических наук Полтавцева, Мария Анатольевна, 2008 год

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 с.