8.6節から8.8節

8.6 グラフの操作

8.6.1 テーブルの準備

PostgreSQL Oracle DB2 
CREATE LANGUAGE plpgsql;
 
SET AUTOCOMMIT ON;
SET TIMING ON;
SET SERVEROUTPUT ON;
 データベース・ロギングの構成ウィザードで、各ログ・ファイルのサイズを1024から4096に変更

テーブル:nodes

MySQL, PostgreSQL, DB2, SQL Server Oracle 
CREATE TABLE nodes(
  id INT NOT NULL,
  name VARCHAR(20) DEFAULT '' NOT NULL,
  CONSTRAINT nodes_pri PRIMARY KEY (id)
);
CREATE INDEX name_idx ON nodes (name);
 
CREATE TABLE nodes (
  id INT NOT NULL,
  name VARCHAR (20),
  CONSTRAINT nodes_pri PRIMARY KEY (id)
);
CREATE INDEX name_idx ON nodes (name);

テーブル:edges

共通 
CREATE TABLE edges(
  head INT NOT NULL,
  tail INT NOT NULL,
  CONSTRAINT edges_pri PRIMARY KEY (head,tail)
);
CREATE INDEX head_idx ON edges (head);
CREATE INDEX tail_idx ON edges (tail);

サンプルデータ

MySQL, PostgreSQL, DB2 Oracle, SQL Server 
INSERT INTO nodes (id,name) VALUES
(1,'A1'),(2,'A2'),(3,'A3'),(4,'A4'),(5,'A5'),
(6,'A6'),(7,'A7'),(8,'A8'),(9,'A9');

INSERT INTO edges (head,tail) VALUES
(1,2),(1,3),(1,4),(2,5),(2,6),
(3,6),(3,7),(6,8),(6,9);
 
INSERT INTO nodes (id,name) VALUES (1,'A1');
INSERT INTO nodes (id,name) VALUES (2,'A2');
INSERT INTO nodes (id,name) VALUES (3,'A3');
INSERT INTO nodes (id,name) VALUES (4,'A4');
INSERT INTO nodes (id,name) VALUES (5,'A5');
INSERT INTO nodes (id,name) VALUES (6,'A6');
INSERT INTO nodes (id,name) VALUES (7,'A7');
INSERT INTO nodes (id,name) VALUES (8,'A8');
INSERT INTO nodes (id,name) VALUES (9,'A9');

INSERT INTO edges (head,tail) VALUES (1,2);
INSERT INTO edges (head,tail) VALUES (1,3);
INSERT INTO edges (head,tail) VALUES (1,4);
INSERT INTO edges (head,tail) VALUES (2,5);
INSERT INTO edges (head,tail) VALUES (2,6);
INSERT INTO edges (head,tail) VALUES (3,6);
INSERT INTO edges (head,tail) VALUES (3,7);
INSERT INTO edges (head,tail) VALUES (6,8);
INSERT INTO edges (head,tail) VALUES (6,9);

ノードあたりの平均エッジ数

共通 
SELECT AVG(c) FROM (
  SELECT id,SUM(c) AS c FROM (
    (SELECT head AS id,COUNT(tail) AS c FROM edges GROUP BY head)
    UNION ALL
    (SELECT tail AS id,COUNT(head) AS c FROM edges GROUP by tail)
  ) tmp
  GROUP BY id
) tmp2;

大きなグラフの作成（下のmakeNumSeqを作ってから）

MySQL PostgreSQL Oracle DB2
（ステートメント終了文字を「@」にしています）		 SQL Server 
CALL makeNumSeq(500);


TRUNCATE TABLE nodes;
 
SELECT makeNumSeq(500);


TRUNCATE TABLE nodes;
 
CALL makeNumSeq(500);


TRUNCATE TABLE nodes;
 
CALL makeNumSeq(500);


DELETE FROM nodes;
 
EXECUTE makeNumSeq 500
GO

TRUNCATE TABLE nodes
GO
 
INSERT INTO nodes (id,name) SELECT n AS id,'' AS name FROM numSequence;
 
TRUNCATE TABLE edges;


INSERT INTO edges (head,tail)
  SELECT a.id AS head,b.id AS tail
  FROM nodes a,nodes b
  WHERE a.id!=b.id
  ORDER BY RAND()
  LIMIT 1250; -- 5*500/2

TRUNCATE TABLE edges;


INSERT INTO edges (head,tail)
  SELECT a.id AS head,b.id AS tail
  FROM nodes a,nodes b
  WHERE a.id!=b.id
  ORDER BY RANDOM()
  LIMIT FLOOR(5*500/2);
 
TRUNCATE TABLE edges;


INSERT INTO edges (head,tail)
  SELECT * FROM (
    SELECT a.id AS head,b.id AS tail
    FROM nodes a,nodes b
    WHERE a.id!=b.id
    ORDER BY DBMS_RANDOM.VALUE()
  ) tmp
  WHERE ROWNUM<=FLOOR(5*500/2);
 
DELETE FROM edges;


INSERT INTO edges (head,tail)
  SELECT a.id head,b.id tail
  FROM nodes a,nodes b
  WHERE a.id!=b.id
  ORDER BY RAND()
  FETCH FIRST 1250 ROWS ONLY;
-- 5*500/2
 
TRUNCATE TABLE edges
GO

INSERT INTO edges (head,tail)
  SELECT TOP (5*500/2) a.id head,b.id tail
  FROM nodes a,nodes b
  WHERE a.id!=b.id
  ORDER BY NEWID()

8.8 ストアド・プロシジャ

8.8.1 連番データの作成

MySQL PostgreSQL Oracle DB2
（ステートメント終了文字を「@」にしています）		 SQL Server 
DROP TABLE IF EXISTS numSequence;





CREATE TABLE numSequence (n INT);
 






CREATE TABLE numSequence (n INT);
 






CREATE TABLE numSequence (n INT);
 






CREATE TABLE numSequence (n INT);
 
IF EXISTS (SELECT * FROM dbo.sysobjects
  WHERE id = OBJECT_ID(N'numSequence') AND
    OBJECTPROPERTY(id, N'IsUserTable') = 1)
  DROP TABLE numSequence
GO

CREATE TABLE numSequence (n INT)
GO

プロシジャ:makeNumSeq

MySQL PostgreSQL Oracle DB2
（ステートメント終了文字を「@」にしています）		 SQL Server 
DROP PROCEDURE IF EXISTS makeNumSeq;





DELIMITER // -- 区切り文字を「//」に変更
CREATE PROCEDURE makeNumSeq(maxNum INT)
BEGIN
  DECLARE i INT DEFAULT 1;
  DELETE FROM numSequence;
  WHILE i<=maxNum DO
    INSERT INTO numSequence (n) VALUES (i);
    SET i=i+1;
  END WHILE;
END//
DELIMITER ; -- 区切り文字を「;」に戻す





CALL makeNumSeq(500); -- ストアド・プロシジャの実行
 
DROP FUNCTION makeNumSeq(INT);






CREATE FUNCTION makeNumSeq(INT) RETURNS void AS '
DECLARE i INT:=1;
BEGIN  
  DELETE FROM numSequence;
  WHILE i<=$1 LOOP
    INSERT INTO numSequence (n) VALUES (i);
    i:=i+1;
  END LOOP;
END;
' LANGUAGE plpgsql;





SELECT makeNumSeq(500);
 







CREATE OR REPLACE PROCEDURE makeNumSeq(maxNum INT) IS
BEGIN
  DECLARE i INT := 1;
  BEGIN
    DELETE FROM numSequence;
    WHILE i<=maxNum LOOP
      INSERT INTO numSequence (n) VALUES (i);
      i:=i+1;
    END LOOP;
  END;
END;
/



CALL makeNumSeq(500);
 
DROP PROCEDURE makeNumSeq@






CREATE PROCEDURE makeNumSeq(maxNum INT)
BEGIN
  DECLARE
    i INT DEFAULT 1;
  DELETE FROM numSequence;
  WHILE i<=maxNum DO
    INSERT INTO numSequence (n) VALUES (i);
    SET i=i+1;
  END WHILE;
END@





CALL makeNumSeq(500)@
 
IF EXISTS (SELECT * FROM dbo.sysobjects
  WHERE id = OBJECT_ID(N'dbo.makeNumSeq') AND
    OBJECTPROPERTY(id, N'IsProcedure') = 1)
  DROP PROCEDURE makeNumSeq
GO


CREATE PROCEDURE makeNumSeq(@maxNum INT) AS
BEGIN
  DECLARE @i INT
  SET @i=1
  DELETE FROM numSequence
  WHILE @i<=@maxNum
  BEGIN
    BEGIN TRANSACTION
    INSERT INTO numSequence (n) VALUES (@i)
    COMMIT
    SET @i=@i+1
  END
END
GO

EXECUTE makeNumSeq 500
GO
別の方法
TRUNCATE TABLE nodes;

INSERT INTO nodes (id,name)
  SELECT id,'' AS name
  FROM GENERATE_SERIES (1,500,1) x (id);
 別の方法
TRUNCATE TABLE nodes;

INSERT INTO nodes (id,name)
WITH x
AS (
  SELECT level AS id FROM DUAL
  CONNECT BY level<=500
)
SELECT id,'' AS name FROM x;
 別の方法
DELETE FROM nodes;

INSERT INTO nodes (id,name)
WITH x (id) AS (
  SELECT 1 FROM SYSIBM.SYSDUMMY1
  UNION ALL
  SELECT id+1 FROM x WHERE id<500)
SELECT id,'' AS name FROM x;

8.8.2 最短経路長

テーブル:paths

共通 
CREATE TABLE paths(
  startNode INT NOT NULL,
  endNode INT NOT NULL,
  length INT NOT NULL,
  CONSTRAINT paths_pri PRIMARY KEY (startNode,endNode)
);
CREATE INDEX s_idx ON paths (startNode);
CREATE INDEX e_idx ON paths (endNode);
CREATE INDEX l_idx ON paths (length);

プロシジャ:shortestPath

MySQL PostgreSQL Oracle DB2（ステートメント終了文字を「@」にしています） SQL Server 
DROP PROCEDURE IF EXISTS shortestPath;





DELIMITER //
CREATE PROCEDURE shortestPath()
BEGIN
  DECLARE maxLength INT DEFAULT 1;
  DECLARE newSize,oldSize INT DEFAULT 0;
  
  INSERT INTO paths SELECT head AS startNode,tail AS endNode,1 FROM edges;
  
  REPEAT
    INSERT IGNORE INTO paths -- pathsのendNodeから1歩進む
      SELECT DISTINCT p.startNode AS startNode,tail AS endNode,maxLength+1 AS length
      FROM paths p
      JOIN edges ON p.endNode=head
      WHERE p.length=maxLength
        AND p.startNode!=tail;
    
    SET maxLength=maxLength+1;
    SET oldSize=newSize;
    SELECT COUNT(*) INTO newSize FROM paths;
  UNTIL oldSize=newSize -- テーブルpathsが変わらなくなるまで繰り返す
  END REPEAT;
END//
DELIMITER ;









TRUNCATE TABLE paths;


CALL shortestPath();
 
DROP FUNCTION shortestPath();






CREATE FUNCTION shortestPath() RETURNS void AS '
DECLARE
  maxLength INT:=1;
  oldSize INT;
  newSize INT:=0;
BEGIN
  INSERT INTO paths SELECT head AS startNode,tail AS endNode,1 FROM edges;
  
  LOOP
    INSERT INTO paths
      SELECT DISTINCT p.startNode AS startNode,tail AS endNode,maxLength+1 AS length
      FROM paths p
      JOIN edges ON p.endNode=head
      WHERE p.length=maxLength
        AND p.startNode!=tail
        AND NOT EXISTS (
          SELECT * FROM paths q
          WHERE q.startNode=p.startNode AND q.endNode=tail);
    maxLength:=maxLength+1;
    oldSize:=newSize;
    SELECT COUNT(*) INTO newSize FROM paths;
    IF oldSize=newSize THEN
      EXIT;
    END IF;
  END LOOP;
