用SQL解决有向图问题

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

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

查看本文来源