Достичь иерархии, Отношения между родителями и детьми эффективным и простым способом

У меня есть стол как

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100)
);

Значение полей:

site_Id : Id of the sites parent_Id : Parent id of the site site_desc : though not relevant to the question but it has the description of the site

Требование заключается в том, что если у меня есть site_id в качестве входных данных, и мне нужны все идентификаторы, помеченные под сайтом. Например:

                    A
                   / \
                  B   C
                / | \ /\
               D  E F G H
              /\
             I  J

Все узлы являются site_Id.

Таблица содержит такие данные:

Site_id  | Parent_ID  |  site_desc
_________|____________|___________
 A       |   -1       |   
 B       |    A       |
 C       |    A       |
 D       |    B       |
 E       |    B       |
 F       |    B       |
 I       |    D       |
 J       |    D       |

......

A является родителем B и C и так далее.

Если B является входным данным, то запрос должен выбрать D, E, I, F, J

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

Что я сейчас делаю:

голосование против

Алгоритм выглядит так:

Initially create a data set object which you will populate, by fetching data from the data base. 
Create a method which takes the parent id as parameter and returns its child nodes if present, and returns -1, if it doesnt have a child. 
Step1: Fetch all the rows, which doesn't have a parent(root) node. 
Step2: Iterate through this result. For example if prod1 and prod2 are the initial returned nodes, in the resultset. 
Iterating this RS we get prod1, and we insert a row in our DataSET obj. 
Then we send the id of prod1 to getCHILD method, to get its child, and then again we iterate the returned resultset, and again call the getCHILD method, till we dont get the lowest node.

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

 Sean16 июн. 2012 г., 18:32
В целом, древовидные модели являются "сложными" в SQL, но не невозможно. В зависимости от размера вашего дерева, если вы выполняете эти запросы во время выполнения, это может бытьvery медленный. В прошлом я предварительно помечал вещи на вкладке или в течение ночи.
 a_horse_with_no_name13 июл. 2012 г., 11:57
Поскольку MySQL не поддерживает рекурсивные запросы, вам будет сложно работать с этим дизайном. Вам следует подумать об изменении своей модели данных, используя вложенные наборы или таблицу закрытий (найдите эти термины, и вы найдете много информации о них)
 siride16 июн. 2012 г., 18:06
@ T-ShirtDude OP означает все дочерние (или дочерние) сайты для данного сайта.
 Sashi Kant13 июл. 2012 г., 12:03
@a_horse_with_no_name: я могу это понять, но изменение модели данных со мной невозможно, так как это упоминалось во многих командах разработчиков в моем проекте, и есть 500 случаев, когда эта таблица рецензируется, я прошу только лучшая техника для получения результатов
 hjpotter9216 июн. 2012 г., 17:56
не могу понять вопрос об "идентификаторах, помеченных под сайтом"

Ответы на вопрос(10)

если вы хотите сделать это в отдельных запросах:http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

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

 05 авг. 2012 г., 02:35
Посмотрите отличное слайд-шоу Билла Карвина:Models for hierarchical data
 16 июн. 2012 г., 18:39
@SashiKant Я не уверен, что ты имеешь в виду. Если вы спрашиваете, поддерживает ли MySQL связывание таблиц, то ответ, скорее всего, «да», поскольку связывание таблиц или любой другой структуры таблиц зависит от вас. Пожалуйста, прочитайте ссылку, которую я также предоставил.
 Sashi Kant16 июн. 2012 г., 18:22
MySQL поддерживает запрос связывания?
 05 авг. 2012 г., 02:20
@siride: просто к вашему сведению, ваша "другая альтернатива" называетсяclosure Таблица.

Вот моя реализация в MySQL

DROP PROCEDURE IF EXISTS SearchTree;
DELIMITER go

