论文部分内容阅读
XML已成为Web上数据表示、集成和交换的标准，它的格式简单、自我描述能力强，实现了内容、结构和表现三者的分离，更适合于数据表示和交换。近年来，XML在各个领域得到了广泛的使用，Web上已经涌现了大量的XML数据。如何对XML文档进行有效地查询成为一个重要的研究课题。XML文档的结构查询通常被转化为两个节点列表之间的结构连接操作。结构连接主要有两种思想：一种是路径分解法，将查询的路径表达式分解成多个简单路径表达式，进行匹配，然后将结果连接起来。这种方法不可避免的要产生无用的中间结果。另一种是小枝模式匹配方法，将查询表达式用树的形式建模，称为“小枝模式”(twig pattern)，再将小枝模式到XML文档树中进行匹配，这种方法使得算法的I／O代价、CPU时间复杂度和空间复杂度降低，提高了查询的效率。最近提出的基于ExtendedDewey编码的小枝模式匹配算法——TJfast能较有效地处理XML文档查询，但是ExtendedDewey编码不支持动态插入，并且TJfast算法的执行效率有待进一步提高。本文针对以上两个不足进行改进，主要工作如下：(1)提出了IFED(Insert-Friendly ExtendedDewey)编码方法，它从ExtendedDewey编码的基础上改进而来，既支持有效的查询，又支持动态插入。(2)TJfast算法的I／O代价和CPU时间复杂度与n个输入列表的大小和最后匹配结果大小的总和线性相关，但是，输入列表中有些不参与连接的节点是可以被跳过的。本文提出了TJDirect算法，它采用一种更为灵活的小枝模式匹配方法，跳过了一些不参与连接的节点，提高了算法的执行效率，并且算法中不再用集合保存匹配的节点，使得空间复杂度降低。(3)通过实验比较了基于IFED编码的TJDirect算法和基于IFED编码的TJfast算法的执行时间，结果显示TJDirect算法的执行效率较高。(4)为XML文档编码，考察IFED编码的存储空间超出ExtendedDewey编码的比值，实验证明IFED编码的存储空间不是很大。