有效支持XML結構連接的CAT索引及其并行算法.pdf

1、本文介紹了一種全新的有效支持XML結構連接的樹索引CAT(CompactAncestorTree)。CAT的基本思想是，對于給定的一個祖先后代查詢(簡稱A-D查詢)或Twig查詢，遍歷XML文檔，找出所有的祖先A的實例，用以建立CAT樹的主干；對于每個A實例，找出它的直接后代D的實例鏈接在它的后面。CAT不需要編碼。 首先，討論了針對A-D查詢的CAT的建立算法，接著討論了基于CAT的A-D查詢的結果輸出，包括按祖先序和按后代序

2、輸出。然后介紹了帶有小樹叉的Twig查詢的CAT的建立和結果輸出算法，Twig查詢分為a[.//b]//c和a//b//c兩種情況討論。因為經(jīng)典的結構連接算法StackTree算法效率較高且使用較廣，因此后面應用基于CAT的結構連接算法和基于StackTree的結構連接算法就A-D查詢和Twig查詢做了大量實驗，實驗結果表明，基于CAT的結構連接在大多數(shù)情況下性能明顯優(yōu)于基于StackTree的結構連接。由于CAT的運算封閉性，其擴展性