“盛拓传媒杯”SQL数据库编程大赛第三期评分及所有参赛选手答题公布！

lastwinner

原帖由 lugionline 于 11-4-12 11:04 发表



首先，这个需求并没有出现在题目的要求中，但是结果要按什么排序是在题目中明确说明的，所以就算你认为这是不足也不应当出现分数比不排序的还低，对吧？

其次，我觉得你不能要求大家对需求进行*猜测*，如果没有在题目中提到的，即使有差异也应当认为正确，比方题目中并没有提到输出列的标题用什么，你能说用
"city1 city2 fee" 做标题的是错的而 "举办城市 目标城市 费用"是正确 吗？ 这个你也可以说是正常的管理需求啊？

每一期的评分标准都会有不同的侧重点，所以评测的时候，两期中出现同样的现象，可能得分都会不一样的

newkid

下面汇报一下我从01号MSSQL的学习成果。它跟ORACLE的最大区别是在递归部分可以使用分析函数，这样UNION ALL的部分就是有选择性地叠加上去，避免了后面的数据滚雪球似的递增。为了在ORACLE中达到同样的效果我使用了TABLE()函数，遗憾的是同样的技巧只能使用一次，作者本来是用子查询x0来为x作优化，但是我如果依样画葫芦地写查询x, 两个子查询的数据都会丢失，这应该是ORACLE的BUG。

下面就是这个ORACLE的写法，递归WITH部分使用TABLE()和分析函数应该是首创，灵感创意要归功lugionline:

CREATE TYPE edge AS OBJECT (
       fn  NUMBER
      ,fm  NUMBER
      ,d   NUMBER
      ,r   NUMBER
      )
/

CREATE TYPE edge_table AS TABLE of edge
/


with
V as -- 点 (编号, 名称, 人数)
(
  select ROWNUM n, A.c, NVL(B.members, 0) m
    from (
                select city1 c from routes
                union
                select city2 c from routes
                ORDER BY 1
         ) A left join cities B on A.c = B.city_name
),
-- 边 (目标城市编号，开始城市编号，开始城市人数，两地距离)
E as
(
  select VC.n cn, VF.n fn, VF.m fm, R.d
   from (
                select city1 c, city2 f, distance d from routes
                union
                select city2 c, city1 f, distance d from routes
        ) R, V VC, V VF
   where R.c = VC.c And R.f = VF.c
),
--采样，预先计算4个，然后用计算出来的最小值去过滤X表的结果
--可能会过滤掉一些，如果运气不是太坏的话，但至少不会变得更坏
X0 (y, c, f, v, str) as --计算表 (层, 举办城市, 费用, 点标志，距离)
(
        select distinct 1, c, 0 f,
                --每个城市一个字符，标识城市是否已经在路径中
                -- cast(stuff(space(VN.n), V.n, 1, 'X') as char(100)) v,
                CAST(RPAD(LPAD('X', V.n),100) AS VARCHAR2(100)) v,
                --每个城市10个字符，城市的距离(已经说了距离是整数，这里取10位,T-SQL中按int计算)
                -- cast(stuff(space(VN.n * 10), (V.n - 1) * 10 + 1, 1, '0') as nvarchar(1000)) s
                CAST(RPAD(LPAD(RPAD('0',10), V.n  * 10),VN.n * 10)  AS VARCHAR2(1000)) as s
        from V, (select count(*) n from V) VN --where V.n <= 4
        union all
        select
                y + 1, X.c,
                X.f + Z.d * 2 * fm  f,
                -- cast(stuff(X.v, Z.fn, 1, 'X') as char(100)) v,
                SUBSTR(X.v,1,Z.fn-1)||'X'||SUBSTR(X.v,Z.fn+1) v,
                -- cast(stuff(X.s, (Z.fn - 1) * 10 + 1, 10, cast(Z.d as nchar(10))) as nvarchar(1000)) s
                SUBSTR(X.str,1,(Z.fn - 1) * 10)||RPAD(Z.d,10)||SUBSTR(X.str,(Z.fn - 1) * 10+11) s
        from X0 X,
             TABLE(CAST(MULTISET(select fn, fm,
                                               -- 加上前面路径的距离
                                              d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))) d
                                       ,row_number() over(order by d + TO_NUMBER(TRIM(SUBSTR(x.str, (E.cn - 1) * 10 + 1, 10)))) r
                                  from E
                                  where        SUBSTR(X.v, E.cn, 1) = 'X' -- 取邻接边
                                          and SUBSTR(X.v, E.fn, 1) = ' '
                                  )
                      AS edge_table
                      )
                ) Z
        where Z.r = 1
) CYCLE V SET cycle_flag TO 'Y' DEFAULT 'N'
,r AS (
SELECT *
FROM (SELECT X0.*
             ,RANK() OVER(ORDER BY f) RNK
         FROM X0
        WHERE Y=(select count(*) from V)
       )
WHERE RNK=1
)
SELECT c1,NVL(c2,'TOTAL'),SUM(cost)
  FROM (SELECT r.c c1, v.c c2, V.m * SUBSTR(r.str, (v.n - 1) * 10 + 1, 10) * 2 cost
          FROM r,v
         WHERE r.c<>v.c
        )
