Internet作为一个全世界信息发布和交流的中心，正在改变人们对信息处理的传统观念。XML具有自描述特点，支持用户自定义标记标明数据的语义，逐渐成为Internet中信息描述和信息交换的事实标准。随着XML数据规模和复杂性的快速增长，人们对XML数据的查询效率提出了更高的要求。　　XML最初主要用于数据交换，数据量小，查询需求简单。早期的XML数据以文档方式存储，以关键字查询等信息检索手段查询，简单易用。但查询能力低，不能满足复杂条件的查询需求，更谈不上查询优化。一些现有的商业数据库如Oracle，DB2等，在系统中扩充了处理XML数据的功能。利用中间件，将XML数据分解并存储于关系数据库中，把XML查询请求转变为SQL等数据库查询语言表达，由关系查询引擎优化并执行，再将查询的结果转换为XML文档。这种方法利用商业数据库成熟的技术存储和查询XML数据，在一定程度上满足了查询复杂性的要求，但是查询语句和数据在不同模型之间多次的转换严重影响了查询效率。传统的数据库查询和优化技术不能满足XML数据查询效率要求，更多的研究者尝试从全新的角度考虑XML查询优化问题。　　与传统的查询优化技术相比，由于XML数据模型的复杂性，缺乏模式信息的有力支持和相对薄弱的相关基础研究，XML查询优化呈现独特的技术特色。主要表现在:查询树的简化，路径表达式选择性计算，表达式分解和受限的执行顺序选择等方面。　　本文针对上述问题，从语义优化，路径选择性计算，表达式分解和执行计划的选择等角度，研究XML查询优化中的关键问题，并将其应用到Native XML数据库管理系统OrientX中，获得了良好的效果。　　近年来，XQuery逐渐成为XML查询语言的事实标准。为了求解XQuery，人们提出了各种代数，目前广泛应用的基于树结构的代数用Pattern Tree Matching方法处理查询。由于各种原因，用户写出的XQuery查询语句中，会包含一些冗余信息，这些冗余信息转换为Pattern Tree中的冗余节点，直接影响了查询效率。其中一些冗余节点可以直接从Pattern Tree的结构中独立的判断，我们称这种冗余节点为语法冗余节点。另一类冗余节点需要模式信息的帮助才能找到并删除。人们称这种冗余节点为语义冗余节点。　　目前XML数据语义优化的方法主要是改进的chase方法和路径等价类方法，二者在优化的过程中，均需要首先扩大Pattern Tree的规模:改进的chase方法需把完整性约束作为冗余条件插入到查询表达式中，路径等价类方法需将不确定路径转换为确定路径。由于XML数据类型的复杂性，这种先膨胀再收缩的做法导致不彻底的优化和效率的丧失。　　本文提出了一种利用模式信息指导的Pattern Tree语义优化方法。我们根据模式信息提供的语义约束关系，和节点在Pattern Tree中的位置，总结出三个冗余节点判断规则。利用判断规则删除PatternTree中的冗余节点，从而达到减少Pattern Tree规模的目的。其特点是:无需把完整性约束作为冗余条件插入到Pattern Tree中，直接定位并删除冗余节点。我们首先提取出纯祖先约束，纯父约束和同时出现等完整性约束，然后利用它们提出并证明了简单叶节点冗余判断规则，叶节点冗余判断规则和非叶节点冗余判断规则。利用这三个规则不但可以判断冗余叶节点，而且可以在保留叶节点的情况下，判断冗余非叶节点。　　模式信息本身的复杂性会影响完整性检查和冗余规则判断的效率。为提高判断冗余节点的效率，我们设计了从模式信息中提取完整性约束的高效算法，和利用完整性约束判断冗余节点的语义优化方法。我们从模式信息存储代价，语义优化后的Pattern Tree规模和算法效率等方面，与等价类方法作了比较实验，从而证明本方法的可行性和高效性。　　用XPath表示的多谓词复杂路径是XQuery的核心表达式，其执行效率也是影响整个查询效率的关键因素。如何优化执行多谓词复杂路径是人们关注的焦点问题。多谓词复杂路径表达式包含多个谓词分支，不同的分支对查询目标的选择性不同，如果选择性低的分支先于选择性高的分支执行，就会有效的减少中间结果从而提高查询效率。因此，如何精确的估计位于不同分支的节点的选择性成为研究的热点。　　多谓词复杂路径中，既隐含数据之间的嵌套结构，更有对分散在结褐中的值的计算(。)为了精确的计算某节点的选择性，需要综合考虑表达式中所有节点对该节点的影响。传统方法在计算节点代价时需大量使用正态分布和独立性分布等假设。但XML数据有复杂的层次结构(,)文本和数值等分散在层次结构中。相关节点的分布以及节点值的分布很难满足传统代价计算常用的分布假设，导致代价估计误差(,)因此正确的抽取XML数据的分布特征，尤其是抓住数据之间的相关性，是决定代价计算精确性的关键因素。　　XML数据的相关性表现在两个方面:值相关和结构相关。值相关表现在不同类型的节点值有相关性。传统的方法采用多维直方图统计这类数据分布。其缺陷有三:首先是很难在具有半结构化和自描述性的XML数据中确定哪些数据是相关的，而人工指定的方法存在明显主观性。其次，由于结构的相关性，值的相关性会沿着嵌套关系扩张，导致直方图维数和个数的爆炸性增长，存储和维护庞大的统计信息会严重降低方法的可用性(。)最后，若计算涉及多个直方图，仍需独立性假设综合直方图的统计结果，导致误差的产生。结构相关性表现为嵌套在不同祖先中的同类节点个数不同。通过抽取模式统计结构信息的方法从整体上把握数据的分布情况而忽略了细节，只适用于数据分布均匀的情况。直方图方法能够体现细节的分布变化，但是，事先建好用于选择性计算的所有节点任何谓词情况的直方图是不可能的。　　XML数据是结构和数值的混合体，目前的方法在计算多谓诃复杂路径表达式中的节点选择性时，孤立的考虑值的分布，或者结构的分布，利用独立分布假设综合计算结果的方法必然导致误差的产生。为此，我们提出了一种基于直方图计算的多谓词复杂路径选择性代价计算方法。我们设计了一种新颖的二维直方图，正确的反映值与位置的关系。把结构的相关性隐含在直方图的位置关系中。所有直方图具有一致的分格，通过直方图运算计算路径中任何节点的选择性。这种方法能够在数据分布扭曲，并且查询条件复杂的情况下，准确的计算多谓词复杂路径表达式的代价。　　沿路径逐个计算节点选择性的方法，当路径很长时，运算次数相应增长，导致代价计算效率的下降。发现，在模式指导下，一些运算可以被跳过。为了提高代价估计的效率，构造了模式与直方图相结合的统计信息模型，给出了利用模式信息简化代价计算树的定理和模式指导生成代价计算树的高效算法(SGM)。通过与著名的复杂路径计算方法XSketch在统计信息存储，代价计算效率和代价估计精确性三个方面的比较实验，验证了本方法的优越性。PM和SGM方法的效率比较实验证明SGM方法可有效的提高代价估计的效率。　　Pattern Tree(PTQ)是复杂的树状结构(,)求解PTQ的过程是查找与之匹配的XML数据的过程。在PTQ中，只有部分节点是需要输出的查询目标节点，其余节点只是中间结果。因此，如何在求解过程中尽量避免中间结果的产生和存在周期，是XML查询优化面临的一个关键问题。　　目前的研究工作集中在高效算法的研究上，显然，只在求解的最后阶段讨论这个问题是不够的。试图从更广泛的角度,研究这一问题。从逻辑层，我们提出了一种PTQ分解策略，能够有效的限制中间结果的产生。在此基础上，在代价估计层，提出了基于生存周期的中间结果规模计算方法，可以正确地反映查询执行时的中间结果状态。利用这种计算方法确定的执行顺序，中间结果的总体规模最小，并且中间结果存在的周期最短。　　本文的工作是在Native XML数据库管理原型系统OrientX的基础上进行的，所提出的许多技术在系统中得到了应用。大量的实验都在原型系统的基础上进行。