为了更直接地针对数据库查询问题，我们将特征函数的一般形式变换成如下的“数据库版本”： 1 若a=ture d (a)= （1） 0 若a=false
其中α是布尔表达式。当构成布尔表达式的算术表达式由表属性及数据库内部函数组成时，特征函数的选择作用就很清楚了。 众所周知，一般关系数据库采用三值逻辑，即布尔表达式有可能取不确定值（“maybe”）。但为了简化表达并因此突出特征函数在加速查询中的本质作用，本文不考虑表属性取不确定值的情形。另外，实现特征函数的数据库（内部）函数（我们称之为特征函数的“元函数”）会因系统和我们主观选择上的不同而不同。例如，Sybase的Transact SQL有两个很有用的内部函数abs（）和sign（），可以直接作为特征函数的元函数。若A和B是任意两个表属性，则 d ［A！＝B］＝abs（sign（A－B）） （2） 为了使元函数有定义，表属性必须是数值变量。因此，除有特别声明而外，本文将一概假定所有举例和一般性讨论中的表属性为非空数值变量。等式（2）可从元函数的定义 abs（A）＝｜A｜ (3) -1 若A<0 sign(A)= 0 若A=0 (4) +1 若A>0 直接推导出来。一般地，经abs（）和sign（）而实现的特征函数是 d ［A＝B］＝1－abs（sign（A－B）） d ［A！＝B］＝abs（sign（A－B）） (5) d ［A d ［A<＝B］＝sign(1－sign（A－B）） d ［A>B］＝1－sign（1－sign（A－B）） d ［A>＝B］＝sign(1＋sign（A－B））) 此外，设α和b 是任意布尔表达式，则 d ［NOTα］＝1－d ［α］ d ［αANDb ］＝d ［α］*d ［b ］ (6) d ［αOR b ］＝sign（d ［α］＋d [b ]） 这里的A和B是表属性，为非空数值量。等式（5）给出了6个最简单的特征函数的元函数表示，但这并不是唯一的表示，还可能其他的表示方法。等式（6）是布尔算子的一般导出规则。对于由最简型式的关系表达式构成的布尔表达式而言，等式（5）和（6）就构成其特征函数的实现规则。对于一般布尔表达式，等式（5）和（6）也是导出其特征函数的基础。一般而言，由（5）和（6）可以推演出一个特征函数类，某些特征函数直接对应于SQL的选择算子。例如，形如d ［A<＝X<＝B］的特征函数显然与判定变量X是否在闭区间［A，B］中有关。利用（5）中的第4个特征函数及（6）中的第2个导出规则， d ［A<＝X<＝B］ ＝d ［(A<＝X)AND(X<＝B)］ ＝d ［A<＝X］*d ［X<＝B］ ＝sign(1－sign（A－X））*sign(1－sign(x－B）） (7) 显而易见，等式（7）右端的区则算术表达式恰是选择算子BETWEEN的一种等价表达。可以仿照上述方法得到其他三个与区间值有关的特征函数，即δ［A 3． 实例分析 为了说明以上引入的特征函数在加速查询处理中的作用，让我们具体分析一个实例。 试考察一个描述学生收入状况的表 Students（name，status，parentincome，selfincome）（8） 其中name是主键，属性status是一种标法量，当status取值1时，表明学生的收入完全来自父母，当status取值0时，表明学生的收入完全是自己劳动所得。针对这个表，假定我们想得到形如（name，income）的查询结果，其中income或为学生自己的收入（当相应的status取0值时）或是来自父母的收入（当相应的status取值为1时）。 从表students的结构及查询结果的语义分析，完成查询的常规方法应当是 SELECT name，income=parentincome FROM student WHERE student=1 UNION (9) SELECT name , income=selfincome FROM student WHERE student=0 这是一个很自然、很直白的查询表达，但同时也是一个非常低效和非常耗费资源的表达。执行这个查询的一般过程是：首先分别执行由算子UNION所连结的两个子查询，然后产生一个存放查询中间结果的临时表并将两个子查询的结果存入以这个临时表中，第3步对临时表作排序以便消除可能存在的重复值。至此，才得到最终的查询结果。在这样的处理中，除对整个表students要遍历两次而且要对中间结果作排序处理，处理上的烦杂和资源的消耗都是显而易见的。查询（9）唯一的优点，是它表达上的自然直白，谁都想得到。 对本例而言，还有更紧凑和更有效的查询表达。例如，不难验证以下的查询 SEIECT name，income=parentincome*status+selfincome*(1-status) FROM students； （10） 从语义上与查询（9）完全等价。但查询（10）不但消耗的存储少而且处理上要有效得多，因为它只遍历一次表students而且避免了可怕的排序操作。这个例子说明，对同一个查询结果，不同的查询表达在处理效率和资源消耗上可能会相去甚远。因此，寻求有效的查询表达方式，不但是必要的而且是可行的。 查询表达（10）与像（9）那样的常规表达不同之处在于，后者的查询条件由两个WHERE子句和算子UNION显式给出，首者将查询条件间接地隐藏在SELECT子句的算术表达式中。无论查询表达采用什么形式，本例都属于“条件检索”的查询类型。如果对照一下查询要求和查询表达（10），不难发现只所以能给出如此简洁而正确的回签，实在是有点“事有凑巧”。如果问题稍作些许改变（例如，属性student取0和1以外的值，或者student取两个以上的标法值，如此等等）问题就不会这么简单了。因此，是否有一种很一般、很系统的解决方案，能让我们对任何显式表达在WHERE子句和相关算子中的选择条件找到与之语义等价的算术表达式？答案是肯定的，这就是我们在下面要介绍的“特征函数法”。
网站地图
收藏本站
高级搜索
相关文章: