数据库系统2-6：关系运算的安全性

文章作者 100test 发表时间 2007:03:10 17:00:05
来源 100Test.Com百考试题网

计算机等级考试训练软件《百宝箱》

　　　

　　 为了使计算机能有效地处理关系运算，必须对关系运算进行限制，使关系运算不致产生无限关系和导致无穷验证。这就是关系运算的安全性问题。
　　1．产生无限关系和无穷验证的原因：
　　(1)在关系代数中规定的集合运算只包含并、交、差和广义笛卡儿积，而不引入补运算，究其原因是为了防止产生无限关系。从关系代数操作的定义看，对任一个有限关系的关系代数操作结果都不会产生无限关系和无穷验证，所以，关系代数系统是安全的。
　　(2) 在关系演算中，表达式{t|?R(t)}、{t1,t2,．．．,tk| R(t)ú t2>9)}可能表示无限关系，也就是说，关系演算，不管是元组关系演算，还是域关系演算，系统都有可能产生无限关系。
　　(3)在关系演算中，当变量t的定义域无穷时，要判断($t)(F(t))为假或("t)(F(t))为真，必须对变量的所有可能取值都进行验证，这就导致无穷验证。
　　2．实现关系运算安全性的设想
　　(1)倘若对任何表达式{t|j(t)}都规定一个有限符号集DOM(j)，使j的演算结果、中间结果所产生的关系，及其元组的各个分量都必须属于集合DOM(j)，这样便保证运算结果的有限性。
　　(2)在解决($t)(F(t))和("t)(F(t))无穷验证中，可设想规定一个有限集合DOM(w)，并限制t只能在DOM(w)中取值。
　　定义1：设j是一个元组关系演算公式，j的符号集合（记为DOM(j)）是由下面两类符号构成的集合：
　　①j中的常量。
　　②j中出现的关系的所有元组的所有分量值。
　　显然，集合DOM(j)是一个有限集合。
　　定义2：一个元组关系演算表达式{t|j(t)}是安全的，如果
　　① 如果j(t)为真，则元组t的每个分量都属于DOM(j)。
　　② 对于j中的每个形如($u)(F(u))的子表达式，如果元组u使F(u)为真，则元组u的每个分量都属于DOM(F)，
　　③ 对于j中的每个形如("u)(F(u))的子表达式，如果元组u使F(u)为假，则元组u的每个分量都属于DOM(F)。
　　定理：安全元组表达式的运算是安全的。
　　证明略。
　　例如有关系R、S如下图：
　　　　　
　　(1) 设有元组演算表达式{t|?R(t}}，因为R是一个有限关系，所以该表达式可能为无限关系。如果定义该表达式的安全约束有限集合为：
　　DOM(j)=Π1（R）∪Π2（R）∪Π3（R）=[b,c,9,2,dh,eg]
其中将一元关系Πi（R）看作一个集合，则原表达式{t|?R(t}}经过安全约束后，它的安全表达式{t|?R(t}}所示的关系R1如下图，这是一个有限关系，但与原关系不等价。若定义原表达式的DOM(j)=[b,c,2,dh]，则经过安全约束后，其安全表达式{t|?R(t}}所表示的关系R2如下图，这也是一个有限关系，但也与原关系不等价。
　　　　　　

　　(2) 设有元组演算表达式{t|S(t)ùt[2]=b}，若定义安全约束有限集合为：
　　DOM(j)=Π1（S）∪Π2（S）∪Π3（S）=[2,3,4,d,b,f,c,e]
则经过安全约束后，它的安全表达式{t|S(t)ùt[2]=b}所表示的关系R3，与原表达式结果一致；若定义安全约束有限集合为DOM(j)=[2,3,4,d,b,f,c]，则它的安全表达式{t|S(t)ùt[2]=b}所表示的关系R4，与原表达式不等价。
　　　　　　　

　　原表达式的最终运算结果为一有限关系时，对该表达式能够找到一个合理的有限集合DOM(j)，使得它在安全约束前后的结果关系一致且等价；反之也然。今后当我们提及安全表达式时，除声明外，总是指安全表达式等价于原表达式，即
（DOM(j)）k ∩{t|j(t)}= {t|j(t)}