Содержание к диссертации
Введение
ГЛАВА 1. Современное состояние проблемы в документно- ориентированных базах данных 13
1.1. Общая характеристика документно -ориентированных СУБД 13
1.2 Основные архитектуры СУБД 20
1.3 Анализ известных моделей построения баз данных 25
1.4 Постановка проблемы оптимизации 29
механизма поиска ДО СУБД
ГЛАВА 2. Теоретическое обоснование оптимизации процесса поиска до СУБД
2. 2 Описание структуры БД 32
2.1.1 Схема БД 33
2.1.2 Механизм отыскания дерева соединений 37
2.1.3 Алгоритм накопления данных 41
2.1.4 Структура хранимых документов 42
2.2 Оптимизация механизма поиска
информации 44
2.2.1 Генерация разбиений множеств 44
2.2.2 Нерекуррентная схема алгоритма генерации всех разбиений 49
2.2.3 Построение алгоритма оптимизации по списку рабочих индексов 54
ГЛАВА 3. Разработка механизма взаимодействия отдельных элементов системы 59
3.1 Общие требования к системе 59
3.2 Логическая структура системы 65
3.3 Структура представления данных 70
3. 4 Индексные структуры 75
3.4.1 Основные типы структур, используемых для индексирования. Древовидные структуры 75
3.4.2 В+ деревья 77
3.4.3 Ранжирование индексов 79
ГЛАВА 4. Построение ядра до субд. оценка производительности системы 83
4.1 Практическая реализация 83
4.1.1 Определение языка программирова
ния для реализации системы 83
4.1.2 Блок-схема ядра системы 84
4.1.3 Модуль поддержки файлов страничной организации 87
4.1.4 Модуль кэширования файла страничной организации 90
4.1.5 Модуль поддержки индексов 94
4.1.6 Модуль поддержки документов 101
4.1.7 Интерфейсный модуль 104
4.1.8 Компоненты работы с БД для Delphi., юб
4.2 Сравнительные характеристики. 118
Заключение 122
Литература 125
Приложения
- Общая характеристика документно -ориентированных СУБД
- Анализ известных моделей построения баз данных
- Нерекуррентная схема алгоритма генерации всех разбиений
- Логическая структура системы
Введение к работе
Одной из важнейших задач, практически любой, компьютерной системы является хранение и обработка данных. Для ее решения были предприняты усилия, которые привели к появлению' в конце б0-х - начале 7 0-х годов специализированного программного обеспечения - систем управления базами данных (СУБД -database management systems). Опыт применения ЭВМ для построения прикладных систем обработки данных показывает, что наиболее эффективным инструментом здесь являются не универсальные алгоритмические языки высокого уровня, а специализированные языки для создания систем управления данными. Такие средства обычно включаются в состав СУБД, но они могут существовать и отдельно. СУБД дают возможность пользователям осуществлять непосредственное управление данными, а программистам быстро разрабатывать более совершенные программные средства их обработки.
Среди существующих СУБД все большую значимость приобретают системы, позволяющие вести обработку и хранение информации в виде электронных документов. В основном это мощные по производительности программные продукты, соответствующие вычислительным комплексам на уровне промышленных стандартов и получившие название документно-ориентированных (ДО СУБД). К сожалению, во многих ' случаях пользователя не
устраивает время поиска информации в таких системах, а при работе на обычных персональных компьютерах (ПК) с относительно небольшими базами данных могут возникать определенные препятствия. К тому же немалая стоимость большинства ДО СУБД нередко ограничивает возможности их использования.
В этой связи проблема построения алгоритмических средств недорогой ДО СУБД, обладающей малым временем поиска и эффективно работающей на обычных ПК, представляется весьма актуальной.
Цель работы. Разработка оптимизированного механизма поиска информации документно-ориентированных СУБД, обеспечивающего высокие скоростные характеристики при работе с документами различной структуры, не требующего для своей эксплуатации вычислительных комплексов промышленного уровня.
Для достижения поставленной цели в рамках диссертационной работы решаются следующие основные задачи:
анализ современного состояния проблемы;
разработка и математическое обоснование метода оптимизации механизма поиска ДО СУБД на основе генерирования разбиений множеств;
разработка алгоритма построения индексных структур с использованием общих принципов реализации ДО СУБД;
разработка алгоритмического и программного обеспечения документно-ориентированной системы, ис~
пользующего оптимизированный механизм поиска информации.
Научная новизна работы состоит в теоретическом обосновании, практической реализации и внедрении в производство специализированной высокоскоростной документно-ориентированной СУБД, основанной на оптимальном методе организации индексных структур. В рамках данного подхода решены, в частности, следующие новые задачи:
1.Разработана модель документно-ориентированной СУБД, основанная на описании ее структуры в виде произвольного графа на множестве данных, обеспечивающая ввод и хранение информации в гарантированном пространстве записей, дающих дерево соединений БД. 2.Разработан метод генерации необходимых разбиений множества данных, соответствующих элементам запроса системы, позволяющий вести оптимальный поиск информации по критерию минимального времени цикла, который ограничен постоянной, не превышающей мощности данных разбиений. 3.Предложен алгоритм взаимодействия отдельных элементов индексных структур, основанный на использовании механизмов полностью инвертированных , файлов совместно с методом формирования разбиений множества данных, и обеспечивающий возможность работы практически с любыми реальными документами.
Практическая ценность работы заключается в следующем :
1.Предложено решение для работы с любым набором данных через интеллектуальный интерфейс ДО СУБД, включая конвертер для преобразования вводимых данных.
2.Разработано универсальное ядро СУБД, обладающее переносимостью на различные операционные системы (Windows- и UNIX- совместимые).
3.Созданы программные компоненты, обеспечивающие простоту разработки новых приложений в системе программирования Delphi.
4.Разработано программное обеспечение, выполненное в виде скрипта для динамического доступа к базе данных в глобальной сети Интернет.
5.Результаты диссертации использованы в учебном процессе в Вологодском государственном техническом университете в курсе «Основы проектирования баз данных и разработка приложений» Результаты диссертационной работы докладывались и получили положительную оценку на:
международном форуме по проблемам науки, техники и образования (Москва, Академия наук о земле, 25-8 ноября 1997);
первой международной конференции «Повышение эффективности теплообменных процессов и систем» в секции «Информационные системы и технологии» (Вологда .ЗоГТУ, 24-27 июня 1998) ;
второй международной научно-технической конференции «Информационные технологии в производственных,, социальных и экономических процессах» (Череповец ЧГУ, 24-27 мая 1999);
межвузовской конференции «Управляющие вычислительные системы. Новые технологии» (Вологда ВоГТУ, март 2 000);
второй международной конференции «Повышение эффективности теплообменных процессов и систем» в сек- ции «Информационные системы и технологии» (Вологда ВоГТУ, 19-22 апреля 2000);
science readings WHITE NIGHT-2000: Abstract of International Ecological Symposium Perspective information tecnology and risk namagment problem on the Millenium threshold (Saint-Petersburg July, 22-27, 2000).
По материалам диссертации опубликовано восемь печатных работ.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений .
Первая глава дает представление о современном состоянии различных по классу и типу систем управления базами данных. Определяются и классифицируются основные типы используемых СУБД. Дается краткое описание преимуществ и недостатков используемых архитектур, моделей данных. Определяется место документно-ориентированных систем в широком
спектре других СУБД, класс задач, которые наиболее предпочтительно решать с их помощью. Определяется цель работы и основные решаемые задачи.
Вторая глава посвящена обоснованию теоретических аспектов разработки. Определяются общие принципы построения СУБД. Описывается математический аппарат системы: структура и схема базы данных, алгоритм проверки существования дерева соединений, логическая структура документа, метод генерации всех разбиений множества данных и на его основе алгоритм оптимизации по набору готовых индексов.
В третьей главе освещаются вопросы проектирования системы, на основе которых определяются принципы реализации. В первом разделе главы формулируются общие требования, далее определяется логическая структура системы, выбираются предпочтительные структуры для хранения данных, а также структуры индексирования.
Четвертая глава, в основном, посвящена практической реализации системы: определение языка программирования и блок-схемы, формирование перечня интерфейсных элементов и описание реализации готовых компонентов для средства визуального проектирования Delphi. В заключение главы приводятся сравнительные характеристики созданной системы _ с широко используемыми СУБД.
Результаты работы внедрены и успешно эксплуатируются в следующих проектах:
Разработана и внедрена система поддержки баз данных проекта «Международная информационная ярмарка товаропроизводителей» в сети Интернет для Федерального информационного центра при Министерстве имущественных отношений РФ, расположенная по адресу ;
Создано программное обеспечение электронной версии Телефонного справочника «Наши абоненты 20 00» для ОАО «Электросвязь» Вологодской области;
Разработан программный комплекс «Статьи», предназначенный для хранения и обработки газетных и журнальных статей, как в локальном варианте, так и в глобальной сети Интернет. Эксплуатируется редакцией газеты «МК в Вологде»;
Реализованы такие готовые программные продукты, как «БухПроф», «Расчет заработной платы», «ИПС «Закон», которые уже более 2-х лет успешно эксплуатируются на 4 8 различных предприятиях и организациях;
Реализован и эксплуатируется программный комплекс «Оперативный учет недвижимости» в МУП «Гортёхинвентаризация» г. Вологды;
Разработано программное обеспечение «Аренда», используемое для учета арендуемых зданий и помещений администрации г. Вологды;
Разработан и внедрен программный комплекс «Вологодская информационная ярмарка», используемый телефонной справочной службой «0 65» г. Вологды.
На защиту выносятся следующие положения:
1.Модель документно-ориентированной СУБД, представленная в виде произвольного графа.
2.Метод генерации всех необходимых разбиений множества данных,
3.Алгоритм организации взаимодействия отдельных элементов индексных структур.
4.Ядро документно-ориентированной СУБД.
Общая характеристика документно -ориентированных СУБД
Одной из важных задач компьютерных систем является хранение и обработка данных. Опыт применения ЭВМ для построения прикладных систем обработки данных показывает, что самым эффективным инструментом здесь являются не универсальные алгоритмические языки высокого уровня, а специализированные языки для создания систем управления данными [21,36,59]. Такие средства обычно включаются в состав СУБД, но они могут существовать и отдельно . Характеристики созданных прикладных пакетов определяются, прежде всего, принятой в СУБД организацией данных и типом используемого транслятора. СУБД позволяют структурировать, систематизировать и организовать данные для их компьютерного хранения и обработки.
Каждую систему управления базами данных можно охарактеризовать следующими параметрами: качественные характеристики - возможность или невозможность хранения в БД информации той или иной структуры; количественные характеристики), такие как максимальное количество хранимых в БД документов, максимальный объем одного документа; скоростные - это скорость выборки нужных документов из БД по произвольному набору поисковых элементов; простота реализации на основе данной СУБД конкретных приложений; рыночная стоимость СУБД.
.На сегодняшний день на рынке программного обеспечения для персональных компьютеров существует большой выбор систем управления базами данных. Всех их условно можно разделить на две основные группы -"дешевые" и "дорогие" [40] .
К первой группе относятся такие популярные СУБД, как FoxPro, Paradox, Microsoft Access, DBase и др. Они характеризуются средними количественными и качественными параметрами, простотой реализации на их основе конкретных приложений, а также очень малой рыночной стоимостью (менее $1000). В то же время их качественные характеристики довольно низки, и часто не удовлетворяют все более растущие потребности конечных пользователей. Основные из них - жесткость структуры хранимой информации, ограничение объема документа, невозможность хранения и/или индексирования в этих СУБД объектов произвольного размера (таких как тексты произвольной длины, графические изображения и т. д.).
Ко второй группе относятся, условно говоря, "большие" СУБД, например, такие как Oracle, Informix, SyBase и др. Эта группа характеризуется высокими количественными, качественными и скоростными характеристиками. Разработка же конкретных приложений с использованием вышеупомянутых СУБД сопряжена с определенными трудностями - для них требуются специалисты высокой квалификации. Но, самый главный недостаток вышеупомянутых СУБД - очень высокая рыночная стоимость, порядка $10000.
Для конечного пользователя привычнее получать информацию в виде электронных документов, которые представляют, по сути, аналоги бумажных. Многие существующие СУБД предоставляют такие возможности, однако в большинстве случаев это сопряжено с появлением дополнительных затрат, т.к. существует необходимость наложения достаточно произвольной структуры документа на довольно жесткую структуру представления данных в СУБД. Эту трудность сейчас пытаются обойти и появились СУБД нового типа, которые позволяют хранить данные непосредственно в виде электронных документов. Такие системы получили название документно-ориентированных СУБД (ДО СУБД) [17,39].
Анализ известных моделей построения баз данных
Можно выделить три основные модели построения баз данных: реляционную, иерархическую и сетевую [21, 4 6, 59]. С развитием микропроцессорной компьютерной техники, с увеличением объемов оперативной памяти и быстродействия компьютеров все большую значимость, удобство и эффективность стала приобретать реляционная модель данных и СУБД на ее основе. Теперь ее распространенность практически вытеснила из обращения вышеперечисленные модели из-за простоты физической организации, понимания и использования. Физически модель представляет собой простую и наиболее привычную форму организации данных в виде таблицы. В теории множеств таблице соответствует термин отношение (relation), который и дал название модели. Для нее имеется развитый математический аппарат - реляционное исчисление и реляционная алгебра, где для баз данных (отношений) определены такие хорошо известные теоретико-множественные операции, как объединение, вычитание, пересечение, соединение и др.
Несомненным достоинством реляционной модели является сравнительная простота инструментальных средств ее поддержки. Однако есть существенный недостаток - жесткость структуры данных (невозмож ность/ например, задания строк таблицы произвольной длины) и зависимость скорости ее работы от размера базы данных. Для многих операций, определенных в такой модели, может оказаться необходимым перебор всех данных.
Важным аспектом традиционной реляционной модели данных является тот факт, что элементы данных, которые хранятся на пересечении .строк и столбцов таблицы, должны быть неделимы и единственны. Это означает, что данные не могут быть развернуты в процессе дальнейшей обработки. Такое правило было заложено в основу реляционной алгебры при ее разработке как математической модели данных.
В дальнейших исследованиях показано, что существует ряд случаев, когда ограничения классической реляционной модели существенно мешают эффективной реализации готовых приложений, поэтому необходимо расширение реляционного аппарата. Если допустить, что значение данных может само состоять из подзначений, то в результате возникает понятие многозначного поля. Проще всего рассматривать набор многозначных полей в таблице как самостоятельную встроенную таблицу [36].
При условии, что встроенная таблица удовлетворяет общим критериям, например имеет уникальный ключ, естественным образом происходит расширение операторов реляционной алгебры.
Эта модель данных поддерживает также ассоциированные многозначные поля, которые часто называют множественными группами. То есть существует возможность связать несколько столбцов с множественными значениями в единое целое, называемое ассоциацией. При этом в строке первое значение одного столбца ассоциации соответствует первым значениям всех других столбцов ассоциации, в такой же связи находятся все вторые значения столбцов и т.д.
Многозначные поля не могут накладываться друг на друга. Такая модель данных была названа постреляционной [36] .
На рисунках 1.3.1 и 1.3.2 продемонстрированы преимущества хранения данных в постреляционной модели, относящейся к непервой нормальной форме перед более громоздкие хранением данных в реляционных моделях хранение части данных такого типичного документа, как накладная.
В непервой нормальной форме- можно создавать многозначные поля переменной длины, все накладные могут храниться в одной логической базе данных. При этом для хранения требуется меньше места и при обработке, не нужно объединять данные, что повышает эффективность их хранения.
Такая модель данных реализована в СУБД Universe. Некоторые расширения аппарата реляционной алгебры присутствуют и в отдельных других промышленных СУБД.
Это расширение реляционной модели является качественно полезным для документно-ориентированных систем, однако для проектируемой СУБД такой аппарат оказывается недостаточным ввиду следующих обстоятельств : недостаток, связанный жесткостью структуры базы данных реляционных СУБД сохраняется; отсутствие механизма поддержки нескольких разнотипных вложенных таблиц; недостаточная отработанность механизма поддержки текстовых полей произвольной длины.
Эти недостатки постреляционных СУБД существенно увеличивают время поиска информации, особенно на персональных компьютерах. Необходима модификация структуры с целью оптимизации выполнения запросов.
Нерекуррентная схема алгоритма генерации всех разбиений
Разбиение множества {1, ..., п} мы будем представлять с помощью последовательности блоков, упорядоченной по возрастанию самого маленького элемента в блоке. Этот наименьший элемент блока будем называть номером блока. Отметим, что номера соседних блоков, вообще говоря, не являются соседними натуральными числами, В этом алгоритме мы будем использовать переменные PREV[i], NEXT[і], 1 і п, содержащие соответственно номер предыдущего и номер следующего блока для блока с номером і (NEXT [і] = 0, если блок с номером і является последним блоком разбиения). Для каждого элемента і, 1 і п, номер блока, содержащего элемент і, будет храниться в переменной BLOCK[і], направление, в котором «движется» элемент і, будет закодирован в булевой переменной FORWARD[і] (FORWARD[і] = true, если і движется вперед). Алгоритм представлен на рис. 2.2.2. Результатом его работы является последовательность всех разбиений множества {1, ..,, п}, в которое каждое следующее разбиение образуется из предыдущего путем перенесения единственного элемента в другой блок.
Этот алгоритм строит сначала разбиение {1, ..., п} (цикл 1) - отметим, что это первое разбиение в списке Ln/ созданном при помощи описанного нами рекуррентного метода. Задача основного цикла 4 Из описанного рекуррентного построения следует, что данный элемент перемещается только тогда, когда все элементы, большие его, достигают своего крайнего левого или правого положения; точнее, активный элемент і является таким наименьшим элементом, что для каждого большего элемента і выполняется одно из двух следующих условий:
(a) FORWARD[i] and (BLOCK[i] =i) , т.е. элемент движется вперед и достигает своего крайнего правого положения (очевидно, і не может быть элементом блока с наименьшим элементом, большим І).
(b) not FORWARD [і] and (BLOCK [і] = 1), т.е. элемент і движется назад и достигает своего крайнего левого положения (в первом блоке).
Этот принцип реализуется в блоках 18, 19, Заодно меняется направление движения элементов і і . Дополнительным условием цикла 18 является і 1, так как из самого представления разбиения следует, что і = 1 не может быть активным элементом (очевидно, что элемент 1 всегда является элементом блока с номером 1) . Если каждый из, элементов і-. 1 ..отвечает усдрвию (а) или (b) , то легко убедиться, что уже порождены все разбиения. В таком случае на выходе цикла 18 имеем і = 1 и следует выход из основного цикла 4, т.е. имеем окончание работы алгоритма. Из рекуррентности алгоритма вытекает также, что активным элементом для первого разбиения списка Ln/ т.е. для {{1, ..., п}}, является элемент п. Такое же значение приписывается переменной і перед входом в цикл 4 (блок 3).
Проанализируем теперь процесс переноса активного элемента (блоки 5 - 16). Сначала отыскивается номер блока, содержащего активный элемент; пусть это будет к. Если этот элемент движется вперед, достаточно перенести его в блок с номером NEXT[к] (блок 11), а в двух остальных случаях переменную NEXT[к] нужно сначала модифицировать. Первый случай имеет место, когда NEXT [к] = О, т.е. когда к есть номер последнего блока разбиения. Тогда і образует одноэлементный блок; при этом достаточно принять NEXT[k] = і и соответственно изменить значения переменных NEXT[i] и PREV[i] (блок 8) . Второй случай имеет место, когда NEXT[к] і, он рассматривается аналогично. Условие NEXT[к] і означает, что все блоки справа от блока с номером к содержат элементы, большие і (все эти элементы занимают свои крайние правые позиции, в противном случае і не был бы активным элементом).
Логическая структура системы
Данный модуль является единственным не представленным в виде законченного объекта. Он представлен в виде интерфейсных функций ядра базы данных. Полный перечень данных функций приведен в приложении. В данном подразделе мы остановимся на кратком описании лишь наиболее важных: int nu__connect ( char users_id, char cfg__id ) Назначение: подключение нового пользователя к системе int nu_disconnect( char users_id ) Назначение: отключение пользователя от системы int nu_down( char cfg_id )
Назначение: принудительное отключение всех пользователей от системы (функция администратора) int nu_docsearch( char users_id, char query_id, char query ) Назначение: выполняет запрос в БД int nu_queryMTD{char users_id, char query_idl, char query_id2, char query_id_res ) Назначение: объединяет два результата поиска по логическому условию НИ" int nu_queryOR( char users_id, char query_idl, char query_id2, char query_id_res ) Назначение: объединяет два результата поиска по логическому условию "ИЛИ" int nu_getqueryresult( char user_id, char query_id, char result )
Назначение: возвращает результат выполнения запроса в БД или результат после выполнения логических операций "И", "ИЛИ". int nu_getdoc( char users_id, char query_id, char doc_number, char doc_id )
Назначение: считывает документ, но не передает его содержимое, все операции с документом в дальнейшем происходят через doc_id int nu_getdocinfо ( char users_id, char doc_id, char code_doc_type, char doc_size ) Назначение: предоставляет пользователю информацию о считанном документе int nu_docread( char users_id, char doc_id, char doc ) Назначение: передает пользователю содержимое документа int nu_docsave( char users_id, char doc_id, char doc ) Назначение: сохраняет документ в БД, если он был изменен int nu_docdel{ char users_id, char doc_id ) Назначение: удаляет документ из БД и из соответствующего ему результата поиска int nu_docadd( char users_id, char doc ) Назначение: записывает новый документ в БД int nu_getindexes( char users_id, char field_code, char start__index/ char number, char indexses )
Назначение: передает пользователю информацию о поисковых ключах и частоте их встречаемости одного из полей БД
На основе вышеуказанных интерфейсных функций целесообразно разработать некий набор компонент для современных систем визуального проектирования готовых приложений. Одной из наиболее распространенного программного обеспечения такого рода в России и в мире является система Delphi фирмы Imprise. Общий перечень компонент, необходимых для использования разрабатываемой СУБД в Delphi приведен в таблице 4.1.4.
TNMBScrollBoxInput. Компонент предназначен для внедрения в него групп полей ввода. Способен скроллировать помещенные в него объекты горизон тально и вертикально. Дополнительные свойства компоненты: ANMBDataSet: String - Имя компоненты, обслуживающей БД.
TNMBScrollBoxEdit, TNMBScrollBoxQuery. Компоненты идентичны объекту TNMBScrollBoxInput, с той лишь разницей, что в данные объекты, помещаются соответственно группы полей для корректировки и запроса.
TNMBSimpleGroup. Компонент описывает простую (недублируемую) группу полей документа.
Предназначен для помещения в него полей документа. Дополнительные методы и свойства компоненты: ReSize ( DX, DY : Integer ) - Изменяет размер рабочей области группы по горизонтали и вертикали на DX и DY пикселей соответственно/ Move ( DX, DY : Integer ) - Перемещает группу по горизонтали и вертикали на DX и DY пикселей соответственно.
ANMBGroupCode: String - Код группы. TNMBMultipleGroup. Компонент описывает дублируемую группу полей документа. Предназначен для помещения в него полей документа. Содержит в себе три кнопки для создания новой реализации группы, для дублирования группы и для удаления какой-либо реализации.
