SQL解惑(第2版) 的一些样题

newkid · 发表于 2010-3-19 23:18

PUZZLE 67 STABLE MARRIAGES PROBLEM
这个题目有点意思，研究的是婚姻稳定性课题。
假设有N男N女，要求用SQL把他们配对，并且不能出现不稳定的情况。
什么样的婚姻不稳定呢？假设AB是一对夫妇，CD是另一对夫妇，如果A喜欢C多于B, 而C也喜欢A多于D, 那么A和C就有可能红杏出墙，这样的配对就是不稳定的。假设A喜欢C多于B, 但是C在A和D之间还是喜欢D多一点，那么A就是单相思也没用，这样的配对还是稳定的。B和D的情况也类似，如果两个互相喜欢超过了自己的配偶，同样也会造成不稳定。

用两张表来保存男女数据：
CREATE TABLE Husbands
(man CHAR(2) NOT NULL, ---- 男ID
woman CHAR(2) NOT NULL, ---- 潜在的女性对象
ranking INTEGER NOT NULL CHECK (ranking > 0),  ---- 对此女的喜欢程度，1为最喜欢，2次之，其他类推
PRIMARY KEY (man, woman));

CREATE TABLE Wives
(woman CHAR(2) NOT NULL,  ---- 女ID
man CHAR(2) NOT NULL, ---- 潜在的男性对象
ranking INTEGER NOT NULL CHECK (ranking > 0),  ---- 对此男的喜欢程度，1为最喜欢，2次之，其他类推
PRIMARY KEY (woman, man));

8男8女的测试数据如下，要求用SQL找出所有的稳定婚姻分配方案。

