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

В 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 2

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

Больше всего я использовал Вложенные наборы .

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

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

Вид дерева:

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

Представление вложенного набора

+-------------+----------------------+-----+-----+
| 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 |
+-------------+----------------------+-----+-----+

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

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

"Flash" является членом "MP3 PLAYERS", "Portable Electronics" и "Electronics"

Или, собственно, члены "Портативной электроники":
- MP3-плееры
- Вспышка
- CD-плееры
- двухстороннее радио

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

Я бы предложил включить поле parent_id в таблицу 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;
         }
      }
}

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

Без поля 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.

Answer 5

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

• Используйте START WITH / CONNECT BY PRIOR конструкций .
• Создание функции PL / SQL.

Answer 6

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

Проверьте этот вопрос .