（计算机软件与理论专业论文）基于语义缓存的查询处理技术的研究与应用.pdf

嘏皿拯 美于语冀援群曲镬谗蹬理技术静骈究与应用 基于语义缓存的凌询处理技术的研究与应用 诗冀瓠较俘与瑾论 硕士生：胡风根 指导教师：李磊教授 摘要 移动计算环境下，由于有邋情带宽窄、网络断接频繁、移动终端资源有 限等缺陷，造成了移动数据存取的瓶颈。它傥该环境下查询处理面临定的 挑战，减少移动节点对数据库的访问正是解决此瓶颈的关键。语义缓襻是基 于客户逡询语义提关建立的一秘察户缓存，内容枣以往壹询的结果| 三l 殷稷应 酶语义攘述季句或针对语义缓存静特，征。客户灞可戳裁趸零憋缓存魏语义信息 进行推理，从而确定客户查询魑谣可在本地被究全解答或部分解答。炼立在 语义缓存基础之上的查询处理就可以减少对数据库的访问凝以及网络上的数 据传输缀，提高查询响应速度。针对这些考虑，本文提出? 一个语义数据存 绩摸羹及箕缍缓，然屠基予该模黧对壹逮处瀵及箕饶纯遴嚣了谨缀熬攥述。 结合内嵌式数据库的优点，本文采用它作为焱询结果和语义数据的管理系统。 本文还设计了一个应用系统框架，最后开发了一个实验系统，对语义缓存模 型和查询处理方法进行了检测。 关键字：查询处理，语义缓存，移动计算，焱询修剪 胡风根 基于语义缓仔查询址理技术的研究与应用t p 山人学硕士学位盹文2 0 0 4 5 r e s e a r c ha n da p p l i c a t i o no f q u e r y p r o c e s s n g b a s e do ns e m a n t i cc a c h n 町g c o m p u t e r s o f t w a r ea n d t h e o r y n a n a e ：h u ，f e n g g e n s u p e r v i s o r ：p r o f e s s o rl i ，l e i a b s t r a c t i nm o b i l ec o m p u t i n ge n v i r o m e n t ，n a r r o wb a n d w i d t h ，f r e q u e n td i s c o n n e c t i o na n d 1 i m i t e dr e s o u r c e sh a v eb e c o m et h eb o r l e n e c ko fd a t aa c c e s s i ti sac h a n l l e g i n gt o q u e r yp r o c e s s i n g s oi t i st h ek e yt os o l v et h ep r o b l e mt or e d u c et h et i m e so f m o b i l ec l i e n t sa c c e s s i n gr e m o t ed a t a b a s ea n dt h eq u a n t i t yo fd a t at r a n s f e r r e d t h r o u 血、v i r e l e s sc o n n e c t i o n w h i l es e m a n t i cc a c h i n gi st h a tt h ec l i e n tm a i n t a i n si n t h ec a c h eb o t hs e m a n t i c d e s c r i p t i o n a n dr e s u l t so fp r e v i o u s q u e r i e s s i n c e s e m a n t i c sa b o u tt h ec a c h e di t e m sa r es t o r e di nas e m a n t i cc a c h e t h ec l i e n ti sa b l e t or e a s o nf r o mt h el o e a lc a c h et od e t e r m i n ew h e t h e raq u e r yc a nb et o t a l l y a n s w e r e d ，h o wi t e a r lb ea n s w e r e d ，a n dw h a td a t aa r em i s s i n g h e n c e ，t h eq u e r y p r o c e s s i n gb a s e do ns e m a n t i cc a c h i n gc a r tr e d u c et h en e t w o r kc o m m u n i c a t i o n c o s t ，a so n l yt h er e q u i r e dd a t aa r es e n tf r o mt h es e r v e rt ot h ec l i e n t a n dt h e na c a c h i n gm o d e lo fs e m a n t i cd a t aa n dad a t ao r g a n i z a t i o na r eg i v e ni nt h i sa r t i c l e b a s e do nt h em o d e l aq u e r yp r o c e s s i n ga n di t s o p t i m i z a t i o na t ed e s c r i b e d a b u i l t i nd a t a b a s ei su s e dt om a n a g et h eq u e r yr e s u l ta n di t s c o r r e s p o n d i n g s e m a n t i cd a t ab e c a u s eo fm a n ym e r i t s a sar e s u l t ，a i la r c h i t e c t u r eo ft h es y s t e m b a s e do ns e m a n t i cc a c h i n gq u e r yp r o c e s s i n gi sd e s i g n e d ，a n dt h e nae x p e r i m e n t a l s y s t e m i sd e v e l o p e d k e y w o r d s ：q u e r yp r o c e s s i n g ，s e m a n t i cc a c h i n g ，m o b i l ec o m p u t i n g ，q u e r y t r i m m i n g h 胡凤根基于语义缓存的鸯询处理技术的研宄与成用中山大学硕士学位论文2 0 0 4 5 0 1 论文主要内容 h u舌 本文的主要内容是研究基于语义缓存的查淘处理技术，并以数据库访问 部件作为其应用背景，给出了语义数据的存储模型，并详细描述了查询处理 算法及其优化处理。在前两者的基础之上设计出了一个查询处理技术的应用 系统框架，然后实现了一个实验系统并给出了相应的实验数据。文章的最后 提供了对语义缓存，查询处理技术，优化处理和实验系统的总结，并对未来 的工作进行了展望。 0 2 论文组织 本文共分为六个章节。 第一章简单介绍了基于语义缓存的查询处理技术的研究背景，分别是问 题的缘由，相关的研究现状和笔者在这方面所做的工作。 第二章讨论了语义缓存与查询处理技术的理论与技术基础，语义缓存的 内容，各种缓存技术的比较，基于范式的查询公式求值算法和查询处理则规 则的逻辑表示等。还讨论了查询处理技术的基础，就是语义数据存储模型与 组织，它们分别是语义数据的逻辑表现形式和物理存储形式。 第三章基于第二章所给出的语义数据的存储模型与组织，给出了查询处 理的解决方法和相应的处理过程，并在最后一节对查询处理进行了优化。为 论述查询处理，本章分了五节分别进行讨论，它们是查询修剪，查询求值， 结合策略，替代策略和优化处理。 第四章则是在前面第二、三章讨论的基础上，设计了应用上述查询处理 技术的数据访问部件的系统架构，并对框架进行了分析。主要包括查询处理 模块，数据管理模块，安全管理模块，日志管理模块，一致性维护模块等。 在本章还对查询公式进行了设计，并讨论了基于这种设计所实现的查询公式 的相交和求差算法。 第五章则是在结合前面各章所述的理论和技术基础上，对试验系统进行 了讨论。分别从试验环境描述，系统实现和实验结果几个方面进行阐述。 第六章是对上述工作的总结，并对今后的进一步工作作了一下展望。 胡风撮 基于语史疆稃靛囊谰娃理技拳豹研究与虚弱串出太学磺士学蹙论文2 0 0 4 一s 1 1 研究背景 第1 章背景 移动计算模式蹴传统计算模式更加灵活多样，代表网络通信发展的主流 和方向。但移动计算环境有通信带宽窄、网络断接频繁、移动终端资源有限 等缺陷，造成了移动数据存取的瓶颈。减少移动节点对其饿带点的访闻建解 决魏稔联豹关键【l 】。毽翦，主要采麓数蕤缓存技零簿决这一溺蘧，久翻辩魏矮 技术避彳予了大量的研究。查询处联技术在移动计算中处于很重要的位鬣，如 何提高该环境下查询的反应速度便成了一个缀德得研究的课题。在语义缓存 孛，查询可以充分利用本地语义缓存鸵嚏密，从箍降低网络殍链，加快晌墩时 闯，并支持移动客户旗蔟对熬数掇访闫【2 窝。 数据缓存是把服务器端的部分常用数据存储到客户端，从而达到减少网 络通信爨的一项技术，主要有页缀存、记录缓襻和语义缓存三类 1 】。页缀存 与记录缓毒虫于只缓存数撂两不镪鸯语义售慧，窖户查询怒否可鞋在客户端 本地解答，要靠与缀务器通信来确定，增大了阏络开销，所戳不逶手移动计算。 语义缓存同时保存畿询结果和语义描述，客户端可以利用零地缓存的语义信 息进行推理，从而确定客户查询怒否可在本地被完全解答或部分解答。鹦一 方瑟，凌本建不能缀剿解答数聱转将竣修剪出来，发往黢务器，这样潍镶 大程寝上减轻网络上镥输静数据激，因此语义缓存技术在移动计雾中褥到广 泛应用。 但怒，日前对语义缓存的研究和应用还存在一定的局隈性，主要表溉在： 1 ) 客户裁蓑要瓣缓存豹数爨秘浯义迸簿缀缓彝管理，壤熬了凝努茨强镑 鞠系统复杂度，会耗费客户端有限的资源； ( 2 1 语义缓存往往把内存作为存储介质，这会影响客户端处理其它事务的 效率，降低客户端速度；同时，由于内j 筝容量的限制，客户端很礁包含 霆够黪藩惑； f 3 1 语义缓存存储数据的粒发通常为“段( 戚块) ”，这种存储模型撼然是 比较粗糙的，查询求值很难优化； f 由予在查询的过程中，并没有保存在服务器查询结果为空的查询记录 刭缓存中。这睇没有充分熬潮羯套运与数据痒穗关鹣僖急，造成了定 的浪费。 近年来，内嵌式数据库技术猩嵌入式系统( 如便携设铸) 等领域樗刹越 来越广泛的应用，麴【7 】中的e b a s e 系统。内嵌式数据库一般具有体积小、占 矮资澈少、效率嵩、速度快显与平台无关等黪点，笼较符合移动终壤竣器豹 要求，而且内嵌式数据库本身是一个小型的数据库管理系统，所以可与大型 2 胡风根基于语义缓存的查询处理技术的研究与应用中山大学砜士学位论文2 0 0 4 5 数据库管理系统在数据存储和运算上实现统一。以往的语义缓存往往把内存 作为存储介质，本文中将使用内嵌式数据库存储和管理客户端缓上的数据以 及相应的语义数据，并且将数据访问部件d a 作为应用背景来研究基于语义 缓存的查询处理技术。 1 2 研究现状 语义缓存及查询处理在文献中被广泛研究，并在不同领域里得到应用。 在中央式系统中，为了节省随后的查询计算并生成更高效的查询计划 3 6 ， 前面的查询结果被缓存到内存中。这样做主要是为了减少磁盘访问。在客户 服务器环境是为了减轻网络拥挤及改善系统可伸缩性 5 2 0 。另外，由于语 义缓存使得客户具有更高的自治性，使它对移动计也特别有吸引力 2 2 。另 外，在一些特定的领域的应用也得到开发，如o l a p ，l d a p ，w w w 以及异构系 统 1 。下面将从缓存模型和查询处理两个方面简要叙述一下早先的基于语义 缓存的查询处理的研究情况。 缓存模型方面，文章 5 】中提出的语义缓存是基于执行过的查询，就是根 据己执行的查询，将数据送入客户缓存。它指定单个缓存项，语义缓存定义 为语义区域的集合，每个语义区域都有一个约束公式描述去内容，只考虑“选 择”查询。文章 2 0 】是基于谓词的缓存。与 5 】不同，它没有指定单个缓存项， 相反，它把整个缓存看成一个整体并用缓存查询谓词的集合来描述。而且它 不检测如何组织和存储项。而且它允许一般的对一个或多个关系的“选择- 投 影连接”查询。文章【1 】中则首次正式定义了所使用的查询、缓存项以及缓存 本身，并给出了一个正式的缓存模型。客户端的整个缓存是由其上的所有语 义段组成的，每个单独的段可能只包含结果的- d , 部分，多个段合在一起可 能产生结果的更大部分或者全部。但这样做会导致客户端的缓存语义段的数 量随着用户访问服务器次数的增多而迅速增加，而且每次查询可能需要进行 多次分割，一次查询完成之后会产生很多小的语义段( 可称之为语义碎片) ， 而这些小的语义段下次会被用于查询的概率很小。这样不仅造成了空间浪费， 而且使查询处理中的修剪、结合和替代等问题变得很复杂。结合上面所述研 究，本文给出了查询、析取范式、记录结果集、结果集以及空结果集的概念， 以用来描述缓存模型。而且基于该模型的处理不会产生语义碎片。 查询处理方面，文章 2 0 首次引入了查询修剪的概念，它是当一个查询 和一个缓存语义有部分重叠时，就把该查询分成两个不连接的部分：重叠部 分和剩余部分。 5 则在此基础上更进一步，把分开的两部分分别称为“探头 查询”和“剩余查询”。但均未给出详细的查询处理策略。文章 1 7 2 5 则在上述基础上给出了相应的查询处理策略。 1 给出了查询计划树的概念。 作者将查询处理机制扩展到考虑整个缓存，当查询被第一个段修剪之后，剩 胡风根基于语义缓存的查询处理技术的研究与应用中山大学硕士学位论文2 0 0 4 5 余查询被下一个候选段修剪，该过程持续到没有段能计算查询结果为止。最 后的剩余查询被发往服务器进行处理。当允许剩余查询被语义段修剪时，查 询处理过程会变得更加困难，尤其是当混合分割发生时，事情变得极为复杂。 该查询计划树则清楚地表示了奁询每部分和涉及的语义段之间的关系。并附 加了一个辅助数据结构“动作列表”，用于分别记录在客户端和服务器端处 理查询的： 作序列。当所有子查询的结果得到后，就可以应用查询计划树和 工作列表把所有的部分结果组合起来形成最后的结果。文章【7 】中提出一个基 于语义缓存的客户缓存机制，给出缓存的内容组织，提出缓存项合并策略： 然后讨论了基于语义缓存的查询处理策略。文章 2 5 则针对如何从基于语义 描述的缓存中导出当前查询( 部分) 结果的问题，研究了查询从缓存导出的充 分条件，并在定义查询与缓存之间的精确匹配、包含匹配和相交匹配几种情 况的基础上，给出缓存与套询、包含与相交匹配的判断条件和相应的算法。 文章 7 2 5 对如何判断本地是否包含某次查询给出了相应的算法，但是对于 如何进行查询修剪只是进行了简单的描述，并未个出具体的算法设计。针对 这些情况，本文中查询处理修剪算法只需要修剪一次即可，而且给出了一个 求出探头查询和剩余查询的算法。针对特定的查询类型( 如涉及算术不等式的 合取查询) ，前人也给出了有效的算法，但是也指出如果允许变量之间的 比较存在，情况会变得非常困难，在整数域内甚至达到n p - h a 埘l 【3 7 】。故本 文中的实现算法没有考虑这种特殊情形。 文章 5 】 6 】 3 5 】研究了语义缓存方面的替代策略问题，并给出了针对不同 语义模型的替代方案。文章【5 】针对客户端缓存和在客户朋琵务器数据库系统中 的替代，给出了一个语义模型，并将这种方法与页面缓存和记录缓存进行了 比较。模型基于三个关键的思想：客户端维护一个对缓存中数据的语义描 述；替代策略的使用信息以一种适应于语义区域的方式存在；维护缓存 数据的语义描述使针对替代策略的合并本地语义标识的复杂评估函数可用， 而不仅仅是l r u 和m r u 。在文章【3 5 】中则提出语义缓存下最小权值项 l w i ( 1 e a s tw e i g h ti t e m ) 替换策略，该策略由缓存项投影属性的访问频率和缓存 项与查询的条件匹配情况，结合数据访问的时间局部性考虑决定缓存项的权 值，替换最小权值项。作者并通过性能分析实验，得出在语义缓存中，基于l w i 替换策略的系统性能要优于基于传统l r u 和l f u 替换策略的系统性能。 1 3 本人的研究工作 本文根据移动计算环境的特点，针对目前语义缓存技术的局限性，创造性 地提出了用内嵌式数据库取代了语义缓存中“段( 或块) ”的存储和管理，建 立了语义数据存储模型，并在此基础上研究出查询求值及其优化算法。优化算 法充分利用了数据库和语义缓存信息，把一个查询分为探头查询，空查询和剩 4 酮风根基于语义缓存的查询处理技术的研就船应用中山大学硕士学位论文2 0 0 4 s 佘餐询三个部分。每次的查询修剪只需黉避行次即可，使处理过程交得简馨。 凌这些磅究工佟的基稿土实现了一个实验系统，著捡测了文中所提出的谮义横 黧秘查询处理方法。 第2 章语义缓存理论基础与存储模型 2 1 理论基础 2 1 1 语义缓存的内容 在客户鼹务器数据库系统中，谮义缓襻是基手客户查诲语义相关建立麴 一耱客户缓存。语义缓存豹内容囊潋缝豢谗豹绩暴戳及稳盔魏接述捧减赞融谬 义缓存戆特薤【3 5 】。 关系数据库有交( i ) 、并( y ) 、投影( 拦) 、选择( 6 f ) 和遥专j k 鬏( 芏) 纛 萃孛基本运算，其中最常用的是选择和投影计算，面最基本的是选择诗舞 ( s e l e c t - f r o m - w h o m f ) ：选择计算中的f 就怒本文所述的查询公式，对应予s q l 中的w h e r e 子旬：所以本文只讨论选择计算，且只针对服务器的单表或视图。 对于每次查询完成之后，在客户端襻储符合条件f 的包含所有字段的记录。i 耐 不仅仅缓存部分字段，因为，在现实嫩活中，大量应用所发出的查询具有很强 的语义相关性【7 】。所以这里并不讨论投影矩操作，因为这个功能可以在本地宓 现。 对予每一次查询完成之后，我们蠢如下的语义表示，这个定义将在后西2 。 2 + 2 繁中出现。 ，荬孛1 3 ( 2 p 延怒逡辑诗算孛戆查谗公式f 豹板敬菠式袭 示，d c 。= o d c p p c r ) ，d c r e d b 。该公式成为结采记录集，荠将鞋藏终为 移动客户端的缓存粒度。 之所以只缓存符合上述要求的焱询，主要出于性能和代价方面的考虑。蓠 先，s e l e c t - f r o m - w h e r e f 句是最常用的畿询语句。对于有更复杂的查询语句的蠢 询，其结果再次利用可能性小，缓存下米的意义不大；第二，谓词表达式瑟求娥 台取式，是考虑到缓存项与查询项描述题配时的性能，因为如果表达式条件中 允许或连接比较项，则表达式的可满足性、隐含性判断是n p 难问题，但如槊按 w 缓存查询缓存，就可以给出多项式时间的判断算法，这个限制可以保证旗于 缓存查询豹性能。另一方夏，实际上这榉的限制并不妨碍谓词表达式的表达能 力，毽为对于任蘩裴空查询谓词袭达式，瓣祭 串不童据矛盾静表达式都可以丽 攒取蘧式表示，摄取莛式是由合取予茂缀或瓣辑取式，嚣建，廷霉将摄取蕊式孛 瓣最擞 摹于语义捱带瓣蠢询娃理技术抟麟究与穗舄串出大学硪士学位论文2 0 0 4 5 的各个析取项分解出来独立地作为一次查询，那么，每次查询的谓词就是取 式，最慝将结果合并就哥达到客户的要求。文章 7 中已对此进行了一定的实验 磅究，并敬褥了不镑静羧采。它绘疆了可缓存矮豹褫念，鬟骞魏下摇述： 对于客户发出的任何一条s e l e c t f r o m rw h e r ef 查询谣句，如果w h e r e 子旬是通过逻辑运算符a n d 连接的任意多个由俑性和常量组成的比较表达式， 那么，我稍稼该语句戈胃缓毒查询，黪惩三元缀( r ，a q ，c q ) 表示，其中粕是 该查询所作用的数攒库关系集合 r t 。，r 1 ，a q 是该查溺所投影兹属拣集合 fa 1 ，a m ) ，c q 鼹查询所要满足的谓词条件液达式c 1 八八c n 对于非可缓 存查询，可以不经缓韶赢接送交数掇痒服务器处理。 疰 予诿义缓存憝黻一次壹询返霾豹结果麓糠度缓存，霸蘧每次缓存瓣数 据也用三元组 描述，称之为结果记录集。谢义缓存的内容通 过一组结果记录集描述，每当有新的数据进入，或有数据被替换，缓存的内 容及结聚记录描述都鼹做相应的改变。每个结采记录集对皮个结果集s c ， 臻采集憝滚是其骞稳翔d c r 戆臻聚记录集条移豹数据痒嚣缀经过劳搡髂掰褥 到的数掰。每个结果浆s c 对应服务器上面的一个关系或者视图。由于每次 查询的焱询条件f 与缓存中的用析取范式所袭示的语义子匈之间可能会存在 一定的交集，当然这墩是缓存的意义所在，那么实际上发犍服务器的查询盼 蠢诲条舞只是f 熟一熬劳，其余端努多霹戳程零缝褥爨。我翻箨在零薅霹鞋 完成的蠹询位探头轰询( p r o b eq u e r y ) ，发往服务器的焱询为剩余森询 ( r e m a i n d e rq u e r y ) 。剁余查询的邋回结果和其捆应的语义予旬存到结果集s c 中，以备下一次查询使用。出予每次查询缓存下来的只是原数据库表的部 分，舔数据库表终凳一个整薅存程豹各令藩瞧之润豹关联获系在缓存串掰能 会丧失。主键是惟一标识关系中元组的属性或属性集，关系中任意两个冗组 的主键都不相同。利用主键的惟一性可以使缓存中的数据恢复它们在原数据 库中应露瓣关联，由予我铝缓存鹣是包含结聚铤录集中关裂d c r 中的聪蠢属 往麓记泶集合，繇戮可班遥兔这黧关联关系蠢客户端缓存审豹丢失。 2 1 2 备种缓存技术的比较 鲡文章j 孛耩滚，爽瑟缓存孛在客户端耧缀务器之瀚臻遴是一个燮疆， 当在客户端需要执行一次查询时，如果本地不存在所要套询的页面，郝么对 该页面的请求被发送到服务器，然后再由服务器返回这个凝面到客户端。替 代策略嬲驰是l r u 竣誊m r u 算法。记录缓存在摄多方露鸯页面缓存类似， 不同之处在于它维妒豹是一条一条豹记录弱不楚一个页瑟，缓存粒度较小。 正由于此，客户端和服务器之间需要传递犬激的小信息，逸会给查询的执行 带来一定的不便。像页面缓存一样，记录缓存采用的也是一种基于访闯的替 鼗繁赡，麴l r u 。敷墨同靛是，激录缓存中没有为记录作s p a f t a li o 巍i t y 瓣标 记，两仅仅只利用了t e m p o r a lt o e a l 谴y 。 6 胡风根基于二语义缓存的奇谰处理技术的研究与应, q l中山大学硕士学位论文2 0 0 4 - 5 语义缓存除了在本地存储记录集之外，还要存储与这些记录集所对应的 查询条件，也就是用析取范式表示的语义子句。它的缓存粒度介于页面缓存 和记录缓存之间，是一个动态的记录集合，给查询处理带来了一定的灵活性。 在前两种查询中，如果在本地缓存中没有足够的数据时，服务器在接到请求 之后将发送一个页面到客户端，而其中并不是所有的数据都是此次查询所需 的，造成了一定的时间和空间上的浪费。语义缓存则不存在这个问题，它可 以通过剩余查询r e m a i n d e rq u e r y 来完成探头查询p r o b eq u e r y 不能完成的部 分，并且只返回必需的查询结果到客户端。 表2 一l 中将语义缓存与页面缓存做了比较 1 】。 表2 1 语义缓存页面缓存原因 只传输需要的数据和 通信费用低高 s c 中简洁的请求表达 缓存空间 低高 只存储满足先前查询 开销的数据 查询处理的 由于s c 保存了语义信 并行性 易难息，想要的数据可以精 确确定 移动客户更加自治，即 用于移动式 高效低效使网络断开，用s c 也 计算环境 可得到部分结果 文章 6 】中，针对三种缓存的特点，也给出了一个简单的比较，如表2 - 2 所示。 表2 2 数据粒度缺少数据缓存替代 页面缓存 g r o u pf a u l t i n g t e m p o r a l l o c a l i t y ( l r u ，m r u ) s p a t i a l 记录缓存 s i n g l ef a u l t i n g l o c a l i t y ( c l u s t e r i n 曲 语义缓存 d y n a m i c a l l y r e m a i n d e r g r o u pq u e r i e s s e m a n t i cl o c a l i t y 从这两个表的比较可以看出，语义缓存较之传统的页面缓存和记录缓存 都有一定的优越性，符合移动环境下数据访问的需要。 7 胡凤根基于语义缓存的查询处理技术的研究与应用中山大学硼j 二学位论立2 0 0 4 5 2 i 3 查询处理规则的逻辑表示 文章 9 提到，关系数据库有一个逻辑解释并且可以用逻辑表示。这些逻 辑表示构成了基于语义缓存的查询处理的理论基础。 设r ：r ( a i ，a n ) 是一个模式，则r 可以看作为一个n 元谓词。 设 r ) = ( a ，a l a ) ，。，( a | 1 1 1 ，a m 。) ) 是r 对应的关系，则( r ) 可以看成为谓 词r 的解释。 设r l ，r 。是模式，则d = r 1 ) u ，u r 。) 是数据库。 设p ，0 是原子公式，则： 设q u e r y ( p ) = p ，q u e r y ( q ) = q ，并且 p ) = 一o ， q ) 2 a ，并假定q u e r y ( p ) 已经执 行，并且p 已经缓存，q u e r y ( q ) 是当前提问则： ( 1 ) 如果p s u bq ，并且由于 p ) q ，则( q 只需从 p ) 中提取。 ( 2 ) 如果pe q uq ，并且由于 p = q ，则q u e r y ( q ) 不必执行。 ( 3 ) 如果，( pi n tq ) ，并且由于 p n q ) = o ，则直接执行q u e r y ( q ) ， 因为无优化可言。 ( 4 ) 如果( p 1 n t q ) ，( p s u b q ) ，则需执行q u e r y ( q ，p ) 。在文章【4 】 中讨论了q u e r y ( q 一p ) 的求值方法。 这正好描述了查询与缓存之间的四中关系：包含、相等、相交和无关a 对这四中关系进行判断，可以得出相应的查询修剪方案，从而最终计算出查 询结果。 2 1 4 基于范式的查询公式求值算法 文章【8 】中提到，一个查询公式都可以化为析取范式的形式。本文的存储 模型中的查询公式就采用了这种范式形式，并给出了基于范式的查询公式求 值算法。 2 1 4 1 查询公式的集合表示 假定所有的查询公式都已化为析取范式，例如： 墨v v v s 。 其中s ，为： a l l a ，2 a i n i 我们把( 1 ) 和( 2 ) 分别叫做析取范式和合取子式。 ( 1 ) ( 2 ) 事实上，在范式中的墨( 或以) 的顺序是没有关系的，因此我们可用集合 表达析取范式和合取予式。例如： 析取式s 。v 是v v a n 表示为 s 。，s ：，最) 合取子式a ， a 。2 a i n ，表示为 4 i ，a j 2 ，a n ) 胡风根基于语义缓存的查询处理技术的研究与虚削 中山大学硕士学位论文2 0 0 4 5 查询公式( 4 1 l a 1 _ ) v ( 爿2 l a 2 勺) v ( 4 ja a 慨) 寻i 厅；为 4 。，a 玑 ， 一：。，a ：。：) ， 4 。，a 。) ) 。 我们称上述表示为查询公式的集合表示。 2 1 4 2 求值算法： 假定查询公式是集合表示的。显然查询公式的求值顺序是：原子公式，合 取子式，最后是析取范式。 算法描述： s t e p l 析取范式s tv s 2v v s 。求值 s t e p 2 找出范式中的所有合取予式a 。i a ，2 a a i n ， s t e p 3 合取子式a j li 4 2 i a i n 求值 s t e p 4 找出子式中的所有原子公式爿。 s t e p 5 原子公式4 。求值 s t e p 6 返回到合取子式层次，计算出合取子式 s t e p 7 返回到范式层次，计算出范式结果 在后面的系统实现中，查询公式的相交和取反算法就是按照这种思路进行的。 2 2 数据存储模型 数据访问部件内嵌于客户端，其内核心是一个基于范式查询公式求值、 优化算法的关系数据库，占用空间很小( 约8 0 k ) ；并以记录的形式存储查询 结果和描述语义。关系数据库有交( i ) 、并( y ) 、投影( 7 c ) 、选择( o f ) 和迪 卡儿积( z ) 五种基本运算，其中最常用的是选择和投影计算，而最基本的是 选择计算( s e l e c t - f r o m - w h e r e f ) ；选择计算中的f 就是本文所述的查询公式， 对应于s q l 中的w h e r e 子句；所以本文只讨论选择计算，且只针对服务器的 单表或视图；事实上，由于客户端存储了整条记录，投影计算可以在本地实 现。 数据访问部件所采用的数据存储模型主要考虑以下二点： 1 ) 客户端须存储查询结果及其语义，并能对所存储的结果和语义进行修 剪、求值、合并和替代的操作： 2 ) 可以维护客户端所存储数据和语义、以及与服务器数据的一致性。 针对这些考虑，下面给出相应的定义： 定义2 1 内嵌式数据库e d b e d b 是数据访问部件中所使用的内嵌式数据库，存储查询结果和语义信 息。 e d b = ( r 1 ，r 2 ，r m ) ，其中r i 中( 1 i n ) 是e d b 中的关系。 这里用a r i 代表由关系r i 结构定义的属性集合，a 代表整个数据库的属 9 胡最撮萋_ = f 遘义壤襻曲蠢询娃瑗技术辩辫究与应用 中山大学轿士学位论文2 0 0 5 性集，有a = u a r i ，( 1 i n ) 。 定义2 + 2 比较谓词p c 对予e d b 的属靛集a ，e d b 的一个比较谓词p c 的澎式是p c ao pc 疆 a ，o p ， ，= ) ，c 是一特定域内的常量。 为简化问题，在研究中，我们假设一个查询的选择条件是比较谓词的 个 王意约束公式，也藏是一个比较谓词台取救枣慝取。 定义2 3 析取范式 析取范式具有逻辑表现形式：p = p l v p 2 v ，v p 。，其中p 是p l 析取斌，且 p i = p i l a p i 2 八，a p i m + 每个p # ( t i n ，l 2 3a n d8 0 0 0 _ s a l a r y 5 0 0 0 可表示为：d c l p = p i = p i o o p t o l p i 0 2 ；其中：p z o o = a g e 2 3 ”， p t 0 1 = “s a l a r ys8 0 0 0 ”，pr 0 2 = “s a l a r y 5 0 0 0 ”； d c 2 口：s e l e c t + f r o mrw h e r ee d u l e v e l = 博士o rs a l a r y =2 3 1p 1 0 1 s a l a r y 5 0 0 0 2p 2 0 1e d u l e v e l 博士 2p 2 1 1 s a l a r y = 3 0 0 0 查询结果记录集d c i 、d c 2 ( 即按照不同语义进行查询的结果集，各记录集 对应语义索引表中的字段d c i d 的值) ： p o c l 的查询结果记录集d c l 表2 - 6 i dn & m es e x s a l a r y e d u l e v e l a g e 0 0 1 小华男 8 0 0 0 博士 2 5 0 0 4 小孙女 5 5 0 0硕士2 7 0 0 5 小李男 6 0 0 0 硕士 2 5 p d c l 的查询结果记录集d c 2 表2 7 1 2 胡风根蔫于语义缓存的查询处理技术的研究与应用中山大学坝士学位论文2 0 0 45 i dn 锄es e x s a l a r ye d u l e v e la g e 0 0 1小华 男8 0 0 0博士2 5 0 0 2 小名男3 0 0 0本科 2 2 l 0 0 7 小刘女1 0 0 0中专2 2 分析d c l 、d c 2 可知：d c i r n d c 2 r = i d = 0 0 1 ”) 。 通过语义关系表( 表2 8 ) 可将结果记录集d c l 和d c 2 合并，得到结果集 s c ，有如形式 ，其中，p = d c i p v d c 2 p ，即( 鼻o o 只o l 只0 2 ) v 最0 0v 昱胪 r s 就是下面的表2 - 9 。 表2 - 8表2 - 9 i dd c i d 0 0 11 0 0 12 0 0 22 0 0 41 0 0 5l 0 0 72 i dn a m es e x s a l a r y e d u l e v e l a g e 0 0 1小华男8 0 0 0博士2 5 0 0 2小名男3 0 0 0本科 2 2 0 0 4小孙女5 5 0 0硕士2 7 0 0 5小李男6 0 0 0硕士2 5 0 0 7小刘女l 0 0 0中专 2 2 上面的举了一个如何有已有的查询结果组成对应于服务器上面某个关系 r 的缓存表的例子。下面结合这个缓存表，在需要举一个例子结合查询处理 过程，对查询处理过程进行辅助说明。 假如现在用户端需要进行如下的查询： s e l e c t + f r o mrw h e r e s a l a r y 2 6 0 0 0 那么我们可以得到 绋，= p q ，= b 0 0 b 0 l 其中有 只o o = s a l a r y = 6 0 0 0 采用这种数据组织方式既可保证客户端所存储数据冗余最少、且数据与 描述语义上的一致性，也可保证与服务器数据的一致。而客户端所存储的语 义表示为析取范式的形式，并以比较谓词为单位进行存储语义信息能最大限 度降低冗余度。 第3 章查询处理与优化 文章【1 0 】第七章提出了几种为解决问题设计有效算法的通用技术，其中一 项很重要的技术就是分治策略。 分治策略的基本思想：把大问题化成较小的子问题，把子问题再化成更 小的子问题，依此下去，直到每个子问题可以方便的求出解。这样，我们从 胡风根基于语义缓存的啬i 旬处理技术的研究与应用中山大学硕上学位论文2 0 0 45 较小于问题的解可以方便地求出较大问题的解。 在查询处理技术中，如果它是一个耗时或者查询速度比较慢的查询，那 么我们可以采用某种方法将查询分割，得到几个查询速度比较快的子查询， 然后合并子查询的结果得到整个查询所要的结果。本章中，我们将用到查询 修剪的概念，并利用查询修剪算法分割查询为探头查询和剩余查询，前者可 以在客户端完成查询计算，后者则发往服务器执行查询。从而实现了闯题的 分解，并利用子查询的解答来解决整个查询求解的问题。在优化算法里面， 我们还提出了空查询的概念。 下面给出查询处理活动的工作流图： i 。 苣之 手飞写固 ， ，审 f t 吼n u 竺竺岁 - 3 1 查询修剪 3 1 1 相关定义 图3 1 定义3 1 查询修剪 当查询q ( 形如 ) 在客户端的s c 表中只能部分解答，将q 分解 为两部分：一部分可从s c 回答p 。( p r o b eq u e r y ) ，另一部分不能从s c 得到 回答r 。( r e m a i n d e rq u e r y ) ，这个分解过程称作查询修剪。 d a 在接收到查询q 后，首先进行修剪，得到p q ( j 影如 ) 和粕( 形 女1 ) ；显然满足：p q p v k p = q ，且p q p a 粕p = 巾。然后分别在 本地和远程数据库执行p 。和k ，并合并它们的结果即为查询q 的查询结果。 这种查询修剪实际上是利用了一种分而治之的策略。 1 4 胡风根基于语义缦i 宇的查询处理技术的研究与应用 中山大学硕士学位论文 2 0 0 4 - 5 定义3 2p q ( p r o b eq u e r y ) p 。是在d a 语义缓存区域查找部分或者全部解答的查询条件，其解空间为 q ，。f q s c 。p 。能在本地得到的解答越多，说明缓存中的数据利用率越高，越能 加快查询的速度。 定义3 3r q ( r e m a i n d e rq u e r y ) 是将q 修剪后的部分发往服务器端进行查询的查询条件，其解空间为 q 。s c 。我们称该运算为差的提取。求出剩余查询的目的是为了尽量剔除在 本地可以得到结果的那部分语义，而将在本地不能得到解答的部分的语义子 句作为查询条件发往服务器端进行查询，返回结果与探头查询结果合并，得 到用户想要得查询。 q 。n s c 。与q ，s c 。关系如图3 所示 图3 2 定义3 4 ：假设存在s c 形如 ，和一个查询q 形如 ，我们称： 1 ) q 能从s c 得到解答，如果s c r = q r 且q p k s c p 在s c r - k 是可满足的： 2 ) q 能从s c 得到全部的解答，如果s c r = q r 且q p ：，s c p 定义3 5 ：p 是一个基公式，如果p 中的所有项为常数。 例： p ：p ( a ，b ，c ) 是基公式， q ：p ( x ，b ，c ) 不是基公式。 也可以这样解释基公式，存在一个查询q 形如 ，当q p 为x _ a 的形式，并且当q h 中含有一条查询结果时，我们也可以称该查询q 是基的。 例如当用户执行一个如下的查询时，返回结果如下表4 1 所示，仅含一 条记录。那么我们就可以说查询是基的。 s e l e c