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

Введение.

Глава 1. Структура размещения данных по первичным ключам.

1.1. Структура организации Вр-дерева.

1.2. Алгоритмы работы Вр-дерева.

1.2.1. Поиск элемента;.24"

1.2.2. Вставка элемента.

1.2.3. Удаление элемента.

1.3. Анализ экономичности предложенной структуры размещения справочников на физических носителях.

1.4. Алгоритм поиска данных в узлах Вр-дерева.

1.5. Анализ быстродействия предложенной структуры размещения справочников на физических носителях.

1.5.1. Линейный поиск.

1.5.2. Бинарный поиск.

1.5.3. Интерполяционный поиск.

1.5.4. Граничный интерполяционный поиск.

1.6. Выводы по первой главе.

Глава 2. Структура размещения данных по вторичным ключам.

2.1. Описание структуры.

2.2. Алгоритмы работы.

2.2.1. Поиск элемента.

2.2.2. Вставка элемента.

2.2.3. Удаление элемента.

2.3. Анализ эксплуатационных характеристик предлагаемой структуры организации многомерных данных.

2.4. Выводы по второй главе.

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

3.1. Предварительные замечания.

3.2. Построение справочников на основе Вр-деревьев.

3.3. Структура программного обеспечения.

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

3.5. Построение хранилища разреженных многомерных данных на основе d-k-d-деревьев.

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

Актуальность темы. В настоящее время не существует таких областей науки, техники и образования, в которых не использовались бы базы данных (БД) [74, 92, 94, 104, 108, 121]. Применение баз данных позволяет осуществлять централизованное хранение информации, оптимизировать доступ к данным и осуществить их компактное хранение [90, 128, 132, 133, 134, 143].

Любая система управления БД (СУБД) состоит из двух достаточно автономных модулей: модуль логического представления данных и модуль физического хранения данных [22, 23, 74, 75, 81, 90, 99].

Модуль логического представления данных обеспечивает диалог пользователях БД, предоставляя графическую среду и высокоуровневый язык манипулирования данными, независимый от используемого аппаратного обеспечения. В его задачи также входит обеспечение многопользовательской работы, управление правами доступа к данным, генерация отчетов и т.д. [77, 80, 81,90, 112].

Модуль физического хранения данных размещает информацию во внутренней и внешней памяти компьютера (в оперативной памяти (ОЗУ), на жестких дисках и иных носителях), манипулируя низкоуровневым, аппаратно-зависимым языком. От данного модуля зависят быстродействие СУБД и экономичность использования аппаратных ресурсов, таких как внутренняя и внешняя память, вычислительная мощность процессора и т.д. [4, 6, 10, 50, 90, 138, 144].

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

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

• коэффициент избыточности, т.е. отношение общего объема используемой памяти к объему, используемому непосредственно хранимыми данными [6, 9, 12,24, 29, 51, 109],

• время поиска, добавления и удаления данных (скорость работы) [6, 9, 14, 55, 65].

