Диплом К

АННОТАЦИЯ............................................................................................................................................	6
1. РЕФЕРАТ ...............................................................................................................................................	7
Ключевые слова. .................................................................................................................................................	7
2. ВВЕДЕНИЕ ............................................................................................................................................	9
3. КОНСТРУКТОРСКАЯ ЧАСТЬ. ......................................................................................................	13
3.1. ИНФОРМАЦИОННЫЕ СИСТЕМЫ. ...........................................................................................................	13
3.1.1. Информация и проблемы ее обработки. ..................................................................................	13
3.1.2. Базы данных и системы управления базами данных. .............................................................	14
3.1.3. Объектные базы данных. ..........................................................................................................	16
3.1.4. Сетевые баз данных...................................................................................................................	17
3.1.5. Системы обработки документов.............................................................................................	19
3.2. АРХИТЕКТУРА КОМПЛЕКСА. ................................................................................................................	20
3.2.1. Отличительные черты..............................................................................................................	20
3.2.2. Модульная диаграмма. ...............................................................................................................	21
3.2.3. Диаграмма процессов. ................................................................................................................	22
3.3. ФАЙЛ ДАННЫХ .....................................................................................................................................	23
3.3.1. Выбор способа реализации ........................................................................................................	23
3.3.1.1. Резервирование по максимуму............................................................................................................	23
3.3.1.2. Непрерывное.........................................................................................................................................	24
3.3.1.3. Сегментация..........................................................................................................................................	25
3.3.2. Структуры данных ....................................................................................................................	27
3.3.2.1. Страница ...............................................................................................................................................	27
3.3.2.2. Нулевая страница .................................................................................................................................	28
3.3.2.3. Запись ....................................................................................................................................................	30
3.3.2.4. Головная страница записи ...................................................................................................................	30
3.3.2.5. Хвостовые страницы записи ...............................................................................................................	31
3.3.2.6. Список свободных страниц .................................................................................................................	31
3.3.3. Иерархия классов ........................................................................................................................	32
3.3.3.1. Класс dsCache .......................................................................................................................................	33
3.3.3.2. Класс dsPage .........................................................................................................................................	33
3.3.3.3. Класс dsRecord......................................................................................................................................	33
3.3.3.4. Класс dsFPL ..........................................................................................................................................	34
3.3.3.5. Класс dsPool..........................................................................................................................................	34
3.3.3.6. Класс dsFile ...........................................................................................................................................	34
3.3.4. Описание реализации..................................................................................................................	35
3.3.4.1. Конструктор создания файла ..............................................................................................................	35
3.3.4.2. Конструктор открытия файла..............................................................................................................	36

