一种概率XML数据树的化简算法

Algorithm for probabilistic XML data tree simplifying

针对概率XML数据树分布节点冗余的问题,提出一种化简概率XML数据树的算法。通过分析概率XML数据树中的路径类型,把概率XML数据树划分为稀疏和紧凑两种形式结构,通过消除概率级联、计算绝对路径的相容类集合和等价类集合等过程把前者变换为后者。理论研究和实例分析表明,该化简算法是有效的,能够解决概率XML数据树的化简问题。

Because the probabilistic XML data tree must have some redundant nodes,this paper presented the algorithm for probabilistic XML data tree simplifying. Based on analyzing some path types in the probabilistic XML data tree,departed the probabilistic XML data trees to the two forms that were the sparse data trees and the compact data trees. The sparse probabilistic XML data tree could be transformed to the compact one by eliminating the probability chain,computing the consistent set of the absolute path and the equivalence set of the absolute path. The theory research and experiment results show that the simplifying algorithm is effective. And it can solve the probabilistic XML data tree simplifying problem.