張瑞軍，黎雯霞，張志清，張 凌，張 鵬

(1. 武漢科技大學(xué)管理學(xué)院，湖北 武漢，430081;2. 武漢鐵路職業(yè)技術(shù)學(xué)院鐵道信號工程學(xué)院，湖北 武漢，430205)

基于“超”實體構(gòu)件的信息組織與呈現(xiàn)

張瑞軍1，黎雯霞2，張志清1，張 凌1，張 鵬1

(1. 武漢科技大學(xué)管理學(xué)院，湖北 武漢，430081;2. 武漢鐵路職業(yè)技術(shù)學(xué)院鐵道信號工程學(xué)院，湖北 武漢，430205)

在關(guān)系數(shù)據(jù)庫中，多層一對多實體級聯(lián)的樹形連接模式常發(fā)生中間結(jié)點語義歧義問題。為此，本文提出一種樹形結(jié)構(gòu) “超”實體模型，給出其概念、數(shù)據(jù)結(jié)構(gòu)、連接查詢算法和樹視圖構(gòu)造算法，分析了相應(yīng)的時間復(fù)雜度和存儲空間復(fù)雜度。在提出構(gòu)件模型的基礎(chǔ)上，設(shè)計了樹形結(jié)構(gòu)“超”實體構(gòu)件和1/K開關(guān)連接構(gòu)件。探討了基于可編輯電子書的〈深度，維度，交互性〉的三元組信息呈現(xiàn)方法?！俺睂嶓w模型及算法在大型信息系統(tǒng)的數(shù)據(jù)庫設(shè)計與主界面設(shè)計中取得了良好的應(yīng)用效果。

“超”實體；樹形結(jié)構(gòu)；信息組織；信息呈現(xiàn)；構(gòu)件；信息系統(tǒng)；數(shù)據(jù)庫

在關(guān)系數(shù)據(jù)庫概念模型中，常存在一種基于層次結(jié)構(gòu)的多級實體聯(lián)系模式，如企事業(yè)單位的行政組織機構(gòu)圖、設(shè)備備件分類、行政區(qū)域劃分等，在信息系統(tǒng)實現(xiàn)時，它多表現(xiàn)為一種樹形菜單式結(jié)構(gòu)[1]。以高校為例，其行政組織通常按[學(xué)校]→[學(xué)院]→[系]→[教研室]的多層級樹形結(jié)構(gòu)規(guī)劃實體，但是當(dāng)某一系為校直屬系時，會新增[學(xué)校]→[系]的關(guān)系模式。這時原有的樹形結(jié)構(gòu)就變?yōu)閳D結(jié)構(gòu)，[系]這一級實體原有的元組語義和函數(shù)依賴也將受到破壞。同時，當(dāng)訪問樹的層級很深、每層元組較多時，多級實體連接運算結(jié)果將寫到內(nèi)存的中間文件里，這將消耗大量的CPU和內(nèi)存資源，導(dǎo)致系統(tǒng)運行效率下降。

研究人員對樹形結(jié)構(gòu)進行了深入探討，如李俊飛等[2]采用TreeView控件設(shè)計樹形結(jié)構(gòu)輸入輸出控件，用于自定義單表和多表關(guān)聯(lián)；陳正銘[3]采用先根遍歷算法分析了樹形結(jié)構(gòu)在數(shù)據(jù)表中的存儲問題；唐青松[4]研究了深度優(yōu)先算法在樹形結(jié)構(gòu)數(shù)據(jù)表中的應(yīng)用。但這些研究均基于每一級實體的固定語義，沒有考慮樹形結(jié)點的語義發(fā)生變化的情況。為此，本文提出一種樹形結(jié)構(gòu)“超”實體的概念，給出其數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)表存儲模式及相關(guān)算法，并將其應(yīng)用于信息系統(tǒng)的數(shù)據(jù)組織與信息呈現(xiàn)中。

1 樹形結(jié)構(gòu)“超”實體

1.1 相關(guān)概念

定義1 樹形結(jié)構(gòu)“超”實體：對于多層具有一對多聯(lián)系的實體，提取其關(guān)鍵字和主要的共用屬性，將命名統(tǒng)一，并增加用于標(biāo)注父結(jié)點的關(guān)鍵字，將封裝好的實體稱為樹形結(jié)構(gòu)“超”實體。

以高校行政組織E-R圖(見圖1)為例，其各實體的關(guān)鍵字(ID1、ID2、…、IDn)和主要屬性(name1、name2、…、namen)命名不同，但語義一致，可將它們歸一化，并增加一個標(biāo)識父結(jié)點的屬性，這樣便形成了如下的關(guān)系模式：

sup_ent(ID，name，upID)

其中，ID為關(guān)鍵字，用于唯一標(biāo)識樹中某一結(jié)點實體；name為結(jié)點名；upID為父結(jié)點的編碼，作為外關(guān)鍵字與父結(jié)點關(guān)聯(lián)。這種關(guān)系模式采用靜態(tài)表的方式實現(xiàn)了如圖2所示的樹形數(shù)據(jù)結(jié)構(gòu)[5]，表1為相應(yīng)的靜態(tài)數(shù)據(jù)表示例。

Fig.1 E-R diagram of administrative organization in universities

表1 樹形結(jié)構(gòu)“超”實體對應(yīng)的靜態(tài)數(shù)據(jù)表示例

Table 1 Example of static data tables related to the tree structure super entity

定義2 邏輯層：“超”實體樹中的各層。各結(jié)點在邏輯層中的深度為樹中各結(jié)點的深度。

定義3 語義層：“超”實體樹中狹義語義相同的各層。若同一語義層的各結(jié)點不在同一邏輯層，則將它們歸約到邏輯層最深的一層。

如表1所示，ID值為001的學(xué)校處于邏輯層和語義層的第1層，邏輯層的第2層為學(xué)院、第3層為系。而ID值為002的計算機系作為直屬系，在邏輯層上為第2層，而語義層則被歸約到第3層。這也有效地解決了[系]這一實體發(fā)生語義歧義的問題。

1.2 基本算法

樹形結(jié)構(gòu)“超”實體具有雙重屬性，在存儲上表現(xiàn)為一個數(shù)據(jù)表，在數(shù)據(jù)結(jié)構(gòu)上表現(xiàn)為樹，其基本算法有：

(1) CreateTree(&T,structure);//按structure結(jié)構(gòu)來構(gòu)造樹。

(2) SetValue(T, cur_node,values); //將values值賦給cur_node結(jié)點的除ID、upID屬性之外的其它屬性組。

(3) GetValue(T, cur_node,values); //取出cur_node結(jié)點屬性組的值，并賦給values變量組。

(4) InsertChild(&T, p, c); //將樹T的子樹c的根結(jié)點ID值賦給p所指向結(jié)點的upID屬性。

(5) DeleteChild(&T, cur_node); //刪除cur_node所指向結(jié)點及以cur_node為根結(jié)點的子樹。

(6) Parent(T, cur_node); //順序訪問按ID屬性索引的數(shù)據(jù)表，若cur_node的upID值不為空，則返回ID值等于cur_node的upID值的結(jié)點，否則返回空。

(7) Son(T, cur_node); //順序訪問按ID屬性索引的數(shù)據(jù)表，返回upID值等于cur_node的ID值的結(jié)點組，否則返回空。

(8) TraverseTree(T, Visit()); //按照Visit()策略訪問樹中的每個結(jié)點一次，且僅訪問一次。這里有兩種遍歷策略：① 順序遍歷，即從頭至尾訪問“超”實體樹所對應(yīng)的數(shù)據(jù)表一次；②廣度優(yōu)先遍歷，即將“超”實體樹所對應(yīng)的數(shù)據(jù)表按upID屬性建立索引，順序訪問該表一次。

1.3 連接查詢運算

信息系統(tǒng)開發(fā)中常涉及多個表之間的關(guān)聯(lián)運算，其算法為：

Connect(T, Ent)；//將“超”實體樹T中處于第k語義層的元組與語義上處于第k+1層的實體關(guān)聯(lián)起來。

這里討論一下查詢運算中從根結(jié)點一直訪問到語義層最深(設(shè)為k)的結(jié)點(葉子結(jié)點)，并與語義上處于第k+1層的普通實體進行連接時(如表1中的教研室元組與另一個教師數(shù)據(jù)表之間的連接)，傳統(tǒng)樹形結(jié)構(gòu)與“超”實體樹之間的算法復(fù)雜度對比。

以上兩個實體的前三個對應(yīng)字段語義相同，假定二者長度相同，前一實體多出Others這一字段。定義sup_ent實體中每個元組的容量為1，則二者元組存儲容量之比為：

(1)

式中：Centi為傳統(tǒng)樹結(jié)構(gòu)第i層實體存儲容量；Csup_ent為樹形結(jié)構(gòu)“超”實體存儲容量；ai為增量因子。

假定傳統(tǒng)樹形結(jié)構(gòu)中第i層實體的元組數(shù)為ni(i=1,2,…,k), 第k+1層實體對應(yīng)數(shù)據(jù)表容量為C。數(shù)據(jù)表連接時通常通過笛卡兒積運算來完成，這時首先在內(nèi)存中按一定規(guī)則交替讀取兩個表的若干塊元組，做連接運算后寫入內(nèi)存的中間文件，再讀取中間文件，根據(jù)查詢的需要做選擇和投影運算。當(dāng)傳統(tǒng)樹形結(jié)構(gòu)的前k層數(shù)據(jù)表做連接運算后并與第k+1層數(shù)據(jù)表連接時，生成的中間文件大小為：

Cent=Cent1×Cent2×…×Centk×C

=n1(1+a1)×n2(1+a2)×…×nk(1+ak)C

(2)

而對于“超”實體樹，只需按upID建立索引，訪問一次后第k層的葉子結(jié)點和第k+1層數(shù)據(jù)表連接即可，生成的中間文件大小為：

Csup_ent=n1+n2+…+nk-1+nk×C

(3)

很顯然有：Cent?Csup_ent。

假設(shè)內(nèi)存每秒讀寫數(shù)據(jù)塊數(shù)為m，則讀寫時間分別為：

Tent=n1(1+a1)×n2(1+a2)×

…×nk(1+ak)C/m

(4)

Tsup_ent=(n1+n2+…+nk-1+nk×C)/m

(5)

同理也有：Tent?Tsup_ent。

2 基于樹形結(jié)構(gòu)“超”實體的信息組織算法

樹形結(jié)構(gòu)“超”實體數(shù)據(jù)表建立好后，可以將其按upID屬性建立索引，采用Windows系統(tǒng)中的TreeView這一類控件對表中數(shù)據(jù)按樹形結(jié)構(gòu)進行組織。這里可以采用廣度優(yōu)先算法來構(gòu)造，其算法描述如下：

(1)游標(biāo)cursor指向數(shù)據(jù)表第1條記錄，將其值賦給結(jié)構(gòu)變量tmp_node，樹的深度depth=1，樹的當(dāng)前結(jié)點tv[depth].cur_node= tmp_node；

(2)游標(biāo)指針下移，若游標(biāo)已指向數(shù)據(jù)表末端，則算法結(jié)束，否則轉(zhuǎn)向(3)；

(3)判斷tv[depth].cur_node.ID是否等于tmp_node.upID。若相等，則將tmp_node作為tv[depth].cur_node的子結(jié)點插入，否則轉(zhuǎn)向(4);

(4)判斷tv[depth].cur_node是否有下一個兄弟節(jié)點，有則訪問下一個兄弟節(jié)點，轉(zhuǎn)(3)，否則轉(zhuǎn)(5);

(5)depth++，轉(zhuǎn)(2)。

