У меня есть таблица, подобная
create table site ( site_Id int(5), parent_Id int(5), site_desc varchar2(100) ); Значение полей:
Требование состоит в том, что если у меня есть site_id как вход, и мне нужны все идентификаторы, помеченные под сайтом. Например:
A / \ BC / | \ /\ DEFGH /\ IJ
Все узлы – 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.
Мне нужна оптимальная оптимизированная техника в рамках ограничения моей модели данных. Не стесняйтесь отвечать, если у вас есть какие-либо предложения.
Пожалуйста, предложите что-нибудь. Заранее спасибо.
К сожалению, если вы не можете изменить модель данных и используете MySQL, вы застряли в ситуации, когда вам нужны рекурсивные запросы, и вы используете СУБД, которая не поддерживает рекурсивные запросы.
Quassnoi написал интересную серию статей в блогах, демонстрируя методы запроса иерархических данных. Его решения довольно умны, но очень сложны. http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/
PostgreSQL – это другая RDBMS с открытым исходным кодом, которая поддерживает рекурсивные запросы , поэтому вы можете получить целые деревья, хранящиеся в том виде, в котором вы показываете. Но если вы не можете изменить модель данных, я бы предположил, что вы не можете переключиться на другую СУБД.
Существует несколько альтернативных моделей данных, которые значительно облегчают выборку произвольных глубинных деревьев:
Я рассказываю об этом в своей статье « Модели для иерархических данных с SQL и PHP» , а также в моей книге « Антипаттеры SQL: устранение ошибок программирования баз данных» .
Наконец, есть другое решение, которое я видел в коде для Slashdot , для своих иерархий комментариев: они хранят «parent_id», как в Adjacency List, но также хранят столбец «root_id». Каждый член данного дерева имеет такое же значение для root_id, которое является наивысшим предком в своем дереве. Тогда легко получить целое дерево в одном запросе:
SELECT * FROM site WHERE root_id = 123;
Затем ваше приложение извлекает все узлы из базы данных в массив, и вам нужно написать код для цикла над этим массивом, вставив узлы в структуру данных дерева в памяти. Это хорошее решение, если у вас много отдельных деревьев, и каждое дерево имеет относительно немного записей. Это хорошо для дела Слэшдота.
Вчера я ответил на этот вопрос, который точно связан с вашей проблемой, которую вы описали: из данного списка смежности вы хотите получить все дочерние узлы определенного родителя – и, возможно, в одномерном массиве, который вы можете легко перебирать.
Вы можете сделать это, используя только один вызов в базе данных, но есть какой-то улов: вы должны вернуть все строки из таблицы. MySQL не поддерживает рекурсивные запросы, поэтому вместо этого вы должны сделать SELECT IN в коде приложения.
Я просто повторю свой ответ, который я связал выше, но в основном, если вы PDOStatement->fetchAll(PDO::FETCH_ASSOC) набор (возможно, из 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 )
Обратите внимание, что мы сохраняем информацию родителя вместе со своими детьми, внуками и т. Д. (Как бы глубока ни была вложенность).
Проверьте модель вложенного набора, если вы хотите иметь возможность сделать это в одном запросе: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/
Другой альтернативой является включение всех связей в таблицу ссылок. Таким образом, каждый сайт будет иметь ссылку на своего родителя, его дедушку и бабушку и т. Д. Все отношения явны. Затем вы просто запрашиваете эту таблицу связей, чтобы получить всех потомков.
Во-первых, я бы порекомендовал немного другой метод хранения дерева: Closure Table . Если вы хотите узнать больше об этом, вы можете найти книгу SQL Antipatterns довольно интересной.
Тем не менее. Самый простой способ, на мой взгляд, создать такую структуру: http://jsbin.com/omexix/3/edit#javascript
Надеюсь, у вас нет проблем с чтением кода JavaScript. Я использовал его, потому что создание неклассифицированных объектов в JavaScript не выглядит таким хакером. Можно реализовать то же самое без ретрансляции на объекте (или ссылках) с помощью многомерного массива, но это выглядит странно.
Вот что делает алгоритм:
Это об этом. В основном вы создаете два списка: со всеми узлами и только с корневым узлом.
Возможно, вам стоит взглянуть на шаблон таблицы закрытия . Я нашел этот сайт информативным. Насколько я видел, есть также несколько вопросов StackOverflow об этой концепции, например, здесь .
Если вы не обновляете таблицу своего 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| ,
Плюсы: – для получения результата вам понадобится один запрос;
Минусы: – больше запросов во время обновлений (но вы можете делать обновления с умом);
Надеюсь, поможет
Другие уже предложили, как это сделать, с небольшими изменениями в структуре таблицы.
Если вы не хотите изменять структуру (даже если это было бы лучше), вы можете сделать следующее:
Обычно можно с уверенностью предположить, что после присвоения идентификаторы не изменяются; если идентификаторы не перетасовываются, т. е. узел 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> = B).
Первый узел, который пройдет, будет B и будет помещен в дерево.
Все последующие узлы могут храниться в их Parent_ID -м узле, который, безусловно, был загружен ранее.
Это было бы неплохо в Python (вы напрямую изменяете родительский узел).
На запрос «Получить всех потомков B» можно ответить на 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.
Другой путь
довольно грубая сила
Другая возможность заключается в том, чтобы рекурсивно сохранять отношение «descendant_of» в другой таблице:
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;
Для этого вы можете создать хранимую процедуру.
Вот моя реализация в 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');
Он возвращает ожидаемый результат.
Основываясь на ваших комментариях, я предполагаю, что вы не хотите менять существующую модель данных, потому что сотни приложений используют ее (и будут разорваны, если вы замените ее чем-то другим).
Корень проблемы заключается в том, что для любого сайта мы знаем только, что это прямой родитель, поэтому нам нужно искать родительский элемент этого родителя рекурсивно, пока мы не найдем корневой сайт.
Если вы можете уйти с пределом глубины / уровня, на который могут быть вложены сайты, вы можете написать один большой запрос, который сделает всю работу за вас, и, вероятно, даже не так медленно загружается. Большинство накладных расходов от запросов на запуск исходит от настройки соединения, пропускной способности сети и т. Д. 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 в нем замедлят его … Тем не менее, он по-прежнему будет быстрее, чем просто получить все или использовать несколько запросов. Если вам нужно поддерживать произвольное количество возможных уровней, то этот запрос не сможет вам помочь. Он должен был бы стать бесконечно большим. В этом случае все, что остается, – это использовать лучший способ …
Тем не менее, перед тем, как вы скопируете это вставить и начнете кодирование, существует способ избежать таких огромных запросов, поддерживающих произвольные глубины и не нарушая обратной совместимости. Это требует изменения модели данных, но она небольшая, что не повредит другим программам, использующим эту модель данных. Короче …
ЛУЧШИЙ ПУТЬ
Добавьте дополнительные столбцы parent_paths, используя что-то вроде ravnur, упомянутое в его ответе, чтобы закодировать полный путь от каждого узла до корня
Заполните этот столбец динамически, используя триггеры для вставки, обновления и удаления. Теперь вы сохраняете избыточные данные. Это не повредит другим программам, но может принести вам значительную выгоду. Убедитесь, что триггеры являются пуленепробиваемыми (возможно, это самая сложная часть), поскольку данные в дополнительном столбце должны всегда синхронизироваться с обычными данными в таблице
Используйте короткий и сладкий запрос, подобный показанному ravnur, который ищет возможность возникновения site_id в любом месте в столбце parent_paths, чтобы напрямую получить всех потомков сайта с этим site_id без какой-либо рекурсии.
я также спрашивал себя, как рекурсивно запрашивать отношения, и мой мозг создал это решение (:
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%, но я думаю, что до тех пор, пока идентификатор автоматически увеличивается, а у ребенка никогда не будет меньшего id в качестве родителя (это должен быть нормальный случай), тогда это может быть решением?