（计算机软件与理论专业论文）基于ajax技术的svg视图增量维护框架的研究.pdf

摘要 摘要 随着互联网逐步普及，万维网( w o r l dw i d ew e b ，简称w e b ) 应用成为基 于互联网向用户提供信息和服务主要方式。用户对于w e b 应用中图像服务的需 求正在不断扩大。可伸缩矢量图( s c a l a b l ev e c t o rg r a p h i c s ，简称s v g ) 凭借 其强大的绘图功能和符合x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 格式等特点， 在多媒体w e b 应用软件中得到了广泛的应用，但由于受到了网络带宽的限制， 容易造成w e b 应用程序响应缓慢，用户长时间等待，降低了系统的可用性。 在地理信息服务等w e b 应用系统开发中经常对s v g 数据进行副本缓存，引 用数据库中物化视图的方法提高查询效率，以减少数据传输的需求。但是缓存的 副本数据需要保持与后台数据源的数据一致，通常的保持一致性的方法是当后台 数据源发生变更后，进行重新查询。重新查询不仅需要重复计算，而且在数据传 输过程中同样会受到网络带宽的限制。 为了减少因后台数据变化引起的再次s v g 数据查询，本文发展了一种增量 维护框架对已经缓存的s v g 视图进行一致性维护，以保证视图数据的正确性和 时效性；并且针对基于w m s 服务的s v g 物化视图设计并实现了增量更新系统； 同时引入a j a x 技术以异步通信的方式支持s v g 物化视图的使用。本文为解决 w e b 环境下大数据量s v g 应用问题和构建s v g 视图增量维护软件系统上提供 了技术积累，并为二次开发人员使用增量维护系统提供了良好的应用接口，而且 系统适合于满足o g c ( o p e ng e o s p a t i a lc o n s o r t i u m ) 的s i m p l ef e a t u r ea c c e s s 标准的以范式表方式组织空间数据的数据源。 关键词s v g ；视图；增量维护；a j a x 北京t 业大学丁学硕士学位论文 a b s t r a c t w i t ht h ei n c r e a s i n gu s eo fi n t e r n e t ，w e ba p p l i c a t i o nh a sb e c o m et h e t r e n dt op r o v i d ei n f o r m a t i o na n ds e r v i c e sf o ru s e rb a s e do ni n t e r n e t a g r e a tm a n yr e q u e s t sh a sr i s e ni nt h ef i e l d so fg r a p h i c a ls e r v i c e si nw e b a p p l i c a t i o n s s c a l a b l ev e c t o rg r a p h i c sw a sw i d e l yu s e di nm u l t i m e d i a s o f t w a r eo nw e bd u et oi t ss t r o n ga b i l i t yo fr e n d i n gp a i n t i n ga n dx m l f o r m a t t e df e a t u r e u n f o r t u n a t e l y ，t h e1 i m i to fb a n d w i d t ho b s t r u c t st h e i n c r e a s i n gu s eo fs v g a sar e s u l t ，i tc a u s e sl a t e n c yo fr e a c t i o no fw e b a p p li c a ti o na n dl o n gw a i tt ou s e r g e o g r a p h i ci n f o r m a ti o ns y s t e mu s u a ll yc a c h es v gd a t at oi m p r o v et h e p e r f o r m a n c ea n d d e c r e a s et h en e e d so fd a t at r a n s f e r t h i si d e ai sd e r i v e d f r o md a t a b a s ef i e l d b u tc o n s i s t e n c eb e t w e e nc a c h e dd a t aa n dd a t as o u r c e i sr e q u i r e d n o r m a l l y ，r e c o m p u t ei se m p l o y e dw h e ns o m ec h a n g e so c c u ri n d a t as o u r c et ok e e pt h ec a c h e dd a t ac l e a n b u ti tn e e d sn o to n l yc o m p u t i n g r e s o u r c e s 。b u ta ls oe n c o u n t e r st h e1i m ito fb a n d w i d t h i no r d e rt oa v o i dr e 。t r a n s f e rs v gd a t aa ss o m ec h a n g e sh a st a k e np l a c e i nd a t as o u r c e ，t h ep a p e rp r o p o s e sa ni n c r e m e n t a lf r a m e w o r kt om a i n t a i n t h ec a c h e dd a t af o ri t sc o n s i s t e n c ya n di nt i m e b a s e do ns v gv i e ww h i c h iss u p p o r t e db yw m s ，t h ep a p e ra l s od e s i g n e da n dd e v e l o p e da ni n c r e m e n t a l m a i n t e n a n c es y s t e m m e a n w h il ea j a xh a sb e e nu s e dt os u p p o r tt h eu s a g eo f s v gi nt h es y s t e mi nw h i c hc l i e n ta n ds e r v e rc o m m u n i c a r ea s y n c h r o n o u s l y t h ec o n t r i b u t i o no ft h i sp a p e ri st oa c c u m u l a t es o m ee x p e r i e n c e sb o t hi n a p p l y i n gl a r g e s c a l e s v go nw e b a n d c o n s t r u c t i o no fi n c r e m e n t a l m a i n t e n a n c es y s t e mf o rs v g b e s i d e s ，t h ep a p e rp r o v i d e sc l e a ra p i sf o r d e v e l o p e rt os e tu p t h e i ro w ns o f t w a r e b y u sin gt h ein c r e m e n t a l m a i n t e n a n c es y s t e m a tl a s t ，t h ei n c r e m e n t a lm a i n t e n a n c es y s t e mi s s u i t a b l ef o rt h ed a t as o u r c ew h i c hi m p l e m e n t st h es f a ( s i m p l ef e a t u r e a c c e s s ) s p e c i f i c a t i o na u t h o r i z e db yo g c k e y w o r d ss v g ：v i e w ：i n c r e m e n t a lm a i n t e n a n c e ；a j a x 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：? 望务拳日期：印耳鲫三日 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：塑越 导师签名： 第1 章绪论 1 1 课题背景 第1 章绪论 近年来，随着互联网逐步普及，它已经成为人们获取信息的主要平台之一。 万维网( w o r l dw i d ew e b ，简称w e b ) 应用是基于互联网向用户提供信息和服 务主要方式。从浏览静态页面到创建具有交互功能的动态页面，用户对于w e b 应用的要求逐渐提高，其中对图像服务的需求正在不断扩大。如地图查询、网络 相册等图像服务越来越多地出现在w e b 应用中，如g o o g l em a p 1 1 ，g 0 2 m a p 2 l 网站等，其中主流的数据格式还是传统的栅格图片格式。 栅格图片以点阵的方式保存每个像素的信息，所以它特别适合于展示照片。 但是在工程设计领域，栅格图片因其放缩可能产生的失真而不能得到广泛应用。 另外修改栅格图片需要对大量像素信息进行处理，造成了其难于构建交互式的应 用。这些问题都为矢量图像的应用带来了机遇。矢量图像的特点是用绘制语言描 述图像，再由解析器绘制。由于图像的表示是描述式的，所以矢量图像具有缩放 不失真、精度高的优势。因此矢量图像非常适用于w e b 应用中提供的一些服务， 如地理信息服务。 可伸缩矢量图像叫c a l a b l ev e c t o rg r a p h i c s ，简称s v g d l ，是一种用x i v i l 表示二维图像的语言。矢量图是通过基本的几何图形( 线、曲面等) 描述图像， 不同于栅格图片只保存点阵信息。因此，矢量图具有很多特性，比如文件的可读 性强，在缩放时候不会产生失真现象等。与w e b 环境下的其它图像格式相比，它 具备三个突出优势：描述内容丰富、动态交互功能和标准化。 首先，s v g 能够描述三种图形对象，包括矢量图形、栅格图片和文本。这些 对象可以被分组、定制显示的样式、变换坐标系以及任意的组合和嵌套。另外， s v g 善于在图形基础上添加多种的特征，比如按某种路径显示图像、实现各种过 滤效果等等。因此，s v g 适合创建丰富的显示内容- o 另外，s v g 支持动态交互。s v g 内置的动画标签能够实现基本图形的动态显 示效果；而且通过嵌入脚本语言，s v g 可以响应触发的事件，如鼠标移动，与用 户进行互动。脚本语言通过文档对象模型( d o c u m e n to b j e c tm o d e l ，简称d o m h l ， 它定义了表示h t m l 或x m l 等文档格式的标准对象模型) 接口，能够操作s v g 中 所有元素节点，从而在各种触发事件中，能动态地修改s v g ，构造丰富的显示效 果，实现强大的交互功能。 最后，s v g 的标准化特点也是其适于w e b 应用开发的重要原因。w e b 是_ 个 北京= i ：业大学工学硕士学位论文 复杂的异构信息平台，为了解决不同w e b 应用间的数据交换问题，需要一种统一 的数据格式。目前x m l 晦1 已经逐渐被人们接受，成为w e b 环境中通用的数据交换 格式。因此，s v g 同样具备了格式通用的特点，并且已经成为w 3 c ( w o r l dw i d ew e b c o n s o r t i u m 1 ，即万维网协会，该组织致力于提供w e b 开发的系列标准) 的推荐 标准。在w 3 c 的影响下，s v g 已经和其它众多的w e b 开发标准兼容，如d o m ，x h t m l ， 使得开发人员可以基于众多标准开发出更加通用的w e b 应用程序。 基于上述三点，s v g 在w e b 应用开发上逐渐取得了开发人员和用户的认可， 并凭借其先天优势在地理信息应用的开发中越发受到人们的关注。w 3 c 推荐的地 图数据w e b 服务标准叫e b 地图服务( w e bm a ps e r v i c e ) ，简称w m s 口1 ，也将 s v g 列为需要支持的数据格式之一。 一系列围绕s v g 应用的研究也开展起来。例如在c a d ( c o m p u t e r a i d e d d e s i g n ) 领域，在高清图像应用领域，如a d o b e 公司的i l l u s t r a t o r 软件中，在 描述特殊符号领域，如利用图形表示数学标记语言( m a t h e m a t i c a lm a r k u p l a n g u a g e ，简称m t a h m l 随1 ) 等方面都得到了充分研究。另外，一些研究人员关注 如何在w e b 环境中提高s v g 应用程序的性能，比如利用视图技术避免重复查询 s v g 数据，提高响应速度。本文也是从这个角度对s v g 应用进行了研究。 1 2 研究目的与意义 研究如何在w e b 环境中应用s v g 逐渐成为了热点，其中的突出问题是如何解 决图像包含的庞大数据量与有限的网络带宽之间的矛盾。w e b 应用程序性能的一 个重要考量标准是响应速度，数据量增大必然增加网络传输负担，造成用户长时 间等待，降低应用程序的可用性。所以解决这对矛盾变成了研究s v g 在w e b 环境 中广泛应用的关键问题。 在处理大量数据的问题上，数据库领域经过多年的研究已经积累了很多的经 验。借鉴数据库领域中的物化视图概念，可以减少数据传输的负担。物化视图的 概念首先在数据库领域提出。视图是从若干数据库基本表中根据某个查询操作取 得的结果表。将这些结果存储在二次存储的过程称作物化。在重复查询时，可以 立即从物化视图获得结果，比重新查询要快，不但节省了计算资源，而且缩短了 系统响应时间。因此在实际的大规模数据库应用中，物化视图是提高系统性能的 常用技术。 物化视图技术同样可以用来提高w e b 应用的性能。w e b 环境中最常见的体系 结构是“客户端服务器”，简称c s 结构。存储在客户端的数据实际上就可以看 作是一种物化视图，而且客户一些的查询操作可以直接从这部分缓存的视图中获 得，避免了与服务器通过网络进行通信，从而避免了海量的图像数据传输过多占 2 第1 章绪论 鼍曼曼皇曼曼蔓皇曼舅曼曼曼曼曼!曼曼曼曼毫曼曼曼曼鼍,i i i i ! 曼皇曼曼曼曼曼蔓皇曼舅曼鼍曼曼蔓曼! 曼曼曼曼曼曼曼! 曼皇 用网络资源，影响w e b 应用程序的性能。缓存在客户端的s v g 数据同样可以看作 服务器端数据的物化视图。 但是，物化视图的一个关键问题是如何保持与数据库原始数据致。由于数 据库经常会进行数据更新，那么从原始数据生成的视图必须进行一致性维护，否 则客户端可能会使用的过期、错误的“脏数据 。进行物化视图一致性维护最简 单的方法是重新查询。但它会增加网络数据传输的负担，尤其在w e b 环境下的地 理信息服务这样需要海量数据的应用中，更加不适合经常使用。 另一种进行一致性维护的方法称为增量更新。它的特点是只更新视图中已经 过时的数据，保持其它数据不变。在视图数据变化较小时，增量更新是十分有效 的，因为需要通过网络传输的数据与重新查询的结果相比，只是很小的部分，节 省了带宽，也提高了应用程序响应时间。而且经验表明，多数的数据库更新只会 影响到很小一部分物化视图数据。 本文发展了一种增量维护框架对已经缓存的s v g 视图进行一致性维护，以保 证视图数据的正确性和时效性，并且针对基于w m s 服务作为数据源的s v g 物化视 图，设计并实现了增量更新系统。同时引入a j a x 叫( 一种新的w e b 开发技术或方 法) 技术以异步通信的方式支持s v g 视图增量系统的使用。本文的研究目的在于 解决w e b 环境下s v g 大规模应用遇到的网络延时问题，给二次开发人员提供一系 列s v 6 视图增量维护框架的应用接口，并为终端用户构建一个基于s v g 的w e b 地 图应用系统。 本文的研究意义在于，为解决w e b 环境下大数据量s v g 应用问题和构建s v g 视图增量维护软件系统上提供了技术积累；并且设计实现系统时将各个功能模块 化，为二次开发人员构建其它应用系统提供了良好的应用接口；作为一个实际的 应用系统，它适合于满足o g c n0 1 的s f a ( s i m p l ef e a t u r eh c c e s s ) 标准的数据 库。s f a 允许两种方式组织数据，它有两种数据储存方式，一种是在表中的几何 数据属性中存储空问坐标数据，另一种是存储空间对像的二进制数据。本文中称 前一种存储方式为“范式表”，本系统适合于使用范式表方式组织空间数据的数 据库。 1 3 课题来源 本研究得到北京市自然科学基金( 项目编号：4 0 5 2 0 0 6 ) 的支持。 1 4 本文工作 本文主要研究了s v 6 视图增量更新的问题。具体工作内容如下： 1 提出了一种针对s v g 视图的增量维护框架 3 北京t 业大学工学坝士学位论文 2 设计、实现了基于w m s 服务作为数据源的s v g 视图增量更新系统 3 引入a j a x 技术，以异步通信的方式支持s v g 视图增量系统的使用 4 扩展了基于w m s 的数据源，增强了w m s 数据源功能，提高了系统的可用 性 本文的内容组织如下： 第1 章绪论。主要介绍课题的背景、来源，s v g 视图增量维护研究目的和 意义，以及本文的主要工作内容。 第2 章物化视图增量维护方法。说明了物化视图增量维护的概念，列举了 在这一研究领域内其它工作者取得的科研成果，并对它们进行了分类比较。同时 指明本文采用程序变换的方法进行视图的增量维护，举例说明其基本原理。通过 与其它增量更新方法比较，论述了该方法适合于s v g 视图增量维护系统的原因。 第3 章增量维护系统设计。首先提出了增量维护框架必需的功能模块，然 后详细说明了在设计和实现s v g 视图增量维护软件系统过程中，如何构建各个模 块。从用户接口、增量维护管理器和数据源三个方面说明了各个部分的功能、实 现方法和交互过程。并引出了数据源需要扩展和改造的问题。这些问题将在第6 章中进行说明。 第4 章利用a j a x 实现异步通信。从用户的角度，说明了s v g 视图增量维护 系统应该引入异步机制为用户提供更好的使用感受。详细介绍了a j a x 的由来和 技术特征。通过与传统w e b 开发方法的比较，突出了a j a x 在提供良好用户感受 和系统性能上的优势。并深入分析了a j a x 的工作原理。最后给出了系统中应用 a j a x 的实际方案。 第5 章w m s 数据源的扩展和改造。从第4 章的软件结构上看，以w m s 系统 为核心的数据源部分在本文中称为“w m s 数据源”。为了适应s v g 视图增量维护 系统的需求，对w m s 数据源应该进行必要的改造，如添加数据过滤器和解决坐标 变换问题。另外，为了增加系统的可用性，需要增强k s 数据源功能，通过添加 辅助数据和定义视图生成结构，为s v g 应用提供更丰富的操作。 第6 章性能测试。以实验的方式记录s v g 视图重新计算和增量维护所耗费 的时间，并进行比较。从测试结果得到结论，增量维护比重新计算所耗费的维护 时间少很多，尤其在应用大数据量的s v g 视图时，性能提升效果更加明显。 最后在结论部分对本文的工作进行了整体总结，同时再次指出工作的意义， 并分析了进一步研究的方向。 4 第2 章物化视图增量维护方法 , i i ie eim_ -=,i i i 曼! 曼曼 第2 章物化视图增量维护方法 2 1 物化视图增量维护的概念 在数据库领域中，视图定义为从数据库的基本表中通过某种计算取得结果 表。视图也可以存储在数据库中以便直接从中读取数据，这样的视图叫做物化视 图。物化视图相当于将某些数据缓存起来以便快速访问，避免了重复计算带来的 资源负担。 物化视图是从基本表中获得，因此要保证它与基本表的数据一致，否则其中 的数据可能过期，通常称作“脏数据”。为了避免产生“脏数据 而进行的工作 叫做视图维护。 大多数情况下，通过重新计算来维护视图数据的一致性是十分浪费的，因为 视图中的变化数据是只小部分，不必要重新计算整个视图。所以，只更新视图中 变化部分的方法称为“增量维护”。物化视图的概念并不局限于数据库领域，如 本文系统中缓存的s v g 数据，也可以看作物化视图。 2 2 相关研究情况 物化视图的增量更新并不是一项新的研究课题，早在数据库系统发展时期， 已经发表了许多针对结构化数据视图增量更新的论文，但是专门讨论s v g 视图增 量更新的文献还较少。所以本文的相关工作部分主要比较应用于x m l 视图的增量 更新维护法，因为s v g 本身就是x m l 的一种实现。 研究人员很早就注意到物化视图带来的好处，因此对于较早出现的关系数据 模型，已经有论文 1 2 对关系模型的视图维护做了阐述。并在论文 1 3 ，1 4 中给 出了其增量维护的方法。然而随着x m i 。被广泛认同，半结构化数据的视图维护成 为研究的热点。与关系数据模型不同，x m l 数据模型符合有序、嵌套的层次结构， 这些特点也决定了x m l 视图维护的特殊性。 在论文 1 5 中提出一种增量维护半结构化数据的算法。该算法基于图的数据 模型o e m ( o b j e c te x c h a n g em o d e l ) 和查询语言l o r e l 。但是这种方法限制了一 些查询语言的特性，如排除了“非”操作；并且局限于单调视图维护，即对数据 源的删除( 插入) 操作只会引起视图的删除( 插入) 。其限制的目的就是为了使 更新操作简化。同时，它引入了辅助数据来检查更新与视图之间的关联性，但辅 助数据的大小并不取决于视图。 ，论文 1 6 将x m l 视图存储在r d b m s ( r e l a t i o n a ld a t a b a s em a n a g e m e n t 5 北京t 业大学工学硕士学位论文 s y s t e m ) 或o r d b m s ( r e l a t i o n a ld a t a b a s em a n a g e m e n ts y s t e m ) 中，利用d b m s 的更新日志来缓冲更新操作，提出特定算法来分析需要更新的相关视图，再生成 相应的操作，完成一致性维护。 论文 1 7 使用代数方法增量维护x q u e r y 视图。x q u e r y 是w 3 c 推荐的标准x m l 查询语言，所谓x o u e r y 视图是指由x q u e r y 语句定义的查询结果。它将数据源的 更新变化转换成若干更新原语的执行，这些原语是基于x m l 代数树( x m la l g e b r a t r e e ，简称x a t ) 的一些操作。x a t 是一种表示表示x q u e r y 查询的数据结构，用 “x a t 表 实现。一旦数据源发生更新变化，在x a t 上自底而上地执行对应的更 新原语，直到根节点，最终完成对x m l 视图的增量更新。虽然这种方法充分利用 到了x q u e r y 语言的强大查询功能，但代价是必须存储查询过程中的中间结果作 为辅助数据。对于较复杂的查询语句，辅助数据将会相当庞大。 论文 1 8 选择x p a t h 作为视图定义语言( x p a t h 是w 3 c 组织推荐的定位x m l 节点的语言，x p a t h 视图也是x m l ) 。通过a x i s ，l a b e l 和p r e d i c a t e 三种操作， 测试变更节点的对视图的影响，从而确定维护方案。此方法同样需要辅助数据， 其大小只依赖于x p a t h 表达式和查询结果的大小，与源数据无关。它并不局限于 单调视图，即对数据源的删除( 插入) 操作只会引起视图的删除( 插入) 。 论文 1 9 中提出用自定义的s c h e m e 来增量更新x p a t h 视图。利用匹配和记 数方法找到需要更新的位置，加以处理。这种方法只适用于单调视图结构。论文 2 0 提出一种增量维护x p a t h x s l t ( e x t e n s i b l es t y l e s h e e tl a n g u a g e t r a n s f o r m a t i o n s ) 视图的算法。该视图是由嵌套了x p a t h 查询语句的x s l t 定义 的，描述从x m l 数据源转换到( x ) h t m l 格式的数据。该方法借助自定义的辅助数 据结构x t - t r e e 保存x p a t h 查询命令，通过一系列算法增量维护视图，避免了重 新执行整个x s l t 的开销。 论文 2 1 提出对w e b 数j ；| ：的有效维护方法，但是它基于x q l 语言，主要针对 x p a t h 定义的物化视图。另外两篇论文 2 2 ，2 3 采用x m ls c h e m a 和关系s c h e m a 来解决视图的增量维护问题。 通过对上述方案的比较，发现影响视图增量更新方法的两个因素是：数据模 型( d a t am o d e l ) 和查询语言( q u e r yl a n g u a g e ) 。上述众多论文中涉及的数据 模型有关系型数据模型( 结构化数据模型) 和x m l ( 半结构化数据模型) 。涉及 的查询语言有x q u e r y ，x p a t h ，l o r e l 和x q j ( x o u e r ya p if o rj a v a ) 等等。本 文采用的数据模型是x m l ，视图定义语言是x p a t h 。x p a t h 是w 3 c 组织推荐的标 准，主要用于定位x m l 节点，它拥有一定的查询能力，适用于多种情况下的应用 需要。 增量更新算法的核心问题是找到视图定义行为和视图更新行为之间的适当 映射。数据模型和查询语言的差异导致了映射的规则不尽相同。本文在x m l 数据 6 第2 章物化视图增量维护方法 模型和x p a t h 查询语言基础上，采用“程序变换 的映射方法来生成指导物化 视图更新的一系列指令，称作更新程序。程序变换的基本策略是根据对输入程序 的分析，经过变换规则的处理，输出另一种功能的程序。从本文来看，输入程序 是x p a t h 命令，输出程序符合x q u e r y 语言规范，能够被x q u e r y 语言解析器分析 执行。而x p a t h 又是x q u e r y 的一个子集，它们都是为了定位查询x m l 而设计的。 另外，s v g 在数据结构上有其特殊性。s v g 规范定义了描述图形的标签及它 们的组织方式。所以s v g 是带有特殊结构的x m l 。这种特殊结构对增量更新算法 会产生一定的影响。因此本文中增量维护方法，并不完全适用于所有x m l 。 2 3 本文的增量维护方法 本文采用的增量维护方法基于论文 2 4 。它的基本原理是从一个程序找到一 个增量更新版本，这个更新版本可以根据输入数据的变化、充分利用原有的计算 结果而生成新的结果。实际上进行了程序的变换，其形式化表示如下：考虑数据 源x 上的一个查询计算q ，查询结果r ，可以表示为r = q ( x ) 。为了避免执行相同 查询时的重复计算，将r 缓存起来，以便重复查询时直接使用。当x 发生了数据 变化x 后，试图找到另一个增量计算版本q ，来计算新的结果r ，即 r = q ( x ，x ，r ) 。增量版本的计算结果要与使用原计算的执行结果等价，表 示为q ( x + x ) = q ( x ，x ，r ) 。为了利用已有的查询结果生成新的视图，以避 免重新查询，要求q 能充分利用r 、x ，尽量少地使用x 。 增量维护方法在视图更新应用中，表示为从定义视图的原始查询计算，找到 一个增量计算指令，利用缓存的物化视图生成新的视图。在w e b 应用环境中，数 据源x 和数据变化x 通常位于服务器端，为了避免将计算参数通过网络传输到 客户端，可以事先将x 和x 带入q 计算，得到只带一个参数r 的计算u ，命 名为更新程序，再将u 程序的代码传给客户端。通常u 的体积很小，便于网络间 传输。在客户端，更新程序u 只需要物化视图r 作为唯一的输入参数即可计算得 到新的视图r ，表示为r = u ( r ) 。寻找q 和生成u 的核心算法详见论文 r 1 6 。 7 北京t 业大学工学硕士学位论文 图2 - 1 瑚l 数据树型结构 f i g u r e 2 1t r e es t r u c t u r eo fx m l d a t a 举例说明，图2 1 表示数据源x 的完整树型结构。考虑一个x p a t h 查询计算 q = d b s 1 3 p r 2 定义了一个视图r ( 图中亮色标注) ，计算结果为r = ( r 。，r ， r mr 。) 。如果在x 中删除b 。子树，按照x p a t h 定义，它的删除操作的路径表示 为d b 3 ，即：a x = d e l e t e ( “d be 3 ”) ，表示删除该路径下的所有节点。 从图1 中可以清楚看出，删除b 。后相当于在r 中删除r 。和r 。增量维护算法能 够发现这种等价关系，并自动生成更新程序u = f n ：s u b s e q u e n c e ( $ r ，l ，2 ) 。其 中“f n ：s u b s e q u e n c e ( s r ，1 ，2 ) ”称为更新程序，它符合x q u e r y 查询语言规范。 “f n ：s u b s e q u e n c e ( k ，m ，n ，) ”是x q u e r y 语言的标准函数，表示从列表k 的第 m 个节点开始，取n 个节点返回。此例中，表示在( r ：，r nr ，r ) 序列中从第 一个节点r 。开始，取到第2 个节点r ，为止。在w e b 环境巾，更新程序u 通过网 络传递到客户端。客户端保留了原有的查询结果r ，直接作为u 的输入参数进行 计算，得到新的视图r = ( r 。，r ，) ，至此完成了物化视图的一致性维护。增量 程序的计算结果与从图上观察的直观结果一致。 2 4 优势比较 相对于2 2 节提到的众多增量维护方案，生成增量更新程序的维护方法主要 有以下优势： 1 更新程序的数据量通常较小，减少了网络数据传输的负担 2 更新程序代码生成过程中可以运用各种优化手段 3 更新程序在客户端执行，可以充分利用客户端的处理能力 8 第2 章物化视图增量维护方法 i ii i u s i l l | i 曼曼曼曼曼! 曼! 曼曼曼曼曼曼寰 4 一致性维护过程中不需要保存辅助数据 其中第1 、3 、4 点特别适用于w e b 应用程序的开发。网络响应时间是考察w e b 应用程序的重要指标，更新程序的较小体积大大减少了带宽的占用，是提升应用 程序性能的重要方法。另外，服务器需要应对成千上万的客户请求，计算负担很 大，所以如果能充分利用客户端的处理能力就可以分担服务器的计算任务，使服 务器的响应时间进一步缩短。最后，维护辅助数据必然要消耗服务器端的资源， 包括存储空间和计算时间。免除辅助数据所节省的资源同样能够减轻服务器的负 担，进一步提高响应时间。因此，对于w e b 环境中的s v g 视图增量更新维护，生 成更新程序的方法是有一定优势的。 2 5 本章小结 本章对物化视图增量维护方法进行了列举和比较。这些方法主要研究对象是 x m l 物化视图。因为s v g 本身也是x m l ，所以这些研究工作也是有借鉴意义 的。由于s v g 具有一定的数据结构规范，导致增量维护算法有一定的特殊性。 然后，本文提出影响增量维护方法的核心因素是数据模型和视图定义语言，并指 出本文采用的增量维护方法是基于x m l 数据模型和x p a t h 查询语言，利用程序 变换的方法完成维护的。同时举例说明了本文采用的基于程序变换思想的物化视 图增量维护方法，并总结了此种维护方法在w e b 开发中的优势。 9 第3 章增量维护系统设计 第3 章增量维护系统设计 3 1 增量维护框架设计 增量维护框架是与具体实现无关的抽象结构设计，它描述了实现增量维护工 作必需的模块及它们的功能和交互过程。在该框架的基础上，设计并实现s v g 视 图增量维护的应用系统。 增量维护框架需要提供的功能包括： 1 接收并处理数据源变更消息( 必须) 2 接收并管理视图查询命令和用户信息( 必须) 3 生成增量更新程序( 必须) 4 管理增量更新程序( 必须) 5 接收并执行更新程序( 可选) 6 接收并管理物化视图( 可选) 对应上述功能需要，增量维护框架构成的模块可以总结为：变更消息管理， 更新程序生成，查询信息管理，更新程序管理。变更消息管理模块接收后台数据 源发生的数据变化消息，启动增量维护过程；更新程序生成模块根据数据变更消 息，通过增量维护算法生成更新程序；更新程序管理模块将所有的更新程序与相 应的用户和查询信息对应起来，并负责去除失效的程序、添加新生成的程序，我 们称之为“版本维护 ；查询信息管理模块接收并管理用户发送的视图查询命令， 以及用户自身的位置信息，为输送更新程序做准备。该框架的基本模块如图3 - 1 所示： 图3 - i 增量维护框架的基本模块 f i g u r e3 - lb a s i cm o d u l e so ff r a m e w o r kf o ri n c r e m e n t a lm a i n t e n a n c e 1 1 北京工业大学工学硕七学位论文 由于执行更新程序与管理物化视图部分会与实际的实现细节相关，例如在 w e b 应用的c s 结构下，这两个模块应该在客户端部署，其中涉及网络通信等细 节问题，因此不便作为增量维护框架的必须模块加以限定。不过，执行更新程序 模块应该能够解析增量更新程序使用的语言；管理物化视图模块应该可以读写物 化视图数据，这是最基本的要求。 另外，数据源是构成实际系统的必要部分，将在下一节系统结构中具体说明。 还有物化视图的应用部分，比如显示s v g 的模块，是应用系统考虑的范围，也将 在下一节中具体说明。 3 2 增量维护系统设计与实现 本文基于上述的增量维护算法和框架，设计并实现了一个实际的软件系统来 完成s v g 视图的增量维护。它的系统结构如图3 3 所示。该系统的主要功能是向 用户提供可定制的地图查询服务。所谓“定制”是指用户通过编写x p a t h 查询命 令获得感兴趣的地图数据。从结构图上看，整个系统是三层体系结构，包括：后 台数据源、应用服务器和前端。在本系统中，它们分别对应：数据库( d b ) 、增 量维护管理器和用户接口。 此系统在设计和实现过程中就注意保持系统的模块化特点，为用户，尤其是 二次开发人员提供了良好的应用接口。并且系统的数据源适合于符合o g c 的 s i m p l ef e a t u r ea c c e s s 标准的以范式表方式组织空间数据的数据库。这两个特 点为本文提出的s v g 视图增量维护系统增加了可用性和实用价值。 3 2 1 用户接口 增量维护框架中的“更新程序执行”和“物化视图管理”两个模块在“用户 接口 部分实现。这里的用户不仅包含使用地图服务的终端用户，而且包括利用 本系统提供的应用接口构建其它系统的二次开发人员。经过分析，面向二次开发 人员的接口主要分为视图获取和视图增量维护两部分。视图获取部分包括“获取 请求对象”、“查询地图数据”、“接收s v g 视图”和“显示s v g 四个功能，对应 的开发接口如图3 2 所示。视图增量维护部分包括“请求进行增量更新维护和 “处理增量更新程序 两个功能。另外，当用户退出应用程序时，需要通知服务 器注销该用户，所以额外需要一个“注销用户”的接口。 1 2 第3 章增量维护系统设计 图3 2 系统为开发人员提供的应用接口 f i g u r e3 - 2a p if o rd e v e l o p e r sp r o v i d e db yt h es y s t e m 上述各个接口的输入输出定义如下： c r e a t e r e q u e s t ( ) 功能：建立一个用于h t t p 通信的对象。 输入：无 输出：用来发送h t t p 请求的脚本对象。 s e n d o u e r y ( d a t a ) 功能：发送用户的查询命令来获取s v g 视图。 输入：d a t a - - x p a t h 查询命令( s t r i n g ) 输出：标志信息( t r u eo rf a l s e ) a c c e p t v i e w ( ) 功能：获取h t t p 响应中的s v g 视图数据，并显示在屏幕上。 输入：无 输出：在屏幕显示s v g ( 1 0 ) d i s p l a y ( v i e w ) 1 3 北京丁二业大学工学硕士学位论文 皇皇曼曼曼曼! 毫! 曼曼曼曼曼曼! 曼! ! 曼曼曼笪! m i m - ! 曼! 曼! 曼量曼曼曼! 曼! ! 曼曼! 蔓! 曼皇曼曼曼曼! 曼! ! 笪! 曼曼! 曼曼曼曼! ! ! 苎! ! 蔓 功能：显示s v g 输入：v i e w - - h t t p 响应中取得的s v g 数据 输出：在屏幕显示s v g ( 1 0 ) g e t u p d p r o g0 功能：请求服务器对当前用户使用的s v g 视图进行增量维护。 输入：无 输出：发送h t t p 请求，通知服务器对本机的s v g 视图进行增量维护。 a c c e p t u p d p r o g0 功能：获取并执行增量更新程序，更新s v g 视图。 输入：无 输出：在屏幕显示更新后的s v g ( i o ) l o g o u t 0 功能：在服务器端注销当前用户，结束更新服务。 输入：无 输出：标志信息( t r u eo rf a l s e ) 以上是对二次开发人员的接口定义。为了使整个系统运转起来，本文基于 i n t e r n e t 浏览器实现了一个应用上述接口的客户端。该客户端主要负责与用户 的交互和s v g 视图的增量更新。 交互的内容包括显示s v g 图像和接受用户输入的查询命令。从s v g 图像显示 工具来看，虽然越来越多的s v g 浏览器软件被开发出来，但是因为各个生产厂商 的各自为政，导致它们对s v g 标准的支持程度参差不齐，还没有达到统一。根据 这些工具的使用方式不同，可以划分为三类：独立软件、开发包和插件。独立软 件是指单独作为一个桌面软件运行，其中的代表有b a t i k ，e s v g 等；开发包是一 系列应用程序接口的集合，它为开发人员提供解析显示s v g 文档的功能，其中比 较著名的是开源项目b a t i k ；插件是指依托于宿主程序乜引，如网页浏览器，而存 在的为某种特定功能开发的工具配件。由于，本文提出的系统基于w e b 环境开发， 所以决定采用插件的方式在浏览器中嵌入显示s v g 的功能配件。 到目前为止，主流浏览器产品，如i e 、f i r e f o x 、o p e r a 等等，都在不同程 度上对s v g 的解析提供了支持。其中f i r e f o x 和o p e r a 解析s v g 的功能是内嵌到 浏览器核心功能中，不需要插件支持，但是它们对s v g 标准的支持有限，尤其对 复杂数据、事件和动画的支持不足。第6 版i e 本身不提供s v g 解析，但是通过 1 4 第3 章增量维护系统设计 嵌入浏览器插件可以很好的支持s v g 显示。表现最为出色的浏览器插件是a d o b e 公司提供的a d o b es v gv i e w e r 比引，简称a s v 。它对s v g 标准的支持相对最为全面， 经过测试，对复杂数据、事件和嵌入脚本等复杂功能都有很好的支持。因此，本 文选定i e + a s v 组合作为系统的客户端软件平台。 客户端交互的另一项功能是接受并处理用户输入命令。在本系统中，用户输 入获取地图图像的查询命令，客户端需要具备一定的逻辑处理能力，应付可能的 命令验证和转发工作。浏览器内嵌的脚本语言可以胜任这项工作汹一3 ，如 j a v a s c r i p t 。脚本语言解析已经成为现代浏览器普遍支持的特性，标准相对统一， 不会因平台软件给实际开发带来太多限制。 综上所述，无论是图像显示还是接收查询命令，都可以理解为一种用户接口， 尤其是接收