OraQA

Oracle Question and Answer

  • Do you have a solution to a problem? Do you have an unanswered question? Login and share it with the Oracle community. More...

Oracle News


Entries RSS feed

Comments RSS feed

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;

 

Leave a Reply

You must be logged in to post a comment.

RSS feed for comments on this question