基于“超”實體構件的信息組織與呈現

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

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

基于“超”實體構件的信息組織與呈現

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

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

在關系數據庫中，多層一對多實體級聯的樹形連接模式常發生中間結點語義歧義問題。為此，本文提出一種樹形結構 “超”實體模型，給出其概念、數據結構、連接查詢算法和樹視圖構造算法，分析了相應的時間復雜度和存儲空間復雜度。在提出構件模型的基礎上，設計了樹形結構“超”實體構件和1/K開關連接構件。探討了基于可編輯電子書的〈深度，維度，交互性〉的三元組信息呈現方法。“超”實體模型及算法在大型信息系統的數據庫設計與主界面設計中取得了良好的應用效果。

“超”實體；樹形結構；信息組織；信息呈現；構件；信息系統；數據庫

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

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

1 樹形結構“超”實體

1.1 相關概念

定義1 樹形結構“超”實體：對于多層具有一對多聯系的實體，提取其關鍵字和主要的共用屬性，將命名統一，并增加用于標注父結點的關鍵字，將封裝好的實體稱為樹形結構“超”實體。

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

sup_ent(ID，name，upID)

其中，ID為關鍵字，用于唯一標識樹中某一結點實體；name為結點名；upID為父結點的編碼，作為外關鍵字與父結點關聯。這種關系模式采用靜態表的方式實現了如圖2所示的樹形數據結構[5]，表1為相應的靜態數據表示例。

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

表1 樹形結構“超”實體對應的靜態數據表示例

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

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

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

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

1.2 基本算法

樹形結構“超”實體具有雙重屬性，在存儲上表現為一個數據表，在數據結構上表現為樹，其基本算法有：

(1) CreateTree(&T,structure);//按structure結構來構造樹。

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

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

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

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

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

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

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

1.3 連接查詢運算

信息系統開發中常涉及多個表之間的關聯運算，其算法為：

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

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

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

(1)

式中：Centi為傳統樹結構第i層實體存儲容量；Csup_ent為樹形結構“超”實體存儲容量；ai為增量因子。

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

Cent=Cent1×Cent2×…×Centk×C

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

(2)

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

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

(3)

很顯然有：Cent?Csup_ent。

假設內存每秒讀寫數據塊數為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 基于樹形結構“超”實體的信息組織算法

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

(1)游標cursor指向數據表第1條記錄，將其值賦給結構變量tmp_node，樹的深度depth=1，樹的當前結點tv[depth].cur_node= tmp_node；

(2)游標指針下移，若游標已指向數據表末端，則算法結束，否則轉向(3)；

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

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

(5)depth++，轉(2)。

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

3 構件

3.1 定義

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

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

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

3.2 樹形結構“超”實體構件

由樹形結構“超”實體的信息組織算法可知，樹形結構“超”實體構件的輸入為數據表，輸出為樹，按照構件的定義，其形式化描述為：

cD= sup_ent001；

In=〈數據表結構及各元組數據〉；

Out=〈樹〉；

Triggers=〈用戶檢索需求〉；

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

3.3 1/K開關連接構件

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

1/K開關連接構件的形式化描述為：

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

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

3.4 可編輯電子書

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

4 基于可編輯電子書的信息呈現方式

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

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

5 應用實例

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

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

對非結構化、半結構化的數據，按照“主題目錄區+工作區”的風格呈現信息，圖7給出了地圖的呈現方式。這種信息呈現模式以樹形結構“超”實體構件為骨架，通過1/K開關連接件與地圖瀏覽器構件相關聯，可以很方便地在工作區內對地圖進行縮放等瀏覽操作。當然也可通過1/K開關連接件與Word編輯器、網頁瀏覽器、視頻播放器等構件相連，完成非結構化信息的呈現。

6 結語

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

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

[2] 李俊飛, 陳皓, 趙衛東. 樹形結構數據輸入輸出控件的設計與實現[J]. 計算機工程與設計，2011，32(9)：3054-3058.

[3] 陳正銘．樹形結構在關系數據庫中的存儲與運算[J]．韶關學院學報，2008，29(9): 18-22.

[4] 唐青松．深度優先算法在創建樹形結構中的應用研究[J]．計算機技術與發展，2014, 24(9)：226-229.

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

[6] 張婷. 多媒體呈現方式與認知風格對學習效果的影響研究[D]. 大連：遼寧師范大學, 2013.

[責任編輯 尚 晶]

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

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

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

TP311

A

1674-3644(2015)05-0385-06