Tuesday, August 18, 2009

Рекурсия в SQL-запросах

С помощью SQL запросов можно творить чудеса! :) И как оказалось среди этих чудес есть рекурсия. В данном посте я хочу рассказать, как реализовать обход дерева с помощью SQL-запроса.

Первым делом создадим таблицу, с которой будем далее работать:
CREATE TABLE "tree" (
  "id" INTEGER DEFAULT NEXTVAL('"tree_id_seq"'::TEXT) NOT NULL,
  "parent_id" INTEGER ,
  "name" VARCHAR(255) NOT NULL,
  
  PRIMARY KEY ("id"),
  FOREIGN KEY ("parent_id") REFERENCES "tree" ("id") ON DELETE CASCADE,
  UNIQUE( "name" )
);


* This source code was highlighted with Source Code Highlighter.

и добавим в неё данные:
INSERT INTO "tree" ("parent_id", "name") VALUES (NULL, 'root');
INSERT INTO "tree" ("parent_id", "name") VALUES (1, 'A');
INSERT INTO "tree" ("parent_id", "name") VALUES (1, 'B');
INSERT INTO "tree" ("parent_id", "name") VALUES (2, 'AA');
INSERT INTO "tree" ("parent_id", "name") VALUES (2, 'AB');
INSERT INTO "tree" ("parent_id", "name") VALUES (3, 'BA');
INSERT INTO "tree" ("parent_id", "name") VALUES (3, 'BB');


* This source code was highlighted with Source Code Highlighter.

Теперь для обхода полученного дерева нам достаточно выполнить следующий запрос:
-- Временная таблица для получения потомков
WITH RECURSIVE child( node_id ) AS
(
  -- Начальная выборка (элемент, с которого начинается выборка)
  VALUES( 1 )
  
    UNION ALL

  -- Рекурсивная выборка
  SELECT
    t."id"   AS "node_id"
  FROM
    "child" c
  JOIN
    "tree" t ON ( c."node_id" = t."parent_id" )
  WHERE
    t."parent_id" = node_id
)

-- Получение потомков
SELECT "node_id" FROM "child"


* This source code was highlighted with Source Code Highlighter.

Результатом работы запроса будут следующие данные:
  name_id
  1
  2
  3
  4
  5
  6
  7

3 comments:

  1. А для какой это СУБД?

    ReplyDelete
  2. Для PostgreSQL. Если я не ошибаюсь, конструкция "WITH RECURSIVE" не является частью стандарта ANSI SQL, поэтому для каждой СУБД реализация будет особенной. Так например в MySQL начиная с 5-ой версии можно реализовать подобную рекурсию с помощью хранимых процедур (http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html).

    ReplyDelete
  3. В Oracle интуитивней синтаксис START WITH ... CONNECT BY

    ReplyDelete