3.3.4.3. Добавление записи ...............................................................................................................................	36
3.3.4.4. Чтение записи .......................................................................................................................................	37
3.3.4.5. Изменение записи.................................................................................................................................	38
3.3.4.6. Удаление записи ...................................................................................................................................	38
3.3.5. Заключение ..................................................................................................................................	38
3.4. ФАЙЛ ИНДЕКСОВ..................................................................................................................................	44
3.4.1. Введение ......................................................................................................................................	44
3.4.2. Выбор структуры индекса ........................................................................................................	44
3.4.3. Особенности реализации ...........................................................................................................	45
3.4.4. Структуры данных ....................................................................................................................	46
3.4.4.1. Общая структура дерева ......................................................................................................................	46
3.4.4.2. Базовый блок дерева ............................................................................................................................	47
3.4.4.3. Блок данных..........................................................................................................................................	49
3.4.4.4. Управляющий блок ..............................................................................................................................	50
3.4.5. Иерархия классов ........................................................................................................................	51
3.4.5.1. Класс btBlock ........................................................................................................................................	51
3.4.5.2. Класс btCtrlBlock ..................................................................................................................................	52
3.4.5.3. Класс btResBlock ..................................................................................................................................	52
3.4.5.4. Класс btTreePath ...................................................................................................................................	52
3.4.5.5. Класс btTree ..........................................................................................................................................	53
3.4.5.6. Класс btTreeStack..................................................................................................................................	54
3.4.5.7. Класс btTreeRes ....................................................................................................................................	55
3.4.5.8. Класс btFind ..........................................................................................................................................	55
3.4.5.9. Класс btCatalog .....................................................................................................................................	55
3.4.5.10. Класс btFile .........................................................................................................................................	56
3.4.6. Алгоритмы управления индексом..............................................................................................	56
3.4.6.1. Алгоритм поиска пары ключ–значение..............................................................................................	57
3.4.6.2. Алгоритм добавления пары ключ–значение ......................................................................................	58
3.4.6.3. Алгоритм удаления пары ключ–значение. .........................................................................................	59
3.4.6.4. Алгоритм разбиения индекса. .............................................................................................................	60
3.4.7. Описание реализации..................................................................................................................	61
3.4.7.1. Конструктор создания ВТ–файла .......................................................................................................	62
3.4.7.2. Конструктор открытия ВТ–файла.......................................................................................................	63
3.4.7.3. Добавление дерева в ВТ–файл ............................................................................................................	63
3.4.7.4. Удаление дерева в ВТ–файл................................................................................................................	64
3.4.7.5. Добавление пары ключ–значение .......................................................................................................	65
3.4.7.6. Удаление пары ключ–значение...........................................................................................................	65
3.4.7.7. Поиск ключа на полное совпадение ...................................................................................................	66
3.4.7.8. Поиск по началу ключа........................................................................................................................	66
3.4.7.9. Поиск по интервалу ключей ................................................................................................................	67
3.4.7.10. Поиск уникальных ключа ..................................................................................................................	67

3.4.8. Заключение ..................................................................................................................................		68
3.5. ЗАКЛЮЧЕНИЕ .......................................................................................................................................		74
3.5.1. Возможные области применения. ............................................................................................		75
3.5.2.	Почему разработанная СУБД не является реляционной? ..............................................	76
4. ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ..................................................................................................		77
4.1. ИССЛЕДОВАНИЕ РЕАЛИЗАЦИИ ФАЙЛА ДАННЫХ ..................................................................................		77
4.1.1. Анализ компактности размещения записей переменной длины. ...........................................		77
4.1.2. Время выполнения базовых операций с записями. ...................................................................		81
4.1.3. Влияние кэширования на скорость работы файла данных. ...................................................		82
4.1.4. Влияние сжатия на объем и скорость работы файла данных. ............................................		83
4.2. ИССЛЕДОВАНИЕ РЕАЛИЗАЦИИ ФАЙЛА ИНДЕКСОВ...............................................................................		83
4.2.1. Анализ компактности хранения ключей и значений в индексе. .............................................		83
4.2.2. Анализ времени поиска ключа в индексе. ..................................................................................		89
4.2.3. Расчет ресурсов оперативной памяти. ...................................................................................		92
5. ТЕХНОЛОГИЧЕСКАЯ ЧАСТЬ.......................................................................................................		93
5.1. ОБЪЕКТ РАССМОТРЕНИЯ ......................................................................................................................		93
5.2. СЛОЖНОСТЬ ПРОГРАММНЫХ СИСТЕМ .................................................................................................		93
5.2.1. Сложность решаемых проблем ................................................................................................		94
5.2.2. Сложность управления процессом разработки......................................................................		94
5.2.3. Гибкость программных систем................................................................................................		94
5.2.4. Сложность описания поведения отдельных подсистем........................................................		95
5.3. АНАЛИЗ СЛОЖНЫХ СИСТЕМ.................................................................................................................		95
5.3.1. Признаки сложных систем .......................................................................................................		95
5.3.2. Общие принципы анализа сложных систем ............................................................................		96
5.4. ОБЪЕКТНО-ОРИЕНТИРОВАННЫЕ МЕТОДЫ ПРОЕКТИРОВАНИЯ .............................................................		97
5.4.1. Цель и продукт проектирования ..............................................................................................		97
5.4.2. Определение объектного подхода.............................................................................................		98
5.4.3. Компоненты объектно-ориентированного проектирования ................................................		98
5.5. КЛАССЫ И ОБЪЕКТЫ...........................................................................................................................		100
5.5.1. Объект ......................................................................................................................................		100
5.5.2. Отношения между объектами ...............................................................................................		101
5.5.3. Класс ..........................................................................................................................................		103
5.5.4. Отношения меду классами ......................................................................................................		103
5.6. ПРОЦЕСС ПРОЕКТИРОВАНИЯ..............................................................................................................		106
5.6.1. Идентификация классов и объектов ......................................................................................		107
5.6.2. Определение семантики классов и объектов.........................................................................		107

