Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Пространственные базы данных

Содержание

Пространственные базы данных Основные характеристики:Представление пространственных объектов в геометрическом пространстве (обычно двух- или трехмерном)Форма (фигура) и расположение – неотъемлемые компонентыЧаще всего у координат численные значения (с определенной дискретностью и нижней и верхней границами)Области применения: геоинформационные системы (ГИСы),
Пространственные базы данных Основные характеристики:Представление пространственных объектов в геометрическом пространстве (обычно двух- Моделирование пространства1) Объектные (object-based) модели пространства  Компоненты пространственных объектов:Идентификационная информацияОписаниеПространственная протяженность Моделирование пространства б) Одномерные объекты = линейные объектыНапример, дороги на картахОсновной геометрический Моделирование пространства2) Полевые (field-based) модели пространстваПространственная информация задается непрерывным1 полем значений, т.е. Моделирование пространстваПример: Способы представления пространственных объектов 1) Мозаичное (tessellation) представлениеРазбиение на ячейки(соты) (возможны разные Способы представления пространственных объектов 2) Векторное представлениеЕстественно для объектных моделей пространстваБазисные элементы Способы представления пространственных объектов 3) Полуплоскостное (half-plane) представлениеЕдинственный используемый примитив: полуплоскость (см.математическое Вычислительная геометрияАлгоритмическая техника для выполнения операций в пространственных базах данных1) Инкрементные алгоритмыРешить Вычислительная геометрияИллюстрация к инкрементному нахождению выпуклой оболочки:(1)(2)(3)(4)(5) Вычислительная геометрия2) Стратегия «разделяй и властвуй»«Разделяй»: задача рекурсивно разбивается на несколько легко Вычислительная геометрияПересечение полуплоскостей с помощью метода «разделяй и властвуй»: Вычислительная геометрия3) Метод заметающей прямой (sweep-line)Разложение пространства на вертикальные полосы, таким образом, Вычислительная геометрияАлгоритм нахождения пересекающихся прямоугольников:beginОтсортировать 2n нижние и верхние x-координаты прямоугольников и Вычислительная геометрияМетод заметающей прямой для нахождения пересекающихся прямоугольников: Вычислительная геометрияТипичные задачи вычислительной геометрии:Расположение точки относительно полигона (внутри или вне)Пересечение отрезков Хранение и извлечение пространственных объектовОбщие замечания:Работа с произвольными фигурами затруднительна  Хранение и извлечение пространственных объектовМинимальные ограничивающие прямоугольники : Хранение и извлечение пространственных объектовВиды запросов к пространственным объектам:Запросы по точному совпадению: Хранение и извлечение пространственных объектовПредставление пространственных объектов на основе трансформации координатk-мерный прямоугольник Хранение и извлечение пространственных объектовПример представления (для одномерного пр-ва):Замечания:В случае применения методов Хранение и извлечение пространственных объектовОтветы на запросы:Простые геометрические вычисления укажут на области, Хранение и извлечение пространственных объектовПредставление пространственных объектов на основе отсеченияПространство разбивается на Хранение и извлечение пространственных объектовДостоинства:Отсечение может осуществляться практически напрямую с помощью любого Хранение и извлечение пространственных объектовПредставление пространственных объектов на основе перекрывающихся областейКаждый прямоугольник Хранение и извлечение пространственных объектовПотенциальные недостатки:Высокая степень перекрытия ухудшает производительностьСтепень перекрытия MBR’ов R-деревьяИндекс на основе перекрывающихся областей - R-дерево [4] (rectangle tree):Сбалансированная динамическая внешняя R-деревьяПример R-дерева:R10R1R2R3R4R5R6R7R8R9R11R12R13R14R15R16 R-деревьяОбработка запросов:Запрос по точке: найти объекты, содержащие заданную точкуНачиная с корня, рекурсивно R-деревьяВставка в R-дерево:Используя процедуру ChooseLeaf (см.след.слайд), найти лист L для вставляемого прямоугольника R-деревьяПроцедура ChooseLeaf:Начать с корневого узла (= N)Если N является листом, вернуть NПросмотреть R-деревьяРасщепление:Наиболее сложная задача (экспоненциальное число альтернатив)Происходит в листе, но может распространиться наверхЗадача: R-деревья  Этапы, требующие нелинейного времени, в процедуре выше:Выбор «ядер» (первых элементов R-деревьяКорректировка дерева:Параметры: лист L и возможно LL, если L был расщепленРасширение границ R-деревьяУдаление (прямоугольника R) из R-дерева:Найти лист L, содержащий R, путем просмотра всех R-деревьяR*-дерево [5]: улучшенная версия R-дереваОткладывает расщепление путем принудительной вставки:Сортировка всех прямоугольников на R-деревьяX-дерево [6]:Может хранить точечные и пространственные данныеПревосходит R*-деревья, TV-деревья, и ряд других Пространственные соединенияТипичная операция при обработке пространственных запросовЗадача: для двух множеств пространственных объектов Пространственные соединенияПримерный сценарий:Оба множества объектов описываются индексом на основе R-дереваУсловие соединения – Применение: географические базы данныхОсновные понятия  Географический объект:Две компоненты:Описательная часть с численно-текстовыми Применение: географические базы данныхГеоинформатические операции  Проекция темы на подмножество описательных атрибутов:Соответствует Применение: географические базы данных Объединение тем:Соответствует реляционному объединениюОбъединяет две темы, имеющие одинаковые Применение: географические базы данныхГеопространственные СУБД1) Специализированные геоинформационные СУБД  ArcInfo:Задумана как набор Применение: географические базы данныхPostgreSQL:Объектно-реляционная СУБДСвободно распространяемая, открытый кодРасширенные возможности:Геометрические типы: точка, линия, УпражненияРассмотрим простой (см.слайды «Вычислительная геометрия» для определения простого полигона) полигон в двухмерном Ссылки на литературу[1] P. Rigaux, M. Scholl, A. Voisard. Spatial Databases, with
Слайды презентации