INSERT INTO Husbands VALUES ('h1', 'w1', 5);
INSERT INTO Husbands VALUES ('h1', 'w2', 2);
INSERT INTO Husbands VALUES ('h1', 'w3', 6);
INSERT INTO Husbands VALUES ('h1', 'w4', 8);
INSERT INTO Husbands VALUES ('h1', 'w5', 4);
INSERT INTO Husbands VALUES ('h1', 'w6', 3);
INSERT INTO Husbands VALUES ('h1', 'w7', 1);
INSERT INTO Husbands VALUES ('h1', 'w8', 7);
INSERT INTO Husbands VALUES ('h2', 'w1', 6);
INSERT INTO Husbands VALUES ('h2', 'w2', 3);
INSERT INTO Husbands VALUES ('h2', 'w3', 2);
INSERT INTO Husbands VALUES ('h2', 'w4', 1);
INSERT INTO Husbands VALUES ('h2', 'w5', 8);
INSERT INTO Husbands VALUES ('h2', 'w6', 4);
INSERT INTO Husbands VALUES ('h2', 'w7', 7);
INSERT INTO Husbands VALUES ('h2', 'w8', 5);
INSERT INTO Husbands VALUES ('h3', 'w1', 4);
INSERT INTO Husbands VALUES ('h3', 'w2', 2);
INSERT INTO Husbands VALUES ('h3', 'w3', 1);
INSERT INTO Husbands VALUES ('h3', 'w4', 3);
INSERT INTO Husbands VALUES ('h3', 'w5', 6);
INSERT INTO Husbands VALUES ('h3', 'w6', 8);
INSERT INTO Husbands VALUES ('h3', 'w7', 7);
INSERT INTO Husbands VALUES ('h3', 'w8', 5);
INSERT INTO Husbands VALUES ('h4', 'w1', 8);
INSERT INTO Husbands VALUES ('h4', 'w2', 4);
INSERT INTO Husbands VALUES ('h4', 'w3', 1);
INSERT INTO Husbands VALUES ('h4', 'w4', 3);
INSERT INTO Husbands VALUES ('h4', 'w5', 5);
INSERT INTO Husbands VALUES ('h4', 'w6', 6);
INSERT INTO Husbands VALUES ('h4', 'w7', 7);
INSERT INTO Husbands VALUES ('h4', 'w8', 2);
INSERT INTO Husbands VALUES ('h5', 'w1', 6);
INSERT INTO Husbands VALUES ('h5', 'w2', 8);
INSERT INTO Husbands VALUES ('h5', 'w3', 2);
INSERT INTO Husbands VALUES ('h5', 'w4', 3);
INSERT INTO Husbands VALUES ('h5', 'w5', 4);
INSERT INTO Husbands VALUES ('h5', 'w6', 5);
INSERT INTO Husbands VALUES ('h5', 'w7', 7);
INSERT INTO Husbands VALUES ('h5', 'w8', 1);
INSERT INTO Husbands VALUES ('h6', 'w1', 7);
INSERT INTO Husbands VALUES ('h6', 'w2', 4);
INSERT INTO Husbands VALUES ('h6', 'w3', 6);
INSERT INTO Husbands VALUES ('h6', 'w4', 5);
INSERT INTO Husbands VALUES ('h6', 'w5', 3);
INSERT INTO Husbands VALUES ('h6', 'w6', 8);
INSERT INTO Husbands VALUES ('h6', 'w7', 2);
INSERT INTO Husbands VALUES ('h6', 'w8', 1);
INSERT INTO Husbands VALUES ('h7', 'w1', 5);
INSERT INTO Husbands VALUES ('h7', 'w2', 1);
INSERT INTO Husbands VALUES ('h7', 'w3', 4);
INSERT INTO Husbands VALUES ('h7', 'w4', 2);
INSERT INTO Husbands VALUES ('h7', 'w5', 7);
INSERT INTO Husbands VALUES ('h7', 'w6', 3);
INSERT INTO Husbands VALUES ('h7', 'w7', 6);
INSERT INTO Husbands VALUES ('h7', 'w8', 8);
INSERT INTO Husbands VALUES ('h8', 'w1', 2);
INSERT INTO Husbands VALUES ('h8', 'w2', 4);
INSERT INTO Husbands VALUES ('h8', 'w3', 7);
INSERT INTO Husbands VALUES ('h8', 'w4', 3);
INSERT INTO Husbands VALUES ('h8', 'w5', 6);
INSERT INTO Husbands VALUES ('h8', 'w6', 1);
INSERT INTO Husbands VALUES ('h8', 'w7', 5);
INSERT INTO Husbands VALUES ('h8', 'w8', 8);
INSERT INTO Wives VALUES ('w1', 'h1', 6);
INSERT INTO Wives VALUES ('w1', 'h2', 3);
INSERT INTO Wives VALUES ('w1', 'h3', 7);
INSERT INTO Wives VALUES ('w1', 'h4', 1);
INSERT INTO Wives VALUES ('w1', 'h5', 4);
INSERT INTO Wives VALUES ('w1', 'h6', 2);
INSERT INTO Wives VALUES ('w1', 'h7', 8);
INSERT INTO Wives VALUES ('w1', 'h8', 5);
INSERT INTO Wives VALUES ('w2', 'h1', 4);
INSERT INTO Wives VALUES ('w2', 'h2', 8);
INSERT INTO Wives VALUES ('w2', 'h3', 3);
INSERT INTO Wives VALUES ('w2', 'h4', 7);
INSERT INTO Wives VALUES ('w2', 'h5', 2);
INSERT INTO Wives VALUES ('w2', 'h6', 5);
INSERT INTO Wives VALUES ('w2', 'h7', 6);
INSERT INTO Wives VALUES ('w2', 'h8', 1);
INSERT INTO Wives VALUES ('w3', 'h1', 3);
INSERT INTO Wives VALUES ('w3', 'h2', 4);
INSERT INTO Wives VALUES ('w3', 'h3', 5);
INSERT INTO Wives VALUES ('w3', 'h4', 6);
INSERT INTO Wives VALUES ('w3', 'h5', 8);
INSERT INTO Wives VALUES ('w3', 'h6', 1);
INSERT INTO Wives VALUES ('w3', 'h7', 7);
INSERT INTO Wives VALUES ('w3', 'h8', 2);
INSERT INTO Wives VALUES ('w4', 'h1', 8);
INSERT INTO Wives VALUES ('w4', 'h2', 2);
INSERT INTO Wives VALUES ('w4', 'h3', 1);
INSERT INTO Wives VALUES ('w4', 'h4', 3);
INSERT INTO Wives VALUES ('w4', 'h5', 7);
INSERT INTO Wives VALUES ('w4', 'h6', 5);
INSERT INTO Wives VALUES ('w4', 'h7', 4);
INSERT INTO Wives VALUES ('w4', 'h8', 6);
INSERT INTO Wives VALUES ('w5', 'h1', 3);
INSERT INTO Wives VALUES ('w5', 'h2', 7);
INSERT INTO Wives VALUES ('w5', 'h3', 2);
INSERT INTO Wives VALUES ('w5', 'h4', 4);
INSERT INTO Wives VALUES ('w5', 'h5', 5);
INSERT INTO Wives VALUES ('w5', 'h6', 1);
INSERT INTO Wives VALUES ('w5', 'h7', 6);
INSERT INTO Wives VALUES ('w5', 'h8', 8);
INSERT INTO Wives VALUES ('w6', 'h1', 2);
INSERT INTO Wives VALUES ('w6', 'h2', 1);
INSERT INTO Wives VALUES ('w6', 'h3', 3);
INSERT INTO Wives VALUES ('w6', 'h4', 6);
INSERT INTO Wives VALUES ('w6', 'h5', 8);
INSERT INTO Wives VALUES ('w6', 'h6', 7);
INSERT INTO Wives VALUES ('w6', 'h7', 5);
INSERT INTO Wives VALUES ('w6', 'h8', 4);
INSERT INTO Wives VALUES ('w7', 'h1', 6);
INSERT INTO Wives VALUES ('w7', 'h2', 4);
INSERT INTO Wives VALUES ('w7', 'h3', 1);
INSERT INTO Wives VALUES ('w7', 'h4', 5);
INSERT INTO Wives VALUES ('w7', 'h5', 2);
INSERT INTO Wives VALUES ('w7', 'h6', 8);
INSERT INTO Wives VALUES ('w7', 'h7', 3);
INSERT INTO Wives VALUES ('w7', 'h8', 7);
INSERT INTO Wives VALUES ('w8', 'h1', 8);
INSERT INTO Wives VALUES ('w8', 'h2', 2);
INSERT INTO Wives VALUES ('w8', 'h3', 7);
INSERT INTO Wives VALUES ('w8', 'h4', 4);
INSERT INTO Wives VALUES ('w8', 'h5', 5);
INSERT INTO Wives VALUES ('w8', 'h6', 6);
INSERT INTO Wives VALUES ('w8', 'h7', 1);
INSERT INTO Wives VALUES ('w8', 'h8', 3);
-----------------------

