楊國清

摘 ?要： 關(guān)系結(jié)構(gòu)是最常用的數(shù)據(jù)邏輯形式。在關(guān)系數(shù)據(jù)庫中，存在局部的樹形結(jié)構(gòu)數(shù)據(jù)形態(tài)。針對關(guān)系數(shù)據(jù)庫中的樹形結(jié)構(gòu)數(shù)據(jù)，提出一種基于矩陣模型的數(shù)據(jù)組織方法，直接使用SQL查詢，在數(shù)據(jù)庫內(nèi)部實(shí)現(xiàn)樹形結(jié)構(gòu)的插入、遍歷、刪除、移動等算法。

關(guān)鍵詞： 關(guān)系數(shù)據(jù)庫; 算法; 樹形結(jié)構(gòu); SQL

中圖分類號：TP311.52;TP311.138 ? ? ? ? ?文獻(xiàn)標(biāo)識碼：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 引言

數(shù)據(jù)庫設(shè)計(jì)活動中，概念模型是面向用戶、面向現(xiàn)實(shí)世界、與數(shù)據(jù)庫管理系統(tǒng)（DBMS：DataBaseManagement System）無關(guān)的數(shù)據(jù)模型。邏輯模型是概念模型在具體DBMS中的數(shù)據(jù)組織形式。邏輯模型有四種形態(tài)：層次結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)、關(guān)系結(jié)構(gòu)、面向?qū)ο蠼Y(jié)構(gòu)。層次結(jié)構(gòu)也就是樹形結(jié)構(gòu)，由一個(gè)根結(jié)點(diǎn)和多個(gè)雙親結(jié)點(diǎn)、孩子結(jié)點(diǎn)、葉子結(jié)點(diǎn)、非葉子結(jié)點(diǎn)等數(shù)據(jù)形態(tài)構(gòu)成?，F(xiàn)實(shí)世界里常見的層次結(jié)構(gòu)有單位組織架構(gòu)、磁盤目錄與文件結(jié)構(gòu)、家譜、論文標(biāo)題與正文結(jié)構(gòu)等[1]。

關(guān)系結(jié)構(gòu)以二維表的形式留存數(shù)據(jù)，是管理信息系統(tǒng)中最常用的數(shù)據(jù)邏輯形式。在數(shù)據(jù)庫應(yīng)用中，存在這樣的特殊情況：主體數(shù)據(jù)形態(tài)采用關(guān)系結(jié)構(gòu)，但局部存在使用樹形結(jié)構(gòu)描述的數(shù)據(jù)。例如：學(xué)生論文寫作系統(tǒng)中，學(xué)生、老師等多數(shù)實(shí)體數(shù)據(jù)是基于關(guān)系結(jié)構(gòu)的，而學(xué)生論文中的標(biāo)題與正文內(nèi)容是基于樹形結(jié)構(gòu)的。解決這種特殊應(yīng)用問題，成為論文寫作系統(tǒng)項(xiàng)目設(shè)計(jì)與實(shí)現(xiàn)的重點(diǎn)與難點(diǎn)。

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

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

1 樹形結(jié)構(gòu)中數(shù)據(jù)的矩陣化

1.1 數(shù)據(jù)原始形態(tài)

我們以論文寫作系統(tǒng)中，論文的標(biāo)題與正文結(jié)構(gòu)為研究藍(lán)本，描述樹形結(jié)構(gòu)數(shù)據(jù)的矩陣化過程。假設(shè)有一篇論文的簡化結(jié)構(gòu)如圖1所示。從圖1中可以看出，樹中“論文”為根結(jié)點(diǎn)，所有“正文”均為葉子結(jié)點(diǎn)，其他為中間結(jié)點(diǎn)。該樹的度為3，深度為5[2]。

1.2 樹的矩陣化

樹形結(jié)構(gòu)矩陣化的具體轉(zhuǎn)換規(guī)則有三條：

⑴ 根結(jié)點(diǎn)編號為0;

⑵ 將某結(jié)點(diǎn)的孩子按從上到下編號，從1開始，依次加1;

⑶ 每個(gè)結(jié)點(diǎn)獨(dú)占矩陣中的一行。該結(jié)點(diǎn)所處的深度特征值為其編號，前面的深度特征值繼承長輩的編號、后面深度特征值指定為0。

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

2 常用算法實(shí)現(xiàn)

2.1 當(dāng)前結(jié)點(diǎn)深度獲取

用于獲取當(dāng)前結(jié)點(diǎn)的深度。在存儲過程中使用動態(tài)SQL語句，可以方便獲取結(jié)點(diǎn)深度。存儲過程的頭部為NodeDepth @RowIDbigint。具體實(shí)現(xiàn)代碼如下：

2.2 遍歷算法

用矩陣法處理過的樹形結(jié)構(gòu)數(shù)據(jù)，其遍歷算法實(shí)現(xiàn)起來比較容易，直接用帶有排序子句的SQL查詢語句即可，代碼如下：

2.3 插入算法

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

上述算法插入的是當(dāng)前結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，如果需要插入孩子結(jié)點(diǎn)，只需要作適當(dāng)調(diào)整。另外，結(jié)點(diǎn)的刪除、移動與插入算法相類似，本文不再贅述[6]。

3 結(jié)束語

針對關(guān)系數(shù)據(jù)庫中的樹形結(jié)構(gòu)，按照矩陣化轉(zhuǎn)換規(guī)則，將樹形數(shù)據(jù)變?yōu)殛P(guān)系表。通過結(jié)點(diǎn)的特征值，可以方便地實(shí)現(xiàn)結(jié)點(diǎn)定位、遍歷、插入等算法。該模型可以在數(shù)據(jù)庫內(nèi)部直接使用SQL實(shí)施，不需要借助高級語言在客戶程序中實(shí)現(xiàn)，較好地達(dá)到了MVC設(shè)計(jì)模式中分層開發(fā)的目標(biāo)。

參考文獻(xiàn)（References）：

[1] 尹志宇，郭晴.數(shù)據(jù)庫原理與應(yīng)用教程（第2版）[M].清華大學(xué)出版社，2017.

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

[3] 張鳳林，皮德常，丁宗紅.關(guān)系數(shù)據(jù)庫實(shí)現(xiàn)U/C矩陣的方法[J].微計(jì)算機(jī)應(yīng)用，2000.4：214

[4] 周琴.矩陣特征值和特征向量在實(shí)際中的應(yīng)用及其實(shí)現(xiàn)[J].高師理科學(xué)刊，2019.7：8-10

[5] 梁敬彬.探討動態(tài)SQL擴(kuò)展的應(yīng)用[J].福建電腦，2018.3：92-94

[6] 王洪蘭.ASP.NET與SQL數(shù)據(jù)庫的連接與查詢方法探索與實(shí)現(xiàn)[J].信息系統(tǒng)工程，2018.10：27-28