Rekurzivní SELECT v pořadí depth-first

[pepak]

Mám jednoduchou tabulku s n-árním stromem:

Kód: [Vybrat]

STROM(id, id_rodice, poradi, payload)
Z této tabulky umím udělat hierarchický dotaz, který mi vrátí všechny položky v pořadí breadth-first:

Kód: SQL [Vybrat]

1. WITH hierarchy(level, id, id_rodice, poradi, payload)
2. AS (
3.   SELECT 0, id, id_rodice, poradi, payload
4.   FROM strom
5.   WHERE id=123 -- ID korene zadane zvenku
6.   UNION ALL
7.   SELECT h.level+1, s.id, s.id_rodice, s.poradi, s.payload
8.   FROM strom s
9.   JOIN hierarchy h ON h.id=s.id_rodice
10. )
11. SELECT * FROM hierarchy
12. ORDER BY level, poradi
13.  

Nenapadá mě, jak to prostředky SQL vrátit v pořadí depth-first. Nějaký nápad?

[jirka]

Ahoj,
jde to tak, že si uložíš do každému záznamu cestu k uzlu. Na MSSQL se dá vhodně použít funkce ROW_NUMBER() OVER(...), která očísluje uzly jednoho rodiče. Následující kód bude fungovat pro maximální počet 9 uzlů jednoho rodiče a max. úrověň 255, pro více se musí upravit výraz pro "path_to_node".

Kód: SQL [Vybrat]

1. WITH hierarchy(level, id, id_rodice, poradi, payload, path_to_node)
2. AS (
3.   SELECT 0, id, id_rodice, poradi, payload, CAST('1' AS VARCHAR(255))
4.   FROM strom
5.   WHERE id=123 -- ID korene zadane zvenku
6.   UNION ALL
7.   SELECT h.level+1, s.id, s.id_rodice, s.poradi, s.payload,
8.          CAST(h.path_to_node + CAST(ROW_NUMBER() OVER(ORDER BY h.level) AS VARCHAR) AS VARCHAR(255))
9.   FROM strom s
10.   JOIN hierarchy h ON h.id=s.id_rodice
11. )
12. SELECT * FROM hierarchy
13.  ORDER BY path_to_node

HTH
Jirka

[pepak]

Díky.

Ve finále jsem to stejně udělal na úrovni aplikace, protože to muselo chodit i na SQL Serveru 2000, který rekurzivní dotazy neumí, ale jsem rád za informaci, jak to udělat.