由于XML具有自描述性和可扩展性等特点,能够满足WEB上对数据描述和存储的需求,因而使得XML正在成为Web上数据表示和交换的事实上的标准。随着XML格式数据的快速增长和广泛应用,对XML数据的查询、转换和存储的研究受到了广泛关注。在XML文档的查询技术研究中,基于小枝模式匹配的结构连接查询是关键的核心内容。对于XML结构查询,可以对XML文档树中的结点或边进行编码,通过编码直接判断结点之间的结构关系,而无需对原XML文档树进行遍历,从而将XML结构查询的计算转化为结构连接的计算。目前对XML文档的编码方法有区间编码、路径编码、前缀编码等。因此,随着不同编码方案的研究,各种相应的结构查询算法也提了出来。对于XML文档基于结构连接的小枝模式匹配查询,是从文档树中查找与查询模式匹配的结点,然后将查找到的匹配结果再组装成最终符合查询表达式的完整树结构。TwigStack是一个典型的关于小枝模式匹配的结构连接查询算法。它采用链栈的数据结构作为缓存,对查询节点流进行整枝计算,从而避免了无用中间结果的产生。基于此算法,又提出了一系列改进的算法。其中Twig~2Stack和TwigList算法分别采用层次关系的堆栈结构和列表结构,避免了复杂的归并过程,进一步提高了查询效率。在我们对小枝模式匹配查询的研究中,发现TwigStack算法对查询节点流在结束时的处理上存在着不足;在对TwigList算法的分析中,发现可以将XML文档的SAX解析应用于查询过程,从而避免了对XML文档进行编码,能进一步提高查询效率。本文的主要工作是:(1)提出了BSTwigStack小枝模式匹配查询算法。该算法增强了原有的TwigStack算法,给出了XML文档在查询节点流结束时的查询匹配处理策略。(2)提出了BSTwigList小枝模式匹配查询算法。针对XML文档的结构特点,在结合XML文档的基于事件的SAX解析方式的基础上,改进了TwigList算法。BSTwigList算法能够应用于节点流模式的小枝查询,在文档解析的同时可以进行模式匹配查询,避免了以往查询算法需要先对文档节点进行编码索引的步骤,使得XML文档在更新时,无需对编码文件进行重新编码和维护,从而减少了查询所需的存储空间,提高了查询效率。(3)最后通过对算法进行的实验和数据测试,给出了算法查询时间响应及性能分析图表,进一步验证了改进的查询算法的有效性。在对以上算法的研究和实现当中,本文所研究的只是XPath查询的一个片段,对于其他形式的XPath查询,仍然有待于进一步的研究;另外本文考虑的只是一种静态XML文档节点数据流的小枝模式匹配查询,而对于在网络环境下的多用户的动态数据流小枝模式匹配查询,还要加以更进一步的研究。这些将成为今后下一步研究的重点和方向。