Проектирование пространственной базы данных.

[remedius]

Кто-нить имел дело с пространсвенными базами данных? Подскажите пожалуйста, что можно своять интересненькое за 16-32 дней по арх. Клиент-Сервер к примеру?Есть идеи, пишите.

[Dimka]

Что такое "пространственная база данных"?

[remedius]

Как я понимаю, это таже бд, только работает с пространственными данными и умеет обрабатывать пространственные запросы. Ну к примеру: найти все дома близ "моего", находящиеся в диапозоне не более 5 миль. Что-то в этом роде. в общем служит в основном для хранении сетей (дорожная сеть к примеру).

[Sla]

Как корабль мы назовем, так мы в нем и поплывем.
Как запрос напишем, такие данные получим.
Вернее, как опишем данные. а потом запрос.

[Dimka]

в общем служит в основном для хранении сетей (дорожная сеть к примеру).

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

[remedius]

а есть како-нить сайт посвященный алгоритмам обработки графов?Да, и что на счет структуры хранения: разве реляционная модель плохо подойдет для этого дела? или желательно изучить объектную модель и возможно даже  объектно реляционную? Как лучше для данной задачи хранить данные: в виде набора таблиц или в виде блобов? (типо бинарник хранящий инфу об объекте)?

[RXL]

remedius, наверно сначала нужно подумать над алгоритмами поиска, а потом уже о формате хранения данных...

[remedius]

dimka,
Я тут подумала,а как же тогда полилинии? что делать, если надо сохранить геометрию? хранить отдельные отношения для каждой полилинии, как множество описывающих ее точек? или, можно к это задаче подойти иначе?

[Dimka]

dimka,
Я тут подумала,а как же тогда полилинии? что делать, если надо сохранить геометрию? хранить отдельные отношения для каждой полилинии, как множество описывающих ее точек? или, можно к это задаче подойти иначе?

Я же говорил:

На вершинах и рёбрах могут строиться другие объекты.

Хоть вершины, хоть рёбра - без разницы.

[remedius]

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

[Dimka]

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

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

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

Ориентированные графы умеренного размера с числом рёбер где-то около (N^2)/2 удобно хранить битовой матрицей NxN (N - число вершин, элемент матрицы - бит, указывающий наличие или отсутствие ребра). Неориентированные графы умеренного размера с числом рёбер где-то около ( N/2)^2 удобно хранить треугольной битовой матрицей NxN - учитывается симметрия матрицы относительно главной диагонали. Скорость работы алгоритмов с матрицами довольно высока.  Для сильно или слабо связанных графов использование матриц нерационально  так как в матрицах содержится много повторяющихся элементов. Для слабо связанных графов, в которых мало количество ребёр, выгодно хранить рёбра в коллекции, нежели заводить матрицу. Для сильно связанных графов, стремящихся к полным графам, выгоднее хранить факты отсутствия рёбер в коллекции. Организация коллекций зависит от задач - лишь бы поиск нужных ребёр или фактов их отсутствия осуществлялся быстро.

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

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

[remedius]

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

[Dimka]

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

Хм... не понял. Карты же векторные, а не растровые?

[remedius]

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

[Dimka]

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

Если речь идёт о наложении векторной карты на различные растровые, то это вообще отдельная тема, более связанная с распознаванием образов, нежели с базами данных.

[remedius]

dimka, МММ...мда, наверно что-то я не догоняю. в общем я думаю, распознование тут не при чем. (да речь идет о наложении). Есть прога такая. MAPINFO, так вот, клиент я буду писать для нее. Там просто создается файлик с описанием проекции, и она сама все накладывает. Главное, чтоб все точки были в правильной проекции. А тут уже будет конечно зависеть от точности представления. Ибо трансформировать, тоже я собираюсь (я этим уже занималась)

[Dimka]

remedius, не знаю такой программы. Открыл первую ссылку про MapInfo, и там было:

В MapInfo используются десятичные градусы

Т.е. широта и долгота. Какие же тогда проблемы с проекциями? Сама программа преобразует то, что в БД хранится... Нет?

P.S. По вопросам, связанным с MapInfo я не помощник. Наверно, начинать надо было с конкретного продукта, а не с абстрактных "пространственных баз данных".

[remedius]

dimka, не совсем так. На самом деле у проги есть своя БД, и даже запросы легенькие моно писать на sql. Но, там не такого понятия как целостность. Поэтому у меня и возникло желание - задание своять своего сервера (скорее приписка к SQL ан .NET - там я слышала есть такая возможность, но не важно). Вот так...Там есть конечно-же и другие недостатки. При чем если своять что-то свое, то можно уже будет специализироваться на конкретных задачах - запросах к пространственным данным, что нет в MAPINFO.

[Dimka]

