论文部分内容阅读
随着Internet的发展,半结构化的数据在信息交换中越来越重要,如何准确、高效地查询XML数据已经成为研究的热点问题。XML文档可以用一棵嵌套的文档树来表示,查询路径也可以表示成一棵查询树即小枝模式,因此XML数据的查询就是从XML文档树中查找出所有满足小枝模式的XML数据片段,这个过程就叫做小枝模式查询。近年来,研究工作者提出了很多匹配小枝模式的查询算法：如TwigStack算法以及最近提出的TwigList和TwigNM算法等。小枝模式中包含有父子边和祖先后裔边两种,这些算法对仅含祖先后裔边的小枝模式查询是很有效的,但是当小枝模式中仅含父子边或同时含有祖先后裔和父子边时,这些算法仍可能产生大量的中间结果,尤其是输入和输出的规模很大时。针对目前算法存在的不足之处,通过结合ViST算法中利用字符串匹配查询从而不需要结构连接的思想,以及Twig2Stack算法中自底向上和不需合并的思想,本文提出了两种基于有序对的小枝模式匹配算法PCTwig和OPTwig,所做的主要工作如下：(1)提出了一种基于有序对的新思路,通过有序对的建立更好地将结点与结点连接起来。利用查询树和文档树中有序对的匹配来进行查询。(2)针对小枝模式中的三种结点：根结点、中间结点和叶子结点,提出三种不同的匹配方法。又根据小枝模式中结点间的两种关系：父子关系和祖先后裔关系,构造了MatchPC和MatchAD函数。(3)提出了两种新算法PCTwig和OPTwig,对文档树和查询树的存储结构进行了规定。对查询树进行自底向上的存储,在碰到分支结点时,进行标记。这样可以在查询过程中对分支进行判断,从而避免无用结点的产生。(4)在实验系统上把两种新算法与经典算法TwigStack和TwigStackList算法进行了比较,证明了PCTwig和OPTwig算法的有效性。