## SQL vs NoSQL: Third International NoCOUG SQL & NoSQL Challenge sponsored by Pythian

Follow @Oratweets

As published in the May 2012 issue of the *NoCOUG Journal*

**THE WICKED WITCH OF THE WEST NEEDS HELP**

**BE IT KNOWN BY THESE PRESENTS** that the Wicked Witch of the West needs your help to create a magic spell to ensure that the Third Annual Witching & Wizarding Ball is a grand success. A great tournament has been organized for practitioners of the arts of Es-Cue-El & No-Es-Cue-El to demonstrate their magic powers.

**Mind-Boggling Puzzle**

The Wicked Witch of the West has invited six friends to the Third Annual Witching & Wizarding Ball at Pythian Academy of Es-Cue-El & No-Es-Cue-El. Burdock Muldoon and Carlotta Pinkstone both said they would come if Albus Dumbledore came. Albus Dumbledore and Daisy Dodderidge both said they would come if Carlotta Pinkstone came. Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone all said they would come if Elfrida Clagg came. Carlotta Pinkstone and Daisy Dodderidge both said they would come if Falco Aesalon came. Burdock Muldoon, Elfrida Clagg, and Falco Aesalon all said they would come if Carlotta Pinkstone and Daisy Dodderidge both came. Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came.

The Wicked Witch of the West needs an Es-Cue-El or No-Es-Cue-El spell to determine whom she needs to persuade to attend the wizarding ball in order to ensure that all her invitees attend.

**Awesome Prizes**

The *August Order of the Wooden Pretzel* will be conferred on the winner, in keeping with the celebrated pronouncement of the supreme wizard of Pee-El/Es-Cue-El that *“some people can perform seeming miracles with straight Es-Cue-El, but the statements end up looking like pretzels created by somebody who is experimenting with hallucinogens.”* As if that singular honor were not enough, a fiery wizarding device that magically displays Oracular tomes will be bestowed upon the champion.

*May the best witch or wizard win!*

**RULES**: Pythian will award a Kindle Fire or an Amazon gift card of equal value to the winner. Prizes may be awarded to runners-up at the discretion of NoCOUG. Submissions should be emailed to **SQLchallenge@nocoug.org**. Contestants may use any SQL or NoSQL technology to create the magic spell. The competition will be judged by Oracle ACE Director Gwen Shapira and the editor of the *NoCOUG Journal*, Iggy Fernandez. Judging criteria include correctness, originality, efficiency, portability, and readability. The judges’ decisions are final. The competition will end at a time determined by the organizers. The judges and organizers reserve the right to publish and comment on any of the submissions, with due credit to the originators. More information about the problem and additional rules can be found at **http://www.nocoug.org/.**

**Updated on 11/15/12:** The results have been published in the November 2012 issue of the NoCOUG Journal. The winner is Lukasz Plata (Poland).

Results of the First International NoCOUG SQL Challenge

Results of the Second International NoCOUG SQL Challenge

with Bool(X) as (select 0 from dual union select 1 from dual)

select EC.X, CP.X, FA.X, DD.X, BM.X, AD.X

from Bool EC, Bool CP, Bool FA, Bool DD, Bool BM, Bool AD

where AD.X <= BM.X and AD.X <= CP.X

and CP.X <= AD.X and CP.X <= DD.X

and EC.X <= AD.X and EC.X <= BM.X and EC.X <= CP.X

and FA.X <= CP.X and FA.X <= DD.X

and CP.X*DD.X <= BM.X and CP.X*DD.X <= EC.X and CP.X*DD.X <= FA.X

and AD.X*BM.X <= DD.X;

0 0 0 0 0 0

0 0 0 0 1 0

0 0 0 1 0 0

0 0 0 1 1 0

1 1 1 1 1 1

Therefore, inviting either EC, CP, FA or AD would suffice.

Thanks, Tegiri. We’ll be posting some clarifications on the NoCOUG website soon. The data set in the announcement is just an example; we’re really looking for a general solution to the following problem:

