## Results of the Third International NoCOUG SQL Challenge

Follow @Oratweets

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

The Third International NoCOUG SQL Challenge sponsored by Pythian—*Love Your Data*™ was published in the May 2012 issue of the *NoCOUG Journal*. The winner, Lukasz Pluta of Poland, will receive an Amazon Kindle from contest sponsor Pythian and—in keeping with the pithy pronouncement of Steven Feuerstein that *“some people can perform seeming miracles with straight SQL, but the statements end up looking like pretzels created by somebody who is experimenting with hallucinogens”*—he will be made a knight of the August Order of the Wooden Pretzel.

Some people can perform seeming miracles with straight SQL, but the statements end up looking like pretzels created by somebody who is experimenting with hallucinogens.

**Mind-Boggling Puzzle**

The Wicked Witch of the West had 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 needed an Es-Cue-El or No-Es-Cue-El spell to determine whom she needed to persuade to attend the wizarding ball in order to ensure that all her invitees attend.

**Mind-Blowing Solution**

Master sorcerer Lukasz Pluta simply noted that if we start with a *minimal* set of invitees, then we can *augment* it—exactly one invitee at a time—by applying a sequence of rules until everybody has been included. Therefore, if we start with the *complete* list of invitees, we can *prune* it—exactly one invitee at a time—by applying the *same* sequence of rules but in *reverse* order until we find a minimal set of invitees. Lukasz assigned a power of two to each invitee (Albus = 1, Burdock = 2, Carlotta = 4, Daisy = 8, …) and used binary arithmetic in a recursive SQL query; the anchor member of the query produces the complete list of invitees, while the recursive member prunes one invitee at a time. Here is his stunningly simple solution, with modifications for readability and efficiency; if there is more than one solution, then all of them are listed.

CREATE TABLE invitees ( invitee_id INTEGER, invitee_name VARCHAR2(128) ); INSERT INTO invitees VALUES (1, 'Albus Dumbledore'); INSERT INTO invitees VALUES (2, 'Burdock Muldoon'); INSERT INTO invitees VALUES (4, 'Carlotta Pinkstone'); INSERT INTO invitees VALUES (8, 'Daisy Dodderidge'); INSERT INTO invitees VALUES (16, 'Elfrida Clagg'); INSERT INTO invitees VALUES (32, 'Falco Aesalon'); CREATE TABLE rules ( rule_id INTEGER, they_will_come INTEGER, if_they_come INTEGER ); -- Burdock and Carlotta will come if Albus comes INSERT INTO rules VALUES (1, 2 + 4, 1); -- Albus and Daisy Dodderidge will come if Carlotta comes INSERT INTO rules VALUES (2, 1 + 8, 4); -- Albus, Burdock, and Carlotta will come if Elfrida comes INSERT INTO rules VALUES (3, 1 + 2 + 4, 16); -- Carlotta and Daisy will come if Falco comes INSERT INTO rules VALUES (4, 4 + 8, 32); -- Burdock, Elfrida, and Falco will come if Carlotta and Daisy come INSERT INTO rules VALUES (5, 2 + 16 + 32, 4 + 8); -- Daisy will come if Albus and Burdock come INSERT INTO rules VALUES (6, 8, 1 + 2);

WITH working_sets(lvl, working_set, removed_id, is_leaf) AS ( -- The anchor member of the recursive query SELECT 1 AS lvl, -- The complete list of invitees SUM(invitee_id) AS working_set, 0 AS removed_id, 0 AS is_leaf FROM invitees UNION ALL -- The recursive member of the query SELECT lvl + 1 AS lvl, -- Remove one invitee from the list CASE WHEN i.invitee_id IS NOT NULL THEN s.working_set - i.invitee_id ELSE s.working_set END AS working_set, invitee_id AS removed_id, -- Flag the leaf nodes CASE WHEN i.invitee_id IS NOT NULL THEN 0 ELSE 1 END AS is_leaf FROM working_sets s LEFT OUTER JOIN invitees i ON ( -- The invitee is in the working set BITAND(s.working_set, i.invitee_id) = i.invitee_id -- The invitee will come since some others are coming AND EXISTS ( SELECT * FROM rules r WHERE BITAND(r.they_will_come, i.invitee_id) = i.invitee_id AND BITAND(s.working_set, r.if_they_come) = r.if_they_come ) ) -- Terminate the recursion at leaf nodes WHERE s.is_leaf = 0 ) SEARCH DEPTH FIRST BY working_set SET seq CYCLE lvl SET cycle TO 1 DEFAULT 0, -- Eliminate duplicates candidate_solutions AS ( SELECT DISTINCT working_set AS candidate_solution FROM working_sets -- Only consider leaf nodes WHERE is_leaf = 1 ) -- List minimal sets only SELECT s1.candidate_solution AS solution FROM candidate_solutions s1 WHERE NOT EXISTS ( SELECT * FROM candidate_solutions s2 WHERE s2.candidate_solution < s1.candidate_solution AND BITAND(s1.candidate_solution, s2.candidate_solution) = s2.candidate_solution );

