图是计算机科学中最重要的数据结构之一。图不仅关注数据对象本身的属性,还关注数据对象之间的相互作用关系,可用于描述复杂的网络结构,例如亚马逊商品网络、FACEBOOK社交网络以及生物的蛋白质网络,等等。近年来,图数据得到了学术界的广泛关注和深入研究,取得了大批研究成果。随着图数据量的不断增大,如何有效地回答图数据中的各种查询是图数据管理研究中最核心的问题。本文提出了一种新的图查询需求:给定一个查询顶点,返回图中包含该顶点的一个合适的子图,返回的子图不能过小以防无法看出该顶点邻域和其他顶点邻域的区别,返回的子图也不能过大以防用户被返回的信息淹没。在这种需求驱动下,本文提出了图数据中的最小唯一诱导子图(Mininal Unique Induced Subgraph,简写为MUIS)查询。MUIS查询是指给定查询顶点,在单图或图集中查询包含该顶点的顶点数最少的唯一诱导子图。MUIS查询为图数据管理提供了新的数据访问和使用手段。MUIS查询不仅可以挖掘顶点邻域的特殊结构,还可以用于顶点的可视化展示以及探索顶点的性质。本文给出了MUIS的形式化定义、探索了MUIS的性质并给出了MUIS的编码方法。提出了过滤-验证的两阶段MUIS查询求解框架,在过滤阶段通过对诱导子图空间进行搜索和剪枝产生MUIS候选集,在验证阶段使用子图同构算法检验MUIS候选集中的诱导子图是否唯一。本文提出了基于查询点的广度优先分层搜索策略保证尽早求得顶点数最少的唯一诱导子图。在单图中,提出了基于已匹配点的剪枝策略减少子图同构测试次数。在图集中,除了使用基于已匹配点的剪枝策略,还加入了利用图的匹配顺序的剪枝策略,进一步提高求解效率。在同构测试算法上,均采用了基于查询点的改进VF2算法,该算法不仅优化了顶点的匹配顺序,还优化了算法实现的数据结构,从而提高了同构测试效率。在实验阶段,在单图和图集中,分别验证了MUIS查询的基础算法和改进算法的有效性并对比了算法的性能。本文提出了平均同构时间和调用递归函数次数两个性能评价标准,使用真实数据集和模拟数据集进行了实验。在单图中,使用了YEAST和HPRD两个真实数据集。在图集中,使用了AIDS和NASA两个真实数据集。经验证,提出的算法均能完成MUIS查询任务,改进算法查询效率得到了大幅度提高,并且当查询所花时间越长时改进算法的优势越明显。此外,通过实验还探索了MUIS查询求解效率的影响因素。通常情况下,随着图中边数、图的数量增多,查询效率降低;随着顶点标签数、边标签数增多,查询效率提高。