ITPUB SQL大赛第三期(二) [转帖]_MySQL, Oracle及数据库讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  MySQL, Oracle及数据库讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 4292 | 回复: 0   主题: ITPUB SQL大赛第三期(二) [转帖]        下一篇 
wayne
注册用户
等级:中校
经验:1690
发帖:221
精华:0
注册:2011-7-21
状态:离线
发送短消息息给wayne 加好友    发送短消息息给wayne 发消息
发表于: IP:您无权察看 2011-9-15 10:20:14 | [全部帖] [楼主帖] 楼主

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)”。

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

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

举个例子,对于A、B、C、D四个城市,获取全路径后,结果为AB、AC、AD、BA、BC、BD、CA、CB、CD和DA、DB、DC。而D作为起点的所有情况,都可以从其他城市为起点到D为终点的情况来获取。

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




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论