答案#1和#2是一样的,只不过是#1是更简单版本，只有四对夫妇。

ANSWER#2:
建立一张辅助表：
CREATE TABLE Wife_perms
(wife CHAR(2) NOT NULL PRIMARY KEY,
tally INTEGER NOT NULL);

INSERT INTO Wife_perms VALUES ('w1', 1);
INSERT INTO Wife_perms VALUES ('w2', 2);
INSERT INTO Wife_perms VALUES ('w3', 3);
INSERT INTO Wife_perms VALUES ('w4', 4);
INSERT INTO Wife_perms VALUES ('w5', 5);
INSERT INTO Wife_perms VALUES ('w6', 6);
INSERT INTO Wife_perms VALUES ('w7', 7);
INSERT INTO Wife_perms VALUES ('w8', 8);

SQL本来有错被我改过来了。
SELECT W1.wife AS h1, W2.wife AS h2, W3.wife AS h3,
   W4.wife AS h4, W5.wife AS h5, W6.wife AS h6, W7.wife AS h7,
   W8.wife AS h8
  FROM Wife_perms W1, Wife_perms W2, Wife_perms W3,
   Wife_perms W4, Wife_perms W5, Wife_perms W6,
   Wife_perms W7, Wife_perms W8
WHERE (W1.tally + W2.tally + W3.tally + W4.tally +
      W5.tally + W6.tally + W7.tally + W8.tally) = 255 ---- 利用位操作实现全排列的过滤条件
   AND NOT EXISTS (SELECT *    ------- 去除不稳定组合
                     FROM Husbands  H1, Husbands  H2,
                           Wives  W1, Wives  W2
                     WHERE H1.man = H2.man
                           AND H1.ranking > H2.ranking
                           AND (H1.man || H1.woman) IN
                           ('h1' || W1.wife, 'h2' || W2.wife, ---- 原SQL中的W1-W8是写的H1-H8所以报TABLE不存在的错
                           'h3' || W3.wife, 'h4' || W4.wife,
                           'h5' || W5.wife, 'h6' || W6.wife,
                           'h7' || W7.wife, 'h8' || W8.wife)
                           AND H2.woman = W1.woman
                           AND W1.woman = W2.woman
                           AND W1.ranking > W2.ranking
                           AND (W1.man || W1.woman) IN
                           ('h1' || W1.wife, 'h2' || W2.wife,
                           'h3' || W3.wife, 'h4' || W4.wife,
                           'h5' || W5.wife, 'h6' || W6.wife,
                           'h7' || W7.wife, 'h8' || W8.wife)
                  );
---------------------
答案#3:
建立一张辅助表存放所有不稳定的过滤表达式。
CREATE TABLE Unstable
(bad_marriage CHAR(16) NOT NULL
);

每个WIFE占两位字符，位置表示男ID号，比如某女如果出现在第5-6位，则表示该女和3号男配对
每行数据里面会有两个女ID, 表示两个配对，而且这两对是不稳定的。
除了这两个女ID外，其他全部用下划线代替，这是因为在LIKE中下划线可以匹配任意字符
这样一行数据表示只要出现了这两个女ID和这两个男ID（即女ID出现的位置）的配对，其他不管如何配对都是不稳定的。
举例：__w5__________w7
这行数据说明W5配H2, W7配H8是不稳定的。

