支持近似图查询的Why-Not问题解释方法*

贺 丹，宗传玉，王 斌，李金旭，杨晓春

东北大学 计算机科学与工程学院，沈阳 110819

支持近似图查询的Why-Not问题解释方法*

贺 丹，宗传玉，王 斌，李金旭，杨晓春+

东北大学 计算机科学与工程学院，沈阳 110819

why-not问题是为查询结果中的缺失元组找到合理的解释。解决数据库查询中的why-not问题不仅能够帮助用户更好地理解查询，而且能够提高数据库的质量和可用性。为了提高图数据库的可用性，提出了支持近似图查询的why-not问题解释方法。该解释方法不仅阐明了为什么why-not问题没有出现在查询结果中，而且给出了一些修改初始查询图的建议，使得why-not问题能够出现在修改后的查询图的查询结果中。该算法分两部分完成：第一部分为候选修改操作生成阶段，首先利用边频率信息提出候选操作集生成基本算法，接着利用图分解操作提出候选操作集生成改进算法，得到修改初始查询图的候选操作集；第二部分基于对查询图修改操作数最少的代价模型，分别采用贪心算法和回溯法选取候选操作，贪心算法设计了合理的贪心函数，回溯法构建了回溯剪枝树，并提出三种剪枝策略执行剪枝操作，最终选取的候选操作集即为支持近似图查询的why-not问题的合理解释。实验表明，该方法可以快速有效地为近似图查询中的why-not问题提供合理解释。

近似图查询；why-not问题；回溯法；剪枝策略

1 引言

目前，数据库系统在资源存储和查询处理方面都十分高效。然而，随着用户需求的不断提升，一方面，用户对最终的查询结果不够满意；另一方面，他们也想知道为什么现有的数据库系统没有返回他们想要的结果，这类问题被称为why-not问题[1]。因此，回答数据库系统中的why-not问题不仅能够满足数据库系统用户的应用需求，同时也是提高数据库系统质量和可用性的重要途径。近期，why-not问题已经引起了数据库研究者们的广泛关注[1-4]，虽然已经取得了一些初步的研究成果，但是研究体系尚未成熟，仍有许多问题值得研究。

在现实世界的许多领域可以用图来表示各种复杂数据实体以及实体之间的关系。例如，在图像处理领域[5-6]，用关系图来表示图像内容，用顶点标号来表示图像中某一区域的特征；在email通信网络，用顶点表示具体的email地址，边表示两个email地址之间的通信往来。尽管在图数据查询领域已经有不少研究，但是大部分研究都集中于图的精确匹配查询[7]。虽然精确图查询能够准确无误地找到与查询图匹配的图，但是在实际应用中，数据库中存储的图数据结构复杂，导致精确图匹配方法查询效率较低。因此，近年来近似图查询受到越来越多研究者的关注。

一般来说，图数据库可以分成两种：第一种是事务型图数据库，该种类型的数据库中存储了大量的图结构，边与节点信息相对简单；第二种是社交网络型图数据库，该类数据库中只存储了一张图，边与节点信息复杂。本文的研究重点为第一种类型，将在第一种类型的数据库上进行近似图查询，并为whynot问题提供合理解释。

近似图查询是图数据库管理系统实现的重要功能，然而在实际应用中，用户常常对数据库管理系统返回的图查询结果不够满意。为提高图数据库系统的质量和可用性，解决近似图查询过程中的why-not问题就显得尤为重要。

为了更好地说明解释近似图查询过程中的whynot问题的实际应用价值，举例如下应用场景：当化学分子研究者在研究分子结构与化学性质的关系时，化学系统中包含的化学物质为CH4、C2H6、C2H2、C2H6O，当他查询与C2H6分子结构相似的化学物质时，系统返回的查询结果为C2H6和C2H6O，这时他可能想知道为什么C2H2没有出现在查询结果中，是否有更合理的查询让查询结果中包含C2H2。在这种场景下，合理地解释用户提出的why-not问题对其研究工作有重要意义。现将该问题形式化举例如下。

例1如图1所示，给定图数据集G={g1,g2,g3}和查询图q。当图差异阈值设定为δ=3时，求得λ(g1,q)=4+5-2×3=3，λ(g2,q)=4+5-2×4=1，λ(g3,q)=5+5-2×3=4，从而近似图查询结果为R={g1,g2}。文中近似图查询返回图数据集中与查询图的差异小于等于给定阈值的图的集合，图差异求解方法参照文献[8]。

Fig.1 Aset of undirected graphG={g1,g2,g3}and query graphq图1 无向图集合G={g1,g2,g3}及查询图q

此时，数据库查询用户可能会提出这样的问题：为什么图g3没有出现在近似图查询结果R中？这就是近似图查询过程中的why-not问题。

通过分析发现，例1中进行近似图查询时，查询图q与图g3的差异为4，大于阈值δ=3，因而查询结果中不包含图g3。为使得查询结果R中包含g3，可以通过对查询图执行增加边(b,d)的操作，使查询图q与图g3之间的差异小于等于δ，从而让图g3出现在查询结果中。

依据上述分析，为了满足用户提出的查询需求，本文为支持近似图查询的why-not问题提出了高效的解释方法。本文的主要贡献如下：

（1）提出了支持近似图查询的why-not问题解释框架。

（2）针对用户提出的why-not问题，结合近似图查询原始结果集，通过统计每条边出现的频率，提出了候选操作集生成基本算法，并得到why-not问题解释候选操作集。

（3）针对候选操作集生成基本算法中的不足，通过对图结构进行分解操作，提出了候选操作集生成改进算法，从而得到why-not问题的解释候选操作集。该改进算法减小了操作代价，提高了why-not问题的解释效率。

（4）在候选操作集的基础上，结合对查询图修改操作数要求最少的代价模型，分别利用贪心策略和回溯剪枝策略，从候选操作集中选取部分候选操作，并对最初的查询图做出相应修改，从而合理解释why-not问题。

