О Spatial Data

Любая приличная СУБД нынче поддерживает то, что называется Spatial Data. А юные СУБД торопятся обзавестись этой поддержкой. А как только обзаводятся, громогласно об этом заявляют. Потому что это — конкурентное преимущество.

Что же это за пространственные данные? Лучше обратиться к Википедии. К описанию стандартов со смешными именами: WKT (Well-Known Text) и WKB (Well-Known Binary).

WKT — это стандартное текстовое описание пространственных данных. WKB — это полностью аналогичное описание, но в бинарном виде. Взаимоотношение между ними примерно такое же, как между текстовым JSON и бинарным монговым BSON. Есть еще GeoJSON, тоже текстовый, но в JSON синтаксисе.

Собственно, «классические» CУБД хранят пространственные данные в виде BLOBов, являющихся некоторым расширением WKB. В отдельных колонках специального типа. А новомодные документоориентированные NoSQL БД, которые хранят документы в JSON или BSON, предпочитают GeoJSON представление.

Как видите, описать можно координаты точек, прямых, ломаных, многоугольников (интересным случаем является многоугольник с дыркой, «бублик»). А также множество точек, прямых, ломаных, многоугольников (единым объектом).

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

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

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

С широтой и долготой тоже есть разночтения, вызванные тем, что Земля не является идеальным шаром. Не является она и эллипсоидом. Но на практике её все же считают эллипсоидом с определенными большим и малым радиусами. И все эти наши гугло/яндексо/бинго/OSM/прочиекарты пользуются широтой и долготой по стандарту WGS 84.

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

Какие операции можно делать с пространственными данными? Ну, банально, находить расстояния. Между точками, между точкой и прямой, между точкой и многоугольником. Хорошо, если у нас евклидова система координат. Применяем теорему Пифагора и вот оно — расстояние. Но вот на земном шаре не все так просто. Ибо градус долготы на разных широтах имеет совсем разное значение в метрах. А прямые — не всегда такие прямые (посмотрите на маршруты авиарейсов, а ведь это прямые). Так что за правильную реализацию подсчета расстояний (в метрах) между точками на земном шаре, заданными широтой и долготой (в градусах), уже стоит сказать разработчикам СУБД спасибо.

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

Ну и конечно же можно индексировать пространственные данные. Тут все несколько интересно. Что индексировать-то? Допустим, нам нужно определить объекты, ближайшие к заданной точке. Т.е. выбрать те объекты, расстояние от которых до заданной точки минимально. Конечно, можно построить функциональный индекс по расстоянию и воспользоваться им для быстрого поиска. Но ведь точка, для которой мы проиндексируем расстояние, в других запросах будет другая.

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

select b.name, Distance(MakePoint(73.391631, 54.976775, 4326), b.geom)
from building b
where b.rowid in
    (select pkid from idx_building_geom where
         xmin > 73.390 and xmax < 73.393 and ymin > 54.975 and ymax < 54.978)
order by 2
limit 5;

Ну и в каких же СУБД все это хозяйство реализовано?

• PostGIS — расширение для PostgreSQL. Самая крутая реализация, все остальные — в догоняющих.
• SpatiaLite — расширение для SQLite. Дада, для той самой маленькой встраиваемой SQL базы есть вполне полноценное расширение для работы с (гео)пространственными данными, почти не уступающее по возможностям PostGIS.
• В MySQL тоже есть стандартное расширение.
• Для Oracle тоже есть Oracle Spatial and Graph. За ваши деньги.
• В MongoDB есть нужные индексы и (относительно) небольшой набор операций.
• У Couchbase, который недавно стал документо-ориентированным, тоже есть какие-то георасширения.
• Тысячи их...

Хранить пространственный объект целиком в колонке таблицы или поле документа — не единственный способ представления. Возьмем, например, границу между двумя государствами. Контур каждой страны — это некий многоугольник, который хранится в каком-то одном значении в БД. И эти многоугольники соприкасаются неким множеством ребер, которые и образуют границу. Но вот беда, каждый многоугольник содержит свою копию описания ребер границы. Во-первых, тут есть дублирование данных. Во-вторых, если кто-то неудачно отредактирует многоугольник одного государства, но забудет отредактировать многоугольник другой страны, то случится межгосударственный конфликт. Потому что где-то контуры стран перестанут соприкасаться, и возникнет ничейная территория. А где-то контуры одного государства зайдут на территорию другого государства.

Можно же один раз указать точки и прямые границы между государствами. А затем сказать, что получившаяся линия входит в контуры обоих государств, и с одной стороны этой линии — одно государство, а с другой — другое. Дублирования, дырок и наложений в этом случае не возникает. Такой способ описания (гео)пространственных данных называется топологией. И реализован он в PostGIS и, если верить Википедии, в Oracle. Забавно, что от SQL там почти ничего не остается. Вся работа делается через функции.

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

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

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

Напоследок еще чуть-чуть:

• Небольшая презентация на тему пространственных данных в СУБД
• Небольшая презентация на тему координат и проекций
• Немного документации с геохакатона