Введение к работе
Актуальность темы. Пространственные методы доступа являются основой геоинформаннонных систем, а также широко используются в других областях применения СУБД, таких как временные базы данных, компьютерное зрение, базы знаний. САПР и др., требующих многоатрибутного индексирования.
Важным свойством таких систем является, с одной стороны, необходимость обеспечивать хранение больших объемов информации, а с другой стороны, необходимость эффективного выполнения различных операций с данными, использующих отношения пространственной близости и вложенности объектов.
Объемы данных, а также требования к эффективности их обработки не позволяют использовать в таких системах обычные методы индексирования такие как В+-деревья, различные варианты линейного хэширования и др., поскольку они позволяют выполнять индексирование только по одному атрибуту, что делает их неэффективными для пространственных запросов.
Все это делает необходимым использование специальных методов доступа к данным в таких системах.
Поэтому разработка пространственных методов индексирования для СУБД представляется весьма актуальной.
Цель работы. Целью диссертационной работы является разработка п улз'чшение методов пространственного индексирования для О'БД. а также разработка алгоритмов на основе пространственных методов доступа для индексирования текстов.
Методы исследования. При решении поставленных задач использовались методологические подходы, характерные для работ по моделированию баз данных и анализу эффективности методов индексирования. В частности, для сравнения различных методов или их моди-
фикаций проводились вычислительные эксперименты, и выполнялись аналитические оценки. Реализация системы сравнения прототипов методов индексирования выполнена на языке программирования С,
Научная новизна. Научную новизну составляют предложенные в диссертационной работе метод хранения пространственных ключей R-дерева, использующий локальные координаты узла; модификация алгоритма динамического удаления и вставки R'-дерева, улучшающая пространственную структуру индекса; динамически создаваемый локальный клеточный индекс, позволяющий сократить время поиска пути при вставке объекта в дерево; комбинированный алгоритм выполнения фильтрующего шага пространственного соединения R-деревьев, обеспечивающий низкую стоимость операций ввода/вывода при контролируемом использовании оперативной памяти и процессорного времени; клеточная эвристика, ускоряющая нахождение релевантных пар записей узлов соединяемых деревьев при выполнении операции пространственного соединения; использование ориентированных многоугольников для внутренних и внешних аппроксимаций пространственных объектов и для TR'-дерева, а также быстрый способ тестирования ориентированных многоугольников на пересечение; алгоритм, использующий пространственные методы доступа для индексирования текстов.
Практическая ценность. Практическая ценность работы определяется возможностью ее использования в любой СУБД, использующей пространственные методы доступа к данным.
Апробация работы. Основные результаты диссертации докладывались на семинарах лаборатории исследования операций, на ежемесячном семинаре Московской секции ACM SIGMOD в ноябре 1996 года, на международных симпозиумах "Advances in Databases and Information Systems" в 1994, 1995, 1996 годах. По теме диссертации опубликованы работы [1-4].
Структура и объем работы. Диссертация состоит из 6 глав, в
