精华推荐：加速软件测试SQL查询的特征函数法

关键字：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 ]）

原文转自：http://www.ltesting.net