（计算机应用技术专业论文）基于xml的移动数据库缓存技术研究.pdf

硕士学位论文 m a s t e r st h e s i s 中文摘要 随着x m l 在各行各业的广泛应用，x m l 已经成为了事实上的一种通用数据表 示和交换的标准，纯x m l 格式在移动数据库中倍受青睐。然而，在移动环境中， 缓存技术对移动数据库的性能有着重要的改善作用，因此在移动数据库中如何高效 地对x m l 数据库进行缓存已经成为当前研究的热点问题。 由于移动环境所特有的移动性、频繁断接性、网络通信的非对称性、移动主机 处理能力的有限性等特点，使得移动环境下的缓存技术不同于传统的基于页面的缓 存技术，需要寻找一种比页面更小的缓存粒度。本文在综合分析现有x m l 数据库 缓存技术的基础上，针对x m l 数据库的特点，提出了适合于移动环境的缓存的粒 度以及缓存的存储模型。 缓存失效报告可以高效维护各移动结点缓存数据与服务器之间数据的一致性。 在缓存失效报告模型的基础上，分析比较了基于x m l 的缓存失效报告算法x 1 r 及 其改进算法。x 瓜改进算法根据数据的访问操作类型和访问频度动态的调整广播区 间长度，使得x i r 算法在移动环境中更加高效。另外，分析研究了基于x m l 的语 义缓存技术以及语义缓存的五种匹配模型，提出了移动数据库中基于x m l 的语义 缓存体系结构图，研究了查询的裁剪技术以及“探测查询”和“剩余查询”。 因为语义缓存是基于实体化视图的基础之上的，通过对移动客户端视图采用 “增量”方式更新可以减少不必要数据的传输，提高带宽利用率。为了更好的对移 动客户端的视图集进行维护，本文在基于p i u 算法的基础上，提出了一种增量视图 更新算法x s i u 。该算法中引用x m l 树型结构中结点的度和数据元的长度，对数据 新鲜度的值进行修正。通过对仿真实验分析表明，该算法能够在带宽急剧下降时有 效的提高传输效率。 关键词：x m l 缓存；缓存失效报告；语义缓存；视图增量更新；数据新鲜度 硕士学位论文 m a s t e r st h e s i s a b s t r a c t a si na l lw a l k so fl i f ea 谢d er a n g eo f m 。a p p l i c a t i o n s ，i nf a c t ，以lh a sb e c o m ea c o m m o ns t a n d a r do ft h ed a t ar e p r e s e n t a t i o na n de x c h a n g e t h e r e f o r e ，t h ex m lf o r m a t b e c o m e sm o r ea n dm o r ea t t r a c t i v ei nt h em o b i l ed a t a b a s e h o w e v e r , i nt h em o b i l e e n v i r o n m e n t ，t h ea p p l i c a t i o no ft h ec a c h ep l a y sak e yr o l ei ne n h a n c i n gt h ep e r f o r m a n c e o ft h em o b i l ed a t a b a s e t h e r e f o r e ，i nt h em o b i l ed a t a b a s eh o wt oh i g h - p e r f o r m a n c ec a c h e x m ld a t a b a s eh a sb e c o m eah o tr e s e a r c hs p o t d u et ot h eu n i q u ep r o p e r t i e so ft h em o b i l ee n v i r o n m e n t , s u c ha st h em o b i l i t y , f r e q u e n td i s c o n n e c t i o n , n o n - s y m m e t r yo ft h en e t w o r kc o m m u n i c a t i o n sa n dt h el i m i t e d p r o c e s s i n ga b i l i t yo ft h em o b i l eh o s ta n ds oo n b e c a u s et h ec a c h ei nt h em o b i l e e n v i r o n m e n ti sv e r yd i f f e r e n tf r o mt h et r a d i t i o n a lc a c h eb a s e do nt h ep a g e ，w eh a v et o f i n da n o t h e rs m a l l e rg r a n u l a r i t yt h a np a g e i nt h i sp a p e r , o nt h eb a s i co fc o m p r e h e n s i v e a n a l y s i st h ee x i s t e d 舭d a t a b a s ec a c h e ，i nt e r m so ft h e 舭d a t a b a s e sp r o p e r t y , w e p r o p o s e dac a c h eg r a n u l a r i t ya n dc a c h es t o r e dm o d e l i nt h em o b i l ee n v i r o n m e n t u n d e rt h ee n v i r o n m e n to ft h em o b i l ed a t a b a s e ，c a c h ei n v a l i d a t i o nr e p o r tc a nb ea l l e f f e c t i v es o l u t i o nt ot h ec a c h ec o n s i s t e n c yp r o b l e m sb e t w e e nt h es e r v e ra n dt h em o b i l e c l i e n t i nt h i sp a p e r , w eh a v ed i s c u s s e dt w ok i n d so f o p t i m i z a t i o na l g o r i t h m sb a s e do nt h e t r a d i t i o n a lc a c h ei n v a l i d a t i o nr e p o r t i e x i ra l g o r i t h ma n dm o d i f i e da l g o r i t h mb a s e do n t h ex i ra l g o r i t h m n el a t t e ra l g o r i t h md y n a m i ca d j u s t st h el e n g t ho ft h eb r o a d c a s t i n t e r v a lb yt h ea c c e s so p e r a t i o nt y p ea n da c c e s sf r e q u e n c y t i l i sm o d i f i e da l g o r i t h mc a n e f f e c t i v ei m p r o v et h ep e r f o r m a n c e b e s i d e s ，w ea n a l y s i sf i v et y p e so fm a t c hm o d e lo ft h e s e m a n t i cc a c h ex m l b a s e da n dp r o p o s e da r c h i t e c t u r eo ft h es e m a n t i cc a c h ex m l b a s e d a n da n a l y s i st h et r i m m i n gt e c h n o l o g ya n d p r o b eq u e r y a n d r e m i n d e rq u e r y s i n c es e m a n t i cc a c h ei sb a s e do nt h em a t e r i a l i z e dv i e w , t h r o u g ht l l e “i n c r e m e n t a l ” u p d a t et h ev i e wo ft h em o b i l ec l i e n t s ，w ec a na v o i du n n e c e s s a r yd a t at r a n s m i s s i o na n d i m p r o v et h eu t i l i z a t i o nr a t i oo fb a n d w i d t h i no r d e rt om a i n t a i nt h ev i e ws e t si nt h e m o b i l ec l i e n tm o r es u i t a b l y , w eh a v ep r o p o s e da ni n c r e m e n t a lv i e wu p d a t e da l g o r i t h m ， i e x s i u sa l g o r i t h mi n t r o d u c e dt h ex m l n o d e s d e g r e ea n dt h el e n g t ho fd a t am e t a t oa m e n dt h ed a t af r e s h n e s s u g hs i m u l a t i o na n a l y s i s w ef i n dt h a tt h i sa l g o r i t h mc a n g r e a t l yi m p r o v et h et r a n s m i s s i o ne f f i c i e n c yw h e n t h eb a n d w i d t hd e c l i n e ss h a r p l y k e y w o r d s ：x m lc a c h e ；c a c h ei n v a l i d a t i o nr e p o r t ；s e m a n t i cc a c h e ；v i e wi n c r e m e n t a l u p d a t e ；d a t af r e s h n e s s n 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：1m 彳 日期：呷加如 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论 导师 日期 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文 规定享受 作者 日期 硕士学位论文 m a s t e r st h e s i s 1 1 研究背景 1 1 1x m l 的发展 第1 章绪论 为了促进数据的交换和操作，在2 0 世纪6 0 年代，通过i b m 公司研究人员的工 作，得出了重要的结论要提高系统的可移植性，必须采用一种通用的文档格式，这 种文档的格式化必须遵守特定的规则。这也就是创建g m l ( g e n e r a l i z e dm a r k u p l a n g u a g e 通用标记语言) 的指导原则。从人们所产生的将文件结构化为标准的格式 的动机出发，i b m 公司创建了g m l ，并在其出版系统内部予以实现。i b m 公司采 用g m l ，以使用单一类型的源文件来维护书籍、报表以及其他各类文件。 1 9 8 6 年，欧洲粒子物理实验室( c e i 玎) 的研究员t i mb e m e r s l e e 和a n d e r e s b e r g l u n d 共同创建了一种基于标记的语言，为在i n t e m e t 上共享的文档做标记，于 是产生了h t m l 。 h t m l 当初仅仅提供了一种对静态文本显示的方法，显然不能适应越来越多的 需要。1 9 9 6 年，人们开始致力于描述一种新的标记语言，它是一种在w e b 中应用 广泛的新的标记语言，它是一种在w e b 中应用s g m l 的灵活性和强大功能的方法。 1 9 9 8 年2 月，w 3 c 批准了x m l l 0 规范。标志着一种崭新的、重要的语言x m l 的 产生，x m l 具备了s g m l 的核心特性，但又非常简洁，x m l 规范的内容甚至不到 s g m l 的十分之一。随即x m l 的应用如雨后春笋地展开，x m l 被看作是i t 行业 中一颗闪亮的新星。 1 1 2x m l 与移动数据库 扩展标记语吉 ( e x t e n s i b l em a r k u pl a n g u a g e ) x m l l l l 大大降低了数据管理和交换 的成本。它具有可扩展性好、所占存储空间小等特点，具有较低的网络传输成本。 因此x m l 在移动数据库具有广阔的应用前景，事实上，x m l 已经成为了一种表示 和存储数据的标准。随着x m l 的普及和广泛使用，许多研究人员开始重视以x m l 硕士学位论文 m a s t e r st h e s i s 格式表示和存储的数据，这使得人们对x m l 数据进行合理存储和快速查询的要求 越来越高，如何快速从大量的x m l 数据中获取信息已经成为一个急需解决的问题。 因此，在移动数据库中高效的处理x m l 数据成为一个新的研究方向。 1 1 3x m l 与移动数据库的缓存技术 由于x m l 所具备的可扩展性、结构性和可验证性等特点，其在各行各业，如 出版发行业、w e b 服务以及网站管理等行业已经得到了广泛的应用，如今x m l 已 经成为了事实上的一种通用数据表示和交换的标准。在移动数据库中，由于服务器 与移动客户端之间的网络具有不稳定性、带宽不够、传输延迟长等特点，因此纯 x m l 格式在移动数据库中倍受青睐。然而，在移动数据库中数据的存储组织方面， 数据的查询，缓存的粒度，缓存的一致性维护和缓存的替换策略方面跟关系数据库 的处理方式具有很大的差别。 为了提高移动客户端的响应速度，减少对远程服务器的频繁查询请求。通常采 用缓存的技术，将一些频繁访问的数据存放到移动客户端。研究表明，对于某个移 动客户端来说，通常只对某部分特定数据感兴趣。因此，当移动客户端提交查询请 求时，就可以通过缓存中的数据来进行“回答 ，而不必向远程服务器请求数据。 这样可以有效提高查询响应速度。为了对分布于若干个关系表中的数据进行重组， 般采用“视图 的技术按照一定的组织方式进行存储，这种技术称之为“实体化 视图”。采用视图方式一方面可以保护原始关系中的数据，另一方面可以使数据在 现有关系表的基础上进行重组显示，从而增加了操作的灵活性。【2 j 近年来，对于x m l 的研究一直是国内外学术界研究的热点之一，得到了广大 研究人员的普遍关注。通过将某个时间段内频繁访问的数据进行缓存，可以减少用 查询的等待延迟，提高客户端对数据的处理效率。移动数据库的传输代价是x m i 数据库的一个很重要的性能指标，因此对用户查询请求的响应时间就显得更加重 要。因此，对频繁使用的数据项进行合理的缓存，一方面可以减少移动客户端对远 程服务器的不必要的查询请求，提高查询响应速度，另一方面可以减轻网络负载， 使移动环境中有限的带宽得以高效利用。因此，研究基于x m l 的移动数据库缓存 技术具有很重要的现实意义。 2 硕士学位论文 m a s t e r st h e s i s 1 2 国内外研究现状 1 2 1 移动环境下关系数据库的缓存技术 1 缓存的复制技术 1 ) 两级复制技术 两级复制【3 ( t w o t i e rr e p l i c a t i o n ) 的概念最早由j g r a y 和j j k i s t l e r 等人提出。 两级复制采用主副本的方式对数据进行组织。在该系统中将结点分为两大类： 第一类为基结点，这类结点与固定的网络环境相联接，在每个基结点中都保存 数据库的副本。这些保存在固定结点中的副本称之为第级复制。 第二类为移动节点，这些结点通过无线网络与第一类基节点相连，并在移动节 点上存放数据库的复制，此为第二级复制。为了保持移动结点中数据一致性，在这 些结点上也保存有两个版本的数据：一类为主版本，另一类为暂态版本。主版本是 从主节点得到的最新值；暂态版本是由本地暂态事务更新的对象值。相应的事务也 被分为基事务和暂态事务。暂态事务对本地暂态数据操作，产生新的暂态副本，在 连接到基节点后，暂态事务提交到基节点，产生基事务，以更新主副本值，使暂态 副本固定下来。 一 2 ) 三级复制技术 三级复制体系结构( t h r e e t i e rr e p l i c a t i o n a r c h i t e c t u r e ) 3 1 ，简称为t t r 。它是 由复制技术、移动客户端的缓存技术以及服务器端的数据广播技术三者相结合的 产物。 t t r 结构由服务器级复制，空中复制，客户机缓存等三级复制机制构成： 第一级复制是指服务器之间的复制技术，又称为“服务器级复制”； 第二级复制是指服务器将频繁访问的数据对象组织起来，通过移动支持基站向 所有移动客户端广播，这种数据复制在无线广播信道上完成，因此而得名，所以又 名“空中复制技术 州； 第三级复制是移动客户端将频繁访问的数据保存在其自身的存储空间里，以保 证在客户机断接时能够从这些保存的数据中读取，所以又称之为“移动客户端缓 存 。 另外，在这种复制技术中，针对移动计算环境，设计了一种弱一致服务器级复 制机制( w e a k l yc o n s i s t e n ts e r v e rr e p l i c a t i o n ) ，简称w c s r ，支持客户应用提出不 同的一致性要求( 严格一致性与弱一致性) ，并采用了基于应用语义的冲突推测与 硕士学位论文 m a s t e r st h e s i s 消解技术，提高了复制消解时的事务成功率。 2 缓存失效报告 国内外已经对移动环境下的缓存失效报告技术进行了大量的研究，其中以 b a r b a r aa n di i n i l i e n s k j 【5 1 的缓存失效广播技术最为著名。在此基础上，人们提出了几 种新的技术来改进缓存失效广播技术。这种技术又名缓存失效报告，即服务器定期 或异步的广播缓存失效报告嘲，该报告中包含了最近被更新的对象，根据报告内容， 客户可使缓存中被更新对象失效，以保证缓存的有效性。以该算法为基础，针对各 种不同的实际情况，又对此算法作了很多改进，例如，j i n g t 7 】和a m e d 等人提出了基 于位序列的自适应缓存失效策略，它对广播的缓存失效报告采用位流形式进行组 织，并附加上对应的时问戳进行广播。为了有效节约移动主机能源，c a i 和t a n 等 人则提出了相对节能的算法。 3 关于移动客户端缓存的研究 所谓的语义缓存是指基于用户查询语句之间的语义相关性的缓存技术，它的思 想为：首先，通过查询的客户端缓存中的历史记录来确定与当前查询存在“相交” 关系的缓存内容，然后在这些缓存项中判断是否有查询的精确匹配或包含可导出匹 配，如果匹配成功，则移动客户端的用户查询结果可以从缓存中通过关系运算如投 影、选择等操作获得；若没有，但缓存项若包含部分用户的查询结果，则可将查询 裁剪为“探测查询”和“剩余查询 ，并将裁剪后的“剩余查询 提交到远程服务 器进行处理，再将服务器中返回的结果与能从缓存中的查询结果进行并运算，从而 形成最终的用户查询结果。 语义缓存区的缓存内容由历史查询的结果集及查询表达式的相关描述构成，缓 存命中则是通过将用户提交的查询表达式同缓存区中的各个语义缓存项进行匹配， 从而判断用户通过语义缓存是否可以回答用户所感兴趣的数据内容。在日常生活 中，移动客户端用户所提交的查询请求具有很强的语义相关性。如一个公司的部门 领导，通常情况下他只对他所负责的部门数据更加感兴趣，所以对公司数据库的查 询服务请求多为该部门相关数据内容，这些查询请求之间具有很高的语义相关性， 为了保证这种关联度比较高的缓存查询效率，通常采用基于时间局部性的语义缓存 以及查询语义局部性的缓存，而且数据的聚集度不好时其效率也能够得到保证。在 文献 8 1 t 9 将语义缓存与以页和元组为粒度的缓存进行了性能上的比较，并通过实验 证明了语义缓存较其它另外两种缓存技术对于关联查询处理只需有更少的带宽需 求及更快的响应速度；文献【9 研究了匹配紧密相关的布尔表达式相交以及包含的判 断问题；文献【1 0 】主要对缓存的完整性与缓存一致性两方面的内容进行了讨论。 4 硕士学位论文 m a s t e r st h e s i s 1 2 2 移动环境缓下基于x m l 的缓存技术 关于x m l 的研究大致经历了三个阶段【9 】： ( 1 ) 使用关系数据库保存x m l ，在具体操作方面需要涉及到x m l 到关系数 据库的相互转换； ( 2 ) 用特定模型系统存储x m l ，它们使用不同的文档存储方法，并设计基于 特定存储模式的查询方式，避免了关系数据库中进行文档映射和发布的开销； ( 3 ) 将x m l 文档存储到关系数据库的特定字段中，如数据库中的b l o b 的字 段中。 在移动数据库中我们可以使用两种方式来使用x m l 数据库：一种是通过接口 和组件将x m l 转换为关系数据库，从而借助关系数据库的缓存技术来实现，但是 这样额外增加了系统的开销，降低了缓存的性能，不能充分发挥x m l 独有的优势； 另一种是使用纯x m l 数据库技术，通过x m l 本身的操纵来实现热点数据的缓存， 目前对基于x m l 缓存技术的研究已经很多，但是较少考虑基于x m l 的移动环境 中的缓存技术。本文将在以下几个方面做一些深入的探讨：基于x m l 的移动数据 库中的缓存的组织和存储、缓存的替换策略以及移动客户端的语义缓存及视图，力 求设计出一种从服务器端到移动客户端基于x m l 的移动环境的缓存体系结构，介 绍了基于x m l 的动态广播失效报告策略来提高移动数据库缓存的效率，并对x m l 的缓存技术进行了进一步的优化。该项目的研究无论在理论上还是在应用方面都有 显著的意义。 1 3 本文所做工作 随着对纯x m l 数据库技术研究的不断深入，x m l 数据库缓存技术正在逐渐 受到了越来越多的研究人员的关注。通过对访问频率高的数据进行缓存，可以有效 地提高用户查询的处理效率和提高查询的响应速度。【lo 】更重要的是，移动环境中网 络数据传输代价是衡量x m l 移动数据库性能的一个非常重要的性能指标，所以对 x m l 数据查询响应时间的要求就显得更加重要。在这种情形下，合理高效地缓存 数据，一方面可以大规模地提高移动数据库的响应速度，减少用户的等待时间，从 而提高网络传输的性能；另一方面，缓存数据也可以有效地减少网络传输中不必要 的负载。 移动环境的网络具有不稳定性，它所特有的频繁断接性、移动性、网络通信的 非对称性、移动主机处理能力的有限性等特点，使得移动环境下的缓存技术不同于 硕士学位论文 m a s t e r st h e s i s 传统的基于页面的缓存技术。在移动环境中，缓存失效报告可以有效地解决缓存服 务器与客户端缓存一致性的问题。针对x m l 数据库的特点对传统的失效报告算法 需要做进一步的优化。对于客户端缓存技术出现了以根据查询表达式语义之间的相 关性进行组织的语义缓存技术。 为了使x m l 数据库能够更好地在移动环境中高效地访问和传输，并确保数据 的一致性。本文在深入研究移动数据库的缓存技术的基础上，针对x m l 移动数据 库的特点，本文作了以下工作： ( 1 ) 服务器与移动客户端缓存的一致性：为了使使移动客户端与服务器保持 数据一致性，介绍了一种新的x m l 缓存失效报告算法，并介绍了在此基础上对该 算法进行改进的算法。 ( 2 ) 移动客户端缓存技术：为了使客户端能够高效地组织本地缓存，本文给 出了缓存存储组织的结构图。针对客户端x m l 的语义缓存，本文提出了一种改进 的x m l 移动数据库的一种语义缓存体系结构模型，并在此基础上分别阐述了基于 x p a t h 表达式的语义缓存技术。 ( 3 ) 语义匹配模型及查询裁剪技术：针对x m l 查询语句的特点，为了提高移 动客户端的查询响应速度，减少对服务器不必要的查询请求，本文分析探讨了查询 语句的五种匹配模型，移动客户端的语义缓存技术以及“查询裁剪 和“剩余查询 技术。 ( 4 ) 提出了一种新的视图更新算法x s i u ：该算法在p i u 算法的基础上，引 入x m l 结构的结点的度和数据元的长度对p i u 算法进行了改进，得到了一种新的 基于x m l 结构的x s i u 算法。该算法动态地建立需要更新结点的新鲜度，并按照 新鲜度的级别进行排队，从而保证新鲜度级别高的能够优先传输给移动计算机。通 过模拟仿真实验证明，这种算法在带宽急剧下降时，能够有效地提高移动环境中视 图的增量更新性能。 1 4 论文的组织 本文共分为五章，其结构安排如下： 第一章是绪论。本章介绍了本文的研究背景，及与本文相关的国内外技术与研 究情况，最后简要的介绍了本文所做的工作及主要研究的成果。 第二章是移动数据库中基于x m l 的缓存组织的方法。本章对x m l 缓存的相 关研究做了介绍，给出了x m l 缓存的移动数据库中的粒度，提出了移动环境中x m l 缓存的组织及存储结构图。然后介绍了移动环境中缓存性能评价的一般指标。 6 硕士学位论文 m a s t e r st h e s i s 第三章是基于x m l 数据库缓存的策略，本章是本论文的工作重点之一。详细 地介绍了移动数据库中缓存技术的两个主要方面的问题： ( 1 ) 服务器与移动主机缓存一致性维护的问题 ( 2 ) 客户端缓存技术 针对一致性问题本文详细介绍了缓存失效报告模型，及基于x m l 的缓存失效 报告算法x i r ，并介绍了在此基础上对该算法进行改进的算法，改进的算法主要思 想是对需要广播的缓存失效报告进行分类，并针对不同类型的失效报告使用不同的 广播区间长度来广播失效报告。针对客户端缓存技术，本章介绍了基于x m l 的语 义缓存技术的五种匹配模型，并介绍了查询的裁剪技术以及“探测查询”和“剩余 查询”。 第四章是基于x m l 缓存的视图增量更新算法。本章也是本论文的工作重点之 一，在本章中提出了一种视图增量更新算法x s i u ，该算法是基于x m l 文档结构增 量视图更新算法的缩写。该算法在p i u 算法的基础上引入了x m l 文档的结点的长 度和结点的度进行修正，并通过模拟实验体现了该算法的优越性能。 第五章是结论。本章给出了本论文的有关结论及未来工作的重点。 7 硕士学位论文 m a s t e r st h e s i s 第2 章移动数据库中基于x m l 的缓存组织的方法 2 1x m l 缓存综述 缓存技术可以有效提高移动数据库的性能。通过客户机的缓存处理，如果移动 客户端的缓存数据可以满足用户数据访问请求时，就不需要通过向移动数据库服务 器发送访问请求，这样减少了网络带宽的需求，避免了网络的传输延迟，同时也减 少了服务器的查询负载。 缓存技术是加速查询处理的重要手段之一。研究人员已经对x m l 缓存技术做 了很多研究。文献 1 3 】中提出了一种新的缓存技术u d c a c h e ，该缓存系统采用前 缀同构和非前缀同构的方法来回答查询。 目前在移动数据库客户端对x m l 缓存技术的研究主要集中在语义研究方面， 而针对x m l 语义缓存技术的研究又主要集中在以下几个方面：【1 2 j 1 查询的语言：x m l 查询中使用得最多的两种查询语言为x q u e r y 和x p a t h ， 在x q u e r y 查询语句中，查询表达式不仅具有语义而且具有严格的执行顺序。而 x p a t h 查询表达式本身就是有效的x q u e r y 查询表达式。在目前的研究中，既有采 用矩阵对查询表达式进行匹配的算法，也有针对x p a t h 查询表达式的字符串匹配算 法。 2 缓存的组织：缓存的组织主要包括缓存的粒度以及缓存的存储。对于不同 的缓存的粒度所采用的算法不同，如不同粒度需要采取不同的存储方法。考虑到移 动环境的特殊性，传统的页面粒度过大，不太适合于移动环境，需要寻求比页面更 小的适合于x m l 特有结构的缓存粒度。 3 模式集：所谓模式集是指通过对现有缓存中已有查询结果集进行重新组合 来回答用户的查询请求，这里的模式可以理解为x p a t h 查询表达式。 2 2 基于x m l 缓存的粒度 缓存的机制取决于缓存的粒度、缓存的一致性维护以及缓存的替换策略。传统 的缓存需要一个比较稳定的网络，较高的带宽。但在移动环境中这些要求均不能满 足，由于能源和响应时间以及无线网络的低带宽，所以传统的基于页面的缓存粒度 8 ：一， 硕士学位论文 m a s t e r sf r h e s i s 不太适用于移动数据库。以页面为粒度的缓存，在无线网络环境中传输需要较长的 时间，这一方面将会导致较低的响应时间，另一方面也会导致较高的能源耗费。显 然，这在无线移动环境中的客户端是不太合理的，因此需要寻求比页面更小的缓存 粒度f i l s l 关系数据库中通常以一条记录为一个单位，每个记录又由多个属性组成。在基 于关系的移动数据库中可以采用一条记录或是某一组属性作为缓存的粒度。在基于 x m l 的移动数据库中无法采用基于关系数据库的缓存粒度，但是可以采用相关联 的部分结点作为缓存的粒度，如将某个结点及其子结点作为缓存的粒度。在下图中， 可以选择以h a r d w a r e 为子树的所有结点。通过图2 1 中可以发现，如果h a r d w a r e 包含子结点很多，这样也会导致缓存粒度过大。事实上，子树下面的子结点并不是 每个结点信息都是用户关心的内容，通过选择那些用户关心的部分子结点作为缓存 的一部分，这样也可以大大减小缓存的粒度。 c o m p a n y 图2 - 1x m l 文档树型结构 2 3 基于x m l 的缓存的存储 在移动环境下可以使用数据本地化或数据预取技术来提高移动主机的缓存效 率。【】5 】通常有以下几种情况会导致用户所访问的数据无法在移动客户端命中缓存数 据：( 1 ) 当数据第一次被读入的时候，因为缓存中没有数据，需要从服务器端读入 数据至缓存中；( 2 ) 当缓存空间不够时会将部分已经缓存的数据移出，这时被移出 的缓存数据可能导致缓存命中失败。 同其它的数据库一样，x m l 的主要操作也包含数据的定位、提取、插入、删 除和更新。其中在x m l 中使用x p a t h 对数据的提取操作最为常用，它是x m l 数 据库有别于其它类型数据库的特征之一。当对结点数据进行读取时，需要通过路径 9 硕士学位论文 m a s t e r st h e s i s 遍历树的相关结点，这种对文档树的遍历通常是很耗时的，在基于x m l 的缓存体 系中，主要采用语义缓存技术。为了提高缓存中大量的x p a t h 的查找速度，在缓存 中通过创建驻留缓存的索引，可以提高x p a t h 的检索速度。在索引中包含原文档的 树型结构，因此可以到达任意方向的任意结点。为了缩小索件文件的大小可以采用 两种策略：( 1 ) 将x m l 文档的标记符号和元素的值以及其它结点信息采用对应的 物理地址进行对应的存储；( 2 ) 采用一定的压缩算法对索引结构进行压缩存储。 数据预取可以大大提高缓存的命中率。它可以通过软件与硬件的方法来实现， 软件预取在很多系统中都使用到，许多程序设计语言系统通过预取指令来实现。如 c + + 编译器就提供预取函数。在移动数据库中，也可以借用这种技术。由于x m l 数据的组织采用树型结构，其结点之间具有一定的“父子”关系，因此当涉及到对某 一个结点的信息进行读取的时候，可采用一定的算法将下一步最有可能用到的相关 结点数据一并读入缓存，这种方法关键在于如何确定哪些结点数据应该被读入。我 们可以采用一些启发性预测规则来对一下步最有可能被读取的数据进行预测，将这 部分数据一并提前读入缓存。为了充分利用移动数据库的网络带宽，在预读这部分 数据时可以在整个网络状态比较空闲时启动，这样一方面可以充分利用网络的带 宽，从而使整个网络带宽不会由于移动结点数据的预读而产生通信带宽负载过重， 影响整体的性能。另一方面也可以极大的提高缓存的命中率。 图2 - 2 移动客户端c a c h e 存储内容示意图 通过以上分析，在缓存中除了存储访问的热点数据以及用户的查询语句外，对 f 数据量比较大的缓存，为了提高响应速度，还应在内在中驻留适当的索引数据结 构，这样可以极大提高缓存的性能。其客户端缓存模型如图2 2 所示。 i o 硕士学位论文 m a sr i e r st h e s i s 2 4 缓存性能的评价 缓存策略的性能通常可以用以下三个方面的指标来进行度量【1 4 】【1 6 1 q 2 2 ： ( 1 ) 平均缓存命中率：所有的移动客户端通过获取本地缓存数据库对象就能 满足用户访问的百分比； ( 2 ) 平均响应时间：所有移动客户端从一个查询请求的提交到查询请求的结 果生成所需时间的均值，它包括从本地有效的缓存提取信息的时间以及从服务器返 回的远程结果所用时间； ( 3 ) 错误率：所有客户端读到错误数据的百分比。 硕士学位论文 m a s t e r st h e s i s 第3 章基于x m l 的移动数据库缓存策略 3 1 缓存策略 在传统的c s 环境中通常使用基于页面的缓存机制，但基于页面的缓存机制需 要页内的数据项具有很高的本地化程度。实际上，移动客户端的数据需求跟点对点 的环境具有很大的不同，由于移动客户端的能源有限，这种基于页面的缓存机制在 低带宽不稳定的无线通道上进行传输需要很高的传输成本，因此需要采用更小粒度 的缓存。【1 4 】 当数据库服务器中的数据更新后，缓存中的数据就会失效。因此需要提供一种 适合移动数据库环境中保持服务器与各个客户端数据一致的策略。传统的缓存策略 需要服务器通知所有相关的客户端无论什么时候这些数据被更新时，但由于每个移 动客户端的断连具有频繁性和随意性，不太容易做到让服务器去跟踪每个失效的缓 存副本。因此需要一个更适合移动无线环境的缓存一致性维护策略。 移动数据库中缓存技术的使用可以很大程度上减轻网络传输的负载，减少移动 主机的能源消耗。由于在移动客户端缓存了部分内容，所以如果请求的数据能够在 本地缓存中得到，移动客户端就不再需要向服务器提交数据请求，但j 下是因为这样， 如果服务器端的数据发生了更新，移动客户端如果不能及时更新对应的缓存内容， 这将使得移动客户端从本地缓存中读到“脏”数据。为了避免这种情况出现，需要 保持事务的a c i d 特性，即原子性、一致性、隔离性和持久性。为了确保各个移动 主机与服务器数据的同步，人们提出了缓存的一致性维护方法。当服务器端的数据 得到更新后，服务器端通过向移动主机周期性地广播已经更新的数据对象或由移动 客户端定时向服务器查询更新的对象，使移动客户端能够保持本地缓存和服务器端 数据对象的一致。其中，最为著名的是缓存失效报告策略，本章第二小节将对此做 深入分析。另外，在客户端为了提高缓存的命中率和缩短响应时间，需要采用一定 的策略对缓存进行匹配，本章第三小节将对此进行阐述。 1 2 硕士学位论文 m a s t e r st h e s i s 3 2 缓存失效报告策略 缓存失效策略在是在移动数据库普遍采用的缓存方案，即服务器定期广播缓存 失效报告，该报告中包含了最近被更新的对象。根据报告内容，移动主机可使缓中 被更新对象失效，以保证缓存的有效性。 在典型的c l i e n t s e r v e r 系统中，客户端缓存的维护有两种方法： 1 服务器端的主动发送：s e r v e r 端发送失效报告给c l i e n t 端。当服务器的数据 被更新后，直接将被更新的内容发送给所有的客户端。 2 客户端的主动请求：c l i e n t 端通过定期向服务发送验证请求，来验证c l i e n t 缓存的有效性。 由于移动主机的频繁断接、有限的网络带宽以及电源能力的限制，使得上述方 法不适合应用于移动计算环境。在断连期间移动主机无法接收缓存失效信息，当其 重新获得连接机会后，又无法判断缓存中的哪部分内容有效，在这种情况只能放弃 整个缓存内容，这使得缓存失去了应有的作用。 在传统的移动数据库系统中，按服务器端是否需要存储移动客户端缓存的状态 进行分类，可以分为“基于状态的”和“无状态的”两种技术。所谓“基于状态的”就是 指服务了解移动客户端缓存中的内容，当数据库被更新时，服务器发送失效报告给 移动客户端。所谓“无状态的”是指服务器无需了解客户端缓存的状态。它的原理是 服务器周期性地广播被更新的对象，移动客户机通过监听报告内容来更新其缓存内 容。由于基于状态的缓存技术实现起来较为复杂，所以一般采用无状态的缓存失效 策略。而无状态的缓存失效策略又可分为同步和异步两种方式。由于同步方式能更 好地适应移动计算机的需要，所以通常使用无状态的同步缓存失效策略。 上述缓存失效策略已有很多研究，但在x m l 移动数据库中上述策略不完全适 用于x m l 数据库的特点，最近，国内外很多研究人员提出了基于x m l 移动数据 库的一些缓存策略，使其能更好地适用于x m l 数据库的结构。在文献 2 3 1 q b 使用实 体化视图来响应x m l 的查询请求，但是没有考虑到无线网络环境的低带宽这一特 点，根据这一特点，在本文的第四章提出了一种新的基于x m l 的视图增量更新算 法。在文献 2 4 中提出了失效报告的策略但是没有针对x m l 特有的结构进行设计优 化的算法。 3 2 1 缓存失效报告模型 缓存失效报告【2 5 h 2 8 1 的算法是一个基于时间戳的算法。服务器生成一个缓存失 硕士学位论文 m a s t e r st h e s i s 效报告并采用周期华记( f 是一个时间系数，是一个失效报告的广播区间) 对客 户端进行广播。一个失效报告就是刚过去的形秒数据项被改变的一个历史记录 犯 一功。当移动主机接收到失效报告后，每一个在缓存中的数据项d ；的时间戳f ， 与失效报告中的时间戳，r 进行比较，如果f ，f i ，r ，则数据项盔从缓存中移去，表 示此数据项在移动主机的缓存中已经过期。 移动主机记录了个查询列表q f = ，i 是在时间间隔【乃，z + 。】的查询) 。当移动 主机收到一个失效报告后，首先对f 与f 尹进行比较，如果f ，f ，则说明移动 缓存的数据项是有效的，并将缓存中的内容直接返回给查询j ，同时将该查询j 从查 询列表中移除。余下的查询采取上面相同的办法进行操作。 巧2 想雹毫 缓存可用响应 并命中缓存 “” ”一 图3 一l 缓存失效报告模型 缓存报告模型如图3 1 所示，在上述模型中，i r 表示缓存失效报告( i n v a l i d a t i o n r e p o r t ) 。当移动主机在z 与z + 之间的时刻接收到一个查询请求时，如果在本地缓 存中存在所需要访问的数据时，此时移动主机还必须等到下一个缓存失效报告的到 来。如果在本地缓存中无法获得查询所需要的数据时，则移动主机需要向服务器发 送一个查询请求。当在正+ 时刻接收到缓存失效报告后，移动主机查看缓存中的数 据是否有效，如果有效，则查询q u e r y 即可得到服务。但如果无效的话则移动主机 需要向服务器发送一个查询请求，该查询请求则需要到z 。时刻的缓存报告到来时 得到响应。 下面分别介绍两种不同的基于x m l 移动数据库实现缓存一致性的算法，第一 种算法x i r 是上述缓存失效报告模型在x m l 移动数据库上应用的改进。第二种算 法是在第一种算法基础上的改进。 1 4 3 2 2 基于x m l 的缓存失效报告算诸x i r j a e - h o c h o i 等人提出了基于x m l 的缓存失效报告算法，简写为x i r 算= ；去口w 其具体内容为： 图3 - 2 移动主机缓存中的x m l 片段瞄1 如图3 - 2 所示，定义x m l 文档的结构如下。 定义1 ：一个x m l 文档是一个四元组d = ( 地如五柚，其中 0 = u 嵋是一个代表结点和属