11GR2的递归WITH子查询(新增内容在第二页)

nyfor · 发表于 2010-5-17 09:43

很强劲!

cargoj · 发表于 2010-5-17 10:05

关注一下。

newkid · 发表于 2010-5-19 00:53

下一个例子是我以前发过的首届NoCOUG国际SQL挑战赛:
http://www.itpub.net/thread-1216120-1-1.html

题目：
有一张表记录了骰子的六个面的面值极其出现概率：
CREATE TABLE die (
  face_id NUMBER(2) NOT NULL CHECK (face_id > 0) PRIMARY KEY,
  face_value NUMBER(2) NOT NULL CHECK (face_value > 0),
  probability NUMBER(10,10) NOT NULL CHECK (probability >=0 AND probability <= 1)
);

INSERT INTO die VALUES (1, 1, 1/6 + 1/12);
INSERT INTO die VALUES (2, 3, 1/6 + 1/12);
INSERT INTO die VALUES (3, 4, 1/6 + 1/12);
INSERT INTO die VALUES (4, 5, 1/6 - 1/12);
INSERT INTO die VALUES (5, 6, 1/6 - 1/12);
INSERT INTO die VALUES (6, 8, 1/6 - 1/12);

注意和传统的1-6骰子不同，概率也不是平均出现的。
现在要用SQL求出在掷N次后各个总面值及其概率。

投掷N次的总面值及其概率可以用这个表的N次笛卡尔积求出来，比如N=3:

SELECT d1.face_value+d2.face_value+d3.face_value
   ,SUM(d1.probability*d2.probability*d3.probability)
  FROM die d1,die d2,die d3
GROUP BY d1.face_value+d2.face_value+d3.face_value;

如果要用一个通用SQL满足不同的N，办法是用CONNECT BY来代替笛卡尔积：

VAR N NUMBER;
EXEC :N :=3;

WITH d AS (
SELECT ROWNUM AS id
   ,SYS_CONNECT_BY_PATH(face_value,'~')||'~' AS v
   ,SYS_CONNECT_BY_PATH(probability,'~')||'~' AS p
  FROM die
WHERE LEVEL=:N
CONNECT BY LEVEL<=:N
)
,d2 AS (
SELECT id
   ,SUM(SUBSTR(v,INSTR(V,'~',1,l)+1,INSTR(V,'~',1,l+1)-INSTR(V,'~',1,l)-1)) AS v
   ,EXP(SUM(LN(SUBSTR(p,INSTR(p,'~',1,l)+1,INSTR(p,'~',1,l+1)-INSTR(p,'~',1,l)-1)))) AS p
  FROM d
   ,(SELECT LEVEL as l FROM DUAL CONNECT BY LEVEL<=:N)
GROUP BY id
   )
SELECT v
   ,SUM(p) AS p
  FROM d2
GROUP BY v
ORDER BY 1;

可以看到，依然是用SYS_CONNECT_BY_PATH来拼接数据，拆开后用SUM求和，用对数反对数求积。

用新的WITH写法是这样的：

WITH t(v,p,lvl) AS (
SELECT face_value  v
      ,probability p
      ,1
   FROM die
UNION ALL
SELECT d.face_value + t.v
      ,d.probability * t.p
      ,t.lvl+1
   FROM die d,t
WHERE t.lvl<:N
)
SELECT v
   ,SUM(p)
  FROM t
WHERE lvl = :N
GROUP BY v;

这里大大简化了求和求积的运算。但是美中不足的是产生了很多中间记录，每一层的数据是上一层的数量*6, 所以当N=3时在t里面总共会有:
6^1+6^2+6^3 = 258行，当N增加的时候效率急剧下降。
虽然中间行数很多，但是其不同的面值数量并不多。上述例子中最后只有20行。如果ORACLE允许我们这么做：

WITH t(v,p,lvl) AS (
SELECT face_value  v
      ,probability p
      ,1
   FROM die
UNION ALL
SELECT d.face_value + t.v
      ,SUM(d.probability * t.p)
      ,MAX(t.lvl)+1
   FROM die d,t
WHERE t.lvl<:N
GROUP BY d.face_value + t.v
)
SELECT *
  FROM t
WHERE lvl = :N;
即在每次递归的时候做一个聚合，那么中间结果将会大大减少，下一轮递归的效率也会高得多。
遗憾的是会报这么一个错：
  FROM t
   *
ERROR at line 15:
ORA-32486: unsupported operation in recursive branch of recursive WITH clause

文档中说，递归成员不可以包含以下元素：
1. DISTINCT 关键字或 GROUP BY 子句
2. model 子句
3. 聚合函数。而分析函数允许在SELECT中使用。
4. 引用了当前query_name的子查询
5. 把当前query_name作为右边的外连接。

1和3其实是一回事。这个限制使得我们无法在递归过程中通过聚合减少中间结果。3说可以用分析函数，但实际上我试不出来：
WITH t(n) AS (
  SELECT 1 FROM DUAL
  UNION ALL
  SELECT 1+MAX(n) OVER() FROM t
WHERE n<3
)
SELECT * FROM t;