“The witch has invited many people to the ball. The attendance of some of the invitees is contingent on the presence of one or more other invitees. Whom should be persuaded to attend in order to guarantee that all her invitees attend?”Don’t assume the number of invitees.

Don’t assume that only one invitee should be persuaded to attend.

Don’t assume that each invitee has listed only one condition.

Don’t assume that every invitee has listed at least one condition.

Don’t assume the number of attendees listed in a condition.

Don’t assume that there is no overlap between conditions.

Don’t include an invitee in the answer if that invitee’s presence is guaranteed by the presence of the other invitees in the answer.

List all answers if there is more than one.

Here are some additional data sets with their respective answers:

Data set 2Answers:

(a) Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg

Data set 3Answers:

(a) Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg

Data set 4Answers:

(a) Albus Dumbledore and Daisy Dodderidge

Data set 5Answers:

(a) Albus Dumbledore and Daisy Dodderidge

Data set 6Answers:

(a) Albus Dumbledore and Daisy Dodderidge

(b) Burdock Muldoon and Elfrida Clagg

(c) Albus Dumbledore and Elfrida Clagg

(d) Burdock Muldoon and Daisy Dodderidge

Data set 7Answers:

(a) Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon

Simplified a query a little:

with Bool(X) as (select 0 from dual union select 1 from dual)

select EC.X, CP.X, FA.X, DD.X, BM.X, AD.X

from Bool EC, Bool CP, Bool FA, Bool DD, Bool BM, Bool AD

where AD.X <= BM.X*CP.X

and CP.X <= AD.X*DD.X

and EC.X <= AD.X*BM.X*CP.X

and FA.X <= CP.X*DD.X

and CP.X*DD.X <= BM.X*EC.X*FA.X

and AD.X*BM.X <= DD.X;

Which hints to general form of the rule. Therefore, full solution must include the following ingredients:

1. Variable number of joins

2. Multiplicative aggregation

3. Extra query over the result to deduce the required minimal attendance

…

Your requirement that query should be generic implies that you are trying to fit rules into data. I anticipate awkward database schema design. Certainly you don’t want to store those constraints as plain text?

Are you sure about example #6 (didn’t check the others)? I’m getting:

[AD BM CP DD EC FA]

0 0 0 0 0 0

0 0 0 1 1 1

1 1 1 0 0 0

1 1 1 1 1 1

which implies that you are mising 3*3-2*2=5 pairs:

CP,DD

CP,EC

CP,FA

AD,FA

BM,FA

There’s no need to store the constraints as plain text.

You’re correct. That’s why magic spells are necessary for this sort of thing :-)

> We’ll be posting some clarifications on the NoCOUG website soon.

Will they be available for Non-NoCOUG-Members? At the moment I cannot find anything. I can only download the NoCOUG Journal, because you linked it in your previous post.

A general question:

What exactly does “whom she needs to persuade to attend the wizarding ball in order to ensure that all her invitees attend.” mean?

In dataset 7 your answer is: “B, C, D, E, F”.

But isn’t “{null}” sufficient?

Whenever one of “B, C, D” or “C, D, E” or “D, E, F” comes, then A will come too, the fifth wizard will come without prerequisites. Since B, C, D, E, F each have no prerequisites, they don’t need to be persuaded and therefore will come when invited. Otherwise (if an invitation to a wizard without prerequisites is not sufficient) always each wizard has to be persuaded.

IMHO the riddle only makes sense if “whom she needs to persuade” means that a wizard has to be persuaded to come despite his/her prerequisites.

Also in dataset 5:

F will come if E comes

F will come if D comes

C and F will both come if A, B, D and E all come

Since F will come when either D or E comes the third condition is redundant, except when you say, that each rule has to be matched.

Regards

Marcus

That’s another clarification that we need to make. The problem statement says that the presence of some of the invitees is contingent upon the presences of some other invitees. Nothing has been said about the presence of those invitees who have not imposed conditions on their presence. In other words, their presence is not guaranteed and therefore the witch has to use her powers of persuasion on them (and on any others whose presence she deems necessary to ensure a full complement of attendees.)

