Variable number of joins

Vadim Tropashko

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.

14 thoughts on “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

    Reply
  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

    Reply

  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.

    Reply

  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.

    Reply

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

    Reply

Leave a reply to The First International NoCOUG SQL Challenge: Nine Ways To Change a Lightbulb « So Many Oracle Manuals, So Little Time Cancel reply