（计算机应用技术专业论文）基于dfs编码的图形数据库topk查询技术研究.pdf

东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果 也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示了谢意。 研究生签名： 起埠日期：巡陴虬 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：耍埠导师签名： 同期：型埠玺丝目 摘要 摘要 图形是一种描述性很强的数据结构。通过加以标记的顶点和边，图形既可以深入描 述一组实体间的关系，也可以直观地描述这些关系间的属性。在复杂结构数据建模方面， 如化合物分子结构，蛋白质基因结构，电路结构，w 曲和x m l 文档等，图形起着很重 要的作用，图形数据库也由此得到广泛的关注和应用。在与图形相关的应用中，存在一 个共同且关键的问题，即如何有效地处理图形查询和检索问题。通常，应用是否成功直 接依赖于查询处理系统的有效性。 本文主要讨论图形数据库的t o p k 查询问题，即给定一个查询图，返回数据库中与 其最相似的k 个图形。将查询图与数据库中的图逐个地进行两两比较是非常耗时的。一 般地图形数据库的查询主要分为查询过滤和查询验证两个阶段。在过滤阶段中，数据库 中不符合条件的图应尽可能多地被过滤，并生成一个候选图形集合。在查询验证阶段， 进一步筛除掉不满足条件的图形，获得最终结果。在过滤阶段，关注如何对图形建立索 引以减小候选图形集合。在验证阶段，一般使用子图同构技术进行验证。 针对图形数据库查询处理和优化需求，重点分析和研究了图形数据库的索引技术和 图形同构技术，在上述的两个技术中均使用d f s 编码对图进行序列化。在此基础上， 进一步研究了图形数据库的t o p k 查询。 在图形数据库的索引技术方面，提出基于频繁语义结构的图形数据库的索引方法， 称为g s i l l d e x 。g s i n d e x 使用g s t r i n g 技术来表示图形，把图形表示成由语义信息的裂片 组成的串，然后找出频繁的具语义信息的裂片，用d f s 编码对这些裂片进行序列化， 在此基础上对这些裂片构造索引树。由这些有语义的裂片构造的索引更加贴近实际的应 用。 在图形同构方面，通过深入分析经典图形同构的算法，根据最小d f s 编码的性质， 即两个图同构当且仅当它们的最小d f s 编码相同，提出了基于d f s 编码的予图同构算 法。 在t o p k 查询方面，根据图形相似性的度量标准，提出基于g s h l d e x 技术的t 0 p k 查询方法，并论述了两种新的查询方式：析取查询和合取查询。这两种查询方式可以根 据用户的需要，按照部分特定的基本子图及它们间的逻辑组合关系进行查询。 实验结果表明，以上技术和方法可有效提高过滤率和验证的准确性，提高查询性能。 关键词：图形数据库d f s 编码索引技术子图同构t o p k 查询 a b s t r a c t g r 印hi sad a t as 仃u c t i l r eg o o da td e s c r i p t i 佃 d e s 嘶b en o to n l yt h er e 恼t i o n sb e 呐e e no 协e c t s ， w i ml a b e l c dv e n e x 懿a n de d g e s ，i tc 触 b u ta l s om ea t t r i b u t e so ft l l er c l 撕o n s i n t u i t i v e l y t h e r e f o r c ，i th 嬲b e 吼p l a y i n ga ni m p o r t 锄tr 0 1 ei nm o d e l i n gc o m p l i c a t o dd a t a s t r u c t u r e s ，s u c ha sc o m p o u n d s ，p r o t e i n s ，c i r c m i t s ，w b ba n dx m ld o 咖n e n t s ( i r 印hd a t a b a s e h a sb e c o m eah o tr e s e a r c ht o p i ca n db e e ne x t e n s i v d yu s e d w i n l 灯a p l l i c sa p p l i c a t i o n s ，t h e r e i sac o m m o n 锄dc m c i a li s s u eo fh o wt 0e 商e c t i v c l yd e a lw i t l l 掣a p h i c a lq u e w 雅dr e 喇“a l p r o b l e l n s u s u a l l y t l l es u c c e s so fa na p p l i c a t i o ni sd i r e c u yd e p e n d e l no nm ee 仔e c t i v e n e s so f n s 鲫n l cq u e r yp r o c e s s m gs y s t e m 7 m st h e s i s 南c u s e so nt 0 p kq u e 巧t e c l l l l i q u e sf o rg r a p hd a t a b a s e s ，i e ，舀v 锄aq u e 巧 莎a p hq ，r e t u mt l l ek - m o s ts i m i l a r 掣a p hi nt h ed a t a b a s e i ti sv e r yt i m e c o n s 啪i n gt oc 觚叮 o u tp a i rw i s ec o m p 撕s o nb e 觚e e i lt h eq u e r y 伊印h 锄dt h e 伊印hi nt h ed a t a b 硒e q i l e r y p r o c e s s i n go f 伊印hd a t a b 嬲ec 趾b ed i v i d ei n t o 觚os t 印s ：( 1 ) s e 鲫c h ，w h i c hc o m p a r e st h e f e a t i l r e so f aq u e 巧聊h qw i m m ef c a _ t u r e so f m e 铲印h s i nn l ed a t a b a s et oc r c a t eac a n d i d a t e q u e 巧觚s w e rs e tq ；( 2 ) v 舐6 c a t i o n ，w h i c hc h c c k se a c h 伊a p hgi nqa g a i n s tqt os e e m e t l l 盯gi n d e e dc o n t a i n sqo ras i m i l a rv e r s i o no f q i nt l l es e 部c hs t 印，w ec o n c e ma b o u t h o wt oc o n s t m c ti n d e xo nm ed a t a b a s et or e d u c ec a n d i d a t es e t i nm ev e r i 6 c a t i o ns t 印，w e u s u a l l yu s es u b g r a p hi s o m o 印h i s mt e c i l l l i q u e s f o rt h en e e d so fg r a p hd 锨出a s eq u e 哕p r o c e s s i n ga 1 1 do p t i m i z a t i o n ，t l l i st 1 1 e s i s 觚a 1 ) ，z 骼 a l l ds t u d i e sn l eg r a p hd 北出弱ei n d e x i n gt e c h i q u e s 锄d 伊叩hi s o m o 叩h i s mt e c h n i q u e s i n b o t l lt e c h i q u e s ，t h em i n i m u md f sc o d ei su s o dt or 印r e s e n tt h e 伊a p h s b a s e do nt h i s ，t l l e 1 o p kq u e r i e sf o r 伊a p hd a t a b 嬲ea r e 如r t h c rs t u d i e d f o rg r a p hd a t a b a s ei i l d e x i n gt e c h l l i q u e s ，a 1 1i n d e x i n gm e n l o d ，c a l l e dg s i n d c x ，w h i c hi s b a s e do n 矗? e q u e i l ts e m a i l t i cs 仃u c t l 】r e nu s e sg s t r i n gt e c l l l l o l o g yt 0r 印r e s e l l t 伊a p ha i l d6 n d o u tm ef 呐u e l l t 锄ds e m 觚t i c 缸舯e n t s ，t h e i lu s et h e s e 丘a g m e n t st oc o n s 仃u c tt h ei n d e x 吮 f o rg r a p hi s o m o 印h i 锄，s o m et y p i c a l 伊a p hi s o m o 咖i s ma l g o r i m m sa r ea n a l y s e di n d e t a i l a c c o r d i n gt ot l l ep r o p e r t yo fm em i n i m u md f sc o d e ，i e t w o 伊a p h sa r ei s o m o 咄i ci f a i l do n l yi ft h e yh a v em es 锄em i n h n 啪d f sc o d e ，w ep r 叩o s e dam in i 】叭md f sc o d eb 弱e d s u b 伊印hi s o m o 印h i s ma l g o r i t l l i l l f o r1 1 0 p ki i l q u i r i 鹤，b a s c do nt h e 伊a p l l i cs i m i l a r i t ym e a s u r e s ，w ep r o p o s e da r o p - k q u e 巧m e m o d su s i n gg s i n d e x w ba l s oa d v a i l c e s 铆on e wq u e 拶m o d e s ：c o n j u l l c t i o nq u e 哕 a l l dd i s c o n j u n c t i o nq u e t l l e s e 帆on e 、) l ，m o d e sc 觚p r o c e s sr e t r i e v a lb a s e do np o r t i t i v e s 乜c t u r e so ft a r g e tr e s u l t sa n dt h el o 百c 嬲s 锄b l yr e l a t i o n so ft l l es 协l c t i l r e st 0m e e tt l l e d e i i l a n d so fn e w a p p l i c a t i o n s e x t e i l s i v ee x p 舐m e i l t sa r ec o n d u c t e d ，锄d l er c s u l t ss h o wt 1 1 a tg s i i l d c xh a sag o o d p e e f o m a i l c ei n 心i n d e xs i z ea n di n d e xc o n s 仃u 甜o n 劬e ，b o t ht h ed f sc o d c db 嬲e d s u b - 聊hi s o m o 印h i s ma 1 9 0 r i n u i la i l dt h et o p kq u e 巧a l g o r i m 【na r ce 任e c t i v ei ni m p r o v i n g b o t l la c c l l r a c ya n de 伍c i e n c y k e yw o r d ：g r 印hd a t a b a s e d f sc o d e ，g r a 曲d a t a b a s ei n d e x ，s u b 伊a p hi s o m o 呻i c ， t o p kq u 唧e v a l u a t i o n 目录 目录 摘要i a b s t l l l c t i i 目录 第1 章绪论1 1 1 研究背景1 1 2 图形数据库t o p k 查询的丰要问题和国内外研究现状3 1 2 1 研究的丰要问题3 1 2 2 研究现状4 1 3 论文研究内容和结构。6 第2 章图形数据库查询的索引构造方法8 2 1 引言8 2 2 图形数据库的基本概念8 2 3 典型的图形数据库的索引方法9 2 3 1 基于路径的索引m 叩h g r 印9 2 3 2 基于频繁结构的索引一g i l l d c x 1 0 2 3 3 图到序列的转化g s t r i n g 1 0 2 4 基于频繁语义结构的图形数据库的索引方法1 1 2 4 1 频繁结构1 1 2 4 2 g s t r i n g 技术1 3 2 4 3 图的序列化1 7 2 4 4 索引构造1 9 2 5 实验。2 0 第3 章子图查询2 2 3 1 引言2 2 3 2 基于矩阵变换的同构算法2 2 目录 3 2 1 图的矩阵变换2 2 3 2 2 图同构矩阵变换算法2 4 3 2 3 图同构实例应用分析2 5 3 3 图同构问题粒子群算法。2 7 3 3 1 粒子群算法原理2 7 3 3 2 离散粒子群算法求解图同构2 9 3 4 基于d f s 编码的图形同构算法。31 3 4 1 最小d f s 编码的求解3 1 3 4 2 子图同构算法3 3 3 5 实验。3 3 第4 章 图形数据库t o p k 查询一3 6 4 1 引言3 6 4 2 图形相似的度量标准3 6 4 2 1 编辑距离( e d i t 距离) 3 6 4 2 2 最大公共子图3 7 4 2 3 基于拓扑子图与编辑距离的距离测量方法3 8 4 3 基于频繁语义结构的图形数据库的索引方法上的t o p k 查询4 0 4 4 t o p - k 查询扩展4 1 4 4 1 合取查询4 1 4 4 2 析取查询4 4 4 5 实验4 5 第5 章总结与展望4 6 5 1 论文研究工作总结4 6 5 2 有待进一步研究的问题4 6 致 射4 8 参考文献4 9 目录 作者在攻读硕士学位期间发表的学术论文。5 2 第l 章绪论 1 1 研究背景 第1 章绪论 计算机科学正以各种方式越来越快地渗透到各个领域之中，其应用日益广泛，同时 也对数据建模不断提出新的要求。 图形就是一种描述性很强的数据结构，通过加以标记的顶点和边，图形既可以描述 一组实体间的关系，也可以描述这些关系间的属性。相比较其它的数据结构，如：树、 序列、集合等，图可以表达更丰富的语义信息。所以在模拟复杂结构和数据方面，图形 有着很重要的作用。现实中，很多领域内的数据都可抽象为图，比如生物信息学中的蛋 白质结构和生物网络、化合物分子结构、w 曲以及x m l 文档( 如图1 1 所示) 。因此， 图形数据库得到了越来越广泛的应用。d a y l i 曲t 系统 1 就是一个用于化合物登记的商业 产品，已经被用于化学信息中。c h 锄i d p l u s 2 是一个由美国国立医学图书馆( n a t i o n a l l i b r 哪o f m e d i c i n en l m ) 提供的免费数据服务，可以提供结构和术语信息的查询。用 户可以在网上通过化合物的名字、结构、毒性甚至质量等方式灵活地查询化学分子。给 定一个查询结构，它可以很快地给出一个很小的分子集以作进一步分析 3 ，4 ，从而缩 短药物设计和其他科学研究的周期。 豢 。毛= j 篱曼搿譬舞： 糕“ 图卜1图形建模的应用 以上所有这些应用说明了图形数据库的重要性和用途的广泛性。在与图形相关的核 心应用中，存在一个共同且关键的问题，即如何有效地处理图形查询问题。通常，应用 是否成功直接依赖于查询处理系统的有效性。 经典的图形查询问题可以描述如下：给定一个图数据库d = 蜀，9 2 ，岛) ，和一个查 1 东南大学硕士学位论文 询图q ，找出所有的蜀d 使得q 是g f 的子图。扫描整个图数据库d ，检查q 是否为图数 据库d 中任意一个图璺的予图十分耗时。这个问题的复杂度部分决定于子图同构问题， 而子图同构问题已被认定为是n p 完全问题 4 5 。此外，现实中的应用如对化合物的搜 索，子图同构检查需要容忍一些不一致，如节点、边和结构的较小差别。 为此，人们对图的索引技术进行了大量的研究。许多方法的基本思想是把图分解为 路径( 如g 1 a p h g r 印 6 ) 或是裂片( 如g i n d e x 7 ) ，然后把路径或裂片作为图检索中的 过滤特征。然而，这些方法有以下缺点： ( 1 ) 即使小规模的图也可能产生出组合爆炸数量级的路径或者碎片，从而导致一 个巨大规模的索引空间。 ( 2 ) 对于特定应用，并不是所有的路径或者碎片都有意义。另一方面，一旦将一 个图分解，就有丢失其全局结构信息的风险，而这些丢失的全局信息可能对特定应用有 更大的意义。即使可能从分解的片段中重建这些全局信息，那也将非常耗费时间。 下面以搜索化学化合物数据库为例说明以上两个缺点。图1 2 ( a ) 和1 2 ( b ) 表示两个 结构高度相似的化合物，我们希望从中抽取得到的特征能够反映这种相似性。 g r a p h g r 印 6 使用路径作为特征。为了表示图1 2 ( a ) 中的化合物，记录了长度小于 3 的2 8 中不同路径的9 6 种情况，如图1 2 ( d ) 所示。如果不是有机化合物中原子的种类 的限制( 大部分为碳和氢) ，g r 印h g r 印甚至会生成更大规模的特征空间。g i n d e x 7 试图 通过只对“有辨别力的裂片”建立索引来减少特征。然而，路径和裂片很少能表达两个 化合物的相似度。为了获得相似度，需要在大量的特征间进行很多的“连接 操作，这 导致了计算时间上代价的急剧增长。 另一方面，在有机化学中，国际化联( p a c ) 命名规则对化合物实行简明地命名。 例如，图1 2 ( c ) 中的两个化合物分别被命名为2 ，3 d i d e o x y _ 3 f l u o r o c y n d i n e 和 c y t i d i n e ，2 3 d i d e o x m 5 d i n u o r o 。 b ) p a t h q 蛐n t i t y p a 【h q u a n 6 t y c 9o2 f lo hl n3o h cj c 旬hic o3 o 3c n 6 n 6c fl clc c1 2 o h clc c o hl c c f2f c2 c c n4n c c 4 c n c6n c n4 n c o30 c n3 c ( ) c2o c c3 c o3c ：c c8 t c 傅) 图卜2两种化合物的三种表达形式 第1 章绪论 通过这些简明的名字，学科专家能确切的知道化合物的结构，而非学科专家或计算 机却无法从这样的命名得知它们的结构，也无法得知它们之间结构的相似性。因此，在 没有将相关学科知识编码成机器可读的形式并且应用于搜索过程的情况下，是不可能将 结构相似搜索建立在国际化联命名规则的基础上的。 由此可知，图形数据库中的查询存在三个重要的难题：( 1 ) 如何有效地存储图形数 据库；( 2 ) 如何建立有效的索引结构来促进模式匹配和图形的相似搜索；( 3 ) 如何定义 图和图之间的相似性。这些问题将在本文的后续章节中展开研究。 1 2 图形数据库t 0 p - k 查询的主要问题和国内外研究现状 1 2 1 研究的主要问题 图形的查询问题是指给定一个图，返回数据库中包含该图或与其相似的图形。一般 地，查询可以分为两种： ( 1 ) 模式匹配：模式匹配就是给出数据库中一组满足模式尸的图形，匹配与否是 由匹配条件来决定的。最常用的匹配条件是子图同构检测，当且仅当尸是g 的子图时， 模式尸匹配图形g 9 。 ( 2 ) 近似搜索：近似搜索是在数据库中找出与所要查询的图形近似的图形。图形间 的近似通常用图形间的编辑距离( e d i td i a t a n c e ) 【1 0 】来衡量。 本文讨论的图形数据库的t o p k 查询问题就是指给定一个查询图，返回数据库中与 其最相似的k 个图形。 如图1 3 所示，图形数据库的查询主要分为查询过滤和查询验证两个阶段。在过滤 阶段中，数据库中不符合条件的图形应尽可能多地被过滤，并生成一个候选图形集合。 在查询验证阶段，进一步筛除掉不满足条件的图形，获得最终结果。 图卜3图形数据库查询处理结构图 东南大学硕士学位论文 在过滤阶段，关注于如何对图形建立索引以减少候选图形集合。在验证阶段，一般 使用子图同构技术进行验证。因此如何建立有效的索引结构和图的同构方法是图形查询 处理的关键技术。对于图形数据库的t o p k 查询，则在此基础上，根据所定义的图形的 相似性度量标准对与查询图相似的图形进行排序并返回结果。 1 2 2 研究现状 由于图形数据库的应用日益广泛，图形数据库的查询问题引起了国外很多专家和学 者的关注，国内外不少大学和机构在这方面进行了大量的研究工作。下面简要分析在图 形数据库的索引技术和图的同构算法方面的研究。 d a y l i g h t 1 是基于路径的技术，用于检索分子数据库子结构的商业系统，数据库 中的每个分子都被表示为一个图。d a y l i g h t 使用“指纹来找到数据库中相关的图。数 据库中的每个图都被关联到一个固定大小的位向量( b i t v e c t o r ) 上，这个向量被称为图 的指纹。给定一个图g ，它的指纹向量由如下方式得到：g 中所有从o 到每个限定长度 的路径都被计算，每个路径被用作种子生成一个随机数，然后将这个随机数的位表示加 入指纹。这样指纹就表示了图的结构特征。两个图的相似性通过比较它们的指纹来计算。 可以采用多种不同的相似性度量如：t a n a m o t oc o c f f i c i e n t ( 共同位的数目除以总共的 位数) ；欧式距离( 集合距离) 。而t v e r s k y 相似性被用来衡量一个数据图的子图和一个 待查询图的相似性。 s h a s h a 等提出了另一个称为g r a p h g r e p 6 的基于路径的技术，它代表了基于路径 方法的最高水平【7 】。g r a p h g r e p 方法列举出每个图形中达到一定长度阈值的所有路径。 索引表中每行代表一个路径，每列代表一个图形。表中的每个实体是这个路径在图形中 出现的次数。g r a p h a g r e p 用路径作为特征。其优点在于： ( 1 ) 路径相对图和树来说，更容易操作； ( 2 ) 索引仅选取最长不超过m a x l 的所有路径，因此，索引空间的大小是可预先计算 的。基于路径的索引将图形分解为路径，对每条路径，分别搜索包含它的图形集合，再 将结果相交。查询过程就是检查g 中是否包含待查询图形q 的所有路径，从而实现过滤。 但是，因为在进行结构分解的时候，可能产生信息丢失，候选集合中非解结果数量也很 多。所以，这个方法并不适合复杂图形的查询。其缺点也很明显，因为路径过于简单， 所以索引项很多，过滤效果并不理想。 g r a p h g r e p 所存在的缺陷激发了研究人员寻找更好图形数据库的索引方法。y a n 提 出了g i n d e x 7 方法，该方法使用频繁的子结构作为特征。频繁的子结构反映了数据库 的本质特征，并且当数据库更新时，频繁子结构保持相对稳定。g i n d e x 使用了两种技术： 第l 章绪论 尺寸增长支持度约束和有判别力的裂片。这使得g i n d e x 只要对少量的裂片进行索引， 从而减小了索引空间并且提高了过滤率。但是，无论是路径还是有判别力的裂片都只有 局部信息，图形的局部与整体间的关系都没有很好的体现。整体结构信息损失，将可能 导致过滤率的下降。而且如何为待查询图形选择合适的特征也是一个难以优化的问题。 因此g i n d e x 方法并没有从根本上解决g r a p h g r e p 方法的潜在问题。此外，通过对图形 数据库挖掘的研究表明，要在数据库中找出这些结构本身就很难，时间和空间复杂度都 很高。 在搜索应用中，这类基于特征的索引对特征的依赖性强，而且因为分解产生的特征 数量较多，为了还原图形，还必须采用连接操作把特征组合在一起，研究表明组合的数 量也极其庞大。 d a v i dw w i l l i a m s 1 7 等人基于图分解( g r a p hd e c o m p o s i t i o n ) 的方法提出了称为 g d i n d e x 的索引方法。他们将原先使用于不带有边标记的稀疏图( s p a r s eg r a p h ) 或者平 面图( p l a n a rg r a p h ) 的分解方法扩展到了带有标记的边的稠密图( d e n s eg r a p h ) 上。通 过图形规范表示法，将每个在图形分解过程中列举出来的子图进行规范编码。用h a s h 函数索引这些编码。对待查询图形也做同样的操作。在搜索的时候，如果待查询图形的 规范编码的h a s h 值与索引中的值相同，则索引项所含图形作为候选图形加入候选结果 集。最后还需要验证候选结果集中的图形的规范编码是否与待查询图形的完全匹配。当 数据库中的图呈现高程度的相似性时，g d i n d e x 可以产生出精简的索引结构，同时能高 效地识别子图异构关系。但是这种方法有局限性，适合于在图的规模比较小时( 顶点数 小于2 0 ) 使用。 复旦大学的j i a n g 等人提出了g s t r i n g 5 的方法。该方法将图转换成有语义信息的 结构组成的序列串，然后再对数据库中的图建立索引。它使用图中有意义的结构作为最 后的图序列串中的基本单元。这不仅减小了结果序列的尺寸，而且可以进行基于语义的 搜索。但该方法需要将数据库中的所有图都建立到索引树中，这样对于较大的图形数据 库其索引树也会很大。 已有的图形数据库搜索研究建立在对半结构化数据查询发展基础上，主要利用数据 库自身信息，例如特定结构( 路径，子图) 建立对应的索引，通过检查待查询图形与目标 图形之间的包含和数量关系实现过滤，减少了候选图形数，减轻验证阶段的计算量，从 而提高查询性能。这种以结构裂片为索引项的思想给了本文很大启发。 对于图的同构算法的研究，目前国内外进行得还较少，图的同构问题可以分为四类： 精确图同构问题、精确子图同构问题、不精确图同构问题、不精确子图同构问题。其中 后而三个问题已经被证明属于n p 完全问题，而对于精确图同构问题的复杂性，目前还 没有一明确的结果，文献 2 2 中指出，图的同构问题既未证明是多项式时间可解的，也 未证明属于n p 完全，正是出于这一点，得到许多学者的关注。 东南大学硕上学位论文 就当前对于图同构问题的研究，国内外学者大多集中在一些特定条件下图同构问题 的研究，或者说特殊图同构问题的研究，这一类问题的研究文章比较多，比如最大外平 面图同构 2 3 2 5 ，树图同构 2 6 ，2 7 ，图的自同构问题。 近期一些文章关注的重点集中在矩阵的特征研究上，试图通过研究同构图矩阵所具 有的性质来进行判定 2 9 】，通过研究矩阵同构所具有一的特征，比如矩阵的秩、矩阵的 排布、矩阵的变换规律，来对问题进行研究。 对于同构问题的另一个研究方向是智能算法，国内外一些文献都给出了不同智能算 法求解同构问题或者相关问题的论述，文献 3 l ，3 2 】使用遗传算法对同构问题进行求解， 把同构问题转化为最小值问题，把种群编码映射到问题的解空间，通过遗传操作来求解 问题最优值，从而得到问题的判定。也有许多国外学者通过神经网络算法对同构问题进 行求解 3 3 ，3 4 ，在这个问题上，国内的一些文献也给出了很好的基于神经网络的同构 算法，文献 3 5 3 7 中利用h o p f i e l d 神经网络来求解图的同构问题，通过引入适当的能 量函数，把同构问题转化为求能量函数全局最小值问题。除此之外，对于一些全新的计 算模式，比如d n a 计算、量子计算，也对同构问题进行了很多的研究，文献 3 8 ，3 9 给 出了同构问题的d n a 计算模型，通过d n a 分子链编码、非解的去除、解的产生和读 取等操作解决了图的同构问题。关于图同构的问题，各种文献都给出了有益的求解方法 和思路，但是还有很多需要改进的地方。 1 3 论文研究内容和结构 在图形数据库的查询处理中，图形的索引，子图同构计算及t o p k 查询都是关键技 术，本文的研究工作将主要围绕这些方面展开。 1 、图形数据库的索引技术 图形的两两比较通常代价很大。子图查询还面临着子图同构的n p 一完全问题。而大 规模的图形数据集会导致大量的两两比较。因此，通过启发式的方法来减少图的两两比 较是建立图索引结构的主要目的。 对数据库中的图形加以合理的索引，不仅可以提高检索的速度，更重要的作用在于， 可以根据索引项，将待查询图形进行分解。分解之后通过比较图形局部的结构进行过滤， 得到较小的候选结果集合。因为图形同构计算复杂度很高，因此要将搜索的过程尽量转 换为在索引上的搜索，可以减少参加同构计算的图形数量，从而提高整个搜索的效率。 索引项的选择也是索引技术中关键问题，针对不同的应用，有不同的选择方式。 2 、子图同构方法的研究 在图形数据库的查询处理的验证阶段，一般使用图的同构方法来进行验证，本文将 第1 章绪论 研究特定条件下的子图同构算法。 3 、t o p k 查询的研究 t o p k 查询是一种重要的查询模式。在一些图形数据库中应用中，需要返回与多个 待查的图形相似的图形。本文将在图形数据库近似搜索中引入t o p k 查询概念，根据所 定义的图形的相似性度量标准对与查询图相似的图形进行排序并返回与查询图最相似 的k 个解。 围绕本文的主要研究工作，论文的组织结构如下： 第1 章介绍了研究背景，图形数据库查询的主要内容和国内外研究成果，本文的研 究内容以及整体结构。 第2 章论述图形数据库的相关概念，提出基于频繁语义结构的索引方法g s i n d e x 。 第3 章论述图同构的典型算法，并提出基于d f s 编码的子图同构算法。 第4 章论述度量图形相似的几个标准，在g s i n d e x 索引和基于d f s 编码的子图同构 算法的基础上，给出相关的t o p k 查询算法并介绍了两种新的查询方式。 第5 章对所作的研究工作进行了总结与展望。 东南大学硕上学位论文 第2 章图形数据库查询的索引构造方法 2 1 引言 一般而言，图形数据库的查询处理可以分成两个主要的步骤： 1 构造索引，这是一个预处理步骤。从图数据库中抽取合适的特征，设计合适的特 征表达形式，并有效地组织、存储这些特征。 2 查询处理，包括两个子步骤：( 1 ) 搜索( s e 盯c h ) ，比较查询图q 和数据库中的图 的特征，生成候选查询集合e ；( 2 ) 认证( v e r i f i c a t i o n ) ，比较q 和e 中的每个图，来 确定g 是否包含q 或与q 相似的结构。 在图的查询过程中，查询响应时间为：乙砌+ i q | ，其中z k 是搜索阶段所需 时间，乙是测试子图同构的平均时间，进行查询图q 和e 中图的测试。在认证阶段， 需用时i q 卜瓦一。来对q 中的图进行假阳性剪枝。由于一。的复杂度是n p 完全的，通常 认证的时间占主导地位。而对于一个给定的查询，五。的值变化不会太大。因此，缩短 查询响应时间的关键就是要让候选集e 尽量小。所以，在生成候选图形集合的阶段，如 何构建索引，如何选取特征，有效地过滤尽可能多的图形，是提高图形搜索效率的关键。 本章主要对图形数据库的索引技术进行研究。首先介绍几个典型的图形数据库的索 引方法，在深入分析这些经典图形同构算法的基础上提出基于频繁语义结构的图形数据 库的索引方法。 2 2 图形数据库的基本概念 图形数据库与普通的关系数据库不同。主要应用在与结构密切相关的领域，包括化 学结构，蛋白质分子结构等方面。图形数据库中存储的是图形文件，所以在图形数据库 上各种操作的实现与关系数据库不同。图形数据库的搜索过程中所涉及的映射、比较、 距离计算都与图的概念有关。 定义：标记图形( 1 a b e l e d 聊h ) 。作为一种一般的数据模型，标记图形可以用来对 复杂数据模型进行建模，如关系模型。标记图形是一个四元组，g = ( v ，e ，) ， 其中，v 是顶点集合，e v v 是连接两个不同顶点的边的集合，是顶点和边的标记 的集合，标记函数，：y ue 一，将顶点和边映射到标记。一个图形数据库是标记图的 集合。图2 1 给出了有三个图形的图形数据库的例子。 8 第2 章图形数据库查询的索引构造方法 c c c c 图2 1 图形数据库 ( c ) 定义：子图同构( s u b 伊a p hi s o m o 印h i s m ) 。给定两个图形，存在一个映射， 厂：y ( g ) 一矿( g ) 满足： ( 1 ) v “y ( g ) ，( “) = ，( “) ， ( 2 ) v ( “，1 ，) e ( g ) ，u ( “) ，厂( 1 ，) ) e ( 9 7 ) 并且，( “，1 ，) = ，( 厂 ) ，厂( ，) ) ，这里，分别为g 和g 的标记函数。 如果存在从一个图g 到另一个图g 的子图同构，那么图g 是图g 的子图。 定义：图形查询( g r a p hq u e r y ) 。给定一个图数据库d = 蜀，9 2 ，) ，和一个查询 图q ，返回查询结果集合d q = 岛i g & ，& d ) 。 2 3 典型的图形数据库的索引方法 2 3 1 基于路径的索引- g r a p h g r e p 对于图形数据库的索引技术，早期的多为基于路径的方法 1 ，6 ，其中，s h a s h a 等 提出的称为g r a p h g r e p 的索引技术代表了基于路径方法的最高水平。g r a p h g r e p 方法列 举出每个图形中达到一定长度阈值的所有路径。索引表中每行代表一个路径，每列代表 一个图形。表中的每个实体是这个路径在图形中出现的次数。g r a p h a g r e p 用路径作为特 征。其优点在于： ( 1 ) 路径相对图和树来说，更容易操作； ( 2 ) 索引仅选取最长不超过m a x l 的所有路径，因此，索引空间的大小是可预先计算 的。基于路径的索引将图形分解为路径，对每条路径，分别搜索包含它的图形集合，再 将结果相交。 c i c c c c 一 c c c c 一 c c c 一 一 c c 东南大学硕士学位论文 查询过程就是检查g ：f 中是否包含待查询图形q 的所有路径，从而实现过滤。但是， 因为在进行结构分解的时候，可能产生信息丢失，候选集合中非解结果数量也很多。所 以，这个方法并不适合复杂图形的查询。其缺点也很明显，因为路径过于简单，所以索 引项很多，过滤效果并不理想。 2 3 2 基于频繁结构的索引g i n d e x 基于路径的索引技术存在着一些缺陷，这激发了研究人员寻找更好图形数据库的索 引方法。y a n 等人提出了g i n d e x 方法，该方法使用频繁的子结构作为特征。频繁的子结 构反映了数据库的本质特征，并且当数据库更新时，频繁子结构保持相对稳定。g i n d e x 使用了两种技术：尺寸增长支持度约束和有判别力的裂片。这使得g i n d e x 只要对少量 的裂片进行索引，从而减小了索引空间并且提高了过滤率。但是，无论是路径还是有判 别力的裂片都只有局部信息，图形的局部与整体间的关系都没有很好的体现。整体结构 信息损失，将可能导致过滤率的下降。而且如何为待查询图形选择合适的特征也是一个 难以优化的问题。因此g i n d e x 方法并没有从根本上解决g r a p h g r e p 方法的潜在问题。 此外，通过对图形数据库挖掘的研究表明，要在数据库中找出这些结构本身就很难，时 间和空间复杂度都很高。 在搜索应用中，这类基于特征的索引对特征的依赖性强，而且因为分解产生的特征 数量较多，为了还原图形，还必须采用连接操作把特征组合在一起，研究表明组合的数 量也极其庞大。 2 3 3 图到序列的转化g s t r i n g 对于图形数据库的查询，另一个方法就是将查询图和数据库中的图都转换成序列， 这样图形查询问题就被转换成序列匹配问题。有些方法使用较好的粒度，即图形中的每 个节点和每条边都出现在结果序列中。然而，这样的方法不能表达出语义信息，并且结 果序列也很大。复旦大学的j i a n g 等人提出了g s t r i n g 的方法。该方法将图转换成有语 义信息的结构组成的序列串，然后再对数据库中的图建立索引。它使用图中有意义的结 构作为最后的图序列串中的基本单元。这不仅减小了结果序列的尺寸，而且可以进行基 于语义的搜索。但该方法需要将数据库中的所有图都建立到索引树中，这样对于较大的 图形数据库其索引树也会很大。 以上的这些图形数据库索引技术的研究主要利用数据库自身信息，例如特定结构 ( 路径，子图，语义结构) 建立对应的索引，通过检查待查询图形与目标图形之间的包含