NoCOUG (My)SQL Challenge entry #2

Feb 18, 2011 / By André Araújo

Tags: , , ,

A few days ago I learned about this year’s NoCOUG SQL Challenge and decided to to put the gray matter between my ears to work. I’ve been teaching a MySQL course this week and my first impulse was to use my MySQL VM to test my solution attempts. However, I eventually decided to use Recursive Subquery Factoring to solve the proposed problem and had to switch to an Oracle 11gR2, since it’s the only database that implements this feature that I know how to use (are there any others?).

I was happy with my solution, but frustrated that I couldn’t run it on MySQL. So I decided to try to make it somehow work on MySQL.

Again, as mentioned in my previous post, the obvious choice for me was to write an ugly SQL statement with a ridiculous amount of joins to traverse the tree and a humongous concatenation to assemble the result string. This was going to be mainly a boring and mechanical work and so I decided to stay away from that path. Without that option, though, I had to make some small compromises.

Even though the solution described below uses no procedural control structures, only SQL statements, it’s still a sequence of query that must be executed in a specific order. I even simulate a loop by executing the same statement a couple of times, and use local variables to store temporary results. So, this is indeed a procedural approach to the problem but using only SQL statements.

The solution also has a limitation: it works only for binary trees that are 7-levels deep. Nevertheless, it can be easily adjusted for other depths.

Having said that, let’s have a look at how it was built.

Traversing the tree

If I could process the tree nodes in a breadth-first traversal order, it would be possible to obtain the final result by using simple string replacements to merge the contents of each node into a single string. The order of the processing, though, is important and I had to find a way to sort the nodes in the exact order. Each level of the tree has to be fully processed before going ahead to the next one, starting from the root. Within each level it doesn’t matter which node is processed first, though.

I solved this in two steps. First, I used MySQL “inline aggregation” (not sure whether this has a specific name or not) to create a string with the nodes’ root names (WORD2 column) in the correct order. What I mean by “inline aggregation” is the ability, in MySQL, to concatenate records returned by a query using the following construction:

select @result := '';  -- initialize the string
select @result := concat(@result, stringColumn)
from aTable;

At the end of the above execution the @result variable will contain the concatenation of all the stringColumn‘s returned by the query.

So, using the example above, I executed the queries below to create the ordered string I needed. I created an auxiliary view (ALLWORDS) to avoid unnecessary typing. The “concatenating query” has to be executed once for each level, storing the result in a local variable:

create view allwords
as
select word2 as root, word1 as word from riddle where (word1 is not null)
union all
select word2 as root, word2 as word from riddle where (word2 is not null)
union all
select word2 as root, word3 as word from riddle where (word3 is not null);

select @n := '';
select @n := concat(@n,',',word,',') from (select word from allwords group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;

Once the string was assembled, I could then use it to sort the rows from the RIDDLE table in the correct order, using the following trick:

select ...
from riddle
order by instr(@n, concat(',',word2,','))

Assembling the words

Now that I had the rows in the order I wanted, all I needed was to process one by one, adding their contents to the result string. However, instead of appending the content of each node to the end of the string, as I did in the example above, I needed to insert them in the correct place, by replacing the root word of the node, which should already appear in the string, with the three words for the node being processed. To do this, I executed:

select @r := null;
select @r := case when @r is null then fragment else replace(@r, word, fragment) end
from (
  select concat(' ',word2,' ') word, concat(' ',ifnull(concat(word1,' '),''),word2,ifnull(concat(' ',word3), ''),' ') fragment
  from riddle
  order by instr(@n, concat(',',word2,','))
) mistery;

And voilá!

mysql> select @rG
*************************** 1. row ***************************
@r:  TRYING TO TYPE ONE HUNDRED DISTINCT WORDS IN A SINGLE PARAGRAPH IS REALLY
TOUGH IF I CANNOT REPEAT ANY OF THEM THEN PROBABLY THOSE WITH MANY LETTERS
SHOULD BE USED MAYBE SOME READERS WILL UTILIZE DICTIONARIES THESAURUSES
THESAURI OR POSSIBLY EVEN ENCYCLOPEDIAS BUT MY PREFERENCE HAS ALWAYS BEEN THAT
GRAY MATTER BETWEEN YOUR EARS SERIOUSLY MARILYN CHALLENGES SUCH AS THIS REQUIRE
SKILLS BEYOND MATH SCIENCE AND PHYSICS SO WHAT DO YOU ASK READING COMPREHENSION
WRITING ABILITY GOOD OLD FASHIONED ELBOW GREASE SCIENTISTS DONT CARE ABOUT
STRUCTURE THEY WANT RESULTS HEY LOOK ONLY ELEVEN MORE LEFT FIVE FOUR THREE TWO
DONE
1 row in set (0.00 sec)

Call to arms!

MySQL folks, put your brains to work and join the challenge! I sincerely hope that there’s a pure SQL implementation for this in MySQL, more elegant than the above. I’d love to see other ways of solving the riddle in MySQL.

The complete solution

create view allwords
as
select word2 as root, word1 as word from riddle where (word1 is not null)
union all
select word2 as root, word2 as word from riddle where (word2 is not null)
union all
select word2 as root, word3 as word from riddle where (word3 is not null);

select @n := '';
select @n := concat(@n,',',word,',') from (select word from allwords group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;
select @n := concat(@n,',',word,',') from (select word from allwords where instr(@n, concat(',',root,',')) = 0 group by word having count(*) = 1) a;

select @r := null;
select @r := case when @r is null then fragment else replace(@r, word, fragment) end
from (
  select concat(' ',word2,' ') word, concat(' ',ifnull(concat(word1,' '),''),word2,ifnull(concat(' ',word3), ''),' ') fragment
  from riddle
  order by instr(@n, concat(',',word2,','))
) mistery;

select @r;

Leave a Reply

  • (will not be published)

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>