INSERT INTO Unstable
SELECT DISTINCT
CASE WHEN W.man = 'h1' THEN W.woman
WHEN Y.man = 'h1' THEN Y.woman
ELSE '__' END
|| CASE WHEN W.man = 'h2' THEN W.woman
WHEN Y.man = 'h2' THEN Y.woman
ELSE '__' END
|| CASE WHEN W.man = 'h3' THEN W.woman
WHEN Y.man = 'h3' THEN Y.woman
ELSE '__' END
|| CASE WHEN W.man = 'h4' THEN W.woman
WHEN Y.man = 'h4' THEN Y.woman
ELSE '__' END
|| CASE WHEN W.man = 'h5' THEN W.woman
WHEN Y.man = 'h5' THEN Y.woman
ELSE '__' END
|| CASE WHEN W.man = 'h6' THEN W.woman
WHEN Y.man = 'h6' THEN Y.woman
ELSE '__' END
|| CASE WHEN W.man = 'h7' THEN W.woman
WHEN Y.man = 'h7' THEN Y.woman
ELSE '__' END
|| CASE WHEN W.man = 'h8' THEN W.woman
WHEN Y.man = 'h8' THEN Y.woman
ELSE '__' END
FROM Husbands W, Husbands X,
Wives  Y, Wives  Z
WHERE W.man = X.man
AND W.ranking > X.ranking
AND X.woman = Y.woman
AND Y.woman = Z.woman
AND Y.ranking > Z.ranking
AND Z.man = W.man;

作者经常莫名其妙发明新表名，这是我猜测出来的另一张辅助表。
CREATE TABLE wife_hdr AS SELECT wife AS NAME FROM Wife_perms;

终于可以运行这个ANSWER#3:
SELECT A.name AS h1, B.name AS h2, C.name AS h3, D.name AS h4,
   E.name AS h5, F.name AS h6, G.name AS h7, H.name AS h8
  FROM wife_hdr a, wife_hdr b, wife_hdr c, wife_hdr d,
   wife_hdr e, wife_hdr f, wife_hdr g, wife_hdr  h
WHERE B.name NOT IN (A.name)
   AND C.name NOT IN (A.name, B.name)
   AND D.name NOT IN (A.name, B.name, C.name)
   AND E.name NOT IN (A.name, B.name, C.name, D.name)
   AND F.name NOT IN (A.name, B.name, C.name, D.name,E.name)
   AND G.name NOT IN (A.name, B.name, C.name, D.name,E.name, F.name)
   AND H.name NOT IN (A.name, B.name, C.name, D.name,E.name, F.name, G.name)
   AND NOT EXISTS (SELECT * FROM Unstable
                     WHERE A.name || B.name || C.name || D.name || E.name || F.name || G.name || H.name
                           LIKE bad_marriage
                  );

结果：
h1 h2 h3 h4 h5 h6 h7 h8
-------------------------
w3 w6 w4 w8 w1 w5 w7 w2
w6 w4 w3 w8 w1 w5 w7 w2
w6 w3 w4 w8 w1 w5 w7 w2
w3 w6 w4 w1 w7 w5 w8 w2
w6 w4 w3 w1 w7 w5 w8 w2
w6 w3 w4 w1 w7 w5 w8 w2
w7 w4 w3 w8 w1 w5 w2 w6
w2 w4 w3 w8 w1 w5 w7 w6
w2 w4 w3 w1 w7 w5 w8 w6

-----------------------
下面是我的答案，我看完题目后想了很久，得到的答案和#3异曲同工，都是先求全排列，再剔除不稳定组合，连用LIKE表达式的思路都是一模一样的!
只不过我用了10G的CONNECT BY NOCYCLE求全排列比作者高效得多，整个SQL即使没用辅助表也比他快一倍多，逻辑读只有他的四分之一。

WITH p AS ( ----- 这两张表主键一样，本来就应该合并为一张，保存一对男女互相给对方的评分。
SELECT SUBSTR(h.man,2) AS h,SUBSTR(w.woman,2) AS w,h.ranking hr,w.ranking wr
  FROM Husbands h, Wives w
WHERE h.man=w.man and h.woman = w.woman
)
,b AS ( --- 求出所有不稳定的过滤表达式。
SELECT /*+ materialize */ ----如果没有materialize 这个hint, 下面的NOT EXISTS就会变成用视图过滤，查询永远跑不出来
   RPAD(LPAD(p1.w,p1.h,'_')||LPAD(p2.w,p2.h-p1.h,'_'),8,'_') bad
  FROM p p1,p p2, p p3, p p4
WHERE p1.h<p2.h  ------ 用小于而不是不等于作连接条件，是为了剔除对称的另一半数据
   AND p1.w<>p2.w
   AND p1.h=p3.h AND p1.w=p4.w AND p2.h=p4.h AND p2.w=p3.w
   AND (p1.hr>p3.hr AND p2.wr>p3.wr
         OR p2.hr>p4.hr AND p1.wr>p4.wr
         )
)
,a AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(rn,','),',') AS res
  FROM (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=8)
