在網(wǎng)格數(shù)據(jù)組織中使用概念

毛艷

（西安文理學(xué)院 陜西 西安 710056）

半結(jié)構(gòu)化數(shù)據(jù)在網(wǎng)頁中的高級(jí)應(yīng)用越來越普遍，商業(yè)企業(yè)每天生產(chǎn)及消費(fèi)大量的數(shù)據(jù)。網(wǎng)格作為網(wǎng)頁上半結(jié)構(gòu)化的數(shù)據(jù)具有相當(dāng)復(fù)雜的內(nèi)部結(jié)構(gòu)，有時(shí)還被提取出來作為命令樹。

在大多數(shù)的網(wǎng)格搜索語言中，網(wǎng)格查詢的結(jié)構(gòu)以鏈接的形式出現(xiàn)，網(wǎng)格元素的價(jià)值被用作選擇謂詞的一部分。有效鏈接模式匹配是網(wǎng)格數(shù)據(jù)庫中網(wǎng)格搜索程序的關(guān)鍵[1]。

筆者概述了一種創(chuàng)新方式，將數(shù)據(jù)的概念考慮進(jìn)來進(jìn)行網(wǎng)格搜索，介紹了在網(wǎng)格數(shù)據(jù)庫中進(jìn)行關(guān)鍵詞搜索的一種有效的演算法。該方法的實(shí)質(zhì)是，如果數(shù)據(jù)的概念是已知的，那么數(shù)據(jù)的概念可以用于搜索最佳化。

首先定義一個(gè)數(shù)據(jù)模型，稱之為CRD-FS。半結(jié)構(gòu)化的數(shù)據(jù)對(duì)象—關(guān)系—屬性模式，包括概念數(shù)據(jù)模型的實(shí)體，以及層次結(jié)構(gòu)網(wǎng)格數(shù)據(jù)。有了CRD-FS數(shù)據(jù)模型，許多網(wǎng)格數(shù)據(jù)庫的概念可以明確的被呈現(xiàn)，但是不能被WSDL及網(wǎng)格模式所識(shí)別。

1 相關(guān)工作

