Интересная задачка. Рекурсия или что?

[RXL]

Есть две таблички:

Код: (SQL)

CREATE TABLE USERS
(
  USER_ID NUMBER,
  // .........
  PRIMARY KEY (USER_ID)
);

CREATE TABLE USER_GROUPS
(
  USER_ID NUMBER,
  GROUP_ID NUMBER,
  PRIMARY KEY (USER_ID, GROUP_ID)
);

В USERS, понятное дело, юзера со своими уникальными номерами. Но там же находятся и группы. Любой пользователь может оказаться группой. Отношения вхождения в группу описаны в USER_GROUPS.

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

Нужно получить список групп, к которым имеет отношение юзер.
Если уровней таких вложений ограниченное число, то я это решил так (для двух уровней групп):

Код: (SQL)

SELECT GROUP_ID
FROM USER_GROUPS
WHERE USER_ID = :USER
  OR USER_ID IN (
    SELECT GROUP_ID
    FROM USER_GROUPS
    WHERE USER_ID = :USER
  )

А вот если не лимитировать вложенность?
Рекурсия?
Какой вариант можно придумать?

P.S.: пожалуйста, ближе к теме и советов поменять структуру данных не надо.

[Dimka]

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

Говорят, в SQL Server 2008 есть специальный тип данных для деревьев, но я пока с ним не сталкивался.

Для оптимизации запросов можно изменить структуру данных, которая бы сразу описывала членство пользователя во всех группах, но выигрыш в работе запроса означает проигрыш на операциях вставки/обновления. И наоборот.

[RXL]

Меня, собственно, интересует не оптимизация, а алгоритмы.
Реализовано это на Oracle 10g.
Скорость выполнения не существенна - вполне можно пару десятых долей секунды потратить.

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

[PooH]

древовидный запрос не подойдет?
что-то типа:

Код: (Text) oracle sql

SELECT *
  FROM user_groups u
CONNECT BY PRIOR u.user_id = u.group_id
 START WITH u.user_id = :v_user_id;

[npak]

Рома, ты сильно рискуешь - нужно ставить запрет на циклические вхождения.

Например - группа А входит в группу В, группа В - в группу С, а группа С в группу А.
Нужно включить в таблицу триггер для отлова циклов при добавлении.

[PooH]

npak, давай не будем гадать =) это может и не понадобится... зависит от назначения БД... кстати, древовидный запрос при существующем цикле выдаст ошибку.

[RXL]

npak, что-то я забыл об этом...

PooH, спасибо!

Вот тест:

Код: (SQL)

CREATE TABLE TEST
(
  USER_ID NUMBER(4) NOT NULL,
  GROUP_ID NUMBER(4) NOT NULL,
  PRIMARY KEY (USER_ID, GROUP_ID)
);

INSERT INTO TEST VALUES (1, 100);
INSERT INTO TEST VALUES (100, 101);
INSERT INTO TEST VALUES (100, 102);
INSERT INTO TEST VALUES (101, 103);
INSERT INTO TEST VALUES (103, 100);
COMMIT;

SELECT USER_ID, GROUP_ID, LEVEL
FROM TEST t
START WITH t.USER_ID = 1
CONNECT BY NOCYCLE PRIOR t.GROUP_ID = t.USER_ID;

Код:

USER_ID	GROUP_ID LEVEL
1	100	 1
100	101	 2
101	103	 3
100	102	 2

NOCYCLE, как раз, предотвращает циклические связи.
Кстати, переставил члены условия - иначе поиск идет в другую сторону - по группе находятся пользователи.
Псевдо-столбец LEVEL показывет уровень иерархии.

Просто cказка! 

     

[PooH]

ну членов условия я наобум ставил...
насчет 10g сомневаюсь, а вот в 11.1 еще больше накрутили =)
http://www.psoug.org/reference/connectby.html