(Продолжение. Начало в №7-9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 27)

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

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

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

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

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

Упрощенная структура БД, организованных LeoBase, выглядит таким образом (стрелками обозначены реляционные ссылки):

База данных "Отрезки" хранит координаты конечных точек (х1, у2; х2, у2) всех отрезков, составляющих полилинии. Эта БД ссылается на БД "Полилинии", содержащую атрибуты (здесь мы касаться их не будем)всех полилиний, которые сами по себе составляют готовые изображения объектов. БД "Полилинии", в свою очередь, ссылается на базы "Объекты", которые хранят имена и описания объектов карты, а также могут ссылаться на прочие БД комплекса. То, что БД "Объекты" существуют во множественном числе, обусловлено тем, что, в зависимости от того, кем является пользователь, об одном и том же объекте карты может потребоваться самая разнообразная информация.

Рассмотрим следующую схему:

Она представляет собой участок карты с нанесенными на него объектами и заданной в виде прямоугольника областью поиска. Рамку, которую пользователь выделил мышкой, можно определить двумя противоположными ее вершинами (на схеме - А и Б). Их координаты обозначаются, соответственно, через (Rх1,Rу1) и (Rх2,Rу2). Полилинии 1-5 на схеме упрощены до отрезков. Итак, перед СУБД стоит задача: найти, какие из объектов входят в заданную рамку (или пересекают ее), а какие - нет. Рассмотрим, как LeoBase справляется с этим.

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

1. На первом этапе происходит самая простая операция: определение безусловно входящих в рамку объектов. Запрос при этом выглядит так:

(((Rx1<=отрезки.x1<=rx2) and (ry1<="отрезки.y1<=Ry2))<p">OR

((Rx1<=отрезки.x2<=rx2) and (ry1<="отрезки.y2<=Ry2)))<p">Как видно из структуры запроса, критерием отбора безусловно входящих в рамку объектов служит расположение хотя бы одной из его конечных точек внутри рамки. Благодаря примененной в LeoBase технологии, которая при поиске позволяет обойтись без перебора, данная операция проходит очень быстро. Результатом поиска, проведенного сразу по четырем ключам, является множество выделенных записей, которое LeoBase сохраняет в состоянии. (3, 4)

2. Выделяются все записи БД. (1-5)

3. Определяется множество объектов, явно не входящих в рамку:

(((отрезки.x1OR

((отрезки.x1>Rx2) AND (отрезки.x2>Rx2))

OR

((отрезки.y1OR

((отрезки.y1>Ry2) AND (отрезки.y2>Ry2)))

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

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

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

6. Множество выделенных записей, сформированное в результате поиска, объединяется с состоянием, сохраненным на первом шаге. Получившееся множество и содержит ответ. (2, 3, 4)

Вторая часть задачи - вывод информации, касающейся объектов, входящих в область - решена с помощью стандартной процедуры LeoBase: проекции из БД "Полилинии" на одну из БД "Объекты".

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

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

В следующей статье мы расскажем о работе LeoBase в сети.

(Продолжение следует)

Владимир КОТЛЯРОВ,
"СофтИнформ", тел. 213-28-13,
e-mail: ui@activ.minsk.by