X路徑是通過網(wǎng)格文檔中的元素及屬性，在網(wǎng)格文檔中發(fā)現(xiàn)信息的一種語言，同UNIX文檔系統(tǒng)中的目錄相似。例如，通過 X 路徑的表示：/院系/課程[代碼=cs4221"]/學(xué)生、學(xué)生姓名?？梢员硎緸閏s4221"課程的學(xué)生的名字。一條X路徑的搜索可以經(jīng)樹狀圖表表示，稱為鏈接方式。X路徑被作為鏈接形式搜索的方式被呈現(xiàn)[2]。

Chippimolchai et al.發(fā)展了一種演繹數(shù)據(jù)庫中概念搜索的最佳化框架[3]。他們概述了一種演算方法，可以將搜索轉(zhuǎn)換成查詢及完整性約束，這些整體性約束是從真實(shí)世界產(chǎn)生的，不能從網(wǎng)格模式或WSDLs.中產(chǎn)生。

2 CRD-FS數(shù)據(jù)模型

半結(jié)構(gòu)化的對(duì)象，關(guān)系，屬性數(shù)據(jù)模式有4個(gè)基本概念：對(duì)象類，關(guān)系類別，屬性及參考，包括4個(gè)圖表：模式圖表、距離圖表、功能獨(dú)立性圖表及層次圖表。

一個(gè)CRD-FS模式圖表代表著作為標(biāo)簽的一個(gè)對(duì)象類。對(duì)象類之間的聯(lián)系類型被描述為標(biāo)簽姓名（對(duì)象類清單），N，P，C”，此處的姓名指示了關(guān)系類型的名稱，對(duì)象類是參與到關(guān)系類型中的對(duì)象類清單，N是一個(gè)整數(shù)，標(biāo)明了關(guān)系類型的程度，P和C是關(guān)系類型中的參與限制，定義了使用標(biāo)準(zhǔn)的最小及最大的符號(hào)。 兩個(gè)對(duì)象類之間的邊緣可以有多于一個(gè)的這樣的關(guān)系類型標(biāo)簽去標(biāo)明對(duì)象類所參與的不同的關(guān)系類型。關(guān)系類的屬性或者關(guān)系類型是有標(biāo)簽圓圈所注解的。對(duì)象類的標(biāo)識(shí)符像填充的圓圈一樣被注解，所有的屬性都應(yīng)當(dāng)并強(qiáng)制的，單值的，包含一個(gè)“？”，標(biāo)明這是單值的，可選的，或者是一個(gè)“+”標(biāo)明多值并且是被請(qǐng)求的，或者是一個(gè)“*”，標(biāo)明其實(shí)可選多值的。對(duì)象類的屬性可以從一個(gè)關(guān)系類型中相區(qū)分出來。前者沒有邊緣標(biāo)簽，當(dāng)后者的關(guān)系類型的名稱屬于自己的標(biāo)簽邊緣時(shí)[4]。

屬性的名字，代碼和學(xué)生編號(hào)分別是對(duì)象類院系、課程和學(xué)生的標(biāo)識(shí)符。每個(gè)學(xué)生都有其獨(dú)有的學(xué)生編號(hào)。標(biāo)題的屬性、標(biāo)記、地址和業(yè)余愛好都是可選的。業(yè)余愛好是多屬性，而學(xué)生姓名是必需的。這里有兩種關(guān)系類型，被稱之為dc and cs.前者是對(duì)象類部門同課程之間的二進(jìn)制關(guān)系類型，后者是課程同學(xué)生之間的二進(jìn)制關(guān)系類型。一個(gè)院系可以由一個(gè)或更多的（1:n）課程，一項(xiàng)課程屬于一個(gè)或只一個(gè)院系（1:1）。一門課程可以由零個(gè)或更多（0:n）學(xué)生；一名學(xué)生可以選修一門或更多課程。學(xué)生同標(biāo)記之間的邊緣上的標(biāo)簽cs標(biāo)明標(biāo)記是關(guān)系類型cs的單獨(dú)價(jià)值屬性。也就是說，一門課程中一名學(xué)生的屬性標(biāo)記。從這些約束條件中，可以派生出{課程；學(xué)生}→標(biāo)記。

3 搜索過程中概念的使用

概念是通過CRD-FS模式進(jìn)行優(yōu)化鏈接模式，從而用3個(gè)鏈接查詢來進(jìn)行搜索評(píng)估的。

搜索1:找出等同于“s123”的學(xué)生元素的學(xué)生姓名值，X路徑表示為：//student[@stuNo=“s123”]/stuName

利用CRD-FS模式，可以知道學(xué)生姓名是學(xué)生對(duì)象類的一個(gè)單一值屬性，學(xué)生編號(hào)是學(xué)生的身份標(biāo)識(shí)，因此學(xué)生編號(hào)→學(xué)生姓名。為了處理搜索，我們只需要找出帶有學(xué)生編號(hào)屬性的網(wǎng)格中的第一個(gè)學(xué)生元素即可。

此外，Wu et al.已經(jīng)提議了一種演算方式，它集中搜索內(nèi)容或具有概念信息值。

搜索2：找出所有學(xué)生的平均分。

解答該搜索處理器需要了解學(xué)生編號(hào)是對(duì)象類學(xué)生的標(biāo)識(shí)符，并且要將課程同學(xué)生之間的關(guān)系類的單值屬性標(biāo)記出來。

搜索3：找出課程中所有學(xué)生所取得的分?jǐn)?shù)。

為了正確完成以上搜索，用戶需要明白學(xué)生編號(hào)是學(xué)生的標(biāo)識(shí)符，代碼是課程的標(biāo)識(shí)符，標(biāo)記是課程與學(xué)生之間關(guān)系類型的單值，每一門課程僅僅由一個(gè)院系所提供，每一門課程在網(wǎng)格文檔中僅僅出現(xiàn)一次。當(dāng)WSDLs模式無法捕捉所有所需概念時(shí)，該信息可以在CRD-FS模式圖表中被捕捉。

