（计算机科学与技术专业论文）分布式序敏感查询处理关键技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 近年来，随着信息技术的迅猛发展，信息资源极大丰富。如何从海量数据中 快速提取少量的最有价值的信息成为了数据库领域面临的一个重大挑战。在此背 景下，数据库领域在最近几年产生了两个新兴的查询分支：t o p k 查询和轮廓查询。 t o p k 查询是根据用户指定的聚集函数查找聚集值最高的前k 个对象：而轮廓查询 则是查找不被其它对象“支配”的对象集。这两种查询为海量数据的查询处理提 供了全新的思想和方法，得到了广泛的研究与应用。由于t o p k 查询和轮廓查询都 是关注含有排序信息的结果集，在本文中我们把t o p k 查询和轮廓查询统称为序敏 感查询。 传统的数据库查询处理技术只能处理存储在磁盘或内存等介质中的静态数据， 而在许多应用中，数据往往以是流的形式动态产生并且不被保存。这种数据模型 被称为数据流模型。数据流模型所具有的无限、连续、快速、实时等诸多特征使 得传统的数据库管理技术无法用于数据流的管理。数据流管理技术也因此成为了 近年来数据库领域研究热点之一如何支持数据流上的序敏感查询处理也正在得 到越来越多的关注。为了区分数据库系统中的快照式查询处理和数据流系统中的 连续的查询处理，在本文中我们将数据库系统中的查询处理称为快照查询处理， 将数据流系统中的查询处理称为监测查询处理。 随着计算机网络技术的发展，越来越多的数据资源产生或存储于网络之中。 如何实现分布式数据资源上高效的序敏感查询处理成为了数据库研究领域的一个 重要问题。目前，分布式序敏感查询处理技术已经取得了一些有价值的探索性成 果，但是总体上还处于发展初期，在许多方面尚未成熟。 在此背景下，本文针对己有工作的某些不足，着重对分布式t o p k 快照查询处 理、分布式t o p - k 监测查询处理和分布式轮廓快照查询处理技术展开深入研究，主 要工作包括： 1 分布式t o p - k 快照查询处理方面。网络延迟对分布式快照查询处理的查询响 应有着严重的影响，而已有的t o p - k 快照查询处理算法对这一方面的考虑不足。针 对这一问题，提出了一种实现非阻塞t o p k 快照查询处理的方法。该方法将异步的 数据访问和渐进式的结果输出相结合，以获得快速的查询响应。基于该方法提出 了一种非阻塞t o p - k 快照查询处理算法p r 及其改进型算法a p r 。理论分析表明， a p r 算法的平均网络流量低于现有同类算法，最大网络流量与现有同类算法相同； 实验结果表明，a p r 算法在响应时间、执行时间和网络流量方面均优于现有同类 算法。 2 分布式t o p - k 监测查询处理方面。分布式t o p k 监测查询处理的核心问题是 第i 页 国防科学技术大学研究生院博士学位论文 如何减少监测过程中的网络流量。针对这个问题，对分布式t o p - k 监测查询处理的 特性进行了深入的理论分析，证明了发生约束冲突的对象集是重新建立监测约束 时所需要的最小集，并提出了一种基于最小约束重建集的约束重建方法。该方法 在重建约束时传输的对象为最少。基于该方法提出了一种面向求和运算的分布式 t o p k 监测查询处理算法m r 。理论分析表明，m r 算法通讯代价与k 无关；实验结 果表明，当k 不小于l o 时，m r 算法的网络流量只有已有同类算法的1 0 5 0 左右。另外，由于m r 算法和已有同类算法都只支持求和运算作为t o p k 监测查询 处理的聚集函数，而在实际应用中，用户给定的聚集函数可能是任意的单调聚集 函数，为此，我们进一步提出了基于最小约束重建集的通用的分布式t o p k 监测查 询处理方法。基于该方法提出了一种支持任意的连续的严格单调函数的分布式 t o p - k 监测查询处理算法g m r 。理论分析表明，g m r 算法的通讯代价是独立于k 值；实验结果表明，g m r 算法的网络流量比朴素的同类方法低一个数量级以上。 3 分布式轮廓快照查询处理方面。如何在节点数较大时减少查询时的网络流 量是分布式轮廓快照查询处理面临的一个重要问题。针对这个问题，提出了分阶 段数据访问来降低网络流量的方法，并由此提出了一种四阶段分布式轮廓快照查 询处理算法f d s l 。实验表明，f d s l 算法在节点数超过4 时在网络流量方面优于 同类算法。 4 基于上述关键技术的研究探索，以海量数据处理中间件s t a r t p m o n i t o r 为支 撑平台，设计并实现了面向海量信息的、支持分布式序敏感查询处理的分析查询 处理引擎s t a r a n a l y s i s 。测试表明，s t a r a n a l y s i s 能够有效的支持海量数据上的分布 式分析查询处理。 综上所述，本文针对分布式序敏感查询处理的几个关键问题提出了有效的解 决方案，对提高分布式序敏感查询处理的效率和实用化程度具有重要的理论意义 和实用价值。 主题词：分布计算，数据库，序敏感， 快照查询处理，监测查询处理，分析查询， t o o k 查询，轮廓查询，数据流管理， 查询处理引擎 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t i nr e c e n ty e a r s ，谢mt h er a p i dd e v e l o p m e n to ft h ei n f o r m a t i o nt e c h n o l o g y ， i n f o r m a t i o nr e s o u r c e sh a v e b e e ng r e a t l ye n r i c h e d h o wt or e t r i e v et h es m a l la m o u n to f t h em o s tv a l u a b l ei n f o r m a t i o nf r o mt h em a 鼹i v ed a t aq u i c k l yh a sb e c o m eag r e a t c h a l l e n g ef o rt h ed a t a b a s ef i e l d i nt i f f sb a c k g r o u n d ，t h e r eh a v eb e e nt w on e wq u e r y b r a n c h e sr a i s e di nt h ed a t a b a s ef i e l di nt h ep a s tf e wy e a r s ，w h i c ha r et h et o p - kq u e r ya n d t h es k y l i n eq u e r y n 圮t o p - kq u e r yi st of i n dt h eko b j e c t sw i t ht h eh i g h e s ta g g r e g a t e v a l u e s ，a c c o r d i n gt oau s e r - s p e c i f i e da g g r e g a t ef u n c t i o n , w h i l et h es k y l i n eq u e r yi st o f i n dt h eo b j e c t sw h i c h 黜n o t “d o m i n a t e d b yt h eo t h e ro b j e c t s t h e s et w oq u e r y m e t h o d sp r o v i d en o v e li d e a sa n dm e t h o d sf o rt h eq u e r yp r o c e s s i n go v e rt h em a s s i v e d a t a t h e r e f o r e ，t h e yh a v er e c e i v e dw i d ea 删o n s ，a n db e c o m eah o tt o p i ci nt h eq u e r y p r o c e s s i n gr e s e a r c hf i e l d a sb o t ht h et o p - kq u e r ya n dt h es k y l i n eq u e r yc o n c e ma b o u t t h er e s u l t sw i t hr a n ki n f o r m a t i o n , w eg i v eau n i f o r mn a m ef o rt h et o p - kq u e r ya n dt h e s ly l i n eq u e r ya st h er a n k a w a r eq u e r yi nt h i sd i s s e r t a t i o n n l et r a d i t i o n a ld a t a b a s eq u e r yp r o c e s s i n gt e c h n o l o g yc a no n l ym a n a g et h es t a t i c d a t a , w h i c ha r es t o r e di nt h em e d i u ms u c ha sd i s ko rm e m o r y ，w h i l ei nm a n y a p p l i c a t i o n s ，t h ed a t aa r co f t e ne m e r g e da sd y r l a l n i cs t r e a m sa n dn o tt ob ep r e s e r v e d t m sd a t am o d e li sk n o w na st h ed a t as t e a n lm o d e l w h i c hh a ss o m es p e c i a l c h a r a c t e r i s t i c s ，s u c ha st h ed a t as t r e a ma r eu n l i m i t e d ，c o n t i n u o u s ，r a p i d ，r e a l t i m ea n ds o o n s ot h ed a t as t r e a m sc a n n o tb em a n a g e db yt h et r a d i t i o n a ld a t a b a s em a n a g e m e n t t e c h n o l o g y t h e r e f o r e ，d a t as t r e a mm a n a g e m e n tt e c h n o l o g yh a sb e c o m eo n eo fh o t s p o t s i nt h ed a t a b a s ef i e l di nr e c e n ty e a r s i ti si i o wr e c e i v i n gm o r ea n dm o r ec o n c e r n st h a t h o wt os u p p o r tt h er a n k - a w a r eq u e r yp r o c e s s i n go v e rd a t as t r e a m s t od i s t i n g u i s h b e t w e e nt h es n a p s h o t - s t y l eq u e r yp r o c e s s i n go f t h ed a t a b a s es y s t e ma n dt h ec o n t i n u o u s q u e r yp r o c e s s i n go ft h es t r e a ms y s t e m ，i nt h i sd i s s e r t a t i o n , w ec a l lt h eq u e r yp r o c e s s i n g o ft h ed a t a b a s es y s t e ma st h es n a p s h o tq u e r yp r o c e s s i n g ，a n dt h a to ft h ed a t as t r e a m s y s t e ma st h em o n i t o r i n gq u e r yp r o c e s s i n g w i t ht h e d e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g y m o r ea n dm o r ed a t a i e s o n r c e sa r ee m e r g e do rs t o r e di nt h en e t w o r k s i th a sb e c o m ea ni m p o r t a n tp r o b l e m t h a th o wt oa c h i e v et h er a n k - a w a r eq u e r yp r o c e s s i n ge f f i c i e n t l yo v e rt h ed i s t r i b u t i o n d a t ar e s o u r c e s c u r r e n t l y ，t h er e s e a r c ho ft h ed i s t r i b u t e dr a n k - a w a r eq u e r yp r o c e s s i n g t e c h n o l o g yh a sm a d es o m ev a l u a b l ee f f o r t sw h i c h , h o w e v e r , a r es t i l li ne a r l ys t a g e so f d e v e l o p m e n to v e r a l l ，a n da r en o tm a t u r ei nm a n yw a y s i nt h i sb a c k g r o u n d ，a i m i n gt 0o v e r c o m es o m ed e f i c i e n c yo ft h ee x i s t i n gw o r k s ，t h i s d i s s e r t a t i o nc o n d u c t sa l li n - d e p t hs t u d yw h i c hf o c u s e so nd i s t r i b u t e dt o p - ks n a p s h o t q u e r yp r o c e s s i n g ，d i s t r i b u t e dt o p km o n i t o r i n gq u e r yp r o c e s s i n ga n dd i s t r i b u t e ds k y l i n e s n a p s h o tq u e r yp r o c e s s i n gt e c h n o l o g i e s n 虻m a i nc o n t e n t so ft h i sd i s s e r t a t i o na r ea s 第试页 国防科学技术大学研究生院博士学位论文 f o l l o w s ： 1 d i s t r i b u t e dt o p ks n a p s h o tq u e r yp r o c e s s i n g 1 1 圮n e t w o r kd e l a yi sas e r i o u s e f f e c to nt h ep e r f o r m a n c eo fd i s t r i b u t e ds n a p s h o tq u e r yp r o c e s s i n g h o w e v e r , t h e e x i s t i n gw o r k sa r el a c ko fc o n s i d e r a t i o no v e ri t t oa d d r e s st h i si s s u e ，w ep r o p o s ean e w m e t h o dt oa c h i e v en o n - b l o c k i n gt o p - ks n a p s h o tq u e r yp r o c e s s i n g b ya c c e s s i n gd a t a s o u r c e sa s y n c h r o n o u s l ya n dp r o d u c i n gr e s u l t sp r o g r e s s i v e l y ，t h i sm e t h o dc a r lp r o d u c e t h ef i r s tf e wr e s u l t sq u i c k l y b a s e do nt h i sm e t h o d ，w ep o p o s ean o n - b l o c k i n gt o p - k s n a p s h o tq u e r yp r o c e s s i n ga l g o r i t h mn a m e dp ra l g o r i t h ma n di t si m p r o v e ra p r a l g o r i t h m t h et h e o r e t i c a la n a l y s i ss h o w st h a t , i nt h et e r m so ft h ea v e r a g en e t w o r k t r a f f i c ，a p ri sb e t t e rt h a nt h ee x i s t i n ga l t e r n a t i v e s , a n di nt h et e r m so ft h em a x i m u m n e t w o r kt r a f f i c a p ri st h es a m et ot h ee x i s t i n ga l t e r n a t i v e s t h ee x p e r i m e n t a lr e s u l t s s h o wt h a t ，i nt h et e r m so ft h en e t w o r kt r a f f i c , t h em s p o n s ct i m ea n dt h ee x e c u t i o nt i m e ， a p ri ss u p e r i o rt ot h ee x i s t i n ga l t e r n a t i v e s 2 d i s t r i b u t e dt o p km o n i t o r i n gq u e r yp r o c e s s i n g i ti st h ek e yi s s u eo fd i s t r i b u t e d t o p km o n i t o r i n gq u e r yp r o c e s s i n go v e rt h em u l t i p l ed a t as t r e a m st h a th o w t or e d u c et h e n e t w o r kt r a f f i ci nt h em o n i t o r i n gp r o c e s s t oa d d r e s st h i si s s u e ，a ni n - d e p t ha n a l y s i sh a s c o n d u c t e df o rt h ec h a r a c t e r i s t i c so fd i s t r i b u t e dt o p - km o n i t o r i n g ，a n dw ep r o v ea t h e o r e mt h a tt h eo b j e c t ss e tw h i c hb r o k e nt h ec o n s t r a i n t si st h em i n i m a ls e tw h i c ha r e n e e d e df o rt h ep r o c e s so fr e b u i l d i n gt h ec o n s t r a i n t s t h e r e f o r e ，w ep o p o s eam e t h o do f r e b u i l d i n gc o n s t r a i n t sb a s e do nt h em i n i m a lc o n s t r a i n t sr e b u i l d i n gs e t i nt h i sm e t h o d t h en u m b e ro fo b j e c t st h a tn e e dt ob et r a n s m i t t e di sm i n i m a l b a s e do nt h em e t h o d ，a s u m - o r i e n t e dd i s t r i b u t e dt o p - km o n i t o r i n gq u e r yp r o c e s s i n ga l g o r i t h mm ri sp r e s e n t e d n l et h e o r e t i c a l a n a l y s i s s h o wt h a tt h en e t w o r kt r a f f i co ft h em ra l g o r i t h mi s i n d e p e n d e n to fk t h ee x p e r i m e n t sr e s u l t ss h o wt h a tt h en e t w o r kt r a f f co fm r i sa b o u t 1 0p e r c e n t a g et o5 0p e r c e n t a g eo ft h a to ft h ep r e v i o u sa p p r o a c h i na d d i t i o n ，m r a l g o r i t h ma n dt h ep r e v i o u sa p p r o a c ho n l ys u p p o r tt h es u mf u n c t i o na st h ea g g r e g a t i o n f u n c t i o no ft o p - 七m o n i t o r i n g ，w h i l ei nt h e p r a c t i c a la p p l i c a t i o n s ，t h ea g g r e g a t i o n f u n c t i o nc a nb ea na r b i t r a r ym o n o t o n ea g g r e g a t i o nf u n c t i o n t h e r e f o r e ，b a s e do nt h e m i n i m a lc o n s t r a i n t sr e b u i l d i n gs e t ，ag e n e r i cm e t h o df o rd i s t r i b u t e dt o p km o n i t o r i n g q u e r yp r o c e s s i n gi sp r e s e n t e d b a s e do nt h i sm e t h o d ，w ep r o p o s ead i s t r i b u t e dt o p - k m o n i t o r i n ga l g o r i t h mn a m e dg m ra l g o r i t h m , w h i c hs u p p o r t sa r b i t r a r yc o n t i n u o u s s t r i c t l ym o n o t o n ea g g r e g a t i o nf u n c t i o n t h et h e o r e t i c a la n a l y s i ss h o wt h a tt h en e t w o r k t r a f f i co ft h eg m r a l g o r i t h mi si n d e p e n d e n to f 丘me x p e r i m e n t sr e s u l t ss h o wt h a t g m rr e d u c e so v e r a l lc o s tb ya no r d e ro f m a g n i t u d ec o m p a r e dw i t ht h en a i v ea p p r o a c h ， 3 d i s t r i b u t e ds k y l i n es n a p s h o tq u e r yp r o c e s s i n g i ti sa n i m p o r t a n ti s s u eo f d i s t r i b u t e ds k y l i n es n a p s h o tq u e r yp r o c e s s i n gt h a th o wt or e d u c et h en e t w o r kt r a f f i ci n t h eq u e r yp r o c e s sw h e nt h en u m b e ro f n o d e si sl a r g e t oa d d r e s st h i si s s u e ，w ep r e s e n ta m e t h o d ，w h i c hr e d u c e st h en e t w o r kt r a f f cb ya c c e s s i n gd a t as o u r c e sv i ap h a s e s ，a n d p r o p o s eaf o u r - p h a s ed i s t r i b u t e ds k y l i n es n a p s h o tq u e r yp r o c e s s i n ga l g o r i t h mn a m e d 第i v 页 国防科学技术大学研究生院博士学位论文 f d s la l g o r i t h m t h ee x p e r i m e n t sr e s u l t ss h o wt h a tf d s li ss u p e r i o rt ot h ee x i s t i n g a l t e r n a t i v e si nt h et e r m so ft h en e t w o r kt r a f f i cw h e nt h en u m b e ro fn o d e si sg r e a t e rt h a n 4 4 b a s e do nt h es t u d i e so ft h ek e yt e c h n o l o g i e ss t a t e da b o v e w eg oo nw i 血t h e i m p l e m e n t a t i o ni s s u e so fd i s t r i b u t e dr a n k - a w a r eq u e r yp r o c e s s i n ge n g i n e i nt h e m a s s i v ed a t ap r o c e s s i n gm i d d l e w a r ep l a t f o r ms t a r t p m o n i t o r , w ed e s i g na n di m p l e m e n t t h ed i s t r i b u t e d a n a l y s i sq u e r yp r o c e s s i n ge n g i n es t a r a n a l y s i s w h i c hs u p p o r t s d i s t r i b u t e dr a n k - a w a r eq u e r yp r o c e s s i n g t h et e s t i n gr e s u l t ss h o wt h a ts t a r a n a l y s i sc a n s u p p o r td i s t r i b u t e da n a l y s i sq u e r yo nm a s s i v ed a t ae f f e c t i v e l y t os u mu p ，w ep r e s e n tt h ew e l l - e v a l u a t e ds o l u t i o n si nt h i sd i s s e r t a t i o nf o rs o m e k e yi s s u e si nd i s t r i b u t e dl a n k - a w a r eq u e r yp r o c e s s i n g w eb e l i e v et h a to u rc o n t r i b u t i o n s c a l lm a k ean i c eg r o u n d w o r kf o rt h ef u t u r er e s e a r c ha n de n g i n e e r i n go nd i s t r i b u t e d r a n k - a w a l q u e r yp r o c e s s i n gb o t hi nt h e o r ya n dp r a c t i c e k e yw o r d s ：d i s t r i b u t e dc o m p u t i n g ，d a t a b a s e ，r a n k - a w a r e t o p kq u e r y s k y l i n eq u e r y ，d a t as t r e a mm a n a g e m e n t s n a p s h o tq u e r yp r o c e s s i n g m o n i t o r i n gq u e r yp r o c e s s i n g ，a n a l y t i c a lq u e r y ，q u e r yp r o c e s s i n ge n g i n e 第v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 非阻塞t o p - k 查询处理中的常用符号表1 9 表2 1 ( 续) 非阻塞t o p - k 查询处理中的常用符号表2 0 表4 1 不同节点数下轮廓集的大小7 5 表5 1 评测数据集8 9 第1 v 页 国防科学技术大学研究生院博士学位论文 图 目录 图1 1 宾馆的轮廓集。 图1 2 本文组织结构示意图 图2 1 分布式t o p k 查询示意图1 8 图2 2t a 算法 图2 3t p u t 算法 图2 4p r 算法。 图2 5a p r 算法 图2 6 不同形状因子下的p a r e t o 分布。3 4 图2 7 步长因子对p r 算法性能的影响3 6 图2 8w o d d c u p 数据集上的性能比较3 7 图2 9 关联数据集上的性能比较。3 7 图2 1 0 不同关联因子下的性能比较3 9 图2 1 l 不同网络状况下的性能比较4 0 图2 1 2 不同k 值下的性能比较4 2 图2 1 3 不同节点规模下的性能比较4 3 图3 1 分布式t o p k 监测示意图4 6 图3 2b a b c o c k & o l s t o n 算法4 7 图3 3b a b c o c k & o l s t o n 算法中的r e s o l u t i o n 过程4 8 图3 4b a b c o c k & o l s t o n 算法中的r e a l l o e a t i o n 函数4 9 图3 5m r 算法5 2 图3 6m r - r e a l l o c a t i o n 函数5 3 图3 7 平均分配与按流量分配策略的比较5 8 图3 8 在w o r m c u p 数据集上执行监测请求l 的比较5 8 图3 9 在w o d d c u p 数据集上执行监测请求2 的比较5 9 图3 1 0 在z i p f 数据集上执行监测请求l 的比较5 9 图3 1 l 在z i p f 数据集上执行监测请求2 的比较5 9 图3 1 2 不同k 值下网络流量6 0 图3 1 3 不同k 值下网络流量的比较6 0 图3 1 4 不同k 值下的消息数量6 0 图3 1 5g m r 算法6 4 图3 1 6g m r 与n d t m 在w o d d c u p 数据集上的性能比较6 6 图3 1 7g m r 与n d t m 在z i p f 数据集上的性能比较6 7 第v 页 国防科学技术大学研究生院博士学位论文 图3 1 8 聚集函数为f 1 ( x ) 时不同k 值下的性能比较6 7 图3 1 9 聚集函数为f 2 ( x ) 时不同k 值下的性能比较6 7 图3 2 0 聚集函数为f 3 ( x ) 时不同k 值下的性能比较6 8 图4 1分布式轮廓查询示意图6 9 图4 2f d s l 算法7 3 图4 3独立分布数据集上h 的取值策略的比较。7 5 图4 4 正相关数据集上h 的取值策略的比较。7 6 图4 5 反相关数据集上两种h 的取值策略的比较。7 6 图4 6 独立分布数据集上f d s l 算法与同类算法的比较7 7 图4 7正相关数据集上f d s l 算法与同类算法的比较。7 7 图4 8反相关数据集上f d s l 算法与同类算法的比较7 7 图5 1s t 们p m o n i t o r 体系结构8 0 图5 2 并行加载服务。8 l 图5 3 并行查询服务。8 2 图5 4 s t a r a n a l y s i s 总体结构示意图8 3 图5 5s t a r a n a l y s i s 中的分析查询示意图8 3 图5 6s t a r a n a l y s i s 中的实时监测示意图8 5 图5 7 各监测节点对单个数据流的监测查询处理8 5 图5 8 优化的查询计划8 7 图5 9 测试环境硬件结构图8 8 图5 1 0 优化前的q u e r y l 的响应时间9 0 图5 1l优化前后的查询计划性能的比较9 1 第v i 页 独创性声明 本人声明所里交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：金查盍压亟盛查塑缝壅差链挂苤熟盔： 学位论文储摊：2 弘一魄聊阳。月置日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：金盔盛庄邀盛查逦缝堡差丝技查蟹盔 学位论文作者签名 作者指导教师签名 日期：朋年口月8 日 日翔：哩叼6 年f o 冠8b 国防科学技术大学研究生院博士学位论文 1 1 1 应用需求 第一章绪论 1 1 研究背景 随着计算机技术的迅猛发展和计算机应用领域的不断扩大，信息资源日益丰 富，涌现了大量的t b 甚至p b 级的数据密集型应用【l ，2 1 。据w i n t e r 公司统计资料， 近年来全球最大的数据库的容量呈指数增长趋势，2 0 0 5 年最大的数据仓库容量已 经达到1 0 0 t b ，而且最大的在线处理数据库容量已经超过了2 0 t b t 3 1 。 面对丰富的信息资源，人们在信息获取时往往希望业务系统能从海量数据中 迅速找出少量的最有价值的信息，而不是让用户从头至尾的逐一挑选。这种用户 需求推动了业务系统在信息的处理方式上的转变。许多数据密集型应用已不再追 求查询结果的完整性，而只关注如何从海量数据中快速提取用户最为关心的少量 信息 4 1 。 然而，在数据库领域，传统的查询处理技术( 包括选择、投影、连接和聚集 等) 不能很好的满足上述用户需求。例如： 例1 1在使用商品推荐系统选购商品时，人们希望商品推荐系统能根据需求 提供一份列有l o 种最有可能满足要求的商品推荐清单，而不是将所有 同类商品全部列出。 例1 2在股票交易中，人们常常需要连续、实时的了解股票行情( 如最近两 个小时涨幅最快的前1 0 支股票等) 来进行投资决策。 与例1 1 和例1 2 类似的用户需求在人们的生活中随处可见。但是，对于例1 1 ， 传统的查询处理技术需要计算所有同类商品的推荐度，然后返回推荐度最高的前 1 0 种商品。这种处理方法的在商品种类增多时，将给推荐系统带来巨大的负载。 对于例1 2 ，由于传统的查询处理技术只能针对入库数据进行快照( s n a p s h o t ) 式 查询，无法支持连续的实时的查询处理。应用需求和现有技术之间的矛盾促使研 究人员寻求新的更为有效的查询处理技术。 1 1 2 序敏感查询的提出 由于传统的查询处理技术不能很好的满足从海量数据中快速查找用户最为关 心的少量信息这一广泛存在的、迫切的应用需求。为此，数据库领域研究人员于 上世纪末和本世纪初分别提出了两种新的查询处理技术：t o p k 查询t 6 - s j , o 轮廓 ( s k y l i n e ) 查询【3 9 1 。 第1 页 国防科学技术大学研究生院博士学位论文 t o p - k 查询 t o p k 查询是根据用户指定的单调聚集函数从数据集中找出函数值最高的前k 个结果睁”。例如查询综合实力最高的前1 0 0 位高校。在许多数据密集型应用中， 快速查找用户最为关心的少量结果是普遍存在的用户需求。在信息检索领域这个 问题得到了很好的研究与应用p 】。例如，我们在使用搜索引擎时一般都能在第一个 返回的页面中找到想要的链接。但是，从例1 1 的分析中可以看到，在数据库领域 传统的查询处理技术不能很好的满足这类需求。针对这个问题，上世纪9 0 年代末， f a g i n 等人借鉴信息检索相关技术的思想，提出了t o p - k 查询的概念 6 - 8 1 。 t o p - k 查询的核心思想是认为数据集中只有少量的数据是用户