在網格數據組織中使用概念

designapp

摘要：商業企業每天產生大量的網格數據，作為網頁信息交換的實際標準，最重要的挑戰之一是如何有效地進行數據搜索，數據搜索可以以鏈接的方式進行。一些研究人員已經研究出了演算法，以減少搜索過程中產生的無效信息。另一些研究人員引入了記錄法，可以進行相關元素的定位，無需搜索原始網格文檔，通過記錄的方式完成搜索過程。文中介紹的方法是基于正在被搜索的數據的概念，以及對網格數據庫的內容搜索及關鍵字搜索，使用概念搜索可以提高搜索效率。
關鍵詞：網格；搜索；最佳化；演算；網頁描述語言WSDL
半結構化數據在網頁中的高級應用越來越普遍，商業企業每天生產及消費大量的數據。網格作為網頁上半結構化的數據具有相當復雜的內部結構，有時還被提取出來作為命令樹。
在大多數的網格搜索語言中，網格查詢的結構以鏈接的形式出現，網格元素的價值被用作選擇謂詞的一部分。有效鏈接模式匹配是網格數據庫中網格搜索程序的關鍵。
筆者概述了一種創新方式，將數據的概念考慮進來進行網格搜索，介紹了在網格數據庫中進行關鍵詞搜索的一種有效的演算法。該方法的實質是，如果數據的概念是已知的，那么數據的概念可以用于搜索最佳化。
首先定義一個數據模型，稱之為CRD—FS。半結構化的數據對象-關系-屬性模式，包括概念數據模型的實體，以及層次結構網格數據。有了CRD—FS數據模型，許多網格數據庫的概念可以明確的被呈現，但是不能被WSDL及網格模式所識別。
1 相關工作
X路徑是通過網格文檔中的元素及屬性，在網格文檔中發現信息的一種語言，同UNIX文檔系統中的目錄相似。例如，通過X路徑的表示：／院系／課程[代碼=＼cs4221”]／學生、學生姓名。可以表示為＼cs4221”課程的學生的名字。一條X路徑的搜索可以經樹狀圖表表示，稱為鏈接方式。X路徑被作為鏈接形式搜索的方式被呈現。
Chippimolchai et al．發展了一種演繹數據庫中概念搜索的最佳化框架。他們概述了一種演算方法，可以將搜索轉換成查詢及完整性約束，這些整體性約束是從真實世界產生的，不能從網格模式或WSDLs．中產生。
2 CRD-FS數據模型
半結構化的對象，關系，屬性數據模式有4個基本概念：對象類，關系類別，屬性及參考，包括4個圖表：模式圖表、距離圖表、功能獨立性圖表及層次圖表。
一個CRD—FS模式圖表代表著作為標簽的一個對象類。對象類之間的聯系類型被描述為標簽姓名(對象類清單)，N，P，C”，此處的姓名指示了關系類型的名稱，對象類是參與到關系類型中的對象類清單，N是一個整數，標明了關系類型的程度，P和C是關系類型中的參與限制，定義了使用標準的最小及最大的符號。兩個對象類之間的邊緣可以有多于一個的這樣的關系類型標簽去標明對象類所參與的不同的關系類型。關系類的屬性或者關系類型是有標簽圓圈所注解的。對象類的標識符像填充的圓圈一樣被注解，所有的屬性都應當并強制的，單值的，包含一個“?”，標明這是單值的，可選的，或者是一個“+”標明多值并且是被請求的，或者是一個“*”，標明其實可選多值的。對象類的屬性可以從一個關系類型中相區分出來。前者沒有邊緣標簽，當后者的關系類型的名稱屬于自己的標簽邊緣時。
屬性的名字，代碼和學生編號分別是對象類院系、課程和學生的標識符。每個學生都有其獨有的學生編號。標題的屬性、標記、地址和業余愛好都是可選的。業余愛好是多屬性，而學生姓名是必需的。這里有兩種關系類型，被稱之為dc and cs．前者是對象類部門同課程之間的二進制關系類型，后者是課程同學生之間的二進制關系類型。一個院系可以由一個或更多的(1：n)課程，一項課程屬于一個或只一個院系(1：1)。一門課程可以由零個或更多(0：n)學生；一名學生可以選修一門或更多課程。學生同標記之間的邊緣上的標簽cs標明標記是關系類型cs的單獨價值屬性。也就是說，一門課程中一名學生的屬性標記。從這些約束條件中，可以派生出{課程；學生}→標記。
3 搜索過程中概念的使用
概念是通過CRD-FS模式進行優化鏈接模式，從而用3個鏈接查詢來進行搜索評估的。
搜索1：找出等同于“s123”的學生元素的學生姓名值，X路徑表示為：／／student[@stuNo=“s123”]／stuName
利用CRD—FS模式，可以知道學生姓名是學生對象類的一個單一值屬性，學生編號是學生的身份標識，因此學生編號→學生姓名。為了處理搜索，我們只需要找出帶有學生編號屬性的網格中的第一個學生元素即可。
此外，Wu et al．已經提議了一種演算方式，它集中搜索內容或具有概念信息值。
搜索2：找出所有學生的平均分。
解答該搜索處理器需要了解學生編號是對象類學生的標識符，并且要將課程同學生之間的關系類的單值屬性標記出來。
搜索3：找出課程中所有學生所取得的分數。
為了正確完成以上搜索，用戶需要明白學生編號是學生的標識符，代碼是課程的標識符，標記是課程與學生之間關系類型的單值，每一門課程僅僅由一個院系所提供，每一門課程在網格文檔中僅僅出現一次。當WSDLs模式無法捕捉所有所需概念時，該信息可以在CRD-FS模式圖表中被捕捉。
有了CRD—FS數據模型所捕捉的概念，我們可以解釋網格詢問是否正確，是否可以提高搜索評估性能。利用存儲在CRD-FS模式圖表中的概念，圖解搜索語言GLASS能夠自動生成搜索所用的X搜索，用戶沒有必要去編寫X搜索詢問。
4 網格中的內容搜索
網格文檔中處理一個鏈接模式的搜索包括結構搜索及內容搜索。大多數現有的演算方法無法將內容同結構搜索相區分。在結構處理期間，它們將內容節點同元素節點一樣處理，搜索所詢問的實際值需要依賴于原始文檔。我們提議將帶有相關表格的一個新的演算值(VERT)提取來克服這些局限。VERT技術是生成相關表格以便來存儲文檔內容，而不是將他們像節點那樣進行處理和標記。筆者所說的演算是基于文檔的概念信息。因為越多的概念被捕捉，筆者就可以進一步優化表格及詢問這樣可以極大的提高效率。
例如，考慮帶有包含標簽的網格樹。可以將數值內容同關系標簽中的母標簽一同存儲，而不是為每個網格標簽和數值內容存儲標簽數據流。有了這些關系表，當用戶在發出一個鏈接搜索時，系統就能夠自動將其重寫至搜索中，這里節點價格大于15，他們的PC關系被稱之為>15的價格節點所取代。可以在表格Rprice中執行至帶有數值的所有價格元素當中。其性能結構以書本的標簽數據流為基礎。ISBN以及價格’> 15，以這種方式，可節省所有大于15的數值內容的數據流的成本，以及在合并標簽數據流之間的結構的成本。用這種方式，當處理鏈接搜索時，也可以節省書本對象同其價值屬性之間的結構及其價格。
最終，基于由ORASS所捕捉到的概念，標題，價格等是書本對象類的唯一價值屬性，能夠將這些屬性的內容價值premerge到一個單獨的帶有書本對象標簽的關聯表格，有了premerged表格，可以對鏈接搜索作出回答。在premerged表格上僅僅可以完成一種有效的選擇。
5 網格中關鍵字連同概念的搜索
關鍵字的近似搜索是搜索網格數據庫的一種友好方式。該區域多數前期所做的努力都是集中于網格關鍵字近似搜索。網格的數據模式普遍都很簡單并且有效。然而，它們并不捕捉數據庫中的聯系，例如身份參考。相反，是基于圖表模式的捕捉聯系的技術，不過這些大多對于計算來說都是無效的。許多現有的技術并不開發模式信息，這些信息通常是以數據庫的形式出現。沒有了模式信息，關鍵詞近似技術在結果中呈現的可能性會很小，并且它們所返回的結果是不相關的。例如，LCA對于基于樹狀模式的關鍵字近似搜索會很大一部分返回到其全部數據庫的根部。
筆者建議的是一種互連對象模式，可以充分開發網格性能并且在模式出現時標注出其模式信息。在我們的模型中，數據庫管理員為結果標識出感興趣的對象類及同興趣對象之間的概念性連接。
有了感興趣的對象類，關于關鍵字近似搜索最具直覺結果的是含有所有關鍵字的興趣對象的清單。較之眾所周知的LCA概念(Lowest Comm on Ancestor)，將這些興趣清單稱之為ICA(Interested Common Ancestor)。同樣，用IRA(Interested Related Ancestors)概念來捕獲興趣對象及包含更多相關結果。一個IRA結果是一對包含所有關鍵字的對象，并且同概念性連接是聯系在一起的。例如，為了搜索“網格搜索程
序”，帶有標題“搜索程序”的標題以及引用或被“網格“所引用的論文被看作是IRA對象。
就執行時間和結果質量而言，實驗性的評估標明該方法要優于大多現存的學術系統。
6 結論
半結構化數據組織中的重要區域之一就是提供可以進行有效數據搜索的演算。本文中概述了一個最佳化方案，在數據已知的時候可以被引用。介紹了一種數據模型，在ORASS中可以呈現出必要的概念，并且已完成的最佳化方案進行描述，展示了當概念被包含在內的時候，鏈接方式是如何最佳化的。如何處理歷史鏈接演算中的價值，概念性的連接與對象類之間如何被運用在關鍵字接近的搜索中。
今后將研究如何使用ORASS中捕捉的其他概念進行鏈接方式詢問的進一步優化，這些優化方案哪些地方是有價值的，通過實驗來表明處理速度的提高。特別的信息是如何同最優化方式所鏈接的，如母子、始祖一后裔關系，否定，節點的指令，恒定值及節點輸出。