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):

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 TOP 1 * FROM TUR_PARIS

WHERE [TO-TOWN] = 'TOULOUSE'

ORDER BY DISTANSE;

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

Следует заметить, что TOP n - нестандартная для SQL конструкция. Перепишем запрос без её использования:

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

),

MIN_DISTANSE( DISTANSE)

AS

(SELECT MIN( DISTANSE)

FROM TUR_PARIS

WHERE [TO-TOWN] = 'TOULOUSE'

)

SELECT TUR_PARIS.*

FROM TUR_PARIS JOIN MIN_DISTANSE ON MIN_DISTANSE.DISTANSE=TUR_PARIS.DISTANSE

WHERE [TO-TOWN] = 'TOULOUSE';

В приведенной обработке сети имеется только одно ограничение — мы построили маршруты в одном направлении. Мы можем проехать из Парижа до Лиона, но нам не позволено совершить поездку из Лиона до Парижа. Для этого мы должны добавить обратные пути в таблицу.

Это может быть сделано с помощью очень простого запроса: