Skip to content

Instantly share code, notes, and snippets.

@xib
Created December 23, 2014 08:17
Show Gist options
  • Save xib/21786eeaa970911f0693 to your computer and use it in GitHub Desktop.
Save xib/21786eeaa970911f0693 to your computer and use it in GitHub Desktop.
Direct Acyclic Directed Graph in MySQL database
-- 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
@binjamil
Copy link

In step 3 of Add Edge procedure, to get the correct hops in resulting edges it should be A.hops + B.hops + 2

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment