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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

ГГолухин Александр Леонидович

МЕТОДЫ ДОСТУПА К ХРОНОЛОГИЧЕСКИМ ДАННЫМ В РЕЛЯЦИОННЫХ СИСТЕМАХ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2006

Работа выполнена на кафедре информатики математика-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук, профессор Братчиков Игорь Леонидович

Официальные оппоненты: доктор технических наук, профессор Копыльцов Александр Васильевич, кандидат физико-математических наук» доцент Графеева Наталья Генриховна

Ведущая организация:

Санкт-Петербургский институт информатики и автоматизации РАН.

Защита диссертации состоится "30" года в 1 ¿Г часов на

заседании диссертационного совета Д 212.232.51 по защите диссертаций на соискание учёной степени доктора наук при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 28, математнко-механический факультет, ауд. Ч О ^

С диссертацией можно ознакомиться в Научной библиотеке имени М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан октября 2006 года.

Учёный секретарь диссертационного совета, доктор физико-математических наук

Мартыненко Б.К.

1. Общая характеристика работы

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

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

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

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

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

Объектом исследования являются размерности времени, промежутки времени, календари, операторы для работы с ними, алгоритмы построения Я-деревьев.

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

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

1. Обоснование и выбор подходов для расширения реляционной модели данных хронологическими понятиями.

2. Выбор и реализация операторов для работы с темпоральным расширением.

3. Обоснование возможности использования Я-деревьев для поиска хронологических данных.

4. Разработка алгоритма построения К-деревьев с минимализацией перекрытий на неравномерных данных.

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

Научная новизна. Предлагаемая диссертация содержит следующие новые результаты, полученные лично автором:

1. Определены базовые понятия темпорального расширения реляционной модели данных.

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

3. Использованы Я-деревья, для доступа к хронологическим данным, по отрезкам времени, представленным в виде двумерных отрезков.

4. Разработан метод построения Я-деревьев с минимализацией перекрытий на неравномерных двумерных данных.

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

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

Личный вклад автора. Все основные результаты диссертации получены автором самостоятельно.

Апробация работы. Научные результаты и основные положения работы представлялись на конференциях:

1. IX Санкт-Петербургская международная конференция «Региональная информатика-2004».

2. XXXVI межвузовская научная конференция аспирантов и студентов «Процессы управления и устойчивость».

Реализация. Полученные результаты реализованы в виде тестовой программной системы на языке программирования С#.

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

Структура и объем диссертационной работы. Диссертация состоит из введения, трех глав, заключения, она излагается на 103 страницах, включая перечень используемой литературы из 77 наименований. Кроме того, в диссертации имеется приложение на 10 листах, содержащее в себе примеры разработанных программ, реализующих алгоритмы, описанные в диссертации.

2. Содержание работы

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

В первой главе «Подходы к формализации модели данных. Опыт использования различных моделей данных в СУБД» обсуждается современное состояние подходов к решению проблемы организации и доступа к данным; проанализированы направления развития моделей данных, рассмотрены основные существующие модели и системы их реализующие.

Рассмотрены различные методы организации упорядоченных данных (последовательностей) и хронологических данных в частности.

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

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

В связи с указанными сложностями, за последние 15 лет было предложено довольно много специализированных моделей данпых для работы с последовательностями. Однако, как показано далее, все они не лишены недостатков. Одним из индикаторов актуальности создания универсальной СУБД для работы с последовательными данными является крайне высокая стоимость специализированных исторических СУБД (которые решают лишь часть проблем хранения и обработки последовательностей), таких как IndustrialSQL Server, PI Data Storage и др.

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

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

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

1. Отсутствие интеграции с реляционной моделью и реализация всей требуемой функциональности в рамках cneifuanтированной модели. Основным недостатком такого подхода является необходимость повторения функциональности реляционной модели в рамках специализированной модели данных.

2. Представление последовательности или группы последовательностей в виде отношения особого типа, для которого действуют все реляционные операторы, Реализация такого подхода требует создания минимальной надстройки над реляционной моделью (по этому наиболее проста). Однако такой подход имеет рад недостатков, а именно:

2.1. сложность эффективной реализации операторов над последовательными данными;

2.2. невозможность динамического добавления/удаления последовательностей в БД без использования DDL - операций (операций описания данных, сокращение от Data Definition Language);

2.3. невозможность выборки нескольких последовательностей на основе некоторого критерия (к примеру, выборки последовательных показаний датчиков, установленных в одном помещении).

3. Представление последовательностей в релягщонной модели в виде значений атрибутов абстрактного типа. Такое представление последовательностей лишено всех недостатков предыдущего подхода и часто используется для реализации моделей последовательных данных на базе объектно-реляционных СУБД. Однако при реализации последовательности в виде абстрактного типа данных все операции над последовательностями реализуются в виде функций, вызываемых из тела запроса на языке SQL. Поскольку оптимизатор SQL ничего не знает о реализации таких функций, оптимизация сложных выражений над последовательными данными невозможна,

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

