用SQL解决有向图问题

2009-12-14 18:41| 发布者: admin| 查看: 21| 评论: 0|原作者: 段誉

■一个常见的高级计算机科学问题可以在“有向......

一个常见的高级计算机科学问题可以在“有向图”的范畴之下描述。有向图是由一组向量和边所连接的一组有限的节点。例如，一个节点可以想象为一座“城市”，而每个向量可以想象为两座城市间的一个“航线”。
有很多算法和论文讲到如何解决每种可能路线的遍历问题以及寻找最短路径或者最小代价路径的问题。这些算法中大部分都是过程化的，或者是使用递归方面来解决的。然而 SQL 的声明性语言使得解决复杂的有向图问题更加容易，而且不需要很多代码。
让我们以两座城市之间的航线为例子，创建一个表保存一些假想数据：
create table airports
(
code char(3) constraint airports_pk primary key,
description varchar2(200)
);
insert into airports values ('LHR','London Heathrow, UK');
insert into airports values ('JFK','New York-Kennedy, USA');
insert into airports values ('GRU','Sao Paulo, Brazil');
create table fares
(
depart char(3),
arrive char(3),
price number,
constraint fares_pk primary key (depart,arrive),
constraint fares_depart_fk foreign key (depart) references airports,
constraint fares_arrive_fk foreign key (arrive) references airports
);
insert into fares values('LHR','JFK',700);
insert into fares values('JFK','GRU',600);
insert into fares values('LHR','GRU',1500);
insert into fares values('GRU','LHR',1600);
不能使用CONNECT BY 语法来解决如何从伦敦到圣保罗，因为在图中有数据产生一个环（从圣保罗飞回）：
select * from fares connect by prior arrive = depart start with depart = 'LHR';
ERROR:
ORA-01436: CONNECT BY loop in user data
要解决有向图问题，我们需要创建一个临时表来保存两个节点之间所有可能的路径。我们必须注意不复制已经处理过的路径，而且在这种情况下，我们不想路径走回开始处的同一个地点。我还希望跟踪到达目的地所需航程的数目，以及所走路线的描述。
临时表使用以下脚本创建：
create global temporary table faretemp
(
depart char(3),
arrive char(3),
hops integer,
route varchar2(30),
price number,
constraint faretemp_pk primary key (depart,arrive)
);
一个简单的视图可以在稍微简化这个例子中使用的代码。视图可以根据 fares 表中的单个航程计算从 faretemp 表中的一个路径到达一下一个航程的数据：
create or replace view nexthop
as
select src.depart,
dst.arrive,
src.hops+1 hops,
src.route||','||dst.arrive route,
src.price + dst.price price
from faretemp src,fares dst
where src.arrive = dst.depart
and dst.arrive != src.depart;
/
show errors;

收藏分享邀请

		自动登录	找回密码
密码			注册

用SQL解决有向图问题

最新评论

相关分类

下级分类