CREATE PROCEDURE SearchTree( IN root CHAR(1) )
BEGIN
  DECLARE rows SMALLINT DEFAULT 0;
  DROP TABLE IF EXISTS reached;
  CREATE TABLE reached (
    site_Id CHAR(1) PRIMARY KEY
  ) ENGINE=HEAP;
  INSERT INTO reached VALUES (root);
  SET rows = ROW_COUNT();
  WHILE rows > 0 DO
    INSERT IGNORE INTO reached 
      SELECT DISTINCT s.site_Id 
      FROM site AS s 
      INNER JOIN reached AS r ON s.parent_Id = r.site_Id;
    SET rows = ROW_COUNT();
    DELETE FROM reached 
      WHERE site_Id = root;
  END WHILE;
  SELECT * FROM reached;
  DROP TABLE reached;
END;
go
DELIMITER ;
CALL SearchTree('B');

Возвращает ожидаемый результат.

 31 янв. 2013 г., 13:58
Пожалуйста, дайте свой отзыв.
 01 февр. 2013 г., 06:49
Могу ли я получить некоторые входные данные по вышеуказанному? Спасибо!
 01 февр. 2013 г., 11:31
Если бы я делал что-то подобное, я бы вызывал хранимую процедуру каждый раз, когда я вставлял новый узел или делал какие-либо обновления, и имел бы вторичную таблицу, в которой я сохранял бы значения хранимых процедур для всех узлов дерева.
 Sashi Kant01 февр. 2013 г., 11:13
Jaspal, Большое спасибо за ваш ответ ... Это действительно полезно, ваша реализация включает в себя создание временной таблицы на лету, что, я думаю, это может быть накладными расходами. Во-вторых, как я уже упоминал, я работаю с логикой иерархии в коде приложения, который выполняет запрос множественного выбора.

closure table шаблон. я нашел этосайт познавательный. Насколько я видел, есть также несколько вопросов StackOverflow об этой концепции, например,Вот.

ответил этотвопрос которая в точности связана с вашей проблемой, которую вы описали:Out of a given adjacency list, you want to get all child nodes of a particular parent - и, возможно, в одномерном массиве, который вы можете легко перебрать.

Вы можете сделать это, используя только один вызов базы данных, но есть своего рода ловушка: вы должны вернутьсяall строки из таблицы. MySQL не поддерживает рекурсивные запросы, поэтому вместо этого вам необходимо выполнитьSELECTв коде приложения.

Я просто повторю свой ответ, на который я ссылался выше, но в основном, если вы возвращаете набор результатов (возможно, изPDOStatement->fetchAll(PDO::FETCH_ASSOC) или другие методы) в формате что-то вроде:

Array
(
    [0] => Array
    (
        [site_id] => A
        [parent_id] => -1
        [site_desc] => testtext
    )
    [1] => Array
    (
        [site_id] => B
        [parent_id] => A
        [site_desc] => testtext
    )
    [2] => Array
    (
        [site_id] => C
        [parent_id] => A
        [site_desc] => testtext
    )
    [3] => Array
    (
        [site_id] => D
        [parent_id] => B
        [site_desc] => testtext
    )
    [4] => Array
    (
        [site_id] => E
        [parent_id] => B
        [site_desc] => testtext
    )
    [5] => Array
    (
        [site_id] => F
        [parent_id] => B
        [site_desc] => testtext
    )
    [6] => Array
    (
        [site_id] => I
        [parent_id] => D
        [site_desc] => testtext
    )
    [7] => Array
    (
        [site_id] => J
        [parent_id] => D
        [site_desc] => testtext
    )
)

Вы можете восстановить всех детей / внуков / правнуков / детей любогоsite_id (если вы знаете идентификатор) с помощью этой рекурсивной функции:

