[论文阅读]《Discovering Graph Functional Dependencies》阅读笔记

2023-09-05 阅读 89 评论 0

摘要：总结：本文介绍了发现图函数依赖，更加清晰地介绍了可满足性问题、蕴含问题以及验证问题（可满足性问题是寻找，蕴含问题是判断|=，验证问题是判断G|=）全文以约化为中心致力于寻找无冗余GFDs集合 c，在寻找的过程中需要判

总结：

本文介绍了发现图函数依赖，更加清晰地介绍了可满足性问题、蕴含问题以及验证问题（可满足性问题是寻找Σ，蕴含问题是判断Σ|=φ，验证问题是判断G|=Σ）全文以约化为中心致力于寻找无冗余GFDs集合 Σc，在寻找的过程中需要判断是否Σ|=φ，以及G|=Σ。定义了一个支持度以及它的阈值，支持度就是用于表示中既得G|X，也得G|Y的节点的个数，这就排除了那些G不满足X的情况，毕竟这种情况虽然根据蕴含成立了，但是所表示的数据意义不大，所以使用了支持度这个东西来尽量的消除GFD内的冗余数据；本文还构建了一棵树，树的水平增长为模式Q的字段树的构造，树的垂直增长为模式的约化，通过从一个节点不断地增长节点和边，即它的支持度在不断的减少，当减少到再减少一下就变成负的GFD时，这就是我们要的最小约化GFD了；当最小约化GFD再减少一下就会得到最小重要约化GFD也是负的GFD，也就是说这个GFD增加一个节点或者边，那么它的支持度低于阈值。我们所要寻找的GFD就是不包含冗余和琐碎的GFDs以及捕捉规律和约束的频繁GFDs，而最小约化GFDs就是这种GFD，即不大也不小，正好合适。

本文分别介绍两个算法SeqDisGFD和ParDis，前者先生成k-bounded GFDs集合Σ，这个集合的内的GFD模式Q的半径为k，且满足阈值，再通过蕴含问题来不断的减少Σ，最终这个集合Σ通过验证问题可以得到最终的cover GFDs Σc，这个Σc是不含冗余GFD的集合。而ParDis则是将SeqDisGFD的三个步骤并行化了，提高了运行的效率。

1、符号介绍

