0 引言

当前, 不确定数据广泛存在于各种传感器网络, 社交网络等各种应用中, 并已成为计算机领域的一个重要研究热点。不确定数据产生的形式多样.例如, 在信息抽取中, 一些学习算法(如, 条件随机场)经常产生不确定数据.当从多个数据源整合数据的时候, 冲突的数据就以不确定数据的形式存储在数据库中.

概率数据库中通常存在指数级别的可能世界(Possible World, 一个可能世界就是概率数据的一个实例), 使得对概率数据的操作非常耗时.不仅如此, 由于不确定性的累积和传播, 可能会降低查询结果的可用性.因此, 有必要降低概率数据库中数据的不确定性.

本文关注于概率RDF(Resource Description Framework, 资源描述框架)图查询的数据清洗, 对源点确定的有向无环查询图(Directed Acyclic Graph with Deterministic Source Points, DSG)查询的数据清洗进行分析.首先, 对查询模型做了介绍, 包括概率数据图模型和查询图模型, 并采用了熵来衡量数据的不确定性, 以此来对问题进行量化分析.然后, 本文提出了3种算法——朴素算法, 不稳定的剪枝算法和稳定的剪枝算法来选择出使得熵降低最大的那条边.最后, 在虚拟数据集和真实数据集上对提出的算法进行了验证.

本文剩余部分的组织形式如下:第1节介绍相关工作; 第2节介绍背景知识; 第3节对问题进行定义; 第四4节对问题进行详细分析; 第5节介绍解决该清洗问题的3种算法; 第6节讨论并报告实验结果; 第7节总结全文.

1 相关工作

在数据产生的过程中, 噪音、错误的数据、数据整集等都可能使数据变得不确定.因此, 关于概率数据库的研究十分火热.不同的查询类型相继被提出来, 例如top-$k$查询、子图搜索、最大(最小)查询和范围查询.文献[1-2]主要研究了关于概率关系数据库和概率XML数据库上的查询估计.同样, 在RDF数据库中也会出现不确定数据, 如Knowledge Vault^[3].针对概率RDF数据库, 不同的模型相继被提出来, 并给出了有效的查询算法.文献[4]介绍了从图数据观点来查询RDF数据.文献[5]介绍了概率RDF查询语言pSPARQL.在文献[6]中, Fukushige提出了使用贝叶斯网络模型来表示概率RDF数据.文献[7]研究了基于贝叶斯网络模型的概率RDF图数据库中搜索高置信度的同构子图的问题, 为了处理这个问题, 作者利用结构剪枝和概率剪枝来减少计算开销.文献[8]提出的概率RDF数据库模型中, 所有边都是互相独立的, 属性分为传递属性和非传递属性, 并且讨论了基于此模型的SPARQL查询.文献[9]介绍了另一种概率RDF模型, 认为同一个顶点相同属性的边是互斥的.

数据清洗是提高概率数据库查询质量的方法之一, 许多学者对概率数据库的清洗进行了研究.如, 在文献[10]中, 作者介绍了关于模式匹配的数据清洗.文献[11]介绍了关于由$x$-元组组成的概率数据库上的PRQ和PMaxQ查询的数据清洗, 并设计了PWS-quality度量标准来量化查询结果.众包平台的出现使得众包成为了数据清洗的重要手段.文献[12-13]介绍了如何利用众包来进行不确定数据上的top-$k$查询.文献[14]处理了带有噪音的实体关系的数据清洗问题, 提出了有效的算法(bDENSE)来选择要众包的问题.文献[15]研究了在众包工作者可能出错的情况下, 进行基于$x$-关系的概率数据库的数据清洗.但目前还没有对概率RDF数据库进行数据清洗的相关研究.本文中所定义概率RDF数据库类似于文献[9]中的模型, 不过没有传递属性, 并且在此模型下, 使用熵来度量查询质量, 进行关于DSG查询的数据清洗.

2 背景知识

RDF数据模型是用来描述网络资源的W3C标准.它广泛用于诸如语义网络的领域.一个RDF三元组可以表示成主体、谓词、客体(简写成$S$, $P$, $O$).在概率RDF数据库中, 谓词所关联的概率值表明了从主体到客体的关系的置信度.例如, 图 1包括了若干概率RDF三元组.

