[Oracle]用SQL解决有向图问题

作者：Builder.com 来源:

 

一个常见的高级计算机科学问题可以在“有向图”的范畴之下描述。有向图是由一组向量和边所连接的一组有限的节点。例如，一个节点可以想象为一座“城市”，而每个向量可以想象为两座城市间的一个“航线”。

有很多算法和论文讲到如何解决每种可能路线的遍历问题以及寻找最短路径或者最小代价路径的问题。这些算法中大部分都是过程化的，或者是使用递归方面来解决的。然而 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;

这个算法相当简单。首先，使用 fares 表中的数据填充 faretemp 表，作为初始的航程。然后，取到我们刚才插入的所有数据，使用它们建立所有可能的二航程（two-hop）路径。重复这一过程，直至在两个节点之间创建了新路径。循环过程将在节点间所有可能的路径都被描述之后退出。如果我们只对某个开始条件感兴趣，那么我们还可以限制第一次的插入从而减少装载数据的量。下面是发现路径的代码：

truncate table faretemp;
begin
    -- initial connections
    insert into faretemp
     select depart,arrive,1,depart||','||arrive,price from fares;
    while sql%rowcount > 0 loop
        insert into faretemp
            select depart,arrive,hops,route,price from nexthop
             where (depart,arrive)
                   not in (select depart,arrive from faretemp);
    end loop;
end;
/
show errors;

select * from faretemp order by depart,arrive;

可以在 中查看输出。

前面的数据有一个小问题。数据是点之间最短路径（最小航程数）的集合。然而，从伦敦到圣保罗的航程却不是最便宜的一个。

要解决最便宜的费用问题，需要对我们的循环做一个改进，当在一个航程中发现一个更便宜的路线时使用这个路线代替原来的路线。修改后的代码如下：

truncate table faretemp;
declare
    l_count integer;
begin
    -- initial connections
    insert into faretemp
        select depart,arrive,1,depart||','||arrive,price from fares;
    l_count := sql%rowcount;
    while l_count > 0 loop
        update faretemp
           set (hops,route,price) =
              (select hops,route,price from nexthop
                where depart = faretemp.depart
                  and arrive = faretemp.arrive)
         where (depart,arrive) in
             (select depart,arrive from nexthop
               where price < faretemp.price);
        l_count := sql%rowcount;
        insert into faretemp
            select depart,arrive,hops,route,price from nexthop
             where (depart,arrive)
               not in (select depart,arrive from faretemp);
        l_count := l_count + sql%rowcount;
    end loop;
end;
/
show errors;

select * from faretemp order by depart,arrive;

可能在中查看输出。

算法发现LHR、JFK、GRU 路线比 LHR、GRU 路线便宜，所以用前者代替了后者。循环将在没有更便宜的费用，并且没有其它可能路线时退出。

---

本文作者：Scott Stephens已经在Oracle工作了13年有余，他曾经在技术支持、电子商务、市场和软件开发等部门工作。更多Scott Stephens 的 Oracle 技巧，请访问我们的.

---