图是一种通用的数据结构,能描述复杂的结构化或半结构化数据,如:XML、WWW、社会关系网络、化合物集合、蛋白质与基因网络等等。随着图在各领域内的成功应用,图数据开始迅速累积。然而,数据量的增加,不但没有带来信息获取的便利,反而由于图数据的复杂本质,使得学习与研究工作更难展开。图查询是图数据集上的一个典型应用,用于从海量图数据中获取用户需要的知识。与传统查询技术相比,图查询具有自己的特点与难点,如:数据结构复杂,操控困难;子图同构已被证明是NP完全问题,是图查询领域中不可避免的基本操作之一;图数据种类繁杂,等等。正是这些难点,导致图查询技术的研究充满了机遇与挑战。本文通过对图数据查询技术的研究,归纳总结了现有研究成果的思想和优缺点,重点研究了频繁子图查询、超图查询、包含查询、相交子图查询等技术专题,主要的研究成果与创新如下:第一、现有效率较高的频繁子图模式查询算法,在生成频繁子图的过程中,对边的扩展通常采用深度优先的方法。而且,对频繁子图的每次扩展,均需要通过子图同构计算验证其正确性。然而,深度优先的扩展方式虽然能有效避免查询算法重复生成中间结果,却带来了更高的时间复杂性。本文提出了一种高效的频繁子图查询算法,通过先生成频繁子树,进而通过这些频繁子树进一步生成频繁子图。在生成频繁子树的过程中,采用深度优先的遍历方式避免中间结果的重复计算,并利用子树同构可在多项式时间内完成的特点提高该部分算法的效率。另一方面,在由子树向子图扩展的过程中,通过广度优先的方式进行扩展,不但能有效避免中间结果的重复生成,而且进一步提高了算法的效率。理论分析与实验结果显示,采用这种查询方法,使查询效率提高了O(√n·logn)倍,并在提高效率的同时,得到正确的结果集。第二、超图查询算法采用过滤与验证模式,即:通过对图集的过滤,得到更小、更精确的候选集,从而降低查询过程中子图同构次数,进而提高算法的效率。超图查询的过滤规则为包含逻辑,即如果甲图包含乙图,则甲图必然包含乙图的所有子图。查询算法的索引通常建立于图集中的频繁模式,包括频繁子图、频繁子树或频繁路径等。然而,在给定查询图之后,无论何种索引,均需要得到查询图包含的索引模式,并通过索引模式支持集的交集得到候选集。在得到查询图包含的索引模式过程中,需要进行查询图子图枚举,并与索引模式之间进行子图同构,得到查询图包含的索引模式。本文提出查询算法VFM,通过图集中关键节点与频繁模式之间的映射,将得到被查询图包含的索引模式的过程由指数形式降低为多项式形式,从而显著提高了算法效率。实验结果表明,采用该算法进行查询,其效率远高于当前已经提出的算法。第三、图查询问题包含的另一类查询问题,称为包含查询。包含查询与超图查询的本质区别在于,它采用的过滤手段为排除逻辑,即:给定查询图,如果图集中的图数据包含的某个模式不是查询图的子图,则该图也必定不是查询图的超图。利用排除逻辑建立的索引,在查询之初,同样要通过枚举或与索引模式之间逐个的子图同构计算得到不被查询图包含的索引模式,这是需要尽力避免的计算开销。本文针对图包含查询中存在的问题,提出利用频繁子图查询过程中形成的深度优先树组织索引,能增量地进行查询图与索引模式之间的子图同构计算。而且,在索引模式的选择中,提出采用频繁模式集中一类特殊的子集——频繁闭模式来建立索引,这种方式不但能极大化地减小候选集的尺寸,同时也避免了过多子图同构计算所带来的负面影响,从而提高了算法的效率。第四、图集的查询问题,并不能完全通过频繁子图查询、超图查询与包含查询解决。相交子图查询问题,能在某些条件下转化为超图查询或包含查询。然而,超图查询或包含查询解决相交子图查询问题时,需要重复进行多次查询,方可得到查询结果,效率低下。针对相交子图查询问题,目前尚无研究结果发表。本文率先提出的相交子图查询算法,通过对数据库图解构,形成基于节点诱导连通子图的有向无环图,并通过边列表对有向无环图的节点信息进行补充,不但能高效完成相交子图的查询工作,而且将索引的规模控制在了适当的范围之内。相交子图查询能解决图集中一类查询问题,因而,本文作为首篇提出该查询算法的文献,意义深远。