SQLGraphExplorer‐11

Test-Case

test-case-0

Relation

• employee relation —— emp : <Ename, Pname>

  • Ename	Pname
    John	P

• department relation —— dept : <Ename, Dname>

  • Ename	Dname
    John	M

View

v，是如下表达式 E 的视图：

• $E=\Pi_{Ename,Dname}(\sigma_{Pname=P}(Emp\bowtie Dept))$

  • Ename	Dname
    John	M

Insert View Update

$Ins(\langle Mary,CS\rangle,E)$

• Inverse Image: $Inv(\langle Mary,CS\rangle,E)={([\langle Mary,Pname\rangle,Pname=P],[\langle Mary,CS\rangle,\top])}$
• $|Inv(\langle Mary,E\rangle,E)|=1$：满足 Insert 的强确定性。
• Translation:
  • $T=ins(({\langle Ename=Mary,Pname=P\rangle},emp),({\langle Ename=Mary,Dname=CS\rangle},dept))$

Delete View Update

$Del(\langle John,M\rangle,E)$

• Inverse Image:

  • $Inv(\langle John,M\rangle,E)={([\langle John,Pname\rangle,Pname=P],[\langle John,M\rangle,\top])}$

• 不满足 Delete 的强确定性，实际上有以下三种Translation：

  • $T=del((\langle John,P\rangle,Emp),(\emptyset,Dept))$
  • $T'=del((\emptyset,Emp),(\langle John,M\rangle,Dept))$
  • $T''=del((\langle John,P\rangle,Emp),(\langle John,M\rangle,Dept))$，由于$T''$不是 minimal change，故不考虑。

• Translation: 算法得到其中一种：

  • $T=del(({\langle Ename=John,Pname=P\rangle},emp),(\emptyset,dept))$

test-case-1

Relation

• R1 : <A,B>

  • A	B
    a	b
    a	b’

• R2 : <B,C>

  • B	C
    b	c
    b’	c

• R3 : <A,C>

  • A	C
    a’	c’

View

v，是如下表达式 E 的视图：

• $E=\Pi_{AC}(\sigma_{B\ge b}(R_1\bowtie R_2))\cup \Pi_{AC}(R_3)$

  • A	C
    a	c
    a’	c’

Insert View Update

$Ins(ac,E)$

• Inverse Image：

  • 论文中的结果是在线的(与数据库状态相关)：$Inv(ac,E)={(ab,bc,\epsilon),(ab',b'c,\epsilon),(\epsilon,\epsilon,ac)}$

  • 实际上的结果是离线的(与数据库状态无关)：$Inv(ac,E)={([aB,B\geq b],[Bc,B\geq b],\epsilon),(\epsilon,\epsilon,[ac,\top])}$

• 不满足 Insert 的强确定性，$|Inv|=2$

• Translation：算法得到其中一种：

  • $T=ins(({[aB,B\geq b]},r_1),([Bc,B\geq b],r_2),(\emptyset,r_3))$
  • 但这不是最小变化，和论文中期望的不符
  • 并且和Delete相比，Insert还存在一个问题就是B的值无法确定

Delete View Update

$Del(ac,E)$

• Inverse Image：
  • 论文中的结果是在线的(与数据库状态相关)：$Inv(ac,E)={(ab,bc,\epsilon),(ab',b'c,\epsilon),(\epsilon,\epsilon,ac)}$
  • 实际上的结果是离线的(与数据库状态无关)：$Inv(ac,E)={([aB,B\geq b],[Bc,B\geq b],\epsilon),(\epsilon,\epsilon,[ac,\top])}$