WHERE cost>0
GROUP BY c1,ROLLUP(c2)
ORDER BY c1,c2 NULLS FIRST;

我心里还有一个想法，就是在递归部分使用标量子查询，也是从这里得到的启发，不知道效果怎样，等有空再来实现。

newkid

标量子查询看起来眼花缭乱，还真的能行，我偷师的本领确实不是盖的：

with
V as -- 点 (编号, 名称, 人数)
(
  select ROWNUM n, A.c, NVL(B.members, 0) m
    from (
                select city1 c from routes
                union
                select city2 c from routes
                ORDER BY 1
         ) A left join cities B on A.c = B.city_name
),
-- 边 (目标城市编号，开始城市编号，开始城市人数，两地距离)
E as
(
  select VC.n cn, VF.n fn, VF.m fm, R.d
   from (
                select city1 c, city2 f, distance d from routes
                union
                select city2 c, city1 f, distance d from routes
        ) R, V VC, V VF
   where R.c = VC.c And R.f = VF.c
),
--采样，预先计算4个，然后用计算出来的最小值去过滤X表的结果
--可能会过滤掉一些，如果运气不是太坏的话，但至少不会变得更坏
X0 (y, c, f, v, str) as --计算表 (层, 举办城市, 费用, 点标志，距离)
(
        select distinct 1, c, 0 f,
                --每个城市一个字符，标识城市是否已经在路径中
                CAST(RPAD(LPAD('X', V.n),VN.n) AS VARCHAR2(1000)) v,
                --每个城市10个字符，城市的距离(已经说了距离是整数，这里取10位,T-SQL中按int计算)
                CAST(RPAD(LPAD(RPAD('0',10), V.n  * 10),VN.n * 10)  AS VARCHAR2(1000)) as s
        from V, (select count(*) n from V) VN --where V.n <= 4
        union all
        select
                y + 1
               ,X.c
               ,X.f + 2* SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),1,10)
                       * SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),21,10)
               ,SUBSTR(X.v,1,SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10)-1)
                ||'X'
                ||SUBSTR(X.v,SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10)+1) v
               ,SUBSTR(X.str,1,(SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10) - 1) * 10)
                ||SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),1,10)
                ||SUBSTR(X.str,(SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10) - 1) * 10+11) s
        from X0 X
       WHERE y<(SELECT COUNT(*) FROM v)
) CYCLE V SET cycle_flag TO 'Y' DEFAULT 'N'
,r AS (
SELECT *
FROM (SELECT X0.*
             ,RANK() OVER(ORDER BY f) RNK
         FROM X0
        WHERE Y=(select count(*) from V)
       )
WHERE RNK=1
)
SELECT c1,NVL(c2,'TOTAL'),SUM(cost)
  FROM (SELECT r.c c1, v.c c2, V.m * SUBSTR(r.str, (v.n - 1) * 10 + 1, 10) * 2 cost
          FROM r,v
         WHERE r.c<>v.c
        )