. себе последовательность А, содержащую коды некоторых ошибок, соответствующие последовательным меткам времени. При этом подробная информация о каждом коде ошибки может содержаться в обычном отношении В. Для получения последовательности, содержащей информацию об ошибках, необходимо выполнить реляционный оператор соединения последовательности А и отношения В. Если

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

5. Расширение понятия «отношения» за счет добавления к нему последовательностей в качестве третьего измерения и расширение всех реляционных операторов для манипулирования отношениями нового типа. Такой подход достаточно труден в реализации, однако лишен всех недостатков, свойственных предыдущим подходам. Используем именно такой подход. В полноценных многомерных БД именно такой подход естественней для работы с последовательностями, реляционную же модель потребуется расширить.

Таким образом, делается вывод о целесообразности применения последнего из рассмотренных подходов.

Во второй главе «Описание используемого способа расширения реляционной модели данных» описано хронологическое расширение реляционной модели данных и примеры его использования. Ниже приводится его сокращенное описание.

Время рассматривается как интервал целых чисел, на котором задан линейный порядок - отношение «<» на множестве чисел. Для поддержки различных размерностей времени рассматривается не один такой интервал, а набор интервалов, элементами каждого из которых являются значения времени какой-либо одной размерности (например, «минуты», «дни» и др.). Для того чтобы иметь возможность сравнивать значения времени разной размерности, пары значений времени разных размерностей должны быть связаны отношениями «является частью». Было дано формальное определение размерности времени.