The difficulty lies in the use of the English language which by nature is imprecise. A precise formulation using relational calculus or some other programming language is the magic spell that the witch needs. Magic spells are very precise :-)

The best we can do is provide examples. Here is yet another example for clarification:

Data set 8

Answers:

(a) Albus Dumbledore

(b) Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon

P.S. I might add that none of the judges have constructed a magic spell yet and we expect that it will be quite difficult to do so.

The third condition is definitely redundant but a human may not easily see that. Therefore, the magic spell should be capable of processing such redundancies :-)

Tegiri, Your solution is interesting even though the magic spell has to be “hand coded.” But does it work for the following data set?

Data set 8

Answers:

(a) Albus Dumbledore

(b) Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon

with Bool(X) as (select 0 from dual union select 1 from dual)

select EC.X, CP.X, FA.X, DD.X, BM.X, AD.X

from Bool EC, Bool CP, Bool FA, Bool DD, Bool BM, Bool AD

where AD.X <= BM.X

and AD.X <= CP.X

and AD.X <= DD.X

and AD.X <= EC.X

and AD.X <= FA.X

and BM.X*CP.X*DD.X*EC.X*FA.X <= AD.X

;

0 0 0 0 0 0

1 0 0 0 0 0

0 1 0 0 0 0

1 1 0 0 0 0

0 0 1 0 0 0

1 0 1 0 0 0

0 1 1 0 0 0

1 1 1 0 0 0

0 0 0 1 0 0

1 0 0 1 0 0

0 1 0 1 0 0

1 1 0 1 0 0

0 0 1 1 0 0

1 0 1 1 0 0

0 1 1 1 0 0

1 1 1 1 0 0

0 0 0 0 1 0

1 0 0 0 1 0

0 1 0 0 1 0

1 1 0 0 1 0

0 0 1 0 1 0

1 0 1 0 1 0

0 1 1 0 1 0

1 1 1 0 1 0

0 0 0 1 1 0

1 0 0 1 1 0

0 1 0 1 1 0

1 1 0 1 1 0

0 0 1 1 1 0

1 0 1 1 1 0

0 1 1 1 1 0

1 1 1 1 1 1

There are two rows missing:

0 0 0 0 0 1

1 1 1 1 1 0

such that no other missing row "covers" them. Informally, having 1s in those columns implies that we must be looking into row

1 1 1 1 1 1

which is present in the data set. This query:

"Find all the rows missing in the result, then select maximal cover" is easy to formalize in SQL, of course.

with Bool(X) as (select 0 from dual union select 1 from dual)

, Aux(EC,CP,FA,DD,BM,AD) as (select EC.X, CP.X, FA.X, DD.X, BM.X, AD.X

from Bool EC, Bool CP, Bool FA, Bool DD, Bool BM, Bool AD

where not(AD.X <= BM.X

and AD.X <= CP.X

and AD.X <= DD.X

and AD.X <= EC.X

and AD.X <= FA.X

and BM.X*CP.X*DD.X*EC.X*FA.X <= AD.X)

) select * from Aux a2 where not exists (select 1 from Aux a1

where a1.EC < a2.EC and a1.CP <= a2.CP and a1.FA <= a2.FA and a1.DD <= a2.DD and a1.BM <= a2.BM and a1.AD <= a2.AD

or a1.EC <= a2.EC and a1.CP < a2.CP and a1.FA <= a2.FA and a1.DD <= a2.DD and a1.BM <= a2.BM and a1.AD <= a2.AD

or a1.EC <= a2.EC and a1.CP <= a2.CP and a1.FA < a2.FA and a1.DD <= a2.DD and a1.BM <= a2.BM and a1.AD <= a2.AD

or a1.EC <= a2.EC and a1.CP <= a2.CP and a1.FA <= a2.FA and a1.DD < a2.DD and a1.BM <= a2.BM and a1.AD <= a2.AD

or a1.EC <= a2.EC and a1.CP <= a2.CP and a1.FA <= a2.FA and a1.DD <= a2.DD and a1.BM < a2.BM and a1.AD <= a2.AD

or a1.EC <= a2.EC and a1.CP <= a2.CP and a1.FA <= a2.FA and a1.DD <= a2.DD and a1.BM <= a2.BM and a1.AD < a2.AD

)

