基于刻面分類模式的構件庫檢索方法

摘要：可復用軟件構件的檢索是構件庫和軟件復用領域研究的一個重要課題。基于刻面分類模式的檢索方式擁有準確、高效的優勢，因而得到了廣泛應用。論文介紹了刻面分類模式的相關概念以及刻面樹的創建方式，分析了基于刻面分類模式對軟件構件庫進行檢索的規則，該規則將用戶選擇的刻面和術語通過合理的并和交運算組合生成數據庫查詢條件來完成檢索。最后根據規則提出了相應算法以及刻面分類模式檢索在實際構件庫系統中的實現方法。

關鍵詞：軟件復用；構件庫；刻面；構件檢索

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)16-21315-03

Component Retrieval Method Based on Faceted Classification Scheme

LIANG Yue1，REN Hong-min1，2，ZHANG Jing-zhou2

(1.Department of Information Engineering， Shanghai Maritime University， Shanghai 200135，China;2.Department of Computer Science and Technology， Fudan University， Shanghai 200433，China)

Abstract: The retrieval of software components is an important issue in the development of component library and research on reusable software. The retrieval technologies based on faceted classification scheme have been widely accepted for its high accuracy and efficiency. This paper introduces the idea of faceted classification scheme and facet tree， analyzes the principles of retrieving components based on faceted classification scheme， which process the facets and terms selected by user and accomplish the condition of data base query by some reasonable union and intersection operations. According to the principles， it proposes an arithmetic and some implementation methods in a real component library management system.

Key words: software reuse; component library; facet; component retrieval

1 引言

隨著對軟件復用技術的深入研究和軟件構件數量的迅速增長，構件庫系統得到了廣泛使用。它對軟件構件進行管理，提供描述、分類、存儲和檢索等功能，滿足用戶查詢和獲取構件的需求。在構件庫系統中，如何高效地檢索，使用戶能夠快速定位到所需要的構件，成為了軟件復用領域研究的關鍵問題之一。

近年來，根據刻面（facet）對軟件構件進行分類以及按刻面進行檢索的方式越來越受到重視。這種方法適用于大規模的構件管理，同時又是檢索代價、復雜性和檢索質量三者最為均衡的方法[1]。與一般的層次分類方式相比，刻面分類模式易于修改，也避免了一般的關鍵詞分類方式容易出現的混亂，能夠提高檢索效率，而且有助于復用者理解構件和目標領域?；谝陨蟽烖c，構件的刻面表示以及在此基礎上的構件檢索技術成為了研究的熱點。

2 相關研究工作

構件的分類和檢索方法有很多種，從構件表示出發可分為人工智能方法、超文本方法和信息科學方法三類[2]，刻面分類檢索方法屬于信息科學法。現代構件庫系統的刻面分類檢索方法最早由Prieto-Diaz和Freeman提出，它通過抽取軟件構件的某些本質特征（稱之為刻面）來作為軟件構件的描述符，對構件進行精確的分類。之后NATO和REBOOT也分別提出了基于刻面的構件分類標準與模型，現在國內的青鳥構件庫就采用了以刻面分類為主、多種分類方式相結合的方法對構件進行分類索引[3]，國外著名的開源軟件網站sourceforge.net和freshmeat.net也提供了按刻面分類方式檢索構件的功能。

但是很多現有的構件庫對于一次在多個刻面下選擇不同的術語進行檢索的支持還不夠，比如sourceforge構件庫只能在功能領域這樣的單一刻面下選擇術語來瀏覽構件，對此，近年來出現了借鑒樹匹配的相關結論來研究構件檢索技術的方法[4]。這種方法將一個構件庫中的刻面分類模式映射成一棵刻面樹，檢索構件時根據用戶輸入的信息和刻面分類模式生成一棵查詢樹，于是將構件的檢索問題轉化為兩棵樹的匹配問題，這也是目前刻面分類檢索方式的主要研究方法。本文則從另一個角度出發，不需生成查詢樹，而是將用戶在刻面樹中選擇的節點根據合理的并和交運算的規則，組合生成查詢條件，結合數據庫檢索技術來實現構件的匹配。文中提出并分析了相關規則，給出了相應的算法以及在構件庫中的實現方法。

3刻面分類模式與刻面樹

在研究刻面分類檢索方法之前，必須首先了解刻面分類模式這一核心概念。

定義（刻面分類模式）： 一個刻面分類模式（faceted scheme）由一組描述構件本質特征的刻面組成，每個刻面從不同的側面對構件庫中的構件進行分類。每個刻面由一組基本的術語（term）構成，稱為術語空間。一個構件可以被各個刻面下的一個或多個術語所描述，而每個刻面反映了對庫中構件的一種劃分[5]。

