NoCOUG Contest Take #1: The Es-cu-el Spell

As heralded by Iggy Fernandez and Gwen Shapira, NoCOUG has launched its Third International SQL vs. NoSQL Challenge.

Pythian is sponsoring the challenge, so I decided not to take part in the contest. However, I’m still having a crack at the problem just for fun. So, here is my first take on it.

The wicked schema

I created two tables to store the information that describes the problem. The first one is a simple lookup table for the invitees’ names.
Note that I chose the IDs as powers of 2 on purpose. This is necessary for the magic es-cue-el spell to work.

create table attendees (id number, name varchar2(30));
insert into attendees values (1, 'Albus Dumbledore');
insert into attendees values (2, 'Burdock Muldoon');
insert into attendees values (4, 'Carlotta Pinkstone');
insert into attendees values (8, 'Daisy Dodderidge');
insert into attendees values (16, 'Elfrida Clagg');
insert into attendees values (32, 'Falco Aesalon');
commit;

The second table stores the “who-follows-who” rules. This table has a column to identify the invitee (ATTENDEE_ID) and another one to indicate who that person will follow to the ball (FOLLOWS). If a person attendance depends on two or more people attending, the FOLLOWS column will hold the sum of those people’s IDs.

create table rules (attendee_id number, follows number);
truncate table rules;
insert into rules values (2, 1);
insert into rules values (4, 1);
insert into rules values (1, 4);
insert into rules values (8, 4);
insert into rules values (1, 16);
insert into rules values (2, 16);
insert into rules values (4, 16);
insert into rules values (4, 32);
insert into rules values (8, 32);
insert into rules values (2, 4 + 8);
insert into rules values (16, 4 + 8);
insert into rules values (32, 4 + 8);
insert into rules values (8, 1 + 2);
commit;

So, to prepare the spell, I created these two tables, populated them with the magical data, and added them to a cauldron with some cane toad venom, a brown snake fillet, one Red Back spider eye, two saltie crocodile teeth, and irukanji stingers, and voilà! This is a complicated spell, though, and comes with a warning: If you try to say it at once, your tongue may take a pretzel shape.

So let’s take this slowly…

The solution candidates

First of all, we will need to test all the possible solutions to verify which ones actually solve the problem and to find the optimal one, i.e. the minimum set of people we need to convince to come to the ball so that all the others will follow.

The number of possible solutions is the following sum of combinations:

(n choose 1) + (n choose 2) + … + (n choose n) = 2ⁿ – 1

where n is the total number of invitees.

The following query will list all the possible solutions for the problem, including their size, which is the number of people in each one:

with
cnt as (
  select count(*) cnt
  from attendees
),
ids as (
  select level id
  from cnt
  connect by level < power(2,cnt)
),
options as (
  select
    i.id,
    listagg(a.name,', ') within group (order by a.name) list_of_people,
    count(*) number_of_people
  from ids i
    join attendees a on bitand(a.id, i.id) != 0
  group by i.id
),

The OPTIONS query above lists all the possible solutions and the initial set of people for each.

Adding the rules

Next we join all the possible solutions (OPTIONS view) with the rules that define the dependencies between attendees (RULES table):

q1 as (
  select
    q0.id, q0.number_of_people, q0.list_of_people,
    q0.id+sum(distinct a0.attendee_id)-bitand(q0.id,sum(distinct a0.attendee_id)) quorum,
    case when q0.id+sum(distinct a0.attendee_id)-bitand(q0.id,sum(distinct a0.attendee_id)) = 63 then 1 else 99 end degrees,
    1 lvl
  from options q0
    join rules a0 on bitand(q0.id, a0.follows) = a0.follows
  group by q0.id, q0.number_of_people, q0.list_of_people
),

The join clause matches each possible solution with the people who will follow the initial quorum for that solution.
The query then calculates the new quorum, which is the union of the initial group of people with the new attendees matched by this join.
The ID for the quorum is the bitwise OR of the solution ID with the IDs of each new attendees. Since Oracle doesn’t have a bitwise OR function, it’s calculated as:

"BITOR"(x, y) = x + y - BITAND(x, y)

If the new quorum totals 63, it means that every invitee is now going to the ball, which confirms the solution is viable. In this case, the query assigns 1 to the DEGREES columns, meaning that the solution was achieved with only 1 degree of influence.
Otherwise, it assigns a very high value to the degree to indicate that the solution hasn’t been confirmed yet.

