PD>А теперь вопрос — как их связать ? Необходимо, чтобы можно было 1) по tree.id получить корень его дерева и 2) имея treeitem.id любого элемента дерева, можно было получить заголовок дерева PD>Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree. Однако это значит, что у всех узлов этого дерева будет храниться этот treeId, что есть дублирование данных. PD>Можно ли его избежать ?
Если это MSSQL — Используйте https://docs.microsoft.com/en-us/sql/t-sql/data-types/hierarchyid-data-type-method-reference?view=sql-server-2017
По нему за одну операцию получите корень дерева, а на него уже можно ссылаться из другой таблицы.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Предки мне вообще не нужны, потомки нужны в другом месте, с ними я разберусь, а сейчас мне нужно лишь по узлу получить заголовок дерева. Я не думаю, что вариант с просмотром восходящего пути к корню (хоть вручную, хоть средствами сервера, если они есть) является наилучшим решением. Просто в силу того, что нечего устраивать проход там, где можно обойтись без него.
Это классический компромисс между памятью (каждый узел хранит ссылку на дерево) и быстродействием (только корень хранит ссылку на дерево). Каждый разрешает его для себя сам. Либо избыточность данных, либо дополнительные вычисления.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Добрый день!
PD>Надо разместить в SQL дерево произвольной арности. PD>Понятно, таблица treeitem и в ней parentId как FK на ее же id PD>Проблема же вот в чем. У дерева должен быть заголовок, содержащий данные, относящиеся к дереву в целом, а не к элементам. Хорошо, еще таблица tree PD>А теперь вопрос — как их связать ? Необходимо, чтобы можно было 1) по tree.id получить корень его дерева и 2) имея treeitem.id любого элемента дерева, можно было получить заголовок дерева
PD>Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree. Однако это значит, что у всех узлов этого дерева будет храниться этот treeId, что есть дублирование данных. PD>Можно ли его избежать ?
видел как то денормализованный вариант
NodeId AncestorId Distance
то есть узел связан со всеми предками,
и можно выбирать потомков/предков (и собственно корень) без рекурсии
Das Reich der Freiheit beginnt da, wo die Arbeit aufhört. (c) Karl Marx
Здравствуйте, Ops, Вы писали: Ops>Это дословный перевод, который ничего не значит. Даже статья в вики какая-то хрень, в отличие от английской. А уж искать информацию по этому словосочетанию — смысла вообще нет.
А вы всё же попробуйте. Например, на этом сайте.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree. Однако это значит, что у всех узлов этого дерева будет храниться этот treeId, что есть дублирование данных. PD>Можно ли его избежать ?
А зачем избегать? Надо делать так, чтобы потом было удобно работать.
Надо разместить в SQL дерево произвольной арности.
Понятно, таблица treeitem и в ней parentId как FK на ее же id
Проблема же вот в чем. У дерева должен быть заголовок, содержащий данные, относящиеся к дереву в целом, а не к элементам. Хорошо, еще таблица tree
А теперь вопрос — как их связать ? Необходимо, чтобы можно было 1) по tree.id получить корень его дерева и 2) имея treeitem.id любого элемента дерева, можно было получить заголовок дерева
Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree. Однако это значит, что у всех узлов этого дерева будет храниться этот treeId, что есть дублирование данных.
Можно ли его избежать ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree. Однако это значит, что у всех узлов этого дерева будет храниться этот treeId, что есть дублирование данных. PD>Можно ли его избежать ?
Еще можно принудительно в каждом дереве держать root treeItem и ссылаться на нее из tree.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree.
А почему не наоборот? Запись из tree ссылается с помощью FK на коренной элемент в treeitem.
Сколько записей в tree, столько и деревьев в базе. Просто же.
PD>Понятно, таблица treeitem и в ней parentId как FK на ее же id
Такая структура позволяет закольцеваться. Имей в виду и закладывай проверки сразу.
Здравствуйте, Mihas, Вы писали:
M>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree. M>А почему не наоборот? Запись из tree ссылается с помощью FK на коренной элемент в treeitem.
А как тогда по любому treeitem.id (не корню) получить его tree ? Устроить восходящий подъем по parentId ?
M>Такая структура позволяет закольцеваться. Имей в виду и закладывай проверки сразу.
Понятно, что позволяет, но не грозит — такого просто не будет.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А как тогда по любому treeitem.id (не корню) получить его tree ? Устроить восходящий подъем по parentId ?
Если скорость не критична, то да. Я бы, кончено, пытался делать это средствами sql, чтобы не тащить вычисление подъема на клиента. Хранимку бы замастрякал или функцию.
Если скорость критична, то я тоже не вижу способов без дублирования. Альтернативой treeitem.treeId я вижу treeitem.treeItemRootId
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Добрый день!
PD>Надо разместить в SQL дерево произвольной арности. PD>Понятно, таблица treeitem и в ней parentId как FK на ее же id PD>Проблема же вот в чем. У дерева должен быть заголовок, содержащий данные, относящиеся к дереву в целом, а не к элементам. Хорошо, еще таблица tree PD>А теперь вопрос — как их связать ? Необходимо, чтобы можно было 1) по tree.id получить корень его дерева и 2) имея treeitem.id любого элемента дерева, можно было получить заголовок дерева
PD>Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree. Однако это значит, что у всех узлов этого дерева будет храниться этот treeId, что есть дублирование данных. PD>Можно ли его избежать ?
Если разрешить клиенту обращаться к узлу только по его полному пути tree_id(title)/id_1/id_2 и т.д., то проблема вообще не возникает, усложняется только клиент.
Здравствуйте, Qulac, Вы писали:
Q>Если разрешить клиенту обращаться к узлу только по его полному пути tree_id(title)/id_1/id_2 и т.д., то проблема вообще не возникает, усложняется только клиент.
Ну в таком случае достаточно передать tree_id и id_item. Этого хватит. Я-то хочу по id_item получить tree_id, и это все, что надо, а узлы выше id_item мне не нужны.
Но требовать от клиента передавать ID самого дерева и узла — это перенос избыточности на клиента. ID узла вообще-то неявно определяет ID самого дерева.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Qulac, Вы писали:
Q>>Если разрешить клиенту обращаться к узлу только по его полному пути tree_id(title)/id_1/id_2 и т.д., то проблема вообще не возникает, усложняется только клиент.
PD>Ну в таком случае достаточно передать tree_id и id_item. Этого хватит. Я-то хочу по id_item получить tree_id, и это все, что надо, а узлы выше id_item мне не нужны. PD>Но требовать от клиента передавать ID самого дерева и узла — это перенос избыточности на клиента.
ID узла вообще-то неявно определяет ID самого дерева.
Это если касаемо дерева в бд, если взять дерево как абстрактную структуру, то узел определяется путем к нему. Id у нас появляется как деталь реализации. Тут у нас либо клиент сложнее либо сервер.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А как тогда по любому treeitem.id (не корню) получить его tree ? Устроить восходящий подъем по parentId ?
Можно сделать view или вспомогательную таблицу с transitive closure, тогда то любому id одним запросом можно будет найти как всех его предков, так и потомков; опционально можно считать расстояние между ними, и, соответственно, выбирать лишь нужный уровень.
Однако мне такая структура только с id и parent_id (adjacent tree) не нравится, хотя она интуитивна и минимальна, но другие модели удобнее с практической точки зрения. Например в постгре есть хорошее расширение ltree, реализующее materialized path
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Здравствуйте, DenisCh, Вы писали:
DC>Есть хорошее русское слово транзитивное замыкание . Оно было бы более уместно на RSDN
Это дословный перевод, который ничего не значит. Даже статья в вики какая-то хрень, в отличие от английской. А уж искать информацию по этому словосочетанию — смысла вообще нет.
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Здравствуйте, Ops, Вы писали:
Ops>Можно сделать view или вспомогательную таблицу с transitive closure, тогда то любому id одним запросом можно будет найти как всех его предков, так и потомков; опционально можно считать расстояние между ними, и, соответственно, выбирать лишь нужный уровень.
Предки мне вообще не нужны, потомки нужны в другом месте, с ними я разберусь, а сейчас мне нужно лишь по узлу получить заголовок дерева. Я не думаю, что вариант с просмотром восходящего пути к корню (хоть вручную, хоть средствами сервера, если они есть) является наилучшим решением. Просто в силу того, что нечего устраивать проход там, где можно обойтись без него.
Здравствуйте, Qulac, Вы писали:
Q>ID узла вообще-то неявно определяет ID самого дерева.
Ну да, вот только с восходящим проходом
Q>Это если касаемо дерева в бд, если взять дерево как абстрактную структуру, то узел определяется путем к нему. Id у нас появляется как деталь реализации. Тут у нас либо клиент сложнее либо сервер.
Если взять абстрактную структуру, то либо
class Tree {
private TreeItem root;
// other tree header fields
}
class TreeItem {
private TreeItem parent;
private List<TreeItem> children;
// TreeItem fields
В этом случае для получения по TreeItem его Tree восходящий проход по parent (aka parentId в БД)
Либо
class Tree {
private TreeItem root;
// other tree header fields
}
class TreeItem {
private TreeItem parent;
private List<TreeItem> children;
private Tree tree;
// TreeItem fields
В этом случае по любому TreeItem его Tree находится за O(1), но все TreeItem одного дерева содержат одну и ту же ссылку tree (aka tree_id в БД)
Здравствуйте, Sinclair, Вы писали:
S>А вы всё же попробуйте. Например, на этом сайте.
А я уже искал когда-то, и как раз там, где имел негативный опыт, пишу английские термины, чтобы другие не мучились. Русские термины — это хорошо, когда они устоявшиеся, и по ним достаточно информации, и я только за, если так станет, но пока имеем что имеем.
Только вот рьяные поборники русских терминов что-то не спешат хотя бы доработать статью в вики.
Переубедить Вас, к сожалению, мне не удастся, поэтому сразу перейду к оскорблениям.
Здравствуйте, Ops, Вы писали:
Ops>А я уже искал когда-то, и как раз там, где имел негативный опыт, пишу английские термины, чтобы другие не мучились. Русские термины — это хорошо, когда они устоявшиеся, и по ним достаточно информации, и я только за, если так станет, но пока имеем что имеем. Ops>Только вот рьяные поборники русских терминов что-то не спешат хотя бы доработать статью в вики.
Во-первых, я не вижу никаких проблем в вики-статье. Там и определение корректное, и примеры понятные.
Во-вторых, вы таки не пробовали искать на rsdn. Иначе бы нашли исчерпывающую дискуссию 11летней давности
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree. Однако это значит, что у всех узлов этого дерева будет храниться этот treeId, что есть дублирование данных. PD>Можно ли его избежать ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Пока вижу только одно решение — в каждом treeitem иметь treeId как FK на tree. Однако это значит, что у всех узлов этого дерева будет храниться этот treeId, что есть дублирование данных. PD>Можно ли его избежать ?
Можно использовать первичный ключ из двух колонок — treeId, nodeId, например:
1,1
1,2
1,3
2,1
2,2
Либо часть разрядов в ID ключа использовать как ID дерева. Например, пусть PK имеет тип int(5), первые 2 разряда будет ID дерева, остальные — ID узла в дереве, т.е.:01
01001
01002
01003
02001
02002
Подобный подход я видел в БД КЛАДР.
Но такие подходы имеют минусы — вместо sequence придётся изобретать свой велосипед, работающий при множественных подключениях к БД, а это сильно усложнит логику твоей системы, увеличит сроки разработки и усложнит поддержку.
Поэтому, думаю, что бы узнать вершину дереву по его листу, лучше будет либо идти по дереву до вершины, либо хранить ID дерева в записи узла. Выбрать приоритет — скорость или отсутствие дублирования информации. Можно хранить вершину дерева не в узле, а в отдельной таблице с колонками treeID, nodeID, но это тоже дублирование информации.
