加速SQL查询的特征函数法

　　1. 查询问题的挑战
　　关系数据库的查询优化始终是一个重要而实际的问题，在那些以查询为主的应用系统中，这几乎是一个成败攸关的问题。但迄今为止，关于这个问题的讨论中所提出的种种解决方案大致可分为两大类，即利用硬件体系结构上的优势及DBMS对并行处理的支持能力的一类方案及完全由应用设计来处理的方案。在本文作者以前所发表的文章中曾推荐过利用临时中介表和表更新方法和快查询处理的策略。在同一篇文章中，我们也曾提到有可能利用程序变换支持查询优化的想法。所有这些建议和想法都属于应用设计类的处理办法，这些方法从某种意义上说有一定的一般性。但是，实际应用不断地提出这样或那样难而“怪”的问题，这些问题极富挑战性，用常规方法往往要以很昂贵的系统资源为代价才有望解决。
　　本文的目的是向读者介绍一种由E.Birger等人首先提出的方法，即加速查询处理的特征函数法。这个方法适用于大多数SQL的数据库系统，如果这类系统还包括为数不多的几个（最少为2个）内部函数，如abs（）及sign（）等，则这个方法就是直接可用的了。在E．Birger等人关于这个方法的研究报告中，曾给出很多极有难度而又很典型的查询要求及其求解办法，其中包括分技条件查询、求行内量的边界值、求直方图、表转置、求中位值、有序集的等段截分以及去边界值问题等。这些问题的共性是，若用常规方法求解，系统无论在存储开销上还是处理开销上都很大，而某些问题（如中值）的求解还相当难。本文将重述这些有趣的查询问题及其解决方案。同时，我们还将讨论“特征函数”作为一种使能技术的其他一些应用可能。
　　
　　2．特征函数及其表示
　　特征函数是来自点集拓扑学的一个纯数学概念，集合S的特征函数定义如下：
　　1 若x? S
　　d s(x)= （0）
　　0 若x? S
　　
　　在这里，任意元素x是否属于集合S，决定函数取不同的值。同时，这里也隐含了一个前提，即任何元素的集合S为范围的归属是完全确定的，不存在元素x的归属不明的情况。显而易见，特征函数是一种识别（或判定）装置。正是这一特性，使它能够成为数据库查询中选择准则的一种等价（和更有效的）替换成分。因此，我们说特征函数是加速查询的实施技术。
　　
　　为了更直接地针对数据库查询问题，我们将特征函数的一般形式变换成如下的“数据库版本”：
　　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子句和相关算子中的选择条件找到与之语义等价的算术表达式？答案是肯定的，这就是我们在下面要介绍的“特征函数法”。
　　
　　4． 几个典型查询的特征函数解
　　正如上面所讲，特征函数能够实现我们的愿望，即将显式的布尔条件转化为标量表达式。因此，特征函数最直接和简便的运用是针对条件检索型的查询，但它的作用并不仅仅止于此。为了较全面地了解特征函数在解决复杂查询中的作用，本节将由易到难介绍和分析若干典型实例。对某些实例，我们还将说明它的应用领域。为了表达上更紧凑，所有出现在标量表达式中的特征函数都没有用元函数展开。因此，如果要通过实际运行验证这里的实例，必须先借助于（5）、（6）替换这里的特征函数。
　　
　　4．1 条件检索
　　由（10）给出的查询可借助于特征函数识为
　　SELECT name，
　　income＝parentincome*d ［status＝1］＋selfincome*d ［status＝0］
　　FROM student （11）
　　如果检索条件仅止于此，用（11）代替（10）并没有什么本质上的意义。但实际问题中的检索条件远比此处复杂而多样。例如，若将上例的要求稍作修改，即在保留status原有语义而外，加上按学生的年龄分段的要求，即以19岁和23岁为年龄的分界点，凡年龄不超过19岁而且依靠父母的学生为一组，凡年龄超过23岁者完全自食其力的学生为第二组，所有其他学生为第三组。在查询结果中，收入（income）一栏有不同的含义：对前两组学生，分别对应于他们父母的收入和学生自己的收入，对第三组学生，则对应于前两组学生收入的算术平均值。在习惯于用常规方法处理查询的人看来，这样的条件就显得大复杂了。实际上，这是很自然的要求，相对于原问题而言，要求的扩展是很轻微的。对照查询表达式（11），不难验证
　　
　　SELECT name，
　　income＝parentincome*d ［atatus＝1］*d ［age<＝19］＋selfincome*sign (d ［status＝O］＋d ［age>23］）＋( (parentinceome＋selfinco me)/2.0*(1一d [status=1]）

查看本文来源