Слайд 2 Пространственные базы данных
Основные характеристики:
Представление пространственных объектов в

Пространственные базы данных Основные характеристики:Представление пространственных объектов в геометрическом пространстве (обычно

геометрическом пространстве (обычно двух- или трехмерном)
Форма (фигура) и расположение

– неотъемлемые компоненты
Чаще всего у координат численные значения (с определенной дискретностью и нижней и верхней границами)
Области применения: геоинформационные системы (ГИСы), системы автоматизированного проектирования (САПРы), графический интерфейс пользователя (GUI), виртуальная реальность, компьютерные игры, анимация и т.д.

Слайд 3 Моделирование пространства
1) Объектные (object-based) модели пространства
Компоненты

Моделирование пространства1) Объектные (object-based) модели пространства Компоненты пространственных объектов:Идентификационная информацияОписаниеПространственная протяженность

пространственных объектов:
Идентификационная информация
Описание
Пространственная протяженность

Классификация объектов на основе

размерности:
Примечание: зависит от приложения, работающего с объектом
а) Объекты нулевой размерности = точки
Формы нет или знание формы объекта не требуется
Площадь объекта очень мала в сравнении со всем рассматриваемым пространством (например, города на картах, здания на картах, пересечения дорог, и т.д.)
Могут появляться в зависимости от масштаба карта (город – точка на мелкомасштабной карте и двухмерный объект на крупномасштабной карте)

Слайд 4 Моделирование пространства
б) Одномерные объекты = линейные объекты
Например,

Моделирование пространства б) Одномерные объекты = линейные объектыНапример, дороги на картахОсновной

дороги на картах
Основной геометрический объект – ломаная линия. Состоит

из конечного множества отрезков (или сегментов или ребер), таких что любая (за исключением двух точек – начала и конца ломаной линии) из конечных точех этих отрезков принадлежит двум отрезкам
Простая ломаная линия – нет пересечений
Замкнутая ломаная линия – точки начала и конца ломаной линии совпадают
Любая кривая может быть представлена с заданной точностью ломаной линией
в) Двухмерные объекты = объекты на плоскости
Сущности-объекты имеют не нулевую площадь
Основной геометрический объект – полигон (многоугольник). Полигон – область, задаваемая замкнутой ломаной линией
Выпуклый полигон P: для любых A,B  P, отрезок AB целиком в P
г) Трехмерные объекты = объемные объекты
(полиэдры=многогранники)

Слайд 5 Моделирование пространства
2) Полевые (field-based) модели пространства
Пространственная информация задается

Моделирование пространства2) Полевые (field-based) модели пространстваПространственная информация задается непрерывным1 полем значений,

непрерывным1 полем значений, т.е. с помощью некой функции (например,

по координатам x и y)
Для каждой точки пространства может использоваться несколько атрибутов
Примеры:
Температурное поле (температура в разных точках)
Атмосферное давление в разных точках
Высота над уровнем моря (на физических картах)
Значения уровня серого цвета на полутоновых цифровых изображениях
Значения красного, синего, зеленого компонентов на цветных (24-битных) изображениях

---------
1 – не в математическом смысле

Слайд 6 Моделирование пространства
Пример:

Моделирование пространстваПример:

Слайд 7 Способы представления пространственных объектов
1) Мозаичное (tessellation) представление
Разбиение

Способы представления пространственных объектов 1) Мозаичное (tessellation) представлениеРазбиение на ячейки(соты) (возможны

на ячейки(соты) (возможны разные формы ячеек)
Фиксированные ячейки: одинаковые ячейки

(сетка прямоугольных координат)
Произвольные ячейки: размеры и формы ячеек различаются между собой
Мозаика с регулярной/нерегулярной структурой
По умолчанию: N x M прямоугольных (обычно квадратных) ячеек, которые называются пикселами
Естественное (дискретное) представление полевых данных
В случае объектных данных: один пиксел для точки, набор (множество) пикселов для ломаной линии или полигона
Более точное представление (с более мелкими ячейками) потребует больше места для хранения; обработка займет больше времени

Слайд 8 Способы представления пространственных объектов
2) Векторное представление
Естественно для

Способы представления пространственных объектов 2) Векторное представлениеЕстественно для объектных моделей пространстваБазисные

