一道数据库开发面试题

已知表route,字段和内容如下:

起始节点 终止节点 距离

a	b	100
a	c	150
a	d	200
b	e	300
b	f	800
e	g	100

要求写sql或者一段代码,找出从节点a开始能到达的所有终点节点(包括间接到达).

1.创建表route,插入数据

CREATE TABLE route (
  begin_node VARCHAR2(3),
  end_node VARCHAR2(3),
  distance NUMBER(4));

INSERT INTO route VALUES('a','b',100);
INSERT INTO route VALUES('a','c',150);
INSERT INTO route VALUES('a','d',200);
INSERT INTO route VALUES('b','e',300);
INSERT INTO route VALUES('b','f',800);
INSERT INTO route VALUES('e','b',100);

2.创建字符串数组类型

CREATE OR REPLACE TYPE t_string_array IS TABLE OF VARCHAR2(10);

3.创建函数,在字符串数组中查找指定的字符串

CREATE OR REPLACE FUNCTION FindInStringArray(src t_string_array, dest VARCHAR2)
RETURN BOOLEAN
IS
i NUMBER(4);
BEGIN
  FOR i in 1..src.COUNT LOOP
    IF src(i)=dest THEN
      RETURN TRUE;
    END IF;
  END LOOP;
  RETURN FALSE;
END;

4.PL/SQL

DECLARE

v_begin_node VARCHAR2(3);
v_end_node VARCHAR2(3);

CURSOR c_route IS SELECT end_node FROM route WHERE begin_node=v_begin_node;

--已经搜索到的途经的节点集合


searchedNodes t_string_array := t_string_array('a');

--节点集合中将要处理的位置


index0 NUMBER(5) := 1;

BEGIN
  --遍历途经的每一个点


  WHILE index0 <= searchedNodes.COUNT LOOP
    --当前要处理的节点


    v_begin_node := searchedNodes(index0);
    
    --当前节点可直接通往的节点


    OPEN c_route;
  
    LOOP
      FETCH c_route INTO v_end_node;
      EXIT WHEN c_route%NOTFOUND;
    
      IF NOT FindInStringArray(searchedNodes, v_end_node) THEN
        --这是一个未在集合中出现过的新节点,增加到集合


        searchedNodes.EXTEND(1);
        searchedNodes(searchedNodes.COUNT) := v_end_node;
        --输出


        DBMS_OUTPUT.PUT_LINE(v_end_node);
      END IF;
    END LOOP;
    
    CLOSE c_route;
    --集合中的下一元素


    index0:=index0 + 1;
  END LOOP;

END;

5.如果数据间引用不存在环路,还可以用递归查询来完成

SELECT end_node FROM route
CONNECT BY begin_node=PRIOR end_node
START WITH begin_node='a'

6.如果要打印出从a开始的遍历路径,该怎么办呢?

PL/SQL 的递归调用

评论

1 楼 蔡华江 2010-03-18  

5.如果数据间引用不存在环路,还可以用递归查询来完成
如果出现环路用connect by nocycle