;

1 1 1 1 1 0

0 0 0 0 0 1

Double checking the original problem:

with Bool(X) as (select 0 from dual union select 1 from dual)

, Aux(EC,CP,FA,DD,BM,AD) as (select EC.X, CP.X, FA.X, DD.X, BM.X, AD.X

from Bool EC, Bool CP, Bool FA, Bool DD, Bool BM, Bool AD

where not(AD.X <= BM.X*CP.X

and CP.X <= AD.X*DD.X

and EC.X <= AD.X*BM.X*CP.X

and FA.X <= CP.X*DD.X

and CP.X*DD.X <= BM.X*EC.X*FA.X

and AD.X*BM.X <= DD.X)

) select * from Aux a2 where not exists (select 1 from Aux a1

where a1.EC <= a2.EC and a1.CP <= a2.CP and a1.FA <= a2.FA and a1.DD <= a2.DD and a1.BM <= a2.BM and a1.AD <= a2.AD

and a1.EC+a1.CP+a1.FA+a1.DD+a1.BM+a1.AD < a2.EC+a2.CP+a2.FA+a2.DD+a2.BM+a2.AD

)

;

1 0 0 0 0 0

0 0 0 0 0 1

0 1 0 0 0 0

0 0 1 0 0 0

Hi, Tegiri,

Most humans cannot understand wizard magic :-) It’s time for you to explain how your query is constructed from the given rules. Would you also explain why the constructed query is guaranteed to return all solutions?

Iggy

Does your query also work for data set 8 above and do you think it generates all the possible answers (and no others) even if the answers have different lengths (as in the case of data set 8)?

For each rule multiply all conditions and compare it with the product of all attendees who put forward this condition. For example:

Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon will all come if Albus Dumbledore comes:

AD <= BM*CP*DD*EC*FA

Informally, if AD=1, then everybody on the list BM,CP,DD,EC,FA should evaluate to 1. This is arithmetic way to express each inequality as logical implication.

Albus Dumbledore will come if Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon all come:

BM*CP*DD*EC*FA <= AD

If everybody on the list BM,CP,DD,EC,FA is 1 then AD has to be 1 as well.

From the original problem, BM, EC, FA come if CP and DD both come translates into:

CP*DD <= BM*EC*FA

Multiplication is just a shortcut for logical connectives. You may rewrite the above inequalities as conjunctions and disjunctions of simpler constraints not involving arithmetic.

Now that we understand how each rule is translated into where clause predicate, let’s look into global picture. The cartesian product generatess different worlds, or possibilities who may come, or who may not. Rules invalidate some. For example:

BM*CP*DD*EC*FA <= AD