объектных моделей пространства
Базисные элементы (примитивы): точки и ребра
Полигон задается

множеством точек, аналогично ломаная линия
2*n возможных описания полигона с n вершинами (выбор стартовой вершины, обход по/против часовой стрелки)
Область – множество полигонов
Представление может дополняться ограничениями (например, только простые1 полигоны)
Векторное представление полевых данных; цифровые модели местности (digital elevation models):
Значения задаются только для подмножества точек
Значения в остальных точках интерполируются
Пример: триангулированные неравномерные сети (triangulated irregular networks)
------------------
1 – граница которого не пересекается сама с собой

Слайд 9 Способы представления пространственных объектов
3) Полуплоскостное (half-plane) представление
Единственный

Способы представления пространственных объектов 3) Полуплоскостное (half-plane) представлениеЕдинственный используемый примитив: полуплоскость

используемый примитив: полуплоскость (см.математическое определение)
Солидный математический базис
Полуплоскость в d-мерном

пространстве задается неравенством: a1x1 + a2x2 + ... + adxd + ad+1  0
Выпуклый полигон – пересечение конечного числа полуплоскостей
Полигон – объединение конечного числа выпуклых полигонов
Отрезок (ребро) линии – одномерный выпуклый полигон (пересечение двух лучей или полупрямых)
Ломаная линия – объединение нескольких отрезков

Слайд 10 Вычислительная геометрия
Алгоритмическая техника для выполнения операций в пространственных

Вычислительная геометрияАлгоритмическая техника для выполнения операций в пространственных базах данных1) Инкрементные

базах данных
1) Инкрементные алгоритмы
Решить задачу для небольшого подмножества входных

данных (точек), затем решить задачу для начального множества плюс одна точка из остающихся и т.д. пока все точки не будут рассмотрены
Пример: нахождение выпуклой оболочки для множества точек
Простейший метод с временной сложностью O(n2):
Построить выпуклую оболочку H3 – для первых трех точек
Для каждой из остальных точек { pi }, i>3:
Если pi внутри Hi-1, то Hi = Hi-1 (проверка «внутри»:
при обходе Hi-1 по часовой стрелке, pi остается справа)
Иначе, добавить pi к Hi-1, возможно удалив старые точки (для pi найти соседние такие точки pa, pb, чтобы угол между отрезками (pa , pi) и (pb , pi) был наибольшим)
Оптимальный алгоритм: O(n log n), используется предварительная сортировка точек

Слайд 11 Вычислительная геометрия
Иллюстрация к инкрементному нахождению выпуклой оболочки:
(1)
(2)
(3)
(4)
(5)

Вычислительная геометрияИллюстрация к инкрементному нахождению выпуклой оболочки:(1)(2)(3)(4)(5)

Слайд 12 Вычислительная геометрия
2) Стратегия «разделяй и властвуй»
«Разделяй»: задача рекурсивно

Вычислительная геометрия2) Стратегия «разделяй и властвуй»«Разделяй»: задача рекурсивно разбивается на несколько

разбивается на несколько легко решаемых подзадач
«Властвуй»: объединение снизу-вверх всех

решений в одно общее решение
Аналогия: бинарное дерево (см.следующий слайд)
Пример: пересечение полуплоскостей
Для простоты считаем, что конечный результат – выпуклый полигон внутри прямоугольника R
Исходное множество из n полуплоскостей рекурсивно разбивается пополам до тех пор пока мы не получим n отдельных полуплоскостей (это дает нам бинарное дерево)
Для каждой из полуплоскостей определяем ее пересечение с R (каждое такое пересечение - выпуклый полигон)
Объединение результатов: рекурсивно снизу-вверх определяем попарные пересечения полигонов
Сложность: O(n log n), т.к. сложность нахождения пересечения выпуклых полигонов - O(n)

Слайд 13 Вычислительная геометрия
Пересечение полуплоскостей с помощью
метода «разделяй и

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

властвуй»:


Слайд 14 Вычислительная геометрия
3) Метод заметающей прямой (sweep-line)
Разложение пространства на

Вычислительная геометрия3) Метод заметающей прямой (sweep-line)Разложение пространства на вертикальные полосы, таким

вертикальные полосы, таким образом, чтобы линии, разделяющие полосы, давали

нужную информацию для решения проблемы
Процесс «заметания» заключается в перемещении вертикальной прямой слева направо, с остановками на границах вертикальных полос и сохранения/обновления информации необходимой для решения
Используются две структуры данных:
Статус заметающей прямой: содержит объекты, связанные с текущей позицией прямой
Перечень событий: содержит границы полос, известные заранее или определяемые динамически
Пример: найти все попарные пересечения множества прямоугольников, стороны которых параллельны координатным осям
Время работы в наихудшем случае O(n2)
Метод на основе заметающей прямой со сложностью прямо пропорциональной количеству находимых объектов (методы с такой сложностью называются output-sensitive methods)

Слайд 15 Вычислительная геометрия
Алгоритм нахождения пересекающихся прямоугольников:

begin
Отсортировать 2n нижние и

