Xml文檔的聚類方法和系統的製作方法

2023-07-25 09:02:56 2

專利名稱：Xml文檔的聚類方法和系統的製作方法
技術領域：
本發明通常涉及XML文檔的聚類，尤其涉及以單遍工作量負荷完成的XML文檔的聚類。
背景技術：
下面提供的一系列參考文獻與本發明相接近；其中的各個參考文獻以括弧中的縮寫(即[FK99]，[TN91]，等等...)的方式來引用。
當前的資料庫或數據倉庫系統使用兩個主要的方案來存儲XML文檔。第一種方案將XML文檔映射到關係表，關係表中的每行表示文檔的(抽象)XML樹中的一個邊[FK99]。通過現有的關係操作符來實現對存儲文檔的XML處理。第二種方案，即原生XML存儲(Native XML Storage)將文檔視為XML樹。它將XML樹劃分成不同記錄，這些記錄包含不相交連接的子樹[KM00]。接著以未解析的文本形式，或使用某種內部表示，在盤頁面中存儲這些記錄。
對於支持用於通過連結(指針)遍歷在數據項之間進行導航的操作符的資料庫系統，相關數據項的聚類在物理布置數據方面是有益的。這裡，如果2個節點通過連結相連，則它們是相關的，並且檢查它們中的一個很可能不久導致檢查另一個。例如，已經表明，數據聚類對於例如IBM的IMS的層次資料庫[Sch77]，及對於面向對象的資料庫(OODB)[TN91，TN92，GKKM93]是有效的。
通常使用例如XSLT、XPath或XQuery的查詢語言處理XML文檔[WC3]。這些語言使用XPath導航操作符遍歷抽象XML樹的路徑。在原生XML存儲系統中，這導致在類似於層次或面向對象資料庫中的記錄的所存儲的XML記錄上的導航。實際上，通常通過路徑索引輔助這種遍歷，這些路徑索引減少了所存儲記錄上的路徑導航的數量。然而，由於XML查詢模式通常是比較複雜的，並且維護多個路徑索引以覆蓋整個XML文檔的代價也是昂貴的，因此路徑索引不能完全消除這種路徑遍歷。此外，許多處理模式使用延遲的訪問，並且由於數據可能已經更新，而會需要附加的遍歷以便重新生效。最後，一般物理布局模式能夠將XML節點分散在許多記錄上。對於這種物理布局，類似預取或緩衝的常規I/O優化技術對於複雜XML查詢可能是無效的。因此，將相關XML節點聚集在一起並且將它們存儲在相同盤頁面中，尤其是對於較大的XML文檔，是有益的。由於盤頁面具有有限的容量，所以不是所有的相關XML節點都能夠容納在單個盤頁面中。因此，需要決定如何向盤頁面分配相關XML節點。OODB中對象的聚類和相關XML節點的聚類之間的關鍵差別在於，在OODB中可根據其類規格事先得知對象的大小，而對於XML文檔，在沒有XML模式的情況下，是在對其進行分析之後才知道節點大小。即使在XML模式可用時，也僅在運行時刻才知道文本節點的大小。
將相關XML節點分配到盤頁面的問題可被視作樹分區問題。要分區的樹是聚類樹，即增加有節點和邊權重的XML樹。概括地講，邊權重模擬XML導航行為(邊權重越高，則意味著相連的XML節點更強烈地″相關″)。節點權重是XML節點的(文本)大小。問題是將聚類樹的節點集合劃分為節點不相交子集(稱作聚類)，使得一個聚類導出一個相連接的子樹，每個聚類均適合一個盤頁面，並且聚類內部邊的總權重(稱作分區的值)最大。反之，聚類間邊的總權重(分區的代價)最小。直觀上，分區的值越高，則意味著盤訪問越少。
對於樹分區問題的一個廣為接受的方案是Lukes的基於動態規劃的樹分區方法[Luk74]。這一方法以自底向上的方式對樹進行操作，並且使用將逐漸增大的子樹分割成分區集合的迭代過程。每個分區是一組非不相交聚類，每個聚類滿足總權重限制(即盤頁面大小)。對於每個子樹，並且對於每個可行的聚類權重，Lukes的方法尋找具有最大值的分區。當被分區的子樹是整個樹本身時，該方法完成。最終獲得的分區是整個樹的具有最大值的分區。然而，Lukes的方法需要過多的存儲器和運行時間，這是由於動態規劃的結果。於是，需要改進Lukes的方法。

發明內容
根據本發明的至少一個當前優選的實施例，概括地考慮了一種用於以單遍工作負荷完成的XML文檔聚類的系統和方法。
概括地講，本發明的一個方面提供了一種用於對XML文檔進行聚類的系統，該系統包括用於按節點分析XML文檔的裝置；用於初始化至少一個所分析的節點的裝置；用於對至少一個所分析的節點進行分區的裝置；和用於處理至少一個所分析的節點的裝置。
本發明的另一個方面提供了一種用於單遍地對XML文檔進行聚類的系統，該系統包括用於按節點分析XML文檔的裝置；用於確定至少一個所分析的節點的XPath工作遍歷的裝置；用於對至少一個所分析的節點進行聚類的裝置；和用於向頁面分配至少一個聚類的裝置。
本發明的另一個方面提供了一種用於對XML文檔進行聚類的方法，該方法包括步驟按節點分析XML文檔；初始化至少一個所分析的節點；對至少一個所分析的節點進行分區；和處理至少一個所分析的節點。
此外，本發明的另一個方面提供了一種機器可讀的程序存儲裝置，其有形地體現一種指令程序，該程序可被機器執行以實現用於對XML文檔進行聚類的方法步驟，所述方法包括步驟按節點分析XML文檔；初始化至少一個所分析的節點；對至少一個所分析的節點進行分區；和處理至少一個所分析的節點。
為更好地理解本發明及其它和進一步的特徵和優點，參考以下結合附圖進行的說明，在所附權利要求中指出了本發明的範圍。