WHERE LEVEL=8
CONNECT BY NOCYCLE rn <> PRIOR rn
)
SELECT res FROM a
WHERE NOT EXISTS (SELECT 1 FROM b WHERE a.res LIKE b.bad);

-----------
24317586
24381576
36417582
36481572
63417582
63481572
64317582
64381572
74381526

newkid · 发表于 2010-3-20 00:28

继续上贴：用BITAND操作来代替LIKE匹配

WITH p AS (
SELECT SUBSTR(h.man,2) AS h,SUBSTR(w.woman,2) AS w,h.ranking hr,w.ranking wr
  FROM Husbands h, Wives w
WHERE h.man=w.man and h.woman = w.woman
)
,b AS ( --- 求出所有不稳定的过滤表达式。
SELECT /*+ materialize */
   TO_NUMBER(RPAD(LPAD(p1.w,p1.h,'0')||LPAD(p2.w,p2.h-p1.h,'0'),8,'0'),'XXXXXXXX') bad -- 转换为16进制，准备位操作
   ,TO_NUMBER(RPAD(LPAD('F',p1.h,'0')||LPAD('F',p2.h-p1.h,'0'),8,'0'),'XXXXXXXX') bit_mask --- 用来去除所有无关的位，只留下两个女ID所对应的位置的数据
  FROM p p1,p p2, p p3, p p4
WHERE p1.h<p2.h
   AND p1.w<>p2.w
   AND p1.h=p3.h AND p1.w=p4.w AND p2.h=p4.h AND p2.w=p3.w
   AND (p1.hr>p3.hr AND p2.wr>p3.wr
         OR p2.hr>p4.hr AND p1.wr>p4.wr
         )
)
,a AS (
SELECT TO_NUMBER(REPLACE(SYS_CONNECT_BY_PATH(rn,','),','),'XXXXXXXX') AS res -- 转换为16进制，准备位操作
  FROM (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=8)
WHERE LEVEL=8
CONNECT BY NOCYCLE rn <> PRIOR rn
)
SELECT TO_CHAR(res,'XXXXXXXX') FROM a
WHERE NOT EXISTS (SELECT 1 FROM b WHERE BITAND(a.res,b.bit_mask)=b.bad) --- 用BITAND操作去掉所有其他数据后，剩下的是不稳定的两对
;

结果不如LIKE快，可能BITAND的CPU操作更昂贵。

〇〇 · 发表于 2010-3-20 08:26

答案2我这里怎么无解
你的NOCYCLE在9i里没有怎么办
SQL> WITH p AS ( ----- 这两张表主键一样，本来就应该合并为一张，保存一对男女互相给对方的评分。
  2  SELECT SUBSTR(h.man,2) AS h,SUBSTR(w.woman,2) AS w,h.ranking hr,w.ranking wr
  3 FROM Husbands h, Wives w
  4  WHERE h.man=w.man and h.woman = w.woman
  5  )
  6  ,b AS ( --- 求出所有不稳定的过滤表达式。
  7  SELECT /*+ materialize */ ----如果没有materialize 这个hint, 下面的NOT EXISTS就会变成用视图过滤，查询永远跑不出来
  8       RPAD(LPAD(p1.w,p1.h,'_')||LPAD(p2.w,p2.h-p1.h,'_'),8,'_') bad
  9 FROM p p1,p p2, p p3, p p4
10  WHERE p1.h<p2.h  ------ 用小于而不是不等于作连接条件，是为了剔除对称的另一半数据
11       AND p1.w<>p2.w
12       AND p1.h=p3.h AND p1.w=p4.w AND p2.h=p4.h AND p2.w=p3.w
13       AND (p1.hr>p3.hr AND p2.wr>p3.wr
14             OR p2.hr>p4.hr AND p1.wr>p4.wr
15             )
16  )
17  ,a AS (
18  SELECT REPLACE(SYS_CONNECT_BY_PATH(rn,','),',') AS res
19 FROM (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=8)
20  WHERE LEVEL=8
21  CONNECT BY NOCYCLE rn <> PRIOR rn
22  )
23  SELECT res FROM a
24  WHERE NOT EXISTS (SELECT 1 FROM b WHERE a.res LIKE b.bad);
CONNECT BY NOCYCLE rn <> PRIOR rn
               *