Вычислительная геометрияАлгоритм нахождения пересекающихся прямоугольников:beginОтсортировать 2n нижние и верхние x-координаты прямоугольников

верхние x-координаты
прямоугольников и поместить результат в E
Пусть L=
while

(E  ) do
begin
p = Min(E)
Извлечь (удалить) p из E
if p - нижняя граница прямоугольника r then begin Найти (и выдать как результат) все прямоугольники из L,
которые пересекаются с r
Вставить r в L
endif
if p - верхняя граница прямоугольника r then
Удалить r из L
endwhile
end

Слайд 16 Вычислительная геометрия
Метод заметающей прямой для нахождения
пересекающихся прямоугольников:

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

Слайд 17 Вычислительная геометрия
Типичные задачи вычислительной геометрии:
Расположение точки относительно полигона

Вычислительная геометрияТипичные задачи вычислительной геометрии:Расположение точки относительно полигона (внутри или вне)Пересечение

(внутри или вне)
Пересечение отрезков прямых
Пересечение ломаных линий
Пересечение полигонов
Отсечение с

помощью прямоугольника (отсечение объекта(-ов) вне границ прямоугольного окна)
Разбиение полигона на треугольники (триангуляция)
Разбиение полигона на трапеции
Представление полигона в виде нескольких выпуклых полигонов

Ограничение, накладываемые на объекты, упрощают алгоритмы; например, в случае полигонов:
Простой полигон: граница не пересекается сама с собой
Монотонный полигон: граница составлена из двух монотонных цепочек вершин: верхней и нижней цепочек вершин полигона (цепочка вершин монотонна, если любая вертикальная линия пересекает образуемую ломаную линию не более одного раза)
Выпуклый полигон (было дано ранее)

Слайд 18 Хранение и извлечение пространственных объектов
Общие замечания:
Работа с произвольными

Хранение и извлечение пространственных объектовОбщие замечания:Работа с произвольными фигурами затруднительна 

фигурами затруднительна 
Рассматривают минимальные ограничивающие прямоугольники (далее

MBR1): наименьший прямоугольник, охватывающий геометрический объект на плоскости, со сторонами, параллельными координатным осям
Значения координат отображаются на интервал [0, 1); пространство – гиперкуб, обозначаемый Ek

Факторы, влияющие на производительность:
Выбранная структура данных
Размерность пространства
Распределение объектов в пространстве:
Плотность в точке P = число прямоугольников, содержащих P
Глобальная плотность = максимум по локальным плотностям

----------
1 - Minimum bounding rectangle или сокращенно MBR; другое название – ограничивающие блоки (bounding box)

Слайд 19 Хранение и извлечение пространственных объектов
Минимальные ограничивающие прямоугольники :

Хранение и извлечение пространственных объектовМинимальные ограничивающие прямоугольники :

Слайд 20 Хранение и извлечение пространственных объектов
Виды запросов к пространственным

Хранение и извлечение пространственных объектовВиды запросов к пространственным объектам:Запросы по точному

объектам:
Запросы по точному совпадению: не типичны для пространственных объектов,

за исключением операций вставки
Запрос по точке: для заданной точки P  Ek найти все прямоугольники R такие, что P  R
Пересечение прямоугольников: для заданного прямоугольника S  Ek найти все прямоугольники R такие, что S  R  
Поиск «включающих» прямоугольников: для заданного прямоугольника S  Ek найти все прямоугольники R такие, что S  R (R включает в себя S)
Поиск прямоугольников «внутри»: для заданного прямоугольника S  Ek найти все прямоугольники R такие, что R  S (R внутри S)
Запрос по объему: по заданным v1, v2  (0,1), v1  v2 найти все прямоугольники с объемом (площадью) в интервале [v1, v2]
Пространственное соединение: для двух множеств k-мерных прямоугольников найти все пары, удовлетворяющие заданному условию соединения (пересечение, включение, нахождение внутри)

Слайд 21 Хранение и извлечение пространственных объектов
Представление пространственных объектов на

Хранение и извлечение пространственных объектовПредставление пространственных объектов на основе трансформации координатk-мерный

основе трансформации координат
k-мерный прямоугольник можно представить 2k-мерной точкой
Возможные варианты

(на примере двухмерного пр-ва):
(cx, cy, ex, ey), где (cx, cy) – центральная точка, а ex и ey – расстояния от центральной точки до сторон прямоугольника
(lx, ly, ux, uy), где (lx, ly) и (ux, uy) – нижняя вершина слева и верхняя вершина справа соответственно
Достоинство варианта a): координаты расположения cx и cy отличны от координат протяженности ex и ey

Частный случай:
Одномерное пространство [0, 1)
Прямоугольник = отрезок  [0, 1)
Варианты представления:
(c, e) = (центр, половина длины)
(l, u) = (начальная точка, конечная точка)

Слайд 22 Хранение и извлечение пространственных объектов
Пример представления (для одномерного

Хранение и извлечение пространственных объектовПример представления (для одномерного пр-ва):Замечания:В случае применения

пр-ва):








Замечания:
В случае применения методов доступа к точечным данным возникает

