Select all path from an Xml that have a content like a graph

Question

I have an XML column with an element like this:

<Root>
    <Word Type="pre1" Value="A" />
    <Word Type="pre1" Value="D" />

    <Word Type="base" Value="B" />

    <Word Type="post1" Value="C" />
    <Word Type="post1" Value="E" />
    <Word Type="post1" Value="F" />
</Root>

that model something like:

and want to select all possible path using XQuery in MSSQL to have something like this result:

ABC ABE ABF DBC DBE DBF

Or somthing like:

<Root>
    <Word Type="pre1" Value="A" />
    <Word Type="pre1" Value="D" />

    <Word Type="pre2" Value="G" />
    <Word Type="pre2" Value="H" />

    <Word Type="base" Value="B" />

    <Word Type="post1" Value="C" />
    <Word Type="post1" Value="E" />
    <Word Type="post1" Value="F" />
</Root>

with this result:

AHBC AHBE AHBF DHBC DHBE DHBF AGBC AGBE AGBF DGBC DGBE DGBF

Answer 1

You can use a CTE to build the unique type list and then use that in a recursive CTE to build the strings. Finally you pick out the strings generated in the last iteration.

with Types as
(
  select row_number() over(order by T.N) as ID,
         T.N.value('.', 'varchar(10)') as Type
  from (select @XML.query('for $t in distinct-values(/Root/Word/@Type) 
                           return <T>{$t}</T>')
       ) as X(T)
    cross apply X.T.nodes('/T') as T(N)
),
Recu as
(
  select T.Type,
         T.ID,
         X.N.value('@Value', 'varchar(max)')  as Value
  from Types as T
    cross apply @XML.nodes('/Root/Word[@Type=sql:column("T.Type")]') as X(N)
  where T.ID = 1
  union all
  select T.Type,
         T.ID,
         R.Value+X.N.value('@Value', 'varchar(max)') as Value
  from Types as T
    inner join Recu as R
      on T.ID = R.ID + 1
    cross apply @XML.nodes('/Root/Word[@Type=sql:column("T.Type")]') as X(N)    
)
select R.Value
from Recu as R
where R.ID = (select max(T.ID) from Types as T)
order by R.Value

SQL Fiddle

Update

Here is a version that have better performance. It shreds the XML to two temp tables. One for each type and one for all words. The recursive CTE is still needed but it uses the tables instead of the XML. There is also one index on each of the temp tables that is used by the joins in the CTE.

-- Table to hold all values
create table #Values
(
  Type varchar(10),
  Value varchar(10)
);

-- Clustered index on Type is used in the CTE
create clustered index IX_#Values_Type on #Values(Type)

insert into #Values(Type, Value)
select T.N.value('@Type', 'varchar(10)'),
       T.N.value('@Value', 'varchar(10)')
from @XML.nodes('/Root/Word') as T(N);

-- Table that holds one row for each Type
create table #Types
(
  ID int identity,
  Type varchar(10),
  primary key (ID)
);

-- Add types by document order
-- Table-Valued Function Showplan Operator for nodes guarantees document order
insert into #Types(Type)
select T.Type
from (
     select row_number() over(order by T.N) as rn,
            T.N.value('@Type', 'varchar(10)') as Type
     from @XML.nodes('/Root/Word') as T(N)
     ) as T
group by T.Type
order by min(T.rn);

-- Last level of types
declare @MaxID int;
set @MaxID = (select max(ID) from #Types);

-- Recursive CTE that builds the strings
with C as 
(
  select T.ID,
         T.Type,
         cast(V.Value as varchar(max)) as Value
  from #Types as T
    inner join #Values as V
      on T.Type = V.Type
  where T.ID = 1
  union all
  select T.ID,
         T.Type,
         C.Value + V.Value
  from #Types as T
    inner join C
      on T.ID = C.ID + 1
    inner join #Values as V
      on T.Type = V.Type
)
select C.Value
from C
where C.ID = @MaxID
order by C.Value;

-- Cleanup
drop table #Types;
drop table #Values;

SQL Fiddle

Answer 2

You need the cross product of these three element sets, so basically write a join without conditions:

for $pre  in //Word[@Type="pre1"]
for $base in //Word[@Type="base"]
for $post in //Word[@Type="post1"]
return concat($pre/@Value, $base/@Value, $post/@Value)

For the extended version, I used two helper functions which fetch all attributes and then recursively concat the results.

It seems MSSQL doesn't allow custom XQuery functions. This code is valid for conformant XQuery 1.0 (and newer) processors.

declare function local:call($prefix as xs:string) as xs:string* {
  local:recursion('', 
    for $value in distinct-values(//Word/@Type[starts-with(., $prefix)])
    order by $value
    return $value
  )
};

declare function local:recursion($strings as xs:string*, $attributes as xs:string*) as xs:string* {
  if (empty($attributes))
  then $strings
  else
    for $string in $strings
    for $append in //Word[@Type=$attributes[1]]
    return local:recursion(concat($string, $append/@Value), $attributes[position() != 1])
};

for $pre in local:call('pre')
for $base in local:call('base')
for $post in local:call('post')
return concat($pre, $base, $post)