Home > NoCOUG, Oracle, SQL > Results of the Third International NoCOUG SQL Challenge

Results of the Third International NoCOUG SQL Challenge


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)

Categories: NoCOUG, Oracle, SQL
  1. November 22, 2012 at 2:56 am

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

  1. No trackbacks yet.

Leave a Reply

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

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 )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 744 other followers

%d bloggers like this: