我有我在以下表中存储的树数据结构:
#stores the actual node data
CREATE TABLE nodes(
nodeId MEDIUMINT NOT NULL AUTO_INCREMENT,
nodeType VARCHAR(10) NOT NULL, #'leaf', 'parallel' or 'sequential'
nodeValue MEDIUMINT NOT NULL DEFAULT 0,
PRIMARY KEY (nodeId)
);
#stores the parent/child relationships
CREATE TABLE parents(
nodeId MEDIUMINT NOT NULL,
parentId MEDIUMINT NULL, # null if it is the root node
PRIMARY KEY (nodeId),
INDEX (parentId),
FOREIGN KEY (nodeId) REFERENCES nodes(nodeId),
FOREIGN KEY (parentId) REFERENCES nodes(nodeId)
);
树中的节点可以是三种类型,'leaf'
节点是树的叶子节点,用户可以随时在其上设置任意值,'parallel'
和'sequential'
节点只能是分支节点,'parallel'
节点的值必须始终始终等于其直系子节点的max(value)
,'sequential'
节点的值必须始终等于其直接子节点的sum(value)
。用户还可以将分支节点从'sequential'
切换到'parallel'
,反之亦然。所有这些动作都必须将其更改级联回到树上,以使数据始终保持一致。我有一些存储的程序可以执行此操作(以下),但我担心无法确保正确进行更改。
DROP PROCEDURE IF EXISTS setLeafNodeValue;
DELIMITER $$
CREATE PROCEDURE setLeafNodeValue(id MEDIUMINT, val MEDIUMINT)
proc:BEGIN
# assume validation checks to ensure it exists and is a leaf node have already been done
DECLARE currentNodeId MEDIUMINT DEFAULT id;
DECLARE currentNodesNewValue MEDIUMINT DEFAULT 0;
DECLARE currentNodesOldValue MEDIUMINT DEFAULT 0;
DECLARE currentNodeType VARCHAR(10) DEFAULT NULL;
DECLARE prevNodesOldValue MEDIUMINT DEFAULT 0;
DECLARE prevNodesNewValue MEDIUMINT DEFAULT 0;
START TRANSACTION;
WHILE currentNodeId IS NOT NULL DO
SELECT nodeType, nodeValue INTO currentNodeType, currentNodesOldValue FROM nodes WHERE nodeId = currentNodeId;
CASE currentNodeType
WHEN 'leaf' THEN
SET currentNodesNewValue = val;
WHEN 'parallel' THEN
SET currentNodesNewValue = (SELECT MAX(n.nodeValue) FROM nodes n JOIN parents p ON n.nodeId = p.nodeId WHERE p.parentId = currentNodeId);
WHEN 'sequential' THEN
SET currentNodesNewValue = currentNodesOldValue + (prevNodesNewValue - prevNodesOldValue);
END CASE;
IF currentNodesNewValue = currentNodesOldValue THEN
COMMIT;
LEAVE proc; #no change is being made
END IF;
UPDATE nodes SET nodeValue = currentNodesNewValue WHERE nodeId = currentNodeId;
SET prevNodesOldValue = currentNodesOldValue;
SET prevNodesNewValue = currentNodesNewValue;
SELECT parentId INTO currentNodeId FROM parents WHERE nodeId = currentNodeId;
END WHILE;
COMMIT;
END$$
DELIMITER ;
DROP PROCEDURE IF EXISTS setBranchNodeType;
DELIMITER $$
CREATE PROCEDURE setBranchNodeType(id MEDIUMINT, newNodeType VARCHAR(10))
proc:BEGIN
# assume validation checks to ensure it exists and is a branch node have already been done
# and that newNodeType is either 'parallel' or 'sequential'
DECLARE currentNodeId MEDIUMINT DEFAULT id;
DECLARE currentNodesNewValue MEDIUMINT DEFAULT 0;
DECLARE currentNodesOldValue MEDIUMINT DEFAULT 0;
DECLARE currentNodeType VARCHAR(10) DEFAULT NULL;
DECLARE prevNodesOldValue MEDIUMINT DEFAULT 0;
DECLARE prevNodesNewValue MEDIUMINT DEFAULT 0;
SELECT nodeType, nodeValue INTO currentNodeType, currentNodesOldValue FROM nodes WHERE nodeId = currentNodeId;
IF currentNodeType = newNodeType THEN
LEAVE proc;
END IF;
START TRANSACTION;
CASE newNodeType
WHEN 'parallel' THEN
SET currentNodesNewValue = (SELECT MAX(n.nodeValue) FROM nodes n JOIN parents p ON n.nodeId = p.nodeId WHERE p.parentId = currentNodeId);
WHEN 'sequential' THEN
SET currentNodesNewValue = (SELECT SUM(n.nodeValue) FROM nodes n JOIN parents p ON n.nodeId = p.nodeId WHERE p.parentId = currentNodeId);
END CASE;
UPDATE nodes SET nodeType = newNodeType, nodeValue = currentNodesNewValue WHERE nodeId = currentNodeId;
IF currentNodesNewValue = currentNodesOldValue THEN
COMMIT;
LEAVE proc;
END IF;
SET prevNodesOldValue = currentNodesOldValue;
SET prevNodesNewValue = currentNodesNewValue;
SELECT parentId INTO currentNodeId FROM parents WHERE nodeId = currentNodeId;
WHILE currentNodeId IS NOT NULL DO
SELECT nodeType, nodeValue INTO currentNodeType, currentNodesOldValue FROM nodes WHERE nodeId = currentNodeId;
CASE currentNodeType
WHEN 'parallel' THEN
SET currentNodesNewValue = (SELECT MAX(n.nodeValue) FROM nodes n JOIN parents p ON n.nodeId = p.nodeId WHERE p.parentId = currentNodeId);
WHEN 'sequential' THEN
SET currentNodesNewValue = currentNodesOldValue + (prevNodesNewValue - prevNodesOldValue);
END CASE;
IF currentNodesNewValue = currentNodesOldValue THEN
COMMIT;
LEAVE proc;
END IF;
UPDATE nodes SET nodeValue = currentNodesNewValue WHERE nodeId = currentNodeId;
SET prevNodesOldValue = currentNodesOldValue;
SET prevNodesNewValue = currentNodesNewValue;
SELECT parentId INTO currentNodeId FROM parents WHERE nodeId = currentNodeId;
END WHILE;
COMMIT;
END$$
DELIMITER ;
我存储过程的交易中默认行锁定是否会保证,如果两个单独的更改会导致同一节点同时更新(例如,每一个更改都会通过每个更改来更新树的根节点)更改将在计算和应用以下更改之前应用,或者我需要在所有节点行上明确设置锁定锁定的锁,该行构成要更改的父谱系,然后对这些行进行更改?
?示例:
(p) - 平行,(s) - 序列具有节点值的树:
(p)4
|
|__(s)3
| |
| |__1
| |
| |__2
|
|__(p)4
|
|__3
|
|__4
#this test data can be seeded with
INSERT INTO nodes (nodeType, nodeValue) VALUES ('parallel', 4), ('sequential', 3), ('parallel', 4), ('leaf', 1), ('leaf', 2), ('leaf', 3), ('leaf', 4);
INSERT INTO parents (nodeId, parentId) VALUES (1, null), (2, 1), (3, 1), (4, 2), (5, 2), (6, 3), (7, 3);
如果一个用户将1
值更改为3
,另一个用户将其父级(s)3
设置为parallel
,则最终结果应为:
(p)4
|
|__(p)3
| |
| |__3
| |
| |__2
|
|__(p)4
|
|__3
|
|__4
但是,如果不保证将更改应用于节点行,则如果在某些中间状态中计算出值(p)5
,则可能会导致root节点。首先处理哪种更改并不重要,只是以确保它们不会重叠和干扰的方式处理它们。
阅读文档,我认为答案是我需要使用其他锁来确保行为正确。我相信我需要:
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
SET autocommit=0;
在我的START TRANSACTION;
语句之前,以锁定在给定更改中更新节点的谱系,并防止这些存储的Procs的其他并发执行相互冲突。这样,所有SELECT
语句都会被隐式转换为SELECT ... LOCK IN SHARE MODE
,他们将等到任何现有的重叠谱系操作已完全完成为止。但是,这不应阻止其他简单的读取在更新进行时读取节点。
所以setLeafNodeValue
SP看起来像:
DROP PROCEDURE IF EXISTS setLeafNodeValue;
DELIMITER $$
CREATE PROCEDURE setLeafNodeValue(id MEDIUMINT, val MEDIUMINT)
proc:BEGIN
# assume validation checks to ensure it exists and is a leaf node have already been done
DECLARE currentNodeId MEDIUMINT DEFAULT id;
DECLARE currentNodesNewValue MEDIUMINT DEFAULT 0;
DECLARE currentNodesOldValue MEDIUMINT DEFAULT 0;
DECLARE currentNodeType VARCHAR(10) DEFAULT NULL;
DECLARE prevNodesOldValue MEDIUMINT DEFAULT 0;
DECLARE prevNodesNewValue MEDIUMINT DEFAULT 0;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
SET autocommit=0;
START TRANSACTION;
WHILE currentNodeId IS NOT NULL DO
SELECT nodeType, nodeValue INTO currentNodeType, currentNodesOldValue FROM nodes WHERE nodeId = currentNodeId;
CASE currentNodeType
WHEN 'leaf' THEN
SET currentNodesNewValue = val;
WHEN 'parallel' THEN
SET currentNodesNewValue = (SELECT MAX(n.nodeValue) FROM nodes n JOIN parents p ON n.nodeId = p.nodeId WHERE p.parentId = currentNodeId);
WHEN 'sequential' THEN
SET currentNodesNewValue = currentNodesOldValue + (prevNodesNewValue - prevNodesOldValue);
END CASE;
IF currentNodesNewValue = currentNodesOldValue THEN
COMMIT;
SET autocommit=1;
LEAVE proc; #no change is being made
END IF;
UPDATE nodes SET nodeValue = currentNodesNewValue WHERE nodeId = currentNodeId;
SET prevNodesOldValue = currentNodesOldValue;
SET prevNodesNewValue = currentNodesNewValue;
SELECT parentId INTO currentNodeId FROM parents WHERE nodeId = currentNodeId;
END WHILE;
COMMIT;
SET autocommit=1;
END$$
DELIMITER ;