## Variable number of joins

### March 25, 2009

Iggy Fernandezs posted a challenge which looks like routine application of recursive query technique:

with njoins (face_value, probability, joins) as ( SELECT d1.face_value , d1.probability, 1 FROM die d1 union all SELECT d1.face_value + d2.face_value AS SUM, d1.probability * d2.probability AS probability, joins+1 FROM njoins d1, die d2 where d1.joins < 10 ) select * from njoins

This is expected to work on Oracle 11.2, DB2, SQL Server (the later two not tested). Filtering out the result with *joins = :n* aggregating and grouping is left as an exercise to the reader.

March 25, 2009 at 4:20 pm

Hi, Vadim,

NoCOUG is organizing “The First International NoCOUG SQL Challenge” (with prizes offered by Apress). I’ll enter your solution into the competition.

Regards,

Iggy

March 25, 2009 at 4:42 pm

Hi, Vadim,

Would you explain how the addition of recursive CTEs makes SQL Turing-complete?

From Chapter 1 of Gray and Reuter:

“The basic theorem of relational databases says that these operators are Godel complete: They are equivalent to first-order predicate calculus [Codd 1971]. But the relational calculus is not Turing complete: It cannot describe all computable functions. A Turing-complete computational model is needed to write general programs. There is no need to invent such a language; almost any programming language will do. Consequently, SQL is always combined with a programming language.”

http://books.google.com/books?q=gray+reuter+%22turing+complete%22

Regards,

Iggy

March 25, 2009 at 10:37 pm

The book on transaction processing is not the ultimate authority on query languages (even though one of the authors happens to be Turing award recipient:-) When wondering about SQL turing completeness it is natural to ask “which SQL”? Datalog — that is very basic SQL with recursion but no aggregation — is claimed to be not turing complete, although I failed to find support for this claim. Here an attempt to simulate http://en.wikipedia.org/wiki/Rule_110 (which is claimed to be Turing complete) in SQL:

with grid (x,y) as (

select 0,0 FROM dual

union all

select c2.x, c2.y+1 from grid c2

where not exists (select * from grid c1, grid c3

where c1.y = c2.y and c1.y = c3.y

and c1.x+1 = c2.x AND c2.x+1 = c3.x)

and c1.y < 10 — safety

union all

select 1 from grid c1, grid c2

where not exists (select * from grid c3

where c1.y = c3.y

AND c2.x+1 = c3.x)

and c1.y = c2.y

and c1.x+1 = c2.x

and c1.y < 10 — safety

…

) SELECT * FROM grid;

Here I had patience to write down only two rule components (out of five), but hope the idea is clear.

March 26, 2009 at 7:30 pm

I am amazed by your solution. I did read about it in your book, but had no clue it was working in 11.2.

I would definitely vote for yours :)

March 27, 2009 at 4:18 pm

Thank you, Laurent: I discovered the challenge via your site.

Regarding rule 110 simulation query in my previous comment, it is not quite a solution because oracle doesn’t allow in the recursive definition clause

1. subqueries and

2. more than two union branches

Workaround the second issue is simple, but absence of subqueries invalidates this approach.

On the other hand, a grid is a spreadsheet, so model clause query should be a straightforward solution. This is remarkable, because excel is often cited as Turing incomplete programming system. I guess the critical item is ability to create new cells dynamically.

March 31, 2009 at 11:52 pm

[...] Go ahead. Try to solve it. Not as easy as it looks? When Iggy first sent me the problem description, I thought it was impossible. I sent it to few friends, just to annoy them. And turned out that it is far from impossible. In the process, the challenge description was leaked, and we have few terrific solutions already: Rob Van-Wijk used Model, Laurent used connect-by and Vadim used 11gR2! [...]

April 20, 2009 at 9:54 pm

[...] Vadim Tropashko’s solution using Common Table Expressions (USA): http://vadimtropashko.wordpress.com/2009/03/25/variable-number-of-joins/ [...]

July 8, 2009 at 5:16 am

[...] fourth solution was found by Vadim Tropashko from the USA who observed that recursive common table [...]

July 12, 2009 at 6:40 pm

[...] fourth solution—by Vadim Tropashko from the USA—used recursive common table [...]

July 31, 2009 at 4:46 am

[...] Vadim Tropashko’s solution using 11gR2 recursive joins This entry should win the shortest solution award. (USA). [...]

July 31, 2009 at 7:45 pm

[...] fourth solution—by Vadim Tropashko from the USA—used recursive common table expressions to generate records. [...]

August 10, 2009 at 3:38 am

[...] Congratulations to Laurent Schneider (Switzerland), Craig Martin (USA), Rob van Wijk (Netherlands), Vadim Tropashko (USA), Alberto Dell’Era (Italy), Fabien Contaminard (France), Cd-MaN (Romania), and André Araujo [...]

September 9, 2009 at 8:02 pm

Hi, Vadim,

It’s official: Oracle Database 11gR2 offers the recursive WITH clause.

Iggy

http://download.oracle.com/docs/cd/E11882_01/server.112/e10881/chapter1.htm#AREANO02555

1.3.1.2 Recursive WITH Clause

The SQL WITH clause has been extended to enable formulation of recursive queries.

Recursive WITH clause complies with the American National Standards Institute (ANSI) standard. This makes Oracle ANSI-compatible for recursive queries.

February 13, 2011 at 8:14 pm

The Second International NoCOUG SQL Challenge has been published in the February 2011 issue of the NoCOUG Journal. The Journal can be downloaded from http://bit.ly/gVNZsW. SQL commands for creating the required data are available at http://bit.ly/g58WVn.