方銀清

(集美大學(xué) 信息工程學(xué)院，福建 廈門 361009)

0 引言

數(shù)據(jù)庫(kù)是現(xiàn)代計(jì)算機(jī)信息處理的核心，特別是大數(shù)據(jù)處理．從上世紀(jì)80年代以來(lái)，關(guān)系數(shù)據(jù)庫(kù)以其安全性、數(shù)據(jù)完整性、良好的數(shù)據(jù)接口得到快速的發(fā)展[1-2]．而樹(shù)型結(jié)構(gòu)是現(xiàn)實(shí)世界中常用的一種非線性的數(shù)據(jù)結(jié)構(gòu)，如家庭族譜、機(jī)器零件、單位組織結(jié)構(gòu)等等．樹(shù)型結(jié)構(gòu)的計(jì)算機(jī)信息處理必須進(jìn)行數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換，把非線性的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為關(guān)系數(shù)據(jù)模型，進(jìn)而把數(shù)據(jù)存入數(shù)據(jù)庫(kù)．而這正是樹(shù)型結(jié)構(gòu)計(jì)算機(jī)處理的難點(diǎn)之一．

1 樹(shù)型結(jié)構(gòu)的屬性

樹(shù)型結(jié)構(gòu)是一種非線性數(shù)據(jù)結(jié)構(gòu)，除根節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都只有一個(gè)前驅(qū)，為該節(jié)點(diǎn)的雙親節(jié)點(diǎn)．每個(gè)節(jié)點(diǎn)可以有多個(gè)后繼，稱為孩子節(jié)點(diǎn)，沒(méi)有孩子的節(jié)點(diǎn)稱為葉子．從一個(gè)節(jié)點(diǎn)到其子孫節(jié)點(diǎn)的分支稱為路徑．從根節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所有的節(jié)點(diǎn)稱為該節(jié)點(diǎn)的祖先．如圖1所示，樹(shù)型結(jié)構(gòu)明顯具有層次關(guān)系，根節(jié)點(diǎn)A屬于第1層，BCD屬于第2層，EFGH 屬于第3層，IJKL屬于第4層．從理論上看，樹(shù)型結(jié)構(gòu)的每個(gè)節(jié)點(diǎn)都和其它的節(jié)點(diǎn)具有關(guān)系，關(guān)系密切的節(jié)點(diǎn)包括它的祖先和子孫[3-4]．

2 樹(shù)型結(jié)構(gòu)的問(wèn)題

樹(shù)型結(jié)構(gòu)的核心是數(shù)據(jù)元素之間一對(duì)多的關(guān)系．然而在關(guān)系數(shù)據(jù)庫(kù)中，表是以行和列的形式組織起來(lái)的數(shù)據(jù)集合，數(shù)據(jù)元素之間呈線性排列，彼此間沒(méi)有關(guān)系．如何在關(guān)系數(shù)據(jù)庫(kù)中設(shè)計(jì)樹(shù)型數(shù)據(jù)結(jié)構(gòu)并有效應(yīng)用，是我們要解決的問(wèn)題[2]．關(guān)系數(shù)據(jù)庫(kù)用一張二維表表示一個(gè)具有共同屬性節(jié)點(diǎn)的集合，每條記錄表示一個(gè)節(jié)點(diǎn)．但是記錄的先后順序和節(jié)點(diǎn)之間的關(guān)系無(wú)關(guān)．節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系也可通過(guò)二維表表示，但必須具有相同的外鍵．對(duì)于具有n個(gè)節(jié)點(diǎn)的樹(shù)型結(jié)構(gòu)，理論上要建立n(n-1)/2張表來(lái)描述它們之間的關(guān)系，這必然造成大量的數(shù)據(jù)冗余，而且給數(shù)據(jù)完整性的維護(hù)造成困難．

圖1 一棵樹(shù)的結(jié)構(gòu)圖

要描述樹(shù)型結(jié)構(gòu)的節(jié)點(diǎn)之間的關(guān)系，通常的做法記錄節(jié)點(diǎn)的同時(shí)記錄其雙親節(jié)點(diǎn)的地址或關(guān)鍵字．這種方法只能直接描述其雙親，不能直接描述它的其他祖先或子孫，這種方法叫做雙親表示法．另外一種方法就孩子表示法，記錄本節(jié)點(diǎn)的同時(shí)記錄所有孩子的關(guān)鍵字．這種方法的問(wèn)題在于，事先不知道每個(gè)孩子的個(gè)數(shù)，會(huì)造成表結(jié)構(gòu)的不確定．同樣的，這種方法只能直接描述其孩子，不能直接描述它的祖先和其他的子孫，這種方法叫做孩子表示法．這兩種方法共同的不足在于，要描述某節(jié)點(diǎn)的所有的祖先和子孫，必須編寫(xiě)算法進(jìn)行遍歷計(jì)算．不能利用關(guān)系數(shù)據(jù)庫(kù)所提供SQL查詢語(yǔ)言來(lái)直接進(jìn)行查詢．而SQL語(yǔ)言是關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)所使用的唯一的數(shù)據(jù)語(yǔ)言，功能非常靈活強(qiáng)大，可以實(shí)現(xiàn)數(shù)據(jù)定義、數(shù)據(jù)操作和數(shù)據(jù)控制等功能[5-11]．

3 樹(shù)型結(jié)構(gòu)的路徑表示方法

一種新的路徑表示方法可以比較好地解決上面方法所遇到的問(wèn)題．路徑表示法的本質(zhì)在于把樹(shù)型結(jié)構(gòu)線性化,關(guān)系數(shù)據(jù)庫(kù)只記錄從根節(jié)點(diǎn)到所有葉子節(jié)點(diǎn)的路徑,并且從左到右編號(hào)．如圖1所示，該圖共有5個(gè)葉子節(jié)點(diǎn)HIJKL，因此共需記錄5條路徑：路徑1：ABEI；路徑2：ABEJ;路徑3：ABFK;路徑4：ACGL;路徑5：ADH．

4 數(shù)據(jù)庫(kù)表的設(shè)計(jì)

設(shè)計(jì)一個(gè)關(guān)系TREE(路徑號(hào)，節(jié)點(diǎn)ID，節(jié)點(diǎn)名稱，節(jié)點(diǎn)所在層)以記錄圖1 中節(jié)點(diǎn)的關(guān)系，即根節(jié)點(diǎn)到葉子的路徑，如圖2所示．節(jié)點(diǎn)所在層為節(jié)點(diǎn)在樹(shù)中的層數(shù)，A在第1層，BCD在第2層，EFGH在第3層，IJKL在第4層.利用ACESS數(shù)據(jù)庫(kù)，創(chuàng)建一張表，名稱為TREE．錄入數(shù)據(jù)后如圖3 所示．

圖2 樹(shù)的存儲(chǔ)表結(jié)構(gòu)

圖3 樹(shù)在表TREE中的數(shù)據(jù)表示

5 節(jié)點(diǎn)關(guān)系SQL查詢

在應(yīng)用樹(shù)型結(jié)構(gòu)時(shí)，經(jīng)常需要查詢的功能有：能獲取任意節(jié)點(diǎn)的子節(jié)點(diǎn)集或子孫節(jié)點(diǎn)集；能獲取任意節(jié)點(diǎn)的父節(jié)點(diǎn)集或祖先節(jié)點(diǎn)集[11]．錄入數(shù)據(jù)后，就可以利用方便靈活的SQL語(yǔ)言，來(lái)進(jìn)行各種查詢．

(1)查詢某個(gè)節(jié)點(diǎn)的祖先，如節(jié)點(diǎn)E的祖先．首先，查出節(jié)點(diǎn)E所在的路徑號(hào)和節(jié)點(diǎn)在樹(shù)中的層數(shù)：

Select path，layer from tree where name=′E′;結(jié)果如圖4．

