一种基于拓扑序列匹配的有向图.ppt

致谢 感谢在座的老师耐心听完我的演讲 感谢实验室的老师和学长，在毕设阶段给予指导和帮助 感谢所有的老师，因为有你们的教导才有我今天的成长 感谢所有同学，给我留下大学生活的美好回忆 感谢关心和爱护我的家人和朋友给予我幸福和快乐 * 基于拓扑序列匹配的有向图子图同构过滤算法 * * 它具有能很好建模存在多种关联的数据以及表示内部具有拓扑结构的数据的优点。 在人们生活、科学研究和工程领域有着更为广泛的应用，但是这种丰富的语义和复杂的内部结构增加了各种查询算法的难度，使得传统的数据查询和处理算法无法继续适用或高效处理。 如图1-1所示，图中的节点表示H2O的原子，节点的标号表示不同的原子类型，图中的边表示H2O的内部化合键，即共价键。与其它数据结构相比，图能够表达更加丰富的语义，在人们生活、科学研究和工程领域有着更为广泛的应用，但是这种丰富的语义和复杂的内部结构增加了各种查询算法的难度，使得传统的数据查询和处理算法无法继续适用或高效处理。 * 例如，GraphGrep(path), gIndex(graph), TREE ?(graph+tree), Treepi(tree)等。 优点：索引构建好以后，可以极大的减少同构测试的次数。 缺点：特征的提取和索引的构建是非常复杂的，构建出的索引往往占用空间很大，而且更新困难。 通过分析各种领域图表示的原型，发现大量的数据采用的都是有向图模型。但是目前，子图包含查询的研究主要是针对无向图的。 数据库动态更新时，前面提到的算法需要离线构造复杂索引，而我们提出的算法只需要进行个别序列处理，从而提高性能。 相对于图的匹配，序列的匹配是简单的。因此，将图拓扑成序列，通过序列的匹配过滤出候选结果集，再做同构测试，得到真正的结果集。 * 环路处理阶段：对图数据库中的有向图使用环路处理算法，从而将有向图转化为DAG； 索引构造阶段：使用分层拓扑算法将图数据库转化的DAG拓扑成序列，作为索引； 过滤阶段：首先使用环路处理算法将给定的查询图转化为DAG，其次对查询图转化的DAG使用分层拓扑算法，从而拓扑成序列，再次对数据库中每个有向图的拓扑序列与查询图的拓扑序列使用序列匹配算法，如果匹配则加入候选结果集。 同构验证阶段：对候选结果集中的图与查询图做同构测试，同构算法采用Ullman算法，得到最终的结果集。 图数据库中的有向图转化成DAG后，只在索引构造阶段执行一次分层拓扑算法拓扑成序列，之后便可重复用于查询阶段。当图数据库更新时，比如有新的有向图加入时，也只需对新加入的有向图执行一次环路处理算法和分层拓扑算法，且对之前的索引没有影响。这点不同于基于“特征”的图索引方法耗费大量时间更新索引。分层拓扑算法和序列匹配的简单性使算法可用于在线操作。 * 性质1同一层的任意两点间不存在偏序关系。 证明：因为算法每次输出所有入度为零的节点到一层，它们之间不存在边，所以不存在偏序关系。 性质2在Li(i=2,…,n)中每一个顶点存在前驱顶点，且必有一个前驱顶点在Li-1中。 证明：假设在顶点v∈Li，v在Li-1中不存在前驱顶点。因为v在Li中入度为零且在Li-1中不存在前驱顶点，所以在输出Li-1时，v入度为零，v在Li-1中，与题设矛盾。 性质3顶点a与顶点b之间存在偏序关系ab,则对应的序列中b必出现在a之后。 证明：由ab知存在边a,b，则当a的入度为0时，b的入度至少为1。算法1每次输出入度为0的顶点，则b必出现在a之后。 * Li为删除所有Lk(ki)包含的顶点及其引出的边之后，入度为零的点的集合。 这个拓扑序列包含了顶点间的并行信息，而且每个DAG对应一个拓扑序列。 * gi为图数据库D中的一个图，q为查询图。分别使用分层拓扑算法获得拓扑序列：gi.str: 1,3/2,5/4/6,7/和q.str: 2,3/4/6,7/。 这两个序列匹配过程如图3.5所示。q.str按层匹配，在①中取q.str的第一层2,3/与Gi.str[1]+匹配，Gi.str[1]+中存在对应的匹配点（图4中用实心箭头指出），将s置为最靠前的匹配点（图4中用空心箭头指出）(3)所在的层数s=1，作为下次匹配的起点；在②中取q.str的第二层4/与Gi.str[1]+匹配，存在匹配点，s设为匹配点所在层数，即s=3；在③中q.str的最后一层6,7/与Gi.str[3]+匹配，存在匹配点。因此，Gi.str匹配q.str，Gi可能包含查询图q，Gi加入候选结果集。 * 证明：假设Gi包含查询图q，Gi.str不匹配q.str。则在q.str的某一层j存在一个顶点x，x在Gi.str[s]+不存在匹配点。⑴ 当j=1时，s=1，因为Gi包含q，Gi.str[1]+必然包含x匹配点 ，推出矛盾。⑵ 当j1时，由性质2知，x在q.s