Study On Holistically Twig Matching Algorithm Over Probabilistic XMLs

Traditional databases manage only deterministic information, but now many applications that use databases involve uncertain data. The uncertainty is inherent in these systems due to measurement, sampling errors, and resource limitations.Nowdays more and more XML documents are used on the web for data storing and data exchanging.We know that XML document is semistructured and it is useful for data filtered on the web. The existing algorithms evaluate twig patterns in a traversal way. The main shortcoming of this way is scanning the whole probabilistic XML document to get the final results. In this thesis, we represent a probabilistic XML document in the form of probabilistic tag streams and then match them in a holistic way. This algorithm is called probabilistic holistic twig.This thesis aims at the match processing algorithm of twig patterns on probabilistic XML documents. We need do something else when we matching for the particularity of the probabilistic XML. The improvements make the algorithm more efficient, and we get the intermediate results with the algorithm of p-TwigStack.Data in probabilistic XML documents are uncertain, and there are corresponding probabilities with them. And also, the intermediate results and the final results of the match will have the corresponding probabilities. The results with low probabilities are not the ones that we want and we will have to pass them. Then the probabilistic threshold will be used. In the queries of probabilistic XML documents, the probabilistic threshold is very important.At last, the efficient of of holistic twig algorithm to the algorithm of possible worlds is compared, and the importance of the probabilistic index is also tested. We show the analysis of the compareing results at the last of the thesis.