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.

About these ads

14 Responses to “Variable number of joins”

  1. Iggy Fernandez Says:

    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

  2. Iggy Fernandez Says:

    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


  3. 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.


  4. 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 :)


  5. 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.


  6. […] 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! […]


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


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


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


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


  11. […] 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 […]

  12. Iggy Fernandez Says:

    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.

  13. Iggy Fernandez Says:

    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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: