Home > NoCOUG, NoSQL, SQL > SQL vs NoSQL: Third International NoCOUG SQL & NoSQL Challenge sponsored by Pythian

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

May 21, 2012 Leave a comment Go to comments

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

Categories: NoCOUG, NoSQL, SQL
  1. tegirinenashi
    May 21, 2012 at 2:08 pm | #1
    Reply | Quote

    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.

  2. Iggy Fernandez
    May 22, 2012 at 11:17 am | #2
    Reply | Quote

    tegirinenashi :

    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 2

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

    Answers:

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

    Data set 3

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

    Answers:

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

    Data set 4

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

    Answers:

    (a) Albus Dumbledore and Daisy Dodderidge

    Data set 5

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

    Answers:

    (a) Albus Dumbledore and Daisy Dodderidge

    Data set 6

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

    Answers:

    (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 7

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

    Answers:

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

  3. tegirinenashi
    May 22, 2012 at 2:27 pm | #3
    Reply | Quote

    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
    …

  4. tegirinenashi
    May 23, 2012 at 1:34 pm | #4
    Reply | Quote

    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?

  5. tegirinenashi
    May 24, 2012 at 9:53 am | #5
    Reply | Quote

    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

  6. Iggy Fernandez
    May 24, 2012 at 5:20 pm | #6
    Reply | Quote

    tegirinenashi :

    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?

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

  7. Iggy Fernandez
    May 24, 2012 at 5:22 pm | #7
    Reply | Quote

    tegirinenashi :

    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

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

  8. Marcus
    May 24, 2012 at 11:12 pm | #8
    Reply | Quote

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

  9. Marcus
    May 24, 2012 at 11:58 pm | #9
    Reply | Quote

    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

  10. Iggy Fernandez
    May 25, 2012 at 5:13 am | #10
    Reply | Quote

    Marcus :

    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.

    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

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

    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.

  11. Iggy Fernandez
    May 25, 2012 at 5:48 am | #11
    Reply | Quote

    Marcus :

    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

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

  12. Iggy Fernandez
    May 25, 2012 at 11:20 am | #12
    Reply | Quote

    tegirinenashi :

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

    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

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

    Answers:

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

  13. tegirinenashi
    May 25, 2012 at 1:46 pm | #13
    Reply | Quote

    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.

  14. tegirinenashi
    May 25, 2012 at 2:05 pm | #14
    Reply | Quote

    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

  15. tegirinenashi
    May 25, 2012 at 2:26 pm | #15
    Reply | Quote

    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

  16. Marcus
    May 25, 2012 at 3:19 pm | #16
    Reply | Quote

    Iggy Fernandez :

    Marcus :

    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.

    I have a solution … almost. It works good enough, that it found additional solutions for dataset 6: A,F / B,F / C,D / C,E / C,F
    It works for each of your datasets, only the last step to eliminate some results fails with an ORA-600, though the technique I use works with simpler data :-(

    Regards

  17. Iggy Fernandez
    May 25, 2012 at 4:43 pm | #17
    Reply | Quote

    tegirinenashi :

    Double checking the original problem:

    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

  18. Iggy Fernandez
    May 25, 2012 at 4:48 pm | #18
    Reply | Quote

    Marcus :

    I have a solution … almost. It works good enough, that it found additional solutions for dataset 6: A,F / B,F / C,D / C,E / C,F

    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)?

  19. tegirinenashi
    May 25, 2012 at 6:27 pm | #19
    Reply | Quote

    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?

    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.

  20. tegirinenashi
    May 25, 2012 at 7:02 pm | #20
    Reply | Quote

    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.

  21. Iggy Fernandez
    May 26, 2012 at 2:38 pm | #21
    Reply | Quote

    tegirinenashi :

    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

  22. Iggy Fernandez
    May 27, 2012 at 8:25 pm | #22
    Reply | Quote

    Marcus :

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

    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.

  23. Ilya
    May 29, 2012 at 1:47 am | #23
    Reply | Quote

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

    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
)

    That can be translated to:

    where 
AD.X > BM.X
or AD.X > CP.X
or AD.X > DD.X
or AD.X > EC.X
or AD.X > FA.X
or BM.X*CP.X*DD.X*EC.X*FA.X > AD.X)

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

    solve as (
  select state istate
  from states
  where exists (
    select null from rules,names where
    trunc(bitand(imask,state)/imask) > trunc(bitand(id,bitand(omask,state))/id)
    and bitand(omask,id)=id
  )
)

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

    solution as (
  select istate
  from solve a
  where not exists (
    select null from solve b
    where bitand(a.istate, b.istate) = b.istate
    and a.istate > b.istate
  )
)

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

    with
input as (
  select
/*
-- DataSet 1 (OK)
    '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.'
*/
--/*
-- DataSet 2 (FAIL)
    'Carlotta Pinkstone will come if Albus Dumbledore and Burdock Muldoon both come.'||
    'Falco Aesalon will come if Daisy Dodderidge and Elfrida Clagg both come.'
--*/
/*
-- DataSet 8 (OK)
    'Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon will all come if Albus Dumbledore comes.'||
    'Albus Dumbledore will come if Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon all come.'
*/
  as text
  from dual
),
names as (
  select power(2,rownum-1) id, nm from (
    select 'Albus Dumbledore' nm from dual union all
    select 'Burdock Muldoon' nm from dual union all
    select 'Carlotta Pinkstone' nm from dual union all
    select 'Daisy Dodderidge' nm from dual union all
    select 'Elfrida Clagg' nm from dual union all
    select 'Falco Aesalon' nm from dual
  )
),
cnt as (
  select count(1) c from names
),
p_rules(n,rule_if,rule_then) as (
  select 0 n, null, null from dual
  union all
  select
    n+1,
    regexp_replace(
      regexp_substr(text, '[^.]+\.’, 1, n+1),
      ‘([^.]+) if ([^.]+)’, ‘\2′) rule_if,
    regexp_replace(
      regexp_substr(text, ‘[^.]+\.’, 1, n+1),
      ‘([^.]+) if ([^.]+)’, ‘\1′) rule_then
  from p_rules, input
  where regexp_substr(text, ‘\.’,1,n+1) is not null
),
rules as (
  select
    (select sum(id) from names where instr(rule_if, nm)0) imask,
    (select sum(id) from names where instr(rule_then, nm)0) omask
  from p_rules
  where n>0
),
states(state) as (
  select 1 state from dual
  union all
  select 1+state from states,cnt
  where 1+state trunc(bitand(id,bitand(omask,state))/id)
    and bitand(omask,id)=id
  )
),
solution as (
  select istate
  from solve a
  where not exists (
    select null from solve b
    where bitand(a.istate, b.istate) = b.istate
    and a.istate > b.istate
  )
)
select listagg(nm,’, ‘) within group (order by nm) "Invitees"
from solution, names
where bitand(istate, id) = id
group by istate
order by "Invitees"
  24. Ilya
    May 29, 2012 at 1:59 am | #24
    Reply | Quote

    Apparently few rows got snatched by some WP plugin.

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

    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
)

    That can be translated to:

    where 
