Google
 

Wednesday, March 28, 2012

Returning full path of records in tables with recursive relationships

A common requirement when dealing with tables with recursive relationship where a record points to another (parent) record in the same table, is to get the full path of the record name. like the case with full folder paths in a file system hierarchy.
For example: (data from http://www.ida.liu.se/~iislab/projects/secont/main/)


CategoryId Name ParentCategoryId
 1 Asset NULL
2 Countermeasure NULL
3 Cryptography 2
4 Encryption 3
5 SignatureAlgorithm 4
6 CryptographicHashFunction 5
7 DSA 6
8 MD5 6
9 EncryptionAlgorithm 4
10 BlockCipher 9
11 AES 10
12 DES 10

For the above data, we need to get this:

CategoryId Name
1 Asset
2 Countermeasure
3 Countermeasure > Cryptography
4 Countermeasure > Cryptography > Encryption
5 Countermeasure > Cryptography > Encryption > SignatureAlgorithm
9 Countermeasure > Cryptography > Encryption > EncryptionAlgorithm
10 Countermeasure > Cryptography > Encryption > EncryptionAlgorithm > BlockCipher
11 Countermeasure > Cryptography > Encryption > EncryptionAlgorithm > BlockCipher > AES
12 Countermeasure > Cryptography > Encryption > EncryptionAlgorithm > BlockCipher > DES
6 Countermeasure > Cryptography > Encryption > SignatureAlgorithm > CryptographicHashFunction
7 Countermeasure > Cryptography > Encryption > SignatureAlgorithm > CryptographicHashFunction > DSA
8 Countermeasure > Cryptography > Encryption > SignatureAlgorithm > CryptographicHashFunction > MD5

This can be achieved using Recursive Common Table Expressions:

WITH CategoryCTE
AS
(
SELECT C.CategoryId, CONVERT(NVARCHAR(500), C.Name) AS Name FROM dbo.Category C
WHERE ParentCategoryId IS NULL
UNION ALL
SELECT C.CategoryId, CONVERT(NVARCHAR(500), CTE.name + N' > ' + C.Name) AS Name FROM dbo.Category C
JOIN CategoryCTE CTE ON C.ParentCategoryId = CTE.CategoryId
)
SELECT * FROM CategoryCTE 

It works like this:
  • The CTE selects from the base table data, the level which has no parents
  • The result is union-ed with the recursive part, which joins the base table with the last value of the CTE up to the current level of recursion
  • The name field of a record is a concatenation between its parent name and its own name
  • Select the result of the CTE