基于模式Ｐ２Ｐ系統復雜查詢處理研究
2007-12-31 00:00:00余敏李戰懷張龍波
計算機應用研究 2007年7期
摘要：通過以關系名的同義關鍵字作為模式信息的索引鍵以及垂直分區關系元組，設計了用結構化重疊網絡索引模式和數據的方法。基于這兩級索引，提出了支持多屬性復雜查詢的算法。定性分析和比較表明，該方法比相關工作更接近P2P數據管理的理想目標。
關鍵詞：對等計算機模型; 基于模式的; 復雜查詢處理
中圖分類號：TP311．13文獻標志碼：A
文章編號：1001－3695(2007)07－0081－05
0引言
Peer－to－Peer模型（又稱P2P模型或對等計算模型）是一種新型的體系結構模型。與傳統的客戶服務器模型不同，P2P系統中沒有集中控制點，從而避免了單點故障。P2P網絡是可擴展的、容錯的、動態的，節點可以容易地加入和離開網絡。因此P2P計算吸引了學術界和工業界越來越多的關注。
支持復雜查詢處理是對現有P2P系統中基于鍵(Key)和關鍵字搜索的自然擴展。要在P2P系統中實現復雜查詢回答功能需要解決若干個挑戰[1]：①P2P系統中Peer可以在任何時刻、任何地點，以任何方式離開網絡，因此產生了完全動態和即興的網絡環境。這樣底層協議必須足夠健壯以處理Peer和網絡故障。②查詢處理必須用完全分布式的過程。在動態P2P環境中，由于缺乏全局知識，查詢執行和優化都非常困難。③為了有效利用系統中的資源，自治Peer之間必須協作。這通常涉及更多的優化問題，如協調、位置感知Peer聚簇和負載平衡等。總而言之，P2P查詢處理必須能夠有效且高效地處理自治Peer組成的大規模動態分布式網絡[1]。
本文關注于P2P系統中的關系查詢處理問題。這是一個重要的研究領域，在電子學習、P2P數據庫、監視和流處理等領域具有廣泛應用前景。一般認為大規模P2P網絡中信息以關系元組的形式存在，這些元組可以用SQL查詢檢索。每個節點保存全部數據元組的一部分。屬于一個關系的元組的各部分可以分布在多個節點上。
P2P系統依賴于重疊網絡以便獨立于底層的物理網絡拓撲。重疊網絡有非結構化和結構化之分。在非結構化重疊網絡中對數據放置方式沒有嚴格要求，求值復雜查詢簡單；但是必須使用洪泛算法在網絡中分布查詢，開銷大卻不能保證在有限的跳步內找到存在的數據，阻礙了低帶寬用戶的加入，限制了P2P技術的應用。結構化重疊網絡通過對數據放置的嚴格限制，提供對查詢效率和系統健壯性的強大理論保證。但是，結構化重疊網絡本身只能支持確切匹配和范圍查詢，不能直接支持共享關系數據所需的連接、聚集等復雜查詢。因此，PIER[2]通過水平分區關系表，利用結構化重疊網絡索引關系的某個屬性來支持復雜查詢。但是它必須假定系統中所有節點服從同一個模式，不適合P2P語義異構網絡中共享信息；并且它僅能索引一個模式元素，而不能有效地支持多屬性復雜查詢。因此，本文研究基于結構化重疊網絡共享模式異構關系數據的方法。定性分析表明，該算法是可取的。
1框架概況
1．1Peer
Peer采用各自的模式來描述自己共享的數據，所關心的Peer模式是Peer節點的外模式。在節點內部，內模式和外模式之間的映射采用傳統數據庫中的視圖機制實現，在此不再贅述。Peer模式中為關系和關系的各屬性均維護一些關鍵字充當同義辭典[3]，進一步描述其語義。這樣，可以不必人工預先指定模式映射。每個節點由本地數據庫LDB、垂直分區器VP、索引分區緩沖區IPB、元數據抽取器ME、本地模式緩沖區LSB、索引模式緩沖區ISB組成。首先，ME從LDB中抽取外模式以及相應的同義辭典放入LSB中，它是本節點提供的共享數據模式。同時ME使用下面介紹的模式索引該模式。ISB存放按照模式索引發布到此節點上存儲的模式信息，然后VP按照共享模式從LDB中提取共享數據，將這些數據垂直分區成(tid，關系名：屬性名，屬性值)三元組[4]后發布到結構化實例索引中。IPB用來存放按照實例級索引分配給本地節點進行維護的三元組。筆者借鑒PIER[5]中軟狀態的方法來確保數據源故障的情況下，它所發布的數據和模式均會最終被丟棄。
1．2P2P網絡
圖1從宏觀角度粗略地描述了本文方法的核心思想：用戶通過用戶界面可以看到用戶當前登錄的節點p的ISB和LSB中的模式，用戶可以據此提出查詢q。p收到查詢后一方面直接用該查詢中使用的關系名和屬性名檢索實例級索引，獲得q的結果；另一方面，p查詢模式級索引，獲得與q語義相似的改寫后的查詢。此后，p再以改寫后的查詢檢索實例級索引獲得進一步的數據。
2模式級索引和實例級索引
2．1模式級索引
模式級索引主要用于檢索與用戶提出的查詢語義相似的模式，以便改寫查詢。模式級索引只需要對字符串的高效確切匹配查詢，因此任何結構化重疊網絡均可以用來做模式級索引。如前所述，要求用戶在創建關系時，為關系和屬性指定一些關鍵字充當同義辭典。對于關系的每個關鍵字，以它作為搜索鍵(結構化重疊網絡的索引Key)，將對應關系的模式信息以(關系名關鍵字，關系名，屬性1，屬性2，…，屬性n)形式發布到結構化重疊網絡中，并且附帶元數據文本文件：①各屬性也均附帶同義詞作為元數據；②附帶與該關系具有外碼(Foreign－key)引用的關系模式信息。
在模式索引中沒有數據源節點的信息，它僅僅包含網絡中可用模式列表，由數據源采用軟狀態的方式定期將自己的模式發布到模式索引中。
在找到含有滿足選擇條件的數據節點后，從該節點上可以找到滿足選擇條件的(tid，R ∶Ai，vi)三元組。為了獲得完整的關系元組(或者在完整的關系元組上應用投影操作)，那么需要以tid作為搜索鍵檢索BATON，經過O(log N)步找到匹配的節點。由于tid使用了數據源名和關系名作為前綴，而BATON沒有使用哈希函數，不破壞數據原來的順序，同一個關系的元組通常位于索引結構中相鄰的節點上。這樣找到全部滿足選擇條件的完整元組并不會比找到其中的一個完整元組花費太多的跳步。
3基于兩級索引的復雜查詢方法
3．1查詢改寫策略
本文僅關注查詢中含有投影、選擇、連接的情況，對于聚集查詢的支持是將來的工作。多操作符查詢采用流水線的方式處理，當一個操作符產生結果時直接流入下一個操作符。因此在計算查詢響應延遲時，對單個操作符只需考慮產生第一個結果元組的延遲。
查詢在網絡中以消息的形式傳遞，消息中包含查詢、查詢發起節點標志、查詢包含的屬性個數、反映各屬性是否翻譯完成的ready位串。
現在考慮如下查詢(為了清晰，這里省略查詢中標注的關鍵字)：
SELECT R.pkey，S.pkey，R.pad
FROM R，S
WHERE R.num1=S.pkey
AND R.num2＞constant1
AND S.num2＞constant2
用戶根據節點p的LSB和ISB中提供的模式提出上述查詢。接收節點p并行進行兩部分工作：①使用這個查詢直接檢索實例級索引。對于單個查詢條件的檢索方法在2．2節中已經說明。對于上述多個操作符的查詢處理算法將在下面說明，只需將R.num2＞constant1視為θR，將S.num2＞constant2視為θS，num1視為JR，pkey視為JS即可。②進行查詢翻譯。以R的各關鍵字分別檢索模式級索引，若存在匹配的關鍵字，那么對于每個關鍵字，在O(log N)步內能夠找到負責該關鍵字的節點。將查詢以消息的形式發往該節點，在該節點上盡可能翻譯查詢中的屬性。由于匹配的關系可能有多個，可能會產生多個改寫后的查詢并引入連接。每改寫一個屬性就將一個屬性的ready位設置為1。如果是涉及多個關系的查詢，那么以下一個關系的關鍵字檢索模式級索引，將查詢發到負責該關鍵字的節點。在該節點上繼續盡可能翻譯查詢。依此類推，直到所有的屬性均翻譯完，或者所有的關系均處理完但是仍有屬性沒有處理。對于后一種情況，直接丟棄這個未翻譯完的改寫后查詢。若所有的屬性均已翻譯完成，則將改寫后的查詢發回查詢發起節點，由查詢發起節點檢索實例級索引，方法與用原始查詢檢索實例級索引的方法相同。
3．2復雜查詢算法
查詢的翻譯和查詢在實例級的求值是分離的兩個過程，因此在討論連接算法時，不區分正在處理的查詢是由用戶根據本地節點模式直接提交的還是經過翻譯后獲得的。
按照垂直分區策略和實例級索引能夠將鄰近的范圍數據相鄰存放的特點，本文連接算法可以實現具有對稱半連接優化的提取—匹配連接算法[5](Fetch－Matches)。在具有有限帶寬的實際環境中，這是目前基于結構化重疊網絡的關系數據查詢引擎最優的連接算法。
按照數據庫理論中的經驗，通常盡可能先執行選擇操作再進行連接。另外，因為原始關系通常很大，所以一般的連接算法均會對原始關系進行某種選擇過濾后再應用連接。算法1說明了與上一節查詢形式相同的復雜查詢的處理方法。因為連接算法是可交換的，所以不失一般性。下面假定R是選擇性比較高(即會篩選掉較多元組)的關系。其中的符號符合關系代數中的標準，如t.JR表示元組t在JR屬性上的值。
3．3復雜查詢算法分析
ComplexQuery首先由查詢發起節點發起θR，無論是范圍查詢還是確切匹配查詢均可在O(log N)步內找到滿足條件的R的元組。對于R的元組，可以在O(log N)步內找到匹配連接屬性的S三元組，應用過濾條件θS，最好的情況下可以直接完成，在最壞的情況下，只需O(log N)步。GetSemiJoin將結果回送查詢發起節點時可以直接使用IP地址回送，不必在網絡中路由。查詢發起節點獲得完整的S元組也可在O(log N)步內完成。因此，整個復雜查詢執行可以在O(log N)步內完成。完成查詢所需的跳步總數與網絡中節點數成對數關系，表明此方法的可擴展性較好，性能有保證。
Algorithm 1 ComplexQuery(R，S，θR，θS，JR，JS，p)
Input:
R，S: two relations to be joined;
θR，θS: selection on R and S respectively;
JR，JS:the join attribute of R and S respectively;
p: the peer issuing the query.
Output:
Results of {t|t∈σθR(R)R.JR=S.JSσθS(S)}.
O={};
if θR not 1， then
ResultR=Selection(R，θR，p);//section 2．2
else
ResultR=R;
for t∈ResultR do
{p searches BATON with t.JR find node q;
Resultsemi=GetSemiJoin(t.JR，JS，S，q，p);}
for o∈Resultsemi do
{p search BATON with o.tid to get complete tuple of S;
get the complete joined tuple tjoin;
O={tjoin∪O;}
Return(O);
Procedure GetSemiJoin(vR，attS，S， θS，p，poriginal)
Input:
vR:the value on join attribute of R;
attS: the join attribute of S;
S: a join relation;
θS: selection on S;
p: the peer performing the query；
poriginal: the peer receiving the outputs.
Output:
Returns the set of triples that value on S.attrS equals to vR.
Resultjoin={o|o=(tid，S:attrS，v)∧v=vR∧o∈Datap});
if θS applys to attrS，then
Resultsel={o|o satisfy θS∧o∈Resultjoin}
else
{ResultS=Selection(S，θS，p); //section 2．2
Resultsel={o|(t∈O′(o.tid=t.tid))∧(t′∈Result(o.tid=t′.tid))};}
Return Resultsel to poriginal;
4相關工作及比較
按建模數據的模型不同，P2P數據管理領域研究項目可以分為以下三類：
（1）Hyperion[8]、PeerDB[3]、PIER[4，5]、CON－QuerP[9]研究關系數據上的查詢。
Hyperion主要關注Peer間語義異構的解決方案，通過映射表、映射表達式和ECA規則控制Peer間的信息交換，必須由領域專家在Peer加入網絡時且查詢發起前預先建立這些對應關系組成一個邏輯的非結構化網絡。Hyperion沒有支持高效查詢處理的結構化模式索引和實例級索引。
本文采用關鍵字標注關系名和屬性名的方法與PeerDB相同，但是PeerDB建立在非結構化重疊網絡之上，利用移動代理，采用受TTL(Time－To－Live)限制的洪泛查詢策略。因此，每個Peer的負載隨網絡中的整體查詢數線性增長且不能保證在有限跳步內找到存在的數據(以及相似模式)。采用結構化重疊網絡索引模式和數據，能夠保證在有限跳步內找到存在的相似模式和數據，從而為查詢翻譯和查詢求值的效率提供理論保證。
PIER[5]中假定所有的節點都服從某個皆知的標準全局模式，將關系水平分組以關系名(PIER中稱為Namespace)和主碼屬性(PIER中稱為resourceID)作為DHT的key，通過哈希函數將元組發布到結構化重疊網絡CAN[10]中。這樣只能高效支持對散列使用的key屬性上的查詢。垂直分區關系可以高效支持關系的所有屬性上的查詢。由于哈希函數破壞了數據順序，CAN本身不能支持范圍查詢。PIER通過在CAN上應用PHT(Prefix Hash Tree)來支持范圍查詢，但是這樣只能提供近似解且效率不高。與此不同，本文通過BATON[7]高效地提供確切查詢和范圍查詢。為了支持關系數據上的復雜查詢，PIER提供了對稱哈希連接和提取—匹配連接算法，并提供了Bloom連接和半連接兩種優化策略。當連接屬性不是DHT索引屬性時，PIER需要以連接屬性作為索引屬性構造全新的臨時哈希索引。實驗表明，在具有有限帶寬的情況下，半連接優于其他連接算法。本文垂直分區關系的方法無須重構索引就可支持連接且可以自動實現對稱半連接的優化。
文獻[4]將關系元組垂直分區后，以屬性名和屬性值的q－gram作為key發布到P－Grid[11]中高效支持屬性名和屬性值上的相似性查詢。本文分區關系元組的方法與它相似，但是與實例級索引使用的索引鍵與它不同；并且它假定所有的關系中屬性名相似的屬性具有相同的含義，因此在指定查詢時不指定關系名。采用q－gram多次存儲，開銷大且不能表達屬性名不同但是含義類似的情況。以PeerDB使用的例子來說明，“Protein”被認為是與“Kinases”相似或相關的屬性，但是就q－gram而言，這兩個詞沒有任何共同之處，就會造成誤舍棄。本文使用了關鍵字充當同義辭典并用結構化重疊網絡索引模式的方式，可以通過確切匹配找到相似的屬性，避免了復雜的字符串到q－gram分解算法，節省了匹配時間。文獻[4]支持相似性連接，它實際上是自然連接的近似解，不能支持等值連接。本文可以支持等值連接和自然連接，提供準確的解。
CON－QuerP是建立在非結構化重疊網絡上的P2P關系數據管理系統。為了維護視圖，它通過使用分布式哈希表構建協調重疊網絡。其中每個節點負責所有擁有某個邏輯表達式的視圖信息。CON－QuerP將數據源也作為視圖發布到協調重疊網絡中。當節點加入CON－QuerP時，并不知道系統中已經存在的數據提供者提供的數據源模式信息。為了得到這些信息以幫助查詢的撰寫，新節點首先通過協調重疊網絡查找感興趣的數據源，然后訪問這些數據源得到具體的模式信息。此后才能進行查詢的撰寫以及查詢處理。本文雖然也用結構化重疊網絡索引模式信息，但是使用模式關鍵字作為索引鍵，索引的目的是進行系統模式翻譯而不是提供給用戶撰寫。因此檢索模式索引的時機和方式也不同。
（2）Piazza[12]既研究XML數據的查詢也關心RDF與XML數據間的映射，從而為語義Web提供支持。但是，Piazza現在的索引實現是集中式的，類似于Web上的搜索引擎，因此可擴展性和健壯性較差。
（3）Edutella[13]、GridVine[6]、RDFPeers[14]研究RDF數據的查詢。與關系數據相比，RDF數據維度固定，處理起來較為簡單。
Edutella采用了Super－Peer節點來提供全局模式，統一其客戶Peer的模式，限制了網絡的動態性。Super－Peer會成為連接到Super－Peer上客戶Peers的瓶頸(特別是為了使索引更新高效，Edutella要求Super－Peer數比Peer總數少得多)。局部指定Peer聚簇規則會造成某些Peer無Super－Peer接收而不能加入網絡；一些非常流行的模式將可能使有些Super－Peer連接大量的Peer，造成負載不平衡。GridVine和RDFPeers基于結構化重疊網絡，但其查詢能力比關系代數簡單。
與相關工作進行比較，以說明本文提出的用結構化重疊網絡構造兩級索引的策略優勢：
（1）P2P系統Peer的自治性造成了Peer模式的異構性，因此P2P系統的查詢處理必須解決異構問題。本文采用指定關鍵字充當同義辭典的方法，較創建復雜的模式映射(通常以視圖或Datalog規則的形式呈現)簡單，非計算機專業的普通用戶就可以勝任，但是這是以犧牲準確性為代價的。
（2）當從用戶處接收到查詢時，一方面用原始查詢檢索實例索引；另一方面使用模式索引對原始查詢進行翻譯。這樣，既能保證初始響應時間，也能檢索到更多的數據，從而提高了查全率。
（3）在構造模式級索引時，不是直接使用原始關系名來發布模式信息，而是使用關鍵字作為索引鍵。這樣做的好處是：①具有相同關鍵字(被認為語義相似)的關系名將分布在同一(或者相鄰的)節點上；②當單個關系不具有全部查詢屬性，但是外碼引用關系共同提供查詢所需的全部屬性時，仍能正確改寫查詢。
（4）在模式索引中沒有數據源節點的信息，它僅僅包含網絡中可用模式列表，由數據源采用軟狀態的方式定期將自己的模式發布到模式索引中。因此不必檢測數據源是否連接，數據源離開時也不必主動通知模式索引，簡化了索引的維護。
Peer數據管理系統通常需要同時達成如表1所示的目標。
表1Peer數據管理
表1中：
①支持語義異構。語義異構是Peer自治的結果，各Peer用自己的模式組織和呈現數據。為了互操作，需要適應P2P動態即興環境的解決方案。
②查詢表達力。可以從其支持的被查詢的數據類型和查詢算子類型體現。關系數據的普遍性使得支持關系數據上的關系運算是具有良好查詢表達力的標志。
③可擴展性。查詢處理的性能和服務質量不因網絡規模擴大而顯著下降。查詢路由跳步數與節點數成對數關系被認為是具有良好可擴展性的標志。
④支持多屬性查詢而無須針對特定屬性重新構造索引。
通過比較發現，本文提出的策略在各種研究目標之間達到了較優的平衡，最接近理想的研究目標。
5結束語
本文借鑒P2P數據管理的語義調解和查詢處理領域取得的一些研究成果，通過垂直分區元組和給模式元素加注同義詞，采用高效支持范圍查詢的結構化重疊網絡索引模式和數據，提出基于兩級索引支持多屬性復雜查詢的算法。通過比較分析，該方法最接近P2P數據管理的理想目標。目前，正在對該算法進行定量的實驗分析。以后將研究在上述索引策略和分區方法的基礎上聚集查詢等更復雜查詢的處理方法。
參考文獻：
[1]QIAN Weining， XU Linhao， ZHOU Shuigeng， et al. CoCache: query processing based on collaborative caching in P2P systems: proc.ofDASFAA2005[C]. Berlin， Heidelberg: Springer－Verlag， 2005:498－510.
[2]HARREN M， HELLERSTEIN J M， HUEBSCH R， et al. Complex queries in DHT－based peer－to－peer networks: proc.of the 1st International Workshop on Peer－to－Peer Systems(IPTPS’02)[C]. London， UK: Springer－Verlag， 2002:242－259.
[3]NG W S， QOI B C， TAN K L， et al. PeerDB: a P2P－based system for distributed data sharing: proc.of the 19th ICDE[C]. Bangalore: IEEE Computer Society Press， 2003:633－644.
[4]KARNSTEDT M， SATTLER K U， HAUSWIRTH M， et al. Similarity queries on structured data in structured overlays: proc.of the 2nd IEEE International Workshop on Networking Meets Databases[C]. Atlanta， GA: IEEE Computer Society， 2006:32.
[5]HUEBSCH R， CHUN B， HELLERSTEIN J M， et al. The Architecture of PIER:an internet－scale query processor:proc.of the 2005 Conference on Innovative Data Systems Research[C]. Asilomar:VLDB， 2005:28－43.
[6]ABERER K， CUDRE－MAUROUX P， HAUSWIRTH M， et al. GridVine: building internet－scale semantic overlay networks: proc.ofthe 3rd International Semantic Web Conference[C]. London: Springer－Verlag， 2004:107－121.
[7]JAGADISH H V， QOI B C， VU Q H. BATON: a balanced tree structure for peer－to－peer networks: proc.of the 31st VLDB Con－ference[C]. New York:ACM， 2005:661－672.
[8]KEMENTSIETSIDIS A， ARENAS M. Data sharing through query translation in autonomous sources: proc.of the Thirtieth International Conference on Very Large Data Bases[C]. San Fransisco: Morgan Kaufmann， 2004:468－479.
[9]錢衛寧.對等計算系統中的數據管理[D].上海:復旦大學，2003:1－142.
[10]RATNASAMY S， FRANCIS P， HANDLEY M， et al. A scalable content－addressable network:proc.of ACM SIGCOMM’01[C].San Diego， CA: ACM， 2001:161－172.
[11]ABERER K， CUDRE－MAUROUX P， DATTA A， et al. P－Grid: a self－organizing structured P2P system[J]. ACM SIGMOD Record， 2003，32(3):29－33.
[12]HALEVY A Y， IVES Z G， MADHAVAN J， et al. The piazza peer data management system[J]. IEEE Transactions on Knowledge and Data Engineering， 2004，17(7):787－798.
[13]NEJDL W， SIBERSKI W， SINTEK M. Design issues and challenges for RDF－ and schema－based peer－to－peer systems[J]. ACM SIGMOD Record， 2003，32(3):41－46.
[14]CAI M， FRANK M. RDFPeers: a scalable distributed RDF repository based on a structured peer－to－peer network: proc.of the 13th International World Wide Web Conference[C]. New York:Sheridan Prin－ting， 2004:650－657.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