樹形結(jié)構(gòu)“超”實體構(gòu)造好后，可作為信息組織的骨架，通過1/K開關(guān)件與數(shù)據(jù)庫、網(wǎng)頁、電子地圖、Word文檔等各種媒介相連，形成一種可編輯電子書，以下就樹形結(jié)構(gòu)“超 ”實體與1/K開關(guān)件的構(gòu)件化進行探討。

3 構(gòu)件

3.1 定義

定義4 構(gòu)件：構(gòu)件是具有一定獨立功能的軟件單元，它通過輸入輸出接口在特定條件的觸發(fā)下完成相應(yīng)的功能。它可重用，也可封裝,其形式化定義為：

c=(cD,In,Out,Func,Triggers)

其中：cD為構(gòu)件的標(biāo)識符；In為構(gòu)件的輸入，有：In=(i1,i2,…,in),n≥0；Out為構(gòu)件的輸出，有：

3.2 樹形結(jié)構(gòu)“超”實體構(gòu)件

由樹形結(jié)構(gòu)“超”實體的信息組織算法可知，樹形結(jié)構(gòu)“超”實體構(gòu)件的輸入為數(shù)據(jù)表，輸出為樹，按照構(gòu)件的定義，其形式化描述為：

cD= sup_ent001；

In=〈數(shù)據(jù)表結(jié)構(gòu)及各元組數(shù)據(jù)〉；

Out=〈樹〉；

Triggers=〈用戶檢索需求〉；

Func=〈CreateTree,InsertChild, SetValue,GetValue, DeleteChild,Parent,Son,TraverseTree,Connect〉。

3.3 1/K開關(guān)連接構(gòu)件

在可編輯電子書中，為了實現(xiàn)不同媒體之間的無縫切換，前驅(qū)構(gòu)件與若干后繼構(gòu)件之間是一種1/K開關(guān)連接方式，形成1/K開關(guān)連接構(gòu)件，類似于物理電路中的單刀多擲開關(guān)。這時高層構(gòu)件是一個前驅(qū)構(gòu)件與多個后繼構(gòu)件的聚集，其構(gòu)件的輸入是前驅(qū)構(gòu)件的輸入，構(gòu)件的輸出是多個后繼構(gòu)件中某一個構(gòu)件的輸出，如圖3所示，其中：Ind為前驅(qū)構(gòu)件的輸入接口；Outd為前驅(qū)構(gòu)件的輸出接口；Out1、Out2、…、Outn分別為構(gòu)件1、構(gòu)件2、…、構(gòu)件n的輸出接口；Trigger1、Trigger2、…、Triggern分別為構(gòu)件1、構(gòu)件2、…、構(gòu)件n的觸發(fā)條件。

1/K開關(guān)連接構(gòu)件的形式化描述為：

1/K_switcher_Con=(cD,In,Out,Triggers)

其中：cD=switcher001；In=Ind；Triggers=(Trigger1,Trigger2,…,Triggern)，有

3.4 可編輯電子書

可編輯電子書以樹形結(jié)構(gòu)“超”實體構(gòu)件為根、1/K開關(guān)連接件為分支、多種閱讀器構(gòu)件為結(jié)點，形成如圖4所示的樹形邏輯構(gòu)架。

4 基于可編輯電子書的信息呈現(xiàn)方式

現(xiàn)代認(rèn)知學(xué)和人類工效學(xué)表明，不同的信息呈現(xiàn)方式對人們的信息獲取能力、知識學(xué)習(xí)能力、決策能力等有很大的影響[6]。典型的信息呈現(xiàn)方式有網(wǎng)頁、信息系統(tǒng)、內(nèi)容組織圖等。網(wǎng)頁以超文本鏈接的方式呈現(xiàn)信息，有利于信息資源的瀏覽與搜索，但由于缺乏對事物的整體認(rèn)識，易讓人產(chǎn)生迷惘感；傳統(tǒng)的信息系統(tǒng)多以二維表文本方式對信息進行組織，有很好的條理性和可交互性，但缺乏直觀的感覺；內(nèi)容組織圖以空間地圖、圖表、視頻等方式呈現(xiàn)信息，對人的視覺形成強烈沖擊，但其層次感不強、信息表達(dá)的深度不夠。這里以“超”實體樹形結(jié)構(gòu)為目錄，采用“快捷菜單+主題目錄區(qū)+工作區(qū)”的∏型結(jié)構(gòu)，給出一種可編輯電子書框架，其中工作區(qū)部分以1/K開關(guān)連接構(gòu)件與樹形結(jié)構(gòu)“超”實體構(gòu)件相關(guān)聯(lián)，既可呈現(xiàn)關(guān)系數(shù)據(jù)庫中的結(jié)構(gòu)化信息，也可呈現(xiàn)網(wǎng)頁、地圖、視頻等非結(jié)構(gòu)化信息，其界面如圖5所示。