проблема «пустых треугольников» (или «мертвых регионов»), см.рисунок выше
Вариант представления с координатами центра и протяженности может быть улучшен, если нам известен верхний предел размера стороны прямоугольника (тогда, например, в одномерном случае можно рассматривать только область [0, limit/2]); в этом случае «живое» пространство будет трапецией, а «мертвые» треугольники сравнительно небольшими

c

l

0

1

L1

L2

L3

L4

0.5

0

1

e





P1

P2

P3

P4

0

1

u


S1


S2


S3


S4

1


Слайд 23 Хранение и извлечение пространственных объектов
Ответы на запросы:
Простые геометрические

Хранение и извлечение пространственных объектовОтветы на запросы:Простые геометрические вычисления укажут на

вычисления укажут на области, соответствующие тому или иному типу

запросов
Пример: одномерные прямоугольники (=отрезки) могут быть представлены точками в двухмерном пространстве (с помощью координат центра и протяженности); для прямоугольника в запросе S = (c, e) имеем:









Недостаток: близко расположенные, но различного объема, прямоугольники могут располагаться довольно далеко друг от друга в двухмерном пространстве

Слайд 24 Хранение и извлечение пространственных объектов
Представление пространственных объектов на

Хранение и извлечение пространственных объектовПредставление пространственных объектов на основе отсеченияПространство разбивается

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

и в большинстве методах доступа к точечным данным, см.тему 8)
Расположение прямоугольника R может быть следующим:
R внутри одной из областей: простая обработка (как и в методах доступа к точечным данным)
R пересекается как минимум с двумя областями
В случае «отсечения»: каждая область пересечения (R с областями на которые разбито пр-во) рассматривается (в том числе хранится) как самостоятельный прямоугольник, но при этом все отсеченные части указывают на один и тот же изначальный объект

Слайд 25 Хранение и извлечение пространственных объектов
Достоинства:
Отсечение может осуществляться практически

Хранение и извлечение пространственных объектовДостоинства:Отсечение может осуществляться практически напрямую с помощью

напрямую с помощью любого метода доступа к точечным данным
Точки

и прямоугольники могут храниться в одном и том же месте
Недостатки:
Повышенные требования к пространству (многочисленные указатели на один и тот же объект)
Дополнительные издержки при операциях вставки и удаления
В случае высокой глобальной плотности необходимы избыточные страницы
Производительность:
Запросы по точному совпадению, по точке и поиск включающих прямоугольников потребуют доступа только к одной странице (при условии, что нет переполнения)
Пересечение прямоугольников и поиск прямоугольников «внутри» может потребовать просмотра всех отсеченных частей прямоугольника запроса; количество false drops может быть большим
Пример реализации:
R+-дерево [3]: сбалансированное внешнее (т.е. данные об объектах хранятся только в листьях) дерево; похоже на R-дерево (см.далее)

Слайд 26 Хранение и извлечение пространственных объектов
Представление пространственных объектов на

Хранение и извлечение пространственных объектовПредставление пространственных объектов на основе перекрывающихся областейКаждый

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

один раз (в отличие от R+-дерева)
Прямоугольники сгруппированы по дисковым страницам
Каждая область (образующая группу прямоугольников) задается минимальным ограничивающим прямоугольником
Области могут перекрываться
Пример:

Слайд 27 Хранение и извлечение пространственных объектов
Потенциальные недостатки:
Высокая степень перекрытия

Хранение и извлечение пространственных объектовПотенциальные недостатки:Высокая степень перекрытия ухудшает производительностьСтепень перекрытия

ухудшает производительность
Степень перекрытия MBR’ов может быть много выше степени

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

Обобщение:
Области (минимальные ограничивающие прямоугольники) могут быть сами сгруппированы, образуя прямоугольники более высокого уровня
Это позволяет построить древовидную структуру

Слайд 28 R-деревья
Индекс на основе перекрывающихся областей - R-дерево [4]

R-деревьяИндекс на основе перекрывающихся областей - R-дерево [4] (rectangle tree):Сбалансированная динамическая

(rectangle tree):
Сбалансированная динамическая внешняя древовидная структура, где узлы –

страницы
Хранит как точки так и прямоугольники
Широко используется; например, в пространственном модуле Oracle
Виды узлов:
Лист содержит пары (R,TID), где R – MBR пространственного объекта, а TID – указывает на точное описание объекта
Внутренний узел содержит пары (R, ptr), где R – MBR прямоугольников в узле-потомке, а ptr – указатель на узел-потомок
Свойства:
Прямоугольники на пути от вершины дерева к листьям вложены друг в друга (т.е. прямоугольник узла-потомка внутри прямоугольника узла-родителя)
Какие-либо ограничения на перекрытие прямоугольников (за исключением только что упомянутого) отсутствуют, но (!) количество перекрытий должно минимизироваться
При емкости страницы в M записей, для количества записей на одной странице определяется нижняя граница - m  M/2
Для N записей, высота (дерева)  logmN1 и количество узлов  N/(m 1)

Слайд 29 R-деревья
Пример R-дерева:
R10
R1
R2
R3
R4
R5
R6
R7
R8
R9
R11
R12
R13
R14
R15
R16