Here we go again…

If the solution wasn’t solved with one degree of influence, it can still be solved with 2 or more degrees. So we continue joining the query above with similar versions of itself, enough times to cover all the possible solutions. All the rule examples provided by NoCOUG can be solved with three degrees of influence, so we only need to add two more joins:

q2 as (
  select
    q1.id, q1.number_of_people, q1.list_of_people,
    q1.quorum+sum(distinct a1.attendee_id)-bitand(q1.quorum,sum(distinct a1.attendee_id)) quorum,
    least(q1.degrees, case when q1.quorum+sum(distinct a1.attendee_id)-bitand(q1.quorum,sum(distinct a1.attendee_id)) = 63 then max(q1.lvl)+1 else 99 end) degrees,
    max(q1.lvl)+1 lvl
  from
    q1
    join rules a1 on bitand(q1.quorum, a1.follows) = a1.follows
  group by q1.id, q1.number_of_people, q1.quorum, q1.list_of_people, q1.degrees
),
q3 as (
  select
    q2.id, q2.number_of_people, q2.list_of_people,
    q2.quorum+sum(distinct a2.attendee_id)-bitand(q2.quorum,sum(distinct a2.attendee_id)) quorum,
    least(q2.degrees, case when q2.quorum+sum(distinct a2.attendee_id)-bitand(q2.quorum,sum(distinct a2.attendee_id)) = 63 then max(q2.lvl)+1 else 99 end) degrees,
    max(q2.lvl)+1 lvl
  from
    q2
    join rules a2 on bitand(q2.quorum, a2.follows) = a2.follows
  group by q2.id, q2.number_of_people, q2.quorum, q2.list_of_people, q2.degrees
),

Note: Oracle 11gR2 introduces the Recursive Subquery Factoring feature, which would be a nice alternative to explicitly joining the query with itself multiple times as above. Recursive Subquery Factoring, though, has many limitations. One of them is that aggregation functions can’t be used. Therefore, I couldn’t use this feature in my solution, since it does require the use of the SUM function.

The multiple joins above continue to apply the rules to the updated quorum, calculating the new attendance and degrees of influence after each iteration, as explained before.

Abracadabra!

After these three joins, we discard all the solutions that haven’t reached a full quorum (6 people => QUORUM = 63), and select only the optimal solutions, i.e., the ones that don’t contain a subset which is also a solution or, in other words, do not include an invitee whose presence is guaranteed by the presence of the other invitees in the answer:

filtered as (
  select id, list_of_people, quorum, number_of_people, degrees
  from q3
  where quorum = 63
)
select a.list_of_people, a.degrees
from filtered a
where not exists (select 1
                  from filtered b
                  where b.number_of_people < a.number_of_people
                    and bitand(b.id, a.id) = b.id)
order by a.degrees, a.list_of_people
/

The final output shows the optimal solutions with the degrees of influence required by each one:

LIST_OF_PEOPLE          DEGREES
-------------------- ----------
Carlotta Pinkstone            2
Falco Aesalon                 2
Albus Dumbledore              3
Elfrida Clagg                 3

So, is that it?

Well, for the appreciators of the es-cu-el white magic, yes, that’s as far as I’ll go.

However, this year NoCOUG has opened its doors for the practitioners of a much darker kind of wizardry: something called NO-es-cu-el!!! I’m no black wizard (yet), but learning new magic and spells is always compelling since it can lead to great powers.

So, I’ll also post my attempt at using black magic. But not in this post and not now. Mixing es-cu-el, no-es-cu-el, and a too long blog post may have disastrous results and I shall not act recklessly when handling such powers.

So, stay tuned and thanks for reading thus far!

Full query