該框架采用〈深度，維度，交互性〉三元組的信息呈現(xiàn)模型。深度方面，以“超”實體樹的組織方式，通過樹結(jié)點的逐層展開，從各個層次來表征信息，讓用戶對事物全貌有一個總體的認(rèn)識；維度方面，以快捷菜單和流行的圖文并茂的QQ菜單，從多側(cè)面、多角度表現(xiàn)事物，并根據(jù)用戶要求定制觀察視覺；交互性方面，通過增、刪、改、除等功能按鈕對對象的屬性進行編輯。

5 應(yīng)用實例

筆者所在項目組承擔(dān)了水利部大型信息系統(tǒng)項目長江防洪工程工情信息服務(wù)系統(tǒng)的設(shè)計與開發(fā)工作。該系統(tǒng)主要對長江中下游沿岸40多個堤段、涵閘、除險加固工程、崩岸整治工程的地質(zhì)情況進行集中管理。作為一種數(shù)字圖書館，該系統(tǒng)除存儲結(jié)構(gòu)化的數(shù)據(jù)庫信息外，還要存儲視頻、網(wǎng)頁、地圖、Word文檔等半結(jié)構(gòu)化或非結(jié)構(gòu)化的信息，傳統(tǒng)結(jié)構(gòu)化的一對多實體級聯(lián)模式已無法滿足其要求。這里采用基于樹形結(jié)構(gòu)“超”實體的可編輯電子書框架。

對結(jié)構(gòu)化數(shù)據(jù)，按照圖5所示的“主題目錄區(qū)+QQ菜單+明細(xì)表+網(wǎng)絡(luò)表”的風(fēng)格呈現(xiàn)數(shù)據(jù)。系統(tǒng)實現(xiàn)時，后臺采用SQL Server數(shù)據(jù)庫存儲地質(zhì)、地貌、水文、巖土、水利等相關(guān)信息。由于所涉及各堤段的從屬關(guān)系特別復(fù)雜，對應(yīng)樹形目錄中各層級的語義不盡相同，故采用“超”實體對樹形目錄進行管理，如圖6所示。圖6中，目錄樹的深度為5，葉子節(jié)點荊江大堤邏輯層為第4層，語義上歸約為第5層；武漢市長江干堤節(jié)點下的葉子節(jié)點長江右岸節(jié)點的邏輯層與語義層均為第5層，這兩類葉子節(jié)點語義相同，均可與數(shù)據(jù)表相連，這就很好地解決了一對多實體級聯(lián)時語義歧義的問題。項目組還進行了對比測試：在相同軟硬件條件下，分別采用傳統(tǒng)的一對多表關(guān)聯(lián)和樹形結(jié)構(gòu)“超”實體進行表結(jié)構(gòu)設(shè)計時，前者算法檢索第5級數(shù)據(jù)表所用時間為5.23 s，而采用后者算法的檢索時間僅為0.56 s。

對非結(jié)構(gòu)化、半結(jié)構(gòu)化的數(shù)據(jù)，按照“主題目錄區(qū)+工作區(qū)”的風(fēng)格呈現(xiàn)信息，圖7給出了地圖的呈現(xiàn)方式。這種信息呈現(xiàn)模式以樹形結(jié)構(gòu)“超”實體構(gòu)件為骨架，通過1/K開關(guān)連接件與地圖瀏覽器構(gòu)件相關(guān)聯(lián)，可以很方便地在工作區(qū)內(nèi)對地圖進行縮放等瀏覽操作。當(dāng)然也可通過1/K開關(guān)連接件與Word編輯器、網(wǎng)頁瀏覽器、視頻播放器等構(gòu)件相連，完成非結(jié)構(gòu)化信息的呈現(xiàn)。