R-деревьяПример R-дерева:R10R1R2R3R4R5R6R7R8R9R11R12R13R14R15R16

Слайд 30 R-деревья
Обработка запросов:
Запрос по точке: найти объекты, содержащие заданную

R-деревьяОбработка запросов:Запрос по точке: найти объекты, содержащие заданную точкуНачиная с корня,

точку
Начиная с корня, рекурсивно просматриваем все поддеревья, MBR’ы которых

содержат данную точку. Дойдя до уровня листьев, получим описания объектов, каждый из которых необходимо проверить на предмет содержания точки
Запрос на пересечение: найти объекты, пересекающиеся с заданным прямоугольником
Обработка такая же как и в a), но проверяется не содержание точки, а пересечение объектов
Выполнение других типов запросов происходит похожим образом

Производительность:
Гарантия отсутствует, т.к. может требоваться просмотр значительного количества узлов дерева
Степень перекрытия MBR’ов, описываемых во внутренних узлах, определяет производительность
Самая важная роль при минимизации степени перекрытия у операции вставки

Слайд 31 R-деревья
Вставка в R-дерево:
Используя процедуру ChooseLeaf (см.след.слайд), найти лист

R-деревьяВставка в R-дерево:Используя процедуру ChooseLeaf (см.след.слайд), найти лист L для вставляемого

L для вставляемого прямоугольника R
Если в L есть место

для R, осуществить вставку; иначе, вызвать процедуру SplitNode, возвращающую листья L и LL, которые совместно содержат R и старые объекты из L
Вызвать процедуру AdjustTree с входными параметрами L и возможно LL. Корректировка (дерева) ведет к увеличению ограничивающих прямоугольников в узлах-родителях, и возможно вызовет расщепление узлов
Если корневой узел был расщеплен на два, то создать новый корневой узел, узлами-потомками которого будут эти два образовавшихся узла

Слайд 32 R-деревья
Процедура ChooseLeaf:
Начать с корневого узла (= N)
Если N

R-деревьяПроцедура ChooseLeaf:Начать с корневого узла (= N)Если N является листом, вернуть

является листом, вернуть N
Просмотреть пары (указывающие на поддеревья) в

узле N. Выбрать ту пару, чей MBR при включении прямоугольника R увеличится наименьшим образом (в идеале, вообще не изменится). Пусть F указатель определенной таким образом пары. В спорных случаях (когда приращение MBR’ов одинаково) – выбирать прямоугольник с наименьшей площадью.
Переопределить N как узел на который указывает F и продолжить с шага 2

Слайд 33 R-деревья
Расщепление:
Наиболее сложная задача (экспоненциальное число альтернатив)
Происходит в листе,

R-деревьяРасщепление:Наиболее сложная задача (экспоненциальное число альтернатив)Происходит в листе, но может распространиться

но может распространиться наверх
Задача: минимизировать степень перекрытия MBR’ов
Эвристическая процедура:

попытаться минимизировать общую площадь двух прямоугольников, образующихся в результате расщепления
Два способа (второй на след.слайде)
SplitNode (квадратичное время):
Найти два прямоугольника R1, R2, которые в случае помещения в один и тот же узел, приведут к наибольшой потере пространства, т.е. для которых Area(MBR(R1, R2){R1, R2}) максимальна. R1 и R2 будут «ядрами» двух формируемых групп прямоугольников
Остановить процедуру, если все прямоугольники распределены по своим группам. Если все остающиеся прямоугольники должны быть отнесены к одной из групп (для того чтобы было выполнено условие минимально допустимого количество записей в данной группе, см.слайд 246), то поместить прямоугольники в эту группу и остановиться
Для каждого из остающихся прямоугольников вычислить d1 = увеличение площади MBR, если прямоугольник отнесен к группе 1, и d2 (если к группе 2). Выбрать прямоугольник с наибольшим значением d1-d2, и вставить его в группу для которой d-значение минимально. Перейти к шагу 2.

Слайд 34 R-деревья
Этапы, требующие нелинейного времени, в процедуре