RDF三元组可以用图的方式来表示^[4].即, 对于每个RDF三元组($S, P, O$), $S$和$O$可以视为一个图中相邻顶点的标签, 谓词$P$则看作从$S$的一个属性, $O$为$S$的属性$P$的属性值.如图 2所示, 它与图 1中的RDF三元组等价.

SPARQL是一种用在RDF数据库上的标准查询语言.概率RDF数据库查询返回的结果是带有置信度的.为表示方便, 采用图 3所表示的数据图.例如, 在图 3所示的数据库中进行图 4所示的查询.表 1列出了对应的查询结果, 包括同构图和相应的概率值, 其中, PHI表示没有子图可以匹配查询图, 即查询结果为空.因此, 任何一个SPARQL查询可以被视为子图模式匹配问题, 就是找出那些与查询图的结构/标签相匹配的RDF图中的子图.这里假设查询图中的源点是确定的.如, 图 4中, $A$是源点并且它是确定的.

本文采用在概率数据库当中广泛用于建模查询处理的可能世界语义.图 5列出了图 3的所有可能世界.一个可能世界的概率等于它包含的所有边的乘积.一个同构图的概率等于所有包含这个同构图的可能世界的概率之和.例如, 同构图(1)的概率就是可能世界(2)和可能世界(6)的概率之和.

目前, 多数清洗问题主要集中在关系数据库和模式匹配领域, 很少有关于图查询的数据清洗, 更没有针对概率RDF数据库上SPARQL查询的数据清洗.本文要处理的是在一定的预算下清洗概率RDF数据库使查询质量提升最大化.这也是绝大多数清洗问题所采纳的思想.幸运的是, 在数据清洗中众包成为了一种十分有效的技术, 尤其是众包平台的出现, 比如Mechanical Turk(MTurk)^[16-17], 使得众包变得非常方便.在RDF图查询中, 清洗的目的是根据查询图找出一条边进行众包使得查询质量提升得最大.

为了说明, 表 1所列出的查询结果的质量为1.427(根据质量度量标准).假设RDF数据库被清洗了, 图 6为清洗过后的RDF数据图(假设边$AaD$被清除了).新的查询结果如表 2所示, 其相应的查询质量为0.88.可以看出, 清洗过后的查询结果的质量提升了.

3 问题定义 3.1 概率RDF数据库模型

根据先前陈述, RDF三元组可以被视为图.现在, 定义概率RDF图.

定义1   (概率RDF数据图)令$G=(V, E, P_E)$是一个有向图, 其中$V$是点集, $E$是边集, 每条边都关联着一个属性. $P_E:E\rightarrow\!\!\!\!\!\!^{^f} [0, 1]$是一个函数, 分配边集$E$中边的存在概率.这里, 有:

(1) 同一始节点同一属性的边是互斥的, 并且这些边的概率之和小于等于1, 即, $\Sigma_ke_{ijk}\leq 1$;

(2) 同一始节点不同属性的边或者不同始节点的边是相互独立的.

在图 3中, 有向边$CbE$和$CbF$是互斥的.这两条边都属同一个属性$C.b$.顶点$C$可能有其他属性, 图中未画出.边$AaD$和$CbE$是相互独立的, 因为它们的始节点不同.

在这种模型下, 每一个属性值是单值的, 也就是说, 某个始节点下同一个属性的边只有一个是正确的.

3.2 查询模型

定义2   (可能世界图, Possible World Graph, PWG)一个概率RDF图$G$的可能世界是概率RDF图的一个实例, 由所有顶点和这些顶点的每个属性下取一条边而组成.

明显地, 一个可能世界图(PWG)的概率等于它所包含的所有边的概率的乘积.

本文研究对某种特殊的RDF查询的数据清洗, 这种查询叫做源点确定的有向无环查询图查询(Directed Acyclic Graph Query with Deterministic Source Points, DSGQ). DSGQ具有2个特征:一是它的查询图是有向无环图; 另一个特征是查询图的所有源点, 即那些入度为0的顶点的标签都是确定的.

定义3   (源点确定的有向无环查询图, Directed Acyclic Graph with Deterministic Source Points, DSG)令$q=(V', E')$是一个有向无环图, 其中, $V'$由两种类型的顶点组成, 一种类型的顶点标签是由"?"起始的字符串, 另外一种则不是.集合$E$里面的边都关联着属性.那些入度为0的顶点(源点)的标签是确定的, 即, 标签不是由"?"起始的.

图 4中, 顶点$A$的入度为0, 它带有确定的标签"$A$".再看另外一个例子, 如图 7, 顶点$A$和$B$的入度为0, 它们各自有确定的标签.

定义4   (概率RDF数据库中的DSG查询, DSGQ)给定一个概率RDF图$G$和一个查询图$q$, DSG查询返回那些与$q$同构的子图和PHI.这些同构子图和PHI组成了查询结果集和一个概率分布函数$Pr:RS\rightarrow (0, 1)$.每一个同构图(或PHI)$r_i\in RS$的概率表示为$Pr(r_i)$, 并且有$\Sigma_{r_i\in RS}Pr(r_i)=1$.

由本文中的模型设置和查询图的特殊性, 可以看出同构图是互斥的.因此, 有$\Sigma_{r_i\in RS}Pr(r_i)=1$.

定义5   (DSGQ的不确定性)对于一个DSGQ, 给定结果集$RS$和概率分布函数$Pr()$, 用香农熵来衡量$RS$的不确定性

$ \begin{align} H({RS})=-\mathop \sum \limits_{r_i \in RS} Pr( {r_i } )\log Pr( {r_i } ). \end{align} $

(1)

例如, 在表 1中, 结果集的不确定性为$H(RS)=-0.56\log0.56-0.2\log0.2-0.24\log0.24= 1.427$(底=2).为了方便, 本文使用函数$h(x)=-x\log x$, 其中, $\log$是以2为底的对数函数.等式(1)可以简化成$H(RS)=\Sigma_{r_i\in RS}h(Pr(r_i))$.

注意log()函数中的底是2, 查询结果集的概率之和为1.香农熵在信息理论中是用来衡量不确定性的函数, 因此本文采用熵来衡量查询结果的不确定性.

定义6  (边正确性问题, Edge Correctness Question, ECQ)一个边正确性问题询问某条边两个顶点之间的关系是否正确.

图 8举例说明了一个ECQ的例子, 问顶点$A$和$C$之间的关系$a$是否正确.

定义7   (问题定义)给定概率RDF数据库和一个DSG查询图, 目的是针对该查询选择一条边进行众包使得查询结果的不确定性下降最大化.

这里将这条使得查询结果的不确定性下降最大的边称为最佳边, 表示成$e_{\max}$.

4 问题分析

用$e_{ijk}$表示结点$i$的属性$j$的第$k$条边, 将其相关的ECQ记作$E_{ijk}$.由于ECQ是一个是/否问题, 可以把它看作服从伯努利分布的随机变量.假设ECQ通过众包平台返回正确的概率等于该ECQ所对应的边在RDF数据库中成立的概率; 相反, 返回否的概率等于该边在RDF数据库中的不成立的概率.

将结果集$RS$分成4个子集: $R_1$表示包括边$e_{ijk}$的同构图的集合; $R_2$表示包括与$e_{ijk}$互斥的边的同构图的集合; $R_3$表示既不包括边$e_{ijk}$也不包括与$e_{ijk}$互斥的边的同构图的集合; $R_4$仅仅包括PHI, 即

$ \begin{align*} \begin{array}{l} R_1 =\{ {r_i {\vert }e_{ijk} \in r_i }\}, \\ R_2 =\{r_i \vert e_{ijl} \in r_i, l\ne k\}, \\ R_3 =\{r_i \vert e_{ijk} \notin r_i \wedge e_{ijl} \notin r_i, l\ne k\}, \\ R_4 =\{ {\rm PHI} \}. \end{array} \end{align*} $

根据以上假设, 有$Pr(E_{ijk}=1)=Pr(e_{ijk}=1)$和$Pr(E_{ijk}=0)=Pr(e_{ijk}=0)$.因此, 如果发布问题$E_{ijk}$后, 得到的返回结果为是$(E_{ijk}=1)$, 有

