Эффективная постоянная рекурсивная структура данных

Question

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

• Получить список всех дочерних элементов узла

• Найти все родительские узлы (== кратчайший путь к корневому узлу)

Примечание: я на стадии планирования, поэтому я еще не ограничен определенной базой данных.

Answer 1

По крайней мере, Oracle может выполнять иерархических запросов .Рассмотрим пример ролей пользователей БД:

CREATE TABLE my_dba_role_privs(
   grantee        VARCHAR2(30),
   granted_role   VARCHAR2(30)
);   

-- assigning roles to roles
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CLIENT', 'SELECT_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CREATE_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CLIENT');

-- assigning roles to users
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_MATT', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_JOHN', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CM_MARY', 'COMMERCIAL_DEP');

Теперь выберите все роли пользователя 'CM_MARY':

SELECT DISTINCT GRANTED_ROLE role_name
  FROM my_dba_role_privs
 START WITH GRANTEE = 'CM_MARY'
       CONNECT BY GRANTEE = PRIOR GRANTED_ROLE;   

Результат:
COMMERCIAL_DEP
CREATE_ORDERS
CLIENT
SELECT_ORDERS

Выбор всех ролей и пользователей, которым принадлежит роль 'CLIENT'

SELECT GRANTEE role_name
  FROM my_dba_role_privs
 START WITH GRANTED_ROLE = 'CLIENT'
       CONNECT BY GRANTED_ROLE = PRIOR GRANTEE;   

Результат:
CL_JOHN
CL_MATT
COMMERCIAL_DEP
CM_MARY

ОБНОВЛЕНИЕ:
Поскольку вы упомянули, дерево будет довольно статичным, может быть интересно попробовать Деревья Джо Селко (примерно 180 строк для чтения).Это не требует самостоятельных соединений вообще!Итак, я ожидаю, что он будет работать в разы быстрее, чем CONNECT BY.Хотя я только что прочитал об этом всего 30 минут назад и не знаю, насколько он хорош в реальном мире

Обновление 2:"Модели с вложенным множеством" с MySQL: Управление иерархическими данными в MySQL Это то же самое, что и «Деревья Джо Селко» выше, но с большим количеством примеров и объяснений.

Answer 2

Если «все дети» означают только прямых детей, просто поместите список детей, а также указатель на родителя на каждом узле.Обратите внимание, что это сделает перемещение узла к другому родителю более дорогим, так как все (великие) дети также должны быть обновлены.

Если «все дети» действительно означают все дети, одинопцией будет построить строку идентификаторов каждого родителя и добавить ее в качестве индексированного столбца.Например, если у вас есть A, с дочерним элементом B, с внуком C, в C будет столбец со значением A/B/C.Теперь, чтобы найти всех потомков A, вы можете просто выполнить запрос LIKE на "A/%".Опять же, однако, это дорого, когда вам нужно сменить родителя узла с дочерними элементами.

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