该文提出了如何将具有各种运算符的正则表达式转化为查询自动机的方法.针对XPath规范中规定的"∥"操作符,即祖先—后代关系操作符,我们提出了一个称为模式自动机(Schema Automata)的数据结构,模式自动机可以接收所有可能出现在XML文档中的片断,也就是说,它可以匹配任何可能出现在XML文档中的路径模式;而传统的自动机要想支持包含连接这一类非正则运算符是非常困难的.为了进一步提高模式自动机的性能,该文还提出了两种优化方法PSA和RWS.前者将模式自动机作为索引的一部分存储在磁盘上,避免了每次计算都要生成模式自动机的开销,后者则是通过following集合和preceding集合来过滤掉模式自动机中多余的状态和转换函数来达到提高查询效率的目的.为了支持自动机匹配算法,该文还提出了高效地支持自动机匹配算法的数据结构:路径模式树和路径实例树.通过与结构连接算法进行性能测试对比,我们发现自动机匹配算法的效率远远高于结构连接算法,PSA和RWS对自动机匹配算法的优化也很显著.与传统的关系数据库中的查询不同,针对半结构化数据的查询更多的是要找到满足某些特定模式的节点.近来,在简单路径查询的问题得到较好解决的基础上,人们将注意力转移到Twig查询中来.该文提出了如何利用索引技术来更好地解决Twig查询的问题.根据路径模式树索引,我们给出了利用自动机匹配路径模式树索引解决这一问题的方法,围绕这一方法,该文对Twig查询自动机的构建,Twig查询自动机与路径模式树的匹配等算法进行了讨论,并与用传统的结构连接方法解决Twig查询进行了实验对比,结果证明,基于自动机的方法在性能上具有较大优势.