（5）在真实数据集和合成数据集上进行了大量的实验测试和分析，验证了本文方法的可行性和高效性。

2 相关工作

2.1 why-not问题

目前，存在多种why-not问题解释模型，文献[1-4]阐述了不同数据和查询集中存在的why-not问题。文献[1]中Chapman等人提出了识别出使why-not元组过滤掉的操作的方法。Tran和Chan以Chapman的工作为基础，提出了通过从用户的反馈中收集whynot元组，执行查询重写操作，从而解释SPJA（select project join aggregate）查询中的why-not问题[2]。文献[3]中，He等人依据用户的偏好来修改k值和权值来解释top-k查询上的why-not问题。文献[4]解决了反向skyline查询中的why-not问题。文献[9-10]提出的算法可以快速有效地为why-not问题返回最小化解释。文献[11]中Islam等人提出了一种叫作FlexIQ（flexible interactive querying）的 SPJ（select project join）查询重写架构，它充分考虑了用户反馈的why和why-not问题。文献[12]实现了一个基于因果关系分析查询处理的框架模型。文献[13]提出了基于查询修改的解释模型，通过分析why-not问题和查询语句，得到一个新的查询语句，使得新的查询语句的查询结果包括原来的查询结果和why-not数据。文献[14-15]提到的数据世系对缺失结果的解释提供了依据。文献[16]利用初始查询中的关键字来解决Web文本查询中的why-not问题。近期，针对近似图匹配过程中的why-not问题，文献[8]利用图的星型结构表示方式，提出了两阶段解释算法，但是该文用星型结构存储图信息，存储空间较大，因而解释效率有待提高。

上述文献为本文的why-not问题解释提供了参考依据，但是与前人的研究工作不同，本文从修改原始查询图的角度出发，将研究重点放在如何解释用户所提出的why-not问题。

2.2 近似图查询

根据图查询匹配的精确程度，可以将图查询分为精确图查询和近似图查询。本文主要研究近似图查询。

针对近似图查询问题，Yan等人在2005年提出了一种基于特征的结构化过滤算法Grafil[17]。该方法结合基于结构查询模式的特点，采用NP难问题的最大集合覆盖方法，提高了时间效率问题。Yan等人在Grafil的基础上于2006年提出了PIS（partition-based graph index and search）算法[18]，在图数据库中建立了基于片段的索引。2006年He等人提出了一种基于树结构建立索引的查询算法C-Tree[13]，它采用闭包树建立索引，用闭包的思想来衡量近似，但是该方法在近似查询中结果的正确性得不到保证。

通过上述分析发现，绝大部分现有方法是在原始图数据库上执行相关操作，并未考虑用户所提出的查询图对查询结果的影响，同时这些方法不能合理地解释近似图查询过程中的why-not问题。鉴于此，基于对用户查询图作出合理修改的思想，本文提出支持近似图查询的why-not问题解释方法。

3 相关定义

定义1（图相似性度量方法）当给定两个图结构g1和g2，文献[15]利用公式λ(g1,g2)=|E(g1)|+|E(g2)|-2×|E(mcs(g1,g2))|来描述两个图之间的差异，其中|E(g1)|表示图g1的边数，mcs(g1,g2)表示图结构g1和g2的最大公共子图，|E(mcs(g1,g2))|表示图g1和g2的最大公共子图的边数。图相似性度量方法定义为：当图g1和g2之间的差异λ(g1,g2)小于等于阈值δ时，图g1和g2定义为相似，否则不相似。

例2图1中g1和g2之间的差异计算为：λ(g1,g2)=4+4-2×3=2。当给定图差异阈值为3时，图g1和g2为相似图结构。

定义2（候选修改操作集）候选操作包括增边和删边两种，增边操作是在查询图中增加部分边，记为add(add operations)，且用add(vi,vj)表示在查询图q中增加边(vi,vj)；删边操作是在查询图中删除部分边，记为del(delete operations)，且用del(vi,vj)表示删除查询图q中的边(vi,vj)。

基于增边和删边操作，将候选修改操作集表示为MOP(modification operations)，MOP中包括所有增边候选操作和删边候选操作。

例3为使查询图q与图g3之间的差异小于等于3，将查询图q修改成q*，如图2所示，需要一个修改操作，即del(b,e)，于是得到why-not问题解释候选操作集为MOP={del(b,e)}。

Fig.2 Converting query graph fromqtoq*图2 查询图q修改成q*

定义3（最小修改代价）通过增边、删边操作将图q修改成图q*所需的最少操作次数。假设每一次增边操作或者删边操作的代价均为1，将查询图q修改为q*的代价函数定义为：cost(q,q*)=∑op，其中op表示对查询图执行的修改操作。

例4接例3，根据定义2，可知将查询图q修改为q*需要一次删边操作，从而可得将查询图q修改为q*所需的最小修改代价为1。

综合上述内容，现给出问题1的描述。

问题1给定查询图q和图数据集G={g1,g2,…,gk,gk+1,…,gn}，根据用户的查询图q，以及图差异阈值δ，得到近似图查询结果集为R={ga,gb,…,gk}，针对用户提出的why-not问题W={gi,gj,…,gn}，要解决近似图查询过程中的why-not问题，就是要在满足图差异阈值δ的条件下，用最小的修改代价cost(q,q*)，将查询图q修改为q*，使近似图查询结果包含R和W。

4 近似图查询why-not问题解释

本章针对why-not问题的难点，提出了支持近似图查询的why-not问题解释框架。并在此框架的基础上，提出了why-not问题解释方法。

4.1 解释框架

本文提出的why-not问题解释框架如图3所示，已知图数据集G，查询图q，近似图查询结果R和why-not问题集W。根据查询图q和why-not问题集W，得到候选修改操作集MOP。选取候选修改操作集中满足代价模型的部分操作对初始查询图q进行修改，将q修改为q*。再利用修改后的查询图q*对图数据集进行近似图查询，使得最终查询结果中包含原始查询结果R和why-not问题集W。

