Как представить дерево данных в SQL?
Я пишу структуру дерева данных, которая объединена из дерева и TreeNode. Дерево будет содержать корень и действия верхнего уровня на данных. Я использую библиотеку пользовательского интерфейса, чтобы представить дерево в форме окна, где я могу связать дерево с TreeView.
Мне нужно будет сохранить это дерево и узлы в БД. Что будет лучшим способом сохранить дерево и получить следующие возможности:
- Интуитивно понятная реализация.
- Легкая привязка. Будет легко перейти от дерева к структуре БД и обратно (если есть)
У меня было 2 идеи. Первый заключается в сериализации данных в одну строку в таблице. Второе - сохранить в таблицах, но затем при переходе к объектам данных я потеряю состояния строк в таблице на измененных узлах.
Есть идеи?
9 ответов
Я добавил в закладки этот слайдшоу об SQL-Antipatterns, в котором обсуждаются несколько альтернатив: http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back?src=embed
Исходя из этого, рекомендуется использовать таблицу закрытия (это объясняется на слайдах).
Вот резюме (слайд 77):
| Query Child | Query Subtree | Modify Tree | Ref. Integrity
Adjacency List | Easy | Hard | Easy | Yes
Path Enumeration | Easy | Easy | Hard | No
Nested Sets | Hard | Easy | Hard | No
Closure Table | Easy | Easy | Easy | Yes
Самая простая реализация - это структура списка смежности:
id parent_id data
Тем не менее, некоторые базы данных, в частности, MySQL, есть некоторые проблемы в обработке этой модели, потому что она требует способности выполнять рекурсивные запросы, которые MySQL не хватает.
Еще одна модель это вложенные множества:
id lft rgt data
где lft а также rgt произвольные значения, которые определяют иерархию (любой дочерний lft, rgt должно быть в пределах любого родителя lft, rgt)
Это не требует рекурсивных запросов, но его медленнее и сложнее поддерживать.
Однако в MySQL это можно улучшить с помощью SPATIAL abitilies.
Смотрите эти статьи в моем блоге:
- Список смежности и вложенные множества: PostgreSQL
- Список смежности и вложенные множества: SQL Server
- Список смежности и вложенные множества: Oracle
- Список смежности против вложенных множеств: MySQL
для более подробных объяснений.
Я удивлен, что никто не упомянул решение с материализованным путем, которое, вероятно, является самым быстрым способом работы с деревьями в стандартном SQL.
При таком подходе каждый узел в дереве имеет путь к столбцу, где хранится полный путь от корня до узла. Это включает в себя очень простые и быстрые запросы.
Посмотрите на пример таблицы:
+---------+-------+
| node_id | path |
+---------+-------+
| 0 | |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 1.4 |
| 5 | 2.5 |
| 6 | 2.6 |
| 7 | 2.6.7 |
| 8 | 2.6.8 |
| 9 | 2.6.9 |
+---------+-------+
Чтобы получить дочерние элементы узла x, вы можете написать следующий запрос:
SELECT * FROM node WHERE path LIKE CONCAT((SELECT path FROM node WHERE node_id = x), '.%')
Имейте в виду, что путь к столбцу должен быть проиндексирован, чтобы быстро выполнять предложение LIKE.
Если вы используете PostgreSQL, вы можете использовать ltreeпакет в расширении contrib (поставляется по умолчанию), который реализует древовидную структуру данных.
Из документов:
CREATE TABLE test (path ltree);
INSERT INTO test VALUES ('Top');
INSERT INTO test VALUES ('Top.Science');
INSERT INTO test VALUES ('Top.Science.Astronomy');
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology');
INSERT INTO test VALUES ('Top.Hobbies');
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy');
INSERT INTO test VALUES ('Top.Collections');
INSERT INTO test VALUES ('Top.Collections.Pictures');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
CREATE INDEX path_gist_idx ON test USING GIST (path);
CREATE INDEX path_idx ON test USING BTREE (path);
Вы можете делать запросы как:
ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science';
path
------------------------------------
Top.Science
Top.Science.Astronomy
Top.Science.Astronomy.Astrophysics
Top.Science.Astronomy.Cosmology
(4 rows)
Это зависит от того, как вы будете запрашивать и обновлять данные. Если вы храните все данные в одной строке, это, по сути, единая единица, к которой вы не можете запросить или частично обновить, не переписав все данные.
Если вы хотите сохранить каждый элемент в виде строки, вы должны сначала прочитать " Управление иерархическими данными в MySQL" (специфично для MySQL, но этот совет подходит и для многих других баз данных).
Если вы когда-либо обращаетесь только ко всему дереву, модель списка смежности затрудняет извлечение всех узлов в корне без использования рекурсивного запроса. Если вы добавите дополнительный столбец, который ссылается на заголовок, вы можете сделать SELECT * WHERE head_id = @id и получить все дерево одним нерекурсивным запросом, но он денормализует базу данных.
Некоторые базы данных имеют пользовательские расширения, которые упрощают хранение и извлечение иерархических данных, например, Oracle имеет CONNECT BY.
Так как это лучший ответ на вопрос "sql trees" в поиске Google, я постараюсь обновить его с точки зрения сегодняшнего дня (декабрь 2018 года).
Большинство ответов подразумевают, что использование списка смежности является простым и медленным, и поэтому рекомендуют другие методы.
Начиная с версии 8 (опубликовано в апреле 2018 г.) MySQL поддерживает рекурсивные общие табличные выражения (CTE). MySQL немного опоздал на шоу, но это открывает новую опцию.
Здесь есть учебник, который объясняет использование рекурсивных запросов для управления списком смежности.
Поскольку рекурсия теперь полностью выполняется внутри механизма базы данных, она намного быстрее, чем в прошлом (когда она должна была выполняться в обработчике сценариев).
В этом блоге приводятся некоторые измерения (которые являются предвзятыми и для postgres вместо MySQL), но, тем не менее, показывают, что списки смежности не должны быть медленными.
Итак, мой вывод сегодня:
- Простой список смежности может быть достаточно быстрым, если ядро базы данных поддерживает рекурсию.
- Сделайте тест с вашими собственными данными и вашим собственным движком.
- Не доверяйте устаревшим рекомендациям, указывающим на "лучший" метод.
Отношения дерева PGSQL
Здравствуйте, я только что разобрался с проектом, над которым работаю, и решил поделиться своей записью. Надеюсь, это поможет. Давайте начнем с некоторых предварительных требований
Это, по сути,
closure tableрешение, упомянутое выше. Использование рекурсивных вызовов. Спасибо за эти слайды, они очень полезны, я бы хотел увидеть их до того, как напишу эту статью :)
предпосылки
Рекурсивные функции
это функции, которые вызывают сами себя, т.е.
function factorial(n) {
if (n = 0) return 1; //base case
return n * factorial(n - 1); // recursive call
}
Это довольно круто, к счастью, pgsql также имеет рекурсивные функции, но это может быть слишком. Я предпочитаю функциональные вещи cte с pgsql
WITH RECURSIVE t(n) AS (
VALUES (1) -- nonrecusive term
UNION ALL
SELECT n+1 FROM t WHERE n < 100 -- recusive term
--continues until union adds nothing
)
SELECT sum(n) FROM t;
Общая форма рекурсивного запроса WITH всегда представляет собой нерекурсивный терм, затем UNION (или UNION ALL), затем рекурсивный терм, где только рекурсивный терм может содержать ссылку на собственные выходные данные запроса. Такой запрос выполняется следующим образом:
Рекурсивная оценка запроса
Оцените нерекурсивный термин. Для UNION (но не для UNION ALL) отбрасывайте повторяющиеся строки. Включите все оставшиеся строки в результат рекурсивного запроса, а также поместите их во временную рабочую таблицу.
Пока рабочий стол не пуст, повторите эти шаги:
а. Вычислите рекурсивный терм, заменив рекурсивную ссылку на себя текущим содержимым рабочей таблицы. Для UNION (но не для UNION ALL) отбрасывайте повторяющиеся строки и строки, дублирующие любую предыдущую результирующую строку. Включить все оставшиеся строки в результат рекурсивного запроса, а также поместить их во временную промежуточную таблицу.
б. Замените содержимое рабочей таблицы содержимым промежуточной таблицы, затем очистите промежуточную таблицу.
чтобы сделать что-то вроде факториала в sql, вам нужно сделать что-то подобное , поэтому опубликуйте
ALTER FUNCTION dbo.fnGetFactorial (@num int)
RETURNS INT
AS
BEGIN
DECLARE @n int
IF @num <= 1 SET @n = 1
ELSE SET @n = @num * dbo.fnGetFactorial(@num - 1)
RETURN @n
END
GO
Древовидные структуры данных (скорее лес :)
Важно отметить, что дерево является подмножеством графа . Это может быть просто обеспечено отношением, которое каждый узел имеет только один родитель.
Представление дерева в PGSQL
Я думаю, что будет проще поработать над этим немного теоретически, прежде чем мы перейдем к sql.
Простой способ представления отношения графа без дублирования данных — разделение
nodes(id, data)с краев. Затем мы можем ограничить
edges(parent_id, child_id)table для обеспечения соблюдения нашего ограничения. требовать, чтобы parent_id, child_id, а также только дочерний идентификатор были уникальными
create table nodes (
id uuid default uuid_generate_v4() not null unique ,
name varchar(255) not null,
json json default '{}'::json not null,
remarks varchar(255),
);
create table edges (
id uuid default uuid_generate_v4() not null,
parent_id uuid not null,
child_id uuid not null,
meta json default '{}'::json,
constraint group_group_id_key
primary key (id),
constraint group_group_unique_combo
unique (parent_id, child_id),
constraint group_group_unique_child
unique (child_id),
foreign key (parent_id) references nodes
on update cascade on delete cascade,
foreign key (child_id) references nodes
on update cascade on delete cascade
);
Обратите внимание, что теоретически все это можно сделать только с одной таблицей, просто поместив parent_id в таблицу узлов, а затем
CREATE VIEW v_edges as (SELECT id as child_id, parent_id FROM nodes)
но для предложения гибкости и для того, чтобы мы могли включать другие структуры графов в эту структуру, я буду использовать общую структуру отношений «многие ко многим». В идеале это позволит распространить это исследование на другие графовые алгоритмы.
Начнем с примера структуры данных
INSERT (id, my_data) VALUES ('alpha', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('bravo', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('charly', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('berry', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('zeta', 'my big data') INTO nodes
INSERT (id, my_data) VALUES ('yank', 'my big data') INTO nodes
INSERT (parent_id, child_id) VALUES ('alpha', 'bravo') INTO edges
INSERT (parent_id, child_id) VALUES ('alpha', 'berry') INTO edges
INSERT (parent_id, child_id) VALUES ('bravo', 'charly') INTO edges
INSERT (parent_id, child_id) VALUES ('yank', 'zeta') INTO edges
-- rank0 Alpha Yank
-- rank1 Bravo Berry Zeta
-- rank2 Charly
Обратите внимание на интересные свойства дерева.
(number of edges e) =( number of nodes n)-1у каждого ребенка есть ровно один родитель.
Тогда мы можем упростить уравнения
let n = node
let p = parent
let c = child
let ns = nodes = groups
let es = edges = group_group // because this is a relationship of a group entity to another group entity
Итак, теперь какие вопросы мы будем задавать.
«Учитывая произвольный набор групп s, каково покрытие графа, если предположить, что узлы наследуют своих потомков?»
Это сложный вопрос, он требует от нас пройти по графу и найти всех дочерних элементов каждого узла в s.
Это продолжается с этого сообщения о переполнении стека
-- some DBMS (e.g. Postgres) require the word "recursive"
-- some others (Oracle, SQL-Server) require omitting the "recursive"
-- and some (e.g. SQLite) don't bother, i.e. they accept both
-- drop view v_group_descendant;
create view v_group_descendant as
with recursive descendants -- name for accumulating table
(parent_id, descendant_id, lvl) -- output columns
as
( select parent_id, child_id, 1
from group_group -- starting point, we start with each base group
union all
select d.parent_id, s.child_id, d.lvl + 1
from descendants d -- get the n-1 th level of descendants/ children
join group_group s -- and join it to find the nth level
on d.descendant_id = s.parent_id -- the trick is that the output of this query becomes the input
-- Im not sure when it stops but probably when there is no change
)
select * from descendants;
comment on view v_group_descendant is 'This aggregates the children of each group RECURSIVELY WOO ALL THE WAY DOWN THE TREE :)';
после того, как у нас будет это представление, мы можем присоединиться к нашим узлам/группам, чтобы вернуть данные. Я не буду предоставлять эти образцы для каждого шага, по большей части мы будем просто работать с идентификаторами.
select d.*, g1.group_name as parent, g2.group_name as decendent --then we join it with groups to add names
from v_group_descendant d, groups g1, groups g2
WHERE g1.id = d.parent_id and g2.id = d.descendant_id
order by parent_id, lvl, descendant_id;
образец вывода
+------------------------------------+------------------------------------+---+----------+---------+
|parent_id |descendant_id |lvl|parent |decendent|
+------------------------------------+------------------------------------+---+----------+---------+
|3ef7050f-2f90-444a-a20d-c5cbac91c978|6c758087-a158-43ff-92d6-9f922699f319|1 |bravo |charly |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|3ef7050f-2f90-444a-a20d-c5cbac91c978|1 |alpha |bravo |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|7135b0c6-d59c-4c27-9617-ddcf3bc79419|1 |alpha |berry |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|6c758087-a158-43ff-92d6-9f922699f319|2 |alpha |charly |
|42529e8a-75b0-4242-a51a-ac60a0e48868|44758087-a158-43ff-92d6-9f922699f319|1 |yank |zeta |
+------------------------------------+------------------------------------+---+----------+---------+
Обратите внимание, что это всего лишь минимальное отношение потомка узла, и фактически потеряны все узлы с 0 дочерними элементами, такими как charly.
Чтобы решить эту проблему, нам нужно добавить обратно все узлы, которых нет в списке потомков.
create view v_group_descendant_all as (
select * from v_group_descendant gd
UNION ALL
select null::uuid as parent_id,id as descendant_id, 0 as lvl from groups g
where not exists (select * from v_group_descendant gd where gd.descendant_id = g.id )
);
comment on view v_group_descendant is 'complete list of descendants including rank 0 root nodes descendant - parent relationship is duplicated for all levels / ranks';
preview
+------------------------------------+------------------------------------+---+----------+---------+
|parent_id |descendant_id |lvl|parent |decendent|
+------------------------------------+------------------------------------+---+----------+---------+
|3ef7050f-2f90-444a-a20d-c5cbac91c978|6c758087-a158-43ff-92d6-9f922699f319|1 |bravo |charly |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|3ef7050f-2f90-444a-a20d-c5cbac91c978|1 |alpha |bravo |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|7135b0c6-d59c-4c27-9617-ddcf3bc79419|1 |alpha |berry |
|c1529e8a-75b0-4242-a51a-ac60a0e48868|6c758087-a158-43ff-92d6-9f922699f319|2 |alpha |charly |
|42529e8a-75b0-4242-a51a-ac60a0e48868|44758087-a158-43ff-92d6-9f922699f319|1 |yank |zeta |
|null |c1529e8a-75b0-4242-a51a-ac60a0e48868|0 |null |alpha |
|null |42529e8a-75b0-4242-a51a-ac60a0e48868|0 |null |yank |
+------------------------------------+------------------------------------+---+----------+---------+
Допустим, например, мы получаем наш набор s групп на основе
users(id , data)стол с
user_group(user_id, group_id)связь
Затем мы можем соединить это с другой таблицей, удалив дубликаты, потому что наш набор
sотношений user_group может привести к дублированию, если пользователи, скажем, назначены как альфа-назначенным charly
+------+--------+
| user | group |
+------+--------+
| jane | alpha |
| jane | charly |
| kier | yank |
| kier | bravo |
+------+--------+
--drop view v_user_group_recursive;
CREATE VIEW v_user_group_recursive AS (
SELECT DISTINCT dd.descendant_id AS group_id, ug.user_id
FROM v_group_descendant_all dd , user_group ug
WHERE (ug.group_id = dd.descendant_id
OR ug.group_id = dd.parent_id) -- should gic
);
SELECT * FROM v_user_group_recursive;
+------+--------+
| user | group |
+------+--------+
| jane | alpha |
| jane | bravo |
| jane | berry |
| jane | charly |
-- | jane | charly | Removed by DISTINCT
| kier | yank |
| kier | zeta |
| kier | bravo |
| kier | charly |
+------+--------+
Если мы хотим, мы можем теперь сгруппировать по узлу и присоединиться, мы можем сделать что-то вроде следующего
CREATE VIEW v_user_groups_recursive AS (
SELECT user_id, json_agg(json_build_object('id', id,'parent_id',parent_id, 'group_name', group_name, 'org_id', org_id, 'json', json, 'remarks', remarks)) as groups
FROM v_user_group_recursive ug, v_groups_parent g
WHERE ug.group_id = g.id GROUP BY user_id
);
comment on view v_user_group_recursive is 'This aggregates the groups for each user recursively ';
+------+-------------------------------+
| user | groups |
+------+-------------------------------+
| jane | [alpha, bravo, berry, charly] |
| kier | [yank, zeta, bravo, charly] |
+------+-------------------------------+
Это потрясающе, мы ответили на вопрос. Теперь мы можем просто спросить, какие группы наследует это использование.
SELECT * from v_user_groups_recursive where user_id = 'kier
Отображение нашей тяжелой работы в интерфейсе
Кроме того, мы могли бы использовать что-то вроде jstree.com для отображения нашей структуры.
async function getProjectTree(user_id) {
let res = await table.query(format('SELECT * from v_user_groups_recursive ug WHERE ug.user_id = %L', user_id));
if (res.success) {
let rows = res.data[0].groups.map(r => {
return {
id: r.id, // required
parent: r.parent_id==null?'#':r.parent_id,// required
text: r.group_name,// node text
icon: 'P', // string for custom
state: {
opened: true, // is the node open
disabled: false, // is the node disabled
selected: false, // is the node selected
},
li_attr: {}, // attributes for the generated LI node
a_attr: {} // attributes for the generated A node
}
})
return {success: true, data: rows, msg: 'Got all projects'}
} else return res;
}
<div id="v_project_tree" class="row col-10 mx-auto" style="height: 25vh"></div>
<script>
function buildTree() {
bs.sendJson('get', "/api/projects/getProjectTree").then(res => {
bs.resNotify(res);
if (!res.success) {
//:(
console.error(':(');
return
}
console.log(res.data);
$('#v_project_tree').jstree({
'core': {
'data': res.data
}
});
})
}
window.addEventListener('load', buildTree);
</script>
Я думаю, что лучший способ - дать каждому узлу идентификатор и parent_id, где родительский идентификатор - это идентификатор родительского узла. Это имеет несколько преимуществ
- Когда вы хотите обновить узел, вам нужно только переписать данные этого узла.
- Когда вы хотите сделать запрос только к определенному узлу, вы можете получить именно ту информацию, которую вы хотите, таким образом, имея меньшую нагрузку на соединение с базой данных
- Многие языки программирования имеют функции для преобразования данных mysql в XML или json, что облегчит открытие приложения с помощью API.
Что-то вроде таблицы "узлов", где каждая строка узла содержит родительский идентификатор (в дополнение к обычным данным узла). Для root родитель является NULL.
Конечно, это делает поиск детей немного более трудоемким, но в этом случае фактическая база данных будет довольно простой.