本站内容搜索:
   您的位置:素材中国>>教程 >>数据库 >>MS SQL >>用SQL解决有向图问题 提交错误报告
用SQL解决有向图问题
[ 来源:素材中国 | 作者:| 时间:2006-01-12 14:15:23 | 浏览:人次 ]

 
 

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

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

 
 
       
   您的位置:素材中国>>教程 >>数据库 >>MS SQL >>用SQL解决有向图问题
 点此在百度搜索关键字"用SQL解决有向图问题"  点此在GOOGLE搜索关键字"用SQL解决有向图问题"
热门文章:
  ·二进制转十进制的SQL函数   ·SQL2005 SSIS
  ·对数据库字段使用默认值   ·exp/imp导出导入工具的使用
  ·经常用到的交叉表问题,一般用动态SQL能生成动态列   ·精华全面接触SQL语法
  ·在存储过程中连接远程数据库并进行操作   ·SqlServer的更新锁(UPDLOCK)
  ·几种分页算法。翻页必备   ·关于SQL Server SQL语句查询分页数据的解决方案

  首页  素材图片  高精图库  矢量图库  网页素材  网页模板  壁纸  明星  下载  教程  字体  香车美女  QQ专题  论坛

网站介绍 | 广告业务 | 设计业务 | 免责声明 | 版权声明 | 联系我们|提交错误报告
素材中国版权所有