由定義可知，一個刻面分類模式包含多個刻面，每個刻面又對應數量不等的多個術語，構成該刻面的術語空間，因此可以很方便地采用樹形結構來表示刻面分類模式，將其中的主刻面、子刻面分別映射為樹中相應的父節點、子節點，將相應的術語映射為樹的葉節點。按這種方法映射生成的樹稱為刻面樹。一個刻面的術語空間中的術語之間也存在層級關系，例如術語T是“數據庫管理系統”，術語T’是“Oracle數據庫管理系統”，顯然被T’描述的構件也能被T描述，稱T是T’的上層術語，在刻面樹中也映射為父節點和子節點。在構件庫系統中，可以根據經驗和實際需要設計刻面分類模式。

4 刻面分類模式的檢索規則與算法

4.1 檢索規則

規則1：如果用戶檢索時選擇了某一刻面，則檢索結果是該刻面下所有子刻面的術語空間中的所有術語所描述的構件集合的并集。

從刻面樹的角度來看，以上規則可以解釋為：選擇了某個刻面節點，就相當于選擇了以此節點為根的子樹中的所有節點。根據規則1可以進一步得到以下規則：

規則2：如果用戶選擇了術語空間不相交（沒有祖先－后代關系）的兩個或多個刻面，那么檢索結果應該是分別選擇這些刻面所得結果的交集。

這是由于術語空間不相交的刻面分別從不同的角度出發對構件進行描述，因此用戶要查找的是同時具有不同方面特性的構件，應該對單個刻面檢索的結果取交集。

對于術語，由于構件本身的復雜性，或者由于構件庫提供的刻面分類模式不夠完善，對構件進行分類描述時，有些構件難以被分類到刻面樹的葉節點，即最下層的術語，而只能籠統地分類到某個中間層術語，因此提出以下規則：

規則3：如果用戶在檢索時選擇了某個非葉節點的術語，則檢索結果是僅被此術語所描述而不被其下層術語所描述的構件。

對于選擇了多個術語的情況，提出以下規則，這也是刻面檢索中最常用的規則。

規則4：如果用戶選擇了同一刻面術語空間中的多個術語，那么檢索結果是分別被這些術語所描述的構件集合取并集。如果用戶選擇了不同刻面術語空間中的多個術語，那么對每個刻面下選擇的術語描述的構件集合取并集得到的結果再取交集作為最終的檢索結果。

這是由于每個刻面的術語空間中的術語是從同一個角度描述構件，用不同的術語做關鍵詞來將構件分為不同的種類，所以選擇同一術語空間中的術語時，用戶要查詢的是分別屬于這些種類的構件，應該對每個術語的檢索結果取并集。而用戶選擇了不同刻面下不同術語空間中的術語時，與規則2的解釋類似，應該在前面取并集的結果基礎上再取交集，表示同時滿足各個刻面下術語的構件。由規則2和規則4不難推論出以下規則。

規則5：如果用戶選擇了某些刻面和另一些術語空間與之不相交的其他刻面下的某些術語，那么檢索結果應該是分別選擇這些刻面所得結果和分別選擇各個刻面下的術語所得結果的交集。

下面舉例說明，某構件庫提供的刻面分類模式如圖1所示，該刻面樹根節點下的兩層是刻面層，刻面層下的兩層是術語層，從A至F共6個黑色的節點表示用戶在檢索時選擇的節點。

圖1 刻面樹檢索規則實例

設每個術語t對應一個謂詞Pt，如果用戶在檢索時選擇了術語t，檢索結果就是所有滿足Pt的構件集合，記為Ct。類似地，將刻面f的檢索結果記為Cf。根據規則1，以刻面A為根節點的子樹中全部6個術語節點的檢索結果取并集作為以刻面A為根的子樹的檢索結果，即CA=C1∪C2∪C3∪C4∪C5∪C6，同理可得CB=C7。根據規則2可得CP=CA∩CB。根據規則3，CC僅包含被術語C所描述的構件，不包含被其子節點術語所描述的構件。根據規則4，術語C、D、E同屬于刻面M的術語空間，有CM= CC∪CD∪CE。又因為C、D、E與F屬于不同刻面的術語空間，因此CQ=CM∩CN = (CC∪CD∪CE)∩CF。最后，根據規則5可得整個刻面樹檢索的最終結果為：

CA∩CB∩CM∩CN = (C1∪C2∪C3∪C4∪C5∪C6)∩C7∩(CC∪CD∪CE)∩CF

若根據規則2對CP和CQ做交運算也能得到相同的結果。

4.2檢索算法

根據規則可知，檢索的過程是對刻面樹進行深度優先搜索，因此將刻面樹中節點按先序遍歷的順序排序，將排好的節點序列作為算法的輸入。此外每個節點要記錄自身的序號以及父節點序號，以便逐層向上查找祖先節點。具體的算法如下：

