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

1、隨著互聯(lián)網(wǎng)技術的發(fā)展，XML作為信息存儲和數(shù)據(jù)交換的標準被廣泛采用，由于客觀世界的復雜性，不確定數(shù)據(jù)存在于一些應用領域。通常不確定信息以概率值的形式在XML文檔中表示，這樣的文檔稱為概率XML文檔，概率XML文檔受到大家越來越多的關注。普通XML文檔的查詢處理已提出許多算法，但概率XML文檔的查詢處理研究較少，本文提出了p-TJFast算法和ProFirstTwig算法。
　　p-TJFast算法是傳統(tǒng)TJFast算法的改進，改進

2、后的p-TJFast算法能夠處理概率XML文檔。概率XML文檔不同于普通XML文檔，其數(shù)據(jù)的存在具有一定的概率值，為了能夠在概率XML文檔中進行Twig模式查詢，需要對擴展Dewey編碼進行相應的改進，增加概率信息。由于概率XML文檔中數(shù)據(jù)存在的概率特性，低概率的結果被舍棄，算法運行的過程中加入過濾操作。實驗結果表明p-TJFast算法能夠很好地實現(xiàn)概率XML文檔查詢處理。
　　Pro First Twig算法采取的編碼方式和p-

3、TJFast算法相同，但與p-TJFast算法不同的是Pro First Twig算法的標簽流是概率序排列的，而包括p-TJFast算法在內(nèi)的大多數(shù)算法的標簽流都是基于字典序排列的。基于概率序標簽流而提出了概率序標簽流的下界的概念，概率值低于下界的標簽流元素不被處理，這極大地減少了被處理的元素個數(shù)，同樣地，Pro First Twig算法運行的過程中加入過濾操作。實驗結果表明Pro First Twig算法處理簡單查詢時具有較高的效率。