Fig.3 Framework of explanation图3 解释框架

4.2 候选操作集生成基本算法

从问题1的描述可知，图的相似性最直观地表现在边结构的相似上，因此，为了得到对查询图的候选修改操作，需要综合考虑原始查询结果集R和whynot问题集W。为了满足用户的查询需求，通过统计出集合R和W中所有边的频率，得到一个边频率表，记为Fre-table，如图4（a）所示。该表包括两列，第一列为边的信息，第二列为相应边出现的频率，该频率值由相应边出现的频数值除以总边数求得。该频率表的统计过程是按照每条边所涉及的节点的字典序进行，每条边在表中出现且仅出现一次。为了对比每条边在集合R和W中的出现情况，将边频率表Fretable按频率值降序排序，得到结果如图4（b）所示。

接着，利用排序后的边频率表Fre-table，在原始查询图q中标出所有边的频率值，如图4（c）所示。对于出现在Fre-table中，却没有出现在查询图q中的边，用红色虚线标出，同时标出其频率值。

Fig.4 Basic algorithm to generate candidate operations图4 候选操作集生成基本算法

通过上述分析可知，要使why-not集合出现在查询结果中，那些在集合R和W中出现频率较高的边应该出现在查询图q中，那些出现频率较低的边则不应该出现在查询图q中。于是，通过对比原始查询图q和Fre-table可以得到候选修改操作，对于在Fre-table中有较高频率值却在查询图q中未出现的边，可以得到相应的增边候选操作，对于在Fre-table中有较低频率值却在查询图q中出现的边，可以得到相应的删边候选操作。

例5如图1，当给定图数据集G={g1,g2,g3}，查询图q，查询结果集R={g1,g2}，why-not问题集W={g3}时，用候选操作集生成基本算法生成候选修改操作的过程为：首先依据集合R和W统计得到边频率表Fre-table，如图4（a）所示；接着将频率表按照频率值降序排序，如图4（b）所示；最后将相应边的频率值在原始查询图q中标出，由于边(b,e)在集合G中未出现，故其频率值为0。从图4（c）发现边(b,d)有较高的频率值，且边(b,c)的频率大于边(b,e)的频率值，同时查询图q中原始存在的边的频率值均大于等于未出现边的最大频率值，于是得到候选修改操作为MOP={add(b,d),add(b,c),del(b,e)}。

现将边频率表的生成算法表述为算法1。

算法1边频率表生成算法

输入：近似图查询结果集R，why-not问题集W

输出：按频率值降序排列的Fre-table

2.For集合R和W中的每一个图结构gkdo

3.For图结构gk中的每一条边(vi,vj)do

4.If Fre-table中不包括边(vi,vj)，则将边(vi,vj)加入Fre-table，并将该边对应频率值设为1；

5.Else将边(vi,vj)在Fre-table对应的频率值加1；

6.End if

7.End for

8.End for

9.按边频率值对Fre-table进行降序排序；

人员素质是保障工作人员自身安全和提升工程质量的最直接和最基本的因素，所以在公路工程的施工过程中，需要全面提升工作人员的素质。在具体的工作开展中，对一线施工人员的素质提升方式为让其了解安全事故引发的后果，并讲解如何对这些事故进行规避，经过长时间的培训后施工人员的安全意识自然会获得提升。对于现场监管人员，培训内容为让其了解各类安保设施的佩戴方式和方法，同时也要让其了解各类机械设备的故障表现形式，通过及时发现安全隐患的方式降低安全事故的发生几率。而对于技术人员，施工单位可以建设全面追责制度，并要求这类人员主动研究专业知识以规避工程安全事故，防止在公路的运行中发生问题。

10.Return排序后的Fre-table。

根据算法1，假设图集合R和W中每个图的平均边数为|E|，则行2～3两重for循环的时间复杂度为|E|(|R|+|W|)。假设Fre-table中包含的边数为m，则行9排序操作的时间复杂度为mlbm。因此算法1的时间复杂度为O(|E|(|R|+|W|)+mlbm)。

4.3 候选操作集生成改进算法

从4.2节中候选操作集生成基本算法的描述可知，通过统计集合R和W中各边的频率，对比原始查询图q，能得到候选修改操作集，但是该方法不够直观，并未考虑集合R和W中每个图的结构特性。鉴于此，本节将综合考虑每个图的结构特性，并提出候选操作集生成改进算法。

图的结构特性可以从以下几方面考虑：节点信息、边信息、节点的度。文献[19]中，Anthony等人提出了图的星型结构表示方式，将图结构按照节点信息分解成不同的星型结构，但是该方法在分解时，每条边的信息被存储了两次，导致空间占用较大。在该文献的启发下，本节将图结构进行分解，为了减小空间占用，每条边仅存储一次，具体分解过程由算法2描述。

为了将每个图分解成多个图结构，算法2首先将gi分解后的结果集gi′初始化为空，并将图gi每条边赋权值0，这是为了使每条边在分解之后的结构中出现且仅出现一次，见行1。接着以图gi中的每个节点为根节点，与之相连的节点为叶子节点，构建树型结构，并使每条边在分解之后的所有树结构中出现且仅出现一次，见行2～6。对于分解之后的树结构，如果其叶子节点为空，则将ε加入结果集，否则将节点vs对应的树结构gis′加入结果集，见行7～8。最后返回结果集gi′，见行10。

算法2图结构分解算法

输入：图结构gi

输出：图gi分解之后的集合gi′

1.将集合gi′初始化为空，并将图gi每条边权值均赋为0；

2.For图gi中的每一个节点vs按字典序do

3.For图gi中与节点vs相连的节点vtdo

4.If边(vs,vt)的权值为0，则将边(vs,vt)加入以节点vs为根节点的树中，并将边(vs,vt)的权值设为1；

5.End if

6.End for

7.If节点vs的叶子节点为空，则将节点vs设为空ε，并加入结果集gi′；