輸入：按先序排列的刻面樹節點序列(N1， N2， …， Nn)，其中去掉了刻面樹的根節點；刻面樹中被選中的節點的集合S

輸出：滿足S給出的查詢要求的構件集合C的表達式

(1) 將集合F、T、C分別置為空集，i=1

(2) while (i≠n+1)/* n是除去根節點的刻面樹的節點總數*/

(3) {if (Ni被選中)

(4){if (Ni是刻面)

(5) {F = Ni，i++/* F記錄當前選中的刻面*/

(6)while (F是Ni的祖先節點)

(7){if (Ni是術語) {將Ni放入當前選中刻面下的術語集合T}

(8) i++

(9)}

(10) }

(11) else/*Ni是被選中的術語*/

(12) {F =逐層向上查找Ni祖先時出現的第一個刻面

(13)將Ni放入集合T，i++/*集合T保存了刻面F下選中的術語*/

(14)while (F是Ni的祖先節點)

(15){if (Ni是被選中的術語) {將Ni放入集合T}

(16) i++

(17)}

(18) }

/*將集合T中所有術語對應的檢索結果取并集存入結果集C */

(19) if (C是空集) {C = (CT1∪CT2∪…∪CTm)}

(20) else {C = C∩(CT1∪CT2∪…∪CTm))}/*不同刻面之間取交集*/

(21) 將集合T清空

(22)}

(23)else{i++}/*沒有選中的節點不做處理*/

(24) }

4.3 算法分析

雖然算法中有循環的嵌套，但內外層循環是對同一個循環變量進行，整個算法只需對所有刻面樹節點進行一次遍歷，因此對于輸入的刻面樹的節點總數n的時間復雜度是線性的，檢索效率高。

5 刻面分類模式檢索在構件庫系統中的實現

在我們開發的構件庫系統原型中，設計并實現了上述規則與算法。該系統為B/S結構，刻面樹由6個刻面，120個術語構成，存儲在服務器端數據庫中，客戶端網頁上用JavaScript編寫了節點前帶有選擇框的樹形結構來顯示刻面樹。由于刻面樹中術語較多，一次下載整個樹的所有節點需要較長時間，因此采用了ASP.NET AJAX框架提供的異步請求方式，客戶端頁面無需整頁刷新，用戶選擇刻面和術語之后可以繼續在頁面上進行操作，提供了良好的用戶體驗。

在數據庫的設計方面，刻面樹表通過節點id和父節點id字段保存樹形結構的層級關系，此外還有節點類型和節點名稱字段。構件表中保存構件的id和名稱、描述、關鍵詞、作者、提交日期等相關信息。構件表與刻面樹表之間通過關聯關系表建立多對多的關系，該表使用了構件id和刻面樹節點id兩個外鍵。此外，由于刻面樹表保存的信息在檢索過程中將被大量頻繁地訪問，因此將其緩存在服務器的內存中，以進一步提高檢索效率。

實際運行中，用戶輸入選擇的節點，系統根據算法的輸出生成SQL查詢語句，完成數據庫檢索工作，將滿足需求的構件列表返回給用戶。經驗證，該系統取得了良好的檢索效果。

6 總結和下一步的工作

本文針對構件庫系統中的大量軟件構件，引入了構件的刻面分類模式，將構件的分類描述映射為刻面樹，提出并分析了用戶同時選擇多個不同層次的刻面和術語時，對構件進行檢索的規則，根據此規則給出了一種對刻面樹進行深度優先搜索的檢索算法，并論述了在實際構件庫系統中的實現方法?；诳堂娣诸惸Ｊ降臋z索方法相比單純依靠關鍵詞搜索或僅在某一個刻面下檢索，可以在一定程度上提高構件檢索的效率，降低用戶查找和理解構件的成本。

在實際應用的構件庫系統中，有了效率較高的檢索方法之后，對數據庫本身的優化，包括數據庫的設計及其查詢語句的優化成為提高整個系統的運行效率的關鍵，也是將來研究工作的重點。

參考文獻：

[1] 高強， 張曉明， 邊小凡. 基于特定領域構件庫系統中刻面分類模式的研究[J]. 計算機工程與應用， 2003， 30: 82-84.

[2] 陳元松， 賈浩. 軟件構件管理與重用方法探究[J]. 電腦知識與技術， 2007， (1): 148-149.

[3] 常繼傳， 李克勤， 郭立峰等. 青鳥系統中可復用軟件構件的表示與查詢[J]. 電子學報， 2000， 28(8): 20-24.

[4] 王淵峰， 張涌， 任洪敏等. 基于刻面描述的構件檢索[J]. 軟件學報， 2002， 13(8): 1546-1551.

[5] 孟聞天， 張維石， 史金余， 等. 一種基于刻面分類描述的軟件構件查詢方法[J]. 計算機工程與應用， 2005， 12: 61-64.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。