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

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

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

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