樹型結構在關系數(shù)據(jù)庫中的描述

方銀清

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

0 引言

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

1 樹型結構的屬性

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

2 樹型結構的問題

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

圖1 一棵樹的結構圖

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

3 樹型結構的路徑表示方法

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

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

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

圖2 樹的存儲表結構

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

5 節(jié)點關系SQL查詢

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結語

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

[1]楊 帆,沈來信.基于樹型結構的數(shù)據(jù)庫管理軟件的設計[J].黃山學院學報,2014,16(3):38～41.

[2]呂 剛,蔣勇銘,王 軍.基于關系數(shù)據(jù)庫的樹形結構設計與實現(xiàn)[J].計算機光盤軟件與應用,2012,(17):224～225.

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

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

[5]張華興,孫 毅,單繼宏.網(wǎng)頁樹形結構自動生成研究[J].計算機系統(tǒng)應用,2009,18(7):61～66.

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

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

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

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

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

[11]鄧宏濤.關系數(shù)據(jù)庫中樹型結構信息的處理方法研究[J].江漢大學學報(自然科學版),2010,38(2):50～53.