圖4 節(jié)點(diǎn)E的路徑和層

再查出E節(jié)點(diǎn)的祖先：

Select id,name from tree where path=1 and layer<3 order by layer；結(jié)果如圖5．

圖5 節(jié)點(diǎn)E的祖先

(2)查詢節(jié)點(diǎn)E的所有子孫.

Select id,name from tree where layer>3 and path in (select path from tree where name=′E′)； 結(jié)果如圖6．

圖6節(jié)點(diǎn)E的子孫

(3)查詢節(jié)點(diǎn)E的所有兄弟和堂兄弟.

Select distinct(name) from tree where layer=3； 結(jié)果如圖7．

圖7 節(jié)點(diǎn)E的兄弟和堂兄弟

6 結(jié)語(yǔ)

把非線性的樹(shù)型結(jié)構(gòu)轉(zhuǎn)化成線性的關(guān)系數(shù)據(jù)庫(kù)模型，是計(jì)算機(jī)處理樹(shù)型結(jié)構(gòu)的難點(diǎn)．利用路徑法解決上述問(wèn)題，并且可以利用現(xiàn)成的SQL語(yǔ)言對(duì)關(guān)系數(shù)據(jù)庫(kù)進(jìn)行操作，不用重新編程，不用重新改造SQL語(yǔ)言，就可以在數(shù)據(jù)庫(kù)中對(duì)樹(shù)型結(jié)構(gòu)進(jìn)行各種操作和查詢．對(duì)這種非線性數(shù)據(jù)結(jié)構(gòu)的信息處理具有很大的實(shí)用性．是非線性數(shù)據(jù)結(jié)構(gòu)線性化方法的一種突破．

[1]楊 帆,沈來(lái)信.基于樹(shù)型結(jié)構(gòu)的數(shù)據(jù)庫(kù)管理軟件的設(shè)計(jì)[J].黃山學(xué)院學(xué)報(bào),2014,16(3):38～41.

[2]呂 剛,蔣勇銘,王 軍.基于關(guān)系數(shù)據(jù)庫(kù)的樹(shù)形結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)光盤軟件與應(yīng)用,2012,(17):224～225.

[3]陳世東,黃有群.Oracle中的遞歸查詢算法在一般數(shù)據(jù)庫(kù)的實(shí)現(xiàn)[J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào),2001,23(5):432～436.

[4]趙愛(ài)芹,陳和平,熊健馳.關(guān)系數(shù)據(jù)庫(kù)層次樹(shù)查詢機(jī)制淺析[J].計(jì)算機(jī)工程與設(shè)計(jì),2006,27(18):3454～3456.

[5]張華興,孫 毅,單繼宏.網(wǎng)頁(yè)樹(shù)形結(jié)構(gòu)自動(dòng)生成研究[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2009,18(7):61～66.

[6]李俊飛,陳 皓,趙衛(wèi)東.樹(shù)形結(jié)構(gòu)數(shù)據(jù)輸入輸出控件的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2011,3(9):3054～3058.

[7]林子雨,楊冬青,王騰蛟.基于關(guān)系數(shù)據(jù)庫(kù)的關(guān)鍵詞查詢[J].軟件學(xué)報(bào),2010,(10):2454～2478.

[8]宋彩霞,新 春.Oracle數(shù)據(jù)庫(kù)基于索引SQL優(yōu)化方法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2004,25(12):2327～2330.

[9]李書(shū)振.ySQL數(shù)據(jù)庫(kù)的安全機(jī)制[J].計(jì)算機(jī)應(yīng)用,2002,22(6):51～53.

[10]蘭旭輝,熊家軍,鄧 剛.基于MySQL的應(yīng)用程序設(shè)計(jì)[J].計(jì)算機(jī)工程與設(shè)計(jì),2004,25(3):442～444.

[11]鄧宏濤.關(guān)系數(shù)據(jù)庫(kù)中樹(shù)型結(jié)構(gòu)信息的處理方法研究[J].江漢大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,38(2):50～53.