有效支持XML結(jié)構(gòu)連接的CAT索引及其并行算法.pdf

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

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