How to flatten tree leaves sequence in SQL

Question

I have a table S which has an 2 columns: Name for ID, and an XML column.
This table represents a tree data.

S
-----+----------------
Name | XmlCol
-----+----------------
 A   | <E><B Id='b1' Type=0 /><B Id='D' Type=1 /><B Id='b2' Type=0 /></E>
 D   | <E><B Id='b3' Type=0 /><B Id='G' Type=1 /></E>
 F   | <E><B Id='b4' Type=0 /></E>
 G   | <E><B Id='b5' Type=0 /></E>

The data appears in given order. Order matters here.

Notice the XML structure.

Type = 0 means that the entry is of type leaf.
Type = 1 means that there is a row in the table with same Name, hence a node and not a leaf.

There are 5 leaves, b1, b2, b3, b4, b5.

What I want is to get a table of all leaves in the sequence presented, like this:

Leaves
--------
b1
b3
b5
b2
b4

when the start node is 'A'

This is the XML parsing snippet, but it is just the begining.

SELECT [Id] = xTree.b.value('@Id', 'varchar(10)')
FROM [S]
CROSS APPLY [XmlCol].nodes('/E/B') AS xTree(b)

Can anyone suggest how to do this in SQL?

Answer 1

Try something like this:

DECLARE @Source TABLE (
    Name VARCHAR(10) PRIMARY KEY,
    XmlCol XML NOT NULL
)

DECLARE @Root VARCHAR(10)='A'

INSERT INTO @Source VALUES 
('A',CONVERT(XML,'<E><B Id="b1" Type="0" /><B Id="D" Type="1" /><B Id="b2" Type="0" /></E>')),
('D',N'<E><B Id="b3" Type="0" /><B Id="G" Type="1" /></E>'),
('F',N'<E><B Id="b4" Type="0" /></E>'),
('G',N'<E><B Id="b5" Type="0" /></E>')

DECLARE @Temp1 TABLE (  
    ID INT IDENTITY PRIMARY KEY,
    Name VARCHAR(10) NOT NULL,
    Type INT NOT NULL,
    Value VARCHAR(10) NOT NULL
)
INSERT INTO @Temp1
SELECT Name, xTree.b.value('@Type', 'int') AS Type, xTree.b.value('@Id', 'varchar(10)') AS Value
FROM @Source
CROSS APPLY [XmlCol].nodes('/E/B') AS xTree(b)

DECLARE @Temp2 TABLE (  
    ID INT PRIMARY KEY,
    Name VARCHAR(10) NOT NULL,
    Type INT NOT NULL,
    Value VARCHAR(10) NOT NULL,
    Position INT NOT NULL
)

INSERT INTO @Temp2
SELECT *, ROW_NUMBER() OVER (PARTITION BY Name ORDER BY ID) AS Position
FROM @Temp1

DECLARE @Temp3 TABLE (
    Name VARCHAR(10) NOT NULL,
    Type INT NOT NULL,
    Value VARCHAR(10) NOT NULL,
    Position FLOAT NOT NULL,
    Level INT NOT NULL,
    PRIMARY KEY (Name, Position)
)

;WITH CTE AS (
    SELECT Name, Type, Value, CONVERT(FLOAT,Position) AS Position, 0 AS Level 
    FROM @Temp2 WHERE Type=0
    UNION ALL
    SELECT t1.Name, t2.Type, t2.Value, 
        t1.Position+t2.Position*POWER(CONVERT(FLOAT,0.1),1+t2.Level), 
        t2.Level+1 AS Level
    FROM @Temp2 t1
    INNER JOIN CTE t2 ON t2.Name=t1.Value
    WHERE t1.Type=1
)
INSERT INTO @Temp3
SELECT * FROM CTE

SELECT Value
FROM (
    SELECT Value, 0 AS Extra, Position 
    FROM @Temp3 WHERE Name=@Root
    UNION ALL
    SELECT Value, 1 AS Extra, Position
    FROM @Temp3 WHERE Value NOT IN (
        SELECT Value 
        FROM @Temp3 WHERE Name=@Root
    )
) u
ORDER BY Extra, Position

A few observations:

• in XML, the value of the attributes should always be quoted

• it's not very clear in which order you want the values that are outside the tree of the given root (in this example, only b4 is not part of the tree starting from A; if there were multiple values like this, in multiple other trees, it's not clear which is the desired order)

• the use of table variables may be avoided by using a more complex CTE, but I think they are helpful for performance

• I assumed a maximum of 10 sub-nodes per level; if there are more sub-nodes, you can change 0.1 to 0.01, for example