WHERE cost>0
GROUP BY c1,ROLLUP(c2)
ORDER BY c1,c2 NULLS FIRST;

newkid

加上x0对x的优化，这下差不多了：

with
V as -- 点 (编号, 名称, 人数)
(
  select ROWNUM n, A.c, NVL(B.members, 0) m
    from (
                select city1 c from routes
                union
                select city2 c from routes
                ORDER BY 1
         ) A left join cities B on A.c = B.city_name
),
-- 边 (目标城市编号，开始城市编号，开始城市人数，两地距离)
E as
(
  select VC.n cn, VF.n fn, VF.m fm, R.d
   from (
                select city1 c, city2 f, distance d from routes
                union
                select city2 c, city1 f, distance d from routes
        ) R, V VC, V VF
   where R.c = VC.c And R.f = VF.c
),
--采样，预先计算4个，然后用计算出来的最小值去过滤X表的结果
--可能会过滤掉一些，如果运气不是太坏的话，但至少不会变得更坏
X0 (y, c, f, v, str) as --计算表 (层, 举办城市, 费用, 点标志，距离)
(
        select distinct 1, c, 0 f,
                --每个城市一个字符，标识城市是否已经在路径中
                CAST(RPAD(LPAD('X', V.n),VN.n) AS VARCHAR2(1000)) v,
                --每个城市10个字符，城市的距离(已经说了距离是整数，这里取10位,T-SQL中按int计算)
                CAST(RPAD(LPAD(RPAD('0',10), V.n  * 10),VN.n * 10)  AS VARCHAR2(1000)) as s
        from V, (select count(*) n from V) VN where V.n <= 4
        union all
        select
                y + 1
               ,X.c
               ,X.f + 2* SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),1,10)
                       * SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),21,10)
               ,SUBSTR(X.v,1,SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10)-1)
                ||'X'
                ||SUBSTR(X.v,SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10)+1) v
               ,SUBSTR(X.str,1,(SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10) - 1) * 10)
                ||SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),1,10)
                ||SUBSTR(X.str,(SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10) - 1) * 10+11) s
        from X0 X
       WHERE y<(SELECT COUNT(*) FROM v)
) CYCLE V SET cycle_flag TO 'Y' DEFAULT 'N'
,F(n) as (select min(f) from X0 where y = (select count(*) from V))
,X (y, c, f, v, str) as --计算表 (层, 举办城市, 费用, 点标志，距离)
(
        select distinct 1, c, 0 f,
                --每个城市一个字符，标识城市是否已经在路径中
                CAST(RPAD(LPAD('X', V.n),VN.n) AS VARCHAR2(1000)) v,
                --每个城市10个字符，城市的距离(已经说了距离是整数，这里取10位,T-SQL中按int计算)
                CAST(RPAD(LPAD(RPAD('0',10), V.n  * 10),VN.n * 10)  AS VARCHAR2(1000)) as s
        from V, (select count(*) n from V) VN where V.n > 4
        union all
        select
                y + 1
               ,X.c
               ,X.f + 2* SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),1,10)
                       * SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),21,10)
               ,SUBSTR(X.v,1,SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10)-1)
                ||'X'
                ||SUBSTR(X.v,SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10)+1) v
               ,SUBSTR(X.str,1,(SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10) - 1) * 10)
                ||SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),1,10)
                ||SUBSTR(X.str,(SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10) - 1) * 10+11) s
        from X
       WHERE y<(SELECT COUNT(*) FROM v)
             AND X.f + 2* SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),1,10)
                       * SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),21,10)
                 <=(select n from F)
) CYCLE V SET cycle_flag TO 'Y' DEFAULT 'N'
,r AS (
SELECT *
FROM (SELECT x2.*
             ,RANK() OVER(ORDER BY f) RNK
         FROM (SELECT * FROM X0 WHERE Y=(select count(*) from V)
               UNION ALL
               SELECT * FROM X WHERE Y=(select count(*) from V)
               ) x2
       )
WHERE RNK=1
)
SELECT c1,NVL(c2,'TOTAL'),SUM(cost)
  FROM (SELECT r.c c1, v.c c2, V.m * SUBSTR(r.str, (v.n - 1) * 10 + 1, 10) * 2 cost
          FROM r,v
         WHERE r.c<>v.c
        )