• 不满足 Delete 的强确定性，有多个Translation，例如：
  • $T=del(({ab},r_1),({b'c},r_2),({ac},r3))$
  • $T=del(({ab,ab'},r_1),(\emptyset,r_2),({ac},r_3))$
• Translation: 算法得到其中一种：
  • $T=del(({[aB,B\geq b]},r_1),(\emptyset,r_2),({ac},r_3))$

test-case-2

Relation

• A1 : <A11,A12,A13,A14,A15,A16,B11>

  • A11	A12	A13	A14	A15	A16	B11
    a11	a12	a13	a14	a15	a16	b01

• A2 : <A21,A22,A23,A24,A25,A26,B21>

  • A21	A22	A23	A24	A25	A26	B21
    a21	a22	a23	a24	a25	a26	b01

• B : <B01,B02,B03,B04>

  • B01	B02	B03	B04
    b01	b02	b03	b04

View

v，是如下表达式 E 的视图：

• $E=\rho_{GH,XM,GJ}(\Pi_{A11,A12,A13}(\sigma_{selection_1}(\sigma_{selection_2}(A1\bowtie B)))) \cup \rho_{GH,XM,GJ}(\Pi_{A21,A22,A23}(\sigma_{selection_3}(\sigma_{selection_4}(A2\bowtie B))))$

  • GH	XM	GJ
    a11	a12	a13
    a21	a22	a23

Insert View Update

$Ins(a_1a_2a_3,E)$

• Inverse Image：

  • $Inv(a_1a_2a_3,E)={(a_1a_2a_3,\epsilon,\epsilon),(\epsilon,a_1a_2a_3,\epsilon)}$

• 不满足 Insert 的强确定性，$|Inv|=2$

• Translation：算法得到其中一种：

  • $T=ins(({[a_1a_2a_3,selection_1\wedge selection_2]},A_1),(\emptyset,A_2),(\emptyset,B))$
  • 但这不是最小变化，和论文中期望的不符

Delete View Update

$Del(a_1a_2a_3,E)$

• Inverse Image：
  • $Inv(a_1a_2a_3,E)={(a_1a_2a_3,\epsilon,\epsilon),(\epsilon,a_1a_2a_3,\epsilon)}$
• 满足 Delete 的强确定性，仅有以下一种Translation：
  • $T=del(({[a_1a_2a_3,selection_1\wedge selection_2]},A_1),({[a_1a_2a_3,selection_3\wedge selection_4]},A_2))$

如何处理给定更新有多个合理转化的情况？

《Relational lenses》的结尾提到了该问题，并介绍了最常见的两种方法：

• 限制条件过滤：以某种方式限制合理的转化集，以便不会出现多个合理转化。

  • 补语限定：在常数补语下，对于特定补语的视图更新，最多会有一种转化

  • 单调性：Hegner对单调性的附加条件确保对于仅由插入/删除组成的更新，其转化是唯一的。

    • 更新转化的单调性(monotonicity)：只从视图中添加记录的更新应该只转化成底层数据库的添加（同样对于删除）。

• 排序：对更新的所有合理转化进行排序，并选择最小的那个转化(minimal change)。

相似问题：底层数据库状态和视图状态之间的映射

《Update semantics of relational views》中描述了该问题。

• 数据库状态：用$s$表示，代表底层数据库中关系的一个**“赋值”**。
• 数据库模式：用$S$表示，所有数据库状态的集合。
• 视图$f$：$s\longrightarrow f(s)$，针对底层数据库状态$s$，可以得到视图$f(s)$。
• $S/f$：读作$S$按$f$划分。$\forall s,s'\in S,s和s'在S/f中处于同一个集合\Longleftrightarrow f(s)=f(s')$。

举例：底层数据库模式$S={a,b,c,d,e}$

• $S/f={{a,b,c},{d,e}}$

• 如果我们在视图$f({a,b,c})$上进行了修改，产生了新的视图状态$f({d,e})$，那么就会存在两个底层数据库更新结果${d,e}$。

• 选择哪一个就是所谓的更新策略的选择。

解决方法

《Inversion of Relational Algebra》

强确定性视图

假设我们有视图$f$，它满足强确定性，用《Update semantic of relational views》来解释：

$1$：$S$上的恒等映射：$S/1={{a},{b},{c},{d},{e}}$

或者更宽松些：$S/f={{a,b,c},{d},{e}}$，但这要求我们修改后的视图状态恰好是$f({d})$或$f({e})$。

弱确定性视图

• 假设原底层数据库状态为$a$
• 视图状态更新为：$f(a)\rightarrow f({d,e})$
• 我们有两种选择$d或e$

弱确定性视图本质上就是待选择集合中有且只有一个最小变化，假设$|d-a|<|e-a|$，那我们选择$a$

《Update semantics of relational views》

补视图

引入补视图的概念，令$f,g\in M(S)$： $$ g和f的互补\Longleftrightarrow \forall s,s'\in S,f(s)=f'(s)\Rightarrow g(s)\neq g(s') $$ 举例：${a,b,c,d,e}$

• $f$：${{a,b,c},{d,e}}$
• $g$：${{a,d},{b,e},{c}}$

常量补视图下的转化

那么即使一个视图$f$不是$S$上的恒等映射，我们也可以借助$g$来补全$f$中丢失(不可见)的信息，从而唯一地反向确定底层数据库状态。

• 假设原底层数据库状态为$a$
• 视图状态更新为：$f(a)\rightarrow f({d,e})$
• 我们有两种选择$d或e$，选择哪个？论文中的选择是：常量补视图下的转化(Translation Under Constant Complement)
  • 我们要保持视图$g(a)$不变，于是我们选择$d$

补视图的选择会缩小$U$的范围

• $U_f$：在视图$f$上的所有更新操作
• $U\subset U_f$：在视图$f$上被允许的更新操作

如果这样呢？

• $f$：${{a,b,c},{d,e}}$
• $g’$：${{a},{b,e},{c,d}}$
• 假设原底层数据库状态为$a$
• 视图状态更新为：$f(a)\rightarrow f({d,e})$
• 我们有两种选择$d或e$，选择哪个？哪个都不能选，因为此时补视图$g'$都变化了！
• 此时我们说：更新$u=f(a)\rightarrow f({d,e})$在补视图$g'$下是不被允许的，读作$u$不是$g'$-可转化的(g'-translatable)

极端情况下：恒等视图$1$是所有视图的补视图，$S/1={{a},{b},{c},{d},{e}}$，但代价是在该视图下，$U=\emptyset$

所以我们有以下结论：

• 视图一般而言有多个补视图
• 给定视图$f$，补全$f$的选择决定了$U_f$中满足g-可转化的集合$U\subset U_f$的大小。只有满足$g$-可转化的更新操作才被允许在视图$f$应用
• 我们有定理如下：当补视图$g$最小时，集合$U$是最大的。（论文中也提到了两个视图之间如何定义比较操作符$\leq$）

两个方向

1. 已知一个视图更新$u_f$，我们去寻找对应的补视图$g$，使得$u_f\in U$
2. 视图更新未知，我们寻找最小补视图$g$，来让用户可操作的更新最多。

《Relational lenses》

这篇文章在传统关系操作符基础上定义了一系列透镜。

• 上面采取的方法是“找外援——两点确定一条直线”，而这篇文章则比较粗暴“直接削弱——把长方形砍成直线”

• 本质上是不断对 数据库模式 和 更新操作 添加限制，使得$U\in U_f$不断缩小，直到满足一对一的映射。

• 但这也使得透镜的能力变得很弱，用文章原话来讲就是：

  • 即使没有对模式的限制，我们定义视图的语言也大大弱于一般关系代数。

我的选择

直接开摆！，之前也说了minimal change 无所谓，反正都是合理转化，随便挑一个就行。代码也确实是这样写的。