asserts that a world where BM=0 (doesn't attend) and AD=1 (attends) is impossible. In my initial attempt I didn't venture beyond just listing all the possibilities, and derived final solution informally. This is as we have seen is just a not exist query on top.

Hi, Tegiri,

Please explain how the NOT EXISTS subquery is constructed. Also, please send solutions for all eight data sets to SQLchallenge@nocoug.org otherwise the judges have no way of testing your solution against all the data sets.

Iggy

We’ve linked to the clarifications from the NoCOUG home page. The direct link is http://www.nocoug.org/download/2012-05/Third%20International%20NoCOUG%20SQL%20&%20NoSQL%20Challenge%20(Additional%20Rules).pdf.

Hi, Iggy and Tegiri,

I’m trying to generalize the Tegiri’s solution just to understand why (or why not) it works. Please note that all of the following is done on Oracle 11gR2 (I’m using some boilerplate code from my own solution to simplify unit-testing), but I’m pretty sure it would not be too hard to port it to any other RDBMS.

My implementation of that solution DOES seem to work for SOME datasets (1 and 8, the ones that Tegiri confirmed as working). It however FAILS for some other datasets, unless I misunderstood Tegiri’s explanation of his solution.

Instead of cartesian product of 6 2-row tables I’m encoding invitee combinations (and rules) as numbers (bitmaps effectively) in range [1, 2^N) where N=6 for our case.

Each invitee ID is encoded as 2^n:

A=1, B=2, C=4, D=8, E=16, F=32

The rules are encoded as follows (DataSet 8):

(if A then BCDE) translates to 000001 -> 111110 (or 1 -> 62)

(if BCDE then A) translates to 111110 -> 000001 (or 62 -> 1)

I’ve started with the rules specified in post#14 (DataSet 8):

That can be translated to:

Which can be generalized as somewhat like this (where imask is the IF part of the rule and omask is the THEN part of the rule):

And to remove redundant solutions one can use something like this:

The complete query (with rule parser to simplify unit-testing) for Oracle 11gR2 is:

Apparently few rows got snatched by some WP plugin.

I’ve started with the rules specified in post#14 (DataSet 8):

That can be translated to:

In dataset 2 isn’t the answer: Daisy Dodderidge, and *Falco Aesalon* *or* Albus Dumbledore, Burdock Muldoon?

I think Tegiri had incorrect NOT EXIST clause.

with Bool(X) as (select 0 from dual union select 1 from dual)

, CP(EC,CP,FA,DD,BM,AD) as (select EC.X, CP.X, FA.X, DD.X, BM.X, AD.X

from Bool EC, Bool CP, Bool FA, Bool DD, Bool BM, Bool AD

), Attending(EC,CP,FA,DD,BM,AD) as (select *

from CP

where AD*BM <= CP

and EC*DD <= FA

), NotAttending(EC,CP,FA,DD,BM,AD) as (select *

from CP

minus

select * from Attending

) select * from NotAttending a1 where not exists (select 1 from NotAttending a2

where a1.EC <= a2.EC and a1.CP <= a2.CP and a1.FA <= a2.FA and a1.DD <= a2.DD and a1.BM <= a2.BM and a1.AD <= a2.AD

and a1.EC+a1.CP+a1.FA+a1.DD+a1.BM+a1.AD < a2.EC+a2.CP+a2.FA+a2.DD+a2.BM+a2.AD

)

;

Thanks for pointing it out. I’ve patched it up so that other readers won’t be confused.

The answer seems to be that Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg must all attend because their presence is required before Carlotta Pinkstone and Falco Aesalon will attend.

Tegiri still has to confirm that his submission works correctly for all eight data sets.

Tegiri still has to confirm that his submission works correctly for all eight data sets.

Also, don’t assume that all answers contain the same number of invitees. Data set 8 below has two solutions; the first contains one invitee and the second contains five.

Data set 8

Answers:

(a) Albus Dumbledore

(b) Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon

with Bool(X) as (select 0 from dual union select 1 from dual)

, CP(EC,CP,FA,DD,BM,AD) as (select EC.X, CP.X, FA.X, DD.X, BM.X, AD.X

from Bool EC, Bool CP, Bool FA, Bool DD, Bool BM, Bool AD

), Attending(EC,CP,FA,DD,BM,AD) as (select *

from CP

where

AD*BM <= CP

and EC*DD <= FA

/*AD <= BM*CP

and CP <= AD*DD

and EC <= AD*BM*CP

and FA <= CP*DD

and CP*DD <= BM*EC*FA

and AD*BM <= DD*/

), NotAttending(EC,CP,FA,DD,BM,AD) as (select *

from CP

minus

select * from Attending

), IncompleteAttendance(EC,CP,FA,DD,BM,AD) as (select * from Attending

where EC!=1 or CP!=1 or FA!=1 or DD!=1 or BM!=1 or AD!=1

), InfluentialAttendees(EC,CP,FA,DD,BM,AD) as (select *

from CP where not exists (select 1 from IncompleteAttendance atn

where cp.EC <= atn.EC and cp.CP <= atn.CP and cp.FA <= atn.FA and cp.DD <= atn.DD and cp.BM <= atn.BM and cp.AD <= atn.AD

) )

select * from InfluentialAttendees ia2 where not exists (select 1 from InfluentialAttendees ia1

where ia1.EC <= ia2.EC and ia1.CP <= ia2.CP and ia1.FA <= ia2.FA and ia1.DD <= ia2.DD and ia1.BM <= ia2.BM and ia1.AD <= ia2.AD

and ia1.EC+ia1.CP+ia1.FA+ia1.DD+ia1.BM+ia1.AD < ia2.EC+ia2.CP+ia2.FA+ia2.DD+ia2.BM+ia2.AD

);

It looks like arithmetics hack doesn’t really work, for dataset#3, at least. So one has to write down logic explicitly, For dataaset#3 we have:

with Bool(X) as (select 0 from dual union select 1 from dual)

, CP(EC,CP,FA,DD,BM,AD) as (select EC.X, CP.X, FA.X, DD.X, BM.X, AD.X

from Bool EC, Bool CP, Bool FA, Bool DD, Bool BM, Bool AD

), Attending(EC,CP,FA,DD,BM,AD) as (select *

from CP

where

/*AD*BM<CP and

DD*EC<FA and

AD*BM*DD*EC<CP*FA — wrong! */

(AD=0 or BM=0 or CP=1) and

(DD=0 or EC=0 or FA=1) and

(AD=0 or BM=0 or DD=0 or EC=0 or CP=1) and

(AD=0 or BM=0 or DD=0 or EC=0 or FA=1)

), IncompleteAttendance(EC,CP,FA,DD,BM,AD) as (select * from Attending

where EC!=1 or CP!=1 or FA!=1 or DD!=1 or BM!=1 or AD!=1

), InfluentialAttendees(EC,CP,FA,DD,BM,AD) as (select *

from CP where not exists (select 1 from IncompleteAttendance atn

where cp.EC <= atn.EC and cp.CP <= atn.CP and cp.FA <= atn.FA and cp.DD <= atn.DD and cp.BM <= atn.BM and cp.AD <= atn.AD

) )

select * from InfluentialAttendees ia2 where not exists (select 1 from InfluentialAttendees ia1

where ia1.EC <= ia2.EC and ia1.CP <= ia2.CP and ia1.FA <= ia2.FA and ia1.DD <= ia2.DD and ia1.BM <= ia2.BM and ia1.AD <= ia2.AD

and ia1.EC+ia1.CP+ia1.FA+ia1.DD+ia1.BM+ia1.AD < ia2.EC+ia2.CP+ia2.FA+ia2.DD+ia2.BM+ia2.AD

);

1 0 0 1 1 1

Oh, it should be “less than equal”, not “less than” — silly me.

dataset#4:

AD <= BM and

BM <= CP and

AD <= CP and

DD <= EC and

EC <= FA and

DD <= FA

0 0 0 1 0 1

#5:

AD <= BM and

BM <= CP and

AD <= CP and

DD <= EC and

EC <= FA and

DD <= FA and

AD*BM*DD*EC <= CP*FA

0 0 0 1 0 1

#6:

AD <= BM and

BM <= CP and

AD <= CP and

DD <= EC and

EC <= FA and

DD <= FA and

BM <= CP and

CP <= AD and

BM <= AD and

EC <= FA and

FA <= DD and

EC <= DD

1 1 0 0 0 0

1 0 0 0 1 0

1 0 0 0 0 1

0 0 0 1 0 1

0 0 1 0 1 0

0 1 0 1 0 0

0 0 0 1 1 0

0 1 1 0 0 0

0 0 1 0 0 1

#7

BM*CP*DD <= AD and

CP*DD*EC <= AD and

DD*EC*FA <= AD

1 1 1 1 1 0

Looks like there is an international collaboration between Tegiri, Ilya, and Vadim but there’s no explanation of how to construct all the common table expressions and the final SELECT clause.

Aren’t the names of inner views/CTEs self explanatory, e.g. IncompleteAttendance that is party attendance that organizer wanted to avoid? BTW, I was surprised with Prolog apparent struggle with that kind of problem: http://cs.stackexchange.com/questions/2031/can-constraint-satisfaction-problems-be-solved-with-prolog.

Tegiri, I read the whole discussion and I must admit that I your query is still a bit unclear to me. I would gladly read a more detailed explanation from you. Thanks!

A very compact solution was received from master sorcerer Lukasz Plata. He starts with the set of all attendees and shrinks it by successive application of the rules.

> From: kmehkeri@gmail.com

> Date: Mon, 28 May 2012 22:16:42 +0200

> Subject: SQL Challenge

> To: SQLchallenge@nocoug.org

>

> Ah. So you need a spell again, dear Wicked Witch of the West.

>

> You have to create a table first to know who likes who. Numbers are

> easier to manipulate than letters. Powers of 2 are even more handy, so

> use them.

>

Here is the magic:

>

> You may find testing scripts for the spell and upgraded version of it

> that outputs letters in attachment. Have fun.

>

> Best Regards,

> Master Sorcerer Łukasz Pluta

Łukasz’ solution can be reformulated using Oracle object types though the bitwise operations used by Lukasz are obviously much more efficient. First the setup:

Łukasz’ solution becomes as follows:

Here is an explanation from Łukasz.

> From: kmehkeri@gmail.com

> Date: Mon, 4 Jun 2012 23:43:09 +0200

> Subject: Re: NoCOUG SQL & NoSQL Challenge (Lukasz Pluta) (excellent solution!)

> To: iggy_fernandez@hotmail.com

>

> Hi Iggy,

>

> Thanks for your interest in my solution! Here’s the reasoning for it

> in detail. I don’t have a blog, so you can surely publish it on your

> site.

>

> Initially, I was considering small teams and expanded them by applying

> rules to get the full set. But I noticed that I would need to consider

> every possible starting team, which can be difficult, especially if

> number of participants is greater than in testing sets. So I decided

> to go the other way and noted that every rule

>

> R: “If we have A, B, … and X in the team, we can add Z, as they will

> invite him”

>

> has a corresponding observation

>

> O: “If we plan to invite A, B, …, X and Z we can remove Z (don’t

> invite him), because he will come anyway”

>

> So if we apply an ordered list of rules [R1, R2, ..., Rn] to a

> starting team and obtain full team in result, it is pretty

> straightforward that we can begin with the full team and apply

> corresponding observations in reverse order – [On, ..., O2, O1] to

> obtain the starting team.

>

> The magic query does just this – starting from the full team applies

> every possible observations list, shrinking the team until it has not

> enough invitees to satisfy any other observation. The query results

> will surely contain all answers and this fact is easy to prove by

> contradiction. If a starting team would exist that our query didn’t

> return and it would take a list of rules [R1, R2, ..., Rn] to

> transform it to the full team, it would mean that the query did not

> consider a list of observations [On, ..., O2, O1]. But since the query

> is designed to take every possible path, it must have considered it –

> so I can assume that such team does not exist and we got all the

> answers.

>

> Although the query results will contain all the answers, it will also

> contain teams that are NOT the answers and I was soooo disappointed

> with this too – the solution would be much cleaner if we could handle

> this nicely in one step. Unfortunately, firstly, I don’t know a way to

> select only leaf nodes from the result set and secondly, some paths

> just lead to non-minimal teams where no more observations can be

> applied – other paths lead to teams being subsets of them – but the

> particular path has no way of knowing other solutions. That’s why I’m

> filtering the results with another query to select only teams that are

> truly minimal.

>

> A few more words about the performance – I was playing with the number

> of invitees and rules and the query was able to find a solution for 16

> invitees, ca. 30 rules and 90 answers in a matter of seconds. For

> larger inputs (20 invitees, 50 rules), it took too long to finish on

> my computer. I misclicked and didn’t save that script (ouch), but if I

> find some time to rewrite it, I will send it to you.

>

> Regards,

> Łukasz Pluta