一个复杂问题的求解过程（三）

今天在PUB里面看到一个帖子：http://www.itpub.net/thread-949571-1-1.html。问题本身并不复杂，不过想借这个问题简单描述一下求解的思路。

前两篇文章介绍了利用PL/SQL构造动态SQL的方法来解决问题，这里讨论如何使用SQL来实现。

一个复杂问题的求解过程（一）：http://yangtingkun.itpub.net/post/468/456641

一个复杂问题的求解过程（二）：http://yangtingkun.itpub.net/post/468/456695

前面两篇文章通过PL/SQL构造动态SQL的方法来实现，这是由于构造子查询的个数是不确定的。

如果利用SQL来实现，就必须首先解决这个问题。也就是说找到一个方法，在不使用多个表连接的情况下，获取所有ID不同POWER之间组合的可能性的和。

SQL> WITH T1 ASITPUB个人空间8d3x3~
}Ekv~
  2  (ITPUB个人空间']n}9kK/D*QK)@
  3  SELECT DISTINCT T.ID, T.VALUE, LEVEL - 1 LV, T.VALUE * (LEVEL - 1) POWER
-o3bmVm*w~;N0  4  FROM TITPUB个人空间3w(GK9]q
  5  CONNECT BY LEVEL <= T.POWER
js'b.xv+F"sH#|0  6  )ITPUB个人空间}#RD+g-md+v;D;lb
  7  SELECT * FROM T1;

        ID      VALUE         LV      POWER
a_pE%d4VDa;n
O0---------- ---------- ---------- ----------ITPUB个人空间vR:l[(Pl
s7l%h
         2          1          1          1ITPUB个人空间 x(R9s|7[ O5ND
         3          4          1          4ITPUB个人空间 D0O)t c8HI(U~
         3          4          0          0
cu3L@+Z_+Y0         5          4          0          0ITPUB个人空间 M!FMD'` b-q
         1          2          2          4ITPUB个人空间4~lj\-IP)`
         5          4          1          4ITPUB个人空间qD%W$EHE'RZ
         4          5          0          0ITPUB个人空间KYl5a#E2s,Z8i w
         2          1          0          0
{&Qa1n_ J,A0         1          2          0          0
Mi;k ?$lrC\(c0         3          4          3         12
A"t,Z0k^J+@/F;B0         4          5          1          5ITPUB个人空间/K1mX]^5VgSi Q
         3          4          2          8
N/t]a RtC/h{0         1          2          1          2
:eU8}s;}!NF0         5          4          2          8

已选择14行。

现在得到的结果是展开了加权与VALUE相乘的所有可能性。下面要达到的目的是ID从1到5中，每个ID任选一条记录，并累加POWER的值，最后过滤结果为16的值。

最自然的想法就是多个表连接通过笛卡儿连接来实现，但是没有办法解决表连接数不确定的问题，想来想去，只有再次通过树形查询来实现：

SQL> SELECT ID, SYS_CONNECT_BY_PATH(POWER, ',') POWER_LISTITPUB个人空间M8yp8WdC!]]y
  2  FROM
c/od*[~J0  3  (
p0qs\6v0h
l0  4   SELECT DISTINCT T.ID, T.VALUE, LEVEL - 1 LV, T.VALUE * (LEVELITPUB个人空间+yY&M$z/\5N*h/C
  5   FROM TITPUB个人空间8r
m*e,~B$Y:H
  6   CONNECT BY LEVEL <= T.POWERITPUB个人空间r^(e2m1c/r
  7  )ITPUB个人空间_ v6C4@&M
  8  START WITH ID = 1ITPUB个人空间[.gnyr!n
  9  CONNECT BY PRIOR ID + 1 = IDITPUB个人空间#Y'zl0c.@g
 10  ORDER BY 1, 2;

        ID POWER_LIST
&q^9R@5Ft%ZU0---------- ------------------------------
)?Ox
cag\XL6cw0[0         1 ,0
qi)H(@
nW9j0         1 ,2ITPUB个人空间1sqaBUX6]
         1 ,4ITPUB个人空间}ktdX*~)~&]
         2 ,0,0
*w&`G4V Is&qw.FTu2I0         2 ,0,1ITPUB个人空间%C;j
I H!v4l)b
         2 ,2,0ITPUB个人空间
a8M,fk(O0go'Srt"T
         2 ,2,1ITPUB个人空间te)HDP(wl
         2 ,4,0ITPUB个人空间6@6X r
o\2[s"^P
         2 ,4,1ITPUB个人空间"p"O|Q4|N Px3o"H OT
         3 ,0,0,0ITPUB个人空间#xY%STk{H;bQ}
         3 ,0,0,12
;N6p]4lOUZ K&ie0         3 ,0,0,4ITPUB个人空间BMu6MNj2E@.F~2o
         3 ,0,0,8ITPUB个人空间:O2]
{M7f7?%WaL+O5}
         3 ,0,1,0
%D
zd&M!xp$[ cj4?,M0         3 ,0,1,12ITPUB个人空间O dX)~3J`-f
         3 ,0,1,4
7n+x;YZv1M(Q6mO0         3 ,0,1,8ITPUB个人空间i`JK*R-X
         3 ,2,0,0
B)eN8{:b0         3 ,2,0,12
-NKG5a"N6\0         3 ,2,0,4ITPUB个人空间EEdl^&Sg&K
         3 ,2,0,8
gn3b5B1w3P0         3 ,2,1,0ITPUB个人空间Q"fs S9Qo"r
         3 ,2,1,12
n D-y+M1f}!m0         3 ,2,1,4
ub2yk%L/DN7Kd0         3 ,2,1,8ITPUB个人空间ykpA7s*z7dAV&uU
         3 ,4,0,0ITPUB个人空间1N2K%RIK,B/Zo4Lc
         3 ,4,0,12ITPUB个人空间F*y}x%w
i&h!A
         3 ,4,0,4ITPUB个人空间;oi9G)`/],i
         3 ,4,0,8
?6{ nBF$qT0         3 ,4,1,0ITPUB个人空间"k3I|i+fQ5C"|A7q
         3 ,4,1,12ITPUB个人空间J$gB+T&BB
         3 ,4,1,4ITPUB个人空间K s3tfX(b_
         3 ,4,1,8
;|D;s a1fJR0         4 ,0,0,0,0
G/nV2a8ft)e}0         4 ,0,0,0,5ITPUB个人空间J7[ W*LL
         4 ,0,0,12,0

eQeNj+W@0         4 ,0,0,12,5ITPUB个人空间(o0n$K;z J6KFs\&w+WF
         4 ,0,0,4,0ITPUB个人空间:~)~}t_6Q
         4 ,0,0,4,5
Wk+j`Y:SoZC*w0         4 ,0,0,8,0
y4E](I)HC@1I\0         4 ,0,0,8,5
o%`j\k5S0         4 ,0,1,0,0ITPUB个人空间4Y+Dv_ CWC
         4 ,0,1,0,5ITPUB个人空间5@9K }4R'H~l
         4 ,0,1,12,0
'D?-] fX b:l H3D0         4 ,0,1,12,5ITPUB个人空间6R l s*r(m
         4 ,0,1,4,0ITPUB个人空间$a2ajK2Wk:K4p5d(r
         4 ,0,1,4,5
A.Y
V;?X0         4 ,0,1,8,0ITPUB个人空间;r,l ^]%of3vf l
         4 ,0,1,8,5ITPUB个人空间 t;_&u!b Be
k
         4 ,2,0,0,0
8r n"wg:xlu4k9BX0         4 ,2,0,0,5ITPUB个人空间]-y7\a!| J+r1Y
         4 ,2,0,12,0ITPUB个人空间5Z"Sz.K4uttb
         4 ,2,0,12,5
b+lA+J0b7Jq0         4 ,2,0,4,0
9B_ t\0X^0         4 ,2,0,4,5ITPUB个人空间$F5N^*r3yt n kJQ
         4 ,2,0,8,0
.Q(B(PMq9C9J wn)Zc0         4 ,2,0,8,5
,Z#{%I6g#Z0h;fxq6_0         4 ,2,1,0,0ITPUB个人空间4c:Y
WUWb c7M8o
         4 ,2,1,0,5
,~s)~ Xd0         4 ,2,1,12,0
y~N$V:x6tR:M0         4 ,2,1,12,5ITPUB个人空间Oyfd3TK:Z1E
         4 ,2,1,4,0ITPUB个人空间:n2Xf/j$f$\3y ni#W
         4 ,2,1,4,5
c4ZK"V6[Xx:I0         4 ,2,1,8,0
'|2UQ7A/{0         4 ,2,1,8,5ITPUB个人空间)sO;Tc3VG
         4 ,4,0,0,0ITPUB个人空间.W z!k0X q-}!G
         4 ,4,0,0,5
+T4?
qv`C5]0         4 ,4,0,12,0
zkAuQ0         4 ,4,0,12,5ITPUB个人空间&`~N$B5eM]V&]"Z
         4 ,4,0,4,0ITPUB个人空间Jy,Y5pO
         4 ,4,0,4,5
o:e[#G}!h!it6P0         4 ,4,0,8,0
)}8AAr*fF e&pPp0         4 ,4,0,8,5
hux X-rB_p \0         4 ,4,1,0,0
"u0}!hYY0         4 ,4,1,0,5ITPUB个人空间 [-^4l\
k7}M p
         4 ,4,1,12,0ITPUB个人空间wm&hWe(L
         4 ,4,1,12,5
3P2vpm
I0o1La~0         4 ,4,1,4,0ITPUB个人空间7T'fh5hljB^1s
         4 ,4,1,4,5ITPUB个人空间}#y1wT tf*[
         4 ,4,1,8,0
/_ rQv,PO0         4 ,4,1,8,5

v;K&B a d0         5 ,0,0,0,0,0
?r5U@ejqX0         5 ,0,0,0,0,4
^RD-o3S0         5 ,0,0,0,0,8ITPUB个人空间!WrnPbf~
         5 ,0,0,0,5,0ITPUB个人空间!|M hi9J7U'n8q1g
         5 ,0,0,0,5,4ITPUB个人空间 Q6B/A gGU
         5 ,0,0,0,5,8
J1O Y]dJ0         5 ,0,0,12,0,0ITPUB个人空间6r;h:Z(M
J eV
         5 ,0,0,12,0,4
8r0s7LG'j4Y0         5 ,0,0,12,0,8
X}-Z UZ*W3d0         5 ,0,0,12,5,0
7}} i}5t$c
uIO(c0         5 ,0,0,12,5,4
Th{/dqvo0         5 ,0,0,12,5,8
\q@#S!bc0         5 ,0,0,4,0,0ITPUB个人空间bP dl IFdk[n
         5 ,0,0,4,0,4
*rp-`2E;h(q0         5 ,0,0,4,0,8
f @dp8FO&n0         5 ,0,0,4,5,0ITPUB个人空间)f.A\2tp-te
         5 ,0,0,4,5,4