WHERE cost>0
GROUP BY c1,ROLLUP(c2)
ORDER BY c1,c2 NULLS FIRST;

newkid

两次用嵌套表会出错，来个混合版，X0用标量子查询，比较昂贵的X用嵌套表，在ORACLE下表现不错：
with
V as -- 点 (编号, 名称, 人数)
(
  select ROWNUM n, A.c, NVL(B.members, 0) m
    from (
                select city1 c from routes
                union
                select city2 c from routes
                ORDER BY 1
         ) A left join cities B on A.c = B.city_name
),
-- 边 (目标城市编号，开始城市编号，开始城市人数，两地距离)
E as
(
  select VC.n cn, VF.n fn, VF.m fm, R.d
   from (
                select city1 c, city2 f, distance d from routes
                union
                select city2 c, city1 f, distance d from routes
        ) R, V VC, V VF
   where R.c = VC.c And R.f = VF.c
),
--采样，预先计算4个，然后用计算出来的最小值去过滤X表的结果
--可能会过滤掉一些，如果运气不是太坏的话，但至少不会变得更坏
X0 (y, c, f, v, str) as --计算表 (层, 举办城市, 费用, 点标志，距离)
(
        select distinct 1, c, 0 f,
                --每个城市一个字符，标识城市是否已经在路径中
                CAST(RPAD(LPAD('X', V.n),VN.n) AS VARCHAR2(1000)) v,
                --每个城市10个字符，城市的距离(已经说了距离是整数，这里取10位,T-SQL中按int计算)
                CAST(RPAD(LPAD(RPAD('0',10), V.n  * 10),VN.n * 10)  AS VARCHAR2(1000)) as s
        from V, (select count(*) n from V) VN where V.n <= 4
        union all
        select
                y + 1
               ,X.c
               ,X.f + 2* SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),1,10)
                       * SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),21,10)
               ,SUBSTR(X.v,1,SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10)-1)
                ||'X'
                ||SUBSTR(X.v,SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10)+1) v
               ,SUBSTR(X.str,1,(SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10) - 1) * 10)
                ||SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),1,10)
                ||SUBSTR(X.str,(SUBSTR((SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' '),11,10) - 1) * 10+11) s
        from X0 X
       WHERE y<(SELECT COUNT(*) FROM v)
) CYCLE V SET cycle_flag TO 'Y' DEFAULT 'N'
,F(n) as (select min(f) from X0 where y = (select count(*) from V))
,X (y, c, f, v, str) as --计算表 (层, 举办城市, 费用, 点标志，距离)
(
        select distinct 1, c, 0 f,
                --每个城市一个字符，标识城市是否已经在路径中
                CAST(RPAD(LPAD('X', V.n),VN.n) AS VARCHAR2(1000)) v,
                --每个城市10个字符，城市的距离(已经说了距离是整数，这里取10位,T-SQL中按int计算)
                CAST(RPAD(LPAD(RPAD('0',10), V.n  * 10),VN.n * 10)  AS VARCHAR2(1000)) as s
        from V, (select count(*) n from V) VN where V.n > 4
        union all
        select  y + 1
               ,X.c
               ,X.f + 2* SUBSTR(z.COLUMN_VALUE,1,10)
                       * SUBSTR(z.COLUMN_VALUE,21,10)
               ,SUBSTR(X.v,1,SUBSTR(z.COLUMN_VALUE,11,10)-1)
                ||'X'
                ||SUBSTR(X.v,SUBSTR(z.COLUMN_VALUE,11,10)+1) v
               ,SUBSTR(X.str,1,(SUBSTR(z.COLUMN_VALUE,11,10) - 1) * 10)
                ||SUBSTR(z.COLUMN_VALUE,1,10)
                ||SUBSTR(X.str,(SUBSTR(z.COLUMN_VALUE,11,10) - 1) * 10+11) s
        from X,TABLE(CAST(MULTISET(SELECT MIN(LPAD(e.d + TO_NUMBER(TRIM(SUBSTR(X.str, (E.cn - 1) * 10 + 1, 10))),10)||LPAD(e.fn,10)||LPAD(e.fm,10)) FROM e where SUBSTR(X.v, E.cn, 1) = 'X' and SUBSTR(X.v, E.fn, 1) = ' ')
                            AS sys.odcivarchar2list
                            )
                        ) z
       WHERE y<(SELECT COUNT(*) FROM v)
             AND X.f + 2* SUBSTR(z.COLUMN_VALUE,1,10)
                       * SUBSTR(z.COLUMN_VALUE,21,10)
                 <=(select n from F)
) CYCLE V SET cycle_flag TO 'Y' DEFAULT 'N'
,r AS (
SELECT *
FROM (SELECT x2.*
             ,RANK() OVER(ORDER BY f) RNK
         FROM (SELECT * FROM X0 WHERE Y=(select count(*) from V)
               UNION ALL
               SELECT * FROM X WHERE Y=(select count(*) from V)
               ) x2
       )
WHERE RNK=1
)
SELECT c1,NVL(c2,'TOTAL'),SUM(cost)
  FROM (SELECT r.c c1, v.c c2, V.m * SUBSTR(r.str, (v.n - 1) * 10 + 1, 10) * 2 cost
          FROM r,v
         WHERE r.c<>v.c
        )
