数据库中的树结构应该怎样去设计

翻译自：Trees in SQL by Joe Celko

这个主题是我的旧主题，但是值得重复的再谈一次，我在新闻讨论组中看到过太多关于SQL树和层次结构的问题。SQL书籍中树结构的常见示例称为邻接列表明细，它如下所示：

CREATE TABLE Personnel (
	emp CHAR(10) NOT NULL PRIMARY KEY,
	boss CHAR(10) DEFAULT NULL REFERENCES Personnel (emp),
	salary DECIMAL (6,2) NOT NULL DEFAULT 100.00
);
2021-07-12-uZcAyE

另外一种表示树的方法是将他们显示为嵌套集，因为SQL是一种面向集合的语言，所以该模型比你在大多数教科书上看到的常见的邻接表更好。我们像这样定义一个简单的Personal表，暂时忽略左(lft)和右(rgt)列：

CREATE TABLE Personnel (
	emp CHAR(10) NOT NULL PRIMARY KEY,
	lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
	rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
	CONSTRAINT order_okay CHECK (lft < rgt)
);

这个问题总是在教科书书中为员工提供一列，为他的老板提供一列。这个表(表2)没有lft和rgt列--被称为邻接表模型，以同名的图论技术命名；节点对彼此相邻。

2021-07-12-XrN01g

组织结构图类似于图1的有向图：

2021-07-12-9RHJ29

表1以多种方式进行了非规范化。我们在一张表中对人员和组织结构图进行建模。但是为了节省空间，假设名称是职位，并且我们有另一个表格来描述担任这个职位的人员。

邻接表模型的另外一个问题是，boss列和employee列是同一种类型（人员姓名），因此应该只显示在规范化表中的一列上。为了证明这不是规范化的，假设”Chuck“将他的名字改为”Charles“；你必须在两列和其他的地方更改他的名字。规范化表的定义特征是一次在一个地方有一个事实。

最后一个问题是邻接表模型没有对从属进行建模。权利在等级制度中向下流动，但如果我解雇Chuck，我就会断开他所有的下属和Albert的联系。有时(例如水管)确实如此，但在嵌套集中不会出现这种情况。

要将树显示为嵌套集，请将节点替换为椭圆，然后将下级椭圆相互嵌套。根将是最大的椭圆，将包含所有其他的节点。叶节点将是最里面的椭圆，里面没有任何其他东西，嵌套将显示层次关系。rgt列和lft列（不能在SQL中使用保留关键字LEFT和RIGHT）显示嵌套。

如果不理解这个模型，那么想象一条小虫子沿着树逆时针爬行。每次到达节点的左侧或右侧时，虫子都会对其进行编号，当虫子回到顶部时，它就会停止。

此模型是显示子节点的一种自然方式，因为最终装配是由其分解未单独节点的物理嵌套组成的。

此时，boss列既是多余的，又是非规范化的，因残可以将其删除。另外注意，树型结构可以保存在一张表中，有关节点的所有信息可以放在第二张表中，你可以在员工编号上加入两者以进行查询。

要将图形转换为嵌套集模型，请考虑沿着树爬行的小虫子。虫子从顶部(根部)开始，然后绕着树完整的走一圈，当涉及到一个节点时，它就会在它正在访问的一侧单元格中放置一个数字并增加计数器。每个节点将得到两个数字-一个用于右侧(rgt)，一个用于左侧(lft)。（计算机科学专业的学生会认为这是一种经过修改的预排序树的遍历算法），最后删除不需要的”Personnel.boss“列，它表示图的变。

这有一些可预测的结果，我们可以使他们来构建查询。根的形式总是(lft=1,rgt=2 * (SELECT COUNT(*) FROM TreeTable))，叶子节点总是有(lft+1=rgt)，between谓词定义了子树等等；以下是一些可用于构建其他查询的常见查询：

  1. 找到一个员工的所有主管，无论树有多深。

     SELECT
 	P2.*
 FROM
 	Personnel AS P1,
 	Personnel AS P2
 WHERE
 	P1.lft BETWEEN P2.lft
 	AND P2.rgt
 	AND P1.emp = :myemployee;

  2. 找到该员工及其所有下属（此查询与第一个查询具有很好的对称性）。

    SELECT
	P2.*