,]2Y.G7OIz*X1r UR0         5 ,0,0,4,5,8ITPUB个人空间n9wjeS
         5 ,0,0,8,0,0ITPUB个人空间W$m5u!M K$j|
         5 ,0,0,8,0,4
&\L0bgB,r R`w-_g0         5 ,0,0,8,0,8
'f'@A2O*B&`wp4pt7G d6t0         5 ,0,0,8,5,0
#A1ls0I'SP5R0         5 ,0,0,8,5,4ITPUB个人空间-?$Y5`,K*n$|!{
         5 ,0,0,8,5,8
hB7e)Rc z+m3ti0         5 ,0,1,0,0,0ITPUB个人空间'Z%w5I4F]D:f
         5 ,0,1,0,0,4
+A K*eeg\w%~0         5 ,0,1,0,0,8ITPUB个人空间I[&lW9\ En
         5 ,0,1,0,5,0
(m*o(\lh*euG8D0         5 ,0,1,0,5,4ITPUB个人空间U3];Mg4pk^L
         5 ,0,1,0,5,8
_Wt/q0U0         5 ,0,1,12,0,0ITPUB个人空间-@A?mm$lZm2]
         5 ,0,1,12,0,4
ov~ g}/I1fBW z0         5 ,0,1,12,0,8ITPUB个人空间 i m YbUU {
         5 ,0,1,12,5,0
W+~p }7o4b&K0         5 ,0,1,12,5,4ITPUB个人空间}
Xa5\8I(}f
         5 ,0,1,12,5,8ITPUB个人空间O3ge [FmP&C
         5 ,0,1,4,0,0ITPUB个人空间a/P!~\%`Z,~q_H
         5 ,0,1,4,0,4ITPUB个人空间"}7J.YAYY
         5 ,0,1,4,0,8
,x)NMl9wp%t}0         5 ,0,1,4,5,0
G4T xR7jK;X0q0         5 ,0,1,4,5,4
|JI,tyZu0         5 ,0,1,4,5,8ITPUB个人空间An%yt&DYoS7YI~
         5 ,0,1,8,0,0
^`1h*q#S%A }2O0         5 ,0,1,8,0,4ITPUB个人空间
i @2hz3kc
         5 ,0,1,8,0,8
;Z T'C$N)?1im+l0         5 ,0,1,8,5,0
[8N1O4h2W'f*A0         5 ,0,1,8,5,4
-ao-uP)`0         5 ,0,1,8,5,8
K3D6X8Q/]3v0         5 ,2,0,0,0,0
h"e4y8SA0         5 ,2,0,0,0,4
0Iqw6f@vg0         5 ,2,0,0,0,8
6yu T Ro$J0         5 ,2,0,0,5,0
z9AA*p2\8LUVs0         5 ,2,0,0,5,4
J9`!Z;O6`;y0         5 ,2,0,0,5,8
gE0F Qi5F c)e0         5 ,2,0,12,0,0ITPUB个人空间
`/| k1WAb/j*[;Yu)o
         5 ,2,0,12,0,4
s/h.h"B kH8A'w0         5 ,2,0,12,0,8ITPUB个人空间z}3i"h)P#pX@3C/O
         5 ,2,0,12,5,0ITPUB个人空间-nT}Y#iEsZ
         5 ,2,0,12,5,4
[D$B n%jm&A0         5 ,2,0,12,5,8ITPUB个人空间9_Eu^:MM|'Z
         5 ,2,0,4,0,0
Tn;@2@'M+n!Dmx r0         5 ,2,0,4,0,4ITPUB个人空间{QXHrI&}
         5 ,2,0,4,0,8
&{&o*g({Uv$U2Q0         5 ,2,0,4,5,0ITPUB个人空间*ct#p!b;V
         5 ,2,0,4,5,4
wB!d.r"e~V9b0         5 ,2,0,4,5,8ITPUB个人空间Dw9uTpV\u*n
         5 ,2,0,8,0,0
"zf fJ4Vv0         5 ,2,0,8,0,4
(k4_OL gJ%x0         5 ,2,0,8,0,8
9au;}Po!?nT0         5 ,2,0,8,5,0
7V+C~*F-{^O!e0         5 ,2,0,8,5,4
;\ ^Rp1N-{0         5 ,2,0,8,5,8
7qk(M8pMv2@ge0         5 ,2,1,0,0,0ITPUB个人空间 As R ]}&s+e&Q
         5 ,2,1,0,0,4

?.U^VE0         5 ,2,1,0,0,8ITPUB个人空间"[3hW.TS~
         5 ,2,1,0,5,0
YN\E{^U:Q,p0         5 ,2,1,0,5,4
].C&edu1T%rN0         5 ,2,1,0,5,8ITPUB个人空间.W/u
]xp8@ Z
         5 ,2,1,12,0,0
-i%n2x h$o0         5 ,2,1,12,0,4
t^;kE|f0         5 ,2,1,12,0,8
_S1PS;zXb oO9P K0         5 ,2,1,12,5,0ITPUB个人空间ZI-o1X5N UgK
         5 ,2,1,12,5,4
&@uzE.@,N%O8y c0         5 ,2,1,12,5,8ITPUB个人空间8}$D Ei(JG
         5 ,2,1,4,0,0ITPUB个人空间E9EbB;TU
         5 ,2,1,4,0,4ITPUB个人空间6_-Y`.b0X
         5 ,2,1,4,0,8
,a2tqTTZE4c5_0         5 ,2,1,4,5,0ITPUB个人空间h[$B:lx
         5 ,2,1,4,5,4
&pG7eU7^K0         5 ,2,1,4,5,8
)Tp,cL f vW1d ^\0         5 ,2,1,8,0,0ITPUB个人空间_2r+Ruv Y
         5 ,2,1,8,0,4
1k sM[ J0         5 ,2,1,8,0,8
's _O-OW%\0         5 ,2,1,8,5,0ITPUB个人空间k!Wj"Nr7Z&A
         5 ,2,1,8,5,4
T4ev:M7v]&{ E B0         5 ,2,1,8,5,8
4[\*HRI;lF/Rk4n0         5 ,4,0,0,0,0
&X$K3oELT.nx*|0         5 ,4,0,0,0,4
|LNxM/G0NXe0         5 ,4,0,0,0,8ITPUB个人空间"vl)NI,`/M(U!e G(d
         5 ,4,0,0,5,0
)v#o6Je\A0         5 ,4,0,0,5,4ITPUB个人空间TmzuT;bkA
         5 ,4,0,0,5,8ITPUB个人空间|M;@%Pz8m*Ye
         5 ,4,0,12,0,0
a7dq?`bR0         5 ,4,0,12,0,4ITPUB个人空间BOacuwh
         5 ,4,0,12,0,8ITPUB个人空间;M'f+S"HFH[
         5 ,4,0,12,5,0ITPUB个人空间|*N!`qb?"Q
         5 ,4,0,12,5,4
hU$Oxb| uE(^o ^[0         5 ,4,0,12,5,8ITPUB个人空间 K gwt:cB
         5 ,4,0,4,0,0ITPUB个人空间_u-Hq;o6[%[T
         5 ,4,0,4,0,4ITPUB个人空间;K tS#zUE0X
ue
         5 ,4,0,4,0,8ITPUB个人空间u;}3j+vXacH.K;i
         5 ,4,0,4,5,0ITPUB个人空间;Wd-]TG
         5 ,4,0,4,5,4ITPUB个人空间q1I_?'fE!f
         5 ,4,0,4,5,8ITPUB个人空间LRn6kJ!C2S&Mu
         5 ,4,0,8,0,0
(r_U {F
f0         5 ,4,0,8,0,4ITPUB个人空间
No aju-i0?
         5 ,4,0,8,0,8
j.Z;r0{Eo0         5 ,4,0,8,5,0
x&^{ k i.[,W#t0         5 ,4,0,8,5,4ITPUB个人空间XbY7_L$|z
         5 ,4,0,8,5,8ITPUB个人空间SCp j(Z1t
Sa L
         5 ,4,1,0,0,0ITPUB个人空间1ol)Q8b]J J W6p}/s
         5 ,4,1,0,0,4ITPUB个人空间(}ZQ)gzW_
         5 ,4,1,0,0,8ITPUB个人空间:K)Zi M9Wj8S`
         5 ,4,1,0,5,0ITPUB个人空间(t5C|/f Xt7}
         5 ,4,1,0,5,4
R(R2I"zj^0         5 ,4,1,0,5,8ITPUB个人空间3w|E\[r3z&J
         5 ,4,1,12,0,0ITPUB个人空间1]`$or)\
         5 ,4,1,12,0,4
o2Q8YJ'UM2QZ-b0         5 ,4,1,12,0,8
)W%~m;k'B:d0         5 ,4,1,12,5,0

N9TD5{+V6K @%t0         5 ,4,1,12,5,4
y4]`2d9p@0         5 ,4,1,12,5,8
!dHC-RE0         5 ,4,1,4,0,0
!e'|AS/Eo0         5 ,4,1,4,0,4
N&Z5if/h'kE'Z0         5 ,4,1,4,0,8ITPUB个人空间v~O3j"s9fE
         5 ,4,1,4,5,0ITPUB个人空间TzcO ^AW&@
         5 ,4,1,4,5,4ITPUB个人空间 L'NT8gFX?
         5 ,4,1,4,5,8ITPUB个人空间 @5z?H+n O8T1I
         5 ,4,1,8,0,0ITPUB个人空间3DQ wB1s d|0v8k
         5 ,4,1,8,0,4
6_7e` K%B0         5 ,4,1,8,0,8
*Y4p RO-V0         5 ,4,1,8,5,0
AY&uz @g0         5 ,4,1,8,5,4ITPUB个人空间DPA&JYG
         5 ,4,1,8,5,8

已选择225行。

从上面的查询结果可以看到，ID为5的记录就等价于5个子查询的笛卡儿的结果。不过这种方式的结果合并到一个字符串里。

下面的工作就是计算每个字符串里面数值的和，然后过滤那些等于16的记录。

最终SQL实现如下：

SQL> SELECT LV_LIST
`YyL{ t0  2  FROMITPUB个人空间 P.[W1q(Rr
X6D5KP[
  3  (
k(kBY{)p2En0  4   SELECT ROWNUM RID,
*t){9A x R.y0  5    ID,
osc1i5eK%i0  6    SYS_CONNECT_BY_PATH(LV, ' ') LV_LIST,ITPUB个人空间,I;Ozf;]-u4ln lD
  7    SYS_CONNECT_BY_PATH(POWER, ',') POWER_LIST
F[q~7LPw%X0  8   FROM
%e9UG {^t3F&mt0  9   (
L5@6R0K!}0 10    SELECT DISTINCT T.ID, T.VALUE, LEVEL - 1 LV, T.VALUE * (LEVEL - 1) POWER
;@J`a W0 11    FROM TITPUB个人空间C"QbN5aB
 12    CONNECT BY LEVEL <= T.POWERITPUB个人空间m1I4r`(~3Td%AT7E
 13   )
+x"Sk)? nN)UL-V0 14   START WITH ID = 1
8sM/@0_:t Q^)\c0 15   CONNECT BY PRIOR ID + 1 = IDITPUB个人空间!ai8se-[bE2y r-ADn
 16  ) A,ITPUB个人空间t3X6W7^q,wH
 17  (SELECT ROWNUM RN, COUNT(*) OVER() ID FROM T) B
Ofzz$_bqi0 18  WHERE A.ID = B.IDITPUB个人空间1h'L&I4gj5D
 19  GROUP BY RID, LV_LISTITPUB个人空间0u}k&\^Zg.d
N
 20  HAVING SUM(SUBSTR(POWER_LIST,ITPUB个人空间:p-cq/e^
 21    INSTR(POWER_LIST, ',', 1, RN) + 1,ITPUB个人空间9kf&h])Cc
 22    INSTR(POWER_LIST || ',', ',', 1, RN + 1) - INSTR(POWER_LIST, ',', 1, RN) - 1)) = 16
`+Sx/R|"|@|0 23  ;

LV_LISTITPUB个人空间Qc8W.Uj`
----------------------------------------------------------------------ITPUB个人空间Y~`&e"_
 2 0 1 0 2
@'m-dP v*d'_2j0 0 0 2 0 2ITPUB个人空间*Ye;m _@NJ'e
 0 0 3 0 1
8be)nS`0 2 0 2 0 1
QIfoP(b0 1 1 1 1 1
^ GNr2y0 1 1 0 1 2
+Ub;Zt(f#Ne!x`*^0 1 1 2 1 0
%f7W7XARz'n
yH0 2 0 3 0 0

已选择8行。