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

WITH tree_CTE (data, id, level, pathstr)
AS (SELECT NAME, ID, 0, cast(' ' as varchar(MAX))
FROM Tree
WHERE ID_FATHER IS NULL
UNION ALL
SELECT NAME, Tree.ID,
tree_CTE.level+4, tree_CTE .pathstr + ' ' +Tree.NAME
FROM Tree JOIN tree_CTE ON tree_CTE.id = Tree. ID_FATHER
)
SELECT SPACE(level) + data as data, id, level, pathstr
FROM tree_CTE;

Результат
data	id	level	pathstr
ALL	1	0
SEA	2	4	SEA
EARTH	3	4	EARTH
AIR	4	4	AIR
ROCKET	10	8	AIR ROCKET
PLANE	11	8	AIR PLANE
CAR	7	8	EARTH CAR
TWO WHEELES	8	8	EARTH TWO WHEELES
TRUCK	9	8	EARTH TRUCK
MOTORCYCLE	12	12	EARTH TWO WHEELES MOTORCYCLE
BYCYCLE	13	12	EARTH TWO WHEELES BYCYCLE
SUBMARINE	5	8	SEA SUBMARINE
BOAT	6	8	SEA BOAT

Мы использовали новый тип данных в SQL 2005, который называется VARCHAR (MAX), поскольку мы не знаем максимального количества символов, которое потребуется при конкатенации VARCHAR (16) в рекурсивном запросе, который может оказаться очень глубоким.

3. Деревья без рекурсии.

В программировании рекурсию всегда можно избежать, если использовать стек. В нашем случае так же можно обойтись без рекурсии, поместив стек внутрь таблицы. Для этого добавим в таблицу два новых столбца.
ALTER TABLE Tree
ADD RIGHT_BOUND INTEGER
ALTER TABLE Tree
ADD LEFT_BOUND INTEGER
Заполним эти новые столбцы следующими числами:
UPDATE Tree SET LEFT_BOUND = 1 , RIGHT_BOUND = 26 WHERE ID = 1
UPDATE Tree SET LEFT_BOUND = 2 , RIGHT_BOUND = 7 WHERE ID = 2
UPDATE Tree SET LEFT_BOUND = 8 , RIGHT_BOUND = 19 WHERE ID = 3
UPDATE Tree SET LEFT_BOUND = 20, RIGHT_BOUND = 25 WHERE ID = 4
UPDATE Tree SET LEFT_BOUND = 3 , RIGHT_BOUND = 4 WHERE ID = 5
UPDATE Tree SET LEFT_BOUND = 5 , RIGHT_BOUND = 6 WHERE ID = 6
UPDATE Tree SET LEFT_BOUND = 9 , RIGHT_BOUND = 10 WHERE ID = 7
UPDATE Tree SET LEFT_BOUND = 11, RIGHT_BOUND = 16 WHERE ID = 8
UPDATE Tree SET LEFT_BOUND = 17, RIGHT_BOUND = 18 WHERE ID = 9
UPDATE Tree SET LEFT_BOUND = 21, RIGHT_BOUND = 22
WHERE ID = 10
UPDATE Tree SET LEFT_BOUND = 23, RIGHT_BOUND = 24
WHERE ID = 11
UPDATE Tree SET LEFT_BOUND = 12, RIGHT_BOUND = 13
WHERE ID = 12
UPDATE Tree SET LEFT_BOUND = 14, RIGHT_BOUND = 15
WHERE ID = 13
Фактически мы реализовали стек, нумеруя строки данных. Вот поясняющая картинка:

ALL	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
	SEA
		SUBMARINE
		BOAT
	EARTH
		CAR
		TWO WHEELES
			MOTORCYCLE
			BYCYCLE
		TRUCK
	AIR
		ROCKET
		PLANE

Теперь, чтобы получить всех предков МОТОЦИКЛА, мы только берем границы МОТОЦИКЛА (MOTORCYCLE) - слева 12, а справа 13 - и помещаем их в предложение WHERE, выбирая данные, правая граница которых превышает 12, а левая меньше 13.

И вот запрос, дающий тот же самый результат, что и сложный иерархический рекурсивный запрос:
SELECT *
FROM Tree
WHERE RIGHT_BOUND > 12
AND LEFT_BOUND < 13;