5.6.3. Разработка связей между классами и объектами. ..............................................................	108
5.6.4. Реализация классов и объектов...............................................................................................	108
5.7. ДОСТОИНСТВА И НЕДОСТАТКИ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОЕКТИРОВАНИЯ .....................	108
6. ОРГАНИЗАЦИЯ ТРУДА И ЭКОНОМИКА ................................................................................	111
6.1. ПОСТРОЕНИЕ СЕТЕВОГО ГРАФИКА И ТЕХНИКО-ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЕ РАЗРАБОТКИ
ПРОГРАММНОГО ПРОДУКТА .................................................................................................................................	111
6.2. АНАЛИЗ СЕТЕВОГО ГРАФИКА .............................................................................................................	113
6.3. ТЭО РАЗРАБАТЫВАЕМОГО ПРОГРАММНОГО ИЗДЕЛИЯ ......................................................................	115
1. Основная заработная плата .........................................................................................................	115
2. Дополнительная заработная плата. ............................................................................................	116
3. Начисления на фонд оплаты труда .............................................................................................	116
4. Оплата работ, выполняемых сторонними организациями........................................................	116
5. Накладные расходы........................................................................................................................	117
6.4. РАСЧЕТ ЭКОНОМИЧЕСКОЙ ЭФФЕКТИВНОСТИ ТЕМЫ ..........................................................................	117
7. ОХРАНА ТРУДА...............................................................................................................................	128
7.1. ВВЕДЕНИЕ ..........................................................................................................................................	128
7.2. ГРАФИЧЕСКАЯ СРЕДА .........................................................................................................................	130
7.3. МЕНЮ И ИХ ТИПЫ ..............................................................................................................................	132
7.4. ЗАКЛЮЧЕНИЕ .....................................................................................................................................	134
ЛИТЕРАТУРА .......................................................................................................................................	136

АННОТАЦИЯ

Настоящий документ представляет собой пояснительную записку к дипломной работе на тему “Библиотека классов, реализующих файл данных и файл индексов для системы управления сетевой объектной базой данных”.

Рассматриваются основные способы хранения записей переменой длины и органи-

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

таны методы хранения записей переменной длины в файле данных и новая модифика-

ция индекса на основе В+деревьев с лучшей скоростью поиска. Описываются библио-

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

ектной базой данных.

Пояснительная записка включает технологическую и организационно-

экономическую части, раздел по охране труда и промышленной безопасности.

1. РЕФЕРАТ

Настоящая документ представляет собой пояснительную записку к дипломной ра-

боте на тему “Разработка библиотеки классов, реализующих файл данных и файл ин-

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

Объем пояснительной записки ___ страниц, формул ___, рисунков ___, таблиц

___, источников Ошибка! Закладка не определена..

Ключевые слова.

База данных, Система управления базами данных, Система обработки документов,

В+деревья, Индексирование, Сегментация данных.

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

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

Предпринята разработка инструмента для создания систем, объединяющих в себе преимущества СУБД и полнотекстовых баз данных. Кроме этого, инструмент изначаль-

но строится как сетевая среда, строящаяся в соответствии с архитектурой клиент-

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