ERROR 位于第 21 行:
ORA-00920: 无效的关系运算符

已用时间:  00: 00: 00.00

SQL> with Wife_perms as
  2  (select 'w'||level wife,level tally  from dual connect by level<=8)
  3  SELECT W1.wife AS h1, W2.wife AS h2, W3.wife AS h3,
  4       W4.wife AS h4, W5.wife AS h5, W6.wife AS h6, W7.wife AS h7,
  5       W8.wife AS h8
  6 FROM Wife_perms W1, Wife_perms W2, Wife_perms W3,
  7       Wife_perms W4, Wife_perms W5, Wife_perms W6,
  8       Wife_perms W7, Wife_perms W8
  9  WHERE (W1.tally + W2.tally + W3.tally + W4.tally +
10       W5.tally + W6.tally + W7.tally + W8.tally) = 255 ---- 利用位操作实现全排列的过滤条件
11       AND NOT EXISTS (SELECT *    ------- 去除不稳定组合
12                         FROM Husbands  H1, Husbands  H2,
13                               Wives  W1, Wives  W2
14                         WHERE H1.man = H2.man
15                               AND H1.ranking > H2.ranking
16                               AND (H1.man || H1.woman) IN
17                               ('h1' || W1.wife, 'h2' || W2.wife, ---- 原SQL中的W1-W8是写的H1-H8所以报TABLE不存在的错
18                               'h3' || W3.wife, 'h4' || W4.wife,
19                               'h5' || W5.wife, 'h6' || W6.wife,
20                               'h7' || W7.wife, 'h8' || W8.wife)
21                               AND H2.woman = W1.woman
22                               AND W1.woman = W2.woman
23                               AND W1.ranking > W2.ranking
24                               AND (W1.man || W1.woman) IN
25                               ('h1' || W1.wife, 'h2' || W2.wife,
26                               'h3' || W3.wife, 'h4' || W4.wife,
27                               'h5' || W5.wife, 'h6' || W6.wife,
28                               'h7' || W7.wife, 'h8' || W8.wife)
29                      );

未选定行

已用时间:  00: 00: 20.04
SQL> with Wife_perms as
  2  (select 'w'||level wife,level tally  from dual connect by level<=8)
  3  select * from wife_perms;

WIFE                                        TALLY
----------------------------------------- ----------
w1                                              1
w2                                              2
w3                                              3
w4                                              4
w5                                              5
w6                                              6
w7                                              7
w8                                              8

已选择8行。

已用时间:  00: 00: 00.00

newkid · 发表于 2010-3-20 23:59

原来数据有错，而且SQL 漏掉了一个连接条件。
DELETE Wife_perms;
INSERT INTO Wife_perms VALUES ('w1', 1);
INSERT INTO Wife_perms VALUES ('w2', 2);
INSERT INTO Wife_perms VALUES ('w3', 4);
INSERT INTO Wife_perms VALUES ('w4', 8);
INSERT INTO Wife_perms VALUES ('w5', 16);
INSERT INTO Wife_perms VALUES ('w6', 32);
INSERT INTO Wife_perms VALUES ('w7', 64);
INSERT INTO Wife_perms VALUES ('w8', 128);

SELECT W1.wife AS h1, W2.wife AS h2, W3.wife AS h3,
   W4.wife AS h4, W5.wife AS h5, W6.wife AS h6, W7.wife AS h7,
   W8.wife AS h8
  FROM Wife_perms W1, Wife_perms W2, Wife_perms W3,
   Wife_perms W4, Wife_perms W5, Wife_perms W6,
   Wife_perms W7, Wife_perms W8
WHERE (W1.tally + W2.tally + W3.tally + W4.tally +
   W5.tally + W6.tally + W7.tally + W8.tally) = 255 ---- 利用位操作实现全排列的过滤条件
   AND NOT EXISTS (SELECT *    ------- 去除不稳定组合
                     FROM Husbands  H1, Husbands  H2,
                           Wives  W1, Wives  W2
                     WHERE H1.man = H2.man
                           AND H1.ranking > H2.ranking
                           AND (H1.man || H1.woman) IN
                           ('h1' || W1.wife, 'h2' || W2.wife, ---- 原SQL中的W1-W8是写的H1-H8所以报TABLE不存在的错
                           'h3' || W3.wife, 'h4' || W4.wife,
                           'h5' || W5.wife, 'h6' || W6.wife,
                           'h7' || W7.wife, 'h8' || W8.wife)
                           AND H2.woman = W1.woman
                           AND W1.woman = W2.woman
                           AND w2.man=h1.man    ----------- 原来漏掉了
                           AND W1.ranking > W2.ranking
                           AND (W1.man || W1.woman) IN
                           ('h1' || W1.wife, 'h2' || W2.wife,
                           'h3' || W3.wife, 'h4' || W4.wife,
                           'h5' || W5.wife, 'h6' || W6.wife,
                           'h7' || W7.wife, 'h8' || W8.wife)
                  );

