Dependencies for Graphs 阅读笔记

2023-09-05 阅读 126 评论 0

摘要：本文提出图实体依赖关系（GEDs graph entity dependencies） GED被定义为图形模式和属性依赖的组合 GEDs可以用常量文字来表示图的函数依赖关系，以捕捉不一致，用带有id文字的键来标识图中的实体(顶点）我们修改了对GEDs的追逐，并证明

本文提出图实体依赖关系（GEDs graph entity dependencies）

GED被定义为图形模式和属性依赖的组合

GEDs可以用常量文字来表示图的函数依赖关系，以捕捉不一致，用带有id文字的键来标识图中的实体(顶点）

我们修改了对GEDs的追逐，并证明了它的教会-罗塞尔性质

我们刻画了GED的可满足性和蕴涵，并建立了这些问题的复杂性和GED的验证问题，存在和不存在常量文字和id文字。

我们还开发了一个完善的、完整的、独立的有限蕴涵几何系统

我们用内置谓词或析取来扩展GEDs，以在表达能力和复杂性之间取得平衡。

我们解决了这些扩展的可满足性、蕴涵和验证问题的复杂性

1、介绍

1.1、图、图模式以及匹配

此处的

Graphs. 图G表示为其中：

V是一个有限的节点集合；E是一个有限的边的集合，(v,ι,v′)表示从节点v到节点v'的边，这条边标记为 ι ，且； L表示节点的标签，通过L(v)可以得到v的标签，L(v)∈Γ；每个节点带有一个元组，其中且，写作和若则，而节点v携带的特殊属性id表示其节点身份。

Graph patterns. 图模式是一个有向图其中：

是一个模式节点集合；是一个模式边集合；是给和分配边的映射；是不同变量的列表，每个变量表示中的一个节点

Matches. 使用来表示两个标签匹配，二者匹配需要满足下面条件之一：（1）ι 和 ι′ 都是在 Γ，且ι = ι′ （2）ι′∈Γ 而 ι 是 ‘_ ’, 在Γ 中'_'可以用来表示任意边

图G中图模式Q的匹配是用映射函数h( )使得对于属于Q的节点v，h(v)找到G中的节点，且

匹配规则是：若（1）任意有；（2）Q中任意边在G中存在边使得，则同态h是图G中模式Q的匹配，边的匹配表示为

这的匹配规则大致为要求模式Q和图G的节点有相同的标签，有相同标签的节点之间的边也得有相同的标签，即若v1和v2属于模式Q，且标签分别为 a,b，v1与v2之间的连线标签为c，则h(v1),h(v2)的标签也得是a,b，它俩之间的连线的标签也得是c，否则它俩就不匹配

文本使用的是同态映射，跟Functional Dependencies for Graphs使用的同构映射不同。

1.2、图实体依赖

图实体依赖φ被定义为，其中是一个图形模式；X和Y是的两个文字集，也就是说X和Y包含于；我们称为φ的模式，称为φ的函数依赖；

对于文字集中的文字x,y有：1、常量文字x.A = c，其中c是U中的一个常量，A是ϒ中的一个属性但不是id； 2、变量文字x.A = y.B，其中A和B是ϒ中的属性，但不是id； 3、id文字 x=id = y=.id

例1、，结合Q1图，若X1由单个常数字x.type=“video game”，Y1由单个常量字y.type = “programmer”组成，这表示电子游戏只能由程序员创造。

，结合Q2图，可以看出，若一个国家有两个首都y,z，则y和z的名字必须相同。

，结合Q3图，可以看出A是x的一个属性，而若x由一个属性A，则y也用属性A。

，结合Q4图，GED声明图形模式Q4是“不合法的”，没有人可以同时是另一个人的孩子和父母

GED的语义解释：

若 (a) 当a 是x.A=c则v.A存在于节点v = h(x)，并且h(x).A=c；这个可以解释为，当模式Q的字段x.A=c，而在图G中找到一个节点h(x)，这个节点也有属性A，并且属性A也等于c

(b) 当a 是x.A=y.B，则属性A和属性B分别存在节点v=h(x)和w=h(y)，且v.A = w.B；可理解为在G中找到两个结点与x,y对应，这两个节点也满足h(x).A = h(y).B

和 (c)当 a是x.id=y.id 则h(x)和h(y) 指的是同一个节点，我们就说a,表示满足a. 可理解为在G中找到两个节点，满足h(x).id=h(y).id,那么这两个节点其实是同一个节点。

当满足X中的所有字段时,可以表示为.

若蕴含时，可以表示为

若G中Q的所有的匹配有则表示为G |= φ。而当Σ中所有的GED φ都是G |= φ，则G |=Σ。

对于，对于字段x.A = c，h(x)可以没有属性A，依旧成立，因为当h(x)可以没有属性A时，不成立，则根据蕴含公式为假，则为真。

而若字段x.A=c，h(x)中有属性A并且h(x).A = c，则h(y)也必须有属性A使得h(y)=c，不然的话就不成立。跟蕴含性质一样，前面为真，则后面必须为真。

使用图的键GKey来表示形式为的GED，其中由和组成，是同构f : 的一个拷贝，和是不相交的；由和；和是Q中指定的节点；X 可以看作有和组成的交集，可以是常量字段、变量字段或id字段。

例如：就是三个GKey。X5由x.title = y.title和x′.id = y′.id组成；X6由x.title = y.title和x.release = y.release组成；X7由x′.name = y′.name和x.id = y.id组成；

看到这了，可能有人想问，为什么要用同态，而不用同构呢？Functional Dependencies for Graphs这篇论文中同构感觉要容易读懂一些，那么为什么要用同态呢？

我们假设之前的现在使用同构，那么同构h用于模式Q5的节点x,y找到图中的h(x')，h(y')是两个节点，且名字不一样x′.name 不等于 y′.name，则，由上可知满足，但是显然其并不满足，所以如果使用同构的话，永远都能满足φ，因此选择了同态。

下图是本文主要使用的符号表：

2、CHASE介绍

2.1 为GEDs修改chase

在介绍等价关系前，需要介绍一下一些新的概念：

给定图G = (V,E,L,FA)，有限的GEDs集合Σ

Equivalence relations.即等价关系

1、对于x ∈ V, 它的等价类表示为，这个等价类是被识别为x的y的集合，y ∈ V。

2、若x.A=y.B且x.A=c被Σ中的GED强制执行，则对于x的每个属性x.A，它的等价类是属性y.B和常数c的集合。

上述等价关系定义2可以理解为，若被GED识别为x的y有两个G的节点y1和y2，则={x,y1,y2}，而若x.A=y.B=c被GED强制执行，则x.A的等价类={x.A,y1.B,y2.B,c}

这种等价关系是自反、传递、对称的，使得：

1、若节点y∈，则节点x∈，且=；所以可以将二者合并，这个很好理解，还是跟上面红字一样，x的等价类是x,y1,y2,则y1的等价类也是x,y1,y2；类似的若对于属性y.B∈，则我们有，很容易看出y.B和x.A的等价类都是{x.A,y.B,c}

2、若存在属性y.B使得y.B∈和y.B∈ ，则 = ，类似的若c∈ 且c∈则二者相等。

3、若节点y∈且y∈，则和相等。

4、若节点y∈，则对于y的每个属性y.B有

一致性

若存在节点y∈使得L(x) L(y)且L(y)L(x) ,则我们称之为标签冲突

若存在y.B∈使得x.A=c且y.B=d，c!=d，则我们称之为属性冲突。

当存在标签冲突或属性冲突时，等价关系Eq在图G上是不一致的。否则就是一致的

Coercion 强制

对于属于V的每个节点x，把G上一致Eq的强制定义为图其中：

V ' 是的集合，用来表示，这个是一个节点，也就是说使用这么个节点来表示这个集合，将被识别为相同的节点表示为同一个节点。

E ′ 是边的集合，也就是说，因为别识别为相同的节点已经被整合成同一个节点了，那么它们的边也应该整合成同一条边。

若中所有的节点都被标记为_,则也是_ ，不然的话，其中，当Eq是一致时，标签就相等，则这些标签融合之后还是名字相同的一个标签，这对应一致性问题的(label conflict)

，就是将别识别为相同节点的属性关系取并集，当Eq一致时，这些属性关系取并集就还是一个，比如x.A=c , y.A=c，那么并集之后就是x.A=c，这对应一致性问题的(attribute conflict).

chase

以初试等价关系Eq0开始，Eq0由和组成，其中每个节点x都属于V，每个属性x.A=c都属于FA(x)；

通过来对chase进行更新，其中是一个Σ的GED；是图G上Eq的coercion 中模式Q的匹配，使得：

（a），（b）Eq′ 跟通过增加一个字段 m（m ∈ Y）来扩展Eq是等价关系，而 y 和Eq‘ 满足以下关系之一：

（1）如果m是x.A=c且，则Eq'拓展Eq通过（a）若h(x).A不在Eq中，包含一个新的等价关系类，（b）往里添加c

（2）如果m是x.A=y.B且，则Eq'拓展Eq通过（a）若h(x).A不在Eq中就是添加（b）往添加h(y).B

（3）如果m是x.id=y.id且，则Eq'拓展Eq通过添加h(y)到

以上过程需要重复

（1）当没有GEDs用来扩张ρ，就结束迭代，这种情况，就说ρ是有效的且ρ=。且很容易验证在中是不一致的

（2）当一开始就不一致，或者迭代到，但是在中是不一致的，这些情况就直接使用禁止约束结束迭代，而ρ是无效的，结果用⊥表示。

例1、考虑图G中v1.A=v2.A=1 ，有和，={ ,}，h1为x → v1 ，h2为y→ v2，h已经满足了X，由上述规则可知，m是x.id=y.id，h(x)=v1, 则={v1}，={v2}，明显v2不在里面，所以往里面添加v2，得到，所以v1和v2被识别为两个相同的节点，则就会把两个节点合并成一个，边也合并了。

考虑其中和，而，h已经满足了X（应该X为空集），由上述规则可知，m是y.id=z.id，h(y)=v1' ，={v1'}，明显v2'不在中，则往添加v2'，得到，所以v1'和v2'被识别为两个相同的节点，coercion G2就是将两个节点合并得到的结果。

因为已经没了GED可以用来更新

2.2 chase的Church Rosser性质

本节证明了使用GEDs进行chase拥有如下的性质：

1、用GEDs chase是有限的，如果对于GEDs的所有集合Σ和所有图G，G被Σ chase的序列都是有限的。

2、如果对于所有的Σ和G，对于G中使用Σ进行chase的所有的终止chasing序列，不管GEDs的顺序如何都产生了相同的结果。也就是说要么全都产生相同的结果，要么结果是⊥。满足这种情况，我们就说GEDs chase具有Church Rosser性质。

3、如果存在一个有效的由Σ引起的终端chase序列，结果为，那么。

定理1、用GEDs追是有限的，且Church-Rosser性质。此外，对于任意一组GEDs集合Σ和图G，如果Σ存在一个有效的G的末端追踪序列，那么，其中是最终结果。也可以用chase(G,Σ)来表示最终的结果。

3 关于GEDS的推理

3.1 可满足问题

Σ的一个模型是一个图G，这个图G有：1、G |= Σ ； 2、每一个Σ 中的，Q在G中有一个匹配。

如果Σ有模型，那么σ中的ged是明智的，不会相互冲突。因此，我们可以应用这些GEDs，而不用担心它们之间的冲突。而可满足性问题就是研究当输入为一个有限的GEDs集合Σ 时，是否会有输出 Σ的一个模型？如果存在，则 Σ是可满足的，不然就是不可满足的。可满足性问题只要求Σ中的每个模式Q在图G中都有一个匹配，而这些匹配不一定是不相交的。

考虑一组GEDs的集合Σ，Σ的标准图可定义为，分别是Vi，Ei，Li的联合，则为空