remedius, так ведь программа "умеет" работать только с данными в определённом формате. Если для неё, скажем, требуются градусы широты и долготы, то никуда от этого не уйти. Иначе ничего она не покажет.

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

[remedius]

dimka, да, я и говорю о точности при преобразовании. Если взять эллипс в широте.долготе (а хранить его соответсвенно по точкакм), преобразовать по точкам в проекционную каку-нить проекцию, а потом обратно, то уж эллипса не будет. Я в принципе и не стремлюсь особо. Но все равно стоит вопрос сколькими точками описывать эллипс 4 или 400?

[remedius]

ладно, в общем, что-то пока мы не о чем...Надо очертить границы того, что можно реализовать за 16-32 дня. Я бы с удовольствием,но с подобной задачей никогда не встречалась. С чего можно начать? Определить-очертить границу запросов, которые моя БД будет обрабатывать и в каком виде будет хранится инфа? Я совсем новичек в этом деле, и боюсь обжечься и не успеть в срок.

[Dimka]

dimka, да, я и говорю о точности при преобразовании. Если взять эллипс в широте.долготе (а хранить его соответсвенно по точкакм), преобразовать по точкам в проекционную каку-нить проекцию, а потом обратно, то уж эллипса не будет. Я в принципе и не стремлюсь особо. Но все равно стоит вопрос сколькими точками описывать эллипс 4 или 400?

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

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

Определить-очертить границу запросов

Я бы так сказал: Что требуется от приложения на данный момент? (Например, показать флажки размещения клиентов на карте города директору. Каждый флажок покрасить в цвета радуги в зависимости от объёмов продаж.) Это требования к приложению. И, отталкиваясь от этого, строить схему БД, намечая запросы. Подумать о функциях ввода информации в БД.

Надо очертить границы того, что можно реализовать за 16-32 дня.

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

[remedius]

dimka, если честно, то это просто курсовая, которую надо сделать за семестр. А потом это все-равно я буду дописывать в данном направлении, ибо надо это сдать будет как проект. (Ну ты сам понимаешь, курсовая важнее.Чем я щас распланирую все, что мне нужно сделать, лучше я что-то сделаю в срок, а потом расширять начну.
Спасибо. Я все учту.

[Dimka]

Ну ты сам понимаешь, курсовая важнее.Чем я щас распланирую все, что мне нужно сделать, лучше я что-то сделаю в срок, а потом расширять начну.

Мне б таких сознательных студентов .

[remedius]

в общем для разработки бд выбрала DB2 Express.

I. Есть по крайне мере 2 способа хранения данных:
1. создавать свой тип данных
2. хранить данные в виде блобов
Что посоветуете?

II. как обрабатывать запросы - в виде процедур, а потом из клиента вызывать их типа exec? или есть еще варианты?

[Dimka]

I. Есть по крайне мере 2 способа хранения данных:
1. создавать свой тип данных
2. хранить данные в виде блобов
Что посоветуете?

Есть нехитрое правило: хранить то, что нужно, и не хранить того, чего не нужно.

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

Если же задача придумана, то до просьбы посоветовать что-нибудь хорошо бы эту задачу изложить.

[Dimka]

II. как обрабатывать запросы - в виде процедур, а потом из клиента вызывать их типа exec? или есть еще варианты?

Это зависит от способа работы с БД. Если БД полностью динамическая, т.е. её структура модифицируется приложением - процедуры будут явно излишни. Если БД статическая, т.е. приложение лишь добавляет/изменяет/читает данные, не меняя структуры БД - лучше хранимые процедуры. Каждая процедура - это элементарная или составная операция обработки данных.

[remedius]

в общем подразумевается хранение пространственных сетей, что означает (как я понимаю), что существует пространственный объект, и что помимо его координат хранится также и система координат где-то. Что кстати подразумевается под изменением структуры БД? К примеру, если перетащить один объект, то соотвтсвенно, координаты других объектов, с ним связанных, также изменятся. Т.е. нужно будет учитывать топологию (так это вроде называется).

[Dimka]

Что кстати подразумевается под изменением структуры БД?

Структура БД - это таблицы, их поля, связи. Перемещение объектов - это операция над данными, хранящимися в БД, а не над структурой БД. Динамическая структура означает, что программа создаёт и/или удаляет таблицы, изменяет в таблицах наборы полей и т.п.

Хранение систем координат в БД... Обычно хранят данные в одном формате (в данном случае, в системе координат), а все преобразования в другие системы координат происходят на "выходе" - данные, хранимые в БД, не переписываются. Пересчёт делает программа или хранимые процедуры, "на лету" подменяя исходный (базовый) формат на требуемый. Иначе и нельзя. Вдруг с БД будет работать несколько пользователей одновременно? И каждый может потребовать перевода в какую-то альтернативную систему координат относительно других пользователей.

[remedius]

поняла спасибо.
По поводу систем координат, я так и собиралась сделать.