關(guān)系數(shù)據(jù)庫(kù)中樹(shù)形結(jié)構(gòu)的矩陣算法研究

楊國(guó)清

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

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

中圖分類(lèi)號(hào)：TP311.52;TP311.138 ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A ? ? 文章編號(hào)：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ù)庫(kù)設(shè)計(jì)活動(dòng)中，概念模型是面向用戶、面向現(xiàn)實(shí)世界、與數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS：DataBaseManagement System）無(wú)關(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)也就是樹(shù)形結(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àn)的層次結(jié)構(gòu)有單位組織架構(gòu)、磁盤(pán)目錄與文件結(jié)構(gòu)、家譜、論文標(biāo)題與正文結(jié)構(gòu)等[1]。

關(guān)系結(jié)構(gòu)以二維表的形式留存數(shù)據(jù)，是管理信息系統(tǒng)中最常用的數(shù)據(jù)邏輯形式。在數(shù)據(jù)庫(kù)應(yīng)用中，存在這樣的特殊情況：主體數(shù)據(jù)形態(tài)采用關(guān)系結(jié)構(gòu)，但局部存在使用樹(shù)形結(jié)構(gòu)描述的數(shù)據(jù)。例如：學(xué)生論文寫(xiě)作系統(tǒng)中，學(xué)生、老師等多數(shù)實(shí)體數(shù)據(jù)是基于關(guān)系結(jié)構(gòu)的，而學(xué)生論文中的標(biāo)題與正文內(nèi)容是基于樹(shù)形結(jié)構(gòu)的。解決這種特殊應(yīng)用問(wèn)題，成為論文寫(xiě)作系統(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)系。由于樹(shù)形結(jié)構(gòu)的遍歷算法無(wú)法用單純的SQL （Structured Query Language）實(shí)現(xiàn)，所以往往需要以C++、Java等高級(jí)語(yǔ)言的結(jié)構(gòu)體或類(lèi)為載體，編寫(xiě)客戶端程序，運(yùn)用遞歸思想，實(shí)現(xiàn)樹(shù)形結(jié)構(gòu)的遍歷、插入、刪除等算法。該方式無(wú)法在模型-視圖-控制（MVC：Model View Controller）軟件開(kāi)發(fā)模式中，將數(shù)據(jù)業(yè)務(wù)邏輯與前臺(tái)用戶界面完全分離開(kāi)來(lái)，前端程序需要過(guò)多地參與數(shù)據(jù)層活動(dòng)，不利于軟件團(tuán)隊(duì)的分層開(kāi)發(fā)，導(dǎo)致開(kāi)發(fā)效率較低。另外，需要建立結(jié)點(diǎn)內(nèi)容與結(jié)點(diǎn)位置的聯(lián)結(jié)，即建立單獨(dú)的結(jié)點(diǎn)關(guān)系表，實(shí)現(xiàn)起來(lái)較為困難。與此同時(shí)，當(dāng)結(jié)點(diǎn)位置有變化時(shí)，需要重新調(diào)整結(jié)點(diǎn)關(guān)系表，必然會(huì)消耗較多的系統(tǒng)資源。

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

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

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

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

1.2 樹(shù)的矩陣化

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

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

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

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

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

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

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

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

2.2 遍歷算法

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

2.3 插入算法

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

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

3 結(jié)束語(yǔ)

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

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

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

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

[3] 張鳳林，皮德常，丁宗紅.關(guān)系數(shù)據(jù)庫(kù)實(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] 梁敬彬.探討動(dòng)態(tài)SQL擴(kuò)展的應(yīng)用[J].福建電腦，2018.3：92-94

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