AD.X > BM.X
or AD.X > CP.X
or AD.X > DD.X
or AD.X > EC.X
or AD.X > FA.X
or BM.X*CP.X*DD.X*EC.X*FA.X > AD.X)
  25. Vadim Tropashko
    May 29, 2012 at 11:01 am | #25
    Reply | Quote

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

  26. Vadim Tropashko
    May 29, 2012 at 11:23 am | #26
    Reply | Quote

    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
    )
    ;

  27. Iggy Fernandez
    May 29, 2012 at 11:32 am | #27
    Reply | Quote

    Ilya :

    Apparently few rows got snatched by some WP plugin.

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

  28. Iggy Fernandez
    May 29, 2012 at 11:36 am | #28
    Reply | Quote

    Vadim Tropashko :

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

    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.

  29. Iggy Fernandez
    May 29, 2012 at 11:39 am | #29
    Reply | Quote

    Ilya :

    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.

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

  30. Iggy Fernandez
    May 29, 2012 at 11:40 am | #30
    Reply | Quote

    Vadim Tropashko :

    I think Tegiri had incorrect NOT EXIST clause.

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

  31. Iggy Fernandez
    May 29, 2012 at 12:46 pm | #31
    Reply | Quote

    Iggy Fernandez :

    Here are some additional data sets with their respective answers

    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

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

    Answers:

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

  32. Vadim Tropashko
    May 29, 2012 at 12:53 pm | #32
    Reply | Quote

    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
    );

  33. tegirinenashi
    May 30, 2012 at 10:59 am | #33
    Reply | Quote

    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

  34. tegirinenashi
    May 30, 2012 at 11:01 am | #34
    Reply | Quote

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

  35. tegirinenashi
    May 30, 2012 at 11:06 am | #35
    Reply | Quote

    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

  36. tegirinenashi
    May 30, 2012 at 11:09 am | #36
    Reply | Quote

    #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

  37. tegirinenashi
    May 30, 2012 at 11:16 am | #37
    Reply | Quote

    #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

  38. tegirinenashi
    May 30, 2012 at 11:19 am | #38
    Reply | Quote

    #7
    BM*CP*DD <= AD and
    CP*DD*EC <= AD and
    DD*EC*FA <= AD
    1 1 1 1 1 0

  39. Iggy Fernandez
    June 1, 2012 at 1:46 pm | #39
    Reply | Quote

    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.

  40. tegirinenashi
    June 1, 2012 at 3:03 pm | #40
    Reply | Quote

    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.

    • Łukasz Pluta
      June 8, 2012 at 10:46 am | #41
      Reply | Quote

      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!

  41. Iggy Fernandez
    June 3, 2012 at 9:06 pm | #42
    Reply | Quote

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

    -- Invitee is represented by a number - power of 2
-- A is 1, B is 2, C is 4, D is 8, E is 16, F is 32
-- Group is represented by a sum of numbers - invitees
create table rules (id integer primary key, will_come integer,
if_they_come integer);

-- SET 1
truncate table rules;
insert into rules values ( 1, 1, 4); -- A will come if C comes
insert into rules values ( 2, 1, 16); -- A will come if E comes
insert into rules values ( 3, 2, 1); -- B will come if A comes
insert into rules values ( 4, 2, 4 + 8); -- B will come if C & D comes
insert into rules values ( 5, 2, 16); -- B will come if E comes
insert into rules values ( 6, 4, 1); -- C will come if A comes
insert into rules values ( 7, 4, 16); -- C will come if E comes
insert into rules values ( 8, 4, 32); -- C will come if F comes
insert into rules values ( 9, 8, 1 + 2); -- D will come if A & B comes
insert into rules values (10, 8, 4); -- D will come if C comes
insert into rules values (11, 8, 32); -- D will come if F comes
insert into rules values (12, 16, 4 + 8); -- E will come if C & D comes
insert into rules values (13, 32, 4 + 8); -- F will come if C & D comes

    Here is the magic:

    with invitees (will_come, if_they_come, team, rule_chain) as (
-- Start with the whole team
select 0, 0, 1+2+4+8+16+32, ''
from dual
union all
-- and eliminate those who will come anyway by the rule - repeat until minimal team is found
select r.will_come, r.if_they_come, bitand(i.team,
1+2+4+8+16+32-r.will_come) as team, i.rule_chain||','||to_char(r.id)
from invitees i join rules r on (bitand (i.team,
r.will_come+r.if_they_come) = r.will_come+r.if_they_come)
),
-- In the result we have the teams who will invite all invitees
-- Choose all distinct of them
teams as (
select distinct team from invitees
)
-- And ensure that no one is redundant (eliminate teams if there exists a smaller team)
select team from teams t1
where not exists (
select team
from teams t2
where t1.team != t2.team
and bitand(t1.team, t2.team) = t2.team);

    >
    > 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:

    CREATE TYPE people_tab AS TABLE OF varchar2(32);