6 結(jié)語

本文提出了一種解決一對多多級實體級聯(lián)中元組語義歧義問題的“超”實體模型及其構(gòu)造算法。該算法吸取樹形數(shù)據(jù)結(jié)構(gòu)的優(yōu)點，以雙親結(jié)點表示法來完成數(shù)據(jù)表的存儲，在軟件實現(xiàn)上采用Windows中TreeView控件進行封裝，在信息呈現(xiàn)方面采用目錄樹結(jié)構(gòu)，配合QQ菜單等控件構(gòu)成一種可編輯電子書框架，并在實際信息系統(tǒng)的設(shè)計與開發(fā)中取得了良好的應(yīng)用效果。該算法框架可以使用戶在使用信息系統(tǒng)時多層次、多角度地了解事物對象，為大型信息系統(tǒng)中的數(shù)據(jù)庫設(shè)計與主界面設(shè)計提供了一種很好的思路。

[1] 張瑞軍. 基于樹形結(jié)構(gòu)的數(shù)據(jù)檢索方式研究[J]. 安徽電子信息職業(yè)技術(shù)學(xué)院學(xué)報,2004，3(3):60-62.

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

[3] 陳正銘．樹形結(jié)構(gòu)在關(guān)系數(shù)據(jù)庫中的存儲與運算[J]．韶關(guān)學(xué)院學(xué)報，2008，29(9): 18-22.

[4] 唐青松．深度優(yōu)先算法在創(chuàng)建樹形結(jié)構(gòu)中的應(yīng)用研究[J]．計算機技術(shù)與發(fā)展，2014, 24(9)：226-229.

[5] 張瑞軍, 杜星球, 陳定方．樹形結(jié)構(gòu)“超”實體構(gòu)造算法在雙重模式下的實現(xiàn)[J]．微計算機信息，2006, 22(11): 215-217.

[6] 張婷. 多媒體呈現(xiàn)方式與認(rèn)知風(fēng)格對學(xué)習(xí)效果的影響研究[D]. 大連：遼寧師范大學(xué), 2013.

[責(zé)任編輯 尚 晶]

Information organization and presentation based on super entity component

ZhangRuijun1,LiWenxia2,ZhangZhiqing1,ZhangLing1,ZhangPeng1

(1.College of Management，Wuhan University of Science and Technology，Wuhan 430081，China; 2.Department of Railway Signal Engineering, Wuhan Railway Vocational College of Technology, Wuhan 430205, China)

In relational database, the problem of semantic ambiguity always happens to the intermediate nodes in tree structure of multilayer one-to-many entity relationship. This paper proposes a model of tree structure super entity, discusses the concepts, data structure, join query method and tree view construction algorithm of the super entity, and analyzes the time and space complexity of the algorithms. On the basis of the proposed component model, a tree structure super entity component and a 1/K switch connection component are designed. A three-tuple information presentation method of 〈depth, dimension, interaction〉 based on editable e-book is explored. Applied to the design of database and main interface of a large information system,the model and algorithms of super entity have yielded excellent results.

super entity; tree structure; information organization; information presentation; component; information system; database

2015-07-06

國家自然科學(xué)基金面上項目(71271161)；湖北省自然科學(xué)基金資助項目(2014CFB804，2015CFB564)；教育部人文社會科學(xué)研究專項任務(wù)項目(工程科技人才培養(yǎng)研究) (13JDGC009)；湖北省科技支撐計劃軟科學(xué)研究類一般項目(2015BDF087).

張瑞軍(1972-)，男，武漢科技大學(xué)教授，博士. E-mail：zrjdoctor@126.com

TP311

A

1674-3644(2015)05-0385-06