SELECT * FROM t
            *
ERROR at line 7:
ORA-32486: unsupported operation in recursive branch of recursive WITH clause

限制4造成的后果是：如果我已经找到了一个答案，无法告诉ORACLE停止遍历其他的枝条。
我期望的写法是：
WITH t(...) AS (
SELECT ...
UNION ALL
SELECT ...
   FROM t,...
WHERE ... AND NOT EXISTS (SELECT 1 FROM t WHERE 找到答案的条件) --- 这个子查询不允许出现t

哪一天这些限制能够去除，这个WITH将会好玩很多。

限制5说不可以用于外连接，但是我试了一下并不报错：
WITH t(v,p,lvl) AS (
SELECT face_value  v
      ,probability p
      ,1
   FROM die
UNION ALL
SELECT d.face_value + t.v
      ,d.probability * t.p
      ,t.lvl+1
   FROM die d,t
WHERE d.face_value = t.v(+)
      AND t.lvl<:N
)
SELECT COUNT(*)
  FROM t;

反过来连也不报错：
WITH t(v,p,lvl) AS (
SELECT face_value  v
      ,probability p
      ,1
   FROM die
UNION ALL
SELECT d.face_value + t.v
      ,d.probability * t.p
      ,t.lvl+1
   FROM die d,t
WHERE d.face_value(+) = t.v
      AND t.lvl<:N
)
SELECT COUNT(*)
  FROM t;

newkid · 发表于 2010-5-19 03:28

进制转换：
要转换的数字放在字符串STR中；源进制为FROM_BASE, 目标进制TO_BASE.
假设超过10的数字用A-Z来表示，也就是最大不超过36进制。

VAR STR VARCHAR2(10);
EXEC :STR := '1234WXYZ';

VAR FROM_BASE NUMBER;
EXEC :FROM_BASE :=36;

VAR TO_BASE NUMBER;
EXEC :TO_BASE :=10;

用CONNECT BY的做法：
WITH n1 AS (
  SELECT SUM((CASE WHEN c BETWEEN '0' AND '9' THEN TO_NUMBER(c) --- 求出每一位的值
               ELSE ASCII(c)-ASCII('A')+10
            END)*POWER(:FROM_BASE,len-rn) ----- 乘上这一位对应的权值
         ) AS the_num    ---- 最后得出这个需要转换的字符串的实际值
FROM (SELECT SUBSTR(:STR,ROWNUM,1) c,LENGTH(:STR) len,ROWNUM rn  ----- 把每一位拆开
         FROM DUAL CONNECT BY ROWNUM<=LENGTH(:STR)
      )
)
,n2 AS (
  SELECT (CASE WHEN n <10 THEN TO_CHAR(n) ELSE CHR(ASCII('A')+n-10) END) AS digi ---- 这一位值该用哪个字符来表示
      ,rn
FROM (SELECT MOD(TRUNC(the_num/POWER(:TO_BASE,ROWNUM -1)),:TO_BASE) n --- 求出该数字在转换后的进制中的每一位的值
            ,ROWNUM rn
         FROM n1
      CONNECT BY ROWNUM <= TRUNC(LOG(:TO_BASE,the_num))+1
      )
)
SELECT REPLACE(SYS_CONNECT_BY_PATH(digi,'*'),'*') ---- 把转换后的每一位字符串起来
  FROM n2
WHERE rn=1
START WITH rn = (SELECT MAX(rn) FROM n2)
CONNECT BY rn = PRIOR rn -1;

REPLACE(SYS_CONNECT_BY_PATH(DIGI,'*'),'*')-
-------------------------------------------
82907382779

递归WITH的做法：
WITH n1(the_num,lvl,c) AS ( ---- 求值：循环对每一位求值，结果不断累积
  SELECT 0,1,SUBSTR(:STR,1,1) FROM DUAL
  UNION ALL
  SELECT the_num*:FROM_BASE+(CASE WHEN c BETWEEN '0' AND '9' THEN TO_NUMBER(c) --- 求出每一位的值
                              ELSE ASCII(c)-ASCII('A')+10
                           END)
      ,lvl+1
      ,SUBSTR(:STR,lvl+1,1)
FROM n1
WHERE lvl<=LENGTH(:STR)
  )
,n2(the_num,n,the_str) AS ( --- 转换：循环对该数字取模，转换为字符串然后拼接
  SELECT TRUNC(the_num/:TO_BASE),MOD(the_num,:TO_BASE),'' FROM n1 WHERE lvl=LENGTH(:STR)+1
  UNION ALL
  SELECT (CASE WHEN the_num=0 THEN -1 --- 用负数来作为结束标记
            ELSE TRUNC(the_num/:TO_BASE)
      END)
      ,MOD(the_num,:TO_BASE)
      ,(CASE WHEN n <10 THEN TO_CHAR(n) ELSE CHR(ASCII('A')+n-10) END)||the_str
FROM n2
WHERE the_num>=0
  )
SELECT the_str FROM n2 WHERE the_num<0
;

THE_STR
------------------
82907382779