目录
摘要
1、介绍
符号表示：Table1 为本文中常见的符号表示
2、关于GFDS的推理
GFDs的可满足性问题
GFDs的蕴含问题
3、GFDS的不一致检测
4、三个算法的介绍
4.1顺序算法
4.2并行算法的介绍
4.2.1复制图的并行算法
4.2.2碎片图的算法
本文提出一种图函数依赖，称之为GFDs。
GFDs捕捉属性-值依赖和实体拓扑结构，并且包含了CFDs是一个特例。
GFDs的满意度和蕴含问题分别是coNP-complete和NP-complete，即满意度和蕴含问题分别是决定是否存在一个非空的图满足Σ中的所有GFDs和Σ是否包含GFD。。
GFDs的验证问题是coNP-complete的
提出了两种并行可测量的算法用于检测GFDs的违规
本文提出了大量的例子，以便于读者理解概念的含义
例1：(1)知识库中的不一致是常见的：
函数依赖(FD)能够探测但上述的不一致问题，也可以用FD来捕捉垃圾邮件。
本文提出了一种称为GFDs的图函数依赖，有两个约束：1、图形模式表示拓扑结构的约束，用于识别定义依赖关系的实体。2、一个CFDs的拓展，用于指定实体属性值的依赖关系。
GFDs包含了FDs和CFDs，用于捕捉相同实体或不同实体之间的属性的不一致。
图G = (V, E, L, FA)中，V表示有限的节点集合；E表示有限的边集合；L表示节点和边的标签可分为L(v)和L(e)；FA(v)表示节点的属性与属性值的对应关系；
图形模式
，VQ是模式结点的集合，EQ是模式边的集合；LQ是给节点还有边分配标签的函数；
是标量的列表；
是参数数量，其等于节点的数量；µ是一个双射函数，将映射到VQ中，或找到节点对应在中对应的变量；使用通配符'_'作为特殊标签
图形模式匹配：在图G上找到与模型Q同构的子图，这个子图G′= (V′, E′, L′, F′A)；h是一个双射函数用于从节点VQ到节点VQ'的映射；而对于标签有LQ(u) = L′(h(u))，LQ(e) = L′(e') 其中e = (u, u′)，e′= (h(u), h(u′))。当然若 LQ(u)是通配符"_"，则LQ(u) = L′(h(u))总是成立。
是本文常使用的匹配向量，由h(x)组成。x是变量，是变量的列表。
图函数依赖：GFDs ϕ = 
,其中Q是图形模式，称为ϕ的模型；X和Y是两个
的两个字段集合。
GFD ϕ指定了两个约束条件：1、由模式Q施加的拓扑约束。2、由X → Y指定的属性依赖。 即GFD既要被Q约束也要被函数依赖约束，Q规定了GFD的范围，使得依赖关系X → Y只施加在由Q标识的每个子图中的顶点的属性上
举几个例子以说明图、图形模式、图形模式匹配以及图函数依赖的关系：
先学习一个新的概念：
满足
，首先将h(µ(x))表示为h(x)，以后就用h(µ(x))表示为h(x)了，因为x本是一个字段，µ是根据这个字段找到其节点。若存在v=h(x)且v.A=c则
满足c，若存在v=h(x)且v.A=y.B则满足y.B。而若X内的所有字段，都存在一个节点有满足字段的属性，则满足X，可表示为
。若X为空，则
对所有的
，若
则
，我们说图G满足GFD
记作G |= 。每当
就有
则说明
。若不满足X则无论满不满足Y都都成立，但是若满足X，则必须满足Y，才能成立，这就跟普通的蕴含关系一样，当X真时，Y必须为真，不然X->Y就为假了。
例1、
，其中X1是
，Y1由
和
组成。由Q1所示，x1为flight id，x2为flight出发的city，x3为flight到达的城市等。y1，y2,y3，y4，y5也是如此。因此GFD 
表示若实体x和y有相同的flight id则它们的离开城市以及目的地一定一样。但是从图中可以看出
，因为但是不满足Y：是因为h(x1).val=DL1,h(y1).val=DL1,则h(x1)=h(y1)，X1是。但是h(x3).val=NYC,h(y3).val=Singapore，二者不相等，所以不满足Y。所以
例2、
，次GFD表示没有实体能够满足y.val和z.val，因为X为空，所以有GFD满足X，可以推出GFD必须要满足Y，则这个GFD才成立。如下图所示通过图形模式匹配有h(µ(y))和h(µ(z))都是表示Canberra，所以二者值相等，所以GFD满足X->Y，所以
。
例3、
可以表示为x必须有一个属性A，不然这个图就不满足GFD了。
定理1：GFDs的可满足性问题是coNP-complete的
推论2: 定义于有向无环图的常数GFDs，其可满足性问题是coNP-complete的
引理3：当且仅当Σ不冲突时，GFDs集Σ是可满足的。
推论4:如果满足下列条件之一，GFDs的集合Σ总是可满足的:
1、Σ仅由变量GFDs组成
2、Σ不包含形式为
的GFDs
定理5、GFDs的蕴含问题是NP-complete的
推论6、当所有的GFDs都被定义为DAG模式，并且它们都没有形式
时，仅对于常数GFDs和变量CFDs，蕴含问题是NP-complete。
引理7、对于
和一个GFDs集合Σ，有Σ|=ϕ，当且仅当Y可以从Σ和X中扣除.
推论8、用树结构模式定义的GFDs的蕴含问题是PTIME的
命题9、GFDs的验证问题是coNP-complete。
定理10、存在并行可测量的算法，给一个GFDs集合Σ和一个复制到n个处理器的图G，在
并行时间内计算Vio(Σ,G)
定理11、存在并行可测量的算法，给定一个GFDs集合Σ，一个分好了的图G和n个处理器，计算Vio(Σ, G)在
并行时间内。
若
，则我们说
违反了
，其中GFD
，
是G根据图模式Q使用
匹配到的一个子图。我们将所有违反的添加到一个违规集合Vio(Σ, G)里。
而我们所谓的错误检测就是输入一个GFDs集合 Σ和一个图G，会有输出一个违反集合Vio(Σ, G)。我们称这个决策问题为GFDs的验证问题，用于判断是否G |= Σ，当然只有违反集合Vio(Σ, G)为空时，G |= Σ。
此算法使用了一个GFDs集合Σ，一个图G，一个单处理器来计算违反集合Vio(Σ, G)。我们称这个算法为detVio
执行如下：
刚开始时Vio(Σ, G) = ∅。枚举G中的模式Q中的所有
，检查是否存在
即是否存在，若违反了就添加到Vio(Σ, G)。
这种算法非常简单，执行起来的时间复杂度非常非常得高，所以对于大图来说是禁止的。
以上算法复杂度这么高，因此我们提出了一个用于解决此问题的并行算法，也就是复制图的并行算法和碎片图的并行算法
首先介绍一下新的符号和概念：
W(Σ, G)表示工作量，是算法计算所有违反集合Vio(Σ, G)所需要的消耗
t(|Σ|,|G|)表示最好的顺序算法在计算Vio(Σ, G)所消耗的时间
T(|Σ|,|G|, n)表示使用n个处理器通过并行算法来计算Vio(Σ, G)所使用的时间
表示Q的最大连通分量；
称为GFD的轴(pivot)；
是连通分量
的具有最小半径节点的标签，可通过
获得对应的节点；使用
表示半径的大小；使用
表示
称之为GFD的轴向量(pivot vector)；如下图所示
和
的轴向量分别是((x,1),(y,1)), ((x,1)), ((x,0),(y,0))和((x,3))
σ 是一个一对一的映射，从
映射到G中的节点，就是上面介绍的轴向量；
和
是不一样的，前者表示G中的节点，后者表示Q中的节点，是的候选(candidate)，当然它俩是对应的，分享相同的标签。
其中
是G中的片段，子图
是对所有
的
邻居
，它大于模型Q对应的子图。我们称
为图G中
的轴候选(pivot candidate)
W(Σ, G)是所有
的集合符号表示为
；是中所有的连通分量Qi的标签对应的轴候选与其对应的G的子图组成的
集合，一般只有1-2个，毕竟Q中的连通分量一般都是1-2个，可以看出W(Σ, G)包含，包含，三者是包含关系。
上面我们通过Q进行匹配得到的子图小于通过
得到的小于图G，如果使用来进行枚举，那么复杂度将会远小于使用G来进行枚举。
若
我们说错误测量算法是并行可测量的，当
时
成立，其中c和l是常数。直觉上使用的处理器数量越多则使用的时间越少，当然在下面的章节会论述这个直觉的错误的。
命题12: 1、负载平衡问题是NP-complete的。2、给定Σ, n和W(Σ, G)，在O(n|W(Σ, G)| + |W(Σ, G)| log|W(Σ, G)|) 时间内有一个2-近似算法来寻找平衡的工作负载分区
此算法先将图G复制到每一个处理器上，我们所要做的就是将工作量均匀的分配到每一个处理器上。
算法名称为repVal，由一个协调器
和n个处理器
组成。协调器上运行了一个程序bPar，处理器上并行地运行了程序localVio，运行过程为：
协调器的程序bPar先将工作量W(Σ, G)均匀地分为
，然后将n个
分别发送到n个处理器上。处理器上的程序localVio收到工作量之后，开始检测违规，并将违规放入
，处理完之后localVio将返回给bPar，bPar再将所有的合并成一个Vio(Σ, G)。过程如下图所示：
bPar是怎样进行工作量均匀分配的呢？
，其中X1是，Y1由和组成。
举个例子：我们使用flight的图和图模式，假设G1有9架飞机flight1–flight9，使用范围为n=3的分区有：
，然后根据分区再产生m=3个M,其中
，rflight和rflight'分别对应Q1中的x x1 x2 x3 和y y1 y2 y3。可以算出
M2包含了4-6,4-6和4-6,7-9. M3包含了7-9,7-9和7-9,1-3. bPar将M1、M2、M3分别发送个3个处理器，交由3个处理器处理。
若
收到9个工作单元{w1, . . . , w9}且评估大小为{22,22,26,26,30,30,24,28,28}，则的贪婪分配策略根据评估生成了一个3分区工作单位{{w1, w3, w9},{w2, w4, w5},{w6, w7, w8}}，之后再将之分到处理器S1, S2, S3。
localVio是如何进行工作的呢？
localVio通过
=
，这里有两个连通分量所以k等于2，
等于1，
表示x对应的flight；通过PV可以得到G的子图
我们举例处理器s1收到的M1为
。有中z bar等于
其中
，可生成子图。则有小工作量
。例有
，22表示
的节点和边数量总和为22. 然后localVio通过枚举的方法检测是否满足GFD，若不满足则将对应的那个h放入本地的 Vio(Σ, G)，直到所有的h都尝试之后，返回本地的 Vio(Σ, G)给bPar
此算法论文没有举例，以后遇到再补充对此算法的使用简介，此处只说了一些定义。
命题13: (1)双标准分配问题是NP-complete (2)在
时间内，存在一种2-近似算法来寻找具有最小通信成本的平衡工作负荷分配
本算法名为disVal。使用了一个协调器
和n个处理器
。disPar首先评估且分区工作量 W(Σ, G)，使得
在每个处理器上都是平衡的，且通信成本最小化。之后每个处理器并行地使用程序dlocalVio来探测局部违规
。最终
首先先介绍一下边界节点再介绍算法的详细工作流程：
是等于图G；
是图G的子图；
；每个子图都驻留在对应的处理器上；而边界节点由内节点和外节点组成，内节点是子图
中那些与其他碎片图有相连边的节点，因为
是直接从G上切割下来的图，那么就一定会有断掉的边，内节点就是中那些有断边的节点；外节点是原本与的内节点连接的其他碎片的节点。
disPar拓展了bPar通过支持1、考虑通信成本的工作量估算 2、双标准分配(Bi-criteria assignment)
那么disPar是如何进行工作量评估的呢？
使用了轴向量
，其中
是在
里
中的；
的局部候选
是在中的；有G中的
邻居图
；中的边界节点
；部分工作单元
（即分配到各个处理器的工作）使用
表示；若
则
使用占位符⊥表示；
是
组成的列表;
是
组成的列表，表示丢失数据；
若对于每个
都一个来自
的单元
的候选
则将
添加到
中去；
是
的总和；
是
的联合。注i ∈ [1, n]且
∈ Σ.
版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间：8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态