8.Else将以节点vs为根节点的树gis′加入结果集gi′；

9.End for

10.Return结果集gi′。

根据算法2，假设图gi边数为|Ei|，则行1对图gi每条边赋值的时间复杂度为|Ei|。图gi节点数为|Vi|，节点的平均度为|Di|，行2～3两重for循环的时间复杂度为|Vi||Di|。因此算法2的时间复杂度为O(|Ei|+|Vi||Di|)。

例6给定例1中的结果集R、why-not集W和查询图q，利用算法2进行分解，得到的结果如图5所示。其中第一行表示图g1利用算法2分解之后的结果集，有g1′={g11′,g12′,g13′,g14′}，同理可得g2′={g21′,g22′,g23′,g24′}，g3′={g31′,g32′,g33′,g34′}，q′={q11′,q12′,q13′,q14′,q15′}。将结果集R和why-not集W分解之后的结果集记为R′，在本例中有R={g1′,g2′,g3′}。值得注意的是，原图中的每条边在分解之后的结构中仅出现一次，因此分解后的图结构g13′、g14′、g22′、g24′、g34′、q14′、q15′为空，用ε表示。

Fig.5 Improved algorithm to generate candidate operations图5 候选操作集生成改进算法

利用算法2将图结构分解之后，为了得到候选修改操作集，需要对比查询图q与图集合R和W中根节点相同的结构之间的差异。候选操作集生成改进算法由算法3描述。

算法3候选操作集生成改进算法

输入：分解之后的图集合R′={g1′,g2′,…,gk′}和q′

输出：候选修改操作集MOP

1.初始化候选操作集MOP为空；

2.For集合q′中的每一个分解结构q1i′do

3.For集合R′中每一个集合gj′中与结构q1i′相对应的结构gji′do

4.If结构gji′中存在边 (u,v)且q1i′中不存在边 (u,v)，则生成候选操作op=add(u,v)，并将该操作加入候选集MOP；

5.Else if结构q1i′中存在边 (u,v)且gji′中不存在边(u,v)，则生成候选操作op=del(u,v)，并将该操作加入候选集MOP；

6.End for

7.End for

8.ReturnMOP

算法3首先将候选修改操作集MOP初始化为空，见行1。接着，对于分解之后的查询图集合q′中的每一个结构q1i′，与所有gj′中与结构q1i′有相同根节点的结构gji′进行对比。对于那些在gji′中出现的且在q1i′中不出现的边(u,v)，说明如果该边出现在查询图中，则能减小查询图和why-not图之间的差异，因此生成增边候选操作op=add(u,v)，并将该操作加入候选集MOP；对于那些在q1i′中出现的且在gji′中不出现的边(u,v)，说明该边的出现，会加大查询图和why-not图之间的差异，因此生成删边候选操作op=del(u,v)，并将该操作加入候选集MOP，见行2～7。最后返回候选修改操作集MOP，见行8。

根据算法3，当查询图q中节点数为|Vq|，图节点的平均度为|Di|，集合R′中包含图个数为k时，则行2～7两重for循环的时间复杂度为O(k|Vq||Di|)。

例7接例6，给定用算法2分解之后的图结构集R′={g1′,g2′,g3′}和q′，利用算法 3 求解候选修改操作集。首先将q11′分别与g11′、g21′和g31′进行比较，发现q11′中的边在g11′、g21′和g31′中均出现，且g11′、g21′和g31′中出现的边在q11′中也出现，于是该列不产生候选操作。接着将q12′分别与g12′、g22′和g32′进行比较，边(b,d)出现在g12′中，却不出现在q12′中，于是产生增边候选操作op1=add(b,d)；边(b,c)和(b,d)出现在g32′中，却不出现在q12′中，得到增边候选操作add(b,c)和add(b,d)，由于add(b,d)操作与op1重复，故只产生候选操作op2=add(b,c)；边(b,e)出现在q12′中，却在g12′、g22′和g32′中未出现，于是产生删边候选操作op3=del(b,e)。接着将q13′分别与g13′、g23′和g33′进行比较，不产生候选操作，将q14′分别与g14′、g24′和g34′进行比较，也不产生候选操作。于是，最终用候选操作集生成改进算法得到的候选修改操作集为MOP={add(b,d),add(b,c),del(b,e)}，如图5中最后一行所示。

4.4 贪心算法

在4.2节和4.3节中分别用候选操作集生成基本算法和改进算法求得了对why-not问题解释的候选修改操作集MOP。通过上文分析可知，对于候选操作集中的每一个候选操作，对查询图的修改代价都是1。如果对查询图q执行候选操作集中的所有操作，能顺利地为支持近似图查询的why-not问题提供合理解释，但是从4.2节和4.3节的分析中会发现当执行某一个候选操作之后，有可能会改变原始结果集R中某一个图与查询图之间的差异，从而导致原始查询结果在修改查询图之后的查询结果中不出现，这不满足问题1的定义。因此，在生成候选操作集之后，需要从中选取部分候选操作，在修改代价cost(q,q*)最小的条件下，满足修改后的查询图q*的查询结果为{R,W}。本文采用贪心算法和回溯法选取候选操作集，本节介绍贪心算法选取候选修改操作。

本文的贪心策略为：对于初始查询结果集R和why-not问题集W中的每一个图，求解其与查询图之间的差异值，得到距离向量d=(λ(q,g1),λ(q,g2),…,λ(q,gk))。如果选择候选操作opi将查询图q修改为q*，这时重新计算查询图与集合R和W之间的差异值，得到新的距离向量d′=(λ′(q,g1),λ′(q,g2),…,λ′(q,gk))，将贪心函数定义如下：

