Sql рекурсия без рекурсии

Question

У меня есть четыре таблицы

create table entities{ 
integer id; 
string name; 
} 

create table users{ 
integer id;//fk to entities 
string email; 
} 

create table groups{ 
integer id;//fk to entities 
} 

create table group_members{ 
integer group_id; //fk to group 
integer entity_id;//fk to entity 
} 

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

Answer 1

Можете ли вы пояснить разницу между сущностью и пользователем? В противном случае ваши таблицы выглядят нормально. Вы делаете предположение, что между группами и сущностями существует взаимосвязь «многие-ко-многим».

В любом случае, с использованием стандартного SQL этот запрос:

SELECT name, group_id 
FROM entities JOIN group_members ON entities.id = group_members.entity_id; 

Это даст вам список имен и group_ids, одна пара на каждой строке. Если объект является членом нескольких групп, объект будет указан несколько раз.

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

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

Answer 2

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

Отъезд this question.

Answer 3

Вы можете сделать следующее:

• Используйте ПУСК С/CONNECT BY ПРИОР constructs.
• Создайте функцию PL/SQL.

Answer 4

В Oracle:

SELECT group_id 
FROM group_members 
START WITH 
     entity_id = :user_id 
CONNECT BY 
     entity_id = PRIOR group_id 

В SQL Server:

WITH q AS 
     (
     SELECT group_id, entity_id 
     FROM group_members 
     WHERE entity_id = @user_id 
     UNION ALL 
     SELECT gm.group_id, gm.entity_id 
     FROM group_members gm 
     JOIN q 
     ON  gm.entity_id = q.group_id 
     ) 
SELECT group_id 
FROM q 

В PostgreSQL 8.4:

WITH RECURSIVE 
     q AS 
     (
     SELECT group_id, entity_id 
     FROM group_members 
     WHERE entity_id = @user_id 
     UNION ALL 
     SELECT gm.group_id, gm.entity_id 
     FROM group_members gm 
     JOIN q 
     ON  gm.entity_id = q.group_id 
     ) 
SELECT group_id 
FROM q 

В PostgreSQL 8.3 и ниже:

CREATE OR REPLACE FUNCTION fn_group_members(INT) 
RETURNS SETOF group_members 
AS 
$$ 
     SELECT group_members 
     FROM group_members 
     WHERE entity_id = $1 
     UNION ALL 
     SELECT fn_group_members(group_members.group_id) 
     FROM group_members 
     WHERE entity_id = $1; 
$$ 
LANGUAGE 'sql'; 

SELECT group_id 
FROM group_members(:myuser) gm 

Answer 5

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

Тот, который я использовал больше всего, это Nested Sets.

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

Простой пример вложенного набора ...

Вид дерева:

-Electronics 
| 
|-Televisions 
| | 
| |-Tube 
| |-LCD 
| |-Plasma 
| 
|-Portable Electronics 
    | 
    |-MP3 Players 
    | | 
    | |-Flash 
    | 
    |-CD Players 
    |-2 Way Radios 

Nested Set Представление

+-------------+----------------------+-----+-----+ 
| category_id | name     | lft | rgt | 
+-------------+----------------------+-----+-----+ 
|   1 | ELECTRONICS   | 1 | 20 | 
|   2 | TELEVISIONS   | 2 | 9 | 
|   3 | TUBE     | 3 | 4 | 
|   4 | LCD     | 5 | 6 | 
|   5 | PLASMA    | 7 | 8 | 
|   6 | PORTABLE ELECTRONICS | 10 | 19 | 
|   7 | MP3 PLAYERS   | 11 | 14 | 
|   8 | FLASH    | 12 | 13 | 
|   9 | CD PLAYERS   | 15 | 16 | 
|   10 | 2 WAY RADIOS   | 17 | 18 | 
+-------------+----------------------+-----+-----+ 

Вы хотите прочитать article I linked, чтобы полностью понять это , но я попытаюсь дать короткое объяснение.

Элемент является членом другого элемента, если (значение «lft» (слева) ребенка больше значения родительского «ltf») И (значение «rgt» для ребенка меньше, чем значение «rgt» родителя)

"Flash" является Therfore членом "MP3-плейеров", "Портативная электроника" и "Электроника"

Или, conversley, члены "портативной электроники" являются:
- MP3-плееры
- Вспышка
- CD-плееры
- 2 Way Radios

У Джо Селко есть целая книга «Деревья и иерархии в SQL». Есть больше вариантов, чем вы думаете, но много компромиссов.

Примечание: Никогда не говорите, что что-то не может быть сделано, некоторые мофы появятся, чтобы показать вам, что в банке.

Answer 6

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

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

tbl_nodes  
---------- 
node_id 
parent_id 
left  
right 
level 

... 

Моего редактор создает иерархически связанные объекты из узлов класса C#

class node { 
     public int NodeID { get; set; } 
     public Node Parent { get; set; } 
     public int Left { get; set; } 
     public int Right { get; set; } 
     public Dictionary<int,Node> Nodes { get; set; } 
     public int Level { 
     get { 
      return (Parent!=null) ? Parent.Level+1 : 1; 
     } 
     } 
} 

Узлы свойство содержит список дочерних узлов. Когда бизнес-уровень загружает иерархию, он исправляет отношения родительский/дочерний. Когда сохраняет редактор nav, я рекурсивно устанавливаю значения свойств слева и справа, а затем сохраняю их в базе данных. Это позволяет мне получить данные в правильном порядке, что означает, что я могу установить родительские/дочерние ссылки во время извлечения, а не делать второй проход. Также означает, что все, что нужно для отображения иерархии (скажем, отчета), может легко получить список узлов в правильном порядке.

Без parent_id поля, вы можете получить строку навигацию к текущему узлу с

select n1.* 
from nodes n1, nodes n2 
where d1.lft <= d2.lft and d1.rgt >= d2.rgt 
and d2.id = @id 
order by lft; 

где @id является идентификатором узла, вы заинтересованы в.

Довольно очевидный материал, действительно, но он применим к элементам, таким как членство вложенных групп, которые могут быть не очевидны, и, как говорили другие, устраняет необходимость замедления рекурсивного SQL.