（计算机软件与理论专业论文）基于newsml上的递归查询和应用.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名：渔耋主! 至 日期：! ：竺垒! - 兰 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅：本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者虢雌导师签名兹妊 山东大学硕士学位论文 基于n e w s m l 上的递归查询和应用 研究生潘新红 指导教师李庆忠教授 摘要 n e w s m l 是i p t c 为适应新闻行业数字化、新闻表现形式多媒体化以及信息海 量化需求而制定的一套基于x m l 的新闻工业标准。随着n e w s m l 的不断发展和应用， 信息储量成指数增加，有效信息和无效信息混合在一起给寻求信息的用户造成混 乱，所以新的问题被提了出来，那就是对有效信息的查询。x q u e r y 就是w 3 c 推出 的一个对x m l 数据查询的个工作草案，它可对n e w s m l 数据进行查询处理。虽然 x q u e r y 核( x q u e r y 的核心子集) 中存在着一些类型规则和标准化规则，但是这些 规则对于结构上递归的查询映射成的函数的内部函数调用无能为力。另外， x q u e r y 虽支持对n e w s m l 数据的结构上递归的查询，但x o u e r y 在确定结构上递归 查询的类型上是不精确的。本文根据n e w s m l 数据和x q u e r y 的处理模式特点，将结 构化函数内联方法应用到结构上递归的n e w s m l 查询中，在类型信息的指导下对 n e w s m l 递归查询进行了优化。由于n e w s m l 数据结构化和类型复杂等特点，查询都 是在类型指导下进行的而且结构化递归查询非常普遍，本文在结构化内联方法中 运用了内联、水平优化和垂直优化规则。另外，文中对结构化内联规则的有效性 进行了证明，从理论上证明运用结构化内联方法减少了查询遍历的节点数，提高 了查询的效率。 跨媒体出版是目前媒体行业发展的热点之一。新闻的跨媒体出版发展的目 标是对新闻资源进行整合。在信息应用方面，按照市场和用户的需求，对新闻信 息资源进行深度加工和增值服务，实现新闻的个性化定制。后工业时代，已经将 工业时代的批量生产转变为个性化服务。而信息服务的个性化尤为突出。本文基 于这样的背景，建立了一个个性化新闻定制模型。 n e w s m l 标准的制定为新闻个性化定制的异构数据同构提供了解决方案。 x q u e r y 的提出为基于n e w s m l 的数据平台的数据搜索和挖掘提供了技术基础。本 山东大学硕士学位论文 文根据n e w s m l 数据结构化特点和x q u e r y 的查询模式特性，将构化函数内联方 法运用到个性化新闻定制中，旨在提高个性化新闻定制模型中检索器的检索效 率，从而提高了搜索体的速度和新闻个性化定制模型的效率。 关键词：n e * , s m l ；x q u e r y ；结构化函数内联；水平优化：垂直优化；个性化新 闻定制 山东大学硕士学位论文 s t r u c t u r a lr e c u r s iv eq u e r ya n da p p lic a tio no nn e w s m l g r a d u a t e ：p a n x i n h o n g s u p e r v i s o r ：p r o f e s s o rl io i n g z h o n g a b s t r a c t n e w s m lw a s p u b l i c i z e db yi p t c i no r d e rt oa d a p tt h et r e n do f t h en e w s d i g i t a l 、 t h er e p r e s e n t i n gs t y l ed i v e r s i f i c a t i o no fn e w s 、t h er e q u i r e m e n to fag r e a td e a lo f i n f o r m a t i o n ，w h i c h i sas u i to fi n d u s t r i a ls t a n d a r d w i t ht h e d e v e l o p m e n ta n d a p p l i a n c e o f n e w s m l ，i n f o r m a t i o nr e p r e s e n t e db yn e w s m lw i l lb e c o m em o r e a n dm o r ea tt h es a m et i m eu s e f u li n f o r m a t i o na n du s e l e s si n f o r m a t i o nw i l lm i x t o g e t h e ra n dm a k ep e r s o n sw h oa r es e a r c h i n gu s e f u l i n f o r m a t i o nc o n f u s e s ot h e p r o b l e m q u e r y i sb r o u g h tf o r t h x q u e r yc a nq u e r yn e w s m l d a t a x q u e r yi sn o ty e t as t a n d a r d ，b u ti th a sb e e n a c c e p t e dw i d e l y 。t y p e r u l e sa n dn o r m a l i z a t i o nr u l e si nt h e x q u e r yc o r ec a nn o td e a lw i t ht h ef u n c t i o nc a l l i nt h ef u n c t i o n sm a p p e ds t r u c t u r a l r e c u r s i v eq u e r yb ya n a l y s i n gx q u e r yp r o c e s s i n gm o d e l i na d d i t i o n ，as t r u c t u r a l l y r e c u r s i v eq u e r yt y p ei n f e r r e db yt h ex q u e r yc o r et e n d st ob ei m p r e c i s es i n c et h e q u e r yr e l i e s o np o l y m o r p h i cr e c u r s i v ef u n c t i o n sw h o s ed e c l a r e dr e t u r n t y p e i s u s u a l l yag e n e r i ct y p ea l t h o u g hx q u e r ys u p p o r t ss t r u c t u r a l l yr e c u r s i v eq u e r y t h i s p a p e r h a sa p p l i e dt h ea p p r o a c ho fs t r u c t u r a lf u n c t i o ni n l i r t i n gt os t r u c t u r a l l yr e c u r s i v e q u e r yb a s e do nn e w s m la c c o r d i n gt ot h ea t t r i b u t e so fn e w s m la n dp r o c e s s i n g m o d e lo f x q u e r y ，w h i c h c a r li m p r o v et h eq u e r ye f f i c i e n c yb ym e a n so f m a k i n gg o o d u s eo fa v a i l a b l et y p ei n f o r m a t i o nt oo p t i m i z e q u e r i e s q u e r yo fn e w s m li sd i r e c t e db yt h et y p eo fn e w s m ld a t aa n ds t r u c t u r a l l y r e c u r s i v e q u e r yi s u n i v e r s a lb e c a u s eo ft h ea t t r i b u t e so fw h i c hn e w s m ld a t a i s s t r u c t u r a la n d t y p ei sc o m p l e x t h i sp a p e r h a sa p p l i e dt h er u l e so f i n l i n i n g ，h o r i z o n t a l o p t i m i z a t i o n ；v e r t i c a lo p t i m i z a t i o n i na d d i t i o n ，t h i sp a p e rd e m o n s t r a t e dt h ev a l i d i t y o ft h es t r u c t u r a lf u n c t i o n i n l i n i n ga p p r o a c hb ym a t h e m a t i c a li n d u c t i o n i tw a s d e m o n s t r a t e di nt h e o r yt h a tt h ea p p r o a c ho f s t r u c t u r a lf u n c t i o ni n l i n i n gd e c r e a s e dt h e 5 山东大学硕士学位论文 n u m b e ro fn o d e s d i s p o s e d t h e p u b l i c a t i o no f d i f f e r e n tm e d i ai sa h o t s p o t i nm e d i a i n d u s t r y t h et a r g e t o ft h ep u b l i c a t i o no fd i f f e r e n tm e d i ai st oc o n f o r m i t yt h en e w sr e s o u r c e ，e s p e c i a l l yi n a p p l y i n go fi n f o r m a t i o n ，t oa c h i e v ei n d i v i d u a ln e w sc u s t o m i z a t i o na c c o r d i n gt ot h e r e q u e s to ft h em a r k e ta n du s e r sb yp r o c e s s i n g i n f o r m a t i o nr e s o u r c e s d e e p l ya n d v a l u ea d d e ds e r v i c e b a t c hp r o d u c t i o ni ni n d u s t r i a lt i m e si sr e q u e s t e dt oc h a n g ei n t o i n d i v i d u a ls e r v i c ei n p o s t - i n d u s t i a l t i m e s t h i sp a p e rb u i l tam o d e lo f i n d i v i d u a l n e w sc u s t o m i z a t i o ni nt h i sb a c k g r o u n d n e w s m l p r o v i d e st h es o l u t i o nf o rd i f f e r e n ts t r u c t u r a ld a t ac h a n g e di n t ot h e s a m es t r u c t u r a ld a t a x q u e r yp r o v i d e st h et e c h n i c a lb a s i sf o rq u e r yo fn e w s m lt h e s t r u c t u r a lf u n c t i o ni n l i n i n ga p p r o a c hh a sm a d eu s eo fas e r i a l so fr u l e st oc h a n g et h e q u e r yi n t oo p t i m a la l g e b r a i ce x p r e s s i o n si n c l u d e dt y p ei n f o r m a t i o n t h i sp a p e rw i l l a p p l yx q u e r yo p t i m i z e db yt h es t r u c t u r a l f u n c t i o ni n l i n i n g a p p r o a c ht o i n d i v i d u a l n e w sc u s t o m i z a t i o n ，w h i c hi m p r o v e dt h ee f f i c i e n c yo fi n d i v i d u a ln e w sc u s t o m i z a t i o n t ol a r g ee x t e n t k e y w o r d s ：n e w s m l ；x q u e r y ；s t r u c t u r a lf u n c t i o ni n l i n i n g ；h o r i z o n t a lo p t i m i z a t i o n ； v e r t i c a lo p t i m i z a t i o n ；i n d i v i d u a ln e w sc u s t o m i z a t i o n 6 山东大学硕士学位论文 第一章绪论 网络技术发展到今日，已经渗透到社会生活的每一个角落。其中，h t m l 语言功不可没。正是因为h t m l 语言的发展，互联网也才得以有现在的辉煌。 但是随着互联网技术发展，它越来越难以满足不同用户提出的各种要求。 1 1 背景和研究动机 htm l 几乎是专门为显示静态文本而设计的，对超级链接支持不足，并缺 乏空间立体描述，不但处理图形、图像、音频、视频等多媒体能力较弱、图文混 排功能简单，而且不能表示多种媒体的同步关系，而人们对信息的需求越来越高， 希望主动灵活地从网上获取信息，因而html 已经不能满足人们的需要。w 3 c 于1 9 9 8 年2 月发布了x m l 标准。 x m l 是一种元标示语言( m e t a m a r k u pl a n g u a g e ) 1 ，是用来说明其他语言 的语言。它在描述数据内容的同时能突出对结构的描述，体现出数据之间的关系。 x m l 的内容和表现形式是分离的。它增加了结构和语义信息，可使计算机和服 务器即时处理多种形式的信息。另外，x m l 解决了h t m l 不能解决的w e b 问题， 如i n t e r n e t 发展速度快而接入速度慢的问题，以及可利用信息多，但难以找到 需要的信息的问题。 x m l 使用d t d ( d o c u m e n tt y p ed e f i n i t i o n 文档类型定义) 来表示数据，用 x s l ( e x t e n s i b l es t y l es h e e tl a n g u a g e ，可扩展的样式语言) 来显示数据。x s l 包括两部分：一个用来转换x m l 文档的方法；一个用来格式化x m l 文档的方法。 x l l ( e x t e n s i b l el i n kl a n g u a g e ) 是x m l 连接语言，它提供x m l 中的连接，与 h t m l 中的类似，但功能更强大。使用x l l 可以多方向连接，且连接可存在于对 象层级，而不仅仅是页面层级。由于x m l 能够标记更多的信息，所以它就能使用 户很轻松地找到他们需要的信息。 利用x m l ，w e b 设计人员不仅能创建文字和图形，而且还能构建文档类型定 义的多层次、相互依存的系统、数据树、元数据、超链接结构和样式表。利用 x m l 可以实现h t m l 无法完成的w e b 应用。如，需要w e b 客户端在两个或更多异 质数据库之间进行通信的应用、试图将大部分处理负载从w e b 服务器转到w e b 客 山东大学硕士学位论文 户端的应用、需要w e b 客户端将同样的数据以不同的浏览形式提供给不同的用户 的应用、需要智能w e b 代理根据个人用户的需要裁减信息内容的应用等。 随着x m l 的发展，各行各业根据自身的特点，纷纷制定本行业的标准。2 0 0 0 年1 0 月 2 ，国际新闻电信理事会i p t c ( i n t e r n a t i o n a l p r e s s t e l e c o m m u n i c a t i o n sc o u n c i l ) 在x m l 的基础上制定出了管理多媒体新闻的标 准一- - n e w s m l ( 新闻扩展标识语言) 。 n e w s m l 标准出台后，立刻得到了包括美联社、法新社在内的众多的世界知 名新闻媒体的大力支持。随着科技的发展和人们对信息需求的提高，特别是互联 网的发展，单一形式的新闻信息服务己不能满足社会需要，多媒体新闻越来越受 到社会欢迎，因此，与多媒体新闻紧密相关的新的新闻技术标准新闻标识语言 必将为国际新闻界广泛采用。 n e w s m l 为多媒体新闻发布、交换提供了一个框架。 3 它贯穿于新闻的整个 生命周期，从新闻的产生、管理和发布到新闻的交换和运用。n e w s m l 继承了x m l 数据的特点，数据是结构化的，能够得心应手地处理大型复杂的文档。同时也是 简洁的、灵活的和可扩展的。n e w s m l 文件可包含正文、视频、音频、图形、图 片等各种形式的多媒体内容。一切与新闻内容有关的资讯都可以纳入n o w s m l 之内 4 。 n e w s m l 实现了新闻信息的可重用性、长久性、共享性和高效性。 5 但n e w s m l 模糊了数据库、文档、和消息之问的界线，要充分发挥n e w s m i 。的所有潜能，还 必须要有一个强大的查嘲语言。x o u e r y 就可对n e w s m l 数据进行查询处理。w 3 c 的x q u e r y 工作小组在2 0 0 3 年1 1 月发布了最新的x q u e r y 草案。 6 x q u e r y 现在 虽然还未成为业界标准，但是它的不断发展及突出优势已经得到了业界的认可， 越来越多的传统数据库产品对x q u e r y 提供支持。 x q u e r y 采用了简洁的类s q l 语法，对于传统的数据库用户是不陌生的。 x o u e r y 由表达式组成，类型可以由一个或多个被处理文档的n e w s m ls c h e m e 来 确定。x q u e r y 最突出的特点是函数化和强类型 7 。 x q u e r y 仍在不断地发展改进过程中。我们从当前公布的x q u e r y 草案的查询 模式分析，x q u e r y 虽然支持对n e w s m l 数据的结构上递归的查询，但在确定结构 上递归查询的类型上是不精确的。 8 如递归函数返回的类型经常被声明为： 山东大学硕士学位论文 x s ：a n y t y p e 9 。另外，x q u e r y 核( x q u e r y 的核心子集) 中存在着的类型规则 和标准化规则对于结构上递归的查询映射成的函数的内部的函数调用无能为力。 为了更好地在x q u e r y 查询中对数据类型定义和优化查询，单单仅依靠x q u e r y 的 现有的类型规则和标准化规则是不可行的。 后工业时代已经将工业时代的批量生产转变为个性化服务。而信息服务的 个性化尤为突出。道理很简单，只要存在着个人差异，就存在着不同的信息需求 这就是信息的个性化需求一一个性化新闻定制，基于n e w s m l 上的个性化新闻定 制是我们面临的一个紧要问题。 1 2 相关研究 x q u e r y 不但能处理n e w s m l 格式的文件，而且能够处理结构上嵌套、类似 n e w s m l 结构的数据库数据。x q u e r y 能从n e w s m l 文档中选择和抽取出复杂的模式， 然后用任意形式表示，并在此基础上进行表达式的计算。x q u e r y 还可以在x m l 文档中创建结构内容。 x q u e r y 是一种函数化语言，它由表达式组成而不是语句 1 3 3 。x q u e r y 也是 一种类型化语言。类型可以由一个或多个被处理文档的n e w s m ls c h e m e 来确定。 另外，x q u e r y 最重要的特征是支持对n e w s m l 数据的结构上递归的查询。 x q u e r y 查询模块包含三个部分， 1 4 第一部分是由名之空间声明和模块引 入语句组成，第二部分包含函数定义，自定义的函数放在这里。这两个部分总称 为查询序( q u e r yp r o l o g ) 。第三部分包含查询语法( q u e r ye x p r e s s i o n s ) 。 每一个x q u e r y 查询包含一个或多个查询表达式。常用的语法：f l w r e x p r s s i o n ，p a t he x p r e s s i o n ，e l e m e n tc o n s t r u c t o r s ，c o n d i t i o n a le x p r s s i o n s ，及 f u n c t i o nc a l l s 。 对于n e w s m l 数据查询，数据存储模式对x q u e r y 的查询没有影响。一般地， 处理n e w s m l 文档有两种方法 1 5 ：一种是直接将n e w s m l 文档作为数据库使用， 另一种是将n e w s m l 数据存储在传统数据库中或是专用于存储x m l 数据的数据库 中。虽然n e w s m l 提供了许多数据库特性：数据存储( x m l 文档) 、s c h e m a ( d t d 、 x m ls c h e m a 语言) 、查询语言( x q u e r y 、x p a t h 等) 、编程接1 ：2 ( s a x 、d o m 、j d o m ) 等，但是它缺少许多真实数据库具备的特性：高效存储、索引、安全性、事务和 山东大学硕士学位论文 数据完整性、多用户访问、触发器、多文档交叉查询等。所以对于数据量小、用 户量小、性能要求一般的，我们可以将n e w s m l 作为数据库直接使用。而对于数 据量大、用户多、性能要求高的，我们就需要用数据库来处理n e w s m l 文件。通 过数据库处理n e w s m l 有两种形式： 1 5 一种是将n e w s m l 的数据存储在传统数 据库中，例如关系型数据库、对象数据库等等，这时，数据库被称为x m l e n a b l e d ： 另一种方式是将n e w s m l 文档存储在一个专用于存储x m l 的数据库中，这时，数 据库被称为n a t i v ex m l 数据库。 虽然x q u e r y 的标准直到现在还未推出，但是它己经得到了各大数据库厂商 的认可，i b m 称将会把x q u e r y 的功能集成到d b 2 数据库管理系列软件中，微软 的新版s q ls e r v e r 都有了对x m l 数据处理的更多支持，另外，o r a c l e 与2 0 0 2 年3 月发表了j a v ax q u e r y 的原形标准，使得在s q l 的查询结果上使用x q u e r y 。 x q u e r y 的查询处理模式分为两个过程 1 6 3 ：外部处理和查询处理过程。 x q u e r y 外部处理包括数据模型的产生、s c h e m a 输入处理和串行化。 在一个查询表达式被处理前，作为查询的表达式的输入文档必须用数据模型 来表示。这个过程属于查询的外部处理过程。一个文档通过x m l 解析器产生一个 x m l 信息集合，这个被解析的文档也许会被一个或多个s c h e m a 验证形成一个抽 象的信息结构，我们称之为模式验证后的信息集合。简称为p s v i 。这个x m l 信 息集合或者是p s v i 最后被转换成数据模型。另外，查询表达式的输入数据有可 能直接来源于关系型数据库或者其它的形式。 1 7 在数据结构中的每一个原子值、元素节点和属性节点都有它们动态的类型。 例如，如果一个数据模型来源于n e w s m l 文档，元素和属性的类型就由s c h e m a 的 确定。属性的值在属性节点里被直接地表示。一个属性节点的类型是未知的，我 们就用动态类型x d t ：u n t y p e d a t o m i c 来表示。元素的值是由他的儿子节点来表 示，这个儿子节点有可能包含文本节点或者是其它元素节点。如果一个元素的类 型是未知的，我们就用类型x d t ：u n t y p e d a n y 来表示。 s c h e m a 输入处理：静态上下文的i n s c o p es c h e m a 的定义是从x m ls c h e m a 中抽取出来的或者由其它的一些机制产生出来的。无论哪种情况，都必须满足被 定义的约束一致性。 串行化是指的是将数据模型中的节点集合转换成八位字节的序列。 山东大学硕士学位论文 一个查询的实现不需要提供串行化的接口。例如，一个查询的实现也许仅需 要一个d o m 接口，或者个基于事件流上的接口。 查询的处理过程包括两个阶段：静态解析阶段和动态估算阶段。其中静态 解析阶段包括四个子阶段：解析阶段、上下文处理阶段、标准化阶段和静态类型 分析阶段。解析阶段主要是分析x q u e r y 表达式的语法。产生语法树。在上下文 处理阶段，查询表达式的语义依赖于输入的上下文。在查询被处理前，输入的上 下文就已经产生。在x q u e r y 中，静态输入上下文由处理环境和x q u e r yp r o l o g 中的声明确定。在x p a t h 中输入的上下文是由处理环境确定。输入的上下文分 为静态和动态两部分。在标准化阶段，每个查询都被映射到x q u e r y 核中，标准 化是通过对查询应用一系列的标准化规则来实现的，首先是通过字的标准化的。 静态类型分析阶段检查每一个查询的类型是否安全，如果安全，决定查询的静态 类型。静态类型分析只在x q u e r y 核中进行。静态类型分析是通过对查询应用一 系列的类型推断规则来实现的既要考虑字的类型也考虑输入文档的已知类型。 如果查询的类型不安全，将返回一个类型错误。如果静态类型分析成功了，将返 回语法树，语法树的每个子表达式都带有它的静态类型，而且也将返回查询的结 果的输出类型。 动态估算阶段有时也称为执行阶段，在这个阶段查询的结果将被计算出。 动态估算阶段由动态上下文处理和动态估算两个阶段组成。动态语义依赖于动态 输入的上下文。动态输入的上下文在x q u e r y 表达式被估算前就已经产生。动态 输入上下文是由处理环境和x q u e r yp r o l o g 中的声明确定。在x p a t h 中，动态输 入上下文是由处理环境确定的。在动态估算阶段，x q u e r y 表达式的值将被计算 出。估算是通过对表达式应用一系列的估算规则来实现的，是从字的估算开始的。 估算的语义只在x q u e r y 核中定义。动态估算的结果或者为一个值或者是一个动 态错误，这个动态错误或者是没有类型或者是类型错误。值得一提的是，逻辑上 把查询处理阶段分为两个时期，并不是说必须分开处理。也许查询处理其会并发 地执行两个时期。上面的查询处理阶段是在查询处理器内部的。具体的x q u e r y 查询处理模式如下图。 1 8 山东大学硕士学位论文 分析x q u e r y 的查询模式及语义可以得出以下结论：不管n e w s m l 数据被直接 使用还是存储于传统数据库中抑或是专用数据库中，x q u e r y 基于n e w s m l 的查询 都不是问题。x q u e r y 虽然处理n e w s m l 数据有许多的优点，但是它在查询时对 类型的判断不够精确而且x q u e r y 核( x q u e r y 的核心子集) 中类型规则和标 准化规则，对于结构上递归的查询映射成的函数的内部函数调用无能为力。 关于x q u e r y 查询的优化已经有了一些研究。其中s e m i m o n a d 1 0 3 和 山东大学硕士学位论文 x d u c e 1 1 的研究就对x q u e r y 核的定型规则系统影响深远。然而，x q u e r y 核在对 待递归查询中的类型确定还不够精确。在这一点上结构化函数内联方法对于递 归查询中的类型确定是一种很好的技术。 关于优化函数，现在大部分的优化技术都将函数简单地看作是外部定义的带 有语义信息的”黑盒子”，而且这些优化技术仅仅考虑非递归函数。对于递归函数 的优化，甚至x q u e r y 核都无能为力。相反，结构化函数内联能够优化递归函数 从而避免了不相关数据赋值。 p r u n i n g 1 2 查询虽然能优化规则路径表达式，但是它对于导航，却不适 用的。 1 3 本文的工作和贡献 x q u e r y 虽然对处理结构化数据有许多的优点，但是根据x q u e r y 的语义和处 理模式，它在处理结构上递归的查询时，对类型的判断不够精确。本文根据 n e w s m l 数据和x q u e r y 的处理模式特点，把结构化函数内联方法应用到结构上递 归的n e w s m l 查询中。将结构上递归的查询，映射成结构上递归的函数后对其进 行调用。这些递归函数将查询中的许多类型信息嵌套进了函数体中，然后采用结 构化函数内联调用这些函数。结构化函数内联方法可被看作是一系列在类型信息 指导下的级联函数内联，得到的结果类型更为精确。连同代数简化，结构化函数 内联将查询转化成关于类型信息的最优代数表达式。这个结果表达式不需要进行 对类型信息来说无用的计算。 由于n e w s m l 数据结构化和类型复杂等特点，查询都是在类型指导下进行的 而且结构化递归查询非常普遍，本文在结构化内联方法中运用了内联、水平优化 和垂直优化规则。另外，文中对结构化内联规则的有效性进行了证明，从理论上 证明运用结构化内联方法减少了查询遍历的节点数，提高了查询的效率。 本文基于跨媒体发展趋势及对新闻信息资源深度加工和增值服务以实现新 闻的个性化定制的市场需求，建立了一个个性化新闻定制模型。根据n e w s m l 数据结构化特点和x q u e r y 的查询模式特性，将构化函数内联方法运用到个性化 新闻定制中，旨在提高个性化新闻定制模型中检索器的检索效率，从而提高搜索 体的速度和新闻个性化定制模型的效率。 山东大学硕士学位论文 1 4 论文架构 本文主要是关注的是基于n e w s m l 上的递归查询和应用。在论文的第二章，主 要分析了n e w s m l 特点、x q e u r y 的发展现状，将结构化函数内联的方法应用到 n e w s m l 的递归查询中，阐述结构化内联方法的基本思想。论文的第三章对结构化 函数内联方法的规则做详细说明并就规则的有效性进行了证明。在文章的第四 章，建立了一个个性化新闻定制模型，在模型中，引入了结构化函数内联方法优 化了的x q u e r y 查询。 值得一提的是，虽然国际新闻电信理事会i p t c ( i n t e r n a t i o n a lp r e s s t e l e c o m m u n i c a t i o n sc o u n c i l ) 于2 0 0 0 年1 0 月公布了n e w s m lv 1 0 ，2 0 0 3 年1 0 ) l 公布了最新标准n e w s m lv 1 2 。但是由于不同国家使用的语言不同，许多国家都 相应地参照i p t c 的标准制定了本国语言的新闻标准，我国的香港中文大学和新华 社都在致力于中文新闻标准的制定中，遗憾的是，直到本文完稿，中文新闻标准 还未出台，所以，本文的例子中的n e w s m l 文档结构均采用的是i p t c 公布的n e w s m l 1 2 标准。 山东大学硕：l = 学位论文 第二章结构化函数内联的方法 从行业角度考虑，n e w s m l 标准的推出得到了世界各大通讯社的欢迎和认同， 如美联社、法新社、新华社。各大通讯社都在为n e w s m l 标准的本地化和推广 做努力。从技术角度考虑，i b m 、微软及o r a c l e 等公司对基于x m l 数据的查 询都采取了积极的应对措施。去年四月，i b m 和微软将向w 3 c 组织提供有关 x q u e r y 标准软件的测试结果。测试的结果体现了x q u e r y 作为新标准的许多的 特征。令人遗憾的是，x q u e r y 至今还未成为标准。在x q u e r y 工作草案小组不懈 努力下，x q u e r y 已经得到了极大地发展最近的草案是在2 0 0 3 年1 2 月公布的。 尽管如此，x q u e r y 仍然对基于n e w s m l 的结构上递归的查询优化力不从心。 2 1 结构上递归查询的概念 结构上递归的查询，指的是包含一个递归导航，或个递归过滤，或者对用 户定义的结构上递归的函数的调用 3 。 递归导航指的是“”，即缩写的相对路径，根据x q u e r y 的语义，“”表 示“d e s c e n d a n t o f s e l f ：”，下面是关于一个递归导航的例子。 一个名为n e w s x m l 文档 m i m e t y p ef o r m a l n a m e = i m a g e j p e g n 山东大学硕士学位论文 查询表达式 l e t $ i n d o c ：= d o c u m e n t ( “n e w s x m l ”) f o rs p r o pi n ( $ i n d o c p r o p e r t y ) w h e r e ( $ p r o p v a l u e = “1 7 0 ”) r e t u r n ) 则查询的结果为： p r o p e r t yv a l u e = 1 7 0 ”纶 递归过滤是指函数f i l t e r ( ) ，该函数将两个节点集合作为该函数的参数。它 过滤掉第一个节点列表的所有后代节点，如果它们在第二个节点列表中也不存 在，就会生成一个由剩余节点的拷贝组成的结果树。从函数的功能可看出，所有 后代节点的遍历就是一个递归的过程，下面是关于一个递归过滤的例子。 l e ts s ：= d o c u m e n t ( “n e w s x m l ”) r e t u r n ( s s ，s s n e w s c o m p o n e n tis s c o n t e n t l t e mi $ s m i m e t y p e ) 则查询的结果为： 山东太学硕士学位论文 2 2 结构化函数内联方法的基本思想 结构化函数内联方法简单的说就是将一个结构上递归的查询，映射成结构上 递归的函数后对其进行调用。这些函数将查询中的许多类型信息嵌套进了函数体 中，然后采用了结构化函数内联的方法调用这些函数。结构化函数内联方法也可 被看作是一系列在类型信息指导下的级联函数内联。连同代数简化，将查询转化 成关于类型信息的最优代数表达式。结果表达式不需要进行对类型信息来说无用 的计算。结构化函数内联方法得到的是一个类型更为精确的结果。 定型和优化一个结构上递归的查询的主要困难是查询中包含函数。为了消除 这些函数，可以内联相应的函数体来取代每个函数调用。由于x q u e r y 查询是在类 型指导下进行的，可利对有关于操作树表达式可能类型的t y p e s w i t c h 表达式的c a s e 规则进行水平优化，以去掉无用的ca s e 规则。保留在类型树中某层的兄弟类 型的有效ca s e 。对于递归的函数，可针对类型树中子孙类型进行垂直优化， 以减少不必要的节点遍历和代数运算。垂直优化主要针对c a s e 中的递归调用。 在进一步探讨之前，先介绍些符号。函数调用用f ( ) ，函数内联用“f ( ) ) ) ， 表达式e 的类型用t ( e ) 。符号 ：表示子类型关系。如果t 1 是t 2 的予类型我们写 作t i ：t 2 。类型t l 和t 2 的交集t = t 1 八t 2 表示t ：t 1 且t ：t 2 。 下面是一个运用结构化函数内联方法的例子。 定义递归函数 d e f i n ef u n c t i o ns l ( x s ：a n y t y p es a ) r e t u r n sx s ：a n y t y p e ， f o r $ ni ns ar e t u r n t y p e s w it c h ( $ n ) a ss x c a s ee l e m e n t p r o p e r t y ( x s ：a n y t y p e ) r e t u r ns x ，s l ( c h i l d r e n ( $ x ) ) c a s e0r e t u r n0 d e f a u l tr e t u r ns 1 ( c h i l d r e n ( $ x ) ) 定义变量 山东犬学硕士学位论文 l e t $ n e w s = f o rs ni n $ n e w sr e t u r n t y p e s w it c h ( s n ) a ss x c a s et n e w s c o m p o n e n tr e t u r n d e f a u l tr e t u r n0 ( 2 ) s l ( c h i i d r e n ( s x ) ) = = f o r $ n li nc h ii d r e n ( s x ) t y p e s w i t c h ( $ n 1 ) a s $ x l ( 2 ) c a s et c o n t e n t l t e mr e t u r n i i ! i h i ! d ! ! ! ( ! 1221 i ( 3 ) d e f a u 】tr e t u r n ( ) ( 3 ) “s i ( c h i l d r e n ( s x l ) ) 2 = f o r $ n 2i nc h i l d r e n ( $ x 1 ) t y p e s w it c h ( $ n 2 ) a s $ x 2 8 山东大学硕士学位论文 c a s ea t t r i b u t eh r e fr e t u r n i i ! f b i ! d 1 2 f 1 222 ! ( 4 ) c a s ee l e m e n tm i m e t y p er e t u r n i ! f b i ! d dl ! ! ) ) !( 5 ) c a s ee l e m e n tc h a r a c t e r is t i c sr e t u r n i i ! i h i ! d ! i i l 2 2211 ( 6 ) d e f a u tr e t u r n0 显然，( 4 ) = = ( ) ，( 5 ) = = ( ) ( 6 ) “s 1 ( c h i i d r e n ( $ x 2 ) ) ) ) = = f o r $ n