на главнуюВсе эхи RU.ALGORITHMS
войти ?

Re: О представлении графа в базе данных

От Alex Mizrahi (2:5020/400) к Kalachihin Vladimir

В ответ на Заголовок предыдущего сообщения в треде (Имя Автора)


From: "Alex Mizrahi" <udodenko@users.sourceforge.net>

AM>> Hа практике неориентированные графы можно считать частным случаем
AM>> ориентированных: если граф G неориентированный, то для каждого ребра
AM>> A->B существует также и ребро B->A.

KV> А вот это никак нельзя считать. Поскольку в неориентированном графе
KV> отсутствует ребро A->B. Там есть только A-B. Или, если хочешь, A<->B.

Hу вот ребро A<->B можно представить в виде пары дуг A->B и B->A.
Можно в том плане, что тогда определения эквивалентны.

AM>> А если подумать -- возможным.

KV> Гы. Как? В свете через абзац выше процитированного?
KV> Hа всякий случай напомню - в теории реляционных баз данных нет
KV> встроенных процедур ;-)

В реляционной базе нет и понятие "граф". Оно возникает на уровне приложение.
Соответственно, на уровне приложения нужно и принимать решение о том, как
представлять данные в базе.
Я вижу два варианта:

1. Добавлять обе пары.
Тогда данных хранится больше (избыточность), добавлять дольше, но выборка
быстрее.
В этом случае мы можем сказать, что неориентированный граф представлен в
виде эквивалентного ориентированного, с которым проще работать, т.к. он
однозначно соответствует отношению, а с отношениями реляционные базы умеют
работать хорошо. (По определению, relation = отношение.)

2. Добавлять только одну пару. Можно для определённости добавлять <A,B> если
A<=B и <B,A> если B<A.
В этом случае избыточности не наблюдается, но некоторые запросы на
выборку становятся сложнее -- например, там может появиться OR или UNION.
В этом случае неупорядоченность пар прийдётся реализовать алгоритмически
в запросах, а на реляционный подход это ложится не совсем гладко.

Вот такой вот трейдофф.

KV>>> Поэтому на практике отношение Предок, Потомок вида A,B рассматривают
KV>>> либо как "Объект A, имеющий потомка B", либо как "Объект B, имеющий
KV>>> предка A".

AM>> Hу это ты уже в какую-то не ту степь ушёл. В теории графов нет
AM>> объектов, предков и потомков. Есть вершины и рёбра/дуги.

KV> Я тут плавно перешёл от теории графов к их представлению в реляционной
KV> форме. А если слово "объект" вызывает у тебя нехорошие аллюзии - замени
KV> его словом "сущность".

Запись <A, B> в базе данных (или как там оно по научном, кортеж?) говорит о
наличии дуги между вершинами A и B.
То есть вполне можно одновременно и про базы данных говорить, и про графы --
без отсебятины.

К твоей формулировке у меня такая претензия -- запись говорит не об объекте,
а об отношении/связи между объектами.

KV>>> Так вопрос - а как правильно?
AM>> Честно говоря, не вижу разницы.

KV> Ото-ж. А я - вижу:

Либо можно сказать, что ты не видишь эквивалентности.

KV>>> Моя практика показывает, что представлять
KV>>> узлы дерева, как объекты, имеющие предка - радикально удобней, чем
KV>>> как объекты, имеющие потомка. В одной известной мне предметной
KV>>> области, которая точно никогда не заморачивалась такими вопросами,
KV>>> все связи строятся именно как указание предка, а не потомка.

AM>> Тут неплохо бы привести пример, честно говоря не понимаю о чём ты...

KV> Hу вот если мы рассмативаем представление связи между двумя объектами
KV> (пардон, сущностями...) в виде атрибутов - указателей на потомков,

Мы ещё о реляционных базах данных или уже об императивном программирование?

В программировании разниwа, конечно, есть.

Hапример, структура

struct vertex {
vertex* parent;
....
};

Она очень простая и компактная, но по ней можно ходить только от листьев
вверх (если говорить о дереве).
Второй вариант:

struct vertex {
vertex []kids;
...
};

позволяет ходить от вершины к листьям. И наконец

struct vertex {
vertex []kids;
vertex* parent;
...
}

позволяет ходить в обоих направлениях.

Hо в реляционных БД направлений нет.
Предположим есть такая таблица:

CREATE TABLE graph1 (parent ..., kid ...);

где пара (parent, kid) означает наличие дуги из parent в kid.

Если записать как

CREATE TABLE graph1 (kid ..., parent ...);

то ровным счётом ничего не изменится, даже запросы переписывать не
прийдётся.

Мне кажется я начинаю понимать о чём ты -- ты хочешь не выделять отношение
графа в отдельное отношение (таблицу), а хранить вместе и информацию об
объектах:

CREATE TABLE graph1 (kid ..., parent ..., kid_data1 ..., kid_data2 ...);

Hа конкретном примере

CREATE TABLE ученик(ид_ученика, ид_учителя, имя, фамилия...);

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

Весь вопрос в кардинальности связей.

KV> то, скажем, визуализация такой связи не может быть независимой для
KV> каждого атрибута, а касается всей кучи таких атрибутов сразу.

А тут нужно вспомнить, что ты визуализируешь не представление, а граф.
Если у тебя "куча аттрибутов", то значит у тебя не один граф, а много.
Можно визуализировать их каждый по отдельности, например. Можно как-то по
другому, пытаться представить одновременно несколько графов.

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

KV> А именно: в случае изображения свёрнутой ветви дерева для первого
KV> потомка надо нарисовать плюсик, а для всех остальных - ничего. А в
KV> случае изображения развёрнутой - для каждого атрибута рисовать что
KV> положено. В некоторых случаях такая зависимость аннойна, а в других -
KV> недопустима. В случае же, если связь представлена указанием на предка -
KV> таких трудностей нет, и что рисовать - целиком проблема, локализованная
KV> в
KV> одном атрибуте.

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

Если ты работаешь с деревом, то там ассиметрию задаёт направлению к корню,
т.к. корень только один.

--- ifmail v.2.15dev5.4
* Origin: Demos online service (2:5020/400)

Ответы на это письмо:

From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку

From: Username
Или коротким

FGHI-url этого письма: area://RU.ALGORITHMS?msgid=<1187408935@killer>+0a833a33