Результат
ID	ID_FATHER	NAME	RIGHT_BOUND	LEFT_BOUND
1	NULL	ALL	26	1
3	1	EARTH	19	8
8	3	TWO WHEELES	16	11
12	8	MOTORCYCLE	13	12

Такое представление деревьев хорошо известно в литературе по БД, особенно в трудах Джо Селко ("Деревья и иерархии" и т. д.).

4. Пример использования СТЕ для решения задачи Коммивояжера.

Проблема состоит в том, чтобы проехать на машине от Парижа до Тулузы, используя сеть автострад.

385 420 470

375 335 305 320

240 205

Создадим таблицу и занесем данные:
CREATE TABLE TUR
(FROM_TOWN VARCHAR(32),

FROM_TOWN	TO_TOWN	MILES
PARIS	NANTES	385
PARIS	CLERMONT-FERRAND	420
PARIS	LYON	470
CLERMONT-FERRAND	MONTPELLIER	335
CLERMONT-FERRAND	TOULOUSE	375
LYON	MONTPELLIER	305
LYON	MARSEILLE	320
MONTPELLIER	TOULOUSE	240
MARSEILLE	NICE	205

TO_TOWN VARCHAR(32),
MILES INTEGER);

Возьмем в качестве начала рекурсии “Париж” и построим СТЕ

WITH

Результат
TO-TOWN
PARIS
NANTES
CLERMONT-FERRAND
LYON
MONTPELLIER
MARSEILLE
NICE
TOULOUSE
MONTPELLIER
TOULOUSE
TOULOUSE

TUR_PARIS ([TO-TOWN])
AS
( SELECT DISTINCT FROM_TOWN
FROM TUR
WHER FROM_TOWN= 'PARIS'
UNION ALL
SELECT TO_TOWN
FROM TUR INNER JOIN TUR_PARIS
ON TUR_PARIS.[TO-TOWN] = TUR.FROM_TOWN
)
SELECT * FROM TUR_PARIS;

Как видно из результата запроса, существует три способа добраться до Тулузы. Отфильтруем пункт назначения.

WITH

Результат
TO-TOWN
TOULOUSE
TOULOUSE
TOULOUSE

TUR_PARIS ([TO-TOWN])
AS
( SELECT DISTINCT FROM_TOWN
FROM TUR
WHER FROM_TOWN= 'PARIS'
UNION ALL
SELECT TO_TOWN
FROM TUR INNER JOIN TUR_PARIS
ON TUR_PARIS.[TO-TOWN] = TUR.FROM_TOWN
)
SELECT * FROM TUR_PARIS
WHERE [TO-TOWN] = 'TOULOUSE' ;
Мы можем уточнить этот запрос, подсчитав число шагов по каждому направлению, расстояния по различным направлениям и выведя списки городов, которые можно посетить, двигаясь по этим направлениям:


WITH
TUR_PARIS([TO-TOWN], STEPS, DISTANSE, WAY)
AS
( SELECT DISTINCT FROM_TOWN, 0, 0
,cast('PARIS' as VarChar(MAX))
FROM TUR
WHERE FROM_TOWN= 'PARIS'
UNION ALL
SELECT TO_TOWN, T_P.STEPS+1,
T_P. DISTANSE + T.MILES, T_P.WAY+ ' '+T.TO_TOWN
FROM TUR T INNER JOIN TUR_PARIS T_P
ON T_P.[TO-TOWN] = T.FROM_TOWN
)
SELECT * FROM TUR_PARIS
WHERE [TO-TOWN] = 'TOULOUSE';

Результат
TO-TOWN	STEPS	DISTANSE	WAY
TOULOUSE	3	1015	PARIS LYON MONTPELLIER TOULOUSE
TOULOUSE	2	795	PARIS CLERMONT-FERRAND TOULOUSE
TOULOUSE	3	995	PARIS CLERMONT-FERRAND MONTPELLIER TOULOUSE

Теперь мы сможем написать рекурсивный запрос решение очень сложной задачи, названной задачей коммивояжера (одна из действительных проблем исследования, на которых Edsger Wybe Dijkstra нашел первый эффективный алгоритм и получил премию Turing Award в 1972):