新尝试：用INSTR代替LIKE。结果仍然是不如LIKE。
WITH p AS (
SELECT h.man AS h,w.woman AS w,h.ranking hr,w.ranking wr
  FROM Husbands h, Wives w
WHERE h.man=w.man and h.woman = w.woman
)
,b AS ( --- 求出所有不稳定的过滤表达式。
SELECT /*+ materialize */
   ' '||p1.h||p1.w||' ' AS b1
   ,' '||p2.h||p2.w||' ' AS b2
  FROM p p1,p p2, p p3, p p4
WHERE p1.h<p2.h
   AND p1.w<>p2.w
   AND p1.h=p3.h AND p1.w=p4.w AND p2.h=p4.h AND p2.w=p3.w
   AND (p1.hr>p3.hr AND p2.wr>p3.wr
         OR p2.hr>p4.hr AND p1.wr>p4.wr
         )
)
,a AS (
SELECT SYS_CONNECT_BY_PATH('h'||LEVEL||'w'||rn,' ')||' ' AS res -- 转换为16进制，准备位操作
  FROM (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=8)
WHERE LEVEL=8
CONNECT BY NOCYCLE rn <> PRIOR rn
)
SELECT res FROM a
WHERE NOT EXISTS (SELECT 1 FROM b WHERE INSTR(a.res,b.b1)>0 AND INSTR(a.res,b.b2)>0)
;

h1w2 h2w4 h3w3 h4w1 h5w7 h6w5 h7w8 h8w6
h1w2 h2w4 h3w3 h4w8 h5w1 h6w5 h7w7 h8w6
h1w3 h2w6 h3w4 h4w1 h5w7 h6w5 h7w8 h8w2
h1w3 h2w6 h3w4 h4w8 h5w1 h6w5 h7w7 h8w2
h1w6 h2w3 h3w4 h4w1 h5w7 h6w5 h7w8 h8w2
h1w6 h2w3 h3w4 h4w8 h5w1 h6w5 h7w7 h8w2
h1w6 h2w4 h3w3 h4w1 h5w7 h6w5 h7w8 h8w2
h1w6 h2w4 h3w3 h4w8 h5w1 h6w5 h7w7 h8w2
h1w7 h2w4 h3w3 h4w8 h5w1 h6w5 h7w2 h8w6

9i没有NOCYCLE，只好用前面那贴求全排列的其他方法了。

〇〇 · 发表于 2010-3-21 19:42

对，叫《对SQL解惑的解惑》

〇〇 · 发表于 2010-3-21 20:00

55#第一个SQL要执行35秒，52#原书答案3要45秒，newkid只要1.88秒

[ 本帖最后由〇〇于 2010-3-21 20:21 编辑 ]

〇〇 · 发表于 2010-3-21 20:22

newkid应该分析时间复杂度，告诉我们他的写法的好处在哪里

newkid · 发表于 2010-3-22 22:56

原帖由〇〇于 2010-3-21 20:22 发表
newkid应该分析时间复杂度，告诉我们他的写法的好处在哪里

大道理我可讲不来，SQL不是过程性语言，而是一种集合运算，我的思维方式就是不断地构造结果集（子查询）逐步逼近答案。每次结果都尽量过滤，让集合尽可能地小。在逐步求精的过程中查看有没有更简洁的写法让步骤（子查询层数）更少。
这个婚姻问题，原书中答案#1,#2,#3和我的答案都是同样思路，就是求出所有可能的配对方案（8!=40320种），用NOT EXIST从中剔除不稳定的组合。
#1和#2为了判断是否不稳定，需要连接原表四次。
其实可以事先把所有不稳定的两两配对找出来，总共才650种，这就是#3和我的思路。
我用了ORACLE的CONNECT BY NOCYCLE来求全排列，比书中所有方法都高效。然后我又尝试并比较了LIKE, BITAND, INSTR几种剔除方法。
还有没有改善余地呢？有！
其实，没有必要等到所有排列组合结果出来才剔除数据。
比方说，有一个不稳定组合:

17______ (即1号男配1号女，2号男配7号女)

当你看到这样的中间结果，后面的全部可以砍掉，没有必要再排列组合下去了。

这个道理我知道，可是CONNECT BY 不允许使用SYS_CONNECT_BY_PATH函数，而我手头没有11GR2, 无法尝试递归的WITH。

