本论文目的是对XML结构连接算法进行研究，分析它们的时间和空间效率。主要的算法包括传统的遍历树算法、树合并算法、队列树算法、栈树算法，所有这些算法都分为按祖先有序和按后裔有序，其中的队列树算法在本论文中首次提出。在论文的最后还实现了文献[33]所提出的单枝查询算法，并将该算法与先生成基本二元结构关系，再将其拼接形成的单枝查询算法进行了比较。最后我们还对在数据库中引入索引和未引入索引时读数据库所用的时间进行了比较。 以上所有这些算法我们均编程实现，实现程序所用的语言是Java，操作系统平台为Windows2000Server，数据库系统为SQL_Server2000。除了在本论文的“引入索引”部分主要研究读数据库所用时间外，其它部分在算法实现中都略去了读取数据所用的时间。程序中我们采取的策略是将我们需要的数据一次性的从数据库中读出，或是放在链表中，或是先放在静态数组中，然后通过指针的移动在需要时读入链表，这样可以减少因读数据库造成的系统误差对研究结果所造成的影响。另外，我们事先并不知道程序一次所处理的数据量有多大，故采用动态链表方式让链表动态延长。在用Java语言实现的算法中，我们定义了一个类，每一个结点是该类的一个实例，每当需要新增一个结点时，只需进行一次类的实例化，然后将其链上链表即可。 XML查询是一种基于树结构的查询，树结构有双亲-孩子和祖先-后裔等结构关系，在一个XML数据库中发现所有满足这种结构关系的结点对是对XML查询的核心操作，它被称为结构查询或结构连接。但如何判断两结点存在双亲-孩子或祖先-后裔结构关系呢(以后将其统称为祖先-后裔结构关系)?既然XML文档可以表示为一棵倒挂的树，我们就可以利用数据结构中树的知识对祖先-后裔结构关系进行查询，对该树进行先根遍历就可以得到按祖先或按后裔有序的祖先-后裔结点对。然而在数据结构中对树的遍历采用的是递归调用，递归调用会导致压栈，这是一种即耗时间又耗空间的处理方式。从另外一个角度来考虑，XML文档是由标记和数据组成的，文档中被标记包围的内容就是数据，标记和数据之间存在一种包含关系，并且这种包含关系不会交叉。文献[30]中ChunZhang等提出了一种机制，这种机制先给每个结点编号，然后通过比较任意两个结点的编号是否存在包括关系，就可以判断它们是否存在祖先-后裔关系。其中产生编号的具体作法如下：假定一个XML文档己被解析成了一棵树，对该树进行深度优先搜索遍历，在遍历过程中顺序地给每一次访问的结点赋值，因为非叶结点总是被遍历两次，一次是通过它访问它的孩子，一次是从孩子结点返回，所以它被赋了两次值，而叶结点只有一个值。所谓包含有点像在数据轴上的范围包含，比如两结点编号分别为(StartPos1，EndPos1)，(StartPos2，EndPos2)，如果StartPos1＜StartPos2且EndPos2＜EndPos1，则第一个结点包含第二个结点，以后我们会看到只需判断条件StartPos1＜StartPos2＜EndPos1即可。 我们对本论文提出的所有算法都编程实现，并且每个程序都重复执行十多次，最终我们得到每个算法的平均执行时间。我们发现在基本的二元结构查询算法中，无论按祖先有序还是按后裔有序，传统的遍历树算法执行的时间最长，因此我们没有对其作进一步的研究。在按后裔有序的算法中，栈树后裔算法的确如文献[31]所述，执行时间最短，其次是队列树后裔算法，树合并后裔算法用时最多。然而在按祖先有序的算法中，栈树祖先算法并不像文献[31]所述的那么好，在某些情况下，其执行时间远远多于其它两种祖先有序算法的执行时间，而树合并祖先算法和队列树祖先算法执行时间总体相当。在对由树合并算法、队列树算法、栈树算法形成的各自单枝查询算法的研究中，我们发现其执行时间的对比情况与其在对应的基本二元结构查询算法中的情况基本相同。我们还在引入索引和不引入索引的情况下对数据库进行了读取操作，发现引入索引后读取数据的时间会更短。在论文最后，我们实现了文献[33]提出的单枝查询PathStack算法，其最终结果按后裔有序，执行时间比前述最快的后裔有序单枝查询算法快上了接近一个数量级的时间。 最终我们认为：在基本的二元结构查询算法中，文献[31]所提出的按后裔有序的栈树算法在时间和空间上的确优于按后裔有序的树合并算法和队列树算法，所以如果要生成按后裔有序的结点对时，最好采用栈树后裔算法。但如果要生成按祖先有序的结点对，则最好采用队列树祖先算法，因为将时间和空间这两个因素综合起来考虑，队列树祖先算法是最好的。在单枝查询算法中，文献[33]提出的PathStack单枝算法在后裔有序的单枝算法中是最好的，但在祖先有序的单枝算法则最好采用由队列树祖先算法形成的队列树祖先单枝算法。