（计算机应用技术专业论文）基于智能技术的topn关系查询处理和优化.pdf

摘要 摘要 数据库系统正在经历巨大的变化，智能技术已经引入到数据库系统的研究 中。2 0 0 4 年在s i g m o d 国际会议上，j i m 研a y 说：“我们正沿着一条有价值的 链条从数据到信息到知识到智慧在慢慢地攀爬”。数据库研究的核心问题之一为 查询处理和优化。近年来t o p - n 查询倍受关注，成为国际上非常活跃的研究课题。 t o p n 查询比传统查询的应用更广泛、更灵活、功能更强大，能够解决传统数据 库管理系统( d b m s ) 无法处理的查询问题；其主要应用包括：数据挖掘、搜索引 擎、决策支持系统、多媒体数据库、信息检索、w e b 智能和w e b 数据库等。 在查询的研究中，关键是对查询准确和快速地处理，因此需要研究查询处 理的理论、方法、技术及优化策略。本文主要对t o p - n 查询进行研究。t o p n 查 询就是，对于用户指定的正整数，如n = 1 0 ，2 0 或1 0 0 ，检索出个元组使 其最好地匹配查询条件，但不一定完全匹配查询条件；输出的结果集合按所用 的距离函数排序。具体内容如下： 1 基于学习的t o p - n 查询处理：本文运用基于学习的策略，给出t o p - n 查询处 理的一种新方法。其主旨为，在初始阶段，对于少数随机的t o p - n 查询，找 出其最佳搜索区域并将相关信息存储在一个知识库中；然后用知识库中的知 识处理新提交的t o p - n 查询；随着被处理的t o p - n 查询的增加，原始知识库 将被不断更新，因而能够更好地处理频繁提交的查询。另外，给出知识库的 维护方法并且用时间序列的理论和方法讨论知识库的稳定性。最后，用大量 的实验来验证基于学习策略的性能，且与其它方法进行比较。实验结果表明 基于学习的方法不仅可以很好地处理低维数据，而且能够很好地处理高维数 据，不惧怕“维数灾难”；与现有其它方法比较，其效率更有优势。 2 基于区域聚类的多t o p - n 查询优化：在很多数据库应用中，存在同时处理多 个提交的t o p n 查询的情形。通常，同时处理多个查询的开销比单个地逐一 处理更有效。对于关系数据库，本文提出了同时处理多个t o p - n 查询的一种 新方法，其基本思想是区域聚类。区域聚类把各个t o p - n 查询的搜索区域聚 集成一些较大的区域并且从这些较大的区域检索元组。这种方法避免了多次 访问同一区域并且减少了对底层数据库随机i o 访问次数。通过大量实验测 北京工业大学t 学博上学位论文 试这种新策略的性能；实验结果表明对于低维( 2 ，3 和4 维) 和高维( 2 5 ，5 0 和 1 0 4 维) 数据，这种方法明显优于逐一处理的朴素方法。另外，虽然区域聚类 方法是为多t o p - n 查询优化提出的，但可以直接运用于多区域查询优化；对 此，本文也进行了研究，其性能也显著优于朴素方法。 3 t o p - n 查询流处理：在数据库系统及其应用中，另一个重要问题是处理在不 同时间提交的t o p - n 查询所形成的查询流。为此，改进了上述基于学习的策 略并且结合区域聚类方法，同时运用缓存机制，对t o p - n 查询流进行综合优 化处理。这种方法使用知识库来存储一些过去查询的相关信息，聚类以往查 询的搜索区域为较大的区域，进而从这些较大区域检索元组。为了回答一个 新提交的查询，尽量从内存中已经检索的结果获取元组。这样，通过尽量减 小搜索区域和避免访问底层数据库来寻求缩短响应时间。同时，这种方法保 持查询高维数据的高效性。另外，给出知识库的维护策略。大量的实验用来 验证此策略的性能，实验结果表明，无论是对低维数据还是高维数据，此方 法的性能比朴素方法的性能明显提高。本文也探究了用类似方法处理区域查 询流，实验表明其性能显著优于朴素方法。 4 基于语义距离的t o p n 查询处理：传统数据库搜索在查询和元组的比较过程 中使用模式匹配。对于一个查询，只有当元组和查询完全匹配时，元组才被 检索。本文研究具有语义的文本属性的t o p - n 查询处理，通过定义新的语义 距离函数，实现数据库搜索过程中词与词之间的语义匹配。目的是不仅返回 与查询完全匹配的元组，而且与查询的语义距离靠近的元组也能被取出。实 现方法的主旨是：基于w o r d n e t 创建索引将元组的词进行语义扩展；通过此 索引来匹配查询词和元组的扩展词，运用一个简单的s q l 选择语句于关系 的自然连接检索出候选元组；然后，用语义距离对候选元组排序，最后输出 t o p n 结果。大量的实验用于测量这种新策略的性能。 基于以上内容的研究结果，本文的主要贡献在于： 1 对于t o p - n 查询处理，提出了基于学习的新方法，通过估计查询的局部分 布密度，确定t o p n 查询的搜索区域；用时间序列的理论和方法，定义和 分析知识库的稳定性。 2 提出了多t o p n 查询优化新问题，并且为了解决此问题，提出了区域聚类 的新方法。区域聚类的对象为“刀一维超矩形”，而通常聚类的对象是“点”。上 l i 摘要 述基于学习的和区域聚类的两种方法，不仅可以很好地处理低维数据，而 且能够很好地处理高维数据，不怕维数灾难。 3 提出了t o p - n 查询流处理新问题，为此，综合运用基于学习的方法、区域 聚类的方法和缓存机制。就本文作者所知，到目前上述多t o p - n 查询优化 和t o p - n 查询流处理这两个问题在国内外文献中未见其它相同报道。 4 定义由一些词汇组成的查询和元组之间新的语义距离函数，基于w o r d n e t 创建索引，实现关系数据库中查询的语义搜索，检索t o p n 结果。本文给 出的方法，其时间效率优于通常基于本体的方法。 关键词：t o p - n 查询；基于学习的策略；区域聚类；语义距离；语义搜索 a b s t r a c t d a t a b a s es y s t e m sa r e u n d e r g o i n gr e v o l u t i o n a r yc h a n g e s ，a n di n t e l l i g e n c ei s m o v i n gt ot h er e s e a r c ho fd a t a b a s es y s t e m s i n2 0 0 4 ，a sm e n t i o n e db yj i mg r a ya t s i g m o dc o n f e r e n c e ，“w e a r es l o w l yc l i m b i n gt h ev a l u ec h a i nf r o md a t at o i n f o r m a t i o nt o k n o w l e d g et ow i s d o m ”q u e r ye v a l u a t i o ni so n eo ft h ek e yi s s u e si n d a t a b a s er e s e a r c h t h e r e f o r e ，n e w t y p e q u e r i e sh a v er e c e i v e dm u c ha t t e n t i o ni n r e c e n ty e a r s ，f o ri n s t a n c e ，t o p nq u e r i e sh a v eb e e na c t i v er e s e a r c hi s s u e s t h e yh a v e m o r ea p p l i c a b l e ，f l e x i b l e ，a n de f f e c t i v et h a nt r a d i t i o n a lq u e r i e s t o p - n q u e r i e sc a n d e a lw i t hp r o b l e m st h a tt r a d i t i o n a ld b m sc a n n o td o ，a n dc a nb eu s e di nm a n yf i e l d s s u c ha sd a t am i n i n g ，s e a r c he n g i n e ，d e c i s i o n s u p p o r ts y s t e m s ，m u l t i m e d i ad a t a b a s e ， 1 n f o r m a t i o nr e t r i e v a l ，w e bi n t e l l i g e n c e ，w e bd a t a b a s ea n ds oo n f i n d i n gt h es t r a t e g i e so fe f f e c t i v e n e s sa n de f f i c i e n c yt oe v a l u a t eq u e r i e si st h e p r i m a r yf o c u so fq u e r yr e s e a r c h ，i n c l u d i n g t h e o r i e s ，m e t h o d s ，t e c h n i q u e s ，a n d o p t i m i z a t i o no fq u e r ye v a l u a t i o n i nt h i sp h dd i s s e r t a t i o n ，t h er e s e a r c hw i l li n v o l v e t o p - ns e l e c t i o nq u e r i e s at o p - ns e l e c t i o nq u e r yi st of i n dt h en t u p l e st h a ts a t i s f yt h e q u e r yc o n d i t i o nt h eb e s tb u tn o tn e c e s s a r i l yc o m p l e t e l yf o rag i v e ni n t e g e rn ( s a y , = l0 ，2 0 ，o r10 0 ) ，a n do u t p u t st h es o r t e dr e s u l t sa c c o r d i n gt oag i v e nd i s t a n c ef u n c t i o n t h em a i nw o r ki n c l u d e s ： 1 l e a r n i n g b a s e dt o p - nq u e r ye v a l u a t i o n w ep r o p o s ean e wm e t h o df o re v a l u a t i n gt o p nq u e r i e so v e rr e l a t i o n a ld a t a b a s e s t h i sm e t h o de m p l o y sal e a r n i n g - b a s e ds t r a t e g y i n i t i a l l y , t h i sm e t h o df i n d sa n d s a v e s t h eo p t i m a ls e a r c hr a n g e sf o ras m a l ln u m b e ro fr a n d o mt o p - nq u e r i e s t h el e a r n e d k n o w l e d g ei st h e nu s e dt oe v a l u a t en e w l ys u b m i t t e dq u e r i e s f u r t h e r m o r e ，t h e k n o w l e d g eb a s ec a nb eu p d a t e db a s e do nn e wu s e rq u e r i e st or e f l e c tn e wq u e r y p a t t e r n ss ot h a tf r e q u e n t l ys u b m i t t e dq u e r i e sc a nb ep r o c e s s e dm o s te f f i c i e n t l y f o r t h ek n o w l e d g eb a s e ，i t sm a i n t e n a n c ei sa d d r e s s e d ，a n di t ss t a b i l i t yi sd i s c u s s e db v u s i n gt h et h e o r i e sa n dt e c h n i q u e so ft i m es e r i e s e x t e n s i v ee x p e r i m e n t sa r ec a r r i e d o u tt om e a s u r et h ep e r f o r m a n c eo ft h i s s t r a t e g ya n dt h er e s u l t si n d i c a t et h a ti ti s h i g h l yc o m p e t i t i v ew i t he x i s t i n gt e c h n i q u e sf o rb o t hl o w - d i m e n s i o n a la n d h i g h d i m e n s i o n a ld a t a ，a n di td o e sn o ts u f f e rt h em u c hf e a r e d “d i m e n s i o n a l i t yc u r s e ， a si tr e m a i n se f f e c t i v ef o rh i g h d i m e n s i o n a ld a t a 2 r e g i o nc l u s t e r i n gb a s e de v a l u a t i o no fm u l t i p l et o p - nq u e r i e s i nm a n yd a t a b a s ea p p l i c a t i o n s ，t h e r ea r eo p p o r t u n i t i e sf o rm u l t i p l et o p - n q u e r i e s t ob ee v a l u a t e da tt h es a m et i m e o f t e ni ti sm o r ec o s te f f e c t i v et oe v a l u a t em u l t i p l e s u c hq u e r i e sc o l l e c t i v e l yt h a ni n d i v i d u a l l y w e p r o p o s ean e wm e t h o d ，r e g i o n c l u s t e r i n gm e t h o d ( r c m ) ，f o re v a l u a t i n gm u l t i p l et o p nq u e r i e sc o n c u r r e n t l yo v e ra a b s t r a c t r e l a t i o n a ld a t a b a s e t h eb a s i ci d e ao ft h i sm e t h o di sr e g i o nc l u s t e r i n gt h a tg r o u p st h e s e a r c hr e g i o n so fi n d i v i d u a lt o p - nq u e r i e si n t ol a r g e rr e g i o n sa n dr e t r i e v e st h et u p l e s f r o mt h el a r g e rr e g i o n s t h i sm e t h o da v o i d sh a v i n gt h es a l t l er e g i o na c c e s s e dm u l t i p l e t i m e sa n dr e d u c e st h en u m b e ro fr a n d o mi oa c c e s s e st ot h eu n d e r l y i n gd a t a b a s e s e x t e n s i v ee x p e r i m e n t sa r ec a r r i e do u t t om e a s u r et h ep e r f o r m a n c eo ft h i sn e w s t r a t e g ya n dt h er e s u l t si n d i c a t et h a ti ti ss i g n i f i c a n t l yb e t t e rt h a nt h en a f v em e t h o do f e v a l u a t i n gt h e s eq u e r i e so n eb yo n ef o rb o t hl o w d i m e n s i o n a l ( 2 ，3 ，a n d4 ) a n d h i g h d i m e n s i o n a l ( 2 5 ，5 0 ，a n d10 4 ) d a t a n o t et h a te v e nt h o u g hr c m i sp r e s e n t e di n t h ec o n t e x to fe v a l u a t i n gm u l t i p l et o p nq u e r i e s ，i ti sd i r e c t l ya p p l i c a b l et oe v a l u a t i n g m u l t i p l er a n g eq u e r i e si nm u l t i d i m e n s i o n a ls p a c e s w ea l s ou s er c mm e t h o dt o e v a l u a t em u l t i p l et r a d i t i o n a lr a n g eq u e r i e sc o n c u r r e n t l y , a n dt h ee x p e r i m e n t a lr e s u l t s i n d i c a t et h a ti ti sa l s os i g n i f i c a n t l yb e t t e rt h a nt h en a f v em e t h o d 3 e v a l u a t i n gas t r e a mo ft o p - ns e l e c t i o nq u e r i e s i nr e l a t i o n a ld a t a b a s e sa n dt h e i ra p p l i c a t i o n s ，a ni m p o r t a n ti s s u ei st oe v a l u a t ea s t r e a mo ft o p ns e l e c t i o nq u e r i e ss u b m i t t e do n eb yo n ea td i f f e r e n tt i m e s f o rt h i s i s s u e ，i n s p i r e db yt h ec a c h i n gm e c h a n i s m s ，w ei m p r o v el e a r n i n g - b a s e ds t r a t e g i e sa n d r e g i o nc l u s t e r i n gt e c h n i q u e s ，a n dt h e np r o p o s ean e w m e t h o dc a l l e dl r c ( l e a r n i n g & r e g i o nc l u s t e r i n g & c a c h i n gm e c h a m s m ) m e t h o d t h i sm e t h o du s e sak n o w l e d g e b a s et os t o r er e l a t e di n f o r m a t i o no fs o m ep a s tq u e r i e s ，g r o u p st h es e a r c hr e g i o n so f t h ep a s tq u e r i e si n t ol a r g e rr e g i o n sa n dr e t r i e v e st h et u p l e sf r o mt h el a r g e rr e g i o n s t o a n s w e ran e w l ys u b m i t t e dq u e r y , o u rm e t h o dt r i e st oo b t a i nm o s tr e s u l t sf r o mt h e p r e v i o u s l yr e t r i e v e dt u p l e st h a ta r es t i l li nm a i nm e m o r y t h u s ，t h i sm e t h o ds e e k st o m i n i m i z et h er e s p o n s et i m eb yr e d u c i n gt h es e a r c hr e g i o no ra v o i d i n ga c c e s s e st ot h e u n d e r l y i n gd a t a b a s e m e a n w h i l e ，t h i sm e t h o dr e m a i n se f f e c t i v ef o rh i g h d i m e n s i o n a l d a t a e x t e n s i v ee x p e r i m e n t sa r ec a r r i e do u tt om e a s u r et h ep e r f o r m a n c eo ft h i sn e w s t r a t e g ya n dt h er e s u l t si n d i c a t et h a ti ti ss i g n i f i c a n t l yb e t t e rt h a nt h en a i v em e t h o do f e v a l u a t i n gas t r e a mo ft o p - nq u e r i e sf o rb o t hl o w - d i m e n s i o n a la n dh i g h - d i m e n s i o n a l d a t a a d d i t i o n a l l y , w ed i s c u s st h ee v a l u a t i o no fas t r e a mo fr a n g eq u e r i e su s i n ga s i m i l a rm e t h o da sl r c ，a n dt h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h em e t h o di s s i g n i f i c a n t l yb e t t e rt h a nt h en a f v em e t h o d 4 s e m a n t i cd i s t a n c eb a s e dt o p - nq u e r ye v a l u a t i o n t r a d i t i o n a ld a t a b a s es e a r c hu s e sp a t t e mm a t c hi nt h ec o m p a r i s o np r o c e s s f o ra q u e r y , t u p l e sa r es e l e c t e do n l yi ft h e ye x a c t l ym a t c hi t b yd e f i n i n gs e m a n t i cd i s t a n c e f u n c t i o n s ，w ep r o p o s ean e wm e t h o dt ou t i l i z es e m a n t i cm a t c hb e t w e e nw o r d si n d a t a b a s es e a r c h t h ea t t e m p ti st h a tt u p l e s ，n o te x a c t l ym a t c h i n g ，b u tc l o s et ot h e q u e r ya c c o r d i n gt os e m a n t i cd i s t a n c e ，c a na l s ob ef e t c h e d t h eb a s i ci d e ao ft h e m e t h o di st oc r e a t ea ni n d e xb a s e do nw o r d n e tt oe x p a n dt h et u p l ew o r d s s e m a n t i c a l l y m a t c h i n gt h eq u e r yw o r d sa n dt h ee x p a n d e dw o r d sb yt h ei n d e x ， v 北京t 业大学t 学博：卜学位论文 c a n d i d a t et u p l e sa r er e t r i e v e db yas i m p l es q ls e l e c t i o ns t a t e m e n tf o rt h en a t u r a lj o i n o fr e l a t i o n s ，t h e ya r es o r t e da c c o r d i n gt ot h es e m a n t i cd i s t a n c ef u n c t i o n ，a n dt h e n t o p - nr e s u l t sa r eo u t p u t f e d e x t e n s i v ee x p e r i m e n t sa r ec a r r i e do u tt om e a s u r et h e p e r f o r m a n c eo ft h i sn e ws t r a t e g y b a s e do nt h er e s u l t so ft h ea b o v ew o r k ，t h em a i nc o n t r i b u t i o n so ft h i s d i s s e r t a t i o ni n c l u d e ： 1 w ep r o p o s ean e wm e t h o df o re v a l u a t i n gt o p - nq u e r i e s t h i sm e t h o de m p l o y s al e a r n i n g - b a s e ds t r a t e g y f o rat o p - nq u e r y , b ye s t i m a t i n gt h el o c a ld i s t r i b u t i o n d e n s i t yo ft h eq u e r y , i t ss e a r c hr e g i o nw i l lb ed e t e r m i n e d a d d i t i o n a l l y , t h es t a b i l i t yo f t h ek n o w l e d g eb a s ei sd e f i n e da n da n a l y z e db yu s i n gt h et h e o r i e sa n dt e c h n i q u e so f t i m es e r i e s 2 f o ro p t i m i z a t i o no fm u l t i p l et o p wq u e r i e s ，w ep r e s e n tan e wm e t h o dc a l l e d r e g i o nc l u s t e r i n gm e t h o d ( r c m ) i nm o s tc a s e s ，t h eo b j e c t st ob ec l u s t e r e da r ep o i n t s f o rc u r r e n tc l u s t e r i n gt e c h n i q u e s h o w e v e lt h eo b j e c t so fr c ma r en - d i m e n s i o n a l r e c t a n g l e s t h ea b o v et w om e t h o d s ，l e a r n i n g b a s e dm e t h o da n dr c m ，d on o ts u f f e r t h em u c hf e a r e d “d i m e n s i o n a l i t yc u r s e ”a st h e yr e m a i ne f f e c t i v ef o rh i g h d i m e n s i o n a l d a t a 3 l e a r n i n g b a s e dm e t h o d ，r e g i o nc l u s t e r i n gm e t h o d ，a n dc a c h i n gm e c h a n i s m a r em e r g e dt oe v a l u a t eas t r e a mo ft o p - ns e l e c t i o nq u e r i e s t ot h eb e s to fo u r k n o w l e d g e ，t h ea b o v et w op r o b l e m so fe v a l u a t i n gt h ek i n do fm u l t i p l et o p - nq u e r i e s a n das t r e a mo ft o p - nq u e r i e st h a tw ec o n s i d e ri n t h i sd i s s e r t a t i o nh a v en o tb e e n i n v e s t i g a t e db e f o r e 4 。d e f i n i n gs e m a n t i cd i s t a n c ef u n c t i o n sb e t w e e naq u e r ya n dat u p l eb o t h c o n s i s t e do fm u l t i p l ew o r d s ，a n dc r e a t i n ga ni n d e xb a s e do nw o r d n e t ，w ep r o p o s ea n e wm e t h o dt oi m p l e m e n ts e m a n t i cs e a r c hi nr e l a t i o n a ld a t a b a s e sa n dt or e t r i e v e t o p - nr e s u l t s t h ee f f i c i e n c yo fo u rm e t h o di sh i g h l yc o m p e t i t i v ew i t he x i s t i n g o n t o l o g yb a s e dt e c h n i q u e s k e yw o r d s ：t o p - nq u e r y ；l e a r n i n g b a s e ds t r a t e g y ；r e g i o nc l u s t e r i n g ；s e m a n t i c d i s t a n c e ；s e m a n t i cs e a r c h v i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：日期：三竺星：! 兰：! 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 导师签名： 第1 章绪论 1 1 课题背景 第1 章绪论 数据库系统正在经历巨大的变化，智能技术已经引入到数据库系统的研究 中【1 ，2 1 ，如j i mg r a y 在2 0 0 4 年s i g m o d 国际会议所说：“我们正沿着一条有价 值的链条从数据到信息到知识到智慧在慢慢地攀爬”1 2 1 。数据库研究的核心问题 之一为查询处理和优化。近年来t o p n 查询的研究倍受关注，成为国际上非常活 跃的课题。t o p - n 查询比传统查询的应用更广泛、更灵活、功能更强大，能够解 决传统数据库管理系统( d b m s ) 无法处理的查询问题。其主要应用包括数据挖 掘、搜索引擎、决策支持系统、多媒体数据库、信息检索、w e b 智能和w e b 数 据库等。 搜索引擎( s e a r c he n g i n e ) 是t o p - n 查询的应用之一。w e b 已经成为一个庞大 的信息源。到1 9 9 9 年2 月，已经有大约8 亿个可公开检索的网页【3 】。查询数据 是w e b 最普遍的应用之一，因此创建了很多搜索引擎用于网页的检索。 随着电子商务的发展，w e b 已经变成购物的乐园。同传统商务和超市购物 相比，电子商务和网上购物省钱、省力、省时而且方便。例如在美国网上购物 已经非常普及，象w a l m a r t 和b a r n e s a n d n o b l e 这样大的零售商都已经建立了 网站销售商品。在我国电子商务和网上购物也有了长足的发展，并且潜力巨大。 一个电子商务w e b 网站，包含大量商品信息，如商品名称和价格等，允许用户 进行浏览，搜索欲购的商品。因此，在网站上必须安装搜索引擎才能使这种搜 索得以进行。 支持电子商务的搜索引擎在很多方面不同于w e b 网页的查找( 如g o o g l e 提 供的功n u ) 。首先，电子商务搜索引擎要提供更复杂的用户界面，用来支持可能 被搜索商品的各种属性，如二手汽车的制造商，型号，出厂日期，所跑里程， 价格等。通常这些界面具有多个输入区，选择菜单和选择项等，但是w e b 网页 搜索引擎一般只有一个输入区提供文本输入。其次，电子商务搜索引擎通常是 基于数据库驱动的，商品或服务的信息一般存储在数据库中，搜索由数据库系 北京t 业大学工学博十学位论文 统执行。从数据库中搜索数据，可使w e b 网页变得更具吸引力。然而，绝大多 数w e b 。网页搜索引擎把要搜索的网页索引预存于一个文本，其覆盖的网页是有 限的【3 ，刖。尽管有些w 曲网页搜索引擎也具有复杂的界面以提供高级查询，但大 多数用户不使用这些界面。 在w e b 上很多网站经常提供相同或相似的商品，例如很多网站卖书，也有 很多网站卖汽车。虽然这些相同或相似商品的属性没有什么不同，但是其价格 往往差距很大。为了能让用户用最低的价格买到最好的商品，需要创建一个统 一的用户界面，用户只需提交一个查询，对于这同一个查询，统一的用户界面 可使多个搜索引擎进行搜索。我们称此统一的用户界面为电子商务元搜索引擎 ( e c o m m e r c em e t a s e a r c he n g i n e ) 。元搜索引擎把用户的一个查询传给多个网站( 也 许经过必要的格式化) 并且将多个网站返回的结果整合为一个结果列表，按一定 的要求( 如按价格) 排序，使最好的个结果排在前面。因此，能够支持t o p - n 查 询的搜索引擎在实际应用中非常重要。 如今在w e b 应用中，有海量的信息是通过查询接口在线访问其后端的w e b 数据库。根据美匡i u i u c 大学的研究【5 】，到2 0 0 4 年4 月，估计整个w e b 上有3 0 7 0 0 0 个网站提供4 5 0 0 0 0 个w - e b 数据库，是b r i g h t p l a n e t 6 】在2 0 0 0 年7 月估计的5 0 0 0 0 个网 站的6 倍多。另外，在4 5 0 0 0 0 个w 曲数据库中，结构数据库有3 4 8 0 0 0 个【5 】。随着 结构数据库，主要是关系数据库在w e b 应用中急剧增加，对关系数据库查询处理 的研究在国际上成为活跃的课题。与传统查询不同，鉴于i r ( i n f o r m a t i o nr e t r i e v a l ) ， 为了更好地适用于w e b 数据库，一些新型查询( 女n t o p 一查询) 的研究是必要的，其 中关键是查询准确和快速地处理；因此需要研究查询处理的理论、方法、技术 及优化策略。本文主要对t o p 查询进行研究，示例如下。 例1 1 考虑一个二手车数据库，其模式( s c h e m a ) 为 u s e d c a r s ( i d # ，m a k e ，m o d e l ，y e a r , p r i c e ，m i l e a g e ) 假设一个客户想买一辆二手车，价格约为$ 5 0 0 0 ，所跑里程约为6 0 0 0 哩。一个 可选的方法是指定如下s q l 查询： s e l e c t f r o mu s e d c a r sw h e r ep r i c e = 5 0 0 0a n dm i l e a g e = 6 0 0 0 但是存在一个问题：在数据库u s e d c a r s 中可能不存在完全满足上述条件的汽车， 只能返回空值。因而妨碍用户找到那些近似满足查询条件的汽车。另一个可选 的方法是指定如下s q l 区域查询： 2 第1 章绪论 s e l e c t 牛f r o mu s e d c a r sw h e r e ( p r i c eb e t w e e n4 0 0 0a n d6 0 0 0 ) a n d ( m i l e a g eb e t w e e n10 0 0a n d10 0 0 0 ) 但是又会存在下列问题：( 1 ) 可能存在非常多的汽车满足查询条件，并且绝大多 数都不是用户想要的；给用户带来太多无用消息，影响用户选择。( 2 ) 对于一个 客户而言，为每个属性确定恰当的查询区域是困难的，也可以说是不可能的， 因为“猜中”的可能性极小。查询区域太小，可能导致返回太少的结果。区域 太大，返回的结果可能太多。 t o p - n 查询将解决上述传统查询存在的问题：给定一个查询，对于用户指定 的正整数，如= 1 0 ，2 0 或1 0 0 ，检索出个元组使其最好地匹配查询条件， 但不一定完全匹配查询条件；输出结果按某种距离排序。 目前关于t o p n 查询的研究还只限于数值属性的数据，描述如下 设贸为实数域，( 吼h ，碳，) ) 是胛维实距离空间，其中以，) 为距离函数。 假设 d c 吼疗是一个数据集或关系( r e l a t i o n ) ，每个元组有刀个属性似1 ，a 2 ，a 门) 一个 元组，d 记为，= ( t l ，龟，如) 对于任意o = ( q l ，q n ) 吖和整数 0 ，一个 t o p n 选择查询( q ，加，简称t o p - n 查询，就是从d 中选择与q 的距离最近的 个元组构成的有序集，并且按距离从小到大排序。t o p n 查询的结果称为t o p - n 元组。有时t o p - n 查询( q ，加简记为q 假设 k ，其中k 是一个由膈口 数值属性决定的阈值参数(