式（1）中，ΔλW表示根据选择的候选操作opi将查询图修改为q*之后，W集合中图差异由不满足阈值δ变为满足阈值δ的图的个数；ΔλR表示R集合中图差异由满足阈值δ变为不满足阈值δ的图的个数；k表示集合R和W中包含的图的个数。该函数表示对于候选操作opi，变化的满足阈值要求的图差异个数与变化的不满足阈值要求的图差异个数的差值占整个图总量的比例，该比例越大，说明候选操作opi对why-not问题解释越有效。因此，用贪心策略选取候选修改操作时，总是选择当前条件下使f值最大的候选操作。该策略综合考虑了候选操作对集合R和W的影响，总是选择当前状态下最合理的操作，将其描述为算法4。

算法4贪心算法选取候选操作

输入：查询图q，候选操作集MOP，初始距离向量d=(λ(q,g1),λ(q,g2),…,λ(q,gk))，图差异阈值δ

输出：选取的候选操作集MOP′

1.初始化选取的操作集MOP′为空；

2.While向量d中存在不满足阈值δ的分量且候选集MOP中存在未选取的操作do

3.For候选操作集MOP中的每一个候选修改操作opido

4.对查询图q执行修改操作opi，得到q*，同时求得d′=(λ′(q,g1),λ′(q,g2),…,λ′(q,gk))为新的距离向量，根据向量d′分别求得ΔλW和ΔλR，利用式（1）求得候选操作opi对应的贪心函数值fi；

5.End for

6.选取贪心函数值fi最大的候选操作加入操作集MOP′

7.End while

8.ReturnMOP′

根据算法4，当候选操作集MOP中候选操作个数为|MOP|，图近似查询结果集R中图数量为|R|，why-not集合W中图数量为|W|时，算法4中行2～7的时间复杂度为O(|MOP|(|R|+|W|))。

例8结合例7，在得到候选修改操作集MOP={add(b,d),add(b,c),del(b,e)}之后，利用算法4从中选取部分候选操作，如图6所示。由算法4，首先计算得到初始距离向量d=(3,1,4)。图6中第一行对应候选操作op1，将查询图q根据操作op1修改为q*之后的结果在图中显示。接着分别计算修改之后的查询图q*与集合R和W中图的差异，得到λ(q*,g1)=4，λ(q*,g2)=2 ，λ(q*,g3)=3，于是距离向量更新为d′=(4,2,3)。接着利用式（1），求得 ΔλW=1，ΔλR=0，从而有f1=0.33。同理，对于候选操作op2求得f2=0，对于候选操作op3求得f3=0.33。

Fig.6 Greedy algorithm based candidate selection图6 贪心算法选取候选操作

根据本文选取的贪心策略，此时选取使f值最大的那个候选操作op1或者op3。如果选取的是op1，那么由更新后的距离向量d′=(2,2,3)可知，集合R和W中所有图的差异小于等于阈值δ，于是最终选取的操作集为MOP′={add(b,d)}。同理，如果选取的是op3，由更新后的距离向量d′=(2,0,3)可知，集合R和W中所有图也满足图差异小于等于阈值δ的条件，因此最终得到的操作集为MOP′={del(b,e)}。根据定义3中的代价函数，两种选取方式的操作代价均为1，因此两种操作集均可。

4.5 回溯法

在候选集选取阶段，需要选取MOP集的一个子集，同时满足操作代价最小。然而满足要求的子集是不唯一的，这就需要设计相应的策略来选取合适的操作子集。除了4.4节设计的贪心算法，本文还采用了回溯法来选取候选子集，并设计三种剪枝策略来剪枝不必要的操作，提高算法的运行效率。

对于本文中候选操作集的选取，首先需要对候选操作集MOP中的所有操作进行排序，排序依据是候选操作生成的先后。此外，为了满足图差异阈值δ的要求，需要求解初始状态时，查询图q与集合R和W中每一个图的差异，d=(λ(q,g1),λ(q,g2),…,λ(q,gk))，同时用λm表示当前距离向量d中的最大值。

根据排序后的候选操作构建操作树，每一层都代表一个候选操作，其中左孩子节点表示执行该候选操作，其右孩子节点表示不执行该候选操作。为了高效地选取操作代价最小的操作集，需要对构建完的操作树进行剪枝。

本文设计了三种剪枝策略：第一种是根据当前的λm值执行剪枝，当λm小于等于设定的图差异阈值δ时，执行剪枝操作。第二种策略需要记录下当前满足阈值δ的最少操作次数，记作minop，如果某一次选取操作时，已选取的操作个数达到minop，但是当前的λm值仍大于阈值δ，则执行剪枝操作。第三种是根据当前的λm值与剩余的候选操作个数的差值执行剪枝，当λm值与剩余的候选操作个数的差值大于设定的图差异阈值δ时，执行剪枝操作。

通过上述三种剪枝策略，能保证选取到的候选操作数最少，满足操作代价最小的要求；此外，通过回溯法选取候选操作能考虑操作的所有可能的组合情况，避免漏解或者解不全的情况。同时，通过剪枝操作能及时去除那些不满足要求的解，避免不必要的比较和计算，提高了算法的效率。

用回溯法选取候选操作的过程由算法5描述。

算法5利用回溯法选取候选操作。首先根据查询图q，查询结果R和why-not问题W求出初始状态下的向量d和λm值，并将minop的值初始化为MOP中操作数的个数，见行1。接着对候选操作集MOP中的候选操作进行排序，见行2。定义一个集合dSet存储构建操作数的过程中每个节点的向量值、λm值及到该节点时执行的操作。dSet中每个元素都是一个三元组，将初始(d,λm,null)存入dSet，见行3。遍历候选操作集中的每一个操作opi构建操作树，如果dSet中某个元素的值小于等于阈值，则更新minop的值，并将该元素对应的操作存入结果集MOP′。如果dSet中某个元素的值满足任意一种剪枝策略，则删除该元素，见行4～5。在遍历完所有操作后，返回结果集MOP′，见行6。

算法5回溯法选取候选操作

输入：查询图q，图差异阈值δ，查询结果集R，whynot问题集W，候选操作集MOP

输出：选取的候选操作集MOP′