function fetch_recursive($src_arr, $id, $parentfound = false, $cats = array())
{
    foreach($src_arr as $row)
    {
        if((!$parentfound && $row['site_id'] == $id) || $row['parent_id'] == $id)
        {
            $rowdata = array();
            foreach($row as $k => $v)
                $rowdata[$k] = $v;
            $cats[] = $rowdata;
            if($row['parent_id'] == $id)
                $cats = array_merge($cats, fetch_recursive($src_arr, $row['site_id'], true));
        }
    }
    return $cats;
}

Например, скажем, вы хотели получить всех детейsite_id D, вы бы использовали функцию так:

$nodelist = fetch_recursive($pdostmt->fetchAll(PDO::FETCH_ASSOC), 'D');
print_r($nodelist);

Будет ли вывод:

[0] => Array
(
    [site_id] => D
    [parent_id] => B
    [site_desc] => testtext
)
[1] => Array
(
    [site_id] => I
    [parent_id] => D
    [site_desc] => testtext
)
[2] => Array
(
    [site_id] => J
    [parent_id] => D
    [site_desc] => testtext
)

Обратите внимание, что мы сохраняем информацию о родителе, вместе с его детьми, внуками и т. Д. (Как бы глубоко ни проходило вложение).

 01 февр. 2013 г., 23:00
Или вы можете написать простой запрос, который объединяет всю эту логику ... Но только если есть ограничение на глубину дерева.

Closure Table, Если вы хотите узнать больше об этом, вы можете найтиSQL Антипаттерны Книга довольно интересная.

Это сказал. На мой взгляд, самый простой способ создать такую структуру:http://jsbin.com/omexix/3/edit#javascript

Надеюсь, у вас нет проблем с чтением кода JavaScript. Я использовал его, потому что создание неклассифицированных объектов в JavaScript не выглядит таким хакерским. Можно реализовать то же самое, не опираясь на объект (или ссылки), используя многомерный массив, но это выглядит несколько запутанным.

Вот что делает алгоритм:

we loop through the list of nodes, once if node's parent does not exits, placeholder is created in the array if node has no parent, it is place in list of root nodes if node has no placeholder in array, the placeholder is created values from node are assigned to placeholder node is registered to the parent, if it has a parent

Это об этом. По сути, вы генерируете два списка: со всеми узлами и только с корневым узлом.