END;
' LANGUAGE plpgsql;




TRUNCATE TABLE paths; -- こうした方が速い


SELECT shortestPath();
 







CREATE OR REPLACE PROCEDURE shortestPath IS
BEGIN
  DECLARE
    maxLength INT:=1;
    oldSize INT;
    newSize INT:=0;
  BEGIN
    INSERT INTO paths SELECT head AS startNode,tail AS endNode,1 FROM edges;
    
    LOOP
      INSERT INTO paths
        SELECT DISTINCT p.startNode AS startNode,tail AS endNode,maxLength+1 AS length
        FROM paths p
        JOIN edges ON p.endNode=head
        WHERE p.length=maxLength
          AND p.startNode!=tail
          AND NOT EXISTS (
            SELECT * FROM paths q
            WHERE q.startNode=p.startNode AND q.endNode=tail);
      maxLength:=maxLength+1;
      oldSize:=newSize;
      SELECT COUNT(*) INTO newSize FROM paths;
      EXIT WHEN oldSize=newSize;
    END LOOP;
  END;
END;
/




TRUNCATE TABLE paths; -- こうした方が速い


CALL shortestPath();
 
DROP PROCEDURE shortestPath@






CREATE PROCEDURE shortestPath()
BEGIN
  DECLARE maxLength INT DEFAULT 1;
  DECLARE oldSize INT;
  DECLARE newSize INT DEFAULT 0;
  
  INSERT INTO paths SELECT head AS startNode,tail AS endNode,1 FROM edges;
  
  REPEAT
    INSERT INTO paths
      SELECT DISTINCT p.startNode AS startNode,tail AS endNode,maxLength+1 AS length
      FROM paths p
      JOIN edges ON p.endNode=head
      WHERE p.length=maxLength
        AND p.startNode!=tail
        AND NOT EXISTS (
          SELECT * FROM paths q
          WHERE q.startNode=p.startNode AND q.endNode=tail);
    COMMIT;
    SET maxLength=maxLength+1;
    SET oldSize=newSize;
    SET newSize=(SELECT COUNT(*) FROM paths);
  UNTIL oldSize=newSize
  END REPEAT;
END@






DELETE FROM paths@


CALL shortestPath()@
 
IF EXISTS (
  SELECT * FROM dbo.sysobjects WHERE id = OBJECT_ID(N'dbo.shortestPath')
    AND OBJECTPROPERTY(id, N'IsProcedure') = 1)
DROP PROCEDURE shortestPath
GO


CREATE PROCEDURE shortestPath AS
BEGIN
  DECLARE
    @maxLength INT,
    @oldSize INT,
    @newSize INT
  SET @maxLength=1
  SET @oldSize=0
  SET @newSize=1
  
  INSERT INTO paths SELECT head AS startNode,tail AS endNode,1 FROM edges
  
  WHILE @oldSize!=@newSize
  BEGIN
    INSERT INTO paths
      SELECT DISTINCT p.startNode AS startNode,tail AS endNode,@maxLength+1 AS length
      FROM paths p
      JOIN edges ON p.endNode=head
      WHERE p.length=@maxLength
        AND p.startNode!=tail
        AND NOT EXISTS (
          SELECT * FROM paths q
          WHERE q.startNode=p.startNode AND q.endNode=tail)
    
    SET @maxLength=@maxLength+1
    SET @oldSize=@newSize
    SET @newSize=(SELECT COUNT(*) FROM paths)
  END
END
GO

TRUNCATE TABLE paths -- こうした方が速い
GO

EXECUTE shortestPath

結果の確認

共通 
SELECT MAX(length) FROM paths;

グラフが大きいときは、次のSQL文を実行しないでください。

共通 
SELECT * FROM paths ORDER BY startNode,endNode;