圖1示出了XML樹和相應的聚類樹；圖2示出了根據本發明的通用XML聚類系統的方框圖；
圖3以圖形方式示出了本發明的接近線性的特性；圖4以圖形方式針對各種單個的查詢工作負荷示出了聚類的缺頁情況；圖5以圖形方式針對各種組合的查詢工作負荷示出了聚類的缺頁情況；圖6是本發明的方法的流程圖；圖7是根據本發明的圖6所示的初始化單元的操作的流程圖；圖8是根據本發明的圖6所示的分區單元的流程圖；以及圖9是根據本發明的圖6所示的後處理單元的流程圖。
具體實施例方式
本發明的一個實施例是樹分區方法XC，它用於對較大的靜態XML文檔進行聚類。在本發明的另一個實施例中，XC優選被集成在具有SAX分析器和邊權重指派器(使用顯式權重或根據公布的工作負荷說明導出權重)的系統中，其中工作負荷是固定的。該系統在操作時產生包含XML文檔的完成節點的聚類樹。如下所述，XC使用各種僅保留在將來能夠有用的那些聚類和分區的技術，並且儘快釋放所有其餘的數據結構。
本公開現在討論XC的關鍵特徵。為了進行討論，將使用圖1(a)中說明的簡單XML樹。圖1(b)示出了相應的聚類樹(具有節點和邊權重)。聚類樹是增加有均為整數的節點和邊權重的XML樹。節點權重是XML節點的(文本)大小，而邊權重模擬將節點放置到相同聚類中的重要性。
本發明的方法優選地用於將介質劃分為大規模的XML樹(兆字節到千兆字節)。對於大型XML樹，多數應用只能在存儲器中保存部分的XML樹。此外，通常按照文檔順序單遍地分析XML文檔，其中每個XML數據節點只被掃描一次。這對XC強制實行隱含的調用順序。不同於Lukes的方法，XC按照自底向上、自左到右的順序處理樹節點。例如，對於圖1(a)中示出的樹，本發明的方法按照以下節點順序處理節點3、2、5、4、8、7、10、9、等等。在執行期間的任意時刻，XC僅在存儲器中保存XML樹的一個片段。該片段是迄今已掃描的XML文檔的部分的子樹。XC沒有關於文檔的其餘尚未掃描的部分的信息。所以，在每一步驟，XC單純根據從已掃描的XML節點獲得的信息做出決定。
類似於Lukes的方法，XC也對聚類樹進行操作。一旦XC完全處理了聚類樹的一個子樹，該子樹即被稱作已處理子樹(並且其根被稱作已處理節點)。XC為一個子樹計算一組分區，其中每個分區是一組不同的聚類。按照聚類的成員節點的權重的總和來計算聚類的權重。包含被分區子樹的根的聚類被稱作中樞聚類，並且其權重被指定為該分區的權重。考慮圖1(a)的樣本XML樹1.節點3(具有數據12345)是具有完全掃描子樹(包含其本身)的第一個節點。XC現在調用Lukes的方法的葉處理步驟，並且初始化用於節點3(葉)的結構。一旦經過處理，以節點3為根的子樹被轉換成只包含一個節點(節點3)的已處理子樹及其相關分區，該分區包含其權重與節點3的權重相等的單個聚類(3)。
2.節點2是具有完全掃描子樹的下一節點(包含其本身和節點3)。XC現在對該子樹的根節點2執行Lukes的方法的內部結點處理步驟。類似於Lukes的方法，內部循環在子節點(只有一個，即節點3)上進行迭代，並且產生中間分區。一旦經過處理，以節點2為根的子樹被轉換成只包含一個節點(節點2)的已處理子樹及其相關分區。應當理解，本發明中是根據一般已知的方法，即合併和連接的方法創建分區。對於通過合併和連接創建分區的一般討論可參見[Luk74]。
本公開現在討論使用權重區間的動態規劃。在處理具有節點權重w≥1的節點時，Lukes的方法檢查其權重為從w到權重邊界W的所有可能分區。這導致O(n W)空間複雜度和O(n W2)時間複雜度。這對於其中n的值可能上百萬(XML節點)並且W可能上千(字節)的較大XML文件是禁止的。為解決此問題，本發明的方法將(1，W)的權重範圍劃分成大小相等的權重區間，並且對於每個權重區間，僅使一個分區與之相關。由應用使用塊大小參數來指定權重區間的數量。塊大小的值(表示為C)可以從1變化到W，並且是W的約數。在所考慮的其權重落在該區間內的分區中，每個權重區間的相關分區具有最大值。所以，對於XC，在Lukes的方法[Luk74]的內部結點處理之後，最多有Wc＝W/C個與該節點相關的中間分區。類似地，內部循環在從1到Wc的權重區間上進行迭代。這些修改將空間複雜度降低到O(n Wc)，並且將時間複雜度降低到O(n Wc2)。這種權重區間逼近技術僅用於將中間分區放置到適當區間中。對是否合併聚類的判定仍然是根據實際的聚類權重(而不是區間)。
例如，當對包含節點2和3的聚類子樹調用Lukes的方法時，創建了2個中間分區。通過連接包含節點2和3的聚類而創建具有權重4和值0的第一分區p42。通過合併包含節點2和3的聚類而創建具有權重9和值20的分區p92。如果W＝10並且塊大小＝10，則Wc＝1並且p42和p92落在單個權重區間內，所以只保留較高值p92。如果W＝10並且塊大小＝5，則Wc＝2，並且保留這兩個分區。如在Lukes的方法中那樣，一旦子樹被處理，則可以丟棄該子樹根的所有子節點(並且釋放存儲器)。
檢查邊界情況C＝1和C＝W是有益的。當塊大小＝1時，本發明的方法完全如Lukes的方法那樣進行操作；它也尋找一個最優分區。當塊大小＝W時，每個節點只產生一個中間分區。換言之，XC按簡單的「貪心」算法進行操作。如果可能，它簡單地合併其當前分區的中樞聚類和子節點的中樞聚類，添加其他的子聚類，從而產生新的(和更加有價值的分區)。否則，它簡單地合併該節點和子節點的當前分區。
本公開現在討論就緒聚類(ready clusters)的識別。除權重區間之外，XC也使用其它策略來限制其存儲器耗用。第一，設計由XC用來表示節點、聚類和分區的基本數據結構，使得一旦一段邏輯數據不再需要，便能夠收回其相應存儲器。第二，XC儘快從存儲器中移除XML文本數據。Lukes的方法保留可能的結果聚類，直到計算出最終的結果分區。聚類的每個XML節點均承載有相應的XML文本。這導致在存儲器中保存整個XML文檔等等，直至計算出最終分區。這是完全不切實際的。本發明的方法通過主動檢測就緒聚類來解決這個問題。
如果滿足以下條件，則與已處理節點x相關的分區中的聚類是就緒的(1)它不包含節點x，因此不能參與任何將來的聚類合併操作，以及(2)它是與節點x相關的每個中間分區的成員，所以將是最終結果分區的成員。一旦處理了以節點x為根的子樹，則就能夠檢測到就緒聚類。接著就緒聚類能夠被從中間分區中移除並被傳送(帶有其XML數據)到頁面分配子系統(參見圖2)。一旦頁面分配子系統向某一頁面分配了一個就緒聚類(即其XML數據)，則該聚類中包含的XML節點能夠和其XML數據一起被刪除。這可以導致存儲器利用率的顯著降低，並且隨之改善運行時間。例如，在沒有識別就緒聚類的情況下對580KB的XML文檔進行聚類會使用2.43MB的存儲器，並且花費170秒的時間。當識別出就緒聚類時，相同文檔可以在1.2秒內被聚類，並且只需要43KB的存儲器。這突顯出就緒聚類識別的關鍵作用。
本公開現在討論處理存儲器限制。雖然本發明使用了降低技術，然而存儲器耗用仍然非常巨大，尤其是對於較大的XML文檔和較小的塊大小值。較大的存儲器耗用通常增加(虛擬存儲器)缺頁情況的數量，因此使性能降級。錯誤的頁面調度特性會使任何方法均不適用於在嚴格時間限制下操作的應用，例如實時數據流應用。如果僅當存在大量可用存儲器時其才能夠在某一處運行，則限制了方法的實用性。本發明的方法XC被設計成在指定時間和存儲器限制下操作的單遍(流數據)XML應用。塊大小參數控制迭代次數，並且還影響存儲器耗用。而且，XC應當能夠在明確指定的存儲器耗用限制下進行操作。
現在描述用於使本發明的基本方法能夠有效地遵從存儲器限制進行工作的技術。這一技術將就緒聚類的思想擴展到就緒子分區。就緒聚類是將成為最終計算的分區的一部分的聚類。就緒子分區是與(聚類樹的)已經處理的子樹的根相關的最高值分區，該子樹是針對整個聚類樹計算的最優近似分區的子集。如果能夠識別就緒子分區，則子分區的聚類能夠被傳遞到頁面分配子系統，並且能夠立即收回相關數據結構，例如XML節點、其文本和聚類的存儲器。分區的消除也降低了將來動態規劃考慮的選項數量；進一步降低了存儲器使用。
通常，在已處理節點x處識別就緒子分區(充分條件是在與x相關的所有分區中，中樞聚類具有權重W)是很難的。而是，當接近存儲器限制時，當前優選的方法是簡單地將某些子分區聲明為就緒的(如下所述)。這一方案急劇降低了存儲器耗用。然而這一方案具有一個缺點它影響了準確性，因為在就緒子分區中可能有某些聚類會在將來的聚類合併操作中使用(這會增加最終分區的值)。因此，重要的是選擇就緒分區，使得最終結果質量(即價值)不受顯著的影響。
一旦處理了一子樹，則保留其中間分區，直到其父節點被處理。例如，對於圖1(a)中出現的XML樹，保留節點7、9和11的中間分區，直到處理了以節點6為根的子樹。根據本發明，維護當前多達k個與已處理節點(即其父節點尚未處理的已處理子樹的根)相關的最高值分區的長度受限的(參數k，例如k＝8)列表HL。這個分區列表僅包含最優分區，使得最優分區的值的總和始終最大。給定存儲器限制M，本發明的方法計算用於管理存儲器使用的高和低″水位標誌″(低＜高＜M)。當存儲器使用超過高水位標誌時，觸發校正動作；一旦存儲器使用到達低水位標誌，則恢復正常操作。
當超過高水位標誌時，本發明的方法XC從HL中選擇具有最高值的分區P。XC接著將這個分區標記為就緒子分區，將其聚類傳遞到頁面分配子系統，並且接著回收相關數據結構的存儲器。P還會形成最終結果分區的子集。XC接著移除P與其相關的XML節點vP(即已處理子樹的根)，並且丟棄vP到其父節點的連結。這個從HL中消除掉最高值分區的過程繼續執行，直到存儲器使用落到低水位標誌之下，或最優分區列表為空。如果存儲器使用違反規定的情況持續存在並且最優分區列表為空，則在上述過程中一旦處理了任何子樹，其最優分區立即被標記為就緒並且被消除掉。
現在參照圖1(a)討論在存儲器使用違反規定期間，本發明的方法的特性。假定在處理文本節點15(INRIA)的同時，存儲器使用越過高水位標誌。這時，已經處理了以節點2、4和6為根的3個子樹，並且它們的最高值分區被存儲在HL中。現在考慮相應的聚類樹圖1(b)。假定在HL中節點6的最高值分區具有最高值，其後跟隨的是節點2的最高值分區，接著是節點4的最高值分區。在這種情況下，(與節點6相關的)第一最高值分區被選擇為就緒分區，節點6被刪除，並且不再是節點1的子節點。如果存儲器使用違反規定的情況持續存在，則(與節點2相關的)最高值分區是下一個要被聲明為就緒的分區。假定現在存儲器使用落在低水位標誌之下，則XC恢復正常操作(也就是說直到下一次越過高水位標誌為止，保留已處理子樹的分區，並且在處理期間如在Lukes的方法中那樣使用這些分區)。
試探策略，即將HL中具有最高值的分區P標記為就緒子分區的策略嘗試使早先的(與vP相關的)分區消除導致的可能價值損失最小。就緒子分區的聲明是在不了解尚待掃描的XML節點的結構和大小的情況下進行的。始終選擇最高值分區作為就緒分區的試探算法是一種解決這種不確定性的途徑。
本公開現在討論根據本發明的XML聚類系統。圖2說明了XML聚類系統200的體系結構，XML聚類系統200掃描XML文檔，將其劃分為聚類，並且將這些聚類分配到(盤)頁面，而所有這些操作均單遍完成。它包括3個不同的子系統邊權重指派器220、樹分區240和盤頁面分配260。附圖中子系統之間的邊(210、230、250和270)表示過程調用。邊權重指派器使用的應用工作負荷信息通常能夠具有不同的形式(例如，統計數據)。
根據本發明，根據這種在其中優選地將XC用作樹分區子系統的體系結構來實現XML聚類系統XCS。優選地，使用C++版本的ApacheXerces SAX分析器(參見http//xml.apache.org/xerces2-j/index.html)，雖然可以使用任何適當的分析器。(考慮到以流方式向SAX分析器饋送XML文檔的情境。)XML聚類系統是其中通過不同SAX事件調用不同功能部件的單個SAX應用。該分析器對每個XML節點僅進行一次掃描，並且創建該節點的存儲器內數據結構表示。這種存儲器內數據結構存儲該XML節點的文本大小，並且充當聚類樹的節點。引導到該節點的邊接著被傳遞到邊權重指派器。
邊權重指派器220使用應用工作負荷信息為聚類樹邊指派權重。在XCS的邊權重指派器中，工作負荷信息包括XPath查詢的列表。也可以提供特定XPath查詢的例如頻率或重要性的附加信息。工作負荷信息也可以包含實際查詢的近似；例如，一個參數化的查詢可以利用一個訪問所有實例的查詢來近似。
對於工作負荷中的XPath查詢，邊權重指派器220優選地使用初級(naive)流式XPath處理器的用於模擬執行的模擬器(這種模擬器能夠被任何流式XPath處理器替代)。當前，該模擬器支持以下類型的XPath查詢1.從文檔根開始的簡單路徑查詢；2.XPath派生或自身(″//″)查詢；3.具有位置和路徑預測的查詢。
另外，該模擬器模擬對查詢的子路徑使用路徑索引的執行。通過適當SAX事件調用模擬器。該模擬器識別會被初級XPath處理器在其實際執行期間遍歷的XML節點。為此，該模擬器使用確定性自動機，該自動機在遍歷XML連結的同時根據目標節點內容在狀態之間進行切換。根據(1)XPath查詢的相對重要性/頻率，(2)XPath查詢中使用的軸和(3)執行計劃(即有或者沒有使用路徑索引)，為相應的聚類樹邊指派權重增量。給予一個聚類樹邊的總權重是由於每個工作負荷查詢而導致的權重增量的總和。
直觀上，所指派的權重模擬初級XPath處理器(在時間上)連續遍歷該邊所連接的節點以及使用該邊的事實。邊權重越高，則在所連接的節點之間的遍歷親合性便越高。這種親合性源於經常被遍歷，並且/或者經常被″重要的″工作負荷查詢遍歷。能夠擴展邊權重指派器220以俘獲更加複雜的工作負荷，例如涉及路徑聯接、或者複雜的預測、XQuery查詢和XSL-T模板的XPath表達的特性。不管XML工作負荷和執行計劃的類型(即索引或非索引的)如何，所有XML查詢均最終被轉換成在抽象XML樹的邊上的遍歷。邊權重指派器220能夠使用高級查詢的邊遍歷信息和頻率/重要性來指派適當的邊權重。
現在參照附圖1示出的XML樹，以及包括3個XPath查詢及其相對權重的應用工作負荷說明邊權重指派器220的執行。
1./bib/book/price202./bib/book/author/affiliation503./bib/book/author[2]/last}30該查詢工作負荷遍歷的所有的邊會被指派反映實際執行的邊權重。
假定在工作負荷XPath查詢的實際執行期間執行的遍歷會在沒有使用任何路徑索引的情況下執行，則這些XPath查詢的相對權重被用於計算查詢對邊權重的影響。例如，被第一工作負荷查詢遍歷的邊被指派20的權重增量，被第二查詢遍歷的邊被指派50的權重增量，並且被第三查詢遍歷的邊被指派30的權重增量。如果一個邊被不止一個工作負荷查詢所遍歷，則其邊權重表示累積的權重。例如，連接節點bib和book的邊(0，1)被所有3個XPath查詢遍歷。因此它會被指派累積的權重100。類似地，連接第二個author節點和book節點的邊(1，13)被第二和第三XPath查詢遍歷。因此這個邊會被指派權重80。最後，邊(1，20)僅被一個工作負荷查詢，即/bib/book/price遍歷，並且被指派權重20。
現在考慮當路徑索引被用於解決某些工作負荷查詢時的情況。例如，考慮關於路徑/bib/book/author的索引。這裡，連接節點bib和book的2個邊被指派權重0(被跳過)。連接節點bib和book的邊(0，1)現在只會被第一查詢遍歷，並且被指派權重20。
一旦邊權重指派器220指派了邊權重，則由樹分區子系統240(在這種情況下為XC)處理聚類樹存儲器駐留部分。針對endElement或characterSAX事件，或者在掃描XML屬性結束時，調用樹分區子系統。於是，XML聚類系統遵循自底向上、自左到右的調用順序。樹分區子系統始終對具有作為其根、剛好完成的XML元素或屬性的聚類子樹(高度為1)進行操作。根據塊大小，XC首先計算子樹的不同分區，並且接著檢測這些分區是否包含任何就緒聚類。就緒聚類被從所計算的分區中移除並且被傳送到頁面分配子系統260。無論怎樣，都為將來本發明的方法的調用而保留所產生的分區。
為了說明樹分區子系統240的調用，考慮圖1提供的XML樹。首先對節點3調用樹分區子系統240，接著對節點2調用樹分區子系統240。一旦對以節點2為根的子樹進行了分區，則釋放節點3的存儲器內表示。保留針對以2為根的子樹計算的分區，直到節點2作為節點1的子節點再次用在分區過程中。繼續執行這個對以x為根的子樹進行分區，釋放x的子節點，檢測就緒聚類和保留分區的過程，直到x為根並且整個樹得到分區為止。
頁面分配子系統260向頁面分配就緒聚類。一旦檢測到就緒聚類，便調用該系統。優選地，頁面分配子系統260按照就緒聚類權重的降序維護就緒聚類的排序列表。優選地，頁面分配子系統260使用單純根據當前可用就緒聚類的權重進行頁面分配決定的在線裝箱算法。其工作如下1.一旦當前存儲的就緒聚類的總大小超過限制(參數)，則選擇最重的聚類並且將其分配給頁面。
2.使用其他的較小聚類，按照權重的降序嘗試填充這個頁面，直到達到頁面大小限制或所有待決聚類均被檢查過。
3.填充後的頁面被發送到盤，收回涉及其已分配的聚類的數據結構的存儲器。
重複這個過程，直到所有就緒聚類均被映射到盤頁面。注意，一旦完成了文檔掃描，便啟動頁面分配子系統以便將所有的其餘在存儲器駐留的就緒聚類映射到盤頁面。
本公開現在討論使用本發明獲得的實驗結果。華盛頓大學XML數據倉庫提供的若干XML文檔(www.cs.washington.edu/research/xmldatasets/)被用於評估本發明的方法。接著對比使用DFS(深度優先存儲)的DCS(深度優先聚類系統)，評估根據本發明使用本方法的系統。DFS是以深度優先方式分析XML文檔的初級聚類算法。參見Tian等人「TheDesign and Performance Evaluation of Alternative XML StorageStrategies(可選XML存儲策略的設計和性能評估)」，Association forComputing Machinery SIGMOD Record(計算機協會SIGMOD記錄)，31(1)(2002年3月)，以得到有關DFS的一般性討論。它以「貪心」方式產生XML節點，其中一旦完成這些XML節點的掃描，便將它們準備好存儲到盤頁面中。DFS完全忽略邊權重。DFS的主要優點是將其處理完成在時間上接近的XML節點放在一起。在兩種情況下，XPath查詢執行期間缺頁情況的數量被用作性能的主要度量。
本發明的方法和Lukes的方法之間的關鍵差別在於，本發明對權重區間而不是對整個權重範圍使用動態規劃。根據本發明，通過塊大小參數(其決定動態規劃區間的數量)來確定權重區間。表1說明了塊大小參數的影響。在這個試驗中，以權重邊界W＝4KB對大小為1.97MB並且包含154855個XML節點的XML文件mondial.xml進行聚類。聚類樹邊被隨機指派權重。如表1所示，隨著塊大小的降低，最終解的值增加。隨著塊大小的降低，所使用(用於動態規劃)的權重區間的數量增加，並且XC變得更加準確。同時，這導致存儲器使用的增加和運行時間的增加。當塊大小為1時，XC的行為類似於確切的Lukes的方法，並且所需的運行時間超過2小時(應用在2小時之後終止)。
表1使用mondial.xml對權重區間的動態規劃的效果

對於4096和256的塊大小，解值之間的差異不顯著。然而應當注意，運行時間從32.5秒增加到了299.9秒。這表明對每個已處理節點(意味著4096個)保留單個分區的策略，即保留具有最高值的分區的策略在實踐中表現良好。如結果所示，對於塊大小1的XC(同等地，Lukes的方法)展現出不切實際的存儲器和運行時間需求；對於較大的塊大小，XC獲得具有合理存儲器和運行時間使用的良好解。
表2使用mondial.xml評估存儲器受限的執行

表2提供了在改變指定的存儲器使用限制的情況下，XC的特性。重用先前試驗的實驗設置(相同文檔，相同權重邊界)，來評估XC的存儲器受限的特性。首先使用4096的塊大小並且沒有任何存儲器限制的情況下進行該試驗。接著以較小的存儲器限制(可用存儲器量從1MB到30KB)重複該試驗。結果表明，即使在極端的存儲器限制的情況下，XC仍然表現良好。此外，隨著可用存儲器數量的降低，XC性能降級適度(2種極端情況的結果分區的值與最優近似解僅相差6％)。對於嚴格的存儲器限制，執行時間從32.5秒降低到9.049秒。這兩個試驗表明，在使用較大的塊大小和較低的存儲器限制時，迅速得到良好的解是可能的。
還度量識別就緒聚類對結果質量的影響。如上所述，當沒有識別就緒聚類時，進行聚類使用大量存儲器，並且需要明顯更多的執行時間。在沒有識別就緒聚類的情況下對mondial.xml進行聚類。由於預計的存儲器使用量相當大，強制一200KB的存儲器限制。在進行就緒聚類識別並按照相同存儲器限制的情況下，重新進行該試驗。當沒有使用就緒聚類識別時，最終聚類的值降低了20％。當就緒聚類沒有被識別時，XC的存儲器消耗相當迅速地達到存儲器限制，並且在達到違反存儲器的規定之前，僅較小的子樹得到了處理。因此，只有具有較小值的聚類被傳送到頁面分配子系統；降低了最終結果的值。
圖3示出了當XML文件的大小增加時(在這種情況下，這意味著輸入XML節點的數量也增加)，XC的特性。對於這個試驗，XMark XML文檔產生工具包[SWK+01]被用於產生各種大小(26KB到116MB)的XMark文檔。根據所連接的節點的類型來指派邊權重。元素-元素邊被指派權重3，元素-屬性邊被指派權重5，元素-文本邊被指派權重9。使用W＝4KB的權重邊界和4KB與1KB的塊大小對每個XMark文檔進行聚類。為了清楚起見，圖3針對從1MB變化到110MB大小的XMark文檔示出了運行時間。如圖3所示，對於該大小的文件，本發明的方法的運行時間幾乎是線性的。
表3DFS和XC的值比較


下面將XC的效率與DFS，即另一樹分區方法的效率相比較。表3提供了使用XC和DFS對6個不同XML文檔進行聚類的結果。以和圖3的試驗相同的方式，根據所連接的節點類型指派邊權重。應當注意，由於沒有區分工作負荷的信息，這一配置對XC有偏差。使用4KB的權重邊界，並且在4KB的塊大小和無限的存儲器情形下執行XC。如表3所示，對於所有文檔，XC產生更好的聚類。然而在許多情況下，XC所需的時間比DFS所使用的時間要多。即使在最有利的配置中(權重邊界等於塊大小)，XC比DFS完成更多的工作並且使用更多的存儲器。這導致XC要慢於DFS。
表4具有基於工作負荷的邊權重的分區(XML文檔-mondial.xml)

前面的試驗使用隨機權重。當已知預計查詢工作負荷時，隨機指派的均勻性不再保持。於是根據基於工作負荷的邊權重指派來獲得聚類結果。使用以下有關mondial.xml的單個XPath查詢/mondial/country/province/city。由初級XPath處理器執行這個查詢。在此執行期間將會被遍歷的XML樹的邊被指派權重100。接著，由使用各種塊大小的DFS和XC對該文檔進行分區。結果如表4所示。在分區值方面可以看出XC明顯優於DFS。實際上，希望這種″偏斜″邊權重指派是普遍情況。
本公開現在討論對本發明的聚類系統的評估，包含對於較大工作負荷的使用。雖然前面的試驗說明XC可用於以合理的空間和時間產生高值分區的聚類算法，但是現在考察所得到的聚類對於各種應用的有效性。為此，測試所得到的頁面內容如何影響查詢處理。在上述原型聚類系統的情境中執行測試。使用該系統的兩個實施例對XML文檔進行分區第一個實施例，XCS，使用XC作為樹分區組件，而第二個實施例，D，使用DFS進行樹分區。
表5評估在線裝箱方法

要評估的本發明的XML聚類系統的第一個部件是頁面指派部件260。表5比較了當使用XCS和DCS進行聚類時存儲6個XML文檔所需的盤頁面的數量，其中一旦完成節點的掃描，XCS和DCS便將XML節點存儲到頁面中。DCS在存儲器中保留多達2個未完成的頁面，並且使用「貪心」策略填充這些頁面(用已完成的XML節點填充)。這一「貪心」策略僅使用XML節點大小以使盤利用率最大。XCS使用如上所述的在線裝箱方法存儲就緒聚類。表5示出了由XCS產生的就緒聚類的數量和相應的頁面數量。如表5所示，DFS(DCS中)產生略優於XC的盤頁面利用率(5％左右)。其一個原因是XC趨向於比DFS存儲更大的數據″塊″。這引起分段，從而導致略微降低了頁面利用率。
現在考察聚類如何影響XML查詢執行的性能。為此，考慮以下針對mondial.xml的查詢工作負荷，其包括3個XPath查詢(Q1)/mondial/country/province/city(Q2)/mondial/country/enthicgroups(Q3)/mondial/country/province/city/name每個查詢被指派相同的權重(100)。分別使用有關/mondial/country和/mondial/country/province的路徑索引執行查詢Q2和Q3(即只有從被索引節點遍歷的邊才被指派非零邊權重)。使用該指定工作負荷產生mondial.xml的XC聚類(XC)。根據這一工作負荷，XCS的邊權重指派器在掃描文檔的同時指派適當的權重。頁面分配子系統260使用裝箱試探算法將就緒聚類250映射到頁面270。3個其它聚類XCi分別基於3個工作負荷，其每個工作負荷包括單個查詢Qi，1≤i≤3。在使用XC的同時，還使用4KB的權重邊界和4KB的塊大小。最後，使用以相同權重邊界產生聚類DFS的較簡單DFS算法(DCS中)，對文檔進行分區。
在3個不同頁面調度情境下針對不同布局(XC，XCi和DFS)模擬初級XPath處理器對每個查詢的執行，並且度量缺頁情況。針對該組合的查詢工作負荷在以下兩種模式中重複該試驗(1)串行這一情境按順序(即Q2Q1Q3)模擬這3個查詢的執行，和(2)並行這一情境以並行方式模擬這3個查詢的執行。針對2個布局XC和DFS評估該組合的查詢工作負荷。
對於這些試驗，產生在執行XPath查詢的同時遍歷的XML節點的跟蹤軌跡。這些軌跡和針對不同聚類的頁面布局一起用於評估頁面調度特性。修改2個重要參數以改變頁面調度情境。首先，緩衝區大小是存儲器中能夠保存的盤頁面的數量。其次，預取量是在單次盤訪問(從所尋址的頁面開始，包含連續頁面)中獲取的連續盤頁面的數量。第一種情境使用1個頁面、其中具有1個預取頁面的緩衝區大小(表示為1/1)；第二種情境考慮無限的緩衝區大小(即在執行期間，獲取的頁面均保留在存儲器中)和1個預取頁面(表示為無限/1)；最後的情境模擬使用具有128個頁面、其中有8個預取頁面的緩衝區的現實情況(表示為128/8)。這一情境使用簡單LRU模式丟棄存儲器內頁面。在所有情況下，都假定4KB的頁面大小。
圖4示出了對各個查詢工作負荷的缺頁情況度量，圖5示出了對串行和並行模式的組合查詢工作負荷的缺頁情況度量。如結果所示，在所有試驗中，XC顯然優於DFS。這表明通過邊權重適當模擬運行時刻的基本原則能夠導致顯著的性能優點。幾乎在所有情況下，DFS聚類引起大量的缺頁情況。對於各個查詢工作負荷，當單純根據工作負荷查詢對文檔進行聚類時，觀察到了工作負荷的最好頁面調度性能。使用組合查詢工作負荷進行聚類僅對第三個查詢Q3有好處。查詢Q1和Q3均遍歷邊province/city，因此組合查詢工作負荷產生的聚類與通過使用具有Q3的工作負荷而產生的聚類一樣好。類似地，參見圖5，這些XPath查詢的串行和並行執行受益於智能聚類。尤其是，組合查詢工作負荷的串行執行從XC的工作負荷已知的聚類中大大受益。串行和並行情況的結果表明，XC利用局部親合性的能力實際上是非常有效的。值得注意，DFS分區值比XC分區值低10％。試驗度量已經表明，即使較小的分區值差異也會導致頁面調度特性的根本差異(圖4和5)。
現在參照圖6，其中示出了根據本發明的實施例的方法的流程圖。在步驟1010，讀取下一個xml標記。在判決塊1020處，確定該xml標記是否具有空值。如果是，則不進行進一步的處理。如果不是，則確定該標記是否是結束標籤(步驟1030)。如果該標記不是結束標籤，則初始化該標記(步驟1040，下面會參照圖7詳細描述)。在初始化之後，確定該標記是否是屬性的當前xml子節點，如判決塊1060所示。如果不是，則該過程返回到步驟1010。如果是，則該標記是以已完成元素為根的子樹，或具有關於其邊的權重的屬性，如數據塊1070所示。返回到步驟1030，如果該標記是結束標籤，則確定該樹節點是否包含子節點，並且該節點是否完成，如判決塊1060所示。如果不是，則該過程返回到步驟1010。如果是，則該標記是以已完成元素為根的子樹，或具有關於其邊的權重的屬性，如數據塊1070所示。接著在步驟1080將數據1070劃分成一組W/C個分區，其中W是分區的權重，C是塊大小，如數據塊1090所示。(下面參照圖8詳細描述步驟1080)。在步驟2000，對數據進行後分區處理，下面會參照圖9詳細描述該處理。根據後分區處理的結果，讀取下一個xml標記(步驟1010)，或者繼續進行分區(步驟1080)。
現在參照圖7，其中示出了圖6的初始化步驟的流程圖。在步驟2010，針對所分析的xml節點創建樹節點。接著確定該樹節點是否是父節點，如判決塊2020所示。如果不是，則該節點變成該樹的根(步驟2040)；如果是，則在父節點和子節點之間建立連結，並且指派邊權重(步驟2030)。在步驟2050，創建具有權重W和值0的初始分區。這個分區接著被加入已創建分區的列表中(步驟2060)。
現在參照圖8，其中示出了圖6的分區步驟的流程圖。在單遍分析XML文檔期間，通過過程調用對一個XML節點調用XC。每當完全掃描了一個XML節點時(即在endElement，characterSAX事件期間，或當掃描屬性標籤及其值時)，調用XC。在每次調用之前，假定對XML節點v調用之前，邊權重指派器必須已經為連接到其XML父節點的邊指派權重。XC始終對節點v起作用，v的子節點的集合代表已經由XC處理的子樹。常數hwm和lwm分別是高和低水位標誌，滿足lwm＜hwm＜存儲器使用限制。
在判決塊2070，確定存儲器使用是否大於hwm。如果是，從(已處理子樹的)最高值分區列表中獲得與所關心節點相關的最高值分區P，並且將其從(已處理子樹的)最高值分區列表中移除(步驟2080)。接著，從聚類樹刪除相關子樹的節點(步驟2090)，並且其聚類被標記為就緒(步驟3000)。接著，該聚類被傳送給頁面分配(步驟3010)。只要存儲器使用大於hwm，這一過程就繼續執行。一旦存儲器使用低於hwm，則使用其根節點的分區和其子節點的分區對子樹進行分區(步驟3020)。創建W/C個分區，其中在具有相同權重的所有分區中，該W/C個分區中的每個分區具有最大值(步驟3030)。這通過創建具有等於v的文本大小的權重wx的聚類節點x來實現；接著將x連接到其父節點。然後，用值0和權重w形成分區Pw，該分區包括含有節點x的單個聚類(Pw＝{(x)})。在所有分區中，具有最大值的分區被選擇為最優分區(步驟3040)。如果v是文本節點(葉)，則Pw被標記為節點x的最優分區。對於所有其它節點，這個分區被標記為初始分區。接著，計算以具有中樞聚類權重w′的節點x為根的最佳中間分區的w=WxC,K,WC,]]>這要調用Lukes的方法(其中連接線被任意斷開)。為具有根x的子樹識別(局部)優化的分區Poptx，以作為在與節點x相關的中間分區中具有最大值的中間分區。接著，刪除該樹的當前根的子節點(步驟3050)，並且接著返回以節點x為根的該樹的W/C個分區(步驟3060)。
現在參照圖9，其中示出了圖6的後分區步驟的流程圖。在判決塊3070，對已分區子樹的W/C個分區中的每個分區進行評估，以檢查它們是否包含XML文檔的根節點。如果這些分區包含根節點(即它們是在整個文檔之上被定義的)，則選擇最優分區(步驟3080)，並且其全部聚類被標記為就緒(步驟3090)。接著，這些就緒聚類被傳送到頁面分配(步驟4000)。如果沒有根節點(判決塊3070)，則在判決塊4010確定是否存在任何就緒聚類。如果沒有，則該過程返回到分區步驟(步驟1080)。如果有，則這些就緒聚類被傳送到頁面分配(步驟4020)。根據需要重複這個過程，如判決塊4010所示。
應當理解，根據至少一個當前優選的實施例，本發明包含用於按節點分析XML文檔的裝置；用於初始化至少一個所分析的節點的裝置；用於對至少一個所分析的節點進行分區的裝置；用於確定至少一個所分析的節點的XPath工作遍歷的裝置；和用於處理至少一個所分析的節點的裝置，其可以被實現在運行適當軟體程序的至少一個通用計算機上。它也可以被實現在至少一個集成電路或至少一個集成電路的部分上。於是，應當理解，本發明可以通過硬體，軟體或二者的組合來實現。
如果這裡沒有另外指出，則將假定這裡提及和引用的所有專利、專利申請、專利出版物和其它出版物(包含基於Web的出版物)在這裡均全文引用作為參考。
雖然這裡已經參照附圖描述了本發明的示例性實施例，但應當理解，本發明並不局限於這些確切的實施例，並且本領域的技術人員在不背離本發明的範圍和宗旨的前提下可以進行各種其他的改變和修改。
參考文獻列表[W3C]World Wide Web Consortium.W3C Architecture Domain.www.w3c.org/xml.Online Document. D.Florescu and D.Kossmann.Storing and Querying XMLData using an RDBMS.IEEE Data Engineering Bulletin，22(3)27-34，1999[Fre91]G.N.Frederickson.Optimal Algorithms for Tree Partitioning.In Proceedings of the Second Annual ACM-SIAM Symposium on DiscreteAlgorithms，pages 168-177，1991[GJ79]M.S.Garey and D.S.Johnson.Computers and Intractability.W.H.Freeman and Co.，1979. C.Gerlhof，A.Kemper，C.Kilger，and G.Moerkotte.Partition-Based Clustering in Object BasesFrom Theory to Practice.InProceedings of the Foundations of Data Organization and Algorithms，FODO′93 Chicago，Illinois，October 13-15，pages 301-316，1993[JN83]D.S.Johnson and K.A.Niemi.On Knapsacks，Partitions，anda New Dynamic Programming Technique for Trees.Mathematics ofOperations Research，8(1)，1983. B.W.Kernighan.Optimal Sequential Partitions of Graphs.J.Assoc.Comp.Mach.，18(1)34-40，1971[KM00]C.Kanne and G.Moerkotte.Efficient Storage of XML Data.In Proceedings of the 16th International Conference on Data Engineering，San Diego，U.S.A.，March 2000.IEEE Computer Society. J.A.Lukes.Efficient Algorithm for the Partitioning of Trees.IBM Journal of Research and Development，13(2)163-178，1974[Luk751 J.A.Lukes.Combinatiorial Solution for the Partitioning ofGeneral Graphs.IBM Journal of Research and Development，19(2)170-180，1975[Sch77]M.Schkolnick.A Clustering Algorithm for HierarchicalStructures.ACM Transactions on Database Systems(TODS)，2(1)27-44，1977. A.R.Schmidt，F.Waas，M.L.Kersten，D.Florescu，M.J.Carey，I.Manolescu，and R.Busse.Why and How to Benchmark XMLDatabases.ACMSIGMOD Record，3(30)，September 2001. F.Tian，D.DeWitt，J.Chen and C.Zhang.The Design andPerformance Evaluation of Alternative XML Storage Strategies.In ACMSIGMOD Record，(31)1，pages 5-10，ACM Press，2002. M.M.Tsangaris and J.F.Naughton.A Stochastic Approachfor Clustering in Object Bases.In Proceedings of the 1991 ACM SIGMODInternational Conference on Management of Data，Denver，Colorado，May29-31，pages 12-21.ACM Press，1991[TN92]M.M.Tsangaris and J.F.Naughton.On the Performance ofObject Clustering Techniques.In Proceedings of the 1992 ACM SIGMODInternational Conference on Management of Data，San Diego，California，June 2-5，pages 144-153.ACM Press，199權利要求
1.一種用於對XML文檔進行聚類的系統，該系統包括用於按節點分析XML文檔的裝置；用於初始化至少一個所分析的節點的裝置；用於對至少一個所分析的節點進行分區的裝置；以及用於對至少一個所分析的節點進行處理的裝置。
2.根據權利要求1所述的系統，其中用於初始化至少一個所分析的節點的裝置包括用於針對至少一個所分析的節點創建至少一個樹節點的裝置；用於提供關於至少一個所分析的節點的XML工作負荷信息的裝置；用於當所分析的節點是父節點時提供至少一個父/子連結並且指派邊權重的裝置；用於當所分析的節點不是父節點時指定所分析的節點為樹的根的裝置；用於創建分區的裝置；以及用於將所創建的分區添加到已創建分區的列表的裝置。
3.根據權利要求2所述的系統，其中用於提供XML工作負荷信息的裝置包括用於當至少一個節點被分析時分析至少一個XPath查詢的裝置；用於識別被XPath查詢訪問的至少一個節點的裝置；以及用於確定經由父-子節點邊對至少一個節點的訪問的次數的裝置。
4.根據權利要求2所述的系統，其中用於創建分區的裝置創建具有權重w′(等於節點權重)和值零的初始分區。
5.根據權利要求1所述的系統，其中用於對至少一個所分析的節點進行分區的裝置包括用於通過利用根節點的分區和至少一個子節點的分區對至少一個所分析的節點進行分區的裝置；用於創建Wc＝W/C(W是權重邊界，C是塊大小)個分區的裝置；用於從該Wc個分區中選擇具有最大值的分區的裝置；以及用於刪除該至少一個所分析的節點的任何子節點的裝置。
6.根據權利要求5所述的系統，其中該Wc個分區的每個在具有該相同權重的所有分區中具有最大值。
7.根據權利要求2所述的系統，其中由較重的邊連接的節點被映射到相同頁面。
8.根據權利要求2所述的系統，其中系統存儲器是受限的。
9.根據權利要求2所述的系統，還包括用於識別至少一個就緒聚類的裝置。
10.一種用於單遍地對XML文檔進行聚類的系統，該系統包括用於按節點分析XML文檔的裝置；用於確定至少一個所分析的節點的XPath工作遍歷的裝置；用於對至少一個所分析的節點進行聚類的裝置；以及用於向頁面指派至少一個聚類的裝置。
11.根據權利要求10所述的系統，其中用於分析至少一個所分析的節點的裝置包括用於為至少一個所分析的節點創建至少一個樹節點的裝置；用於提供關於至少一個所分析的節點的XML工作負荷信息的裝置；用於當所分析的節點是父節點時提供至少一個父/子連結並且指派邊權重的裝置；用於當所分析的節點不是父節點時指定所分析的節點為樹的根的裝置；用於創建分區的裝置；以及用於將所創建的分區添加到已創建分區的列表的裝置。
12.根據權利要求11所述的系統，其中用於提取XML工作負荷信息的裝置包括用於當至少一個節點被分析時分析至少一個XPath查詢的裝置；用於識別被XPath查詢訪問的至少一個節點的裝置；以及用於確定經由父-子節點邊對至少一個節點的訪問的次數的裝置。
13.根據權利要求11所述的系統，其中用於創建分區的裝置創建具有權重w′(等於節點權重)和值零的初始分區。
14.根據權利要求10所述的系統，其中用於對至少一個所分析的節點進行分區的裝置包括用於通過利用根節點的分區和至少一個子節點的分區對至少一個所分析的節點進行分區的裝置；用於創建Wc＝W/C(W是權重邊界，C是塊大小)個分區的裝置；用於從該Wc個分區中選擇具有最大值的分區的裝置；以及用於刪除該至少一個所分析的節點的任何子節點的裝置。
15.根據權利要求14所述的系統，其中該Wc個分區的每個在具有該相同權重的所有分區中具有最大值。
16.根據權利要求11所述的系統，其中由較重的邊所連接的節點被映射到相同頁面。
17.根據權利要求10所述的系統，其中系統存儲器是受限的。
18.根據權利要求10所述的系統，還包括用於識別至少一個就緒聚類的裝置。
19.一種用於單遍地對具有至少一個節點的XML文檔進行聚類的系統，該系統包括用於指派邊權重的裝置；用於進行樹分區的裝置；以及用於頁面指派的裝置。
20.根據權利要求18所述的系統，其中系統存儲器是受限的。
21.根據權利要求19所述的系統，還包括用於識別至少一個就緒聚類的裝置。
22.一種用於對XML文檔進行聚類的方法，包括步驟按節點分析XML文檔；初始化至少一個所分析的節點；對至少一個所分析的節點進行分區；以及處理至少一個所分析的節點。
23.根據權利要求22所述的方法，其中初始化至少一個所分析的節點的步驟包括針對至少一個所分析的節點創建至少一個樹節點；提供關於至少一個所分析的節點的XML工作負荷信息；當所分析的節點是父節點時提供至少一個父/子連結並且指派邊權重；當所分析的節點不是父節點時指定所分析的節點為樹的根；創建分區；以及將所創建的分區添加到已創建分區的列表中。
24.根據權利要求23所述的方法，其中提供XML工作負荷信息的步驟包括當至少一個節點被分析時分析至少一個XPath查詢；識別被XPath查詢訪問的至少一個節點；以及確定經由父-子節點邊對至少一個節點的訪問的次數。
25.根據權利要求22所述的方法，其中以權重w′(等於節點權重)和值零來創建初始分區。
26.根據權利要求22所述的方法，其中對至少一個所分析的節點進行分區的步驟包括利用根節點的分區和至少一個子節點的分區對至少一個所分析的節點進行分區；創建Wc＝W/C(W是權重邊界，C是塊大小)個分區；選擇該Wc個分區中具有最大值的分區；以及刪除該至少一個所分析的節點的任何子節點。
27.根據權利要求26所述的方法，其中該Wc個分區的每個在具有該相同權重的所有分區中具有最大值。
28.根據權利要求23所述的方法，其中由較重的邊所連接的節點被映射到相同頁面。
29.根據權利要求22所述的系統，還包括識別至少一個就緒聚類。
30.一種機器可讀的程序存儲裝置，有形地體現可被機器執行以實現用於對XML文檔進行聚類的方法步驟的指令程序，所述方法包括步驟按節點分析XML文檔；初始化至少一個所分析的節點；對至少一個所分析的節點進行分區；以及處理至少一個所分析的節點。
全文摘要
本發明公開了用於XML文檔的聚類的方法和系統。所述方法在指定的存儲器使用限制下操作。該系統實現該方法，並且掃描XML文檔，根據應用工作負荷指派邊權重，將XML節點的聚類映射到盤頁面，所有這些均在分析器控制的對XML數據的單遍處理中完成。應用工作負荷信息被用於產生導致大大降低所考慮的工作負荷的缺頁情況的XML聚類方案。本發明公開了用於表示工作負荷信息的若干方案。例如，工作負荷可以列出在應用期間調用的XPath操作符，以及其調用頻率。通過引入例如查詢重要性或查詢編譯代價的附加特性，能夠進一步細化應用工作負荷。使用隨機方案也能夠模擬XML訪問模式。
文檔編號G06F7/00GK1614594SQ20041007826
公開日2005年5月11日 申請日期2004年9月21日 優先權日2003年11月7日
發明者R·博爾達維卡爾, S·K·帕德馬納班, O·什穆埃利 申請人:國際商業機器公司