Содержание к диссертации
Введение
Глава 1. Подходы к формализации модели данных. Опыт использования различных моделей данных в СУБД. 11
1.1 Подходы к организации доступа к данным 11
1.2 Выработка требований 21
1.3 Постановка задачи повышения эффективности доступа к хронологическим данным 31
Глава 2. Описание используемого способа расширения реляционной модели данных 33
2.1 Метод темпорального расширения реляционной модели данных 33
2.2 Операторы для задания размерностей времени 39
2.3 Операторы для задания календарей 46
2.4 Операторы работы с темпоральным расширением 48
2.5 Выводы по второй главе 53
Глава 3. Методы индексирования хронологических данных. 54
3.1 Выработка требований 54
3.1.1 Особенности темпорального индексирования 54
3.1.2 SR-дерево 56
3.1.3 SR*-flepeBO 59
3.2 Управление пространственными данными 61
3.3 Алгоритмы улучшения качества R-деревьев 65
3.3.1 Глобальные алгоритмы 66
3.3.2 Алгоритмы разбиения множества объектов на минимально пересекающиеся группы 67
3.4 Практический анализ глобальных алгоритмов 77
3.5 Расширяемая архитектура 79
3.6 Выводы по третьей главе 81
Заключение 82
Библиографический список использованной литературы 85
- Подходы к организации доступа к данным
- Метод темпорального расширения реляционной модели данных
- Выработка требований
Введение к работе
Актуальность темы диссертационной работы в первую очередь определяется её ориентацией на важную практическую проблему эффективного доступа к хронологическим данным в системах управления базами данных.
В настоящее время наиболее широко используются системы управления реляционными базами данных. Предлагаемые методы ориентированы на решение поставленной проблемы путем создания темпорального расширения реляционной модели данных.
Основой расширения модели является определение его базовых понятий. Такими понятиями для хронологических данных традиционно являются: размерность времени, метка времени, шкала времени и календарь. При этом в настоящий момент нет расширения, вводящего в реляционную модель эти понятия. Существующие модели, содержащие эти понятия, либо узко специализированы, либо существенно отличаются от реляционной, что не позволяет их использовать для работы с существующими базами.
Разработка темпорального расширения реляционной модели позволяет повысить эффективность и удобства работы с хронологическими данными. Построение методологии индексации таких данных должно способствовать полному снятию проблемы работы с хронологическими данными.
Анализ существующих исследований, посвященных решению задачи повышения качества работы с хронологическими данными, выявил крайне незначительное число готовых и апробированных решений, что во многом связано с отсутствием достаточно проработанной теории и практики решения задачи хронологического расширения реляционной модели данных. Эффективное решение описанной задачи и составляет суть диссертационной работы.
Объектом исследования являются размерности времени, промежутки времени, календари, операторы для работы с ними, алгоритмы построения R-деревьев.
Предметом исследования является темпоральноеое расширение реляционной модели данных и использование R-деревьев для поиска хронологических данных.
Целью работы является повышение скорости и удобства доступа к хронологическим данным в реляционных системах управления базами данных за счет построения расширения реляционной модели данных, учитывающего специфику хронологических данных, а также скорости доступа - за счет использования R-деревьев и разработки алгоритма построения R-деревьев с минимализацией перекрытий на неравномерных данных. Для достижения поставленной цели в диссертационной работе поставлены и решены следующие задачи:
Обоснование и выбор подходов для расширения реляционной модели данных хронологическими понятиями.
Выбор и реализация операторов для работы с темпоральным расширением.
Обоснование возможности использования R-деревьев для поиска хронологических данных.
Разработка алгоритма построения R-деревьев с минимализацией перекрытий на неравномерных данных.
Основные методы исследования. В качестве методов исследования использовались статистический анализ, теория множеств, анализ алгоритмов, реляционная алгебра. Компьютерная реализация выбранных операторов и алгоритма производилась на основе объектно-ориентированного подхода.
Научная новизна. Предлагаемая диссертация содержит следующие новые результаты, полученные лично автором:
Определены базовые понятия темпорального расширения реляционной модели данных.
Разработаны операторы для задания введенных базовых понятий и работы с ними.
Использованы R-деревья, для доступа к хронологическим данным, по отрезкам времени, представленным в виде двумерных отрезков.
Разработан метод построения R-деревьев с минимализацией перекрытий на неравномерных двумерных данных.
Теоретическая значимость работы заключается в создании расширения реляционной модели данных для работы со временем, которое может послужить платформой для усовершенствования существующих реляционных систем управления базами данных. Разработанный метод построения индекса с учетом времени позволяет эффективно обрабатывать хронологические данные, что дает возможность широко применять предложенное расширение при работе с ними. Кроме того, предложенный подход позволяет ввести прямо в базу используемые методы обработки хронологических данных.
Практическая значимость работы заключается в создании тестовой системы, реализующей предложенный алгоритм построения R-дерева и поиск по тестовым данным с его использованием. Предложенный подход может быть легко применен в реляционной системе управления базами данных, полная же разработка такой системы достаточно трудоемка и выходит за рамки данной работы.
Личный вклад автора. Все основные результаты диссертации получены автором самостоятельно.
Апробация работы. Научные результаты и основные положения работы представлялись на конференциях:
IX Санкт-Петербургская международная конференция «Региональная информатика-2004».
XXXVI межвузовская научная конференция аспирантов и студентов «Процессы управления и устойчивость».
Реализация. Полученные результаты реализованы в виде тестовой программной системы на языке программирования С#.
Публикации. Автором опубликовано по теме диссертации 3 печатные работы.
Структура и объем диссертационной работы. Диссертация состоит из введения, трех глав, заключения, она излагается на 103 страницах, включая перечень используемой литературы из 77 наименований. Кроме того, в диссертации имеется приложение на 10 листах, содержащее в себе примеры разработанных программ, реализующих алгоритмы, описанные в диссертации.
Подходы к организации доступа к данным
Перед тем как начать изучать организацию доступа к данным в СУБД остановимся на вопросе выбора разновидности СУБД для изучения. СУБД планомерно развиваются от разрозненных таблиц и древовидных структур к сочетающим эти подходы реляционным базам данных [2. 19, 21], и далее к реляционно-обьектным базам данных [16, 20] и распределенным хранилищам данных. Но так как сетевые и иерархические модели уже изжили себя и не отвечают современным требованиям, а реляционно-обьекные пока не определились до конца со всеми общими принципами и методами доступа, то целесообразным видится рассмотрение устоявшихся подходов как раз реляционных баз данных, как наиболее развитых.
Хотя многие полагают, что реляционные СУБД, являясь наиболее распространенным современным аппаратом построения информационных систем, не представляют уже интереса в научном отношении, остается еще много нерешенных или решенных не полностью проблем. Об этом свидетельствует поток статей, посвященных тематике чисто реляционных систем, а также активная деятельность ком пани й-производителей коммерческих реляционных систем, стремящихся улучшать свои продукты и придавать им новые качества. [4, 12, 57, 58]
Продолжающаяся работа исследователей затрагивает вопросы оптимизации запросов, новых алгоритмов выполнения реляционных операций, оптимизации структур хранения данных и другие аспекты, непосредственно определяющие эффективность СУБД. Те же самые вопросы занимают и разработчиков коммерческих СУБД, которые, кроме того озабочены и более прикладными проблемами.
Метод темпорального расширения реляционной модели данных
Представление времени в модели. Будем рассматривать время как интервал целых чисел, на котором задан линейный порядок - отношение « » на множестве чисел. Для поддержки различных размерностей времени будем рассматривать не один такой интервал, а набор интервалов, элементами каждого из которых являются значения времени какой-либо одной размерности (например, «минуты», «дни» и др.). Для того чтобы иметь возможность сравнивать значения времени разной размерности, необходимо связать пары значений времени разных размерностей отношениями "является частью". Например, для связи размерностей «секунды» И «МИНуТЫ», ОТНОШеНИе «ЯВЛЯеТСЯ ЧаСТЬЮ» - ЭТО фуНКЦИЯ Минуты = секунды 60, где div - операция целочисленного деления. Дадим теперь формальное определение размерности.
Определение 1. Размерность времени (і - это либо интервал целых чисел Т. называемый интервалом, размерности (обозначается Т (д)), либо тройка (Т.г/, і -» ) где Т - интервал целых чисел, называемый интервалом, размерности. 7] - некоторая другая размерность, і 1 - - отношение «является частью» из интервала размерности ц в интервал Т, обладающее следующими свойствами:
Выработка требований
В связи с расширением области применения систем баз данных и включения в них новых типов данных возникает необходимость разработки новых методов хранения, так как такие традиционные и широко используемые структуры хранения как В-деревья [7, 36] далеко не всегда позволяют организовать эффективный доступ к данным. В системах автоматизированного проектирования (САПР) и автоматизированного управления технологическими процессами (АСУ ТП) часто требуется организовать хранение исторических (хронологических, темпоральных) данных [45]. Несмотря на то, что для темпоральных баз данных (ТБД) было предложено большое количество структур хранения [63], для эффективного решения конкретных практических задач возникает необходимость разработки новых методов хранения исторических данных. В данной главе предлагается метод индексирования исторических данных, который получил название SR -дерево, и представляет собой модификацию SR-дерева [48]. Данный метод позволяет организовать поиск и модификацию записей в исторических базах данных большого объема.
Традиционные базы данных храпят мгновенный снимок объектов модели предметной области, т. е. любое изменение объекта в базе данных приводит к тому, что предыдущее состояние объекта становится недоступным. В отличие от традиционных систем, ТБД позволяют сохранить информацию об эволюции объектов предметной области: для любого объекта, который был создан в момент времени tstart и закончил свое существование в момент времени tend, в базе данных будут сохранены все его состояния на временном интервале \tst!ITt,temi\. Таким образом, в ТБД при каждом изменении состояния объекта будет сохраняться запись в базе данных. Уникальный идентификатор такой записи состоит из ключа объекта и временного интервала, на котором данное состояние объекта было актуальным, и имеет следующий вид: {key, [Wt, W]}, где key - ключ записи, [tatart,tend] - временная метка записи. Важной особенностью ТБД является то, что в них возможны запросы не только по ключу, но и по времени. Например, произвести выборку всех состояний объекта с ключом к на временном интервале [/-1,] или получить состояния всех объектов, которые были актуальны в момент времени t (срез по времени ). Следовательно, методы хранения темпоральных баз данных должны эффективно поддерживать как запросы по ключу, так и по времени.
