SQL Solution for the Third International NoCOUG SQL & NoSQL Challenge
August 17th, 2012 By Frank Zhou
SQL vs NoSQL: Third International NoCOUG SQL & NoSQL Challenge sponsored by Pythian
As published in the 102nd 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.
------------------SQL Solution : SQL vs NoSQL: Third International NoCOUG SQL & NoSQL Challenge ----------------
WITH TAB AS
(SELECT ATTENDEES, DEPENDING_ON, REGEXP_COUNT(DEPENDING_ON, ',' ) +1 AS CNT, ROWNUM AS RULE_ID
FROM
(SELECT DEPENDING_ON, LISTAGG(D_ATTENDEE, ',' ) WITHIN GROUP(ORDER BY D_ATTENDEE) AS ATTENDEES
FROM
(SELECT DISTINCT REGEXP_SUBSTR(ATTENDEES,'[^,]+',1,LEVEL) AS D_ATTENDEE, DEPENDING_ON
FROM
(SELECT REGEXP_REPLACE(ATTENDEES, ', +', ',') AS ATTENDEES,
REGEXP_REPLACE(DEPENDING_ON , ', +', ',') AS DEPENDING_ON, RULE_ID
FROM RULES
)
CONNECT BY PRIOR RULE_ID = RULE_ID
AND LEVEL <= REGEXP_COUNT(ATTENDEES, ',' ) +1
AND PRIOR dbms_random.string ('p', 20) IS NOT NULL
)
GROUP BY DEPENDING_ON
)
),
DATA(PATH, ROOT, RULE_ID) AS
(SELECT CAST(T.DEPENDING_ON||','||T.ATTENDEES||',' AS VARCHAR2(4000)) AS PATH, DEPENDING_ON AS ROOT, RULE_ID
FROM TAB T
UNION ALL
SELECT OLD.PATH||','||NEW.DEPENDING_ON||','||NEW.ATTENDEES||',' AS PATH, OLD.ROOT, NEW.RULE_ID
FROM DATA OLD, TAB NEW
WHERE EXISTS
(SELECT NULL
FROM TABLE(CAST(MULTISET(SELECT REGEXP_SUBSTR(NEW.DEPENDING_ON ,'[^,]+',1,LEVEL)
FROM DUAL
CONNECT BY LEVEL <= REGEXP_COUNT(NEW.DEPENDING_ON, ',' ) +1
) AS SYS.DBMS_DEBUG_VC2COLL ) )
GROUP BY NEW.DEPENDING_ON
HAVING SUM(CASE WHEN INSTR(','||OLD.PATH||',', ','||COLUMN_VALUE||',')>0
THEN 1
END) = NEW.CNT
)
AND NEW.RULE_ID <> OLD.RULE_ID
AND EXISTS
(SELECT NULL
FROM TABLE(CAST(MULTISET(SELECT REGEXP_SUBSTR(NEW.ATTENDEES ,'[^,]+',1,LEVEL)
FROM DUAL
CONNECT BY LEVEL <= REGEXP_COUNT(NEW.ATTENDEES, ',' ) +1
) AS SYS.DBMS_DEBUG_VC2COLL ) )
GROUP BY NEW.ATTENDEES
HAVING SUM(CASE WHEN INSTR(','||OLD.PATH||',', ','||COLUMN_VALUE||',')<1
THEN 1
END ) > 0
)
)
CYCLE RULE_ID SET IS_CYCLE TO '1' DEFAULT '0',
BASE AS
(SELECT ROOT AS DEPENDING_ON, PATH
FROM
(SELECT ROOT, PATH, REGEXP_COUNT(PATH, ',') P_CNT,
MAX(REGEXP_COUNT(PATH, ',')) OVER (PARTITION BY ROOT) MAX_PATH_CNT
FROM
(SELECT ROOT, LISTAGG(COLUMN_VALUE, ',' ) WITHIN GROUP (ORDER BY COLUMN_VALUE) AS PATH
FROM (SELECT ROOT, PATH, ROWNUM AS ID FROM DATA WHERE IS_CYCLE = 0 ) A,
TABLE(SET(CAST(MULTISET(SELECT REGEXP_SUBSTR(A.PATH ,'[^,]+',1,LEVEL)
FROM DUAL
CONNECT BY LEVEL <= REGEXP_COUNT(A.PATH, ',' ) +1
) AS SYS.DBMS_DEBUG_VC2COLL )) )
GROUP BY ROOT, ID
)
)
WHERE P_CNT = MAX_PATH_CNT
),
NUM_OF_PERSON AS
(SELECT XMLCAST(XMLQUERY ('fn:count( fn:distinct-values(ora:tokenize($str, ",")))'
PASSING REGEXP_REPLACE(CONCAT(str, ','), ', +', ',') AS "str"
RETURNING CONTENT
) AS NUMBER ) AS num
FROM
(SELECT LISTAGG(DEPENDING_ON||','||ATTENDEES, ',') WITHIN GROUP (ORDER BY NULL) AS str
FROM RULES)
),
COMBINATION (PATH, PATH_SET, DEPENDING_ON, DEPEND_SET ) AS
(SELECT PATH, CAST(MULTISET(SELECT REGEXP_SUBSTR(PATH ,'[^,]+',1,LEVEL)
FROM DUAL
CONNECT BY LEVEL <= REGEXP_COUNT(PATH, ',' ) +1
) AS SYS.DBMS_DEBUG_VC2COLL) AS PATH_SET,
DEPENDING_ON,
CAST(MULTISET(SELECT REGEXP_SUBSTR(DEPENDING_ON ,'[^,]+',1,LEVEL)
FROM DUAL
CONNECT BY LEVEL <= REGEXP_COUNT(DEPENDING_ON, ',' ) +1
) AS SYS.DBMS_DEBUG_VC2COLL ) AS DEPEND_SET
FROM BASE
UNION ALL
SELECT NEW.PATH,
OLD.PATH_SET MULTISET UNION DISTINCT
CAST(MULTISET(SELECT REGEXP_SUBSTR(NEW.PATH ,'[^,]+',1,LEVEL)
FROM DUAL
CONNECT BY LEVEL <= REGEXP_COUNT(NEW.PATH, ',' ) +1
) AS SYS.DBMS_DEBUG_VC2COLL) AS PATH_SET,
NEW.DEPENDING_ON,
OLD.DEPEND_SET MULTISET UNION DISTINCT
( CAST(MULTISET(SELECT REGEXP_SUBSTR(NEW.DEPENDING_ON ,'[^,]+',1,LEVEL)
FROM DUAL
CONNECT BY LEVEL <= REGEXP_COUNT(NEW.DEPENDING_ON, ',' ) +1
) AS SYS.DBMS_DEBUG_VC2COLL) MULTISET EXCEPT OLD.PATH_SET
)
FROM COMBINATION OLD, BASE NEW
WHERE NEW.DEPENDING_ON <> OLD.DEPENDING_ON
AND OLD.PATH <> NEW.PATH
AND CAST(MULTISET(SELECT REGEXP_SUBSTR(NEW.PATH ,'[^,]+',1,LEVEL)
FROM DUAL
CONNECT BY LEVEL <= REGEXP_COUNT(NEW.PATH, ',' ) +1
) AS SYS.DBMS_DEBUG_VC2COLL)
NOT SUBMULTISET OF OLD.PATH_SET
AND CARDINALITY( SET(OLD.PATH_SET) ) < ( SELECT NUM FROM NUM_OF_PERSON)
)
CYCLE DEPENDING_ON SET IS_CYCLE TO '1' DEFAULT '0',
ALL_SET AS
(SELECT DISTINCT LISTAGG(COLUMN_VALUE, ',') WITHIN GROUP (ORDER BY COLUMN_VALUE) AS DEPEND_SET
FROM
(SELECT DEPEND_SET, ROWNUM AS ID
FROM COMBINATION A
WHERE IS_CYCLE = 0
AND CARDINALITY(PATH_SET) = (SELECT NUM FROM NUM_OF_PERSON )
), TABLE(DEPEND_SET)
GROUP BY ID
)
SELECT DISTINCT DEPEND_SET
FROM ALL_SET ORG
WHERE NOT EXISTS
(SELECT NULL
FROM ALL_SET B, XMLTABLE('fn:count( fn:distinct-values(ora:tokenize($str, ",")))'
PASSING B.DEPEND_SET||','||ORG.DEPEND_SET AS "str"
COLUMNS CNT number PATH '.' )
WHERE B.DEPEND_SET <>ORG.DEPEND_SET
AND CNT = REGEXP_COUNT(ORG.DEPEND_SET, ',' ) +1
)
ORDER BY DEPEND_SET;
-------------------------------------------TESTING DATA------------------------------------
CREATE TABLE RULES
(
RULE_ID NUMBER,
ATTENDEES VARCHAR2(1000 BYTE),
DEPENDING_ON VARCHAR2(1000 BYTE)
);
-- Data set #1
truncate table RULES;
INSERT INTO RULES VALUES(1,'Burdock Muldoon, Carlotta Pinkstone','Albus Dumbledore');
INSERT INTO RULES VALUES(2,'Albus Dumbledore, Daisy Dodderidge','Carlotta Pinkstone');
INSERT INTO RULES VALUES(3,'Albus Dumbledore, Burdock Muldoon, Carlotta Pinkstone','Elfrida Clagg');
INSERT INTO RULES VALUES(4,'Carlotta Pinkstone, Daisy Dodderidge','Falco Aesalon');
INSERT INTO RULES VALUES(5,'Burdock Muldoon, Elfrida Clagg,Falco Aesalon','Carlotta Pinkstone,Daisy Dodderidge');
INSERT INTO RULES VALUES(6,'Daisy Dodderidge','Albus Dumbledore, Burdock Muldoon');
commit;
-- result:
-- a. Albus Dumbledore
-- b. Carlotta Pinkstone
-- c. Elfrida Clagg
-- d. Falcon Aesalon
-- Data set #2
truncate table RULES;
INSERT INTO RULES VALUES(1,'Carlotta Pinkstone','Albus Dumbledore,Burdock Muldoon');
INSERT INTO RULES VALUES(2,'Falco Aesalon','Daisy Dodderidge,Elfrida Clagg');
commit;
a) Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg
-- Data set #3
truncate table RULES;
INSERT INTO RULES VALUES(1,'Carlotta Pinkstone','Albus Dumbledore,Burdock Muldoon');
INSERT INTO RULES VALUES(2,'Falco Aesalon','Daisy Dodderidge,Elfrida Clagg');
INSERT INTO RULES VALUES(3,'Carlotta Pinkstone,Falco Aesalon','Albus Dumbledore, Burdock Muldoon,Daisy Dodderidge,Elfrida Clagg');
commit;
(a) Albus Dumbledore, Burdock Muldoon, Daisy Dodderidge, and Elfrida Clagg
-- Data set #4
truncate table RULES;
INSERT INTO RULES VALUES(1,'Burdock Muldoon','Albus Dumbledore');
INSERT INTO RULES VALUES(2,'Carlotta Pinkstone','Burdock Muldoon');
INSERT INTO RULES VALUES(3,'Carlotta Pinkstone','Albus Dumbledore');
INSERT INTO RULES VALUES(4,'Elfrida Clagg','Daisy Dodderidge');
INSERT INTO RULES VALUES(5,'Falco Aesalon','Elfrida Clagg');
INSERT INTO RULES VALUES(6,'Falco Aesalon','Daisy Dodderidge');
commit;
(a) Albus Dumbledore and Daisy Dodderidge
-- Data set #5
truncate table RULES;
INSERT INTO RULES VALUES(1,'Burdock Muldoon','Albus Dumbledore');
INSERT INTO RULES VALUES(2,'Carlotta Pinkstone','Burdock Muldoon');
INSERT INTO RULES VALUES(3,'Carlotta Pinkstone','Albus Dumbledore');
INSERT INTO RULES VALUES(4,'Elfrida Clagg','Daisy Dodderidge');
INSERT INTO RULES VALUES(5,'Falco Aesalon','Elfrida Clagg');
INSERT INTO RULES VALUES(6,'Falco Aesalon','Daisy Dodderidge');
INSERT INTO RULES VALUES(7,'Carlotta Pinkstone,Falco Aesalon','Albus Dumbledore, Burdock Muldoon,Daisy Dodderidge,Elfrida Clagg');
commit;
(a) Albus Dumbledore and Daisy Dodderidge
-- Data set #6
truncate table RULES;
INSERT INTO RULES VALUES(1,'Burdock Muldoon','Albus Dumbledore');
INSERT INTO RULES VALUES(2,'Carlotta Pinkstone','Burdock Muldoon');
INSERT INTO RULES VALUES(3,'Carlotta Pinkstone','Albus Dumbledore');
INSERT INTO RULES VALUES(4,'Elfrida Clagg','Daisy Dodderidge');
INSERT INTO RULES VALUES(5,'Falco Aesalon','Elfrida Clagg');
INSERT INTO RULES VALUES(6,'Falco Aesalon','Daisy Dodderidge');
INSERT INTO RULES VALUES(7,'Carlotta Pinkstone','Burdock Muldoon');
INSERT INTO RULES VALUES(8,'Albus Dumbledore','Carlotta Pinkstone');
INSERT INTO RULES VALUES(9,'Albus Dumbledore','Burdock Muldoon');
INSERT INTO RULES VALUES(10,'Falco Aesalon','Elfrida Clagg');
INSERT INTO RULES VALUES(11,'Daisy Dodderidge','Falco Aesalon');
INSERT INTO RULES VALUES(12,'Daisy Dodderidge','Elfrida Clagg');
commit;
-- a. Albus Dumbledore, Daisy Dodderidge
-- b. Albus Dumbledore, Elfrida Clagg
-- c. Albus Dumbledore, Falco Aesalon
-- d. Burdock Muldoon, Daisy Dodderidge
-- e. Burdock Muldoon, Elfrida Clagg
-- f. Burdock Muldoon, Falco Aesalon
-- g. Carlotta Pinkstone, Daisy Dodderidge
-- h. Carlotta Pinkstone, Elfrida Clagg
-- i. Carlotta Pinkstone, Falco Aesalon
-- Data set #7
truncate table RULES;
INSERT INTO RULES VALUES(1,'Albus Dumbledore','Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge');
INSERT INTO RULES VALUES(2,'Albus Dumbledore','Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg');
INSERT INTO RULES VALUES(3,'Albus Dumbledore','Daisy Dodderidge, Elfrida Clagg, Falco Aesalon');
commit;
a) Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon
-- Data set #8
truncate table RULES;
INSERT INTO RULES VALUES(1,'Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, Falco Aesalon','Albus Dumbledore');
INSERT INTO RULES VALUES(2,'Albus Dumbledore,Falco Aesalon, Elfrida Clagg','Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, Falco Aesalon');
commit;
(a) Albus Dumbledore
(b) Burdock Muldoon, Carlotta Pinkstone, Daisy Dodderidge, Elfrida Clagg, and Falco Aesalon
-- Data set #9
truncate table RULES;
INSERT INTO RULES VALUES(1,'Carlotta Pinkstone, Daisy Dodderidge','Albus Dumbledore,Burdock Muldoon');
INSERT INTO RULES VALUES(2,'Albus Dumbledore,Falco Aesalon','Daisy Dodderidge, Elfrida Clagg');
commit;
-- a.Albus Dumbledore,Burdock Muldoon,Elfrida Clagg
-- b.Burdock Muldoon,Daisy Dodderidge,Elfrida Clagg
----------------------------------------------------TEST CASES------------------------------
-- Data set #1
SQL> /
DEPEND_SET
--------------------------------------------------------------------------------
Albus Dumbledore
Carlotta Pinkstone
Elfrida Clagg
Falco Aesalon
-- Data set #2
SQL> /
DEPEND_SET
--------------------------------------------------------------------------------
Albus Dumbledore,Burdock Muldoon,Daisy Dodderidge,Elfrida Clagg
-- Data set #3
SQL>
SQL> /
DEPEND_SET
--------------------------------------------------------------------------------
Albus Dumbledore,Burdock Muldoon,Daisy Dodderidge,Elfrida Clagg
-- Data set #4
SQL> /
DEPEND_SET
--------------------------------------------------------------------------------
Albus Dumbledore,Daisy Dodderidge
-- Data set #5
SQL> /
DEPEND_SET
--------------------------------------------------------------------------------
Albus Dumbledore,Daisy Dodderidge
-- Data set #6
SQL> /
DEPEND_SET
--------------------------------------------------------------------------------
Albus Dumbledore,Daisy Dodderidge
Albus Dumbledore,Elfrida Clagg
Albus Dumbledore,Falco Aesalon
Burdock Muldoon,Daisy Dodderidge
Burdock Muldoon,Elfrida Clagg
Burdock Muldoon,Falco Aesalon
Carlotta Pinkstone,Daisy Dodderidge
Carlotta Pinkstone,Elfrida Clagg
Carlotta Pinkstone,Falco Aesalon
9 rows selected.
-- Data set #7
SQL> /
DEPEND_SET
--------------------------------------------------------------------------------
Burdock Muldoon,Carlotta Pinkstone,Daisy Dodderidge,Elfrida Clagg,Falco Aesalon
-- Data set #8
SQL> /
DEPEND_SET
--------------------------------------------------------------------------------
Albus Dumbledore
Burdock Muldoon,Carlotta Pinkstone,Daisy Dodderidge,Elfrida Clagg,Falco Aesalon
-- Data set #9
SQL> /
DEPEND_SET
--------------------------------------------------------------------------------
Albus Dumbledore,Burdock Muldoon,Elfrida Clagg
Burdock Muldoon,Daisy Dodderidge,Elfrida Clagg
SQL> spool off;