with
cnt as (
  select count(*) cnt
  from attendees
),
ids as (
  select level id
  from cnt
  connect by level < power(2,cnt)
),
options as (
  select
    i.id,
    listagg(a.name,', ') within group (order by a.name) list_of_people,
    count(*) number_of_people
  from ids i
    join attendees a on bitand(a.id, i.id) != 0
  group by i.id
),
q1 as (
  select
    q0.id, q0.number_of_people, q0.list_of_people,
    q0.id+sum(distinct a0.attendee_id)-bitand(q0.id,sum(distinct a0.attendee_id)) quorum,
    case when q0.id+sum(distinct a0.attendee_id)-bitand(q0.id,sum(distinct a0.attendee_id)) = 63 then 1 else 99 end degrees,
    1 lvl
  from options q0
    join rules a0 on bitand(q0.id, a0.follows) = a0.follows
  group by q0.id, q0.number_of_people, q0.list_of_people
),
q2 as (
  select
    q1.id, q1.number_of_people, q1.list_of_people,
    q1.quorum+sum(distinct a1.attendee_id)-bitand(q1.quorum,sum(distinct a1.attendee_id)) quorum,
    least(q1.degrees, case when q1.quorum+sum(distinct a1.attendee_id)-bitand(q1.quorum,sum(distinct a1.attendee_id)) = 63 then max(q1.lvl)+1 else 99 end) degrees,
    max(q1.lvl)+1 lvl
  from
    q1
    join rules a1 on bitand(q1.quorum, a1.follows) = a1.follows
  group by q1.id, q1.number_of_people, q1.quorum, q1.list_of_people, q1.degrees
),
q3 as (
  select
    q2.id, q2.number_of_people, q2.list_of_people,
    q2.quorum+sum(distinct a2.attendee_id)-bitand(q2.quorum,sum(distinct a2.attendee_id)) quorum,
    least(q2.degrees, case when q2.quorum+sum(distinct a2.attendee_id)-bitand(q2.quorum,sum(distinct a2.attendee_id)) = 63 then max(q2.lvl)+1 else 99 end) degrees,
    max(q2.lvl)+1 lvl
  from
    q2
    join rules a2 on bitand(q2.quorum, a2.follows) = a2.follows
  group by q2.id, q2.number_of_people, q2.quorum, q2.list_of_people, q2.degrees
),
filtered as (
  select id, list_of_people, quorum, number_of_people, degrees
  from q3
  where quorum = 63
)
select a.list_of_people, a.degrees
from filtered a
where not exists (select 1
                  from filtered b
                  where b.number_of_people < a.number_of_people
                    and bitand(b.id, a.id) = b.id)
order by a.degrees, a.list_of_people
/

The 8 NoCOUG sample datasets

-- Dataset #1
-- 1. Burdock Muldoon and Carlotta Pinkstone will both come if Albus Dumbledore comes
-- 2. Albus Dumbledore and Daisy Dodderidge will both come if Carlotta Pinkstone comes
-- 3. Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone will all come if Elfrida Clagg comes
-- 4. Carlotta Pinkstone and Daisy Dodderidge will both come come if Falco Aesalon comes
-- 5. Burdock Muldoon, Elfrida Clagg, and Falco Aesalon will all come if Carlotta Pinkstone and Daisy Dodderidge both come
-- 6. Daisy Dodderidge will come if Albus Dumbledore and Burdock Muldoon both come
truncate table rules;
insert into rules values (2, 1);
insert into rules values (4, 1);
insert into rules values (1, 4);
insert into rules values (8, 4);
insert into rules values (1, 16);
insert into rules values (2, 16);
insert into rules values (4, 16);
insert into rules values (4, 32);
insert into rules values (8, 32);
insert into rules values (2, 4 + 8);
insert into rules values (16, 4 + 8);
insert into rules values (32, 4 + 8);
insert into rules values (8, 1 + 2);
commit;
-- Answers
-- a. Albus Dumbledore
-- b. Carlotta Pinkstone
-- c. Elfrida Clagg
-- d. Falcon Aesalon
-- Dataset #2
-- 1. Carlotta Pinkstone will come if Albus Dumbledore and Burdock Muldoon both come
-- 2. Falco Aesalon will come if Daisy Dodderidge and Elfrida Clagg both come
truncate table rules;
insert into rules values (4, 3);
insert into rules values (32, 24);
commit;
-- Answers
-- a. Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg
-- Dataset #3
-- 1. Carlotta Pinkstone will come if Albus Dumbledore and Burdock Muldoon both come
-- 2. Falco Aesalon will come if Daisy Dodderidge and Elfrida Clagg both come
-- 3. Carlotta Pinkstone and Falco Aesalon will both come if Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg all come
truncate table rules;
insert into rules values (4, 3);
insert into rules values (32, 24);
insert into rules values (4, 35);
insert into rules values (32, 35);
commit;
-- Answers
-- a. Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg
-- Dataset #4
-- 1. Burdock Muldoon will come if Albus Dumbledore comes
-- 2. Carlotta Pinkstone will come if Burdock Muldoon comes
-- 3. Carlotta Pinkstone will come if Albus Dumbledore comes
-- 4. Elfrida Clagg will come if Daisy Dodderidge comes
-- 5. Falco Aesalon will come if Elfrida Clagg comes
-- 6. Falco Aesalon will come if Daisy Dodderidge comes
truncate table rules;
insert into rules values (2, 1);
insert into rules values (4, 2);
insert into rules values (4, 1);
insert into rules values (16, 8);
insert into rules values (32, 16);
insert into rules values (32, 8);
commit;
-- Answers
-- a. Albus Dumbledore and Daisy Dodderidge
-- Dataset #5
-- 1. Burdock Muldoon will come if Albus Dumbledore comes
-- 2. Carlotta Pinkstone will come if Burdock Muldoon comes
-- 3. Carlotta Pinkstone will come if Albus Dumbledore comes
-- 4. Elfrida Clagg will come if Daisy Dodderidge comes
-- 5. Falco Aesalon will come if Elfrida Clagg comes
-- 6. Falco Aesalon will come if Daisy Dodderidge comes
-- 7. Carlotta Pinkstone and Falco Aesalon will both come if Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg all come
truncate table rules;
insert into rules values (2, 1);
insert into rules values (4, 2);
insert into rules values (4, 1);
insert into rules values (16, 8);
insert into rules values (32, 16);
insert into rules values (32, 8);
insert into rules values (4, 35);
insert into rules values (32, 35);
commit;
-- Answers
-- a. Albus Dumbledore and Daisy Dodderidge
-- Dataset #6
-- 1. Burdock Muldoon will come if Albus Dumbledore comes
-- 2. Carlotta Pinkstone will come if Burdock Muldoon comes
-- 3. Carlotta Pinkstone will come if Albus Dumbledore comes
-- 4. Elfrida Clagg will come if Daisy Dodderidge comes
-- 5. Falco Aesalon will come if Elfrida Clagg comes
-- 6. Falco Aesalon will come if Daisy Dodderidge comes
-- 7. Carlotta Pinkstone will come if Burdock Muldoon comes
-- 8. Albus Dumbledore will come if Carlotta Pinkstone comes
-- 9. Albus Dumbledore will come if  Burdock Muldoon comes
-- 10. Falco Aesalon will come if Elfrida Clagg comes
-- 11. Daisy Dodderidge will come if Falco Aesalon comes
-- 12. Daisy Dodderidge will come if Elfrida Clagg comes
truncate table rules;
insert into rules values (2, 1);
insert into rules values (4, 2);
insert into rules values (4, 1);
insert into rules values (16, 8);
insert into rules values (32, 16);
insert into rules values (32, 8);
insert into rules values (4, 2);
insert into rules values (1, 4);
insert into rules values (1, 2);
insert into rules values (32, 16);
insert into rules values (8, 32);
insert into rules values (8, 16);
commit;
-- Answers
-- a. Albus Dumbledore and Daisy Dodderidge
-- b. Albus Dumbledore and Elfrida Clagg
-- c. Albus Dumbledore and Falco Aesalon
-- d. Burdock Muldoon and Daisy Dodderidge
-- e. Burdock Muldoon and Elfrida Clagg
-- f. Burdock Muldoon and Falco Aesalon
-- g. Carlotta Pinkstone and Daisy Dodderidge
-- h. Carlotta Pinkstone and Elfrida Clagg
-- i. Carlotta Pinkstone and Falco Aesalon
-- Dataset #7
-- 1. Albus Dumbledore will come if Burdock Muldoon, Carlotta Pinkstone, and Daisy Dodderidge all come
-- 2. Albus Dumbledore will come if Carlotta Pinkstone, Daisy Dodderidge, and Elfrida Clagg all come
-- 3. Albus Dumbledore will come if Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon all come
truncate table rules;
insert into rules values (1, 14);
insert into rules values (1, 28);
insert into rules values (1, 56);
commit;
-- Answers
-- a. Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon
-- Dataset #8
-- 1. Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon will all come if Albus Dumbledore comes
-- 2. Albus Dumbledore will come if Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon all come
truncate table rules;
insert into rules values (2, 1);
insert into rules values (4, 1);
insert into rules values (8, 1);
insert into rules values (16, 1);
insert into rules values (32, 1);
insert into rules values (1, 62);
commit;
-- Answers
-- a. Albus Dumbledore
-- b. Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon