Direct Acyclic Directed Graph in MySQL database

DAG_MySQL.sql

-- Based on the original articel at http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o
-- Here is a port to MySQL

-- Edge table
DROP TABLE IF EXISTS `Edge`;
CREATE TABLE IF NOT EXISTS `Edge` (
  `id` int(11) NOT NULL,
  `entry_edge_id` int(11) DEFAULT NULL COMMENT 'The ID of the incoming edge to the start vertex that is the creation reason for this implied edge; direct edges contain the same value as the Id column',
  `direct_edge_id` int(11) DEFAULT NULL COMMENT 'The ID of the direct edge that caused the creation of this implied edge; direct edges contain the same value as the Id column',
  `exit_edge_id` int(11) DEFAULT NULL COMMENT 'The ID of the outgoing edge from the end vertex that is the creation reason for this implied edge; direct edges contain the same value as the Id column',
  `start_vertex` varchar(50) NOT NULL COMMENT 'The ID of the start vertex',
  `end_vertex` varchar(50) NOT NULL COMMENT 'The ID of the end vertex',
  `hops` int(11) NOT NULL COMMENT 'Indicates how many vertex hops are necessary for the path; it is zero for direct edges',
  `source` varchar(50) NOT NULL COMMENT 'A column to indicate the context in which the graph is created; useful if we have more than one DAG to be represented within the same application  CAUTION: you need to make sure that the IDs of vertices from different sources never clash; the best is probably use of UUIDs'
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='DAG Edge table (http://goo.gl/awkHtB)';

ALTER TABLE `Edge`
 ADD PRIMARY KEY (`id`);

ALTER TABLE `Edge`
MODIFY `id` int(11) NOT NULL AUTO_INCREMENT;



-- Procedure add_edge()
DROP PROCEDURE IF EXISTS `add_edge`;
DELIMITER $$
CREATE PROCEDURE `add_edge`(`param_start_vertex_id` VARCHAR(50), `param_end_vertex_id` VARCHAR(50), `param_source` VARCHAR(50))
proc_label:BEGIN
    DECLARE r INT;
    DECLARE NewId INT;
    
    IF EXISTS(
        SELECT id 
        FROM Edge 
          WHERE start_vertex = param_start_vertex_id
            AND end_vertex = param_end_vertex_id
            AND hops = 0
            AND source = param_source) 
    THEN
        LEAVE proc_label;
    END IF;
    
    
    IF param_start_vertex_id = param_end_vertex_id 
    OR EXISTS (SELECT Id 
                   FROM Edge 
                   WHERE start_vertex = param_end_vertex_id 
                     AND end_vertex = param_start_vertex_id
                     AND source = param_source)
    THEN
        LEAVE proc_label;
    END IF;
    
    
    INSERT INTO Edge (
        start_vertex,
        end_vertex,
        hops,
        source)
    VALUES (
        param_start_vertex_id,
        param_end_vertex_id,
        0,
        param_source);

    SELECT LAST_INSERT_ID() INTO NewId;
    
    UPDATE Edge
      SET entry_edge_id = NewId
        , exit_edge_id = NewId
        , direct_edge_id = NewId 
      WHERE Id = NewId;


    -- step 1: A's incoming edges to B
    INSERT INTO Edge (
         entry_edge_id,
         direct_edge_id,
         exit_edge_id,
         start_vertex,
         end_vertex,
         hops,
         source) 
      SELECT Id
         , NewId
         , NewId
         , start_vertex 
         , param_end_vertex_id
         , hops + 1
         , param_source
      FROM Edge
      WHERE end_vertex = param_start_vertex_id
        AND source = param_source;

    -- step 2: A to B's outgoing edges
   INSERT INTO Edge (
         entry_edge_id,
         direct_edge_id,
         exit_edge_id,
         start_vertex,
         end_vertex,
         hops,
         source) 
      SELECT NewId
         , NewId
         , Id
         , param_start_vertex_id 
         , end_vertex
         , hops + 1
         , param_source
      FROM Edge
      WHERE start_vertex = param_end_vertex_id
        AND source = param_source;

    -- step 3: A’s incoming edges to end vertex of B's outgoing edges
    INSERT INTO Edge (
         entry_edge_id,
         direct_edge_id,
         exit_edge_id,
         start_vertex,
         end_vertex,
         hops,
         source)
      SELECT A.Id
         , NewId
         , B.Id
         , A.start_vertex 
         , B.end_vertex
         , A.hops + B.hops + 1
         , param_source
      FROM Edge AS A
         CROSS JOIN Edge AS B
      WHERE A.end_vertex = param_start_vertex_id
        AND B.start_vertex = param_end_vertex_id
        AND A.source = param_source
        AND B.source = param_source;
END$$
DELIMITER ;



-- Procedure remove_edge_id ~ remove by edge_id

DROP PROCEDURE IF EXISTS `remove_edge_id`;
DELIMITER $$
CREATE PROCEDURE `remove_edge_id`(`param_id` INT)
proc_label:BEGIN
    DECLARE RowCount INT;

    IF NOT EXISTS (SELECT Id from Edge WHERE Id = param_id) THEN
        LEAVE proc_label;
    END IF;
    
    CREATE TABLE TempPurgeList (Id int);
    
    -- step 1: rows that were originally inserted with the first
    -- AddEdge call for this direct edge
    INSERT INTO TempPurgeList
        SELECT Id
          FROM Edge
          WHERE direct_edge_id = param_id;

    -- step 2: scan and find all dependent rows that are inserted afterwards
    label1: LOOP
        INSERT INTO TempPurgeList
            SELECT Id    
                FROM Edge
                WHERE (hops > 0)
                  AND ( entry_edge_id IN ( SELECT Id FROM TempPurgeList ) 
                        OR exit_edge_id IN ( SELECT Id FROM TempPurgeList ) )
                  AND (Id NOT IN (SELECT Id FROM TempPurgeList ));

        IF ROW_COUNT() = 0 THEN
            LEAVE label1;
        END IF;
    END LOOP label1;

    DELETE FROM Edge
       WHERE Id IN ( SELECT Id FROM TempPurgeList);

    DROP TABLE TempPurgeList;
END$$
DELIMITER ;



-- Procedure remove_edge

DROP PROCEDURE IF EXISTS `remove_edge`;
DELIMITER $$
CREATE PROCEDURE `remove_edge`(`param_start_vertex_id` VARCHAR(50), `param_end_vertex_id` VARCHAR(50), `param_source` VARCHAR(50))
BEGIN
    DECLARE ParamId INT;

    DECLARE CONTINUE HANDLER FOR NOT FOUND BEGIN END;

    SELECT Id INTO ParamId
        FROM Edge 
        WHERE start_vertex = param_start_vertex_id
          AND end_vertex = param_end_vertex_id
          AND hops = 0
          AND source = param_source;

    IF ParamId IS NOT NULL THEN
        CALL remove_edge_id(ParamId);
    END IF;
END$$
DELIMITER ;




-- Test

TRUNCATE TABLE `Edge`;
CALL add_edge('HelpDesk', 'Admins', 'AD');
CALL add_edge('Ali', 'Admins', 'AD');
CALL add_edge('Ali', 'Users', 'AD');
CALL add_edge('Burcu', 'Users', 'AD');
CALL add_edge('Can', 'Users', 'AD');
CALL add_edge('Managers', 'Users','AD');
CALL add_edge('Technicians', 'Users', 'AD');
CALL add_edge('Demet', 'HelpDesk', 'AD');
CALL add_edge('Engin', 'HelpDesk', 'AD');
CALL add_edge('Engin', 'Users', 'AD');
CALL add_edge('Fuat', 'Managers', 'AD');
CALL add_edge('G l', 'Managers', 'AD');
CALL add_edge('Hakan', 'Technicians', 'AD');
CALL add_edge('Irmak', 'Technicians', 'AD');
CALL add_edge('ABCTechnicians', 'Technicians', 'AD');
CALL add_edge('Jale', 'ABCTechnicians', 'AD');



SELECT start_vertex, hops 
    FROM Edge 
    WHERE end_vertex = 'Admins';

-- => return:
-- start_vertex, hops
-- HelpDesk, 0
-- Ali, 0
-- Demet, 1
-- Engin, 1



SELECT end_vertex, hops 
    FROM Edge 
    WHERE start_vertex = 'Jale';

-- => return:
-- end_vertex, hops
-- ABCTechnicians, 0
-- Technicians, 1
-- Users, 2