有了CRD-FS數(shù)據(jù)模型所捕捉的概念，我們可以解釋網(wǎng)格詢問是否正確，是否可以提高搜索評(píng)估性能。利用存儲(chǔ)在CRD-FS模式圖表中的概念，圖解搜索語言GLASS能夠自動(dòng)生成搜索所用的X搜索，用戶沒有必要去編寫X搜索詢問。

4 網(wǎng)格中的內(nèi)容搜索

網(wǎng)格文檔中處理一個(gè)鏈接模式的搜索包括結(jié)構(gòu)搜索及內(nèi)容搜索。大多數(shù)現(xiàn)有的演算方法無法將內(nèi)容同結(jié)構(gòu)搜索相區(qū)分。在結(jié)構(gòu)處理期間，它們將內(nèi)容節(jié)點(diǎn)同元素節(jié)點(diǎn)一樣處理，搜索所詢問的實(shí)際值需要依賴于原始文檔[5]。我們提議將帶有相關(guān)表格的一個(gè)新的演算值（VERT）提取來克服這些局限。VERT技術(shù)是生成相關(guān)表格以便來存儲(chǔ)文檔內(nèi)容，而不是將他們像節(jié)點(diǎn)那樣進(jìn)行處理和標(biāo)記。筆者所說的演算是基于文檔的概念信息。因?yàn)樵蕉嗟母拍畋徊蹲?，筆者就可以進(jìn)一步優(yōu)化表格及詢問這樣可以極大的提高效率。

例如，考慮帶有包含標(biāo)簽的網(wǎng)格樹?？梢詫?shù)值內(nèi)容同關(guān)系標(biāo)簽中的母標(biāo)簽一同存儲(chǔ)，而不是為每個(gè)網(wǎng)格標(biāo)簽和數(shù)值內(nèi)容存儲(chǔ)標(biāo)簽數(shù)據(jù)流。有了這些關(guān)系表，當(dāng)用戶在發(fā)出一個(gè)鏈接搜索時(shí)，系統(tǒng)就能夠自動(dòng)將其重寫至搜索中，這里節(jié)點(diǎn)價(jià)格大于15，他們的PC關(guān)系被稱之為>15的價(jià)格節(jié)點(diǎn)所取代?？梢栽诒砀馬price中執(zhí)行至帶有數(shù)值的所有價(jià)格元素當(dāng)中。其性能結(jié)構(gòu)以書本的標(biāo)簽數(shù)據(jù)流為基礎(chǔ)。 ISBN以及價(jià)格’>15.以這種方式，可節(jié)省所有大于15的數(shù)值內(nèi)容的數(shù)據(jù)流的成本，以及在合并標(biāo)簽數(shù)據(jù)流之間的結(jié)構(gòu)的成本。用這種方式，當(dāng)處理鏈接搜索時(shí)，也可以節(jié)省書本對(duì)象同其價(jià)值屬性之間的結(jié)構(gòu)及其價(jià)格。

最終，基于由ORASS所捕捉到的概念，標(biāo)題，價(jià)格等是書本對(duì)象類的唯一價(jià)值屬性，能夠?qū)⑦@些屬性的內(nèi)容價(jià)值premerge到一個(gè)單獨(dú)的帶有書本對(duì)象標(biāo)簽的關(guān)聯(lián)表格，有了premerged表格，可以對(duì)鏈接搜索作出回答。在premerged表格上僅僅可以完成一種有效的選擇。

5 網(wǎng)格中關(guān)鍵字連同概念的搜索

關(guān)鍵字的近似搜索是搜索網(wǎng)格數(shù)據(jù)庫的一種友好方式。該區(qū)域多數(shù)前期所做的努力都是集中于網(wǎng)格關(guān)鍵字近似搜索。網(wǎng)格的數(shù)據(jù)模式普遍都很簡單并且有效。然而，它們并不捕捉數(shù)據(jù)庫中的聯(lián)系，例如身份參考。相反，是基于圖表模式的捕捉聯(lián)系的技術(shù)，不過這些大多對(duì)于計(jì)算來說都是無效的。許多現(xiàn)有的技術(shù)并不開發(fā)模式信息，這些信息通常是以數(shù)據(jù)庫的形式出現(xiàn)。沒有了模式信息，關(guān)鍵詞近似技術(shù)在結(jié)果中呈現(xiàn)的可能性會(huì)很小，并且它們所返回的結(jié)果是不相關(guān)的[6]。例如，LCA對(duì)于基于樹狀模式的關(guān)鍵字近似搜索會(huì)很大一部分返回到其全部數(shù)據(jù)庫的根部。

