SQL Challenge I – Solution

Both Gary and Philip postd working versions. Gary's didn't work for me when I had the same letter more than one time in the string. Philips did work and the need to deal with each letter as if it is unique can of course be questioned. The intent was for a solution that could handle that and as Philip showed adjusting that is as easy as to just add a distinct.

My version is based on not using analytical functions of which I thought connect by was a part. Looking at it in another way, I wanted something that could be adopted to other databases.

My starting version of the solution would be:

   with v    as (select 'ABC' v from dual)
,base as (select substr(v.v,1,1) nv, 1 nn from v
union all
select substr(v.v,2,1) nv, 2 nn  from v
union all
select substr(v.v,3,1) nv, 3 nn  from v)
select a.nv||b.nv||c.nv
from base a, base b, base c
where a.nn not in(b.nn, c.nn)
and b.nn not in (c.nn)

What's not to like? I get to use one with construct that takes the output from another with construct as it's input. :-)
The "base" with gives us a result table that has one letter from the input string on each row. I'm then joining that with itself three times (as I have three letter in the string) to get a cartesian product that holds all cominations. It has the valid combinations (where all three letters are used) and invalid ones (where some letters are used more than one time). The last thing is to remove the invalid combinations. I do this by checking if the number I assign to each value (nn) occurs more than one time in the result. For AAA we would have nn for table alias A, B, and C be 1. I only have to check if each value occurs later on in the column list as if it was equal to an earlier one, the test for that earlier one would detect that the same was used.

So it works… Interesting and satisfying at the same time. However, the union is not too lovable. How can we avoid it? Well, the easy way would of course be to use the connect by trick, but as I intended to not use it I'll have to cheat and use anoter unrelated table (view).

   with v    as (select 'ABC' v from dual)
,base as (select substr( v.v,rownum,1) nv
,rownum nn from v, all_objects
where rownum <= length(v.v))

select a.nv||b.nv||c.nv
from base a
,base b
,base c
where a.nn not in (b.nn, c.nn)
and b.nn not in (c.nn)

I'm usig all_objects which should have more rows than the length of a string you want all combinations. It works, but I still prefer the connect by version if I were to use it. This way it does satisfy the limitation I put up for this.

So while this works, it is not as dynamic as one could want it to be. You need a different SQL if you have a four letter string. It ieasy to change this for that, but it is still annoying to have to have many different ones. An alternative would be to write PL*SQL to generate the SQL and then execute it. While that may be nicer, I wanted a solution that was a single statement.

I did find a way to do it. I'm sure it can be done easier and nicer. Maybe analytic functions would make the SQL faster and easier to understand. However, This way combines XML, with clauses, and dynamic in-line queries. For fancy use of the Oracle database, it's almost optimal… How practical it would be to use this very often and with long strings would have to be tested before getting it into a production scenario.

   with v as (select 'ABC' v from dual)
,base as (select substr(v.v,rownum,1) nv
,rownum nn
from v
,all_objects
where rownum <= length(v.v))       ,sel  as (select 'select ' ||                        substr(max(sys_connect_by_path('a'||
nn||'.nv', '||')),3)||' data' a
from base
connect by prior nn = nn - 1
start with nn = 1)
,frm  as (select 'from ' ||
substr(max(sys_connect_by_path(
'base a'||nn, ',')),2) a
from base
connect by prior nn = nn - 1
start with nn = 1)
,whr2  as (select 'a'||(nn-1)||'.nn not in('||
substr(max(sys_connect_by_path(
'a'||nn||'.nn', ', ')),2) ||
')' cond
,max(rownum) rn
from base
,v
where nn > 1
connect by prior nn = nn + 1
start with nn = length( v.v)
group by nn
order by nn)
,whr  as (select 'where ' || substr(max(
sys_connect_by_path(cond, ' and '))
,5) a
from whr2
,v
where not rn = length(v.v)
connect by prior rn = rn + 1
start with rn = length( v.v) - 1)
select extractvalue(t.column_value,'/DATA')
from sel a
,frm b
,whr c
,xmltable(
'for $root in $vals
return $root/ROWSET/ROW/DATA'
passing xmltype(dbms_xmlgen.getxml(
'with v    as (select ''ABC'' v
from dual)
,base as (select substr(v.v,rownum,1) nv
,rownum nn
from v
,all_objects
where rownum <= length(v.v))'                              ||a.a||' '                              ||b.a||' '                              ||c.a)) as "vals") t; 

The formatting is a bit forced here as I need it to fit in the line size google allows on this blog. I will not explain in detail what I have tried to achieve in this SQL. If you would want me to talk about what I'm doing in a post, leave a comment and I'll try to write it up in a post soon.

In short, I'm generating different pieces of the SQL statement needed in the with clauses and them I'm using that to create the XML document with all these cominations ina single XML document. I'm then using some XML function and XMLTable with an XML Query to get it back out form one row (one XML doc) to multiple rows to get it back to relational data.

The threaad that started me thinking about this was this thread. There are some permutations things there that solves this with pure analytics. But why do this the easy way when you can make it more complicated. Laurent's solution is probably the only one that scales well with longer strings.

I hope you enjoyed this and hopefully even learned something. I know I did, both that Cartesian products can be used in ways I hadn't really thought of and that I need to learn more about analytical functions.

I also learned more about XML function and how to move data in and out of these dynamic in-line queries.

May 18th, 2007 by