R-деревья Этапы, требующие нелинейного времени, в процедуре выше:Выбор «ядер» (первых элементов

выше:
Выбор «ядер» (первых элементов в группах)
Выбор следующего прямоугольника (шаг

3)

SplitNode (линейное время):
Выбор первых элементов для групп: для каждого измерения найти два прямоугольника, которые имеют наибольшую нижнюю границу (по этому измерению) и наименьшую верхнюю границу соответственно; определить максимум (по всем измерениям d) следующего выражения:
|Max(нижн.граница R1 по измерению d)  Min(верх.граница R2 по измерению d)|
длина всего рассматриваемого множества прямоугольников по измерению d ;
другими словами, будет выбрана пара прямоугольников с
наибольшим нормализованным расстоянием между нижней и
верхней гранями
Выбор следующего прямоугольника: выбирать любой из остающихся

Квадратичная процедура работает до определенной степени лучше линейной, в некоторых случаях много лучше линейной

Слайд 35 R-деревья
Корректировка дерева:
Параметры: лист L и возможно LL, если

R-деревьяКорректировка дерева:Параметры: лист L и возможно LL, если L был расщепленРасширение

L был расщеплен
Расширение границ прямоугольников, включающих прямоугольники листа L


Расщепление внутренних узлов при необходимости

AdjustTree:
Зададим N = L и, если существует, NN = LL
Если N – корневой узел, то остановиться
Пусть узел P – родитель N и PN – запись в P об узле-потомке N. Скорректировать MBR в PN (MBR прямоугольников из узла N)
Если NN существует, то создать новую запись PNN, указывающую на NN и хранящую MBR прямоугольников из узла NN
Если P вмещает в себя PNN, то вставить PNN в P, иначе:
Вызвать SplitNode, производящую P и PP, совместно содержащие PNN и старые записи узла P
Переопределить N = P и NN = PP, и перейти к шагу 2

Слайд 36 R-деревья
Удаление (прямоугольника R) из R-дерева:
Найти лист L, содержащий

R-деревьяУдаление (прямоугольника R) из R-дерева:Найти лист L, содержащий R, путем просмотра

R, путем просмотра всех поддеревьев, MBR’ы которых пересекаются с

R
Удалить R из L
[подготовка к сжатию дерева] Задать N = L и Q = empty (= множество удаляемых узлов)
Если N – корневой узел, то перейти к шагу 7, иначе: пусть узел P – родитель узла N и PN – запись в P об узле N
[проверка условия минимальной заполнености узла] Если в узле N менее чем m (см.слайд 246) записей, то удалить PN из P and добавить узел N в множество Q, иначе скорректировать MBR в PN
Переопределить N = P и перейти к шагу 4
[передислокация записей из удаленных узлов] Заново вставить в R-дерево все записи из множества Q. Записи из удаленных листов вставляются в листы (с помощью операции стандартной вставки). В тоже время, записи из удаленных внутренних узлов вставляются во внутренние узлы так, чтобы листья, образуемых ими поддеревьях, были на том же уровне, что и листья основного дерева
Если у корневого узла только один узел-потомок, то сделать потомка новым корневым узлом

Слайд 37 R-деревья
R*-дерево [5]: улучшенная версия R-дерева
Откладывает расщепление путем принудительной

R-деревьяR*-дерево [5]: улучшенная версия R-дереваОткладывает расщепление путем принудительной вставки:Сортировка всех прямоугольников

вставки:
Сортировка всех прямоугольников на основе расстояний между их центрами

и центром соответствующих MBR’ов
Определенная часть наиболее удаленных прямоугольников удаляется и затем повторно вставляется
Более сложная эвристическая процедура для расщепления:
См.[5]
Временная сложность O(M*logM) для M прямоугольников
Превосходит R-дерево
Хорошо работает в качестве метода доступа к точечным данным
«Эталонная» структура данных для других структур пространственных данных (пожалуй, наиболее известный метод доступа к пространственным данным)

Слайд 38 R-деревья
X-дерево [6]:
Может хранить точечные и пространственные данные
Превосходит R*-деревья,

R-деревьяX-дерево [6]:Может хранить точечные и пространственные данныеПревосходит R*-деревья, TV-деревья, и ряд

TV-деревья, и ряд других структур, особенно в пространствах большой

размерности
Основное предположение: с ростом размерности пространства последовательный индекс становится все более эффективен, т.к. перекрытия становятся все больше и больше
Решение: внутренние узлы могут быть произвольного размера; суперузел содержит более одной страницы
Многостраничный суперузел с (физически) последовательно расположенными страницами обрабатывается быстрее, чем такое же число отдельных страниц
Для пространств большой размерности большие суперузлы предпочтительны
X-tree настраивается на число измерений
X-tree – «эталонная» структура для других структур данных высокой размерности

Слайд 39 Пространственные соединения
Типичная операция при обработке пространственных запросов
Задача: для

Пространственные соединенияТипичная операция при обработке пространственных запросовЗадача: для двух множеств пространственных

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

предикату, например:
Равенство
Пересечение (перекрытие)
Включение (асимметрично)
Близость
Другие топологические зависимости (слева от, справа от, на севере от, и т.д.)
В силу использования MBR’ов требуются два шага:
Фильтрация: найти пары MBR’ов, удовлетворяющих предикату
Уточнение: для каждой из пар, найденных на шаге 1, осуществить окончательную проверку, учитывая реальную геометрию объектов

Слайд 40 Пространственные соединения
Примерный сценарий:
Оба множества объектов описываются индексом на

Пространственные соединенияПримерный сценарий:Оба множества объектов описываются индексом на основе R-дереваУсловие соединения

основе R-дерева
Условие соединения – пересечение

Стандартный алгоритм:
Основан на обходе

деревьев в глубину
Начать с корневых узлов
На каждом шаге рассматриваются два узла (N1, N2); вычисляются пары пересекающихся записей (e1, e2), где e1N1, e2  N2
Процедура вызывается рекурсивно для поддеревьев, задаваемых e1 и e2
При достижении уровня листов происходит сравнение непосредственно самих объектов
Совершенствование алгоритма:
Проверять только пары (e1, e2), в которых и e1 и e2 пересекаются с (MBRN1  MBRN2)
Метод заметающей прямой: рассматривать два множества прямоугольников (красные и синие), искать пересечения только красных с синими

Слайд 41 Применение: географические базы данных
Основные понятия
Географический объект:
Две

Применение: географические базы данныхОсновные понятия Географический объект:Две компоненты:Описательная часть с численно-текстовыми

компоненты:
Описательная часть с численно-текстовыми атрибутами, например, город – название,

население и т.д.
Пространственная часть (то что мы называем пространственным объектом) описывает геометрию (расположение, форму), например, город: полигон в двухмерном пространстве
Элементарные и сложные (сложно-составные) объекты:
Сложные объекты состоят из других элементарных/сложных объектов
Тема (theme):
Класс (тип) географического объекта
Соответствует отношению в реляционной бд; тема задается схемой и есть экземпляры темы (класса)
Примеры тем: реки, города, страны, дороги и т.д.

Слайд 42 Применение: географические базы данных
Геоинформатические операции
Проекция темы

Применение: географические базы данныхГеоинформатические операции Проекция темы на подмножество описательных атрибутов:Соответствует

на подмножество описательных атрибутов:
Соответствует реляционной проекции
Визуальный результат: часть атрибутов

на карте пропадает
Выборка на основе описательных атрибутов:
Соответствует реляционной выборке
Остаются только те географические объекты, что удовлетворяют условиям выборки
Визуальный результат: часть объектов пропадает
Геометрическая выборка:
Объекты в заданном окне: выбираются объекты (возвращаются целиком), пересекающиеся с заданным прямоугольником
Запрос по точке: выбираются объекты, геометрия которых содержит данную точку
Отсечение по заданному окну: выбираются объекты (возвращаются только(!) пересечения, а не целые объекты), пересекающиеся с заданным прямоугольником

Слайд 43 Применение: географические базы данных
Объединение тем:
Соответствует реляционному объединению
Объединяет

Применение: географические базы данных Объединение тем:Соответствует реляционному объединениюОбъединяет две темы, имеющие

две темы, имеющие одинаковые схемы
Наложение тем:
Рядовая операция

в геоинформационных приложениях
Пространственное соединение: вычислить пересечения
На основе пересечений создаются новые географические объекты:
Описательные атрибуты берутся от обоих пересекающихся объектов
Пространственная компонента определяется геометрией пересечения
Метрические операции:
Например, расстояние между Москвой и Санкт-Петербургом
Топологические операции:
Например, список стран, имеющих общую границу с Россией (Украина, Белоруссия, Литва, Латвия и т.д.)
Список городов до которых можно долететь (без дополнительной посадки) из Санкт-Петербурга

Слайд 44 Применение: географические базы данных
Геопространственные СУБД
1) Специализированные геоинформационные СУБД