WHERE cost>0
GROUP BY c1,ROLLUP(c2)
ORDER BY c1,c2 NULLS FIRST;

lugionline

原帖由 newkid 于 2011-4-12 23:46 发表

关于MSSQL的CTE我有个疑问。在UNION ALL里面的X, 你看到的数据是截止目前X表的全部数据，还是只有最近的一层？（层数＝MAX(Y)）
你的row_number()是不是对每个X记录分别排序(相当于有个隐含的PARTITION BY)，还是对新产生的所有数据进行排序？

递归部分的 X 表是上一次的计算结果
The semantics of the recursive execution is as follows:
1.Split the CTE expression into anchor and recursive members.
2.Run the anchor member(s) creating the first invocation or base result set (T0).
3.Run the recursive member(s) with Ti as an input and Ti+1 as an output.
4.Repeat step 3 until an empty set is returned.
5.Return the result set. This is a UNION ALL of T0 to Tn.

row_number的确对每条X分别排序

with
a(n) as (select 'b' union select 'a'),
b(n) as (select 1 union select 2),
x (v, n, n1, r) as
(
        select 0, n, 0, cast(0 as bigint) from a
        union all
        select x.v + 1, x.n, b.n,
        ROW_NUMBER() over(order by x.n, b.n) r
        from x ,b where v < 1
)
select * from x order by v, n, n1

结果
v           n    n1          r
----------- ---- ----------- --------------------
0           a    0           0
0           b    0           0
1           a    1           1
1           a    2           2
1           b    1           1
1           b    2           2

也就是上面的 order by x.n 其实是没有用的，这是一个让人惊奇的结果

〇〇

ROW_NUMBER() over(order by b.n, x.n) 输出什么

lugionline

v           n    n1          r
----------- ---- ----------- --------------------
0           a    0           0
0           b    0           0
1           a    1           1
1           a    2           2
1           b    1           1
1           b    2           2

这个row_number执行的时机是处理当前递归表的某一条记录时做的，所以对递归表的字段排序或者partition没有任何意义

有人认为这个是个bug，MS把这个叫做特性，不过对于第三题，这个还真是一个特性