（计算机应用技术专业论文）基于目标的数据库测试查询生成技术研究.pdf

r e s e a r c ho ng e n e r a t ln g t a r g e t e dq u e rle sf o rd a t a b a s et e s t in g ad i s s e r t a t i o ns u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro fe n g i n e e r i n g b y l u o ，l a i l i s u p e r v i s e db y j i n ，y u a n p i n g d e p a r t m e n to fc o m p u t e rs c i e n c e e n g i n e e r i n g s o u t h e a s tu n i v e r s i t y m a r c h2 0 1 0 东南大学学位论文独创性声明 本人声明所呈交的学位论文足我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得东南人学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：巧壕1 日期：丝丝盥型盟一 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的 公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：j 牡导师签名： 日期： 芝战 r ) 力f 衄f r , t l2 摘要 摘要 当在数据库设计过程当中引进了一项新技术，必须在不同操作系统环境下测试新数据库 系统的性能。通常，数据库测试会选择一套复杂的数据集和s q l 查洵集，并分别在引进新技 术前后的数据库系统中执行，最后比较二者的性能。当数掂集选定后，需要利用查询生成工 具构造大最的s q l 查询。现有的测试食询集生成技术大都肇于测试数据集的数据模式，没有 明确考虑其中的数据实例特性。这样的工具不能保证通用性及数据库测试所要求的用例覆盖 性。目前数据集生成的研究已经相当成熟，凼此本文重点研究s o l 查询集生成。针对给定测 试数据集，本文研究的目标测试查询生成算法构造的查询不仅满足已有研究具备的一维势 ( c a r d i n a l i t y ) 约束条件，还能为多维势约束i 、u j 题提供较精确的解。 本文的目标查询生成算法首先将数值域约束条件问题转化为空间域约束条件问题，然后 通过二分查找、空i 日j 分割及空间裁剪确定空间域约束条件中的参数值。二分查找过程采用了 基于评估层采样的贪心算法。本文重点研究了现有的采样技术，然后针对目标查询生成问题 提出了一种综合采样技术，从而有效优化查询条件的参数范罔选择。这使得所生成的s q l 测 试查询更能反映现实数据库的数据分布特征及实例特性，同时大大缩减了数据库中新技术引 进的测试周期。 最后，在丌源数据管理器p o s t g r e s q l 上进行了实验，并通过实验结果验证了该方法的实 际效用。 关键词：基于目标查询；势约束；采样；空间裁剪；评估 a b s t r a c t a b s t r a c t w h e nan e wt e c h n i q u ei si n t r o d u c e di nad a t a b a s ed e s i g n i n g i ti sn e c e s s a r yt ou s eal a r g e n u m b e ro ft e s t i n gd a t aa n dq u e r i e st ov a l i d a t et h ep e r f o r m a n c eo ft h ed a t a b a s ei nv a r i o u so p e r a t i n g s y s t e m s t y p i c a l l y , ac o m p l e xs e to fd a t aa n ds q lq u e r i e sa r ec h o s e nt on mo nt h es y s t e m sb e f o r e a n da f t e rt h ei n t r o d u c t i o no ft h en e wt e c h n i q u e ，a n dt h e p e r f o r m a n c e so ft h et w os y s t e m sa r e c o m p a r e d g i v e nt h ed a t as e t ，w en e e dq u e r yg e n e r a t i o nt o o l st og e n e r a t eal a r g en u m b e ro fs q l q u e r i e s u n f o r t u n a t e l y , m o s te x i s t i n gq u e r yg e n e r a t i n gt e c h n i q u e sa r ed a t as c h e m ab a s c da n dd i d n t e x p l i c i t l yt a k et h ef e a t u r e so fd a t ai n s t a n c e si n t oc o n s i d e r a t i o n a sac o n s e q u e n c e s u c ht o o l sc a n n o t g u a r a n t e ev e r s a t i l i t ya n dt h ec o v e r a g eo ft e s tc a s e su s u a l l yr e q u i r e df o rd a t a b a s et e s t i n 2 a st h ed a t a s e tg e n e r a t i n gt e c h n o l o g yi sq u i t em a t u r e ，t h i sp a p e rf o c u s e so nt h ep r o b l e mo fg e n e r a t i n gq u e r i e s t h a tn o to n l ys a t i s f y o n ed i m e n s i o n a jc a r d i n a l i t yc o n s t r a i n t sb u ta l s op r o v i d eq u i t ep r e c i s es o l u t i o n f o rm u l t i - d i m e n s i o n a lc a r d i n a l i t yc o n s t r a i n t sp r o b l e m t h et a r g e t e d q u e r yg e n e r a t i o na l g o r i t h mt h a t t h i s p a p e rp u t sf o r w a r df i r s t c o n v e r t st h e c o n s t r a i n t sp r o b l e mi nv a l u ed o m a i nt ot h eo n ei ns p a c ed o m a i n a n dt h e nm a k e su s eo fb i n a r y s e a r c h ，s p a c ec u t t i n ga n ds p a c ee x p l o r a t i o nt od e t e r m i n et h ep a r a m e t e rv a l u e sf o rs p a c ec o n s t r a i n t s a n dag r e e d ya l g o r i t h mb a s e do ne v a l u a t i o nl a y e rs a m p l i n gi su s e di nt h e b i n a r ys e a r c hp r o c e d u r e o nt h eb a s i so fa n a l y z i n ge x i s t i n g s a m p l i n ga l g o r i t h m s t h i sp a p e rp u t sf o r w a r das y n t h e s i s s a m p l i n gt e c h n i q u ew h i c hc a ne f f e c t i v e l yn a r r o wt h es c o p eo fq u e r yp a r a m e t e r s t h i sm a k e st h e s q lt e s t i n gq u e r i e sg e n e r a t e dm o r es u i t a b l et ob o t ha c t u a id a t ad i s t r i b u t i o na n dd a t ac h a r a c t e r i s t i c s a n ds h o r t st h ep e r i o do fd a t a b a s et e s t i n gw h e nan e wt e c h n i q u ei s i n t r o d u c e di nad a t a b a s e d e s i g n i n g f i n a l l y , e x p e r i m e n t sw e r ec o n d u c t e do n a n o p e n s o u r c e d b m sp o s t g r e s q la n dt h e e x p e r i m e n t a lr e s u l t ss h o w e dt h em e t h o do ft h i sp a p e rt ob ep r a c t i c a la n du s e f u l k e y w o r d s ：t a r g e t e dq u e r y ；c a r d i n a l i t yc o n s t r a i n t ；s a m p l i n g ；s p a c ec u t t i n g ；e v a l u a t i o n u 录 摘要 a b s t r a c t 目录 第一章绪论 目录 i 1 1 论文石j 究背景与意义1 1 2h i 标奁询生成技术研究的现状和存往的问题1 1 3 论文的下作目标和硼f 究内容2 1 4 论文的组织安排3 第二章基于采样的连接选择性评估算法 2 1 连接选择性i 口j 题描述一 2 2 两大类连接选择性评价算法比较 2 3 六种连接选择性评仆算法比较 2 王j 也缮迸挣例子膨兢盒 2 3 2 廷馁透帮刃子膨石掰缈： 2 4 两种采样模式下连接选择性评什算法比较。 2 4 1 碰搂迸拶丝伊彩街编伊烂： 2 5 本章小结 第三章基于目标的数据库测试查询生成问题分析 3 1 基于目标的数据库测试奋询生成问题描述8 3 1 1 基f 目标的数据库测试查询生成潮题的定义8 3 2 一维势约束9 3 3 多维势约束1 0 i i j 磁立拦彬改1 1 3 3 2 力耀历! 苏z 莹脚：j j 一 3 4 本章小结1 2 第四章基于目标的数据库测试查询生成算法1 3 4 1 空阳j 多子割1 3 4 2 空m 探索1 5 4 2 j ，厨! 矿矿分1 6 4 z 2 生 阿戏剪j 6 4 2 3 隽 珐丝麂扮笏17 4 3 评f i o i 层1 7 4 王j 洲；左循觥秀葶艽1 7 重i 2 黝钐缶黝蒯1 8 4 4 本章小结1 8 第五章基于目标的数据库测试查询生成算法改进 1 9 5 1ti n d e x 采样模式的缺点1 9 5 2 综合采样模式的优点一1 9 5 3 采样算法的i 口l 顾1 9 i ijti n d e x 采襻旋艿多舅漾。2 0 5 3 2tc r o s s 粟7 掌旋才争缠 2 j 5 3 3 改拦算弦一缮台粟存微2 j 5 4 综合采样算法性能分析2 2 5 4 1 丢争豸警刍 i 集z 严猫羹坶；2 2 5 4 2 带谚07 镶f 黝j ! z 乎泓 5 5 本章小结2 6 第六章改进前后的目标测试查询生成算法的性能评估 | 1 1 2 7 _ - - - - - - - - 4 4 4 5 l n i n 5 6 7 8 - - - 一 - 一 - 东南人学f 砍i j 学位论义 6 1 系统架陶 6 2 实验结果 6 2 1 一维约震劈倒 6 2 2 多维约束：g 振奋询生成 6 3 总l ； 第七章结论 致调 参考文献 攻读硕士期间发表论文 第一帚绪论 1 1 论文研究背景与意义 第一章绪论 不合理的数据库设计和s q l 语句都会带来数据库性能l u 】题。当数据库设计过程当中引进 了一项新技术，必须在不同操作系统坏境下测试新数据库系统的性能，通常，数据库测试会 选择一套复杂的数据集和s q l 查询集，分别在引进新技术前后的数据库系统中执行，最后比 较二者的性能。只有性能有所改进，该技术才能得到肯定。 数据库系统建立之后，必须通过输入大量的测试数据来验证数据库的性能。测试数据是 为数据库中的一个或者多个数据表生成的样本数据，可以通过测试数据验证数据库的性能， 从而对数据库的质量进行评估，以便对数据库设计进行优化。在目前的数据库测试技术研究 中，文献9 ，1 1 ，1 7 1 已经为构造满足属性条件的合成数据做了大量研究。下一步需要基于产生的 数据构造大量的s q l 查询，文献 1 6 ，1 4 研究开发了r a g s ，q g e n 等能产生大量随机s q l 查询的查询生成器，最后在数据库系统上执行这些查询，根据查询的结果与之前产生的测试 数据的一致程度来测试该数据库系统的性能。 然而，以上研究生成的测试数据和测试查询集大都基于测试数据集的数据模式，即只考 虑了数据集逻辑模式( 视图) ，没有考虑现实数据实例特性( 如数据偏斜性、数据相关性等) 。 因此这些工具在构造满足特定要求的查询时存在一些缺陷。 例如，对于一个新设计的数据库内存管理器，希望测试其给多层哈希连接查询带来的影 响，即在进行哈希连接操作时内存管理器为每个中间结果分配的内存大小对查询操作性能的 影响。在设计测试用例时要考虑很多s q l 连接查询，而这些s q l 连接查询产生的子查询中 满足条件的元组个数存在很大差异，即中间结果的内存需求各异。哈希连接的内存需求由内 部和外部输入大小决定。给定一个数据集，可以通过改变关系表的选择条件来控制输入的大 小。目前在没有其它额外信息的情况下，只能通过不断地试错来找到能够满足一定选择条件 的参数。对该问题进一步研究，例如，测试基于管道实现的查淘处理器组件的连接算法性能， 需要构造大量的s q l 连接测试查询，并且控制这些s q l 测试查询的子查询中间结果集大小。 然而由于数据的偏斜( s k e w ) 特性和属性之间的相关性，测试的实现具有很大困难。 本文提出的目标查询生成技术通过减少测试所需时问和提高测试准确性缩短数据库系统 引进新技术的周期。 1 2 目标查询生成技术研究的现状和存在的问题 数据库测试的早期，各厂商使用的测试指标，方法及系统配置等各异，往往突出各自的 优点，隐藏其缺点。在这种情况下出现了一些测试程序标准组织，最具代表性的有专门制定 事务处理和数据库领域的测试程序标准机构t p c ( t r a n s a c t i o np r o c e s s i n gp e r f o r m a n c e c o u n c i l ) ，t p c 为数据库测试和事务处理系统制定了标准测试序列，包括t p c c 、t p c h 、 t p c w 、t p c r 。 b r u n o 【i j 在2 0 0 6 年第一次提出目标查询生成相关问题，其研究产生的具体查询实例基于 一个约束集而并不是随机产生。但其只研究一维势约束的特例，而且指出多维情况下该问题 的确切解是一个n p 问题。还基于选择条件之间的独立性假设提出了爬山法，将查询生成分 东i 萄人学硕l j 学位论丈 成两个步骤：第一步，中明j 也牛f = j 标查询的语义约束；第二步，找到满足约束的查询实例。 第一步依赖于评估组件，因此需要人工干预，第二步则可以自动化。 其研究存在的i 、u j 题与不足有： 1 其研究只是基于一维势约束的特例； 2 其研究提出的爬法基于选择条件之间独立性假设，且该方法容易陷入局部最小，迭代 过程若进行适当修剪可以优化算法： 3 其研究指h j 在多维势约束情况下得不到确切解。 b i n n i g i 二i 在2 0 0 7 年提j 也查询敏感的q a g e n 算法，传统数捌霄测试中首先给i 【 测试数据， 然后根据所给数据来产生测试奁询，与传统做法相反，q a g e n 足根据测试金询来产生“量身 定做”的测试数据，输入数据视图、测试查询和查询约束，输出所需的测试数据。数据生成 分为两步：第一步，符号查询处理；第二步，实例化数据。第一步引入符号处理器和条件解 析器两个组件，目的是符号化用户定义的约束。q a g e n 能为复杂查询产生查询敏感的测试数 据。 其研究存在的问题与不足有： 1 其研究为每个测试查询用例产生一个不同的数据集，该方法由于内存负载过重而不适于 测试数据库新性能： 2 其研究所使用的符号查询处理器速度慢且价格昂贵； 3 其研究支持的操作和用例有限。 m i s h r a ，k o u d a s ，z u z a r t e1 3 】提出一种目标查询算法来获得和目标近似的结果，该算法在 二分查找过程中采用贪心算法，该贪心算法在真实数据库中引用采样技术来进行数据采样， 并利用空问裁剪算法优化测试查询，最终产生基于现实数据的目标查询。 其研究存在的问题与不足有： 1 其研究为每个测试查询用例产生一个近似满足条件的数据集； 2 其研究基于数据表中各列之i 、日j 相互独立假设； 3 其研究应用的ti n d e x 采样具有局限性，因为ti n d e x 采样假设参与连接的两张表都建立 了索引，并没有考虑到现实的数据库中很多表并没有建立索引。 1 3 论文的工作目标和研究内容 本文的工作目标是提出一种基于现实数据并且查询敏感的查询自动生成算法，以构造基 于现实数据分布及符合特定的数据特性要求的s q l 测试查询。针对特定的测试用例，通过控 制其中问结果集的输入输出大小，使得测试查询集和测试数据集更精确、效率更高，以达到 有效改进数据库测试效果的目的。 本文致力于对m i s h r a ，k o u d a s ，z u z a r t e1 3 】提出的目标查询算法进行改进和完善，使产生 的目标查询既能像b r u n o i l l 提出的算法那样使s q l 查询产生的中间结果和预期一致，又能像 m i s h r a ，k o u d a s ，z u z a r t e 1 3j 提出的算法那样为测试数据产生基于现实数据的目标查询。 本文提出的目标查询生成算法首先将数值域约束条件问题转化为空间域约束条件问题， 然后通过二分查找、空间分割及空间裁剪确定空i 日j 域约束条件中的参数值。二分查找过程采 用一种基于评估层采样的贪心算法。本文重点研究现有的采样技术，然后针对目标查询生成 问题提出了一种综合采样技术，从而有效优化查询条件的参数范围选择。该目标查询生成算 法还用到以下几种技术： 概率消除技术：用ti n d e x 采样算法时，用到概率消除技术。概率消减技术的输入为关系 r 的采样样本r ，然后将子连接s + 中和r 中至少有一个元组连接的元组从s 中删除。尽 一管这个简单的技术并不实际判断删除哪个子连接或哪个元组，但是实验却表明每个子连 接中的元组对数评估值以一个很大的概率在一个很小的误差因子范围内。 第一章绪论 基于现实数据的采样厅法：海最的信息隐臧在具有特定查淘能力的查询接口后，使人无 法了解一个数据实例特征。基于现实数据采样方法通过从数据库中以增量的方式获取近 似随机的样本进行数掼一：分布估计。 基于贪心算法的空l 、h j 裁剪方法：结合计算几何中多维空问点集的剖分方法一贪心算法， 在多维约束集数据处理过程中引入该贪心算法，提出一种基于网格f 用贪心算法进行空间 点集的剖分) 的空问裁剪方法。对窄问的拓扑结构进行按规j l ! | j 等分，得到n 维的网格，利用 贪心算法寻找若干参考点，最后给这些参考点打分，分数最高的点就是所期望的解。 1 4 论文的组织安排 本文的内容共分七章，具体安排如下： 第一章绪论，介绍论文研究背景以及目标查洵生成技术研究的现状和存在的问题。 第二章描述基于采样的连接选择性评估算法。 第三章和第阴章提出并详细介绍基于目标的数据库测试查询生成算法。 第五章对第四章的查询生成算法进行改进。 第六章将改进后的算法性能和m i s h r a ，k o u d a s ，z u z a r t e1 3 】提出的目标查询算法性能进行 实验比较。 第七章回顾整个测试查询生成的工作，对全文做一个总结。 第二章堆十采样的连接选择悱计估算法 第二章基于采样的连接选择性评估算法 本研究的主要：i 一作是提出综合采样算法来改进现有的目标测试查询生成算法。综合采样算 法的提出需要先比较现有的六种基于采样的连接选择性评f r 与算法的性能，通过比较分析后综 合现有算法的优点，对现有算法存在的缺陷进行改进，最后得到具体的综合采样算法。 目标测试查渐生成算法利用空l 、日j 分割和窄i 、日j 裁剪来优化测试奄淘。冈为连接选择性评估不 仅能判定空间裁剪过程是否选择了一个较好的空| 白j 算子，而目能以比较小的代价估计出空间 算子的结果集大小。目标查洵生成算法需要根据这个结果集来优化，e 成的查询。因此，采样 的连接选择性评估算法的性能高低直接影响着目标测试查询生成算法性能的高低。所以在分 析目标测试查询问题之前有必要先介绍基于采样的连接选择性评估问题。 2 1 连接选择性问题描述 在查询优化，容量规划、在线查询丌销估计、系统访问控制和负载均衡中都间接用到连 接选择性估计。而在审计和统计研究中则直接用到连接的选择性估计。如果巧妙设计，基于 采样的连接选择性估计算法可以既快速又准确。该算法不要求对数据的统计信息进行保持和 存储，在数据相互关系和偏斜性方面也具有鲁棒性。 对于给定的关系r 和s ，等值连接r 冈s 的选择性是指笛卡尔积r s 上的相关元组裂片 的选择。连接的选择性估计是一个很具有挑战性的问题，因为等值连接r 冈s 得到的元组数 比笛卡尔积r s 中的元组数要少得多。例如：如果r ，s 和r 冈s 中的元组个数都为1 0 6 ，那 么从r 中随机选择的一个元组和s 中随机选择的一个元组连接的概率只有1 1 0 6 。所以需要对 r s 中大量元组进行恰当观察以确保选择性评估足够准确。评估算法的成本越低越好。 2 2 两大类连接选择性评估算法比较 连接选择性评估算法分别反复从关系r 和5 获得元组样本，将两组元组样本进行连接， 然后观察连接后的元组有多少出现在目标连接中，这种方法称为独立采样模式。连接选择性 评估算法也可以从r s 中获得随机元组并观察这些元组有多少出现在连接中，这种方法称为 叉积采样模式。独立采样模式每步采样后将样本丢弃。叉积模式每步采样后将样本元组存储 在内存中，然后观察采样得到新的和之前存储得到的元组，最后记录结果。如果关系s 在连 接键上建立了索引，那么存在第三种方法，即每步从关系r 随机均匀地选取一个元组，利用 索引来计算s 中和r 中随机选取到的元组连接后的元组数目。这样，每步采样能够观察r s 中的l s1 个元组，其中i si 表示关系s 中元组的个数。这种方法称为索引采样模式。 这三种方法都可以归纳成两大类：元组级采样模式和页级采样模式。这两类方法在r s 的每个采样过程中观测到的元组数各不相同。元组级采样方法每步采样分别从r 和s 中随机 均匀地选取一个元组，然后和从r s 中随机均匀选择得到元组一一对比，这导致无限多次的 ，o s 。然而，页级采样模式由于元组已经以页为单位存储在主存中，对每个关系可以以页 为单位来采样，然后利用采样到的页中的元组。这样页级模式每次，o 观察到的r s 中的元 组数比元组级模式更多。 东南人学硕i ：学位论文 2 3 六种连接选择性评估算法比较 将2 2 节的选择方式进行组合得到六个不同的采样算法：t i n d e p ，t c r o s s ，t i n d e x ， p i n d e p ，p c r o s s 和p i n d e x 。有关的数据采样文献已经提出了这些算法，但是对这些算 法从没有做过性能方面的研究。本节将比较分析这六种连接选择性评估算法的性能并给 f 分 析结果。 2 3 1 连接选择因子的概念 本节首先研究关系r 和s 等值连接r n s 的选择因子肛，肛= ( i r 冈si ) ( 1 ri i si ) 。 假设元组在内存中的存储和调动以页为单位，且每页中的元组数k 1 。用统一的方法对独立 采样模式、叉积采样模式和索引级模式进行分析，本文给出一个广义的采样模型，将关系r 中的元组分为l 个块，标e 为i , 2 ，l 的块中的元组数为巩。同理，将关系s 中的元组分为m 个块，标记为1 2 ，m 的块中的元组数为肌。当- - - - n s = 1 时，该模型简化为元组级模式；当 2 月s2 庀时，该模式演化为页级模式。关系r 的块z 和关系s 的块m 等值连接的选择性记 为v ( t ，m ) 。即v ( z ，m ) 的值为块z 和块m 等值连接得到的元组数除以总数飞。连接选择因子可 以表示为： 1 】i f “；土了yv “，1 ) l m 白急。 ( 式2 - 1 ) 2 3 2 连接选择因子的无偏估计 假设存在索引z ，m ，z 和m 使得v ( z ，朋) v ( 1 ，mr ) 。当对所有的索引，m ，z 和m 都 有 ，( z ，优) = v ( t ，mr ) ，这是个p r i o r i 问题，那么评估问题是平凡的。 本章第二节指出，本文考虑两个重复利用已有样本的方法：独立采样和叉积采样。独立 采样模式的第，l 步，遍历关系r 随机选取的块。中的所有元组和关系s 随机选取的块m 。中 的所有元组。那么 犯。，m 。) ：咒1 是块索引的一个独立一致分布随机序列，t 和m 。相互独立， 对1s ，sl ，有p l 。= ，】= 1 l 。对1sm m ，有p o f 。= 优】- = 1 m 。这两个块的等值连接选 择因子k 。= ，犯。，m 。) ，n 步后，u 的自然估计为： k = i 荟nk ， ( 式2 2 ) 估计k 是无偏的，因为e i l 。肛。估计量的方差为砌厂【k 】。一0 - l ，其中 ，l 仃2 = 面1 丢l 磊m ( v ( l 胁) 一) 2 ( 式2 _ 3 ) 2 4 两种采样模式下连接选择性评估算法比较 叉积采样模式和独立采样模式的区别在叉积采样每步采样得到的块中的元组不丢弃而是 存储在内存中。因此每步连接选择因子除了计算从关系r 和s 中采样得到的新块中的元组等 笙：里竺芏鲞! ! 竺坚堡垄堡：! 鲨篁翌鲨 值连接外，还要汁算关系r 中采样得到的新块和s 中之自，j 采样得剑的块中的元组等值连接及 关系s 中采样得到的新块和r 中之前采样得到的块中的元组等值连接。给定上面的解释，可 知又积采样模式的第，z 步能得到2 n 一1 个观察样本：杉，k ，k , n - i ，k 屹川，k - 1 , nk 一，其中 v ，= v ( ，m ，) 。在，z 步叉积采样后，可以得到甩2 个观察样本。而甩步独立采样后，只得到甩个 观察样本。通过观察可知n 步独立采样得到的n 个观察样本之i 、h j 是统计独立的，然而n 步叉积 采样得到的观察样本k ，和k 2 _ _ i a j 在i - - k 或_ = z 时是相关的。，l 步后，叉积模式中弘的估计 为： e 2 砉善荟k ， ( 式2 - 4 ) 可以看出e 是无偏估计，当，z 1 时，e 叱】= 肛。进一步有：当n 1 时， v a r y 。 ：去仃2 + 掣孑2 ( 式2 - 5 ) 当n 1 时， 。 扩。圭善( ”+ 吉薹刊2 却 ( 式2 。6 ( 式2 - 6 中的总量一和的定义为：胁2 吉荟v ( l 优) ，2 去善v ( 厶研) ，其中： 1szsl ，1smsm 。 将元组级、页级采样和独立、叉级采样组合合，得到四个评估算法t i n d e p 、p i n d e p 、 t c r o s s 和p c r o s s 。当用n r = 1 和仫= l s l ( 即关系s 只分成一个块) 的独立采样可以得到算法 t i n d e x 。同理，用n r = k 和n s = i si 的独立采样可以得到算法p h l z d e x 。 2 4 1 连接选择性评估的偏序性 下面提供比较不同估计算法在固定步采样后“变异估计的依据。( v a r 代表变异性，变异 性越小，评估的统计有效性越高。) 首先比较独立采样和叉积采样，一个n 步采样的固定分割 模式( 即n 。和n 。固定) 用k 表示基于独立采样的估计，用k 表示基于叉积采样的估计。 定理1 ：当n 芑1 时，有v a r y1s】。v a r y 。 定理l 的证明见参考文献 5 7 1 。它断言尽管得到的观察样本是统计相关的，但统计有效 性不会随着已有样本块的重复利用而降低。 下面比较同一种采样( 独立采样或者叉积采样) 模式下，不同的分割模式情况的评估变 异性。用e 表示关系r 分割后每个块的元组数n 。和关系s 分割后每个块的元组数n ，的估计， 用y 。表示关系r 分割后每个块的元组数n 。和关系s 分割后每个块的元组数nv s 的估计。在 第一种分割模式下，关系r 的第一个块中的元组个数为1 到n r ，第二个块中的元组为n r + 1 到 2 ，l 。同理，关系s 的第一个块中的元组个数为1 到n 。，第二个块中的元组为n ，+ 1 到2 ，l 。 第二种分割模式也做同样的假设。 定理2 ：假设整数k r ，k s 乏1 ，并且，lk = k 和甩i = k s n s ，那么对n 1 有v a r y 。】sv a r y 。】。 定理2 的证明见参考文献 5 7 1 。定理2 断言尽管元组的连接键值可能是统计相关的，统 计有效性不会随着每个样本中的元组数的减少而减少。实际上，定理1 和定理2 证明了变异 之间的严格不等性。 定理1 和定理2 用来比较固定步评估算法t i n d e p 、p i n d e p 、t c r o s s ，p c r o s s ， t i n d e x 和pi n d e x 的变异性。如果在n 步( n 1 ) 采样后，p r o c1 评估算法的变异评估值 东南人学坝l ：学位论义 小于或等rp r o c 一2 评估算法的变异评估值，那么p r o c 一1 s 。p r o c 一2 。若相等记为 p r o c 一1 = 。o r o c 一2 。另瞄么有p c r o s ss ，f c r o s s5 ，f i n d e p ，p c r o s ss ，p i n d e ps 。f i n d e p 矛口p i n d e xs 。t i n d e x 。可以推出：t i n d e xs ，f c r o s s 和p i n d e xs ，p c r o s s 。自i f 面提至0 t 一砌撅算法和，l r = l 矛t l n s = i si ( 即关系s 只分成一个6 肠出) 的独立采样相对应。 p _ i n d e x 。 ti n d e x 图2 - 1 六种采样算法的连接选择性估计比较 从图中不难看出，算法p i n d e p 和f c r o s s 是不可比较的，根据不同算法p i n d e p 得到的 变异性估计值可能大于也可能小于算法f c r o s s 得到的估计值。同理，算法p c r o s s 和 t i n d e p 也是不可比较的。 2 5 本章小结 本章比较了六种基于采样的连接选择性评估算法的性能。因为采样的连接选择性评估算 法的性能高低直接影响着目标测试查询生成算法性能的高低，所以本章先给出连接选择性评 估的一些概念，为下面章节分析采样算法准备预先知识。有关数据库采样的文献 5 5 ，5 6 1 已经 提出一些采样算法，这些算法将在第五章中详细分析，本文对传统采样算法做一些改进后为 本研究用到的评估层丌发出一种综合采样算法，通过这种综合采样算法束使m i s h r a ，k o u d a s ， z u z a r t e1 3 j 提出的目标查询算法效率更高，适用性更强。 f 加 卫 第j i 章恭 二日标的数捌库测试色t 白j 生成 u 题分忻 第三章基于目标的数据库测试查询生成问题分析 上一章的连接选择性评估算法用于采样过程，而目标查询生成算法采用基于采样的评估 层柬优化算法。下面详细介绍目标测试查询生成i 、u j 题，再根掘基f 采样评估层在目标查询生 成算法中出现的位置柬引进综合采样算法，进而对目标畲询生成算法进行改进。 本章考虑多维目标测试查询生成问题时，将多维势约束条件的参数值的确定问题简化为 求多维线性方程组解i u j 题。 3 1 基于目标的数据库测试查询生成问题描述 图3 - 1 描述一个简单测试用例，给定一个查询q ，一个子查询的目标势约束集，执行查 询的测试数据库d 。本文修改q ，产生一个满足目标势约束的新查询q 7 ，修改查询q 的选 择条件并确定条件中的参数值，称这个问题为目标测试查询生成i 、u j 题。 s e l e c t f r o ma ，b ，cw h e r e ai d = bi da n dbi d 2 i d 2a n d a x 5 0 0a n d c 7 _ 5 0a n dc w 2 0 0a n dcw 2 0 0 0 图3 一l 一个简单的测试用例 3 1 1 基于目标的数据库测试查询生成问题的定义 1 0 0 k 给定一个数据库d 和一个定义在关系r l ，r 上的连接查询，查询有d 个范围约束条件 日，每个范围约束格式如r ；x i c i 。将一个双边约束分解为两个单边约 束。接下来，不失一般性地假设p 的格式为薯 c 可以改写为一x i 一c ，用d 和 c ? 来表示条件p 定义的值域下限和上限，条件只中的常量c 满足c lsc ，sc i “，条件p 的取 值范围为掣一d + 1 ，把条件只称为第f 维，查询q 有d 个维度。范围条件只能修改表达式里 的常量，如a g e 5 0 可以改为a g e 5 0 和c w 1 的用例。 3 2 一维势约束 考虑一维势约束的目标测试查询生成问题，下面给出只需d ( dl o g n ) 次访问评估层的一维 约束算法。 算法1 一维约束算法 1 ： 2 ：s i n g l e c o n s ( q ，) ( 3 ：q 7 = a ； 4 ：e = e r r o r ( q u e r y ( q r , d ) ，) ； 5 ：f o ，每一维f 如 6 ：p = p r e d i c a t e ( q ) ： 7 ： 只= u 比； 8 ： a 。= q u e r y ( p ) ； 9 ： o = f i n d ( q p , n ) ； 给定数据库d 一维约束( 查询q ，目标n ) 检布q 的误差 使第f 维条件失效 生成一个新的查询 1 0 ：e = e r r o r ( o u e r y ( q r , d ) ，n ) ；检查q 的误差 1 1 ：i fe e t h e n 1 2 ：