關系數據庫中樹形結構的矩陣算法研究

楊國清

摘 ?要： 關系結構是最常用的數據邏輯形式。在關系數據庫中，存在局部的樹形結構數據形態。針對關系數據庫中的樹形結構數據，提出一種基于矩陣模型的數據組織方法，直接使用SQL查詢，在數據庫內部實現樹形結構的插入、遍歷、刪除、移動等算法。

關鍵詞： 關系數據庫; 算法; 樹形結構; SQL

中圖分類號：TP311.52;TP311.138 ? ? ? ? ?文獻標識碼：A ? ? 文章編號：1006-8228（2020）03-50-03

Research on matrix algorithm of tree structure in relational database

Yang Guoqing

（Guangdong Peizheng College School of Data Science and Computer Science， Guangzhou， Guangdong 510830， China）

Abstract： Relational structures are the most commonly used form of data logic. In the relational database， there is a local tree structure data form. A matrix model based data organization method is proposed for the tree structure data in the relational database， and the SQL queries are used directly to implement the interpolation， traversal， deletion， and moving algorithms of the tree structure within the database.

Key words： relational database; algorithm; tree structure; SQL

0 引言

數據庫設計活動中，概念模型是面向用戶、面向現實世界、與數據庫管理系統（DBMS：DataBaseManagement System）無關的數據模型。邏輯模型是概念模型在具體DBMS中的數據組織形式。邏輯模型有四種形態：層次結構、網狀結構、關系結構、面向對象結構。層次結構也就是樹形結構，由一個根結點和多個雙親結點、孩子結點、葉子結點、非葉子結點等數據形態構成。現實世界里常見的層次結構有單位組織架構、磁盤目錄與文件結構、家譜、論文標題與正文結構等[1]。

關系結構以二維表的形式留存數據，是管理信息系統中最常用的數據邏輯形式。在數據庫應用中，存在這樣的特殊情況：主體數據形態采用關系結構，但局部存在使用樹形結構描述的數據。例如：學生論文寫作系統中，學生、老師等多數實體數據是基于關系結構的，而學生論文中的標題與正文內容是基于樹形結構的。解決這種特殊應用問題，成為論文寫作系統項目設計與實現的重點與難點。

目前比較普遍的做法是：使用雙親法或孩子法，單獨建立結點關系表，記載每個結點的雙親或者孩子，以確定結點之間的先后關系。由于樹形結構的遍歷算法無法用單純的SQL （Structured Query Language）實現，所以往往需要以C++、Java等高級語言的結構體或類為載體，編寫客戶端程序，運用遞歸思想，實現樹形結構的遍歷、插入、刪除等算法。該方式無法在模型-視圖-控制（MVC：Model View Controller）軟件開發模式中，將數據業務邏輯與前臺用戶界面完全分離開來，前端程序需要過多地參與數據層活動，不利于軟件團隊的分層開發，導致開發效率較低。另外，需要建立結點內容與結點位置的聯結，即建立單獨的結點關系表，實現起來較為困難。與此同時，當結點位置有變化時，需要重新調整結點關系表，必然會消耗較多的系統資源。

經過研究發現，采用一種全新的基于矩陣的組織形式留存樹形結構數據，可以完美地解決上述問題。該方法只需要在結點數據中添加相關的位置特征值，不需要建立單獨的結點關系表，結點的位置可以直接從自身數據中得到。新方法不用考慮樹的度（結點孩子數的最大值），只需要關注樹的深度（樹的層數）。直接用SQL語句，就可以方便快捷地實現數據遍歷、插入、刪除、移動等算法。與此同時，數據業務處理邏輯可以完全交由數據后臺完成，可以方便快捷地實現MVC所要求的分層處理目標[2]。

1 樹形結構中數據的矩陣化

1.1 數據原始形態

我們以論文寫作系統中，論文的標題與正文結構為研究藍本，描述樹形結構數據的矩陣化過程。假設有一篇論文的簡化結構如圖1所示。從圖1中可以看出，樹中“論文”為根結點，所有“正文”均為葉子結點，其他為中間結點。該樹的度為3，深度為5[2]。

1.2 樹的矩陣化

樹形結構矩陣化的具體轉換規則有三條：

⑴ 根結點編號為0;

⑵ 將某結點的孩子按從上到下編號，從1開始，依次加1;

⑶ 每個結點獨占矩陣中的一行。該結點所處的深度特征值為其編號，前面的深度特征值繼承長輩的編號、后面深度特征值指定為0。

按照以上規則，圖1所示的某論文的樹形結構被處理為一張矩陣表，如表1論文矩陣表所示。Depthi代表深度i的特征值。i為深度索引號，其最大值為樹的深度減1[3-4]。

2 常用算法實現

2.1 當前結點深度獲取

用于獲取當前結點的深度。在存儲過程中使用動態SQL語句，可以方便獲取結點深度。存儲過程的頭部為NodeDepth @RowIDbigint。具體實現代碼如下：

2.2 遍歷算法

用矩陣法處理過的樹形結構數據，其遍歷算法實現起來比較容易，直接用帶有排序子句的SQL查詢語句即可，代碼如下：

2.3 插入算法

在矩陣的某位置插入新行，只需要確定新行不同深度的特征值，不需要修改其他結點的數據。算法思路為：獲取當前結點的位置，在其雙親的所有孩子中，尋找最底層的最大特征值，加1后的新值作為新行的最大深度特征值，同一行前面的特征值來源于其父輩，后面默認為0。使用頭部為addPart @RowIDbigint的存儲過程，結合動態SQL語句技巧，可以快速實現插入算法。具體代碼如下：

上述算法插入的是當前結點的兄弟結點，如果需要插入孩子結點，只需要作適當調整。另外，結點的刪除、移動與插入算法相類似，本文不再贅述[6]。

3 結束語

針對關系數據庫中的樹形結構，按照矩陣化轉換規則，將樹形數據變為關系表。通過結點的特征值，可以方便地實現結點定位、遍歷、插入等算法。該模型可以在數據庫內部直接使用SQL實施，不需要借助高級語言在客戶程序中實現，較好地達到了MVC設計模式中分層開發的目標。

參考文獻（References）：

[1] 尹志宇，郭晴.數據庫原理與應用教程（第2版）[M].清華大學出版社，2017.

[2] 李國勇，王燕霞，熊黎麗等.基于樹形組織結構的數據隔離模型[J].自動化與儀器儀表，2018.11：231-235

[3] 張鳳林，皮德常，丁宗紅.關系數據庫實現U/C矩陣的方法[J].微計算機應用，2000.4：214

[4] 周琴.矩陣特征值和特征向量在實際中的應用及其實現[J].高師理科學刊，2019.7：8-10

[5] 梁敬彬.探討動態SQL擴展的應用[J].福建電腦，2018.3：92-94

[6] 王洪蘭.ASP.NET與SQL數據庫的連接與查詢方法探索與實現[J].信息系統工程，2018.10：27-28