Описаны различные подходы к построению индексов и файлов данных для хране-

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

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

Операции даны с указанием параметров и возвращаемых результатов.

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

ханизмов кэширования.

Характеристики созданных программных средств позволяют сделать вывод о по-

вышении качества автоматизации документооборота по сравнению с существующими

подобными системами на базе реляционных СУБД и о существенном повышении каче-

ства текстового поиска по сравнению с традиционными средствами поиска по формаль-

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

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

Технологическая часть содержит изложение объектно-ориентированной техноло-

гии разработки программного обеспечения. В данном разделе развиваются теоретиче-

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

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

Организационно-экономический раздел содержит технико-экономический анализ разработки с расчетом трудоемкости и таблицей для сетевого графика работ.

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

подчеркивается связь этого стандарта с медицинскими рекомендациями по построению диалогов человека с компьютером.

1Common User Access - стандарт построения пользовательских интерфейсов для прикладных про-

грамм. Разработан фирмой IBM.

2. ВВЕДЕНИЕ

Сейчас никто не будет спорить с тезисом о повсеместном распространении вычис-

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

Если сравнить сферы наиболее интенсивного применения вычислительной техни-

ки на заре ее появления и сегодня, то видно явную тенденцию к смещению от выполне-

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

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

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

ривается далее.

Информация является очень широким и абстрактным термином. Под информаци-

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

Под обработкой информации понимается хранение ее в памяти компьютеров, поиск,

передача на другие узлы вычислительной сети, вывод на принтер и т. п. Основными ви-

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

пьютерной обработке. Они сохраняют свое приоритетное положение и по настоящее время.

Ядром всех программных систем обработки информации являются базы данных1 и

системы управления2 ими. Подробно понятия БД и СУБД будут раскрыты в первом раз-

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

ным категориям, например, по типу доступа к БД, типу организации информации в БД,

1Далее по тексту БД

2Далее по тексту СУБД.

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

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

И раньше и сейчас существует реальная потребность в решении задач полноцен-

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

видна. В силу названных недостатков СУБД, для решения задач обработки текстов тра-

диционно применялись специализированные программы, выделяемые в класс так назы-

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

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

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

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

ния остаются нерешенными до сих пор, несмотря на потребность в подобных про-

граммных комплексах.

В настоящей работе предпринята разработка инструмента для создания систем,

объединяющих в себе преимущества СУБД и полнотекстовых баз данных. Кроме этого,

инструмент изначально строится как сетевая среда в соответствии с архитектурой кли-

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

Цель работы – создание платформы разработки прикладных программ, предна-

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

намической структурой2. Смысл применения этих программ – повышение производи-

тельности труда в делопроизводстве.

Большинство реальных документов имеют в своем составе разнородную инфор-

мацию: фактографическую, текстовую, табличную, графические образы, звуковые ме-

1Например, поля BLOB (binary large object) в СУБД Interbase и поля MEMO в dBase III.

2В западной компьютерной прессе уже введен специальный термин - Compound Documents.

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

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

ции для программных продуктов этого типа – системы обработки документов (СОД).

Естественно, что разные предметные области используют различные форматы до-

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

влетворения различных требований разных пользователей было решено делать не кон-

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

лей только средствами адаптации программного продукта.

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

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

ставлен обширный API1, с помощью которого он разрабатывает приложение для кон-

кретной проблемной области. Подробное описание разработки в целом приведено в первом разделе конструкторской части.

Среди аналогов, на текущий момент, можно назвать Lotus Notes и OS Pick.

Lotus Notes2 – программная платформа для разработки систем автоматизации до-

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

Windows, OS/2, UNIX и Mac OS, причем наблюдается резкое возрастание числа при-

кладных программ, разработанных и разрабатываемых в настоящий момент на его ос-

нове. Естественно, что Lotus Notes имеет гораздо более богатый набор сервисных функ-

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

сокого класса.

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

2Первая версия выпущена фирмой Lotus Development Corp. в 1990 году.