Просторові типи даних
Всі СУБД, як спеціалізовані, так і неспеціалізовані можуть безпосередньо представляти тільки певні типи інформації. За будь-якої СУБД варто модель даних: точний опис типів інформації та як інформація повинна бути логічно організована. З цього випливає, що для добре продуманої СУБД, такою, що може бути логічно розширена, формулювання відповідної моделі даних повинна передувати власне розробці СУБД. Таким чином, моделювання даних відіграє важливу роль в розробці СУБД. У даній статті розглядається поняття просторового тип даних з точки зору теорії типів даних, моделей даних і баз даних. Просторові дані можуть бути самого різного виду та призначення, такі як: цифрова модель рельєфу (скалярні чи векторні поля), геометричні фігури (двовимірні або тривимірні), покриття.
Просторові типи даних для СУБД повинні бути:
- замкнутими на безлічі операцій,
- мати формально-певну семантику,
- бути певними в термінах кінцевого уявлення доступного в комп'ютерах,
- пропонувати адекватні можливості для подання реальних просторових об'єктів,
- бути незалежними від конкретної моделі СУБД, але взаємодіяти з будь-хто.
Подання геометрії просторових об'єктів
Основне призначення просторових типів даних - представляти такі властивості реальних об'єктів як розташування, форма, розміри тобто геометрію об'єктів.
Геометрія це комбінація координатної геометрії і системи прив'язки [3]. Координатна геометрія складається з чотирьох складових:
- Послідовність координатних точок, заданих в одній і тій же системі прив'язки.
- Набір інших геометрій заданих в одній і тій же системі прив'язки.
- Алгоритм інтерпретації, який використовує ці геометрії і точки, для того щоб 'побудувати' координатний геометричний об'єкт, який неявно визначає розташування геометрії в просторі і часі.
- Просторово-часова система прив'язки, яка визначає відповідність між координатної геометрією і розташуванням, даючи геометрії інтерпретацію в 'реальному світі'.
Зазвичай координати точок скалярні, але можуть бути з різних областей визначення. наприклад:
де x, y і (не обов'язково) z - речові числа (координати абстрактної геометрії)
де E і N (Easten і Northing) - речові числа (координати карти)
Прості приклади геометрії асоціюються з декількома координатними точками, які проектуються в точки "реального світу" за допомогою системи прив'язки константної для заданої геометрії. Більш складні геометрії можуть бути сконструйовані за допомогою використання декількох простих геометрій. Цей конкретний клас геометрії матиме пов'язаний з ним метод інтерпретації, який використовує відповідні координатні точки для того, щоб виконати конструювання координатної геометрії, яка визначає розташування геометрії в просторово-часової системі прив'язки. Зауважимо, що глибина рекурсивного визначення може бути такою, яка потрібна для побудови складної геометричної конструкції, і що просторово-часова система прив'язки є константною для всієї конструкції. Наприклад, кожне кільце полігону може бути представлено у вигляді простої замкнутої лінії (послідовності точок з лінійною інтерполяцією). Полігон може бути представлений у вигляді набору граничних кілець зі звичайною інтерполяцією.
Система прив'язки це спосіб привласнення величин положенню, часу, або іншим описатели якості або кількості. Система прив'язки може бути результатом не тільки від координатної геометрії, але і від часу. У загальному випадку системи прив'язки можна розділить на просторові, тимчасові і просторово-часові.
Просторова система прив'язки це функція, яка положенням в просторі ставить у відповідність геометрії координатних кортежів в математичному просторі, зазвичай векторному просторі з речовими величинами координат і навпаки ставить у відповідність координатним величинам і геометрії положення в 'реальному світі'.
Тимчасова система прив'язки це функція, яка часу ставить у відповідність координату (зазвичай, одномірні точки і інтервали) і навпаки, координатної геометрії ставить у відповідність час в 'реальному світі'.
Просторово-часова система прив'язки це з'єднання просторової і тимчасової систем прив'язки, яке використовується для того, щоб координатної геометрії ставити у відповідність положення в просторі і часі. Як правило, це з'єднання використовує ортогональні координати, для подання простору і часу.
У більшості просторових СУБД підтримуються три основних типи координатної геометрії: точкові, лінійні, площинні. Точкові об'єкти представляються однією або декількома точками, лінійні - однієї або декількома лініями, майданні - одна чи кілька компонентами, кожна компонента складається з зовнішнього кордону і довільного кількість внутрішніх кордонів.
Покриття це різновид (підтип) об'єкта. Покриття має властивість зазвичай зване функцією покриття. чиє значення це функція, яка має деяку просторову область в якості області визначення, а множина значень може бути будь-яким безліччю. Як правило, безліч значень є безліччю однорідних кортежів. Покриття може мати більш ніж одну властивість, яка має функцію покриття в якості значення.
Тип Покриття має безліч важливих підтипів. наприклад:
- растровий образ
- Сітка
- Покриття дискретними точками
- Покриття лінійними ланцюжками
- TIN покриття
- покриття геометрією
- поверхня
- покриття многогранниками
- Найближчий сусід і втрачена область
- Покриття сегментованими лініями
Покриття може використовуватися для представлення одного об'єкта або безлічі об'єктів. Наприклад, безліч всіх доріг в деякій країні може розглядатися як один об'єкт - дорожня мережа. Просторова область визначення може бути будь-який геометрією або колекцією геометрій. Зазвичай геометрія супроводжується системою просторової прив'язки, так що його точки справляють вплив на стан в просторі. Найбільш поширена область визначення це безліч ночек. Це може бути кінцевий набір точок або безліч всіх точок належить деякої певної геометрії. Покриття з такою областю визначення точок ставлять у відповідність деякі значення (вектора). Так само допускається, що область визначення складається з безлічі геометрій. Покриття цього виду Геометриям ставлять у відповідність величини (вектора).
Для математичного формулювання поняття системи типів даних використовується гетерогенна алгебра [4]:
A = (S1 S1s | s Про S>, d | DОS>)
де S - кінцеве безліч імен сортів (типів), S - кінцеве безліч символів (імен) операцій, As - сорт (безліч) з ім'ям s, f d: A s1 x. xAsn Ю As є операція позначається d. Серед операцій можуть бути нуль-мірні: така операція (Ю s) задає об'єкт (елемент) As. Пара (S1 S) називається сигнатурою алгебри A.
Є три основні класи операцій на просторових даних:
- Просторові предикати, що виражають відносини геометрії;
- Операції, які повертають атомарні просторові значення;
- Операції, які повертають числа.
Просторові предикати порівнюють дві просторові величини на предмет їх відносин і повертають логічне значення.
Можна виділити наступні класи відносин:
- топологічні відносини, такі як суміжні, всередині, розділені; вони є топологічним изоморфизмом; GEOxGEO Ю BOOL
- відносини орієнтації, наприклад, вище, нижче на північ, на південь, а GEOxGEO Ю BOOL
- метричні відносини, наприклад, "відстань <100". GEOxGEOxREAL Ю BOOL
Топологічні відносини є найбільш важливими і вивчені досить глибоко. Основне питання полягає в тому, чи можливо перерахувати всі варіанти відносин. Один метод для цього був запропонований в [5]. Спочатку він був сформульований для простих областей (пов'язаних і без пустот) і заснований на порівнянні перетинів їх кордонів і внутрішніх областей. Для будь-яких двох об'єктів визначаються чотири безлічі перетинів, кожне з яких може бути порожнім або непустою, що дає в сукупності 16 комбінацій (див. Таблицю). Вісім з них не мають сенсу, два є симетричними, і в результаті виходить шість різних відносин: розділені, всередині, стосується, так само, покриває, перекриває.
Вираз топологічних відносин через перетин кордонів і внутрішніх областей
А перекриває В
Друга група операцій складається з операторів повертають в якості результату атомарні просторові значення.
- Оператори перетин, об'єднання, різниця представляють відповідні теоретико-множинні операції над двома атомарними просторовими величинами. GEOxGEO Ю GEO
- Оператор спільний кордон знаходить загальну граничну лінію (лінії) двох величин типу лінія або область. GEOxGEO Ю GEO
- Оператор контур обчислює величину типу лінія що є кордоном величини типу область. GEO Ю GEO
- Оператор внутрішність застосовується до лінійним величинам і повертає величину типу область, межею якої є дана лінія. GEO Ю GEO
- Оператор оболонка повертає мінімальний обмежує прямокутник (интервальную оболонку), коло мінімального радіусу, що містить об'єкт, або опуклу оболонку об'єкта. Оболонки, як правило, використовуються для фільтрації об'єктів при виконанні запитів і для індексації безлічі об'єктів. GEO Ю GEO
Третя група операцій містить просторові оператори, які повертають числа.
алгебра ROSE
Однією з найбільш відомих робіт присвячених просторовим типам даних є алгебра ROSE [2].
Основна ідея алгебри ROSE - використовувати решітки (realm) в якості області визначення лежать в основі типів даних. Решітка як загальна концепція бази даних це кінцева, динамічна, що визначається користувачем структура лежить в основі однієї або кількох системних типів даних. Геометрична решітка, певна в алгебрі ROSE є планарним графом над сіткою з кінцевим дозволом. Проблеми обчислювальної надійності і топологічної коректності вирішуються в рамках граткової шару, так, що просторові алгебри певні над гратами мають дуже хороші топологічні властивості. Грати також взаємодіють з СУБД для поліпшення геометричній коректності при створенні або оновленні об'єктів. Алгебра ROSE визначена над гратами і пропонує загальні типи для подання точок, ліній і областей разом з безліччю відповідних операцій. Вона описана в рамках полиморфной системи типів і взаємодіє з моделлю даних СУБД і мовою запитів через абстрактний інтерфейс моделі об'єктів.
Решітка це безліч точок і непересічних відрізків прямої заданий над дискретної областю визначення, тобто сіткою. Значення просторових типів даних можуть бути спроектовані з об'єктного подання до решітку. Граткових просторові типи даних алгебри ROSE називаються points, lines і regions. Що лежить в основі сітка виникає просто з того факту, що в пам'яті комп'ютера числа мають кінцеве уявлення. На практиці ці уявлення будуть фіксованої довжини і відповідають цілим або речовим типам даних доступним в мовах програмування.
Формальне визначення граткових просторових типів даних (ПМД) представлено у вигляді послідовності шарів. Кожен шар визначає свої власні структури і примітиви.
Нижній шар являє геометричні примітиви. Він визначає дискретний простір NxN, де N = - підмножина безлічі натуральних чисел. Об'єкти в цьому просторі це точки і відрізки прямої з координатами з N, звані N-точки та N-сегменти. Визначається набір операцій (предикатів) таких як лежить N-точка на N-сегменті або перетинаються два N-сегмента або знайти N-точку перетину двох N-сегментів. Важливим є те, що ці визначення дано в термінах "безпомилкової" цілочисельний арифметики і, таким чином, можуть бути чітко реалізовані.
Далі визначаються геометричні решітки, елементи яких називаються R-точками і R-сегментами. Основними операціями на решітках є перетин і видалення N-точок і N-сегментів, які можуть породити перебудову сегментів. Грати надають інтерфейс для взаємодії з СУБД. Наприклад, операція вставки N-сегмента крім зміненої решітки повертає перебудований N-сегмент і безліч перебудованих сегментів бази даних, які повинні бути змінені разом з логічними покажчиками на ці сегменти.
Другий рівень визначає деякі структури представлені на решітках, які використовуються в якості основи для визначення ПТД. Решітка може розглядатися як планарний граф; R-циклом називається цикл в цьому графі. R-гранню називається R-цикл, відповідний області з дірками, можливо містить кілька інших розділених R-циклів. R-примітивом називається мінімальна R-грань. Ці три поняття підтримують визначення типу даних області. R-блоком називається компонент зв'язності граткової графа, він підтримує визначення типу даних лінії. Для всіх цих структур визначаються предикати, що описують їх можливі відносини.
Третій шар являє просторові типи даних точки, лінії, області і визначає структуру відповідних значень цих типів. Точкове значення є безліччю R-точок. Є дві альтернативи для подання ліній і областей. У першій значення типу лінії є безліччю R-сегментів, а значення типу області безліч R-примітивів. Інша альтернатива еквівалентна, але "семантично багатшими": значення типу лінії є безліччю розділених R-блоків, а значення типу області - безліччю розділених R-граней. Крім того, є примітиви просторової алгебри певні на значеннях цих типів.
Верхній рівень алгебри ROSE включає формальне визначення семантики всіх операцій.