Применение: географические базы данныхГеопространственные СУБД1) Специализированные геоинформационные СУБД ArcInfo:Задумана как набор

ArcInfo:
Задумана как набор инструментальных средств разработки
Большой выбор пространственных

функций
Подсистемы: Arc – пространственные данные, Info – описательные данные
Представление пространственных данных: векторное, растровое (сеточное), триангуляционное
2) Расширения реляционных СУБД
Oracle Spatial:
Новый пространственный тип данных
SQL расширен операторами для манипуляций с пространственным типом данных
Пространственное индексирование на основе Z-порядка (см.предыдущую тему)
Оптимизация запросов, например, для пространственных соединений

Слайд 45 Применение: географические базы данных
PostgreSQL:
Объектно-реляционная СУБД
Свободно распространяемая, открытый код
Расширенные

Применение: географические базы данныхPostgreSQL:Объектно-реляционная СУБДСвободно распространяемая, открытый кодРасширенные возможности:Геометрические типы: точка,

возможности:
Геометрические типы: точка, линия, прямоугольник, полигон, окружность и т.д.
Операции

с геометрическими объектами: сдвиг, масштабирование и т.д.
Индекс на основе обобщенного R-дерева
Вставка геометрических объектов в виде строки координат в SQL, например, треугольник – ‘((1,2), (4,5), (3,1))’
В тоже время:
Не поддерживаются топологические операции (например, близости)
Не поддерживается наложение тем
Не поддерживается пересечение полигонов

Слайд 46 Упражнения
Рассмотрим простой (см.слайды «Вычислительная геометрия» для определения простого

УпражненияРассмотрим простой (см.слайды «Вычислительная геометрия» для определения простого полигона) полигон в

полигона) полигон в двухмерном пр-ве, задаваемый списком точек по

часовой стрелке – P = ((x1, y1), (x2, y2), ... (xn, yn)). Предложить правило (основные принципы), определяющее находится ли заданная точка (x, y) внутри P. Предложите варианты правила в случаях, если полигон: выпуклый, не выпуклый, точки на гранях полигона не внутри P.
Предложить способ (основные принципы) для нахождения пересечения двух треугольников в двухмерном пространстве.

  • Имя файла: prostranstvennye-bazy-dannyh.pptx
  • Количество просмотров: 129
  • Количество скачиваний: 0