как рекурсивно запрашивать отношения, и мой мозг создал это решение (:

SELECT * FROM
(
    SELECT t2.* FROM table t1, table t2 where t2.parent = t1.id OR t2.parent 0 GROUP BY t2.id, t2.parent
) as all_relations
WHERE all_relations.parent >= '_the_id_'

# if you dont want a subtree use only the inner select

Я не уверен на 100%, но я думаю, что если идентификатор автоматически увеличивается, и у ребенка никогда не будет меньшего идентификатора, чем у его родителя (это должно быть нормальным случаем), тогда это может быть решением?

site В таблице часто можно использовать следующую стратегию:

create table site
(
site_Id int(5),
parent_Id int(5),
site_desc varchar2(100),
parents_path varchar(X)
);

parents_path равно пути к выбранному узлу от корня. Например, для листаJ так должно быть|A|B|D|.

Плюсы: - вам понадобится один запрос, чтобы получить результат;

Минусы: - больше запросов во время обновлений (но вы можете делать обновления с умом);

Надеюсь, поможет

 14 июл. 2012 г., 21:27
select * from site where instr(parents_path, concat('|', your_param, '|') > 0, Этот запрос вернет все строки с "B" то есть все дочерние строки "B";
 Sashi Kant14 июл. 2012 г., 20:20
как я могу достичь цели с этим, пожалуйста, напишите пример запроса
Решение Вопроса

если вы не можете изменить модель данных и используете MySQL, вы застряли в ситуации, когда вам нужны рекурсивные запросы, и вы используете СУБД, которая не поддерживает рекурсивные запросы.

Quassnoi написал интересную серию статей в блогах, в которых были показаны методы запроса иерархических данных. Его решения довольно умны, но очень сложны. http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

PostgreSQL - это еще одна СУБД с открытым исходным кодом, котораяподдержка рекурсивных запросовТаким образом, вы можете получить целое дерево, хранящееся в том виде, как вы показываете. Но если вы не можете изменить модель данных, я предполагаю, что вы не можете переключиться на другую RDBMS.

Существует несколько альтернативных моделей данных, которые значительно упрощают выборку деревьев произвольной глубины:

Closure Table Nested Sets aka Modified Preorder Tree Traversal Path Enumeration aka Materialized Path

Я расскажу об этом в своей презентацииМодели для иерархических данных с SQL и PHPи в моей книгеАнтипаттерны SQL: предотвращение ошибок в программировании баз данных.

Наконец, еще одно решение, которое я видел, использовалось в коде дляSlashdotдля их иерархии комментариев: они хранят & quot; parent_id & quot; как в Списке Смежности, но они также хранят & quot; root_id & quot; колонка. Каждый член данного дерева имеет одинаковое значение для root_id, который является наивысшим узлом-предком в своем дереве. Тогда легко получить целое дерево в одном запросе:

SELECT * FROM site WHERE root_id = 123;

Затем ваше приложение извлекает все узлы обратно из базы данных в массив, и вы должны написать код для цикла по этому массиву, вставив узлы в древовидную структуру данных в памяти. Это хорошее решение, если у вас много отдельных деревьев, а в каждом дереве относительно мало записей. Это хорошо для случая Slashdot.

я предполагаю, что вы не хотите менять существующую модель данных, потому что сотни приложений используют ее (и сломается, если вы замените ее чем-то другим).

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

Если вы можете избежать ограничения глубины / уровня вложенности сайтов, вы можете написать один замечательный запрос, который сделает всю работу за вас и, вероятно, даже не настолько медленный для загрузки. Большинство накладных расходов при запросах запуска возникает из-за настройки соединения, пропускной способности сети и т. Д. MySQL может быть очень быстрым.

Запуск нескольких запросов умножает все накладные расходы, поэтому мы этого не хотим. Выполнение SELECT * и последующие вычисления в логике приложения означают, что вы будете извлекать все данные каждый раз, максимально увеличивая нагрузку на сеть, поэтому мы этого не хотим.

Если допустимый предел глубины дерева приемлем, вы можете объединить несколько запросов в один огромный запрос, который выполняет всю работу и возвращает точный набор результатов, который вам нужен. В качестве примера я использовал ваши данные, но с A, B, C и т. Д. Заменил на 1, 2, 3 (так как ваши столбцы int).

Чтобы получить всех прямых потомков корневого узла (с site_id = 1), сделайте это:

select site_id from site where parent_id = 1

Чтобы получить внуков корневого узла, сделайте это:

select grandchild.site_id 
from site grandchild, site child 
where grandchild.parent_id = child.site_id 
and child.parent_id = 1

Чтобы получить правнуков корневого узла, сделайте это:

select greatgrandchild.site_id 
from site greatgrandchild, site grandchild, site child 
where greatgrandchild.parent_id = grandchild.site_id 
and grandchild.parent_id = child.site_id 
and child.parent_id = 1

Чтобы получить всех потомков корневого узла, просто объедините вышеупомянутые запросы в один огромный запрос, например так:

select site_id
from site
where site_id in (
    select site_id 
    from site 
    where parent_id = 1
)
or site_id in (
    select grandchild.site_id 
    from site grandchild, site child 
    where grandchild.parent_id = child.site_id 
    and child.parent_id = 1
)
or site_id in (
    select greatgrandchild.site_id 
    from site greatgrandchild, site grandchild, site child 
    where greatgrandchild.parent_id = grandchild.site_id 
    and grandchild.parent_id = child.site_id 
    and child.parent_id = 1
)

Я думаю, вы видите, как это работает. Для каждого дополнительного уровня создайте запрос, который находит узлы, которые находятся на таком же расстоянии от сайта, для которого вы ищите потомков, и добавьте этот запрос в супер-запрос с дополнительным 'или site_id in () "...

Теперь, как вы видите, только для трех уровней это уже становится большим запросом. Если вам нужно поддерживать, скажем, 10 уровней, этот запрос станет огромным, и все операции OR и IN в нем замедлят его ... Однако он все равно будет быстрее, чем просто получение всего или использование нескольких запросы. Если вам нужно поддерживать произвольное количество возможных уровней, этот запрос не может вам помочь. Это должно было бы стать бесконечно большим. В этом случае все, что остается, это использовать лучший способ ...

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

A BETTER WAY

Добавьте дополнительный столбец parent_paths, используя что-то вроде ravnur, упомянутое в его ответе, для кодирования полного пути от каждого узла до корня

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

Используйте короткий и приятный запрос, подобный тому, который показал ravnur, который ищет вхождение site_id в любом месте столбца parent_paths, чтобы напрямую получитьall потомки сайта с этим site_id без какой-либо рекурсии.

 01 февр. 2013 г., 23:06
Примечание: я понимаю, что запросы в моем посте могут быть оптимизированы с помощью объединений и т. Д., Но лично я нахожу синтаксис, который я использовал здесь, наиболее понятным для пояснения. Если вы реализуете это, прочитайте о соединениях и перепишите запросы, чтобы использовать их вместо этого; вероятно, это повысит производительность, поскольку MySQL сможет лучше использовать индексы.

как сделать это с небольшими изменениями в таблице. состав.

Если вы не хотите изменять структуру (даже если это будет лучше), тогда вы можете сделать как это:

SELECT * FROM site ORDER BY Parent_ID, Site_id;

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

Итак, это гипотезы:

- we prefer not to change the table layout
- we never change the IDs once assigned
- we never reorder the tree, moving IDs around

Поэтому становится возможным создать дерево в памяти (и даже уменьшить запрос сам добавляя WHERE Site_ID & gt; = B).

Первый пройденный узел будет B и будет помещен в дерево.

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

В Python это будет очень хорошо (вы напрямую модифицируете родительский узел).

Запрос & quot; Получить всех потомков B & quot; можно ответить в PHP, как это:

$nodes  = array( $parent_id );

$cursor = SQLQuery("SELECT * FROM site WHERE Site_ID > ? "
        .  "ORDER BY Parent_ID, Site_Id ;", $parent_id);

while ($tuple = SQLFetchTuple($cursor))
    if (in_array($tuple['Parent_ID'], $nodes))
        $nodes[] = $tuple['Site_Id'];
SQLFree($cursor);

// The first node is the global parent, and may be array_shift'ed away
    // if desired.

Another way
quite brute force

Другая возможность заключается в том, чтобы сохранить & quot; downndant_of & quot; отношение рекурсивно в другом Таблица:

    TRUNCATE descendants;
    INSERT INTO descendants ( node, of ) VALUES ( -1, NULL );

    INSERT INTO descendants SELECT SiteId, ParentId FROM site JOIN
           descendants ON ( site.ParentId = descendants.of );

И повторяйте INSERT, пока количество вставленных строк не станет равным нулю (или общее количество ряды у потомков перестают увеличиваться; запрос размера таблицы в большинстве БД выполняется очень быстро).

На этом этапе вы сохраните все одноуровневые отношения. Сейчас:

INSERT IGNORE INTO descendants SELECT s1.node, s2.of FROM
           descendants AS s1 JOIN descendants AS s2 ON (s1.of = s2.node);

... снова, пока потомки не перестанут расти (для этого потребуется количество вставок, равное максимальное количество уровней). Общее количество СОЕДИНЕНИЙ будет вдвое больше количества уровней.

Теперь, если вы хотите получить всех потомков узла 16, вы просто запросите

SELECT node FROM descendants WHERE of = 16;

Ваш ответ на вопрос