/

CREATE TYPE solutions_tab AS TABLE of people_tab;
/

CREATE TABLE rules
(
  rule_id integer,
  if_they_come people_tab,
  they_will_come people_tab
)
NESTED TABLE if_they_come STORE AS if_they_come_nt
NESTED TABLE they_will_come STORE AS they_will_come_nt;

CREATE TABLE invitees
(
  invitee_id integer,
  invitee VARCHAR2(32)
);

INSERT INTO invitees values (1, 'A');
INSERT INTO invitees values (2, 'B');
INSERT INTO invitees values (3, 'C');
INSERT INTO invitees values (4, 'D');
INSERT INTO invitees values (5, 'E');
INSERT INTO invitees values (6, 'F');

COMMIT;

INSERT INTO rules values (1,people_tab('A'), people_tab('B'));
INSERT INTO rules values (2,people_tab('A'), people_tab('C'));

INSERT INTO rules values (3,people_tab('C'), people_tab('A'));
INSERT INTO rules values (4,people_tab('C'), people_tab('D'));

INSERT INTO rules values (5, people_tab('E'), people_tab('A'));
INSERT INTO rules values (6, people_tab('E'), people_tab('B'));
INSERT INTO rules values (7, people_tab('E'), people_tab('C'));

INSERT INTO rules values (8, people_tab('F'), people_tab('C'));
INSERT INTO rules values (9, people_tab('F'), people_tab('D'));

INSERT INTO rules values (10, people_tab('C','D'), people_tab('B'));
INSERT INTO rules values (11, people_tab('C','D'), people_tab('E'));
INSERT INTO rules values (12, people_tab('C','D'), people_tab('F'));

INSERT INTO rules values (13, people_tab('A','B'), people_tab('D'));

COMMIT;

    Łukasz’ solution becomes as follows:

    -- Lateral derived tables are used in the solution because an "ORA-00932: inconsistent datatypes" message is received when the join is written in a more normal way.
-- The following event is required because Oracle does not officially support lateral derived tables
ALTER session SET events '22829 trace name context forever';

SET sqlblanklines on

CREATE OR REPLACE VIEW if_they_come AS
WITH common_table_expression(lvl, if_they_come) AS
(
  -- The first solution is the superset of invitees
  SELECT 1, CAST(MULTISET(SELECT invitee FROM invitees) AS people_tab)
  FROM dual

  UNION ALL

  -- Generate new solutions by shrinking the current set
  -- If the current set contains all the members of if_they_come and they_will_come, then remove the members of they_will_come from the current set
  -- Note that they_will_come only has one member
  SELECT lvl + 1, c.if_they_come MULTISET EXCEPT r.they_will_come
  FROM common_table_expression c, LATERAL(SELECT r.they_will_come FROM rules r WHERE (r.if_they_come MULTISET UNION r.they_will_come) SUBMULTISET c.if_they_come) r
  WHERE lvl > 0
)
-- Eliminate duplicates
SELECT column_value AS if_they_come
FROM (SELECT SET(CAST(MULTISET(SELECT if_they_come FROM common_table_expression) AS solutions_tab)) AS solutions FROM dual) s, TABLE(s.solutions);

-- Identify the solutions which don't have subsets
SELECT i1.if_they_come
FROM if_they_come i1
WHERE NOT EXISTS(SELECT * FROM if_they_come i2 WHERE i2.if_they_come SUBMULTISET OF i1.if_they_come AND i2.if_they_come != i1.if_they_come);
  42. Iggy Fernandez
    June 4, 2012 at 4:01 pm | #43
    Reply | Quote

    Iggy Fernandez :

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

    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

  1. June 2, 2012 at 7:28 am | #1
    NoCOUG contest take #1: the Es-cu-el spell | The Pythian Blog
  2. June 27, 2012 at 7:35 am | #2
    My first experience with Cassandra – Part 1 | The Pythian Blog

Leave a Reply

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

Gravatar
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 )

Cancel

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 399 other followers