1.根据查询图q、查询结果集R和why-not问题集W计算初始图差异向量d=(λ(q,g1),λ(q,g2),…,λ(q,gk))和初始λm值，初始化minop值为|MOP|；

2.根据候选操作的生成顺序对MOP中所有候选操作进行排序，得到MOP={op1,op2,…,opn}；

3.定义一个集合dSet存储构建操作树的过程中每个节点的向量值、λm值及到该节点时执行的操作，dSet中每个元素都是一个三元组，将初始(d,λm,null)存入dSet；

4.For每一个MOP中的元素opido

根据是否执行操作opi更新当前的集合dSet，如果dSet中某个元素的λm值小于等于阈值δ，则更新minop的值，并将该元素的操作存入MOP′，如果dSet中某个元素的值满足任意一种剪枝策略，则删除该元素；

5.End for

6.ReturnMOP′

从算法5可知，当候选操作集MOP中候选操作个数为|MOP|时，在最坏情况下，剪枝策略的作用得不到发挥，需要构建完整的搜索树，从而算法5的时间复杂度为O(2|MOP|)。

例9结合例8，当图差异阈值设为δ=3，查询结果为R={g1,g2}，why-not问题集为W={g3}时，利用算法3得到的候选操作集为MOP={add(b,d),add(b,c),del(b,e)}，此时利用算法5来选取候选操作，如图7所示。

Fig.7 Backtracking with pruning based candidate selection图7 回溯法选取候选操作

图7中每条边上的1表示执行该层候选操作，0表示不执行该层候选操作。从图7可知，当执行候选操作op1之后，图差异向量更新为d=(2,2,3)，λm=3，有λm≤δ，满足图差异阈值δ=3的要求，此时将minop更新为1，根据第一种剪枝策略，其后的操作树被剪枝（如图7中剪枝1）。当不执行候选操作op1，图差异向量和λm均不发生变化，于是向下扩展一层。当执行候选操作op2之后，图差异向量更新为d=(4,2,3)，λm=4，minop值不发生变化，此时不满足λm值小于等于阈值δ的条件，但操作数已经达到当前的minop值，根据第二种剪枝策略，其后的操作树被剪枝（如图7中剪枝2）。当不执行候选操作op1和op2时，有d=(3,1,4)，λm=4，于是向下扩展一层。当执行候选操作op3之后，图差异向量更新为d=(2,0,3)，λm=3，有λm≤δ，满足图差异阈值δ=3的要求，minop值不变。

通过上述分析，可知本例一共有两种why-not问题解释方案，即MOP′={add(b,d)}或MOP′={del(b,e)}。

5 实验结果与分析

本文将在不同数据集上进行大量的实验，用实验结果来证明本文方法是正确且高效的。

5.1 实验环境及实验数据集

本文实验采用的操作系统为Windows7，系统内存为8 GB，编程环境为Visual Studio 2012，实验代码用C++编程语言实现。

本文选取真实数据集StanfordSNAP（http://snap.stanford.edu/data/email-Enron.html）和合成数据集Synthetic来评估算法的性能。

（1）真实数据集StanfordSNAP。该数据集抽取于SNAP，其中的email-Enron通信网络中包含了超过50万件email的通信信息，该网络中的节点表示email地址，如果email地址i至少给地址j发送了一封邮件，那么在图中就存在一条从节点i到节点j的无向边。该数据集一共包括36 692个节点，183 831条边。从中抽取4个图集合G1、G2、G3和G4，它们分别包括1 000、2 000、3 000和4 000个图。每个图都是以某一个email地址i为中心，将与其有邮件往来的地址抽取出来。同时为4个数据集设计了3个不同的查询图qr1、qr2和qr3，以及相应的why-not问题。

（2）合成数据集Synthetic。该数据集是根据实验需求，随机生成4个图集合G1′、G2′、G3′和G4′，分别包括1 000、2 000、3 000和4 000个图。为4个数据集设计了3个不同的查询图qs1、qs2和qs3，并设计相应的why-not问题。

每个实验数据集中总节点数和总边数如表1所示。

Table1 Information of vertices and edges表1 数据集节点和边信息

查询图的设计主要是依据实验数据集G1、G2、G3、G4和G1′、G2′、G3′、G4′，从数据集中选取出部分图作为查询图。由于查询图选取自实验数据集，其结构和大小与数据集中图的结构和大小相同。此外，选取图数据集中与查询图的差异接近阈值的图作为why-not图。

本实验主要从两方面对支持近似图查询的whynot问题解释算法进行评估：（1）why-not问题解释算法的有效性；（2）why-not问题解释算法的时间性能。

5.2 why-not问题解释算法的有效性

对why-not问题解释算法的有效性从两方面进行评估：候选操作集生成基本算法和改进算法生成候选操作个数；贪心算法和回溯法生成why-not问题解释个数。

候选操作集MOP中候选修改操作的个数受到数据集大小的影响。图8（a）显示了当why-not问题包含一个图时，利用候选操作集生成基本算法，得到的候选修改操作个数随数据集SNAP的增加而变化的情况，图8（b）则显示了同样条件下，候选修改操作个数随合成数据集Synthetic的增加而变化的情况。从图中可知，随着数据集的增加，候选修改操作个数也随之增加。例如，当查询为qr1，SNAP数据集从1 000变化到4 000时，得到的候选修改操作个数分别为8、12、20和23。同理，当采用候选操作集生成改进算法时，也能得到相同的实验结果，如图9所示。

为了对比基本算法和改进算法在生成候选操作个数上的差异，将利用查询qr1、qr2、qr3和qs1、qs2、qs3得到的候选操作个数分别取平均值，得到的结果如图10所示。从图10（a）可知，对于同一规模数据集，用改进算法得到的候选操作个数比用基本算法得到的多，这是因为改进算法综合考虑了图的结构特性。从图中还可知，随着数据量的增加，得到的候选操作个数也会增加，因为当数据量增加时，近似图数量也会增加，相应图中的边数增加，从而候选操作数量增加，对于真实数据集SNAP和合成数据集Synthetic能得到相同的结论。