Размерность времени ц — это либо интервал целых чисел Т, называемый интервалом размерности (обозначается г(//)), либо тройка где Т —

интервал целых чисел, называемый интервалом размерности, 7 — некоторая другая размерность, — отношение «является частью» из интервала

размерности 7 в интервал т, обладающее следующими свойствами: • это сюръективная функция;

где область определения

В случае если размерность ц описывается тройкой (г,?,/^^,), будем говорить, что размерность м задана через размерность 7. Было также определено понятие метки времени.

Метка времени — это пара где ц — это размерность времени, а г — целое число из интервала г(ц), называемое значением времени.

Отношение "является частью*1 предназначено для задания новых размерностей времени на базе существующих. Кроме того, оно служит для преобразования меток времени одной размерности в метки времени другой размерности.

. Пусть задана размерность Если для сюръекции F^

множество значений {г,,...,^} является прообразом для значения г, то будем говорить, что (г,м) состоит из {(г^т?),,..,(г*, 17)}. Будем записывать это следующим образом: (г, ~ {(г, - - - ^ (гл. ^7)} * Если при этом размерность 7 задана через размерность v, и каждая из меток (г,,7) состоит из {(r^vX-.-.O^.v)}, то

также будем говорить, что (гсостоит из а размерность ft

задана (транзитивно) через размерность v. Факт того, что размерность м задана через размерность 17 (напрямую или транзитивно) будем обозначать следующим образом: п^М- Будем также считать, что для любой размерности // имеет место и для любых меток времени {т,м) выполняется

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

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

Размерности времени ц и ц называются сравнимыми, если существует размерность v (общая размерность), что ¡л и 17 заданы через v (напрямую или транзитивно).

Пусть р и 7 — сравнимые размерности времени, v — их общая размерность (произвольная), т.е. v-*/*, и пусть (г2,7)~Я, где м

и Я — некоторые множества меток времени размерности v. Тогда:

• если для любой общей размерности времени к выполняется условие Ms Я, то будем говорить, что (г|(//) входит в и записывать это следующим образом:

• если для любой общей размерности времени v выполняется следующее условие: <r„t то будем говорить, что (гx,ft) раньше чем (га,7), а {тг,п) позже чем (г,,//), и записывать это следующим образом:

• если для любой общей размерности времени н выполняется м[)н, то будем говорить, что (г,,¡j) пересекается с fo,?), и записывать это следующим образом: (г|,^)П(г2,>/)*<з.

С практической точки зрения важна задача нахождения всех меток

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

Будем говорить, что размерность времени ц «агрегируется в» размерность //, (^37)» если они сравнимы, и для любых размерностей времени v таких, что V-* ц и к-и7, выполнено следующее условие: v(r, Т}\3(г,, fi)-{(гл, v\..., (гй к)},,i = 1....к:

(^V) - (_YJ0-„, v\..(г4, v )}

причем метки времени зависят только от (г, 17) и не зависят от

выбора у.

Будем говорить, что размерность времени ¡л «точнее чем» размерность 7 (^77), если они сравнимы, и выполнено следующее условие: У(г,//),Э(г»:(г,/|)с(т\7).

Мы определили метку времени как целое число с указанием размерности. Такое представление, несомненно, является удобным для хранения меток времени в базе данных и для выполнения вычислений, но не является ни привычным, ни удобным для пользователя. В реальной жизни люди пользуются метками времени, представленными по структурным (относительным) шкалам, таким как «годышесяцыгсутки» и др. Поэтому мы определим понятие шкалы времени и способ представления любой метки времени по любой шкале.

Введем оператор, возвращающий первую метку времени размерности 7, пересекающуюся с заданной меткой времени (г,/*) (обозначим этот оператор first((r,M\fj)X следующим образом:

• если размерности м и ц сравнимы, то ßrst((rt А^п)^^, где г^, =л1ш{г':(г,/|)П(г',я)*®}» т.е. это минимальное значение из таких г', что метка времени (г',7) пересекается с (г,я); а если при этом таких г' нет, то оператор first((T,v\?j) не определен;

• если ц и 7) несравнимы, то для них оператор firstiir.fi), tj) не определен.

Аналогично определим оператор /а«((г,/Д 7), возвращающий последнюю метку времени размерности 7, пересекающуюся с заданной меткой времени

Пусть jut,i = \...n, — различные сравнимые размерности времени. Тогда запись вида :...: д, будем называть шкалой времени.

Пусть размерность времени 7 сравнима с /t„i-l...n. Будем называть представлением метки времени (г,7) по шкале^ запись вида (rt 7), где:

Если при этом результат хотя бы одного используемого в данном определении оператора first не определен, то будем считать, что метка времени (г,т?) не представима по шкале t\

Было также сформулировано достаточное условие однозначности представления меток времени по шкале.

Пусть задана шкала времени #:...: д, и размерность времени j? . Пусть при этом выполняется условие ^ <rj или Тогда, для любой метки времени

(гесли существует представление по шкале Мяу то оно однозначно определяет эту метку времени.

Данное утверждение служит базой для проверки корректности представления меток времени по шкале.

У шкал имеется два основных назначения:

1. представление пользователю меток времени, хранящихся в базе данных, в удобном для него виде;

2. предоставление пользователю возможности самому задавать интересующие метки времени в удобном для него виде, а также задавать новые размерности времени и календари.

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

При задании метки времени (1,17) через ее представление (т, :...:тй,т?) по шкале уц :...://„ кроме явного указания элементов г,, будем также использовать обозначение last. Данное обозначение, встречающееся на месте tip обозначает следующее:

last((jirst((T, jjI ), Mi-1 Ы)" f'rst((first((t. r}\ Mt-i \ Щ- \

Например, если задана шкала годы'.недели, то представление (2003 \last, недели) определяет последнюю неделю 2003 года.

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

Множество меток времени одной размерности будем называть календарем.

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

Отношение «является частью» при определении новых размерностей

времени можно задавать следующим образом: внутри диапазона значений времени t(ij) выделить непересекающиеся непустые подмножества, пронумеровать эти подмножества подряд идущими целыми числами, и считать, что каждому значению времени размерности т), принадлежащему такому

подмножеству, ставит в соответствие значение времени размерности м* являющееся номером этого подмножества.

В этом случае полностью определяется двумя свойствами:

• набором подмножеств множества значений времени размерности ц ;

• нумерацией этих подмножеств,

Задав эти два свойства, мы определяем отношение "является частью". Именно таким образом определяется это отношение для размерностей времени.

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

В третьей главе «Методы индексирования хронологических данных» исследуется возможность представления хронологических данных в виде пространственных и, как следствие, применение к ним соответствующих методов индексации.

Основное направление исследований в области управления пространственными данными - это структуры данных для хранения и представления пространственных данных. Результаты этих исследований были внедрены в ряде географических информационных систем (GIS - geographical information system). Наиболее популярны среди известных структур данных R-деревья, которые используются для представления неточечных объектов (в частности прямоугольных областей). Серьезная проблема, связанная с R-деревьями, заключается в том, что они допускают перекрытие ограничивающих прямоугольников. Поскольку каждый объект, находящийся в одной из этих перекрывающихся областей, принадлежит только одному ограничивающему прямоугольнику, то в общем случае требуется просмотр множества ветвей дерева индексации. Для R-деревьев были предложены некоторые оптимизирующие методы.

R-дерево представляет собой разновидность сильиоветвящегося дерева. Внутренние узлы дерева представляют собой набор записей вида (cp,Reci)y где ср является указателем на узел-потомок, a Rect — минимальным прямоугольником, который покрывает все прямоугольники узла-потомка. Лист дерева представляет собой набор записей вида (Oid^Rect), где Oid является ссылкой на запись в базе данных, которая описывает геометрический объект, а Rect является минимальным прямоугольником, который покрывает данный

геометрический объект. Пусть М есть максимальное число записей узла, а т является минимальным числом записей узла (2 <= от <= Л//2). Тогда для К.-дерева должны выполняться следующие условия:

- корень дерева имеет не менее двух потомков, если он не является листом;

- внутренний узел имеет не менее т и не более А/ потомков, если он не является корнем;

- каждый лист имеет не менее т и не более М записей, если он не является корнем;

-все листья находятся на одном и том же уровне.

Практическое сравнение эффективности различных вариантов Я-деревьев проведено в ряде работ. Наиболее быстродействующими из них являются К*-деревья, поэтому в дальнейшем в данной работе использована именно эта разновидность Я-деревьев.

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

Данная индексная структура предназначена для эффективного выполнения регионального поиска, поэтому основная идея дерева заключается в разбиении пространства в каждом узле дерева на минимально пересекающиеся труппы, что позволяет при выполнении поиска эффективно отсекать неверные ветви работы алгоритма. Задача разбиения в общем случае, видимо, по меньшей мере является ЫР-полной, так как в настоящее время даже для двух групп не известно полиномиального алгоритма. Поэтому во всех алгоритмах построения Я-деревьев используются эвристические подходы, дающие на реальных данных далеко не оптимальные разбиения.

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

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

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

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

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

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

min Ts(jt(n*,)

, где 5 - функция площади.

Предлагается следующая стратегия построения R-дерева, близкого к оптимальному.

Алгоритм построения дерева

По заданному множеству из N объектов Е, строим R-дерево с

параметрами т, М [1].

Шаг 1. Начало. Построим корень дерева и определим количество уровней дерева по формуле ¿(w)=flogw JV"}.

Шаг 2. Построение дерева. Вызовем алгоритм построения узла, передав ему в качестве параметра корень дерева и всё множество объектов.

Алгоритм построения узла

По заданному множеству из N объектов Е, и узлу Т строим потомков

узла, имеющего уровень L (¿ = 1 для листьев).

Шаг 1. Построение листьев. Если L = 1, то заполняем узел объектами Е,

и заканчиваем.

Шаг 2. Выбор количества потомков узла. Вычисляем количество потомков у данного узла по формуле К -1.

Шаг 3. Построение узлов. Вызываем алгоритм разделения на группы для разбиения всего множества объектов на К групп, минимизируя сумму попарных пересечений групп. При этом в алгоритм передаем номер уровня L для правильной оценки минимального и максимального допустимого количества объектов в группах. Для каждой полученной группы строим пустой узел — потомок текущего узла и вызваем для него рекурсивно алгоритм построения узла с этой группой в качестве множества.

Наиболее сложной частью предложенной стратегии является алгоритм разделения на группы, от трудоёмкости которого зависит общая сложность алгоритма. Предлагается вариант данного алгоритма.

Алгоритм разбиения множества объектов па минимально пересекающиеся группы

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

Неравномерный алгоритм разделения на группы Заданное множество из N объектов Е, делим на К групп с соблюдением ограничения на количество объектов в группах снизу mL~l и сверху Mi_1, где I — текущий строящийся уровень дерева.

Шаг 1. Разделение на две группы. Вызываем алгоритм разделения на две группы, передав в качестве аргументов всё множество объектов Е, и соотношение разделения ([АГ/2]):(^-[^/2]) для получения групп С?, и G2.

Шаг 2. Рекурсивное разделение. Если [К/2] >1, то вызываем алгоритм разделения на группы, передав в качестве аргументов полученную группу G, с параметром деления [К/2], иначе выдаем в качестве результата G,. Если К-[К/2]>1, то вызываем алгоритм разделения на группы, передав в качестве аргументов полученную группу G2 с параметром деления К-[К/2], иначе выдаем в качестве результата Ga.

Алгоритм разделения на две группы Заданное множество из N объектов Е, делим на 2 группы в заданном соотношении площадей kit с соблюдением ограничения на количество объектов снизу к-ти сверху к-М1'1 для первой группы, а также снизу l-m1'1 и сверху 1-Мм для второй, где I —текущий строящийся уровень дерева.

Шаг 1. Выбор оси координат для сортировки. Выберем такую ось координат i, на которой достигается максимальное значение выражения

шах

' шах RiJ ~ min R(J"

фшуры) *«JY1>U |

шах Rl* - min RJ/

<jmryptij 4>"DT)Hj

где RiJ и я*'- соответственно меньшее и большее значение /-й координаты минимального объемлющего j-ю фигуру прямоугольника.

Шаг 2. Разделение по группам. Разделим все объекты на три части по значению Р'Ц) - + );2 для выбранного г по квантилям уровня а и 1-а

(а е [0;0,5]— параметр разделения по труппам): из наименьшей по значениям части образуем первую группу объектов, а из наибольшей - вторую группу. Оставшиеся объекты распределим по группам в шагах 3 и 4.

Шаг 3. Проверка завершения. Если все объекты распределены, то заканчиваем. Если одна из групп в результате дальнейших операций будет недополнена (количество объектов в группах pl <k-mL~1 или рг <1-т1'1), то вставим в неё все оставшиеся объекты и закончим. Если одна из групп в результате дальнейших операций будет переполнена (количество объектов в группах px>k-ML~l или pi>I-ML~,\ то вставим в другую группу все оставшиеся объекты и закончим.

Шаг 4. Распределение объектов. Берем любой нераспределённый объект и помещаем его в группу, размер которой увеличится в минимальной степени при взвешивании по к и /. Переходим на шаг 3.

На втором шаге работы алгоритма разделения присутствует параметр а разделения по группам. Для установления его влияния на качество получаемого

разбиения было проведено экспериментальное моделирование работы глобального алгоритма построения Я-дерева, использующего алгоритм разбиения «Разделяй и властвуй». При этом было установлено, что уменьшение значения а приводит к некоторому улучшению структуры К-дерева на неравномерных распределениях и распределениях со значительным перекрытием объектов. С другой стороны, это приводит к снижению скорости работы алгоритма и уменьшению качества разбиения на точечных и регулярных наборах данных.

Суммируя достоинства и недостатки поведения алгоритма при разных значениях а на различных распределениях объектов, эмпирически было выбрано значение параметра разделения для универсального применения, равное 0,45. При этом если на практике имеются некоторые сведения о реальном распределении объектов, то значение параметра а, вероятно, стоит оценить дополнительно в зависимости от требований конкретной задачи.

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

соответствует больший процент попадания в нужные узлы при поиске.

*

В заключении содержится перечень задач, которые были решены в результате диссертационного исследования, а также сведения об апробации и внедрении результатов работы.

3. Основные результаты работы

В представленной работе для достижения поставленных задач решены следующие вопросы.

1. Изучены существующие и перспективные методы организации доступа к данным, в частности хронологическим.

2. Разработано специальное расширение реляционной модели для работы с хронологическими данными.

3. Разработан набор операторов для работы с предложенным расширением.

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

5. Предложен алгоритм построения Я-деревьев на неравномерных данных с минимализацией перекрытий.

6. Проведена оценка трудоемкости предложенного алгоритма.

4. Публикации автора по теме диссертации:

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

[1] Полухин А.Л. Методы доступа к пространственным данным. — IX Санкт-Петербургская международная конференция «Региональная информатика-2004». Материалы конференции., СПб, 2005, стр.7581.

[2] Полухин А.Л. Метод темпорального расширения реляционной модели данных. — XXXVI межвузовская научная конференция аспирантов и студентов «Процессы управления и устойчивость». Материалы конференции., СПб, 2005.

[3] Полухин А.Л. Операторы темпорального расширения реляционной модели данных. // Вестник С.-Петерб. ун-та. Сер.10. март 2006. Вып.1. С.123-132.

Подписано в печать 12.10.2006 Формат 60x84 1/1 (¡.Бумага офсетная. Печать офсетная. Усл. печ. л. 1,2. Тираж 100 экз. Заказ Ха 382,

Отпечатано в ООО «Издательство "ЛЕМА"»

199004, Россия, Санкт-Петербург, В.О., Средний пр., д.24, тел./факс: 323-67-74 e-mail: izd_lema@mail.ru

-/ÖC

Аннотация 2Снисок сокран];ений и условных обозначений

Глава 1. Подходы к формализации модели данных. Оныт ис-нользования различных моделей данных в СУБД

1.1 Подходы к организации доступа к данным И

1.2 Выработка требований

1.3 Постановка задачи повышения эффективности доступа к хро-нологическим данным

Глава 2. Описание используемого способа расп1ирения реля-ционной модели данных

2.1 Метод темпорального расширения реляционной модели данных

2.2 Операторы для задания размерностей времени

2.3 Операторы для задания календарей

2.4 Операторы работы с темноральным расширением

2.5

Выводы но второй главе

Глава 3. Методы индексирования хронологических данных

3.1 Выработка требований

3.1.1 Особенности темнорального индексирования

3.1.2 SR-дерево

3.1.3 ЗК*-дерево

3.2 Управление пространственными данными

3.3 Алгоритмы улучшения качества R-деревьев

3.3.1 Глобальные алгоритмы

3.3.2 Алгоритмы разбиения множества объектов на мини-мально пересекаюЕдиеся грунпы

3.4 Практический анализ глобальных алгоритмов

3.5 Расширяемая архитектура

3.6

Выводы но третьей главе

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

Глава 1 содержит обзор современного состояния подходов к решению проблемы организации и доступа к данным; проанализированы направления развития моделей данных, рассмотрены основные существующие модели и системы их реализующие. Рассматриваются различные подходы к организации упорядоченных данных (последовательностей) и хронологических данных в частности. Даются наиболее характерные примеры практической работы с хронологическими данными в СУБД. Выявляются общие черты, достоинства и недостатки обсуждаемых подходов. Завершается глава указанием наиболее перспективного подхода к работе с хронологическими данными, постановкой целей и задач исследования.

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

Глава 3 посвящена методам индексации хронологических данных в СУБД. Первая часть главы посвящена описанию особенностей организации эффективного доступа к хронологическим данным. В ней так же предлагается метод переноса подходов к работе с пространственными данными на хронологическую модель. Вторая часть содержит ряд деталей работы с пространственными данными, а также особенности обработки пространственных соединений. Третья часть посвящена ключевому моменту использования предложенного подхода для хронологических данных, а именно алгоритму построения индекса. На основе более простых решений предлагается свой алгоритм. В оставшейся части главы проведен анализ полученных в ней результатов и излагается ряд предложений по направлению разработок, с целью дальнейшего повышения эффективности работы с хронологическими данными. Глава так же заканчивается выводами из полученных в ней результатов.

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

Оглавление.

Аннотация 2

Список сокращений и условных обозначений 7

Введение 8

3.6 Выводы по третьей главе

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

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

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

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

Заключение.

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

Также в этой работе был предложен новый метод доступа для хранения исторических данных, который получил название ЗЯ*-дерево; рассматриваются вопросы формирования и организации сегментов данных для исторических БД с большим числом записей. К SR*-дереву, как разновидности R-дерева применимы подходы, используемые для пространственных данных. В работе приведены алгоритмы построения оптимизированных R-деревьев, наиболее перспективных и популярных структур хранения и индексации, предложенных к настоящему времени. И наконец, показана возможная схема расширяемой архитектуры обработчика запросов.

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

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

Резюмируя, для достижения поставленных задач решены следующие вопросы.

1. Разработано специальное расширение реляционной модели для работы с хронологическими данными.

2. Разработан набор операторов для работы с предложенным расширением.

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

4. Предложен алгоритм построения R-деревьев на неравномерных данных с минимализацией перекрытий.

5. Проведена оценка трудоемкости предложенного алгоритма.

Основные положения и отдельные результаты работы докладывались и обсуждались на следующих конференциях:

• XXXVI межвузовская научная конференция аспирантов и студентов «Процессы управления и устойчивость» (Санкт-Петербург, 2005)

• IX Санкт-Петербургская международная конференция «Региональная информатика - 2004» (РИ-2004) (Санкт-Петербург, 2004)

1. Аткинсон М. и др. Манифест систем объектно-ориентированных баз данных // Системы Управления Базами Данных, №4, 1995, с.142-155.

2. Дейт К.Дж. Введение в системы баз данных, 7-е издание: Пер. с англ.- М.: Издательский дом "Вильяме 2001 1072 с.

3. Гуляев А.И. Временные ряды в динамических базах данных. М.: Радио и связь, 1989 г. - 128с.

4. Иванов А.Ю., Саенко И.Б. Основы построения и проектирования реляционных баз данных. СПб: ВАС, 1998 г. - 80с.

5. Ким В., Гарза Ж.Ф., Грэхэм Б. Пути развития объектно-реляционных технологий баз данных. // Системы управления базами данных, №04, 1996.

6. Кирстен В., Иренгер И., Рёриг Б., Шульте П. СУБД Cache': объектно-ориентированная разработка приложений. СПб, "Питер 2001.

7. Кнут Д.Э. Исскуство программирования, Том 3: Сортировка и поиск.- М.: Издательский дом Вильяме, 2000.

8. Когаловский М.Р. Расширение реляционной модели баз данных временных рядов // Управляющие системы и машины. 1994. № 6.

9. Кречетов Н., Петухова Е., Скворцов В., Умников А., Щукин Б. Постреляционная технология Cache' для реализации объектных приложений. -М, МИФИ, 2001.

10. Маслов Д.В. Модель баз данных для хранения и обработки упорядоченных данных в АСУТП и экономических приложениях. // Промышленные АСУ и контроллеры. 2003. № 12

11. И. Маслов Д.В. Некоторые вопросы функциональности и производительности WinCC версии 5.1 // Промышленные АСУ-и контроллеры. 2003. №6. с. 45-46.

12. Мейер Д. Теория реляционных баз данных./ Пер. с англ. М.: Мир, 1987 г., 608с.

13. Полухин A.JI. Методы доступа к пространственным данным. IX Санкт-Петербургская международная конференция "Региональная информатика-2004". Материалы конференции., СПб, 2005, с.75-81.

14. Полухин A.JI. Метод темпорального расширения реляционной модели данных. XXXVI межвузовская научная конференция аспирантов и студентов "Процессы управления и устойчивость". Материалы конференции., СПб, 2005.

15. Полухин A.JI. Операторы темпорального расширения реляционной модели данных. // Вестник С.-Петерб. ун-та. Сер.10. 2006. Вып.1. с.123-132.

16. Прохоров А. Использование объектно-реляционных СУБД для хранения и анализа временных рядов. //КомпьютерПресс. 2001. - №6.

17. Сидоров А.А., Маслов Д.В. (Самара, ООО НВФ "CMC"). Реляционно-темпоральная модель данных.

18. Скворцов А.В. Алгоритмы улучшения качества R-деревьев. Томский госуниверситет, 2001.

19. Смирнов В. Системы хранения данных тенденции, решения, перспективы. //Корпоративные системы. - 2002. - №3 - С. 24-29.

20. Чемберлин Д. Анатомия объектно-реляционных баз данных // Системы Управления Базами Данных, №1-2, 1998, с.3-24.

21. Энсор Д., Стивенсон Й. Oracle. Проектирование баз данных: Пер. с англ. К.: Издательская группа BHV, 1999 - 560 с. ISBN 966-552-019-9

22. Allen J. F. Time and time again: The many ways to represent time. // International Journal of Intelligent Systems 6 (4), July 1991. New York, USA. - John Wiley & Sons, Inc, 1991. - p. 341-356.

23. Batory D. et al. GENESIS: An Extensible Database Management System. IEEE Trans, on Software Engineering, vol. 14, no. 11, Nov. 1988.

24. Beckman N., Kriegel H.-P., Schneider, Seeger B. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. Proc. ACM SIGMOD, 1990.

25. Bertino E., Kim W., and Garza J. Composite Objects Revisited. Proc. ACM SIGMOD Intl. Conf. on Management of Data, Portland, Oregon, June 1989.

26. Bettini C., Dyreson C.E., Evans W.S., Snodgrass R.T., Wang X.S. A Glossary of Time Granularity Concepts. Temporal Databases: Research and Practice, Eds. Etzion 0., Jajodia S., Sripada S., Springer-Verlag, 1998.

27. Bettini C., De Sibi R. Symbolic Representation of User-defined Time Granularities. Annals of Mathematics and Artificial Intelligence, 2000, Vol. 30, No. 1-4, pp. 53-92.

28. Bettini C., Wang X.S., Bertino E., Jajodia S. Semantic Assumptions and Query Evaluation in Temporal Databases. ACM SIGMOD Conference, 1995, pp. 257-268.

29. Bettini C., Wang X.S., Jajodia S. A General Framework for Time Granularity and Its Application to Temporal Reasoning. Annals of Mathematics and Artificial Intelligence, 1998, Vol. 22, No. 1-2, pp. 29-58.

30. Bliujute R. R-Tree Based Indexing of Now-Relative Bitemporal Data. -Proc. VLDB Conf., 1998.

31. Bozkaya Т., Ozsoyoglu M. Indexing Transaction Time Databases. -Information Sciences, 1998.

32. Chandra R., Segev A. Managing Temporal Financial Data in an Extensible Database. Proceedings of the 19th Conference on Very Large Databases,1993, pp. 302-313.

33. Chou H.T., Kim W. A Unifying Framework for Versions in a CAD Environment. Proc. Intl. Conf. on Very Large Data Bases, August 1986, Kyoto, Japan.

34. Chou H.T., Kim W. Versions of Schema for Object-Oriented Databases. Proc. Intl. Conf. on Very Large Data Bases, Long Beach, Calif., Sept. 1988.

35. Clifford J., Warren D.S. Formal semantics for time in databases. ACM Transactions on Database Systems, 1983, Vol. 8 , No. 2, pp. 214-254.

36. Comer D. The Ubiquitous B-tree. ACM Сотр. Surv., 11(2), 1979.

37. Date C.J., Darwen H., Lorentzos N. Temporal Data & the Relational Model (1st edition). Morgan Kaufmann, 2002, 480 pages.

38. Dreyer W., Kotz A.D., Schmidt D. An Object-Oriented Data Model for a Time Series Management System. Proceedings of the 7th International Working Conference on Scientific and Statistical Database Management,1994, pp. 186-195.

39. Dyreson C.E., Evans W.S., Lin H., Snodgrass R.T. Efficiently Supported Temporal Granularities. IEEE Transactions on Knowledge and Data Engineering, 2000, Vol. 12, No. 4, pp. 568-587.

40. Easton M. Key-Sequence Data Sets on Indelible Storage. IBM Journal of Research and Development, 30(3), 1986.

41. Faloutsos С., Sellis Т., and Roussopoulos N. Analysis of Object-Oriented Spatial Access Methods. Proc. ACM SIGMOD Intl. Conf. on Management of Data, San Francisco, Calif., May 1987, pp. 426-439.

42. Freytag J. A Rule-Based View of Query Optimization. Proc. ACM SIGMOD Intl. Conf. on Management of Data, pp. 173-180, San Francisco, Calif., 1987.

43. Greene D. An Implementation and Perfomance Analysis of Spatial Data Access Methods. Proc. Data Engineering, 1989.

44. Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching. -Proc. ACM SIGMOD, 1984.

45. Jensen C.S. A Consensus Glossary of Temporal Database Concepts. ACM SIGMOD Rec., 23(1), 1994.

46. Katz R. Towards a Unified Framework for Version Modelling in Engineering Databases. ACM Computing Surveys, vol. 22, no. 4, Dec. 1990, pp. 375408.

47. Kim W., Ballou N., Garza J., Woelk D. A Distributed Object-Oriented Database System Supporting Shared and Private Databases. ACM Trans, on Office Information Systems, Jan. 1991, pp. 31-51.

48. Kolovson C.P., Stonebraker M. Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. Proc. ACM SIGMOD, 1991.

49. Kriegel H., Schiwietz M., Schneider R., Seeger B. // Proc. Symp. On the Design and Implementation of Large Spatial Databases, Santa Barbara. -1989. P.413-418.

50. Leban В., McDonald D., Forster D. A Representation for Collection of Temporal Intervals. Proceedings of the AAAI-1986, 5th International Conference on Artificial Intelligence, 1986, pp. 367-371.

51. Lin L., Risch Т., Skuld M., Badal D. Indexing Values of Time Sequences- Proceedings of the 5th International Conference on Information and Knowledge Management, 1996, pp. 223-232.

52. Lin L., Risch T. Quering Continuous Time Sequences Proceedings of the 24th International Conference on Very Large Databases, 1998, pp. 170-181.

53. Lomet D.B., Salzberg B. The Perfomance of a Multiversion Access Method.- Proc. ACM SIGMOD, 1990.

54. Maurer W.D., Lewis T.G. Hash Table Methods. ACM Сотр. Surv., 7(1), 1975.

55. Niezette M., Stevenne J. An Efficient Symbolic Representation of Periodic Time. Proceedings of the International Conference on Information and Knowledge Management, Lecture Notes in Computer Science, 1993, Vol. 752, pp. 161-168.

56. Ning P., Wang X.S., Jajodia S. An Algebraic Representation of Calendars // Annals of Mathematics and Artificial Intelligence. 2002. Vol. 36, No. 1-2. Pp. 5-38.

57. Oracle8i Concepts. Release 2 (8.1.6). December 1999. Part No. A76965-01

58. Oracle8i Administrator's Guide. Release 2 (8.1.6). December 1999. Part No. A76956-01

59. Oracle8i Time Series User's Guide. Release 8.1.5. February 1999. A67294-01

60. Ramakrishnan R., Donjerkovic D., Ranganathan A., Beyer K.S., Krishnaprasad M. SRQL: Sorted Relational Query Language. Proceedings of the 10th International Conference on Scientific and Statistical Database Management, 1998, pp. 84-95.

61. Shasha D. Time Series in Finance: the array database approach, http: / / www. cs. nyu. edu/cs/faculty / shasha/papers / j agtalk.html

62. Richardson J. Supporting Lists in a Data Model (A Timely Approach). -Proceedings of the 18th International Conference on Very Large Databases, 1992, pp. 127-138.

63. Salzberg В., Tsotras V.J. Comparison of Access Methods for Time-Evolving Data. ACM Сотр. Surv., 31(2), 1999.

64. Schmidt D., Dittrich K.A., Dreyer W., Marti R. Time Series, a Neglected Issue in Temporal Database Research / Proceedings of the Int. Workshop on Temporal Databases. 1995.

65. Segev A., Shoshani A. A Temporal Data Model Based on Time Sequences. Temporal Databases - Theory, Design and Implementation, Eds. Tansel A.U. et al., The Benjamin/Cummings Publishing Company, 1993, pp. 248269.

66. Segev A., Shoshani A. Logical Modeling of Temporal Data. Proceedings of ACM SIGMOD Conference, 1987, pp. 454-466.

67. Sellis Т., Roussopoulos N., Faloutsos C. The R-Tree: A Dynamic Index for Multi-Dimensional Objects. Proc. VLDB Conf., 1987.

68. Seshadri P. Management of Sequence Data. Ph.D. Thesis, University of Wisconsin, Computer Science Department, 1996.

69. Seshadri P. SEQ: A Model for Sequence Databases. 1995.

70. Seshadri P., Livny M., Ramakrishnan R. The Design and Implementation of a Sequence Database System. Proceedings of the 22th International Conference on Very Large Databases, 1996, pp. 99-110.

71. Snodgrass R., Aim I. Temporal Databases. IEEE computer, vol. 19, no. 9, Sept. 1986, pp. 35-42.

72. Snodgrass R. The Temporal Query Language TQuel. ACM Trans, on Database Systems, vol. 12, no. 2, June 1987, pp. 247-298.

73. Stonebraker M. The Design of the Postgres Storage System. Proc. VLDB Conf., 1987.

74. Varman P.J., Verma R.M. An Efficient Multiversion Access Structure. -IEEE Trans, on Knowledge, Data Engineering, 9(3), 1997.

75. Wang X.S., Bettini C., Brodsky A., Jajodia S. Logical Design for Temporal Databases with Multiple Granularities. ACM Transactions on Database Systems, 1997, Vol. 22, No. 2, pp. 115-170.

76. Woelk D., Kim W. Multimedia Information Management in an Object-Oriented Database System. Proc. Intl. Conf. on Very Large Data Bases, Brighton, England, Sept. 1987, pp. 319-329.

77. Yao F.F., van Leeuwen J. Computational Geometry. Handbook of Theoretical Computer Science, Vol. A. MIT Press, 1998.