有向图G = (V,E,L,FA)，其中V是有限的节点集合；E是(v,v')中v到v'的边的集合，v和v'是V中的节点；L是节点和边的标签，L(v)∈Θ，L(e)∈Θ；FA是一个等式元组；

若对于每个节点v和边e，V'⊆ V，E′⊆ E，L′(v) = L(v)，FA'(v) = FA(v)，则G'是G的子图，表示为G'= (V′,E′,L′,FA')

图形模式，其中VQ是模式节点的集合；EQ是模式边的集合；LQ是模式节点和模式边的标签；是变量的列表；µ一个将映射到VQ的双射函数；

模式匹配：图G中模式Q的匹配是一个子图G′，G′=(V′,E′,L′,FA')对于Q来说是同构的，也就是说它俩的拓扑结构相同，即存在双射函数h从VQ到V'的映射使得：

（1）对于任意节点u ∈ VQ，有L′(h(u)) ⪯ LQ(u)

（2）当且仅当e′= (h(u),h(u′))是G'中的一条边且 L′(e′) ⪯ LQ(e)时，则e = (u,u′)是Q中的一条边

这的模式匹配为什么是⪯而不是=呢？因为图形模式中存在有通配符"_"，通配符表示任意符号大于别的标签。

要从Q中的x映射到G中的节点v，本来应该是h(µ(x)) = v的，由于表示的比较麻烦，省去了µ，直接写成h(x)=v就能表示x对应Q中的节点到G中节点的映射

图函数依赖GFD：其中是图形模式，称为φ的模式；X和Y是的两个字段集合。

GFD φ是拓扑约束Q和属性依赖X → Y的组合，Q指定了φ的范围，使得X→Y只适用于Q的匹配

语义：如果h满足X中的所有字段x，使得h(x)=v且h(x).A = v.A = c，则我们称h满足X，表示为

表示h满足X 蕴含 h满足Y；

如果G中Q的所有匹配都有 |= X → Y，则称为图G满足GFD φ，表示为G |= φ

如果Σ中所有的φ，都存在G |= φ，则称为G |= Σ

正和负（Positive and negative）：这种形式的GFD称之为negative，即在G中的Q的匹配h使得h |=X；如果这个GFD不是负的，那么它就是正的。

当X=∅时，它说在一个图中，不存在Q的匹配，即表示这个Q是非法结构的

当X≠∅时，表示模式Q和条件X的组合是“不一致的”。

三个经典的问题：

可满足性问题：存在一个图G有： 1、G|=Σ ； 2、Σ中存在一个的GFD Q，这个Q是在G中有一个匹配，那么这个GFDs就是可满足的。

蕴含问题：给定一个GFDs集合Σ和另一个GFD φ，是否Σ|=φ，蕴含分析对于计算已发现的GFDs的覆盖和消除冗余GFDs是必要的。

验证问题：给定一个GFDs集合Σ和一个图G，是否G|=Σ

三个问题的区别是：可满足性问题是寻找Σ，蕴含问题是判断Σ|=φ，验证问题是判断G|=Σ

固定化参数可处理：如果存在可计算函数f和P的算法，使得对于P的任何实例(x,k)，需要O(f (k)·|x|c)时间才能找到解，其中c是一个常数，则称为固定参数可处理。其中在传统的复杂性理论中，x是一个输入，k是描述x结构的参数。

如对于一个GFDs的集合Σ，我们使用k来表示的，也就是用k来表示Q的定点数量。有了参数，那么上面的三个问题就多了参数k。

定理1、对于GFDs，蕴含问题和可满足性问题都是用参数k处理的固定化参数，但是即使有参数k和d，验证问题仍然是co-W-hard，其中d表示图G中节点的最大度。

如果从模式Q '到Q的子图存在一个同构，则GFDφ'被嵌入到模式Q中

enforced(ΣQ) 是一个等式原子的集合，这些等式必须被强制于图G中以满足Σ，如若x.A=c且y.B=c在enforced(ΣQ)中，则x.A=y.B∈ enforced(ΣQ)；亦或者如果是在ΣQ中，则Y ⊆ enforced(ΣQ)；亦或者中，若X可以由ΣQ导出，则Y也在ΣQ中。也就是跟若ΣQ | φ且ΣQ 满足X，则ΣQ必满足Y 一个道理，若X中的等式可由enforced(ΣQ)导出，则Y中的等式也得由enforced(ΣQ)导出，所以Y也必须在enforced(ΣQ)中；

closure(ΣQ, X) ，对于嵌入在Q中的GFDs集合ΣQ，closure(ΣQ, X)满足：X ⊆ closure(ΣQ, X)；如果在ΣQ中且如果X'中所有字段可以由closure(ΣQ, X)通过等式原子导出，则Y' ⊆ closure(ΣQ, X)。当X等于空时，enforced(ΣQ)等于closure(ΣQ, X)。若x.A=c,x.A=d当时c≠d，则closure(ΣQ,X)是冲突的。当且仅当closure(ΣQ, X)是冲突的或者l ∈ closure(ΣQ,X)，则Σ |= φ，closure冲突就是说Σ 不满足X，则Σ 不论满不满足Y，Σ 都是满足φ的，l ∈ closure(ΣQ,X) 就是说Σ | l ，当Σ | l 时，无论Σ 是否满足X，Σ都满足 φ。

k-clique问题：给定一个无向图G和一个自然数k，在G中是否存在一个大小为k的小团

k-bounded GFDs： 当的节点个数小于等于k时，就说模式是k-bounded的，而如果Σ中的所有都是k-bounded的，则这个GFDs集合Σ就是k-bounded的。

命题2：当k为常数时，k有界的GFDs的可满足性、蕴含性和验证性问题都在PTIME中

2、DISCOVERY PROBLEM

2.1 符号定义

本节的目的是找到GFDs集合Σ使得G|=Σ

不重要的GFDs：对于，如果X等价于false或者l能够通过等式的传递性由X导出，那么这个GFD就是不重要的，也就是说能够被满足的就是不重要的。

表示的是Q约化了Q'，如果从Q'中删除节点或边亦或者Q'的一些标签改成了通配符_得到Q，也就是说Q的节点和边比Q'少或者有限标签表示为_，即Q1≪ Q2是Q1约化Q2，Q1的节点或边要比Q2少一些，亦或者Q2更加具体一些。

轴pivot：对于属于的一个变量z，称之为Q的轴，对于G中的所有结点v，都存在G中的Q的一个匹配h，使得h(z)=v，由节点v的dQ邻节点组成，dQ是从节点v到最远的节点需要dQ跳。也就是在Q中找一个变量z，通过h将z映射到G中对应的节点，然后得到一个G的子图，子图的中心是h(z)，半径是dQ

如果存在一个从Q1到Q2的同构映射 f 使得（a）f(z1)=z2 其中zi是Qi的轴（b）f 映射X1中的变量和 l1 到X2中的变量和 l2，使得f (X1) ⊆ X2且f (l1) = l2 （c）通过映射f 或 f (X1) ⊊ X2 有 Q1≪ Q2 ，那么就说φ1约化φ2表示为：φ1≪ φ2

举个栗子：，其中X1={y.type="film"}，l是x.type="producer" ，以x为轴。

考虑一个以x为轴的GFD，其中是通过给Q1添加一条边(y,z)得到的，z的标签是award；是X1∪ {y.name = ‘Selling out’}，φ1≪。

考虑GFD，其中由y.name="Selling out"组成，因为X1⊈则φ1

对于任意的GFD φ′≪ φ，如果G|=φ 但是都有G|≠ φ′ ，则称一个正的GFD φ在图G中被约化了。如果它既是重要的又约化的，则它在G中是最小的。即这个φ′ 有G|≠ φ′且φ′≪ φ，G|=φ，则称φ'是最小的

一个约化的正φ 保证如下：1、左约化，即对于任何合适的真子集X'⊊ X，有，因此X不包含冗余的字段。 2、模式约化，即对于任何满足≪ 的，有

一个约化的负φ 如果是通过（1）增加一条边到Q中，以此获得 φ = 或（2）增加一个字段到X中以此获得 φ =从一个正的最小的GFD的延伸，那么这个负的GFD φ是最小的。也就是说它是由模式Q或字段X上到ψ的最小变化触发的。

最小GFDs 集合Σ：如果对于任何φ ∈ Σ, 有Σ Σ \ {φ}，即Σ中不包含冗余的GFDs。

图G中Σ的一个cover Σc是Σ的一个子集使得（a）G|=Σc （b）Σc≡Σ （c）Σc上所有的GFDs都是最小的（d）Σc子集是最小的，也就是说Σc不包含冗余或不重要的GFDs

支持度：考虑，φ的支持度定义为Q在G中满足X→Y的匹配数。例如，考虑模式Q[x]包含一个标记为person x的节点，Q ' [x,y]包含从person x到person y的一条边，标记为hasChild。在现实生活中的图G中，我们经常发现Q '的支持度大于Q，虽然Q是Q'的子模式，因为一个人可能有多个孩子;

接下来提出一个GFDs的支持度的概念，关于它的模式和它的属性相关性的支持度模式支持度：对于G中Q的所有匹配h(z)，这个由h(z)推导出与z匹配的节点集表示为Q(G,z)，而模式Q的支持度被定义为supp(Q,G) = |Q(G,z)|。它量化了G中满足由Q在z处“枢轴”构成的拓扑约束的实体的频率。

定义（反单调性约束）：当且仅当对于所有项目集S和S'时，约束C是反单调的：如果S⊇S'和S满足C，则S'满足C。

关系测量：用于量化Q中的变量依赖性，定义了GFD φ的关系ρ(φ,G)为，其中Q(G,Xl,z)表示Q(G,z)的子集使得|X 和| l ，这个相当于是中，Q满足X和l，排除了Q只满足X和Q既不满足X又不满足l。可以验证只要G|=φ，Q(G,X → l,z) = Q(G,z)，则ρ(φ,G)=1了，这不能准确的描述X和l 的关系。

图G中正GFD φ的支持度定义为：supp(φ,G) = supp(Q,G) ∗ ρ(φ,G) = |Q(G,Xl,z)|.

定理3、对于任意图G和重要的正GFDs φ1和φ2，如果φ1 ≪φ2，则supp(φ1,G) ≥ supp(φ2,G)

负的GFDs的支持度：由于负的GFDs无法被满足，所以无论如何都有Q(G,Xl,z) = ∅，则不再使用Q(G,Xl,z) = ∅来定义负的GFDs的支持度。

现实生活中只关心有正GFDs通过增加一步所变成负GFDs，则负的GFDs 的支持度定义为，其中（1）若X= ∅，Φ′由模式Q'组成，这些模式Q'有相同的轴z使得Supp(Q',G)>0，且Q'是通过去除Q的边（也有可能是节点）得到的。（2）若X≠ ∅，Φ′ 由正的GFDs φ'= 组成，这些GFDs有相同的轴z使得G|=φ' ，X中存在字段l'使得X=X′∪ {l′}

如果supp(φ,G)≥ σ，其中σ是一个支持度阈值，则说GFD φ是频繁的。

正负GFD的意义：(1)对于正的GFDφ，其支持度量化了存在并符合φ的实体;(2)对于负GFD φ，其支持度由正GFDφ′的支持度所决定;也就是说，负GFDs描述了观察世界中“不存在”的案例;未知数据对负GFDs的发现没有影响。

2.2 Discovery 问题

Discovery 问题就是以一个图G、一个大于2的自然数k、一个大于0的支持度阈值 σ作为输入。得到输出所有k-bounded最小GFDs φ的cover Σc，这个所有k-bounded最小GFDs φ是σ-frequent，即supp(φ,G) ≥ σ

2.3 顺序GFD发现算法 SeqDisGFD。

算法大概：算法SeqDis以k^2迭代运行。在每次迭代i，它发现并存储所有大小为i(有i条边)的最小σ-频繁GFDs到集合Σi中。在第一次迭代中，它通过初始化带有单节点模式的频繁GFD的GFD生成树来“冷启动”GFD发现。然后，通过交错两个水平生成过程扩展treeT:垂直生成扩展图模式Q，水平生成生成依赖项X→y。在每次迭代i (0 < i < k^2)， SeqDis生成并验证GFD候选项，并填充tree T的水平-i部分。

模式验证：算法SeqDis首先执行垂直生成，这将在T的 i 层(稍后将讨论)生成新的图形模式。每个模式Q'通过添加新边e(可能带有新节点)扩展i−1层模式Q。然后执行模式匹配，为i层的所有模式查找匹配项。

GFD验证：然后，它执行水平生成，这将一组文字与T i层上新验证的图形模式关联起来，以生成一组GFD候选对象。对每批GFD候选对象进行GFD验证，寻找处于Σi的GFD，即满足G的i层候选对象，这些候选对象频繁且最小。当与i层模式相关的所有GFD候选对象都被验证后，验证过程终止。

SeqDisGFD算法由（1）SeqDis 给定输入G,k, σ，发现k-bounded最小 σ-frequentGFDs的集合Σ；（2）SeqCover给定Σ，计算Σ的cover Σc

SeqDis

用C(k,G)表示图G中有k限的GFD候选数。算法SeqDis检查C(k,G)多个候选数，并对每个候选数进行验证。

定理5：存在一种用于GFD发现的算法DisGFD，它相对于SeqDisGFD是可并行扩展的。

生成树：GFD候选者的生成由树T控制，其中T=，每个属于的节点v在 i 层存储了一对，其中v.是一个有i条边的图形模式；v.lvec是一个向量，其中每个条目lvec[l]记录一个以字段l为根的字段树。这的 l 是x.A = c 或 x.A = y.B，x，y属于。

举个栗子：GFD φ1= Q1[x,y](y.type = “film” → x.type =“producer”)，GFD φ4= Q′1[x,y,z]({x.type = “producer”,z.name =“Academy best picture”} → y.type = “film”). 下图就是一棵GFD生成树T，就只有两个节点，上面那个节点存储了v(Q1,Q1.lvec)，其中Q1指的是下图右边那个Q1，Q1.lvec则是一个以x.type='producer'为根的树，相当于将φ1的函数依赖弄成了一棵树

第二层的节点存储了v(Q1',Q1'.lvec)，而Q1'.lvec 以y.type='film'为根节点

因为Q1'是通过给Q1增加一条y->z的边得到的，所以Q1到Q1'有一条边。对于第i层的φ=，长度|X|最大为J=i |Γ| ( |Γ| + 1)，其中Γ由G中的属性组成

GFD生成（GFD Spawning）生成树T通过执行以下两个“原子”操作生成新的GFD候选对象。

垂直生成（Vertical spawning） 操作VSpawn(i) 通过向i-1层的每个模式v.Q增加一条边e的方式创建新的节点v'.Q'，也就是垂直地增加了一条e(v,v')的边。如上图Q'就是通过向Q添加一条边e=(y,z)得到的。

水平生成（Horizontal spawning） HSpawn生成带有属性和常量的字段。HSpawn(i,j)在生成树的第i层的字段树的第j层执行，它产生一个GFD候选者φ=集合，其中Q的范围覆盖了第i层的模式，|X|=j ，并且X内的字段和l 来自于 Γ 的属性，而G中的常数则由VSpawn收集

在模式Q和字段l处，一旦证实G |= ， HSpawn就停止展开X。VSpawn在supp(Q,G) <σ时停止展开Q。这些策略确保了GFDs发现在实践中的可行性。

引理4：对于GFDs的cover Σc 大于支持度σ，

（a）Σc不包含不重要的GFDs φ；

（b）对于任意φ=，如果G|=φ，则如果X⊊ X′，Σc不包含；

（c）如果GFD φ=有支持度supp(Q,G)<σ ，则如果Q ≪ Q′，Σc不包含

发现负GFDs：使用来存储负的GFDs。在验证过程的每次迭代i中，SeqDis在模式匹配中先通过触发负垂直NVSpawn以此了拓展VSpawn来查找case (a)中的负GFDs，再通过触发负水平NHSpawn以此了拓展HSpawn来查找case (b)中的负GFDs。

case a：Q通过向Q'添加一条边得到，其中supp(Q′,G) ≥ σ，否则supp(φ,G) = max supp(Q′,G) < σ。一旦第i层的模式的集合Qi被生成并验证，NVSpawn(i)就会在第i次迭代被VSpawn(i)触发。它用来发现所有supp(Q′, ) = 0的模式Q′∈Qi并且添加到。通过Q′的存在，保证了supp(φ，G)≥σ。

case b：负的GFD φ′通过向X增加一个字段延伸，supp(φ,G) ≥ σ否则supp(φ′,G) = maxsupp(φ,G) < σ。一旦 HSpawn(i,j)验证了G|=φ 且 supp(φ,G) ≥ σ，它就生成负的候选者，其中X'就是通过给X延伸一个字段得到的。如果Q(G,X′,z)=0，就添加φ′到。由于φ的存在，保证了supp(φ'，G)≥σ。

SeqCover：

给定由SeqDis计算出的一组GFDs的Σ，SeqCover算法计算出一组Σ的cover Σc

工作原理：对每一个φ∈Σ，根据刻画检查是否Σ\{φ}|=φ，如果是，则将φ从Σ中移除。Σφ=φc，一直迭代到φ不能被移除为止并以Σc结束。这是内在的顺序，一个接一个地检查φ。

SeqDis算法正确生成并验证了所有k有界σ-频繁最小GFDs的集合Σ，用引理4去除不重要的和非约化的GFDs。而且，SeqCover能够正确计算Σ的覆盖。(1)对每一个φ∈σ，通过表征GFD蕴涵进行蕴涵检验。(2)当φ终止时，Σc中部蕴涵φ。因此Σc是Σ的一个覆盖物

2.4 并行GFD发现算法 DisGFD

定理5:存在一种用于GFD发现的算法DisGFD，它相对于SeqDisGFD是可并行扩展的。

算法DisGFD由ParDis （并行化SeqDis对应的部分来发现G的k有界最小σ-频繁GFDs的集合Σ）和ParCover（并行化SeqCover来计算一个cover Σc）

算法由master Sc和n个workers组成，图被分为n个片段 (F1, . . . ,Fn)，并且被分配到n个workers上 (P1, . . . ,Pn)

此算法跟SeqDis都在第i步采用Σi存储最小的有i条边的σ-频繁GFDs，ParDis算法首先初始化σ和treeT(第1-2行)，然后最多进行k2超步。在每个超步i (0 < i < k2)， ParDis通过进一步“并行化”核心步骤，即SeqDis的模式验证(垂直生成)和GFD验证(水平生成)，并行生成并验证GFD候选项。

ParDis

(1)并行模式验证。ParDis在主Scto上执行垂直生成VSpawn(i)，在T的i层生成图模式。如果产生了新的模式，它就会进行并行模式匹配，为所有第i层的模式寻找匹配，从而为GFD候选对象做出贡献。

(2)并行GFD验证。然后，ParDis算法和验证过的图形模式在sct上执行水平生成HSpawn(i,j)，生成一组GFD候选对象。操作HSpawn(i,j)迭代j∈[1,j]，其中j = i|Γ|(|Γ| + 1)，然后对候选GFDs进行并行验证。一旦每个超步i结束，Σ将被所有证实的最小频率GFDs Σi展开。

这两个步骤迭代，直到没有新的gfd产生，或者所有k-bounded的GFD都被检查完

并行模式匹配：将VSpawn(i)生成的图形模式集表示为Qi'。ParDis算法并行进行增量模式匹配，如下所示：

（1）在Sc上，对于每个模式Q'∈Qi', ParDis构造一个工作单元(Q,e)，将Q' “分解”成一个已验证的模式Q，并在Q上添加一条边e以获得Q'。不知道对不对。对所有t∈[1,n]，执行一个连接Q(Fs)▷◁ e(Ft)，在碎片Fs局部计算Q ' (Fs)的请求。也就是说，e被视为单边图案。然后，它将工作单元分配给n个workers，以并行计算，遵循工作负载平衡策略(参见下面的细节)。

（2）在接收到一组工作单元后，每个工人Ps增量计算Q'(Fs)，通过(a)将t∈[1,n]的局部验证匹配Q(Fs)与e(Ft)，其中e(Ft)从Pt运送到Ps，如果s≠t;和(b)验证Q ' (Fs)与同构校验匹配。在这之后，每个工人Pi为下一轮存储匹配Q(Fs)' 。一旦验证了所有模式，它将向Sc发送一个标志Terminate

并行验证：一旦所有workers发送Terminate给Sc, ParDis算法开始执行HSpawn(i,j)生成，并将传递给n个workers，并行验证GFD候选对象。