$ \begin{align} Pr({r_i \vert E_{ijk} =1} )=\left\{\!\! \begin{array}{ll} \dfrac{Pr( {r_i })}{Pr({e_{ijk} =1})}, & {r_i \in R_1, } \\ {0}, & {r_i \in R_2, } \\ {Pr({r_i }), }& {r_i \in R_3, } \\ 1-\dfrac{Pr( {R_1 } )}{Pr( {e_{ijk} =1} )}-Pr( {R_3 }), & {r_i ={\rm PHI}.} \end{array} \right. \end{align} $

(2)

如果得到返回结果为否($E_{ijk}=0$), 有

$ \begin{align} Pr({r_i {\vert }E_{ijk} =0} )=\left\{\!\! \begin{array}{ll} 0, & {r_i \in R_1, } \\ \dfrac{Pr( {r_i })}{Pr( {e_{ijk} =0})}, & {r_i \in R_2, } \\ {Pr( {r_i }), }&{r_i \in R_3, } \\ 1-\dfrac{Pr( {R_2 } )}{Pr( {e_{ijk} =0})}- Pr({R_3 }), &{r_i ={\rm PHI}.} \\ \end{array} \right. \end{align} $

(3)

然而, 在众包$E_{ijk}$之前并不能知道它返回的结果会是什么.但返回的结果要么是$E_{ijk}=1$, 要么是$E_{ijk}=0$.因此, 可以使用期望质量$(H(RS|E_{ijk}))$和期望质量提升$(E\Delta H)$来量化分析问题.令$E\Delta H$表示众包$E_{ijk}$后结果集的期望质量下降, 通过结合条件熵, 有

$ \begin{align} & E{\Delta }H = H({RS})-H(RS\vert E_{ijk} ) \notag\\ & \qquad = H({E_{ijk}})-(H({RS, E_{ijk} })-H({RS}))\notag \\ & \qquad = H({E_{ijk} })-H(E_{ijk} \vert RS). \end{align} $

(4)

问题的目标是最大化$E\Delta H$, 所以越大的$H(E_{ijk})$和越小的$H(RS, E_{ijk})$越好.注意$H(RS)$是常量.接着, 展开$H(E_{ijk}|RS)$.

$ \begin{align} &H(E_{ijk} \vert RS) \notag\\ &= \mathop \sum \limits_{r_i \in R} f({Pr( {r_i, E_{ijk} =1} ), Pr( {r_i, E_{ijk} =0})}) \notag\\ & = \mathop \sum \limits_{r_i \in R_1 }( {h( {{Pr}( {r_i })})-h( {Pr( {r_i })} )}) \notag\\ & \, +\mathop \sum \limits_{r_i \in R_2 } ( {h( {Pr( {r_i } )} )-h( {Pr( {r_i })} )} ) \notag\\ & \, +\mathop \sum \limits_{r_i \in R_3 } f( {Pr( {r_i } )Pr( {E_{ijk} =1}), Pr( {r_i })Pr( {E_{ijk} =0})} ) \notag\\ & \, +f( {Pr({\rm PHI}, E_{ijk} =1} ), Pr( {{\rm PHI}, E_{ijk} =0})) \notag\\ &= ( {h( {Pr( {e_{ijk} =1} )} )+h( {Pr( {e_{ijk} =0})} )} )Pr( {R_3 } ) \notag\\ & \, +h( {Pr( {e_{ijk} =1})-Pr( {e_{ijk} =1} )Pr( {R_3 } )-Pr( {R_1 })}) \notag\\ & \, +h( {Pr( {e_{ijk} =0})-Pr( {e_{ijk} =0} )Pr( {R_3 })-Pr( {R_2 })} ) \notag\\ & \, -h( {Pr( {\rm PHI} )}), \end{align} $

(5)

其中, $f(x, y)=h(x)+h(y)-h(x+y)$.

定义8   (有效属性)出现在结果集$RS$中的边对应的属性叫做有效属性.

定义9   (有效边)属于有效属性的边叫做有效边.

令$EA$表示有效属性集, $EE$表示有效边的集合.考虑表 1中的例子, $EA=\{A.a, C.b, D.b\}$, $EE=\{AaD, AaC, DbE, CbF\}$.

如果众包那些不属于有效边集里的边, 那么它将不会带来任何质量提升.下面的定理说明了这个性质.

定理1  如果$e_{ijk}\notin EE$, 那么$E\Delta H=0$.

证明  如果经由众包后$E_{ijk}=1$, 那么查询结果与众包之前一样, 即, $H(RS|E_{ijk}=1)=H(RS)$.如果$E_{ijk}=0$, 查询结果仍然与众包之前一样.因此, 众包$E_{ijk}$之后, 期望质量提升$E\Delta H=H(RS)-Pr(E_{ijk}=1)H(RS|E_{ijk}=1)-Pr(E_{ijk}=0)H(RS|E_{ijk}=0)=0$.

根据上述定理, 没有必要考虑有效边集$EE$之外的边.下一部分介绍3种算法来解决这个边选择问题.

5 算法实现

该部分介绍3种算法来选择使得$E\Delta H$最大化的边.它们分别是朴素算法(Naïve Algorithm)、不稳定剪枝算法(Unstable Pruning Algorithm)、稳定剪枝算法(Stable Pruning Algorithm).

由于$h(Pr({\rm PHI}))$是一个常量, 因此只需要计算$E\Delta H'$而非$E\Delta H$,

$ \begin{align} E\Delta H' =&( {h( {Pr( {e_{ijk} =1} )})+h( {Pr( {e_{ijk} =0})} )})(1-Pr( {R_3 } )) \notag\\ & -h( {Pr( {e_{ijk} =1} )-Pr( {e_{ijk} =1} )Pr( {R_3 })-Pr( {R_1 })}) \notag\\ & -h( {Pr( {e_{ijk} =0})-Pr( {e_{ijk} =0} )Pr( {R_3 })-Pr( {R_2 })} ). \end{align} $

(6)

因此, 寻找最大化$E \Delta H'$的边等价于寻找最大化$E\Delta H$的边.

5.1 朴素算法

朴素算法是解决本文问题的最基本算法, 其基本思想就是计算每条有效边的$E\Delta H'$, 选择出$E\Delta H'$最大的那条边即可.其具体过程是先访问查询结果集$RS$找出部分有效边, 再访问概率RDF数据图$G$找出剩余的有效边, 这样就获得了有效边集$EE$.然后计算集合$EE$中每条边的$E\Delta H'$.最后从中选出$E\Delta H'$最大的那条边.算法1描述了该过程.为了方便, 用$e'$来表示与边$e$互斥的任何边.

算法1  朴素算法

输入: $RS$结果集

输入: $G$概率RDF数据图

输出: $e_{\max}$使期望质量提升最大化的边

1.访问$RS$获得有效属性集$EA$

2.访问$G$获得有效边集$EE$

3. while ($e_{\rm cur}=EE.{\rm getNextEdge}())\neq {\rm null do}$

4.   while (${\rm iso}Q_{\rm cur}=RS.{\rm getNextIso}Q()) \neq {\rm null}$ do

5. if ${\rm iso}Q_{\rm cur}$包含$e_{\rm cur}$ then

6. $e_{\rm cur}\cdot p1\leftarrow e_{\rm cur}\cdot p1+{\rm iso}Q_{\rm cur}\cdot {\rm getProb}()$

7. else if ${\rm iso}Q_{\rm cur}$包含$e'_{\rm cur}$ then

8. $e_{\rm cur}\cdot p2\leftarrow e_{\rm cur}\cdot p2+{\rm iso}Q_{\rm cur}\cdot {\rm getProb}()$

9. else

10. $e_{\rm cur}\cdot p3\leftarrow e_{\rm cur}\cdot p3+{\rm iso}Q_{\rm cur}\cdot {\rm getProb}()$

11. end if

12.   end while

13.    $e_{\rm cur}\cdot {\rm delta}\leftarrow E\Delta H'$

14. end while

15. $e_{\max}\leftarrow {\rm null}$

16. $\max{\rm Delta}H\leftarrow0$

17. while ($e_{\rm cur}=EE.{\rm getNextEdge}())\neq $ do

18.   if $e_{\rm cur}.{\rm getDeltaH}()>\max{\rm Delta}$ then

19:      $e_{\max}\leftarrow e_{cur}$

20:      $\max{\rm Delta}H\leftarrow e_{\rm cur} \cdot {\rm getDelta}H()$

21.   end if

22. end while

23. return $e_{\rm max}$

5.2 不稳定剪枝算法

对于函数$f(x)=-\log x-(1-x)\log(1-x)$, 当$x \in [0, 0.5]$时单调递增, 当$x \in [0.5, 1]$时单调递减.可以将有效边按照$H(e)$的大小降序排列逐个访问, 并且用$H(E_{ijk}|RS)'$代替$H(E_{ijk|RS})$, 其中

$ \begin{align} H(E_{ijk}|RS)' =&( {h( {Pr( {e_{ijk} =1} )})+h( {Pr( {e_{ijk} =0})} )})Pr( {R_3 }) \notag\\ &+h({Pr( {e_{ijk} =1})-Pr( {e_{ijk} =1} )Pr( {R_3 })-Pr( {R_1 })} ) \notag\\ &+h( {Pr( {e_{ijk} =0})-Pr( {e_{ijk} =0} )Pr( {R_3 } )-Pr( {R_2 })}). \end{align} $

(7)

此外, 将已访问有效边中的最佳边的$E\Delta H'$记为maxDelta$H$.那么, 若当前有效边的$H(e)$小于maxDelta$H$, maxDelta$H$对应的那条边即为最佳边.

不稳定剪枝算法正是通过设置这种上限来加快算法的运行.该算法先获得有效边集$EE$, 再将其中的边按照$H(e)$的大小降序排列, 然后逐个访问这个降序列表中的有效边, 计算$H(E_{ijk}|RS)'$和$E\Delta H'$.当遇到某条边的$H(e)$小于$\max{\rm delta}H$时, 该算法终止.因为之后的边的$E\Delta H'$不可能大于$\max{\rm Delta}H$, 也就是说, 算法终止时$E\Delta H'$等于$\max{\rm Delta}H$的那条边就是最大化$E\Delta H$的边.算法2描述了该过程.

算法2  不稳定剪枝算法

输入: $RS$结果集

输入: $G$概率RDF数据图

输出: $e_{\max}$使期望质量提升最大化的边

1.访问$RS$获得有效属性集$EA$

2.访问$G$获得有效边集$EE$

3.将$EE$按照$H(e)$的大小降序排序

4. $\max{\rm Delta}H\leftarrow 0$

5. $e_{\max}\leftarrow {\rm null}$

6. while $e_{\rm cur}=EE.{\rm getNextEdge}())\neq {\rm null}$ do

7. while (${\rm iso}Q_{\rm cur}=RS.{\rm getNextIso}Q()) \neq {\rm null}$ do

8. if ${\rm iso}Q_{\rm cur}$包含$e_{\rm cur}$ then

9. $e_{\rm cur}\cdot p1\leftarrow e_{\rm cur}\cdot p1+{\rm iso}Q_{\rm cur}\cdot {\rm getProb}()$

10. else if ${\rm iso}Q_{\rm cur}$包含$e'_{\rm cur}$ then

11: $e_{\rm cur}\cdot p2\leftarrow e_{\rm cur}\cdot p2+{\rm iso}Q_{\rm cur}\cdot {\rm getProb}()$

12. else

13. $e_{\rm cur}\cdot p3\leftarrow e_{\rm cur}\cdot p3+{\rm iso}Q_{\rm cur}\cdot {\rm getProb}()$

14. end if

15. end while

16. if $H(e_{\rm cur})-EH(RS|E_{ijk})'>{\rm maxDelta}H$ then

17. ${\rm maxDelta}H\leftarrow H(e_{\rm cur}) -EH(RS|E_{ijk})'$

18. $e_{\rm max}\leftarrow e_{\rm cur}$

19. end if

20. if $H(e_{\rm cur}) < \max{\rm Delta}H$ then

21. return $e_{\max}$

22. end if

23. end while

5.3 稳定的剪枝算法

该算法中, 在构造$EE$时来计算每条边的$Rr(R_1)$.用一张二维表$EET$来记录出现在同构图中的有效边及相应的$Rr(R_1)$.如图 9所示, 第一列表示顶点的有效属性及该属性的所有效边的$Pr(R_1)$之和, 记作$Pr(Attr)$.每一行(除第一列)则为同一属性下的有效边及相应的$Pr(R_1)$.在遍历同构图的边时, 如果边还没有在$EE$中, 则在$EE$中和表中新增这条边, 且将$EE$中新增的这条边指向其表中的位置, 并将其所属同构图的概率加到新增有效边的$Pr(R_1)$上去; 如果$EE$中有, 直接把其所属同构图的概率加到的对应有效边的$Pr(R_1)$上去.然后, 根据图G向$EE$中增添没有出现在同构图中的有效边, 将这些有效边指向$EET$中其所属的属性.剩余步骤类似于不稳定的剪枝算法.算法3详细描述了该算法的过程.

在这种方法下, 如果一条边指向了$EET$的第一列, 那么其$Pr(R_1)$等于0;否则的话, 其$Pr(R_1)$可以从表中直接得到.对于一条边的$Pr(R_2)$, 它等于其对应属性的$Pr$(Attr)减去该边的$Pr(R_1)$.对应每条边的$Pr(R_3)$可通过$1-Pr(R_1)-Pr(R_2)$求得.

如图 9, 右边为二维表$EET$, 左边为有效边集$EE$. $ EET$的第一列为顶点属性及其$Pr(R_1)$, 该$Pr(R_1)$等于它包含的有效边的$Pr(R_1)$之和.边$CbF$是没有出现在同构图中的有效边, 它指向属性$Cb$.

算法3  稳定的剪枝算法

输入: $RS$结果集

输入: $G$概率RDF数据图

输出: $e_{\max}$使期望质量提升最大化的边

1.初始化二维表$EET$为空

2. $Pr({\rm PHI})\leftarrow1$

3. while (${\rm iso}Q_{\rm cur}=RS.{\rm getNestIso}Q()) \neq {\rm null}$ do

4. $Pr({\rm PHI})\leftarrow -Pr({\rm iso}Q_{\rm cur})$

5. while (${\rm edg}e_{\rm cur}\in {\rm iso}Q_{\rm cur}) \neq {\rm null}$ do

6. if ${\rm edg}e_{\rm cur}\notin EE $ then

7.在$EET$中寻找其所属的行, 若有则新增${\rm edg}e_{\rm cur}$, 其$Pr(r_1)$初始化为$Pr({\rm iso}Q_{\rm cur});$

若无则新增属性和${\rm edg}e_{\rm cur}$, 它们的$Pr(r_1)$都初始化为$Pr({\rm iso}Q_{\rm cur})$

8: $EE$中新增${\rm edg}e_{\rm cur}$并令其指向表中所属位置

9. else

10.其对应边和属性的$Pr(r_1)$加上$Pr({\rm iso}Q_{\rm cur})$

11. end if

12. end while

13. end while

14.访问$G$将没有出现在同构图中的有效边添加到$EE$中, 并令其指向到$EET$中相应的属性上

15.对$EE$按照$H(e)$的大小降序排序

16. while ($e_{\rm cur}=EE.{\rm getNextEdge}())\neq {\rm null}$ do

17. if $H(e_{\rm cur})-EH(RS|E_{ijk})'>{\rm maxDelta}H$ then

18. $\max{\rm Delta}H\leftarrow H(e_{\rm cur}) -EH(RS|E_{ijk})'$

19. $e_{\max}\leftarrow e_{\rm cur}$

20. end if

21. if $H(e_{\rm cur}) < \max{\rm Delta}H$ then

22. return $e_{\max}$

23. end if

24. end while

5.4 算法比较

为了比较3种算法的时间复杂度, 用$m$表示同构图数量, $s$表示查询图的边数, $a$表示有效性个数, $d$表示平均度数(这里, 某个顶点某个属性的起始于该顶点的弧的个数称为该顶点该属性的度数), $e$表示有效边数量, $n$表示顶点数.可以看出, 有关系$ad=e$.

在朴素算法中, 遍历同构图得到$EA$的时间复杂度是$O(ms)$.访问RDF图来获得有效边集的时间复杂度为$O(an)$.对于$EE$中的每条边, 计算$Pr(R_1)$、$Pr(R_2)$和$Pr(R_3)$的时间复杂度为$O(ms)$.最后, 耗时$O(e)$选出最佳边$e_{\max}$.因此, 该算法总的时间复杂度为$O(an+ems)$.

在不稳定的剪枝算法中, 找出最佳边, 它需要遍历$EE$中的前$k$个边.明显地, $k$的取值范围为1到$e$.寻找有效属性集和有效边集的时间复杂度与朴素算法是一样的.对有效边排序的时间复杂度为$O(e\log e)$.最后, 该算法耗时$O(kms)$选出最佳边$e_{\max}$.因此, 整个时间复杂度为$O(kms+an+e\log e)$.

在稳定的剪枝算法中, 构造二维表$EET$的时间复杂度为$O(ms(a+d))$, 并且耗时$O(an)$来构造完整的有效边集$EE$.然后, 对$EE$进行排序, 耗时$O(e \log e)$.最后, 耗时$O(k)$选出最佳边.因此, 该算法的时间复杂度为$O(ms(a+d)+an+e\log e+k)$.由于$d$比较小, 且$k$的取值范围为1到$e$, 可以忽略, 因此复杂度为$O(ams+an+e\log e)$.

虽然这三种算法都能够从有效边集中选出最佳边, 朴素算法对于每条有效边需要遍历所有同构图, 不稳定的剪枝算法通过设置上限只需访问前$k(1 < k\leq e)$条有效边, 稳定的剪枝算法通过构建表$EET$, 使得其时间复杂度与$a$相关, 而与$k$无关.当$k=e$时且不考虑$e\log e$, 不稳定的剪枝算法退化为朴素算法, 但是稳定的剪枝算法能够永远保证比朴素算法好.

6 实验

实验基于虚拟数据集和YAGO^[18]数据集分别进行分析.实验运行环境为Windows7专业版, 酷睿i3-3240和Java 1.8.0_25.

图 11的实验基于10 000个顶点随机生成4个虚拟数据集.它们的平均度数分别是2, 3, 4, 5, 如图 10所示.同一个顶点的同一属性的边是互斥的, 否则的话就是相互独立的.为了增加复杂度, 将顶点分成若干层次, 至少每个层的每个顶点大约从10 000个属性随机选择5到20个属性使这些点的部分边指向下一层顶点, 其他的边随机指向其他顶点.

图 10表示了4个平均度数不同的数据库的三元组个数, 并假设每个属性服从泊松分布.在每个数据库上使用50个平均直径为6的查询图做查询, 且这些查询图中顶点的出度最大为3.对于RDF数据库, 采用矩阵来表示.图 10表示的是对这些查询作数据清洗的的平均结果图.图 11(a)表示的是用不同的方法选择出来的边去众包所带来的平均$E\Delta H$, 其中, $R$表示从$EE$中随机选择一条边, $H$表示从$EE$中选择最接近0.5的那条边, $B$表示选择最佳边.可以看出, 选择最佳的那条边所带来的质量提升要远远超过其他两种方法.图 11(b)表示4组查询的平均有效属性集, 有效边和同构图个数的大小.可以看出, 有效边数量和有效属性数量满足$ad=e$.图 11(c)显示了选择最佳边的3种方法所需的时间开销, 查询时间不包括在内.其中, N表示朴素算法, U表示不稳定剪枝算法, S表示稳定的剪枝算法.可以看出, 朴素方法的时间开销最大，不稳定的剪枝算法在第一个数据库上要略快于稳定的剪枝算法, 在其余3个数据库上则相反, 这要取决于$k$和$a$的大小.

对于真实数据集, 本文使用部分YAGO数据集, 在此基础上增加从顶点到其他点的互斥边, 使其平均度数为4.另外, 假设每个属性服从泊松分布.在此数据集上, 使用50个平均直径为5的查询图做查询.从图 12看出, 选择最佳边所带来的质量提升是最高的, 而且两种剪枝算法要比朴素算法要快得多.

7 总结

本文首先构建了概率RDF数据库和其相应的查询模型.接着, 基于这个模型对DSG查询作数据清洗并且使用熵来量化查询结果的不确定性.此外, 通过分析问题, 对众包某条边所带来的质量提升进行量化, 并且找出了影响它的因素.然后介绍了3种算法来找出最佳边, 并分析了它们的复杂度.最后, 通过实验对比验证了算法的正确性和效率.