Xpoint
   [напомнить пароль]

Хранение ориентированного графа в БД

Метки: [без меток]
2006-03-06 20:40:34 [обр] Sync[досье]

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

Задача состоит в построении отношений между сотрудниками фирмы.

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

Что значит оптимальная структура? Чтобы с минимальными затратами находить подобного рода штуки:

- нахождение цепочки от сотрудника до последнего его подчиненного

- аналогично от сотрудника до самого высшего начальника над ним

- нахождение всех подчиненных первого (второго, ...) уровня (то есть прямых, посредственных,... подчиненных)

- аналогично всех стоящих выше.

и т.д.

То, что пришло в голову первым:
узлы

employ_id name

связи

link_id name
1 podchinen
2 nachalnik
3 friend

узлы-связи

employ_1 employ_2 link_id
1 2 1
1 3 3
3 2 2

не совсем подходит, так как большие трудности возникают даже при нахождении пути от сотрудника А до сотрудника Б,
при выводе, например, подчиненных второго ранга (то есть подчиненных моих подчинненных) и тд.

спустя 7 часов [обр] Антон Пыжёв(0/8)[досье]

Sync[досье] На мой взгляд, в данном случае лучше всего использовать матрицу смежности вершин Aij = (aij), где aij = 1, если существует дуга из i-й вершины в j-ю, aij = 0 в противном случае. Размерность матрицы, очевидно, n на n, где n - число вершин (сотрудников).

Далее модифицируем алгоритмы поиска в глубину и в ширину под конкретные задачи.

спустя 16 минут [обр] Антон Пыжёв(0/8)[досье]
UPD: Матрицу удобнее хранить в базе, а алгоритмы используют динамические структуры. Поэтому, придется предусмотреть преобразование матрицы смежности в списки смежности и обратно.
спустя 1 час 1 минуту [обр] Закиров Руслан(0/341)[досье]
Собрал список тем с вопросами по теме, статью писать по ним пока нет врмени.
Хранение древовидных структур в реляционных БД
спустя 6 часов [обр] GRAy(0/259)[досье]
Sync[досье] Реляционная БД (если вы о реляционных бд спрашиваете) вообще не оптимальна для хранения графов и работы с ними. Так что добиться от неё одинаково хорошей производительности для всех приведённых вами зачач невозможно. Вернее сказать - вам в любом случае придётся идти на компромис между лёгкостью управления такой структурой (т.е. добавление, удаление, перенос поддеревьев и т.п.) и лёгкостью выборки произвольных наборов данных из неё. Задача преобразования "матрицы смежности" в/из "списки смежности" (sic!) это как раз то, что будет занимать большее или меньшее время в зависимости от выбраной структуры хранения. В вашем примере некоторые подмножества сотрудников образуют иерархии (начальник-подчинённый) а некоторые образуют просто списки (коллеги) и уже одно это означает, что "оптимальности" для обеих случаев одновременно достигнуть не удастся.
спустя 1 год 10 месяцев [обр] jenik15[досье]
Программа для построения с матрицы смежности матрицу инцидентности. Делает поиск в глубину, ширину .Ищет Эйлерову цепь. Удобно сравнивать две матрицы и список смежности.
Можно переключиться между русским и украинским языком.
найти прогу можно на:
http://www.steamstudios.3dn.ru/
Powered by POEM™ Engine Copyright © 2002-2005