Следует отметить, что сравнение коэффициента избыточности принято проводить раздельно для внутренней памяти (ОЗУ) и внешней памяти (жестких дисков, CD-ROM'ob, магнитных лент и т.п.) [2, 5, 9,10, 50, 56]. Также самостоятельно оцениваются время работы с «атомарными» единицами информации и с их большими массивами. Это связано с тем, что существуют структуры, обеспечивающие медленную работу с единичными данными, но большую скорость работы с их пакетами, что может быть актуально для аналитических систем [22, 35, 37, 48, 82, 99].

Как известно, большинство современных аналитических систем ориентированны на операции поиска в массивах статических или слабо меняющихся данных [19, 22, 82, 99, 104, 118, 121]. Для таких систем актуальна высокая скорость поиска больших массивов информации. С другой стороны, для систем реального времени наиболее необходимы высокая скорость добавления информации в потоковом режиме, т.е. небольшими, «атомарными» порциями. Не существует на данный момент модели физического хранения данных, обеспечивающей как высокую скорость обработки потоковых запросов, так и анализа больших массивов данных. Поэтому для каждого класса систем - аналитических либо потоковых - используются различные модели физического хранения данных [19, 22, 28, 72, 137].

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

В настоящее время существующие модели хранения данных на физических носителях делятся на два типа: модели поиска по первичному ключу, они необходимы для добавления «атомарных» данных в режиме реального времени [24, 32, 88, 117, 121, 122], и модели поиска по вторичным ключам, которые предоставляют возможность поиска больших массивов информации [76, 93, 100, 109, 121, 138, 143].

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

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

• связный список,

• хеш,

• В+-дерервья,

• список пропусков.

Связный список представляет собой простейшую структуру, предназначенную для хранения небольших последовательностей редко обновляющихся данных. Время выполнения поиска в связном списке наибольшее среди всех моделей поиска по первичному ключу, а коэффициент избыточности примерно равен коэффициенту избыточности В+-деревьев и меньший, нежели у хеша [88].

Хеш представляет собой эффективную структуру поиска по статичным данным. В сбалансированном состоянии его коэффициент избыточности стремится к 1, время же поиска данных наименьшее среди всех известных структур. Однако, в связи с тем, что подбор хеш-функции зачастую является нетривиальной задачей, данную структуру невозможно использовать для хранения часто обновляющихся данных, тем более при их поступлении в режиме реального времени [13, 27, 32, 47, 88].

В+-деревья являются структурой, ориентированной на хранение часто обновляющихся данных и способна оперировать данными, находящимися как во внутренней, так и во внешней памяти. Время поиска данных в В+-дереве в 100-1000 раз меньше времени поиска в связном списке, однако в 1.2 -1.5 раза больше времени поиска в хеше. Коэффициент избыточности В+-дерева находится в пределах 1.2-1.5. На данный момент именно эта структура наиболее широко используется в СУБД в качестве модели поиска по первичному ключу. Это связано еще и с тем, что для В+-деревьев наибольшее время поиска лишь незначительно отличается от среднего [88, 90, 109, 126, 128, 129].

Список пропусков является вероятностной структурой основанной на связном списке. Он также как и В+-деревья ориентирован на работу с часто обновляющимися данными. Время поиска данных в списке пропусков примерно в 1.5 раза меньше, нежели у В+-деревьев, а коэффициент избыточности чуть выше. Основной отличительной особенностью списка пропусков является его вероятностная природа: отклонения реальных значений времени поиска элемента от среднего гораздо более значительны, нежели у В+-деревьев. В отличие от последних, максимальное время поиска данных в списке пропусков ограничено лишь длиной структуры (что на несколько порядков больше, чем у В+-деревьев). Именно эта причина является основным препятствием использования списка пропусков в системах реального времени [129].

Ниже, в таблице 1, представлены основные характеристики перечисленных моделей поиска по первичному ключу (N - количество хранимых элементов):

Таблица 1

Характеристики основных моделей поиска по первичному ключу

Модель Коэф. избыточности Т 1 поиска ср Т ± поиска max Область применения

Связный список 1 N + 1 2 N Сверхмалые хранилища данных

Хеш 1-3 1 2 Статические данные

В+-деревья 1.2-1.5 Oln(iV) 20\n(N) Системы реального времени

Список пропусков 1.2-1.4 A\n(N)+B (А<0) N Оперативные хранилища вне систем реального времени

Далее рассмотрим основные модели поиска по вторичным ключам:

• многомерные массивы,

• реляционные схемы «звезда» и «снежинка»,

• многомерное хеширование,

• k-d- деревья.

Многомерные массивы (ММ) на данный момент являются одним из наиболее распространенных методов организации поиска по вторичным ключам. Они наиболее широко используются в многомерных БД (МБД). Хотя скорость поиска данных в многомерных массивах высока, однако она находится в зависимости от того, по какой оси многомерного массива ведется поиск. Кроме того, многомерные массивы имеют высокий коэффициент избыточности (3-100), что ограничивает их использование в БД большого объема (более 100-500 Мбайт) [76,83, 111, 122, 142, 143, 147].

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

OLAP-приложениях делает необходимым их рассмотрение. Коэффициенты избыточности для схем «звезда» и «снежинка» отличаются незначительно и превышают многомерные массивы, а скорость поиска данных отличается от последних крайне незначительно. Все это делает невозможным применение данных моделей для поиска по вторичным ключам в больших БД [76, 83, 103, 112, 122, 125, 133, 134].

Многомерное хеширование состоит из множества различных методов организации вторичных ключей в хеш. Они имеют незначительные отличия в способах организации оглавления хеша и в эксплуатационных характеристиках. Наиболее удачной реализацией многомерного хеша является «файл с двойной сеткой». Его коэффициент избыточности составляет около 1.3-2, что много меньше, нежели у многомерного массива. Время поиска данных меньше, нежели в многомерных массивах, к тому же многомерное хеширование в отличие от массивов изначально ориентированно на хранение больших объемов данных и приспособлено для операций с внешними накопителями [27, 47, 53, 56, 64, 129]. k-d - деревья являются модификацией балансированных деревьев (В-деревьев), ориентированными на работу с многомерными данными. Алгоритмы их работы не имеют значительных отличий от работы В-деревьев, поэтому им присущи все их недостатки: существует вероятность такого поступления данных, при котором будет построено вырожденное дерево. Процедура балансировки k-d-дерева не может происходить в режиме реального времени. Коэффициент избыточности k-d-дерева составляет около 1.2-1.5, это наименьшее значений среди всех существующих моделей, k-d-деревья также ориентированны на работу с внешней памятью и скорость поиска данных у них в 1.5-2 раза выше, нежели у многомерного хеша. Однако вставка и удаление элементов могут выполняться в десятки раз дольше, в связи с необходимостью балансировки дерева. Существует модификация k-d-дерева, балансируемая автоматически. Однако коэффициент избыточности данной структуры составляет 2-4 [2, 8, 12, 24, 26, 29, 34, 35, 37, 40, 50, 51, 55, 69].

Ниже, в таблице 2, представлены основные характеристики перечисленных моделей поиска по вторичным ключам (V - количество измерений):

Таблица 2

Характеристики основных моделей поиска по вторичным ключам

Модель Коэф. избыточности Т 1 поиска Т 1 вставки Область применения

Многомерные массивы 3-100 aV aV+e Малые хранилища данных

Реляционное хранения 10-200 bV+c (Ь>а) bV+c+f Малые хранилища данных

Многомерный хеш 1,3-2 dV\n(N) dV\n(N)+ S Большие оперативные хранилища данных k-d-деревья 1,2-1,5 0\n{N) N Оперативные статичные хранилища данных

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

Одним из возможных направлений преодоления указанных выше недостатков известных моделей физического хранения данных является:

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

• разработка новой модификации k-d-деревьев, имеющей низкий коэффициент избыточности и растущей «снизу-вверх», что обеспечивает постоянную поддержку дерева в сбалансированном состоянии.

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

Задачи исследования:

1. Разработать способ уменьшения коэффициента избыточности В+-дерева.

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

3. Разработать алгоритмы балансировки k-d-дерева, не увеличивающий его коэффициент избыточности.

4. Создание программного обеспечения, реализующее разработанные модели хранения данных.

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

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

На защиту выносятся:

1. Структура размещения данных на физических носителях по первичным ключам - Вр-дерево.

2. Алгоритм поиска данных в упорядоченном массиве.

3. Структура размещения данных на физических носителях по вторичным ключам - к-с1-В+-дерево.

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

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

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

3. Разработана структура размещения данных на физических носителях по вторичным ключам - d-k-d-дерево. Предложенная структура в отличие от k-d-дерева автоматически поддерживается в сбалансированном состоянии, занимая при этом небольшую часть внутренней памяти ЭВМ.

Практическая значимость работы:

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

2. Предложенная структура хранения данных по первичным ключам, основанная на использовании Вр-деревьев, позволяет повысить скорость поиска элемента на треть, занимая на 20% меньше памяти, нежели В+-деревья.

3. Предложенная структура хранения разреженных многомерных данных, основанная на использовании d-k-d-деревьев, позволяет уменьшить общий объем памяти, занимаемый данными в 1.5 раза при значительном увеличении скорости их поиска.

4. Экспериментальная проверка эффективности предложенных методик и структур на примере их использования в системе сбора и анализа данных пользовательского трафика ЗАО «Деловая сеть» — крупнейшего сетевого провайдера в Уфе показала высокую эффективность предложенных алгоритмов и структур.

Объем и структура работы

Диссертационная работа состоит из введения, трех глав, заключения, библиографии и 2 приложений. Основная часть содержит 128 страниц и включает в себя 60 рисунков и 21 таблицу. Список литературы содержит 152 наименования. В Приложениях приведены: фрагменты исходных кодов и акт внедрения.

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

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

2. Реализована структура хранения данных по первичным ключам на основе Вр-деревьев, которая показывает на треть более высокую производительность и занимает на 20% меньше памяти, нежели В+-деревья.

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

ЗАКЛЮЧЕНИЕ

В процессе выполнения работы получены следующие результаты:

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

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

3. Разработана новая структура организации разреженных многомерных данных на основе модифицированных k-d-деревьев, основанная в отличие от известных модификаций на динамическом определении координат ветвления в каждом узле. Применение данной структуры позволяет исключить хранение несуществующих элементов, поэтому объем занимаемой ею памяти на жестком диске в 10-100 раз меньше, нежели несжатые многомерные данные. Кроме того, данная структура автоматически балансируется при вставке или удалении элементов при неизменном коэффициенте избыточности.

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

1. Айвазян С.А., Бухштабер В.М., Юнюков И.С., Мешалкин Л.Д. // Прикладная статистика: классификация и снижение размерности. М.: Финансы и статистика. - 1989. - 212 с.

2. Артемьев В. Что такое business intelligence? // Открытые системы. -2003.-№4.-80 с.

3. Архипенков С., Голубев Д., Максименко О. Хранилища данных. От концепции до внедрения // М.: Диалог-МИФИ. 2002. - 126 с.

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

5. Баутов А. ИТ и прогнозирование экономических процессов // Директор ИС. 2002. - №9. - 112 с.

6. Бич Д. К объектным моделям данных // Открытые системы. 1994. -№4.-С. 5-55.

7. Буч Г. Объектно-ориентированный анализ и проектирование с примерами на С++, 2-Е ИЗД. // М.: «Издательство Бином». 1998 г. - 467 с.

8. Вирин В. Храните данные в микрокубе // Computerworld. -2002. № 46. - 76 с.

9. Волков Д. От частного к общему // Открытые системы. 2002. - №2. -84 с.

10. Волков И., Галахов И. Архитектура современной информационно-аналитической системы // Директор ИС. 2002. - № 3. - 128 с.

11. Галатенко В., Гвоздев А. Типы и структуры данных в informix-universal server // СУБД. 1997. - №03. -92 с.

12. Галахов И. Проектирование корпоративной информационно-аналитической системы // Открытые системы. 2003. - № 4. — 88 с.

13. Гвоздев В.Е., Павлов С.В., Ямалов И.У. Информационное обеспечение контроля и управления состоянием природно-технических систем: Учеб. Пособие // УГАТУ Уфа, 2002. - 138 с.

14. Гик Дж. Прикладная общая теория систем // М.: Мир. 1981. 212 с.

15. Глинников М. ИТ-рецепты ICN // Директор ИС. 2002. - № И.100с.

16. Глоссарий по хранилищам данных, многомерному моделированию и анализу данных // Директор ИС. -2002. № 3. - 108 с.

17. Дмитриев П. «Кворум» продвигает порталы // Сети. -2003. №1.96 с.

18. Дэйт К.Дж. Введение в системы баз данных, 6-е издание // Пер. с англ. К.; М.; СПб.: Издательский дом «Вильяме». - 1999. - 624 с.

19. Дюк В.А. обработка данных на пк в примерах // СПб: Питер. 1997. -248 с.

20. Дюк В.А., Самойленко A. Data mining: учебный курс // СПб: Питер. -2001.-404 с.

21. Зырянов М. Диалектика быстрого роста // Computerworld. 2001. - № 46.- 104 с.

22. Зырянов М. Эволюция продолжается // Computerworld. 2001. - № 35.-88 с.

23. Иванов П. Ситуационная аналитика // Computerworld. 2003. - № 19. -76 с.

24. Ивлев Д.В., Левков А.А., Христодуло О.И. Оценка эффективности индексных структур в многомерных базах данных // Интеллектуальные системы управления и обработки информации: Тез. доклада междунар. науч. техн. конф. Уфа: Уфимск. гос. неф.техн. ун-т, 1999.

25. Ильясов Б.Г., Кабальнов Ю.С., Ивлев Д.В., Левков А.А., Христодуло О.И. Применение многомерных технологий при созданииинформационных систем в образовании // Телематика 2001: Тез. доклада междунар. науч. методич. конф. Санкт-Питербург, 2001.

26. Йодан Э. Структурное программирование и конструирование программ // М.: Мир. 1974. - 415 с.

27. Ким В. Три основных недостатка современных хранилищ данных // Открытые системы №02-2003.

28. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах // Открытые системы. 1997. - № 4. - с. 41-44.

29. Кнут Д. Искусство программирования, том 1 // Основные алгоритмы,3.е изд. М.: "Вильяме". - 2000. - 560 с.

30. Комафорд К. Корпоративная отчетность: серверная архитектура для распределенного доступа к информации // Открытые системы. 1999. - № 2. -96 с.

31. Комплексное решение для создания систем управления предприятием // http://www.osp.ru/news/busines/2002/03/11 01 .htm

32. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации // М.: Нолидж. 2001. -248 с.

33. Коул Б. Появляются продукты для многомерного представления информации из баз данных // Computer World. 1994. - № 47. - 76 с.

34. Кречетов Н. Продукты для интеллектуального анализа данных. // Рынок программных средств. 1997. - № 14. -с. 32-39.

35. Крил П. Oracle расстается с express olap // Computerworld. 2002. - № 21.-76 с.

36. Кузнецов С. Хранилища данных в начале века // Открытые системы. 2002. - № 1.-80 с.

37. Левков А.А., Христодуло О.И. Применение циклических структур для организации эффективного размещения информации на физических носителях в субд // Телекоммуникации и информатизация образования. 2003. -№ 1. - С.43-52.

38. Левшин И. Эксперименты на себе // Computerworld. 2002. - № 34.72 с.

39. Лисянский К. Архитектурные решения и моделирование хранилищ и витрин данных // Директор ИС. 2002. - № 3. - 112 с.

40. Львов М. Построение информационно-аналитической системы // Открытые системы. 2003. - № 4. - 88 с.

41. Майерс Г. Надежность программного обеспечения // М.: Мир. 1980. -360 с.

42. Мартин Дж. Организация баз данных в вычислительных системах // М.: Мир. 1980.-662 с.

43. Масштабируемость систем бизнес-аналитики // http://www.interface.ru/crystal/cms.htm

44. Моран Б. Перспективы data mining // http://www.osp.ru/win2000/sql/editor/200212sel35.htm

45. Нагао М., Катаяма Т., Уэмура С. Структуры и базы данных // М.: Мир. 1986.- 198 с.

46. Николаи Дж. IBM объединяет olap и добычу данных // Computerworld. 2001. - № 46. - 72 с.

47. Оганесян А. Модели и инструменты интеграции // Открытые системы. 2000. - № 11. - 80 с .

48. Оузьер Д. Разработка приложений баз данных в среде delphi 5 // Бином. 1997. 524 с.

49. Педерсен Т.Б., Йенсен К. Технология многомерных баз данных // Открытые системы. 2002. - № 1. - 88 с.

50. Позин Б., ИТ будущего: потребности и возможности (1-я часть) // Директор ИС. 2002. - № 2. - 112 с.

51. Рамодин Д. D3 server 7.0 постреляционная современная система управления базами данных // Мир ПК. - 1997. - № 3. - 100 с.

52. Редько В.Н., Басараб И.А. Базы данных и информационные системы // Математика и кибернетика. 1987. - № 6. - 31 с.

53. Ривкин М. Новые возможности oracle 9.2 // Открытые системы. — 2002. -№ 11.-96 с.

54. Рузайкин Г.И. Кладезь знаний по бд // Мир ПК. 2003. - № 4. - 96 с.

55. Салливан Т. OLAP наоборот // Computerworld. 2002. - № 27. - 60 с.

56. Салливан Т. Данных больше, доступ - лучше // Computerworld. -2001. -№38. -96 с.

57. Салливан Т. Это надо рисовать: программное обеспечение анализа данных становится более выразительным // Computerworld. 2000. - № 42. — 80 с.

58. Сахаров А.А. Концепции построения и реализации информационных систем, ориентированных на анализ данных // СУБД. 1996. - № 4. - 56 с.

59. Сахаров А.А. Принципы проектирования и использования многомерных баз данных (на примере oracle express server) // СУБД. 1996. - № 3.-60 с.

60. Современные аналитические технологии для студентов МЭСИ // http://www.osp.ni/news/events/2002/06/l 3 02.htm

61. Спирли Э. Корпоративные хранилища данных. Планирование, разработка, реализация. Том.1: Пер. с англ. // М.: Вильяме. 2001. - 616 с.

62. Стулов А. Особенности построения информационных хранилищ // Открытые системы. 2003. - № 4. - 84 с.

63. Уитни Р. Итеративный алгоритм для массивов данных // http://www.osp.ru/win2000/sql/olap/14olap09.htm

64. Уитни Р. Оптимизация службы analysis services в sql server 2000 // http://www.osp.ru/win2000/sql/olap/200305so228.htm

65. Федоров С. Стратегическое планирование сетей масштаба предприятия // www.citforum.ru/database/articles/art 15.shtml

66. Фокс Д. OLAP для разработчиков // http://www.osp.ru/win2000/sql/olap/57olap04.htm

67. Фонсека Б. Cognos фокус на OLAP // Computerworld. - 2003. - № 8. -64 с.

68. Цикритзис Д., Лоховски Ф. Модели данных // М.: Финансы и статистика. 1985. - 344 с.

69. Цуприков С. Методология sybase для создания хранилищ и витрин данных // http://www.interface.ru/sybase/msy.htm

70. Чаудхури С., Дайал У., Ганти В. Технология баз данных в системах поддержки принятия решений // Открытые системы. 2002. - № 1. - 80 с.

71. Шуленин А. Масштабируемость аналитических систем // Windows & .NET Magazine/RE. 2002. - №1-2. - 128 с.

72. Эдельштейн X. Битовые массивы ускоряют обработку запросов к информационным хранилищам // Computerweek. 1996. - № 28. - 36 с.

73. Янг Дж., Танг Ч., Сони С., Куртц В. Измерение быстродействия работы алгоритмов// http://www.osp.ru/win2000/sql/olap/25olap08.htm

74. Abel, D. J. and Mark, D. M. A comparative analysis of some two-dimensional orderings // Geographical Information Systems. -1990. № 4. - C.21-31.

75. Abel, D. J. and Smith, J. L. A data structure and algorithm based on a linear key for a rectangle retrieval problem // Computer Vision. 1983.- № 24.- C.l-13.

76. Ang, C. and Tan, T. New linear node splitting algorithm for R-trees // Springer-Verlag. 1992. - 212 c.

77. Atkinson M., Bansilhon F., DeWitt D., Dittrich K., Maier D., Zdonik S. The Object-Oriented Database System Manifesto // 1st Int. Conf. Deductive and Object-Oriented Databases: Kyoto, Japan. 1989. - C.4-6

78. Bayer, R. 1996. The Universal B-tree for multidimensional indexing // Technical Report 19639, Technische Universitat Mrnchen, Munich, Germany: http://www.leo.org/pub/comp/doc/techreports/tum/informatik/report/1996/TUM-I9639.ps.gz.

79. Bayer, R. and McCreight, E. M. Organization and maintenance of large orderedindices // Acta Informatica. 1972.- № 3. - C.173-189.

80. Becker, L. and Guting, R. H. Rule-based optimization and query processing in an xtensible geometric database system // ACM Trans. Database Systems. 1992. - № 17. - C.247-303

81. Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B. The R-tree: An ancient and robust access method for points and rectangles // In Proc.: ACM SIGMOD Int.Conf. on Management of Data. 1990. C.322-331.

82. Bentley, J. L. 1979. Multidimensionalbinary search in database applications // IEEE Trans.Software: Eng. 1979. - № 5.- C.333-340.

83. Bentley, J. L. and Friedman, J. H. 1979. Data structures for range searching I I ACM Сотр. 1979. - № 11. -C.397-409.

84. Bentley, J. L. Multidimensional binary search trees used for associative searching // Comm. ACM. 1975.- № 9. - C.509-517.

85. Berchtold, S., Keim, D., and Kriegel, H.-P. The X-tree: An index structure for high-dimensional data // In Proc.: 22nd Int. Conf. on Very Large Data Bases. 1996.- C.102-106.

86. Boulding K.E. General Systems Theory The Skeleton of Science // Management Science. - 1956. -№ 2. - C.13-23.

87. Brinkhoff, T. and Kriegel, H.-P. The impact of global clustering on spatial database systems // In Proc.: 20th Int. Conf. on Very Large Data Bases. 1994. - C.168-179.

88. Buchmann, O. Genther, T. R. Smith, and Y.-F. Wang Eds., Design and Implementation of Large patial Databases // LNCS 409: Berlin, Heidelberg, New York. 1990.-332 c.

89. Burkhard, W. A. Interpolation-based index maintainance 7/ BIT 23.-C.274-294.

90. Chaudhuri S., Dayal U., An Overview of Data Warehousing and OLAP Technology // SIGMOD Record: Vol.26. -1996. № 1. - C.213-215.

91. Codd E.F. A Relational Model of Data for Large Shared Data Banks // CACM. 1970. №6.201 c.

92. Codd E.F. Relational Completeness of Data Base Sublanguages // Data Base Systems: Courant Computer Science Symposia Series 6. 1972.422 c.

93. Codd E.F., Codd S.B., Salley C.T., Providing OLAP (On-Line Analytical Processing) to User-Analysts // An IT Mandate: E.F.Codd & Associates.- 1993. 175 c.

94. Cornelio A., Shamkant B. Navathe, Keith L. Doty. Extending Object-Oriented Concepts to Support Engineering Applications // 6th Int. Conf. Data Eng.: Los Angeles, Calif., USA. -1990. № 2.- C.5-9.

95. Dandamudi, S. P. and Sorenson, P. G. Improved partial-match search algorithms for BD-trees // The Computer Journal. 1991. -№ 5. - C.415-422.

96. Demarest M. Building The Data Mart // DBMS. 1994. -№ 6. C.34-46.

97. Evangelidis, G., Lomet, D., and Salzberg, B. 1995. The hB-tree: A modified hB-tree supporting concurrency, recovery and node consolidation // In Proc.: 21st Int. Conf. on Very Large Data Bases. 1995. - C.551-561.

98. Faloutsos, C. and Gaede, V. Analysis of n-dimensional quadtrees using the Hausdor fractal dimension // In Proc.: 22nd Int. Conf. on Very Large Data Bases. -1996.-311 c.

99. Faloutsos, C. and Kamel, I. Beyond uniformity and independence: Analysis of R-trees using the concept of fractal dimension // In Proc.: 13th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. 1994.- C.4-13.

100. Flajolet, P. On the performance evaluation of extendible hashing and trie searching // Acta Informatica. 1996. - № 20. - C.345-369.

101. Freeston, M. A general solution of the n-dimensional B-tree problem // In Proc.: ACMSIGMOD Int. Conf. on Management of Data.- 1995. C.80-91.

102. Freeston, M. On the complexity of BV-tree updates // In Proc.: Workshop on Constraint Databases and their Application. -1997. C.282-293.

103. Goldstein J., Ramakrishnan R., Shaft U. Compressing relations and indexes // In Proc.: IEEE Conf. on Data Engineering, Orlando, FL, USA. 1998. -C.370-379.

104. Goyal K., Ramamritham K., Datta A., Thomas H. Indexing and Compression in Data Warehouses // Technical Report: Indian Institute of Technology, Bombay. 1999.-98 c.

105. Hellerstein, J. M., Koutsoupias, E., and Papadimitriou, С. H. Towards a theory of indexability // In Proc.: 16th ACM SIGACT-SIGMOD-SIGART Database Systems. 1997. 189 c.

106. Hellerstein, J. M., Naughton, J. F., and Pfeffer, A. Generalized search trees for database systems // In Proc.: 21th Int. Conf. on Very Large Data Bases. -1995. C.562-573.

107. Henrich, A. Adapting the TransformationTechnique to Maintain MultiDimensional Non-Point Objects in k-d-Tree Based Access Structures // In Proc.: 3rd ACM Workshop on Advances in Geographic Information Systems. 1995. -312 c.

108. Henrich, A., Six, H.-W., and Widmayer, P. The LSD tree: Spatial access to multidimensional point and non-point objects // In Proc.: 15th Int. Conf. on Very Large Data Bases. 1989. - C.45-53.

109. Hoel, E. G. and Samet, H. Benchmarking spatial join operations with spatial output // In Proc.: 21st Int. Conf. on Very Large Data Bases. 1995. - C.606-618.

110. J. T. Robinson, The K-D-B Tree: A Search Structure for Large Multidimensional Dynamic Indexes // Proc.: ACM SIGMOD. 1984. - C.10-18.

111. Jagadish, H. V. Linear clustering of objects with multiple attributes // In Proc.: ACMSIGMOD Int. Conf. on Management of Data. 1990. - C.332-342.

112. Johnson T, Performance Measurements of Compressed Bitmap Indices // Proceedings: 25th International Conference on Very Large Data Bases. 1999. № 8. — C.278-289.

113. Kamel, I. and Faloutsos, C. Hilbert R-tree: An improved R-tree using fractals // In Proc.: 20th Int. Conf. on Very Large Data Bases. 1994. - C.500-509.

114. Kedem, G. The quad-CIF tree: a data structure for hierachical on-line algorithms // In Proc.: 19th Conf. on Design and Automation. 1982. - C.352-357.

115. Kolovson, C. and Stonebraker, M. Segment indexes: Dynamic indexing techniques for multi-dimensional interval data // In Proc.: ACM SIGMOD Int. Conf. on Management of Data. 1991. - C. 138-147.

116. Kumar, A. G-tree: A new data structure for organizing multidimensional data // IEEE Trans. Knowledge and Data Eng. 1994. - № 6. - C.341-347.

117. Lo, M. L. and Ravishankar, С. V. Spatial joins using seeded trees // In Proc.: ACMSIGMOD Int. Conf. on Management of Data. 1994.- C.209-220.

118. Ohsawa, Y. and Sakauchi, M. BD-tree: A new N-dimensional data structure with efcient dynamic characteristics // In Proc.: 9th World Computer Congress, IFIP. 1983. - C.539-544.

119. Orenstein, J. Multidimensional tries used for associative searching // Information Processing Letters. 1982. - C.150-157.

120. Otoo, E. J. A mapping function for the directory of a multidimensional extendible hashing // In Proc.: 10th Int. Conf. on Very Large Data Bases. 1984. -C.493-506.

121. Overmars, M. H., Smid, M., Berg, Т., and van Kreveld, M. J. Maintaining range trees in secondary memory // Part I: Partitions. Acta Informatica. 1990.- № 27. - C.423-452.

122. Pendse N. OLAP Architectures // The OLAP Report: http://www.olapreport.eom/Architectures.htm#top

123. Robinson, J. T. The K-D-B-tree: A search structure for large multidimensional dynamic indexes // In Proc.: ACM SIGMOD Int. Conf. on Management of Data. -1981. С. 10-18.

124. Schneider, R. and Kriegel, H.-P. The TR-tree: A new representation of polygonal objects supporting spatial queries and operations // In Proc.: 7th Workshop on Computational Geometry. 1992. - C.249-264.

125. Seeger, B. and Kriegel, H.-P. Techniques for design and implementation of spatial access methods // In Proc.: 14th Int. Conf. on Very Large Data Bases. -1988. C.360-371.

126. Seeger, B. and Kriegel, H.-P. The buddy-tree: An ecient and robust access method for spatial data base systems // In Proc.: 16th Int. Conf. on Very Large Data Bases. 1990.-C.590-601.

127. Seeger, В. Performance comparison of segment access methods implemented on top f the buddy-tree // In Advances in Spatial Databases. 1991. — C.277-296.

128. Sellis, Т., Roussopoulos, N., and Faloutsos, C. The R+-tree: A dynamic index or multi-dimensional objects 7/ In Proc.: 13th Int. Conf. on Very Large Data Bases.- 1987. -C.507-518.

129. Sevcik, K. and Koudas, N. Filter trees for managing spatial data over a range of size granularties // In Proc.: 22th Int. Conf. on Very Large Data Bases. -1996.-C. 16-27.

130. Shekhar, S. and Liu, D.-R. CCAM: A connectivity-clustered access method for aggregate queries on transportation networks: A summary of results // In Proc.: 11th IEEE Int. Conf. on Data Eng. 1995. - C.410-419.

131. Six, H. W. and Widmayer, P. Spatial searching in geometric databases // In Proc.: 4th IEEE Int. Conf. on Data Eng. 1988. - C. 496-503.

132. Smith, T. R. and Gao, P. Experimental performance evaluations on spatial access methods // In Proc.: 4th Int. Symp. on Spatial Data Handling. 1990. - 692 c.

133. Stanley Y. W. Su. Extensions to the Object-Oriented Paradigm // COMPSAC'89: 13th Annu. Int. Comput. Software and Appl. Conf. 1989. - 131 c.

134. Stuckey, P. Constraint search trees // In Proc.: Int. Conf. on Logic Programming. 1997. - 100 c.

135. Subramanian, S. and Ramaswamy, S. The P-range tree: A new data structure for range searching in secondary memory // In Proc.: ACM-SIAM Symp. on Discrete Algorithms. 1995.-C. 120-187.

136. T.B. Pedersen, C.S. Jensen, C.E. Dyreson A Foundation for Capturing and Querying Complex Multidimensional Data // Information Systems. 2001. - №5. - C.42-47.

137. Tropf, H. and Herzog, H. Multidimensional range search in dynamically balanced r-trees // Angewandte Informatik. 1998. - № 2. - C.71-77.

138. V. Gaede and О. Geunther Smid, M. and Overmars, M. H. Maintaining range trees in secondary memory // Part II: Lower bounds. Acta Informatica. 1990. -№ 27. - C.453-480.

139. Vassiliadis P., Sellis Т.К. A Survey of Logical Models for OLAP Databases // ACM SIGMOD Record, vol. 28. 1999. - № 4. - 117 c.

140. White, M. N-trees: Large ordered indexes for multi-dimensional space // Technical report: Application Mathematics Research, Statistical Research Division, US Bureau of the Census. 2002. - 134 c.

141. Wu K., Otoo E., Shoshani A. Compressing Bitmap Indexes for Faster Search Operations // In Proc.: SSDBM. 2002. - 484 c.