FROM
	Personnel AS P1,
	Personnel AS P2
WHERE
	P1.lft BETWEEN P2.lft
	AND P2.rgt
	AND P2.emp = :myemployee;

  3. 将group by和其他的聚合函数添加到这些基本查询中，你就有了分层的报告。例如，每个员工控制的总工资。

    SELECT
	P2.emp,
	SUM(S1.salary)
FROM
	Personnel AS P1,
	Personnel AS P2,
	Salaries AS S1
WHERE
	P1.lft BETWEEN P2.lft
	AND P2.rgt
	AND P1.emp = S1.emp
GROUP BY
	P2.emp;

    在邻接表模型中，你必须使用游标来完成这个功能。

  4. 找到每个节点的级别，以便你可以将树打印为缩进列表。

    SELECT
	COUNT(P2.emp) AS indentation,
	P1.emp
FROM
	Personnel AS P1,
	Personnel AS P2
WHERE
	P1.lft BETWEEN P2.lft
	AND P2.rgt
GROUP BY
	P1.emp
ORDER BY
	P1.lft;

  5. 嵌套集模型具有邻接表模型没有的兄弟姐妹的隐含排序。插入一个新的节点作为最右边节点的兄弟节点。

    BEGIN
DECLARE
	right_most_sibling INTEGER;
	SET right_most_sibling = (
	SELECT
		rgt
	FROM
		Personnel
	WHERE
		emp = :your_boss);
	UPDATE
		Personnel
	SET
		lft = CASE WHEN lft > right_most_sibling THEN
			lft + 2
		ELSE
			lft
		END,
		rgt = CASE WHEN rgt >= right_most_sibling THEN
			rgt + 2
		ELSE
			rgt
		END
	WHERE
		rgt >= right_most_sibling;
	INSERT INTO Personnel (emp, lft, rgt)
		VALUES('New Guy', right_most_sibling, (right_most_sibling + 1))
END;

  6. 要将邻接表模型转换为嵌套集模型，请使用下推堆栈算法。假设我们有这些表：

    树持有邻接表模型。

    CREATE TABLE Tree
(emp CHAR(10) NOT NULL,
boss CHAR(10));

INSERT INTO Tree
SELECT emp, boss FROM Personnel;

-- Stack starts empty, will holds the nested set model
CREATE TABLE Stack
(stack_top INTEGER NOT NULL,
emp CHAR(10) NOT NULL,
lft INTEGER,
rgt INTEGER);

BEGIN
	ATOMIC
DECLARE
	counter INTEGER;
DECLARE
	max_counter INTEGER;
DECLARE
	current_top INTEGER;
	SET counter = 2;
	SET max_counter = 2 * (
	SELECT
		COUNT(*)
		FROM
			Tree);
	SET current_top = 1;
	INSERT INTO Stack
	SELECT
		1,
		emp,
		1,
		NULL
	FROM
		Tree
	WHERE
		boss IS NULL;
	DELETE FROM Tree
	WHERE boss IS NULL;
	WHILE counter <= (max_counter - 2)
	LOOP
		IF EXISTS (
			SELECT
				*
			FROM
				Stack AS S1,
				Tree AS T1
			WHERE
				S1.emp = T1.boss
				AND S1.stack_top = current_top) THEN
BEGIN
	-- push when top has subordinates, set lft value
	INSERT INTO Stack
	SELECT
		(current_top + 1), MIN(T1.emp), counter, NULL
	FROM
		Stack AS S1,
		Tree AS T1
	WHERE
		S1.emp = T1.boss
		AND S1.stack_top = current_top;
	DELETE FROM Tree
	WHERE emp = (
			SELECT
				emp
			FROM
				Stack
			WHERE
				stack_top = current_top + 1);
	SET counter = counter + 1;
	SET current_top = current_top + 1;
END
ELSE
	BEGIN
		-- pop the stack and set rgt value
		UPDATE
			Stack
		SET
			rgt = counter,
			stack_top = - stack_top -- pops the stack
		WHERE
			stack_top = current_top
		SET
			counter = counter + 1;
	SET current_top = current_top - 1;
END IF;
END LOOP;
END;

    尽管此过程有效，但是你可能希望使用一种包含数组的语言，而不是坚持使用SQL。

上一页博客下一页学习&成长

最后更新于

这有帮助吗？