Fig.8 The number of candidate modified operations based on basic algorithm图8 基本算法生成候选修改操作个数

Fig.9 The number of candidate modified operations based on improved algorithm图9 改进算法生成候选操作个数

除了对比候选操作集生成基本算法和改进算法的差异，需要比较贪心算法和回溯法在生成why-not问题解释个数上的差异，如图11所示。

为了对比贪心算法（greedy algorithm，GA）和回溯法（back trace，BT）在生成why-not问题解释个数上的差异，将利用查询qr1、qr2、qr3和qs1、qs2、qs3得到的解释个数分别取平均值，得到的结果如图11所示。从图11（a）可知，对于同一规模数据集，用回溯法得到的解释个数比用贪心算法得到的多，这是因为回溯法比贪心算法考虑更全面，从而得到的解释个数更多。此外，随着数据量的增加，回溯法和贪心算法得到解释个数的差异逐渐增大。

通过上述实验结果及分析可知，候选操作集MOP中候选修改操作的个数随数据集的增加而增加，因而why-not问题解释的数量也随之增加。此外，不同的候选操作选取算法会得到不同数量的why-not问题解释个数。

综上可知，本文提出的why-not问题解释方法是有效且稳定的。

5.3 why-not问题解释算法的时间性能

本文why-not问题解释算法的有效性在5.2节得到验证，本节从时间性能方面对why-not问题解释算法进行评估。评估从以下两方面进行：基本算法和改进算法生成候选修改操作所需时间；贪心算法和回溯法选取候选操作所需时间。

首先考虑基本算法和改进算法生成候选操作所需时间，如图12所示。

为了对比基本算法和改进算法生成候选操作集所需时间的差异，将查询qr1、qr2、qr3和qs1、qs2、qs3生成候选操作所需时间分别求解平均值，得到的结果如图12所示。从图12（a）可知，对于同一规模数据集，用改进算法生成候选操作集的时间明显小于用基本算法的时间。

Fig.10 Comparison between basic algorithm and improved algorithm图10 基本算法和改进算法对比

Fig.11 Comparison between GAand BT图11 贪心算法和回溯法对比

Fig.12 Comparison between basic algorithm and improved algorithm图12 基本算法和改进算法对比

Fig.13 Comparison between GAand BT图13 贪心算法和回溯法对比

接着考虑贪心算法和回溯法选取候选操作所需时间。

用回溯法选取候选操作所需时间的实验结果如表2所示。从表中可知，真实数据集SNAP和合成数据集Synthetic候选操作选取时间差别不大。此外，对于同一个查询，随着数据集规模的增加，候选操作所需时间呈指数增长。例如，对于查询qr1，当数据集大小从1 000变化到4 000时，候选操作选取所需时间分别为464、1 856、7 424、14 848 ms，这与之前分析的算法5的时间复杂度为O(2|MOP|)相符合。

Table 2 Running time of candidate selection表2 候选操作选取时间

为了比较贪心算法和回溯法选取候选操作所需时间，对查询qr1、qr2、qr3和qs1、qs2、qs3生成解释所需时间分别取平均值，从图13可知，用贪心算法生成whynot问题解释的时间明显小于用回溯法的时间，这是由于用回溯法生成的解释数量多于贪心算法，从而贪心算法的时间小于回溯法。

综上，本节通过大量实验对why-not解释算法的有效性和时间性能进行评估，从实验结果可知本文算法是正确且高效的。

6 结束语

本文提出了支持近似图查询的why-not问题解释方法，通过统计边频率和图分解的方法，得到候选修改操作集，并利用贪心算法和回溯法选取候选操作，最终得到why-not问题解释。实验结果表明，本文的方法能够快速有效地为why-not问题返回合理的解释。

