Skip to content

Instantly share code, notes, and snippets.

@Phally

Phally/DAG_MySQL.sql

Forked from xib/DAG_MySQL.sql
Last active August 29, 2015 14:25
Download ZIP

Revisions

  1. @xib xib created this gist Dec 23, 2014.
    257 changes: 257 additions & 0 deletions DAG_MySQL.sql
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,257 @@
    -- 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