后来回想到30楼的排列组合题，里面有一种逐步排列的答案(#4)，正好是我需要的，我可以加入自己的过滤条件！

目前最快的写法：
WITH w AS (SELECT ROWNUM i FROM DUAL CONNECT BY ROWNUM<=8)
,p AS ( ----- 这两张表主键一样，本来就应该合并为一张，保存一对男女互相给对方的评分。
SELECT SUBSTR(h.man,2) AS h,SUBSTR(w.woman,2) AS w,h.ranking hr,w.ranking wr
  FROM Husbands h, Wives w
WHERE h.man=w.man and h.woman = w.woman
)
,b AS ( --- 求出所有不稳定的过滤表达式。
SELECT /*+ materialize */ ----如果没有materialize 这个hint, 下面的NOT EXISTS就会变成用视图过滤，查询永远跑不出来
   LPAD(p1.w,p1.h,'_')||LPAD(p2.w,p2.h-p1.h,'_')  bad
   ,p2.h lvl ----- p2.w 在第几位出现, 在此位之后的没必要组合下去了
  FROM p p1,p p2, p p3, p p4
WHERE p1.h<p2.h  ------ 用小于而不是不等于作连接条件，是为了剔除对称的另一半数据
   AND p1.w<>p2.w
   AND p1.h=p3.h AND p1.w=p4.w AND p2.h=p4.h AND p2.w=p3.w
   AND (p1.hr>p3.hr AND p2.wr>p3.wr
         OR p2.hr>p4.hr AND p1.wr>p4.wr
         )
)
,t1 AS (SELECT /*+ materialize */ SUBSTR('12345678', i, 1) a,
            SUBSTR('12345678',1,i-1)||SUBSTR('12345678',i+1) c
      FROM w
      WHERE i <= 8
   )
,t2 AS (SELECT /*+ materialize */ a || SUBSTR(c , i , 1) a,
            SUBSTR(c,1,i-1)||SUBSTR(c,i+1) c
      FROM w,t1
      WHERE i <= 7
            AND NOT EXISTS (SELECT 1 FROM b WHERE b.lvl=2 AND a || SUBSTR(c , i , 1) LIKE b.bad)
      )
,t3 AS  (SELECT /*+ materialize */ a || SUBSTR(c, i, 1) a,
            SUBSTR(c,1,i-1)||SUBSTR(c,i+1) c
      FROM w,t2
      WHERE i <= 6
            AND NOT EXISTS (SELECT 1 FROM b WHERE b.lvl=3 AND a || SUBSTR(c , i , 1) LIKE b.bad)
      )
,t4 AS  (SELECT /*+ materialize */ a || SUBSTR(c, i, 1) a,
            SUBSTR(c,1,i-1)||SUBSTR(c,i+1) c
      FROM w,t3
      WHERE i <= 5
            AND NOT EXISTS (SELECT 1 FROM b WHERE b.lvl=4 AND a || SUBSTR(c , i , 1) LIKE b.bad)
      )
,t5 AS  (SELECT /*+ materialize */ a || SUBSTR(c, i, 1) a,
            SUBSTR(c,1,i-1)||SUBSTR(c,i+1) c
      FROM w,t4
      WHERE i <= 4
            AND NOT EXISTS (SELECT 1 FROM b WHERE b.lvl=5 AND a || SUBSTR(c , i , 1) LIKE b.bad)
      )
,t6 AS  (SELECT /*+ materialize */ a || SUBSTR(c, i, 1) a,
            SUBSTR(c,1,i-1)||SUBSTR(c,i+1) c
      FROM w,t5
      WHERE i <= 3
            AND NOT EXISTS (SELECT 1 FROM b WHERE b.lvl=6 AND a || SUBSTR(c , i , 1) LIKE b.bad)
      )
,t7 AS  (SELECT /*+ materialize */ a || SUBSTR(c, i, 1) a,
            SUBSTR(c,1,i-1)||SUBSTR(c,i+1) c
      FROM w,t6
      WHERE i <= 2
            AND NOT EXISTS (SELECT 1 FROM b WHERE b.lvl=7 AND a || SUBSTR(c , i , 1) LIKE b.bad)
      )
SELECT /*+ materialize */ a || c
  FROM t7
WHERE NOT EXISTS (SELECT 1 FROM b WHERE b.lvl=8 AND a || c LIKE b.bad)
;

〇〇 · 发表于 2010-3-23 16:59

SQL> set timi on
SQL> /

A||C
-----------------------------
74381526
24381576
24317586
63481572
64381572
36481572
63417582
64317582
36417582

已选择9行。

已用时间: 00: 00: 00.26
nice!

[精华] SQL解惑(第2版) 的一些样题

回复 #56 zhangfengh 的帖子

回复 #60 newkid 的帖子

浏览过的版块