概率XML的Twig查詢處理算法的研究與實(shí)現(xiàn).pdf

1、近年來(lái)，對(duì)于概率XML數(shù)據(jù)管理，已經(jīng)有不少理論研究。但是，對(duì)twig查詢處理，仍然缺少著比較高效的算法。因此，本文中針對(duì)概率XML的twig查詢處理算法進(jìn)行研究。
　　首先，本文提出一種新的針對(duì)概率XML文檔的編碼策略，pDewey編碼策略，來(lái)對(duì)文檔中的普通節(jié)點(diǎn)和分布節(jié)點(diǎn)的標(biāo)簽和概率進(jìn)行編碼。從而根據(jù)編碼可以高效地計(jì)算:任意一個(gè)節(jié)點(diǎn)的所有祖先節(jié)點(diǎn)的編碼、標(biāo)簽和概率;任意兩個(gè)節(jié)點(diǎn)的公共祖先節(jié)點(diǎn)的編碼、標(biāo)簽和概率。這些性質(zhì)對(duì)twig模

2、式匹配與匹配結(jié)果的概率計(jì)算都是至關(guān)重要的。
　　接著，本文提出一種新的針對(duì)概率XML文檔的分流策略，Tag+Probability分流策略。它不僅根據(jù)節(jié)點(diǎn)的標(biāo)簽，而且根據(jù)節(jié)點(diǎn)的概率，將編碼后的節(jié)點(diǎn)集合劃分成多個(gè)節(jié)點(diǎn)流，使得同一個(gè)節(jié)點(diǎn)流中的節(jié)點(diǎn)，具有相同的標(biāo)簽和相近的概率。從而能在查詢處理時(shí)，對(duì)輸入數(shù)據(jù)進(jìn)行剪枝，從而節(jié)省I/O代價(jià)，顯著地提高查詢處理的效率。
　　最后，基于提出的編碼策略和分流策略，本文提出一種新的概率XML文

3、檔twig查詢處理算法，pTJFastTP算法。作為一種holistic twig join算法，它能夠高效地對(duì)概率XML文檔進(jìn)行twig模式匹配。在連接階段，算法利用pDewey編碼，對(duì)匹配結(jié)果的概率計(jì)算，并且，一邊連接一邊根據(jù)概率閾值對(duì)中間結(jié)果進(jìn)行剪枝，從而進(jìn)一步提高效率。
　　本文進(jìn)行詳盡的實(shí)驗(yàn)，評(píng)價(jià)pTJFastTP算法的性能。實(shí)驗(yàn)中，采用各種不同結(jié)構(gòu)的數(shù)據(jù)和twig查詢，將pTJFastTP與目前效率最高的概率XML的t