筆者建議的是一種互連對(duì)象模式，可以充分開發(fā)網(wǎng)格性能并且在模式出現(xiàn)時(shí)標(biāo)注出其模式信息。在我們的模型中，數(shù)據(jù)庫管理員為結(jié)果標(biāo)識(shí)出感興趣的對(duì)象類及同興趣對(duì)象之間的概念性連接。

有了感興趣的對(duì)象類，關(guān)于關(guān)鍵字近似搜索最具直覺結(jié)果的是含有所有關(guān)鍵字的興趣對(duì)象的清單。較之眾所周知的LCA概念（Lowest Common Ancestor），將這些興趣清單稱之為ICA （Interested Common Ancestor）。 同樣，用 IRA （Interested Related Ancestors）概念來捕獲興趣對(duì)象及包含更多相關(guān)結(jié)果。一個(gè)IRA結(jié)果是一對(duì)包含所有關(guān)鍵字的對(duì)象，并且同概念性連接是聯(lián)系在一起的。 例如，為了搜索 “網(wǎng)格搜索程序”，帶有標(biāo)題“搜索程序”的標(biāo)題以及引用或被“網(wǎng)格“所引用的論文被看作是IRA對(duì)象。

就執(zhí)行時(shí)間和結(jié)果質(zhì)量而言，實(shí)驗(yàn)性的評(píng)估標(biāo)明該方法要優(yōu)于大多現(xiàn)存的學(xué)術(shù)系統(tǒng)。

6 結(jié) 論

半結(jié)構(gòu)化數(shù)據(jù)組織中的重要區(qū)域之一就是提供可以進(jìn)行有效數(shù)據(jù)搜索的演算。本文中概述了一個(gè)最佳化方案，在數(shù)據(jù)已知的時(shí)候可以被引用。介紹了一種數(shù)據(jù)模型，在ORASS中可以呈現(xiàn)出必要的概念，并且已完成的最佳化方案進(jìn)行描述，展示了當(dāng)概念被包含在內(nèi)的時(shí)候，鏈接方式是如何最佳化的。如何處理歷史鏈接演算中的價(jià)值，概念性的連接與對(duì)象類之間如何被運(yùn)用在關(guān)鍵字接近的搜索中。

今后將研究如何使用ORASS中捕捉的其他概念進(jìn)行鏈接方式詢問的進(jìn)一步優(yōu)化，這些優(yōu)化方案哪些地方是有價(jià)值的，通過實(shí)驗(yàn)來表明處理速度的提高。特別的信息是如何同最優(yōu)化方式所鏈接的，如母子、始祖-后裔關(guān)系，否定，節(jié)點(diǎn)的指令，恒定值及節(jié)點(diǎn)輸出。

[1]Wu T，Xue Y，Cui Y.Preserving Traffic Privacy in Wireless Mesh Networks[C]//Proceedings of WoWMoM’06， 2006.

[2]Bouam S，Othman J B.Data security in grid using multipath routing[C]//Proccedings of 14th IEEE International Symposium on Personal.Indoor and Mobile Radio Communication，2003.

[3]Michell S，Srinivasan K.State based key hop protocol:A lightweightsecurity protocolforwirelessnetworks[C]//Proceedings of PE-WASUN’04，2004.

[4]Soliman H S，Omari M.Application of synchronous dynamic encryption system in mobile wireless domains[C]//In Proceedings of the 1st ACM international workshop on Quality of service and security in wireless and mobile networks （Q2SWinet’05），2005:24-30.

[5]Junaid M，Mufti M，Ilyas M U.Vulnerabilities of IEEE 801.11i Wireless LAN CCMP Protocol，Transactions on Engineering[C]//Computing and Technology V11，2006.

[6]Housley R， Using Advanced Encryption Standard （AES）Counter Mode With IPsec Encapsulating Security Payload（ESP）[C]//RFC 3686，2004.