ITPub博客

首页 > Linux操作系统 > Linux操作系统 > ITPUB SQL大赛第三期(二)

ITPUB SQL大赛第三期(二)

原创 Linux操作系统 作者:yangtingkun 时间:2011-04-13 23:51:38 0 删除 编辑

SQL大赛第三期解法的最终答案。

第三期题目参考:http://www.itpub.net/thread-1408182-1-1.html

版主newkid点评参考:http://www.itpub.net/thread-1415335-1-1.html

ITPUB SQL大赛第三期:http://yangtingkun.itpub.net/post/468/516164

 

由于时间的关系,一直没有时间去检查第三期到底哪里出现了错误。

检查查看了一下代码,发现问题出在一个偷懒的想法上。

由于上一篇文章最后贴出的代码就是存在问题的代码,这里就不重复贴出了,下面给出的是修改之后的代码:

SQL> WITH ROUTE_D AS
  2  (
  3   SELECT CITY1 R, CITY2 T, DISTANCE DIS
  4   FROM ROUTES
  5   UNION ALL
  6   SELECT CITY2, CITY1, DISTANCE
  7   FROM ROUTES
  8  ),
  9  ROUTE_ALL_D (C1, C2, LINES, DISTANCE) AS 
 10  (
 11   SELECT R, T, CAST('"' || R || '"' || T || '"' AS VARCHAR2(4000)), DIS
 12   FROM ROUTE_D
 13   WHERE R != (SELECT MAX(GREATEST(CITY1, CITY2)) FROM ROUTES)
 14   UNION ALL
 15   SELECT A.C1, T, LINES || T || '"', DIS + DISTANCE
 16   FROM ROUTE_D R, ROUTE_ALL_D A
 17   WHERE A.C2 = R.R
 18   AND INSTR(LINES, '"' || T || '"', 1, 1) = 0
 19   AND DISTANCE + DIS <=
 20    NVL
 21    (
 22     (
 23      SELECT DISTANCE
 24      FROM ROUTES RS
 25      WHERE (A.C1 = RS.CITY1
 26       AND R.T = RS.CITY2)
 27      OR (A.C1 = RS.CITY2
 28       AND R.T = RS.CITY1)
 29     ),
 30     9.9E38
 31    )
 32  ),
 33  RESULT_HALF AS
 34  (
 35   SELECT C1 R, C2 T, MIN(DISTANCE) DIS
 36   FROM ROUTE_ALL_D
 37   WHERE C1 < C2
 38   GROUP BY C1, C2
 39  ),
 40  RESULT_ALL AS
 41  (
 42   SELECT R, T, DIS
 43   FROM RESULT_HALF
 44   UNION ALL
 45   SELECT T, R, DIS
 46   FROM RESULT_HALF
 47  ),
 48  RESULT AS
 49  (
 50   SELECT R, T,
 51    DIS * 2 * C.MEMBERS COST,
 52    SUM(DIS * 2 * C.MEMBERS) OVER(PARTITION BY R) COST_CITY
 53   FROM RESULT_ALL R, CITIES C
 54   WHERE R.T = C.CITY_NAME(+)
 55  )
 56  SELECT R, NVL(T, 'TOTAL') T, NVL(SUM(COST), 0) COST
 57  FROM
 58  (
 59   SELECT R, T, COST, RANK() OVER(ORDER BY COST_CITY) RN
 60   FROM RESULT
 61  )
 62  WHERE RN = 1
 63  GROUP BY GROUPING SETS ((R, T), R)
 64  ORDER BY R, DECODE(T, 'TOTAL', CHR(0), T)
 65  ;

R          T                COST
---------- ---------- ----------
D          TOTAL           68356
D          A                3200
D          B                3224
D          C                3634
D          E                7300
D          F                7598
D          G                3840
D          H               14580
D          I                4400
D          J               12352
D          K                8228
D          L                   0

已选择12行。

SQL大赛中提交的代码的唯一区别是第13行,这里是“WHERE R != (SELECT MAX(GREATEST(CITY1, CITY2)) FROM ROUTES)”,而SQL大赛中出现问题的语句是“WHERE R != (SELECT MAX(CITY_NAME) FROM CITIES)”。

这里的本意是指,由于AB的距离和BA的距离是相等的,所以在获取全路径的时候,没有必要将所有的CITY都作为起点,可以有一个城市不作为起点进行递归,获取到其他城市的路径,因为这个城市所有的路径都可以从其他城市的结果中获取。

而这个城市取最大的城市,SQL相对更容易实现,因为随后的RESULT_HALF会取所有C1 < C2的结果,然后调换起点、终点来得到全路径。

举个例子,对于ABCD四个城市,获取全路径后,结果为ABACADBABCBDCACBCDDADBDC。而D作为起点的所有情况,都可以从其他城市为起点到D为终点的情况来获取。

这个优化的思路并没有问题,问题在于开始本打算用ROUTES表中最大的列来进行过滤,但是发现CITY信息存在于ROUTES表中的CITY1CITY2两个列中,要不然需要使用UNION ALL要不然需要上面这样使用GREATEST方式,这显得比较麻烦,由于CITIES表中所有城市存在一个列中,于是偷懒使用了这张表。但是忘记了这张表中的数据可能并不完全,比如默认数据的例子中就缺少了L。可惜的是,这个错误并没有导致上面的查询结果发生改变,因此这个错误在测试的时候并没有检查出来。

 

 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/4227/viewspace-692463/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
暂无介绍

注册时间:2007-12-29

  • 博文量
    1955
  • 访问量
    10524820