The above solution limits the number of invitees to the number of bits in the numeric data type. The limitation can be overcome using multisets as follows:

CREATE TYPE invitees_t AS TABLE OF VARCHAR2(32) / CREATE TYPE solutions_t AS TABLE OF invitees_t / 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'); CREATE TABLE rules ( rule_id INTEGER, they_will_come invitees_t, if_they_come invitees_t ) NESTED TABLE if_they_come STORE AS if_they_come_nt NESTED TABLE they_will_come STORE AS they_will_come_nt; INSERT INTO rules VALUES (1, invitees_t('B', 'C'), invitees_t('A')); INSERT INTO rules VALUES (2, invitees_t('A', 'D'), invitees_t('C')); INSERT INTO rules VALUES (3, invitees_t('A', 'B', 'C'), invitees_t('E')); INSERT INTO rules VALUES (4, invitees_t('C', 'D'), invitees_t('F')); INSERT INTO rules VALUES (5, invitees_t('B', 'E', 'F'), invitees_t('C', 'D')); INSERT INTO rules VALUES (6, invitees_t('D'), invitees_t('A', 'B'));

WITH working_sets(lvl, working_set, removed, is_leaf) AS ( -- The anchor member of the recursive query SELECT 1 AS lvl, -- The complete list of invitees CAST(MULTISET(SELECT invitee FROM invitees) AS invitees_t) AS working_set, NULL AS removed, 0 AS is_leaf FROM dual UNION ALL -- The recursive member of the query SELECT lvl + 1 AS lvl, -- Remove one invitee from the list CASE WHEN i.invitee IS NULL THEN s.working_set ELSE s.working_set MULTISET EXCEPT invitees_t(i.invitee) END AS working_set, i.invitee AS removed, -- Flag the leaf nodes CASE WHEN i.invitee IS NULL THEN 1 ELSE 0 END AS is_leaf FROM working_sets s LEFT OUTER JOIN invitees i ON ( -- The invitee is in the working set invitees_t(i.invitee) SUBMULTISET OF s.working_set -- The invitee will come since some others are coming AND EXISTS ( SELECT * FROM rules r WHERE invitees_t(i.invitee) SUBMULTISET OF r.they_will_come AND r.if_they_come SUBMULTISET OF s.working_set ) ) WHERE s.is_leaf = 0 ) CYCLE lvl SET cycle_flag TO 1 DEFAULT 0, -- Eliminate duplicates candidate_solutions AS ( SELECT column_value AS candidate_solution FROM TABLE(SET(CAST(MULTISET( SELECT working_set FROM working_sets -- Only consider leaf nodes WHERE is_leaf = 1 ) AS solutions_t))) ) -- List minimal sets only SELECT s1.candidate_solution AS solution FROM candidate_solutions s1 WHERE NOT EXISTS ( SELECT * FROM candidate_solutions s2 WHERE s2.candidate_solution SUBMULTISET OF s1.candidate_solution AND s2.candidate_solution != s1.candidate_solution );

Lukasz Pluta becomes the fifth knight of the august order, following in the footsteps of Alberto Dell’Era (Italy), Andre Araujo (Australia), Rob van Wijk (Netherlands), and Ilya Chuhnakov (Russia).

**Credits**

The idea for the challenge came from a 1995 paper by C. J. Date titled *“Functional Dependencies are Fun: An Informal Look at the Formal World of FDs.”*

Results of the First International NoCOUG SQL Challenge

Results of the Second International NoCOUG SQL Challenge

I Heart Recursive Subquery Factoring (Recursive Common Table Expressions)

Congratulation Lukasz Pluta for both the solutions, your wooden pretzel is well deserved !

If all possible combinations of working_set, invitee_id could be pre-generated then challenge would be solved using “old-school” connect by. 🙂

Described solution with working sets implemented using connect by instead of recursive subquery factoring looks as following