E-BaseIII介绍

上一页 1 2 3 下一页

四、E-Base III采用的求值算法

4．1 预备知识

　　在数据库关系模型中的五个基本运算是：交（I）， 并（Y）投影（π），选择（σF），和迪卡儿积（χ），其中最基本和最重要的是选择操作（σF ）。选择操作中的F就是本文所述的查询公式。它对应于SQL中的WHERE子句。

　　查询公式是一类很特别的一阶逻辑公式，下面我们给出定义和讨论它们的性质 。

性质1：设F是查询公式，事实上F 是封闭的并且是由前束存在量词约束的。

　　例如：设F为 X=a ∧ Y>100 ∧ Y<1000,

　　事实上F表示的逻辑含义是

　　$X $Y (X=a ∧ Y>100 ∧ Y<1000).

性质2：设F是查询公式，事实上存在与F等价的查询公式F'，其中F'中不存在￢。

　　证明： 把F中任意原子公式￢（XθY）转化为了Xθ'Y，其中如果θ分别是 =， =/=，<，>，<=，>=，则θ'分别转换成=/=,=,>=,<=,>,<。显然F与F'是等价的。

性质3：设F是查询公式，F有一等价的范式F'。

　　证明：设F是查询公式,由性质1知F的全部量词（存在量词）前置，因此对F的非量词部分做任何变换时都与变量无关，因此可以把不同的原子公式等同于不同的命题。根据命题逻辑范式定理有，任意F具有下面形式的等价范式F'：

（A11∧．．．∧A1n) ∨ （A21∧．．．∧A2n) ∨．．．∨ （Ak1∧．．．∧A1nk) (析取范式）
或
（A11∨．．．∨A1n) ∧ （A21∨．．．∨A2n) ∧．．．∧ （Ak1∨．．．∨A1nk) (合取范式）。

　　考虑实际应用的习惯性，我们选取合取范式作为F'。

　　事实上存在着十分简单的方法把任意命题公式翻译成等价的命题范式。

　　总结上述性质，我们可以得出结论：存在着简单和机械的算法把任意一个查询公式翻译成NOT_free合取范式。

4．2 查询公式的集合表示

　　表达式表示成逆波兰表示有两个主要目的：

• 去掉括号。

• 按照子表达式的求值顺序排列运算符和运算数的顺序。

　　由于合取范式具有固定的形式且具有固定的求值顺序，因此采用逆波兰表示已无意义。

　　假定所有的查公式都已化为合取范式，例如：

　　　S1 ∧ S2 ∧．．． ∧ Sn.　　　 　( 1 )

其中Si为：

　　　Ai1 ∨ Ai2 ∨ ．．． ∨ Aini.　　 ( 2 )

我们把（1）和（2）分别叫做合取式和析取子式。

　　事实上，在范式中的Si(或 Aij)的顺序是没有关系的，因此我们可用集合表达合取式和析取子式。例如：

合取式

　　　S1 ∧ S2 ∧．．． ∧ Sn 表示为{ S1 ，S2 ，... ，Sn}；

析取子式

　　　Ai1 ∨ Ai2 ∨ ．．． ∨ Aini表示为{Ai1 ， Ai2 ， ... ， Aini}；

查询公式

　　　（A11∨．．．∨A1n) ∧ （A21∨．．．∨A2n) ∧．．．∧ （Ak1∨．．．∨A1nk)

　　表示为

　　{{A11，．．．，A1n} ， {A21，．．．，A2n} ，．．．， {Ak1，．．．，A1nk}}。

　　我们称上述表示为查询公式的集合表示。

4．3 求值算法

　　假定查询公式是集合表示的。显然查询公式的求值顺序是：原子公式，析取子式，最后是合取式。下面我们分别叙述其求值（valuation)。

4．3. 1 原子公式求值

　　在查询公式中原子公式是Xq Y，明显Xq Y是一个一阶谓词，但是是一个特别的谓词。

　　在一阶逻辑中为了给每个N元谓词一个解释（模型论），我们要定义一个Dn->{F,T}上的映射，或说定义一个N元关系Rn 。如果某N元组rn ∈ Rn，则rn映射T，否则F。

　　XθY是一个二元谓词，我们可以给予XθY一个解释，或者说为XθY定义一个二元关系Rθ：如果任意二元组＜x,y＞，x,y∈D(解释空间）并且x,y满足θ关系，则＜x,y＞∈ Rθ。事实上我们是无法显式构造Rθ，因为D常常是无限的。

　　在数据库中是不保留Rθ的，原子公式，XθY是由系统求值（通常叫内部谓词）。Xθ Y的求值为：

　　其中X与Y满足θ关系是由系统自动判别的。

4．3. 2 析取子式求值

设S，{Ai1 ， Ai2 ， ... ， Aini}是某析取子式的集合表示，S的求值为：

4．3. 3 合取公式求值

设F，{ S1 ，S2 ，... ，Sn}是一合取式的集合表示，F的求值为：

4. 3. 4 查询公式的求值算法

　　设F，{S1,S2,...,Sn}是一查询公式的集合表示,Si，{Ai1 ， Ai2 ，．．．， Aini}是析取子式集合表示，n表示F中析取子式的个数， ni表示每一析取子式中原子公式的个数，则F的求值算法可用类C语言表示如下：

　　　boolean　　C_val(F,n)
　　　　　　　　　　{
　　　　　　　　　　　for(i=1;i<=n;i++)
　　　　　　　　　　　　if(D_val(Si,ni)==0) return 0;
　　　　　　　　　　　return 1;
　　　　　　　　　　}

　　　boolean　　D_val(Si,ni)
　　　　　　　　　　{
　　　　　　　　　　　for(i=1;i<=ni;i++)
　　　　　　　　　　　　if(A_val(Ai)==1) return 1;
　　　　　　　　　　　return 0;
　　　　　　　　　　}

　　　boolean　　A_val(A)
　　　　　　　　　　{
　　　　　　　　　　　if((Xq Y)==1) return 1 else return 0;
　　　　　　　　　　}

　　其中C_val D_val A_val函数分别完成合取公式，析取子式和原子公式的求值；原子公式XθY的求值是由系统完成的。

4．4 优化

4．4．1 求值顺序优化

　　我们知道在逻辑演算中有如下性质：

　　性质1： 0 ∧ A1 ∧ A2 ∧．．．∧ An=0

　　性质2： 1 ∨ A1 ∨ A2 ∨．．．∨ An=1

　　假定F,{S1,S2,．．．,Sn}是查询公式的合取集合表示并且假定Si集合中仅有一个元素，明显根据性质1有

　　　　C_val(F,n)=0　当且仅当　$Si(Si∈F ∧ A_val(Si)=0)。

　　或者说，在F中只要有一个Si，它的析取子式求值为零则F的合取子式求值为零。意思是当如果已知存在某析取子式求值为零，则余下的析取子式求值是不必要的。根据这个性质，如果把最容易求值为零的析取子式（原子公式）优先求值，则余下的析取子式的求值可以省略，从而达到优化的目的。

　　我们认为原子公式 XθY求值为零可能性是由θ确定的并且大小是如下排列的：

　　=,<(或>),<=(或>=),=/=.

　　同理，假定S，{A1,A2,．．．,An} 是析取子式的集合表示，根据性质2，显然如果把最容易求值为1的原子式优先求值，则余下的原子式求值可以省略，同样可以达到优化的目的。

　　显然，原子公式Xq Y求值为一可能性大小是按为零可能性大小的反序排列的。

 上一页 1 2 3 下一页