SQLGraphExplorer‐5
-
输入：
- 目标表中的某行(tuple)（不妨称之为t）
- 表示关系表达式(Relational Expression)的 sql 语句（不妨称之为E）
-
输出：
- 可以找到t的逆像的“逆关系表达式”（不妨称之为InvE(t,E)）
- “逆关系表达式”( InvE(t,E) )的“执行结果”是：t 的逆像集Inv(t,E)=${t_1,t_2,...,t_n}$
链接：Translating View Updates Using Inversion of Relational Algebra
这篇论文提及了逆关系表达式的公式，以及相关概念
全集 U 中的元素名为属性, U 的每个属性 A 和一个域
在模式 X 之上的元组 t 是一个从 X 到
- 一个定义在全集 U 上的数据库
$D$ 是一系列关系符号的集合 —${R_1,R_2,...,R_n}$ .每个$R_i$ 和一个关系模式$\mathcal{R}_i$ 相关联. -
$D$ 的一个实例就是一系列关系实例的集合 —${r_1,r_2,...,r_n}$ ,其中每个$r_i$ 都是$R_i$ 的一个实例. - 一个关系表达式
$E$ 可以根据一系列关系符号($R_1,R_2,...,R_n$ )来定义 :$E(R_1,...,R_n)$ .该关系表达式的结果则可根据一系列关系实例($r_1,r_2,...,r_n$ )来定义 :$\varepsilon(r_1,r_2,...,r_n)$
定义 4
-
k-元组 :
$(t_1,t_2,...,t_n), t_i$ 是一个元组. - 一个 k-元组是一阶的,如果它只包含一个非空元组 : (
$\epsilon,...,\epsilon,t,\epsilon,...,\epsilon$ )
- 一个基本限制是一个布尔表达式:
-
$$c = \top(true)/-(false)/x\theta y \\\ \theta \in \{<,\le,>,\ge,=\} \\\ x,y \in \sum$$ - 一个限制是一个复杂布尔表达式 :
-
$$C=c_1\wedge c_2\wedge ...\wedge c_n \\\ c_i是一个基本限制$$
一个限制 k-元组(c-k-元组)可表示为:
逆像集合的定义如下:
- 四种操作符(projection, extension, append, completion)
操作数是 c-k 元组
操作数是 c-k 元组集合
值得注意的是：
论文的原文对于
$\overline{\Gamma}$ 的定义非常模糊，也没有给出具体求解的公式或算法。所以这块比较麻烦。。。sch(E) 也是如此
例子：
--sch(R1)=AB ; sch(R2)=BC
SELECT A,C FORM R1 JOIN R2 WHERE B=b
$E=\Pi_{AC}(\sigma_{B=b}(R1\bowtie R2))$ , 假设执行的结果是$\mathcal{P}={[(ac),\top]}$ ，推导过程如下
-- 假设目标表为R3,sch(R3)=AC,输入tuple(行)为ac
SELECT A FROM R1 WHERE R1.A=a AND R1.B=b
SELECT C FROM R2 WHERE R2.B=b AND R2.C=c
Inverting relational expressions: a uniform and natural technique for various database problems
论文 1 的研究并不针对逆关系表达式，仅是用到了这个概念。于是顺着论文 1 的参考文献，我找到了论文 2
- 关系 r 是从一组属性(A)到某个域(D)的函数(元组)集合。为了简单，我们假设一个常见的(无限)域
- 关系类型：指的是关系的属性集合$\alpha(r)$
- 关系名：具有相关类型的符号 R
- 关系实例：如果 r 的类型等于 R 的类型，则关系 r 是关系名 R 的实例
- 关系操作符：projection, join, union, selection
- 关系表达式：由关系名和关系操作符构成的格式良好的表达式
- 关系表达式类型：该表达式的结果的属性集合$\alpha(f)$
- 数据库模式：一系列关系名的集合{R1,R2,.. ..,Rn}
- 表：表是允许作为条目的变量和常量的关系
- 变量 V：是一个可数无限的符号集
- X 类型的表：指的是元组的任何有限集合
- 赋值 v：任何 V->D 的映射， 赋值能以标准的方式在集合 D(对于 D 中的所有 c，v(c)=c)和元组和表的集合上扩展
- Rep(T)：是一个函数，该函数为表 T 分配如下一组关系
${s\ |\ \exist v,v(T)\sube s}$ - 表是“扩展”的关系，在文献IL11中引入，以表示不完整的信息。应该将表格视为表示关系集的一种手段
表具有如下三个基本属性：
在文献IL2中，作者证明了一个用表格表示关系式逆的一般定理，这里给出了只有一个关系符号的表达式的特例
定理 1：
- f 是一个 PJ-expression，T 是一个表格，那么存在一个表格 U 使得：
$Rep(U)=f^{-1}(Rep(T))={s:f(s)\in Rep(T)}$
- 一般而言存在很多这样的表 U，通过文献IL2中的算法，我们可以构造出$f^{-1}(T)$，即 U
- 文献IL2中提出的计算$f^{-1}(T)$的算法是一个类似于 Tableau 构造的递归过程：
- 如果
$f=g\bowtie h$ ，则$INVERSE(f)=INVERSE(g,\pi_{\alpha(g)}(T))\cup INVERSE(h,\pi_{\alpha(h)}(T))$ - 如果
$f=\pi_Yg$ ，通过添加相关属性的新列来扩展 T，即$INVERSE(f)=INVERSE(g,Y')$
- 如果
关系$\Omega$-表达式集合可以在表集合上正确扩展，只要对于任意表格 T 和任意关系$\Omega$-表达式 f，都有
$Rep(f(T))\equiv_{\Omega}f(Rep(T))$
$f(T)$ ：f 的结果$f(Rep(T))={f(s):s\in Rep(T)}$ $x\equiv_\Omega y$ ：表示两个关系集合 x,y 是$\Omega$-等价的，即对于任意$\Omega$-关系表达式 f，$\bigcap f(x)=\bigcap f(y)$
Incomplete Information in Relational Databases
论文 2 中有一些没有提及的相关背景理论，其中很重要的一部分就是这篇文章(貌似引用还蛮多的?)，于是我读了该论文作为一个补充。
关于关系数据模型的相关概念。
-
$\mathscr{U}$ ：一个固定的、有限的集合 - A,B,C：一般指代$\mathscr{U}$的属性
- X,Y,Z：一般指代属性集合。例如，属性集合{A,C}通常写做 AC
- D(A)：$A\in\mathscr{U}$，D(A)是 A 的属性域。我们通常假设$|D(A)|\ge2$。通常写做$D=\bigcup_{A\in\mathscr{U}}D(A)$
- 常量：D 中的元素通常被称为常量
- a,b,c：D(A),D(B),D(C)的元素通常写做 a,b,c
- X 上的元组：指的是一个映射 t，$\forall A\in X, t(A)\in D(A)$
- 元组：通常表示为与属性相关的值字符串
- t[AC]：表示 t 对 Y 的限制
- 例子：假设 t 是一个 X 上的元组，t=abc,X={ABC},Y={AC},那么 t[Y]=t[AC]=ac。
- X 上的关系：指 X 上的任何有限元组集
- 类型：t 是 X 上的元组，r 是 X 上的关系。
- 元组类型：$\alpha(t)=X$
- 关系类型：$\alpha(r)=X$
- 多重关系相关概念：
- 多重关系：$<r_1,r_2,...,r_n>$
- 多重关系的类型:$<X_1,X_2,...,X_n>$，(
$r_i$ 是$X_i$上的关系)。 - 对于两个具有相同类型的多重关系
$\pmb{r}=<r_1,...,r_n>$ ,$\pmb{s}=<s_1,...,s_n>$ 。如果$\forall r_i\sube s_i,1\leq i\leq n$ ，那么$\pmb{r}\sube\pmb{s}$ - 所有多重关系的集合写做
$\mathscr{R}$ -
$\mathscr{R}(X_1,...,X_n)=<X_1,...,X_n>$ ：表示所有多重关系的类型集合 -
$\mathscr{R}(X)$ ：类型 X 的所有关系的集合
- 对于一个多重关系集合$\mathscr{X}$，如果$\forall \pmb{r},\pmb{s}\in\mathscr{X},\alpha(\pmb{r})=\alpha(\pmb{s})$，那么我们成$\mathscr{X}$是齐次的。
- 而所有的齐次多重关系组成的类，我们用$\mathscr{I}$表示，$\mathscr{I}$的元素一般用字母$\mathscr{X},\mathscr{Y},\mathscr{Z}$表示
- 常见的关系运算符：
-
Projection:
$\pi_Y(r)={t[Y]:t\in r}(Y\sube\alpha(r))$ -
Selection：$\sigma_E(r)={t\in r:E(t)=true}$
- E 表示选择条件，它是一个表达式，其基本算子包括
$(A=a),(A=B)$ ,其中$A,B\in \mathscr{R},D(A)=D(B),a\in D(A)$
- E 表示选择条件，它是一个表达式，其基本算子包括
- Union：$r\cup s$，其中$\alpha(r)=\alpha(s)$
- Join：$r\bowtie s = {t:\alpha(t)=X\cup Y\wedge t[X]\in r\wedge t[Y]\in s }$，其中$X=\alpha(r),Y\in\alpha(s)$
- Difference：$r-s=r\backslash s$
- Renaming：$s^A_B(r)={s^A_B(t):t\in r}$，其中$A\in\alpha(r),B\in\mathscr{U}\backslash\alpha(r),D(A)=D(B)$
-
Projection:
-
$\Omega$ -关系表达式：由关系名和关系运算符构建的格式良好的表达式。例如：$\sigma_{A=a}(R_1)\bowtie\pi_{AB}(R_2)$是一个$PS^+J$-关系表达式 - 多关系$\Omega$-表达式：多个$\Omega$-关系表达式序列，$\pmb{f}=<f_1,...,f_k>$
-
关系表达式的类型化：假设与$\pmb{f}$相关联的是序列$<R_1,...,R_n>$，那么：
-
$\pmb{f}$ 的参数类型定义：$\alpha(\pmb{f})=<\alpha(R_1),...,\alpha(R_n)>$ -
$\pmb{f}$ 的结果类型定义：$\beta(\pmb{f})=\alpha(\pmb{f}(\pmb{r}))$
-
-
表示系统：一个三元组——$<\mathscr{T},Rep,\Omega>$
-
$\mathscr{T}：$ 多表集合 -
$Rep$ ：一个从多表集合到齐次多重关系的映射，$\mathscr{T}\rightarrow\mathscr{I}$ -
$\Omega$ ：关系操作符的集合
-
-
假设多重关系集合$\mathscr{X}\in\mathscr{I}$，$\pmb{f}$是一个$\Omega$-表达式，两者满足条件$\alpha(\pmb{f})=\alpha(\mathscr{X})$，于是我们有：
$\pmb{f}(\mathscr{X})={\pmb{f}(\pmb{r}):\pmb{r}\in \mathscr{X}}$ - 这样，任何$\Omega$-表达式$\pmb{f}$都能以自然方式被处理为映射$\pmb{f}:\mathscr{I}\rightarrow\mathscr{I}$
- 。。。。。。看晕了这块，先跳了
-
给定一个多关系表达式$\pmb{f}$和一个多重关系集合$\mathscr{X}\in\mathscr{I}$，二者满足$\alpha(\pmb{f})=\alpha(\mathscr{X})$，我们可以定义
$\mathscr{X}$ 中的 f-信息：$\mathscr{X}^{\pmb{f}}=\bigcap\pmb{f}(\mathscr{X})$