图是最通用的数据建模结构之一,被广泛地应用于许多领域,包括社交网络分析、语义网和生物网研究等。随着信息技术的发展和各种互联网应用的出现,各种图结构数据呈爆炸式增长。面向图数据的树模式匹配查询是图数据集上的一类重要查询,在实际应用中显得越来越重要。具体地,一个树模式匹配查询是为了查找图结构数据上符合查询结构约束的实例。它是图数据集上许多其他查询的重要组成部分。本文对该类查询进行了深入的研究,其主要研究成果包括以下方面。　　 第一、本文深入研究了针对可达树模式匹配查询的两个已有算法PathStackD和TwigstackD并提出了一系列新的面向图结构数据的整体匹配算法。具体地,本文提出了一种对可达模式匹配查询结果的通用划分方法,将查询结果分为四类:Type-l,Type-2,Type-3和Type-4。本文系统分析了PathStackD和TwigStackD算法原理,指出PathStackD无法正确返回部分Type-4结果,TwigStackD无法正确返回Tvpe-2和Type-4结果。Type-2和Type-4都是实际应用的查询中非常普遍的查询结果。本文详细分析了两种算法的时间和空间复杂性,讨论了算法中的两个重要技术对算法正确性和有效性的影响,即生成树的生成策略和节点过滤过程。本文将整体匹配方法应用到图结构数据的模式匹配查询中,融合栈编码和池编码,提出一个路径模式匹配查询算法和两个树模式匹配算法。实验验证了文中对PathStackD和TwigStackD的理论分析结果同时验证了新提出算法的效率和可扩展性。本文中提出的算法第一次将整体匹配方法应用于图结构数据上的查询处理中。　　 第二、本文提出了一种支持布尔逻辑,允许部分查询节点为输出节点的模式匹配查询GTPQ。通过引入以命题逻辑定义的结构谓词,GTPQ不仅可以表示查询节点属性约束条件,而且对结构约束有很强的表达能力。本文研究了GTPQ的查询优化相关的四个关键问题,分别是可满足性问题、包含、等价和最小化问题。我们指出仅含逻辑析取和(或)逻辑合取的模式匹配查询的可满足性问题可在线性时间内判定,但当将逻辑非引入查询时,可满足性问题变为NP-完全的。GTPQ的包含、等价和最优化问题是NP-难的。本文提出利用图结构来表示查询处理中的中间结果,该方法能有效减少存储中间结果代理的空间代价并能避免连接操作所带来的巨大时间代价。基于图节点可达索引的大量已有研究工作,本文提出一个节点过滤过程框架。它可以高效地过滤大部分甚至所有冗余的数据节点,最大程度减少后续边匹配操作的复杂度。本文进一步给出了基于3-hop可达索引的GTPQ处理算法GTEA。针对以部分查询节点为输出的模式匹配查询,该算法能动态压缩查询模式自适应优化处理过程。实验结果显示,即使是处理一般的合取树模式匹配查询,GTEA的时间代价、空间代价和I/O开销也远低于现有的算法。将取非和析取谓词引入到查询中后,GTEA相对基于分解的方法以使用其他算法的策略具有更大优势。实验同时也显示了基于可达索引的节点过滤过程比基于遍历的过滤过程的显著优势。本文是针对支持布尔逻辑的面向图结构数据的模式匹配查询的四个关键问题和查询处理算法的第一项研究工作。