[1]Chapman A,Jagadish H V.Why not?[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data,Providence,USA,Jun 29-Jul 2,2009.New York:ACM,2009:523-534.

[2]Tran Q T,Chan C Y.How to ConQueR why-not questions[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,Indianapolis,USA,Jun 6-10,2010.New York:ACM,2010:15-26.

[3]He Z,Lo E.Answering why-not questions on top-kqueries[C]//Proceedings of the 28th International Conference on Data Engineering,Washington,Apr 1-5,2012.Washington:IEEE Computer Society,2012:750-761.

[4]Islam M S,Zhou Rui,Liu Chengfei.On answering why-not questions in reverse skyline queries[C]//Proceedings of the 29th International Conference on Data Engineering,Brisbane,Australia,Apr 8-12,2013.Washington:IEEE Computer Society,2013:973-984.

[5]Liu Jianzhuang,Lee Y T.A graph-based method for face identification from a single 2D line drawing[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,3(1):1106-1119.

[6]Lladós J,Martí E,Villanueva J J.Symbol recognition by errortolerant subgraph matching between region adjacency graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,3(1):1137-1143.

[7]Cheng J,Ke Yiping,Ng W,et al.Efficient query processing on graph databases[J].ACM Transactions on Database Systems,2009,34(1):1-48.

[8]Islam M S,Liu Chengfei,Li Jianxin.Efficient answering of why-not questions in similar graph matching[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(10):2672-2686.

[9]Zong Chuanyu,Yang Xiaochun,Wang Bin,et al.Minimizing explanations for missing answers to queries on databases[C]//LNCS 7825:Proceedings of the 18th International Conference on Database Systems for Advanced Applications,Wuhan,China,Apr 22-25,2013.Berlin,Heidelberg:Springer,2013:254-268.

[10]Zong Chuanyu,Wang Bin,Sun Jing,et al.Minimizing explanations of why-not questions[C]//LNCS 8505:Proceedings of the 19th International Conference on Database Systems for Advanced Applications,Bali,Indonesia,Apr 21-24,2014.Berlin,Heidelberg:Springer,2014:230-242.

[11]Islam M S,Liu Chengfei,Zhou Rui.User feedback based query refinement by exploiting skyline operator[C]//LNCS 7532:Proceedings of the 31st International Conference on Conceptual Modeling,Florence,Italy,Oct 15-18,2012.Berlin,Heidelberg:Springer,2012:423-438.

[12]Meliou A,Gatterbauer W,Moore K F,et al.Why so?or Why no?Functional causality for explaining query answers[R].Washington:University of Washington,2009.

[13]He Huahai,Singh A K.Closure-tree:an index structure for graph queries[C]//Proceedings of the 22nd International Conference on Data Engineering,Atlanta,USA,Apr 3-8,2006.Washington:IEEE Computer Society,2006:38.

[14]Cheney J,Chiticariu L,Tan W C.Provenance in databases:why,how,and where[J].Foundations and Trends in Databases,2009,1(4):379-474.

[15]Gao Ming,Jin Cheqing,Wang Xiaoling,et al.The research summarizes of data lineage management technology[J].Chinese Journal of Computers,2010,33(3):373-389.

[16]Chen Lei,Xu Jianliang,Lin Xin,et al.Answering why-not spatial keyword top-kqueries via keyword adaption[C]//Proceedings of the 32nd International Conference on Data Engineering,Helsinki,Finland,May 16-20,2016.Washington:IEEE Computer Society,2016:697-708.

[17]Yan Xifeng,Yu P S,Han Jiawei.Substructure similarity in graph databases[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data,Baltimore,USA,Jun 14-16,2005.New York:ACM,2005:766-777.

[18]Yan Xifeng,Zhu Feida,Han Jiawei,el al.Searching substructures with superimposed distance[C]//Proceedings of the 22nd International Conference on Data Engineering,Atlanta,USA,Apr 3-8,2006.Washington:IEEE Computer Society,2006:88.

[19]Zeng Zhiping,Tung A K H,Wang Jianyong,et al.Comparing stars:on approximating graph edit distance[C]//Proceedings of the 35th International Conference on Very Large Data Bases,Lyon,France,Aug 24-28,2009.New York:ACM,2009:25-36.

附中文参考文献：

[15]高明,金澈清,王晓玲,等.数据世系管理技术研究综述[J].计算机学报,2010,33(3):373-389.

Explaining Why-Not Questions onApproximate Graph Queries*

HE Dan,ZONG Chuanyu,WANG Bin,LI Jinxu,YANG Xiaochun+

School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China

2016-08,Accepted 2016-10.

Why-not questions aim to seek clarifications on the missing tuples for query results.Answering why-not questions on database queries not only helps user better understand the query,but also improves data quality and the availability of database.To enhance the availability of graph database,this paper proposes an efficient explaining technique for why-not questions on approximate graph queries.This technique gives explanations for missing graphs,as well as some suggestions how to modify the initial query graph to let the missing graphs appear in the query result set.Algorithm for answering approximate graph queries includes two parts:the first part is a candidate generation phase,which proposes the basic algorithm according to frequency information of edges,and the improved algorithm by graph decomposition operation to acquire candidate operation set.And in the second part,in order to minimize the cost of modifying initial query graph,greedy algorithm and backtracking are proposed separately to select candidate operations.Reasonable greedy function is designed for greedy algorithm.The pruning trees based on candidate selection are built and three strategies for selecting candidate operations from the candidate set are proposed.The final candidate operation set includes the reasonable explanations for why-not questions on graph queries.According to experiments,the algorithm proposed in this paper can efficiently generate reasonable explanations for why-not questions on approximate graph queries.

approximate graph queries;why-not questions;backtracking;pruning strategy

+Corresponding author:E-mail:yangxc@mail.neu.edu.cn

10.3778/j.issn.1673-9418.1608050

*The National Natural Science Foundation of China under Grant Nos.61572122,61322208,61272178,61532021(国家自然科学基金);the National Basic Research Program of China under Grant No.2012CB316201(国家重点基础研究发展计划(973计划)).

CNKI网络优先出版:2016-10-31,http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1650.014.html

HE Dan,ZONG Chuanyu,WANG Bin,et al.Explaining why-not questions on approximate graph queries.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1871-1885.

A

TP311.1

HE Dan was born in 1992.She is an M.S.candidate at School of Computer Science and Engineering,Northeastern University.Her research interests include approximate graph query and data provenance,etc.

贺丹（1992—），女，湖南湘潭人，东北大学计算机科学与工程学院硕士研究生，主要研究领域为近似图查询，数据世系等。

ZONG Chuanyu was born in 1985.He is a Ph.D.candidate at School of Computer Science and Engineering,Northeastern University.His research interests include data quality management and data provenance,etc.

宗传玉（1985—），男，山东潍坊人，东北大学计算机科学与工程学院博士研究生，主要研究领域为数据质量管理，数据世系等。

WANG Bin was born in 1972.He received the Ph.D.degree in computer science from Northeastern University in 2008.Now he is an associate professor at Northeastern University,and the member of CCF.His research interests include design and analysis of algorithms,databases and data quality,etc.

王斌（1972—），男，辽宁沈阳人，2008年于东北大学获得博士学位，现为东北大学副教授，CCF会员，主要研究领域为算法设计与分析，数据库，数据质量等。

LI Jinxu was born in 1992.He is an M.S.candidate at School of Computer Science and Engineering,Northeastern University.His research interests include database and data query,etc.

李金旭（1992—），男，河北承德人，东北大学计算机科学与工程学院硕士研究生，主要研究领域为数据库，数据查询等。

YANG Xiaochun was born in 1973.She received the Ph.D.degree from Northeastern University in 2001.Now she is a professor and Ph.D.supervisor at Northeastern University,and the senior member of CCF.Her research interests include theory and technology of database and data quality analysis,etc.

杨晓春（1973—），女，辽宁沈阳人，2001年于东北大学获得博士学位，现为东北大学教授、博士生导师，CCF高级会员，主要研究领域为数据库理论与技术，数据质量分析等。