基于結構索引的高效XML查詢處理方法.pdf

1、XML已經成為網絡上數(shù)據表示和交換的通用標準。隨著XML的應用越來越廣泛，對XML查詢效率的要求也越來越高。模式樹匹配是XML查詢的核心操作，在高效處理模式樹匹配的各種方法中，結構化連接算法最為流行。[BKS02]中提出的結構化連接算法TwigStack可以對模式樹進行整枝連接，避免了二元連接中無用的中間結果。由于TwigStack算法的高效穩(wěn)定易兼容等特點，很多研究工作在它的基礎上進行了優(yōu)化。TwigStack算法的I/O和cpu開銷

2、與輸入XML元素的數(shù)量密切相關，所以提高算法效率的一個可行方法是在算法開始之前篩掉盡量多的無用結點。一些工作使用了結構索引1-index來避免讀入不滿足路徑條件的XML元素。這種方法可以大大提高模式樹匹配的效率，但是它不夠靈活，一種固定劃分規(guī)則的結構索引并不能適合各種不同的XML文檔和不同的查詢。 本文中提出了一種新的結構索引 JoinGuide，它沒有采用其它索引的結構摘要的形式，而是一個以路徑表達式為結點的樹。索引結點之間的

3、邊代表著路徑表達式之間的包含關系。根據路徑表達式的不同選擇，JoinGuide索引的粒度在標簽劃分和F&B-index索引之間。它具有很好的靈活性，可以為XML中每種標簽單獨的選擇劃分的粒度，并且在劃分時充分考慮了XML文檔的靜態(tài)特征和動態(tài)特征，以取得總性能的最優(yōu)。 本文中還針對傳統(tǒng)的模式樹元組匹配結果中XML元素重復的問題進行了改進，提出了一種消除冗余的緊湊模式樹結果表示方式LinkedResultTree，它對每個出現(xiàn)在結果

4、中的XML元素只保存一次，并對每個二元結構關系只用一個值記錄與該結點滿足結構關系的元素集的位置，大大減少了保存結果所需要的空間。I司時本文還基于JoinGuide索引和LinkedResultTree提出了新的模式樹匹配算法TwigStackCompact，它避免了TwigStack算法中最后耗時的歸并連接步驟，提高了算法的速度。最后文章還針對擴展的模式樹模型APT提出了對應的匹配算法TwigStackCompactAPT，避免了復雜的