（计算机软件与理论专业论文）xml数据库中数据缓存技术的研究.pdfVIP

x m l 数据库中数据缓存技术的 i j | = 究 图表目录 图i 数据树 图2 树类型 图3 条件捌类型 圈4 不完全树 图5 查询树1 、 图6 查询树2 图7 查询l 返回的结果 图8 查询2 返回的结果 图9 查询所有带有图片的照相机 图1 0 对于查询q 返回空集的条件树 图1 l 已知不完全树的条件树类型 图1 2p r o d u c t l ，p r o d u c t 2 与结果的三种情况相结合 图1 3 不完全树中的已知数据部分 图1 4o l y m p u s 和n i k o n 所满足的条件树类型 图1 5 查询3 的查询树 图1 6 查咖3 生成的条件树结点 图17 查询4 的查询树 图1 8 查询4 生成的条件树类型 图l9p r o d u c t 2 b 图2 0 新的查询树 图2 1j 2 e e 三层体系结构 。- 。- 。- 。 。 ，监 监 上生 也 竖 卫 卫 卫 卫 垫 塑 堑 丝 堑 签 型 堑 堑 2 至 2 墨 图2 2 体系结构 图2 3 算法流程图 图2 4 查询界面 图2 5 查询返回结果 图2 6 树类型以及第一次的查询树 圈2 7 查询1 生成的条件树类型 2 9 3 l 5 0 5 0 5 3 5 3 图2 8 查询2 生成的条件树类型塑 图2 9 不完整树的条件树类型丝 复旦大学捌士学位论义 x m l 数据库中数据缓存技术的删f 究 粥4 负兆5 9 负 摘要 x m i 。数掘库的检索是基于结点的，存放大量甚至海量数据的x m l 文件会 导致检索速度极低。随着x m l 数据库的广泛应用，如何对x m l 数据库中的数 掘进行缓存以提高对x m l 数据库的查询效率成为了一个新的研究方向。 本论文提出了将带有不完全信息的x m l 树应用到x m l 数据库数据缓存中 的方法，并实现了一个基于j 2 e e 三层系统结构框架的书店书籍信息的查询系统， 它有效的利用不完全树缓存了书籍信息，提高了查询的效率。 本论文首先介绍了带有不完全信息的x m l 树的概念，然后详细定义了不完 全树生成过程中所涉及到的算法，然后是对本论文所实现的系统的详细介绍，其 中包括详细定义了不完全树的一种切实可行的表示方法，最后对系统的发展进行 了展颦，提出了若干的掰力方向，其中包括改变系统现有x m l 数据的查询方法、 不完全树可能出现的无限膨胀的情况的解决办法以及当不完全树过于庞大的时 候，不完全树的精简方法或结点替换方法。 本论文的刨新点主要有以下几点：1 、将带有不完全信息的x m l 树运用到 x m l 数据库数据缓存中。2 、定义了不完全树的一种切实可行的表示方法。3 、 详细的定义了不完全树生成过程中所涉及的算法。其中包括不完全树中已知数据 结点的生成算法，不完全树的条件树类型的生成算法，查询重写算法，查询树的 条件树类型的生成算法等。 关键词：x m l 数据库，数据缓存，不完全树，条件树类型 复旦大学硕j 二学位论文 兰坚兰墼坐堕塾坐竺鱼些查塑业兰兰塑! 型兰! | ! ! 墨 r e s e a r c h e so nd a t ac a c h i n gi nx m ld a t a b a s e s a b s t r a c t e f f i c i e n c yp r o b l e mw i l lo c c u rw h e nw eq u e r yb i gd a t ai nx m ld a t a b a s e s b e c a u s et h em e t h o do fq u e r y i n gi sb a s e do nn o d e s r e s e a r c ho nd a t ac a c h i n g i nx m ld a t a b a s e sh a sb e c o m ean e wr e s e a r c hd i r e c t i o nw i t h t h er a p i d d e v e l o p m e n t o fx m ld a t a b a s e s w ep u tf o r w a r dan e wm e t h o do fd a t ac a c h i n gi nx m ld a t a b a s e sb yu s i n g x m lw i t hi n c o m p l e t ei n f o r m a t i o ni nt h i st h e s i s w eh a v ea l s od e v e l o p e d as y s t e mb a s e do dt h et h r e et i e r sa r c h i t e c t u r eo fj 2 e e ，w h i c hi si n t e r e s t e d i nt h ei n f o r m a t i o no ft h eb o o k si nt h eb o o k s t o r e t h es y s t e mi n c r e a s e s t h ee f f i c i e n c yo fq u e r i e sb ye f f e c t i v e l yu s i n gt h ei n c o m p l e r et r e et oe a c h t h ei n f o r m a t i o no ft h eb o o k s i nt h i s t h e s i s ，w e f i r s ti n t r o d u c et h ec o n c e p t i o no fx m lw i t h i n c o m p l e t ei n f o r m a t i o n t h e n w ed e f i n eaf e a s i b l em e t h o dt or e p r e s e n tt h e i n c o m p l e t et r e e w ea l s od e f i n es o m ea l g o r i t h m st h a ta r eu s e dd u r i n gt h e c r e a t i o no ft h ei n c o m p l e t et r e e a tt h ee n do ft h i st h e s i st h ef u t u r e d e v e l o p m e n ta n dt h ew o r k i n gd i r e c t i o no ft h es y s t e ma r em e n t i o n e d ，w h i c h i n e l u d e st h ec h a n g ea b o u tt h em e t h o df o r ) ( m lq u e r ya n dt h er e p l a c e m e n t m e t h o do ft h ei n c o m p l e t et r e e o u rc o n t r i b u t i o n sc a nb es u m m a r i z e da s ： 1 w ee a c ht h ed a t ai nx m ld a t a b a s e su s i n gi n c o m p l e t et r e e 2 w ed e f i n eaf e a s i b l em e t h o dt or e p r e s e n tt h ei n c o m p l e t et r e e 3 w ed e f i n et h ea l g o r i t h m st h a ta r eu s e dd u r i n gt h ec r e a t i o no ft h e i n c o m p l e t e t r e e t h ea l g o r i t h m si n c l u d ek n o w nd a t ae r e a t i o n a l g o r i t h m ，c o n d i t i o n a lt r e et y p e sc r e a t i o na l g o r i t h m ，q u e r y i n g r e w r i t i n ga l g o r i t h m ，e t c k e y w o r d s ：x m ld a t a b a s e s ，d a t ac a c h i n g , i n c o m p l e t et r e e s ，c o n d i t i o n a lt r e e t y p e s x m l 数据库中数据缓俘技术的研究 第一章引言 1 1 x m l 1 4 数据库数据缓存的需求背景 1 i 1x m l 数据库 2 应用越来越广泛 信息叫代的到来触发了人们对各种信息获取和管理的需求，信息的非结构化 成为关系数据库不易解决的难题。而管理非结构化数据恰恰是x m l 数据库所擅 长的，随着x m l 成为数据交换规范的工业标准，x m l 数掘库在业界的位置也 更加巩固 3 。 与传统关系数据库相比，x m l 数据库具有以下特点： x m l 数掘库的数据模型可以是树、图等层次数掘模型，而传统的关系数 据库是以关系数据模型理论为基础的，所以x m l 的数据结构比关系数据库更具 有表现力，它能够对诸如网页等半结构化数据进行有效的存取和管理，而且更加 便于对层次化的数据进行操作。 传统数掘库语言允许对数据元素的值进行操作，但不能对元素名称进行操 作x m l 数据库则提供了对标签名称的操作，并且包括了对路径的操作。 x m l 数据库的显示丰富多样，其多样性由x s l 4 ( e x t e n s i b l es t y l e s h e e t l a n g u a g e ，可扩展样式表语言) 指定，而传统关系数据库的显示方式相对简单。 传统关系数据库只能采用s q l 查询语言，而x m l 文档查询语言包括 x q u e r y 5 、x p a t h 6 、x m l - q l 7 、q u i l t 8 等。 x m l 数据库的模式主要由d t d 、x m ls c h e m a 确定，而传统关系数据库 由数据字典决定；不过以文档为中心的x m l 文档其内容是有顺序的，顺序性使 得查询操作尤其是连接和修改操作更加复杂，而在传统数据表中，表项之间的顺 序是可以互换的。 x m l 数据库在管理复杂数据结构中所表现出来的超强能力，已经逐渐为用 户所认同。对于异构信息系统的集成，比如b 2 b 、b 2 c 集成、电子信息的发布、 电子销售等，以及在数字图书馆、音视频媒体中心、电子邮件管理、企业信息 和知识管理中心等以文档为中心的应用中，x m l 数据库也显示出了它的潜力。 就算是对遗留系统有较高要求的用户，也可以从支持x m l 的数据库中找到足够 的支持。 兰坚! 墼塑壁! 塑塑堡堡垫查墼竺塞 一墨兰【_ 三! 三! 墨 1 1 2 如何对x m l 数据库数据进行缓存成为一个新的研究方向 x m l 数据库的检索是基于结点的检索存放大量甚至海量数据的x m l 文 件会导致检索速度极低。x m l 的修改也是基于结点的，所以修改效率也很低。 另外当前的数据库和搜索引擎等的数据缓存方法【9 【1 0 【1 1 】【1 2 【1 3 都没有利用 x m l 本身的半结构化特点实现缓存，因此如何对x m l 数据库中的数据进行缓 存以提商数据库的查询效率成为了一个新的研究方向。 1 2 相关工作 对x m l 数据库进行数据缓存的研究是一个崭新的研究方向，在 1 】中作者将 关系数据痒中的不完金信息的思想应甩到x m l 数据席中给出了带有不完全信 息的x m l 树的概念，并定义了与不完全树的表示和查询相关的概念，x m l 数 据的缓存在 4 7 f 4 s 中有所研究，本论文受 4 9 j 中提到的想法所启发，将不完全树 的思想应用到x m l 数据库的数据缓存中，通过缓存来提高x m l 数据库查询效 率，在论文中具体的定义了一种可行的不完全树的表示方法，论文中还定义了不 完全树生成过程中所涉及至0 的几个算法并加以实现。 1 3 本文的工作成果 本论文研究的目标是如何利用带有不完全信息的x m l 树 1 来缓存x m l 数 据库数据，以及如何利用已经缓存的数据来提高x m l 数据库数据查询效率。 本论文主要的工作成果如下： 1 介绍了不完全树的表示和查询过程中所涉及到的概念。 2 定义了一种切实可行的不完全树的表示方法。 3 具体定义了不完全树生成过程以及查询过程中所涉及的算法，其中包括 不完全树的已知数据结点的生成算法，不完全树条件树类型的生成算法，查询重 写算法等。 4 在系统上t 设计并实现了一个基于j 2 e e 三层系统结构框架【1 5 】实现的贸 有x m l 数据缓存功能的系统 1 4 本文组织 本文在第二章中首先对关系数据库中的不完全信息以及如何从不完全信息 复苴丈学碗士学位论文 x m l 数据库中数据缓存技术的研究第8 负共5 9 负 中获取信息的方法进行介绍，然后介绍了 1 】中作者如何将关系数据库中的不完 全信息表示的思想应用到x m l 数据库中，用带有不完全信息的x m l 树来表示 不完全信息，并详细的介绍了不完全树中所涉及的一些具体的概念、定义和说明。 本文在第三章中定义了不完全树生成过程中涉及的主要算法，其中包括不完 全树的重新生成算法，以及如何从不完全树中获取信息的算法流程，以及查询树 的重写算法。 第四章中开始讨论系统的实现。首先介绍了系统的总体构架和开发环境，然 后介绍了对于系统的些说明和简化限制，然后是系统中所涉及的相关的x m l 文件满足的d t d ，在这一部分详细的介绍了本论文使用的表示不完全信息的方 法，最后是系统的具体实现函数的介绍和界面。 第五章在完成对系统的展望以后，对整个系统的设计和开发工作进行了总 结。 。一 。 复旦大学礤士学位论文 兰坚! 墼堡壁! 墼塑堡登垫查塑竺塞一兰2 l 三! ! ! 旦 2 1x m l 介绍 第二章相关概念的介绍及定义 x m l 是互联网联合组织( w 3 c ) 创建的一组规范，以便于软件开发人员和 内窑创作者在网页上组织信息，其目的不仅在于满足不断增长的网络应用需求， 同时还希望借此能够确保在通过网络进行交互合作时，具有良好的可靠性和与交 互操作性。 与h t m l 一样。x m l 也源自s g m l 1 6 1 ( s t a n d a r dg e n e r a l i z em a r k u p l a n g u a g e 一种老资格的通用标记语言) ，它保留了s g m l 8 0 的功能，使复杂程 度降低2 0 ，尽管如此，x m l 却有着h t m l 语言所欠缺的巨大伸缩性与灵活性。 x m l 不再像h t m l 一样有着一成不交的格式。x m l 实际上是一种定义语言， 即使用者可以定义无穷无尽的标记来描述文件中的任何数据元素，从而突破了 h t m l 固定标记集合的约束，使文件的内容更丰富更复杂并组成一个完整的信息 体系。 x m l 语言可以让信息提供者根据需要，自行定义标记及属性名，也可以包 含描述法，从而使x m l 文件的结构可以复杂任意程度。x m l 主要有三个要素： s c g e r a a 1 7 ( 模式) 、x s l ( e x t e n s i h l es t y l e s b e e tl a r t g u a g e 可扩展样式语言) 和 x l l 【1 8 】( e x t e n s i b l el i n kl a n g u a g e 可扩展链接语言) 。s c h e m a 规定了x m l 文件 的逻辑结构，定义了x m l 文件中的元素，元素的属性以及元素和元素的属性之 间的关系，它可以帮助x m l 的分析程序校验x m l 文件标记的合法性；x s l 是 用于规定x m l 文档样式的语言，它能在客户端使w e b 浏览器改变文档的表示 法，从而不需要再与服务器进行交互通信；x l l 将进步扩展目前w e b 上已有 的简单链接。良好的数据存储格式，可扩展性，高度结构化、便于网络侍输是 x m l 主要的四大特点，决定了其卓越的性能表现。 2 2x m l 数据库介绍 事实上x m l 作为数据交换的标准，更着嚣于统一数据格式，而不是提供j 数据库的特性。因此在x m l 应用中，数据库作为数据管理的位置依然没有改变。 x m l 数据本身的树形结构不同于关系模型中的二维袭结构，这种差别反映 在数据库产品处理x m l 数据的技术上，形成两大阵营：x m l e n a b l e dd b m s ( x e d ) 和n a t i v ex m ld b m s ( n x d ) 。 兰坚! 墼塑壁! 墼塑望查垫查塑! ! 塞 一笙j 竺堕苎! ! 墨 x e d 是在原有数据库基础上扩展了x m l 支持模块，完成x m l 数据和数据 库之间的格式转换和传输。从存储粒度上，可以把整个x m l 文档作为r d b m s 表中行，或把x m l 文档进行解析后，存储到相应的表格中。为了支持w 3 c 的一些x m l 操作标准，如x p a t h ，x e d 提供一些新的原语( 如o r a c l e 9 i r 2 增加 了一些数据包来操作x m l 数据等) ，并优化了x m l 处理模块。 n x d 则出现在x m l 数据处理领域内，一般采用层次数据存储模型，保持 x m l 文档的树形结构，省掉了x m l 文档和传统数据库的数据转换过程。n x d 是专门为存储x m l 文档设计也兼有一般数据库的特性，例如支持事务，并发 控制，查询语言，安全机制，二次开发接口等。唯一的不同之处在于其内部存储 模型是基于x m l 文档树形结构，而非关系模型。 x m l 文档有两种文档类型：第一种是”以数据为中心”( d a t a c e n t r i c ) 。”以数 据为中心”的x m l 文档着重于文档中的数据，而非文档格式，如航班信息、销 售定单、科学计算结果等。这种文档的数据一般由机器产生，来源于传统数据库 中的数据。主要应用在电子商务、e r p 、e a i 等领域，集成不同数据源的数据， 交换信息。”以数据为中心”的x m l 文档具有以下特点：结构化的数据、数据粒 度大小适中、很少或没有混和内容( m i x e i dc o n t e n t ) 、文档顺序( d o c u r a e n t o r d e r ) 不重要。第二种是”以文档为中心”( d o c u m e n t c c n t r i c ) 。”以文档为中心”的x m l 文档主要是用来表示人类自然语言描述的数据，如电子邮件、书和用户手册。这 种文档具有更复杂的结构，一般不是机器自动产生的。目前w e b 上的大部分数 据都可以表示成这种文档。“以文档为中心”的文档具有以下特点：半结构化或非 结构化的数据、较多的混和内容( m i x e dc o n t e n t ) 、文档顺序( d o c u m e n t - o r d e r ) 重 要。 对于”以数据为中心”的x m l 文档，x b d 可以方便地将其中的数据抽取，存 储在传统数据库中，但对于”以文档为中心”的x m l 文档则显得力不从心了。 n x d 由于无需在两种模型之间转换数据，因此在处理”以文档为中心”的x m l 文 档就很有优势。 n x d 是专门为存储x m l 文档设计，也兼有般数据库的特性，例如支持 事务，并发控制，查询语言，安全机制，= 次开发接口等。 r o n a l db o u r r c t 对n x d 有如下定义( 1 9 ： ”n x d 的逻辑模型建立在x m l 文档，而非文档中的数据之上，并根据它来 存取数据。该模型至少包括元素( e l e m 锄t ) 、属性( a t t r i b u t e ) 、p c d a t a 和文档顺 序，例如x p a t h 的数据模型等，n x d 的最小存储单位是x m l 文档”。 一般认为，n x d 应该具有以下几个特性：文档集合( d o c u m e n tc o l l e c t i o n 、， 查询、更新，事务、锁和并发控制、二次开发接口等。 复旦大学硕士学位论文 ：坚! 塑塑壁! 墼塑堡鱼垫查塑型墨l 旦兰l ! i ! ! 兰 2 3 不完全信息介绍 不完全信息最早在关系数据库中被广泛的研究 2 0 ，很多的研究都将重点放 在如何获得符合向不完全数据库提出的查询的“正确的”语义结果 2 1 2 2 2 3 2 4 2 5 。通常获得不完全信息的“正确的”语义结果的获取有两 种方法： 第一种：c o l s e dw o r l da s s u m p t i o n ( c w a ) c w a 表示除了在不完全数据库中明确表示的信息以外，不存在任何别的信 息。 第二种：o p e n w o r l d a s s u m p t i o n ( o w a ) o w a 表示除非在不完全数据库中明确的排除该数据，否则任何数据都可能 存在的。 在本论文中的不完全树利用c w ao w a 两者的结合，用带有不完全信息的 x m l 树来表示缓存的数据，该树中包含已经缓存的数据，也包含了根据已经缓 存的数据而产生的剩余数据可能满足的条件，当用户对其进行查询的时候，首先 得到已知数据，然后根据剩余数据可能满足的条件向x m l 数据库提出新的查询 以获取更多的信息。 在 2 6 中详细的介绍了如何利用c - t a b l e s 来表示关系数据库中的不完全信 息，在 2 7 j 2 s 2 9 中研究了处理关系数据库中的不完全性的复杂度在 3 0 i 中侧重研究了如何更新关系数据库中的不完全信息。在本论文实现的系统是利用 带有不完全信息的x m l 树来缓存x m l 数据库的数据信息，它是在 3 1 中的对 于不完全信息的研究上建立的，该表示方法也是在 3 2 儿3 3 3 4 3 5 3 6 中研究 的如何利用视图来回答用户查询的基础上建立的，在 3 7 中也研究了在半结构化 数据中的不完全信息问题，下面缓存数据的表示方法中用到的概念和相关的定义 在 1 】中有详细的介绍，下面简单的介绍一下不完全树中涉及到的相关概念。 2 4 不完全树中的相关概念 2 4 1 数据树( d a t at r e e s ) 本论文中将x m l 看成是树，例如 x i a o w u c h u a nr d 复且丈学磺士学位论文 兰竺! 鳖塑壁生塾塑堡鱼垫查塑型塑苎j 三丝羔型 x i a o y a h o o c o n l 其对应d t d 3 8 为p e r s o n n a m e ，a d d r , e r n a i l + 将这个x m l 看成如图l 所示的数据树： p e l s 0 r i 爪 n a m ea d d r ? x 凯加】a n r d e l 磷1 i 、 幽硼驰跏。蛐 图1 数据树图2 树类型 用n 表示无限的结点集合，表示无限集合n 的命名集台，q 表示无限结 点集合n 的值集合。 下面是对数据树的具体的定义： 在艺上的数据树是一个三元组 ： 其中t 是一个有限的树，树中结点属于n 。 是结点的命名功能，它将树中的每个结点与中的名字联系。 v 实现树中结点值的映射，它将树中的每个缩点都与q 中的一个值对应。 2 4 2 树类型( t r e et y p e s ) 在x m l 文件中，用d t d 来描述文件的结构，在系统中，用简单的d t d 来 表示树的类型。 对于结点命名集合，通过在子结点上加上辅助标记w 来描述结点含有该子 结点出现次数的限制w 共有四种表示符号，+ ，7 ，1 。 树类型定义： 在上的树类型t 是一个三元组( ，i ，t ) ，其中r 是根结点，而t 对属于z 中的每个结点口进行类型定义t ( 口) 。 如果一个数据树t 满足( ，r ，t ) ，记做t 卜一，所有的满足t 的数据树记做 r e p ( t ) 。 对于任意一个属于的结点d ，如果t ( 口) 包含有口，一，则对于表达式o ，m 根据 董且大学硕士学位论文 的值不同有以下意义： w = 1 表示结点口有且只有一个名字为口，的子结点 = ? 表示结点最多有一个名字为口。的子结点 _ + 表示结点d 最少有一个名字为的子结点 = + 表示结点口没有对名字为q 的子结点的个数的限制 其中对于m = 1 简单的用它的结点的名字表明有且只有一个结点 例如对于数据树类型： - r o o t ：6 a t a o g c a t a l o g p r o d u c t + p r o d u c t _ i l a r f l e ，p r i c e ，c a t ，p i c t u r e c a t - s u b c a t 它表示的意义是：数据树的根结点是c a t a l o g ，c a t a l o n g 结点至少有一个 p r o d u c t 子结点，蕊p r o d u c t 结点有四个子结点，n s l l l e ，p r i c e ，c a t ，p i c t u r e ，而c a t 子结点底下又有一个子结点s u b c a t 。用树来表示，如图2 所示。 2 , 4 3 条件树类型( c o n d i t i o n a l t r e e t y p e s ) 下面讨论下不完全信息的表示方法。本论文中使用条件树类型来表示不完 全信息，条件树类型对树类型( t r e et y p e s ) 进行y - 个方面的扩充( 在不同的上下 文情况下，使用不同的名字，加上条件指定的d t d 扩充方法在【3 9 1 1 4 0 1 1 4 t 1 中有深入 的研究) ： 】允许对结点类型进行分离操作 2 允许对数据值指定条件 3 允许增加一个说明措施来允许不同类型的结点使用相同的结点名称 在介绍条件树类型之前。先介绍一下简单的条件树类型。在上的简单条件 树类型是一对( r ，t e n d ) ，其中- 是从是对简单条件树中结点向树类型中结点的映 射，它实现了对树类型的结点分离操作，c o n d 指定任何一个原来的树结点口要 满足的条件，所有满足简单条件树类型的树表示为r c p ( t ，c o n d ) o 例如对于树类型 r o o t ：d e a l e ri r d e a l e r_ u s e d c a r ln e w c a r u s e d c 甜_ a d + n e w c a r - a c t * a d _ m o d e l y e a r i m o d a l 树类型的= d e a l e r ，u s e d c a r , n e w c a r ，a d ，m o d e l ，y e a r ) 对于经销商来说他拥有的车只有用过的车才有年这个后继结点，因此将车 a d 分为两个不同的结点a d n e w , a d u s e d ，新的树类型为： r o o t ：d e a l e r d e a l e r_ u s e d c a r in e w c a r u s e d c a r a d u s e d n e w c a r a d n e w a d u s e d m o d e l ，y e a r a d n e w_ m o d e l 新的树类型的= d e a l e r , u s e d c a r , n e w c a r , a d n e w , a d u s e d ，m o d e l ，y e a r ) 。 为了使新的生成的树满足原来的树类型，必须定义一个有，到的映射盯， 例如在上面的例子中要定义映射盯( a d u s e d ) = c r ( a d n e w ) = a d ，这样就实现了允许 凡个可能的不同的结点类型来共用同一个结点的名字。 映射盯负责通过将树中的结点名称替换成盯( 口) 将一个数据树t 转化为数据 树t7 ，现在就对条件树结点类型进行定义： 关于和，的条件树结点类型是一个三元组：( t ，c o n d ，仃) ： 其中( t ，e o n d ) 是在上的简单条件树类型，d 是从结点集合一到结点集合 上的映射。 关于z 的数据树t 包含在r e p ( t ，c o n d ，盯) 中，当且仅当在r e p ( t ，e o n d ) 存在 个予树t 满足t = 仃( t ) 。 例如在图4 中不完全树中的结点p r o d u c t l ，p r o d u e t 2 b ，p r o d u c t 2 c 是条件树类型 结点其具体表示如图3 所示： p r o d u c t 2 c p r o d u c t o u b c 4 t 3 c a m e r 6 图3 条件树类型 相应的映射盯定义为：c r ( p r o d u c t 2 c ) = o ( p r o d u c t 2 b ) = c r ( p r o d u c t l ) - - p r o d u c t 复旦大学硕士学位论文 器一 莎一 e咄 巷 兰坚! 塾塑生! 墼塑望查垫查墼塑塞曼三里苎三! 里 2 4 4 不完全树( i n c o m p l e t et r e e s ) 有了数据树和条件树类型的定义，现在就可以定义不完全树了，不完全树包 括两个部分；已知的数据，未知数据，已知的数据是有数据树表示，未知的数据 有条件树类型来描述。下面就定义不完全树： 不完全树包括下面几个方面： 1 在和上的条件树类型，它表示未知的信息，它的结点名称来自于集 合= 。 2 已知数据树。它表示已知的数据，结点的名称来自于集合。 在本论文的缓存系统中就是用不完全树来表示已经缓存的数据以及可能数 据库中拥有的数据所满足的条件的，在系统中，利用已经得到缓存的数据快速的 获得用户所需的数据，并根据条件树类型结点生成效率更高的查询语句向x m l 数据库提出新的更加精确、有效的查询，并根据查询的结果重新生成不完全树， 具体的实现在第四章。 图4 是不完全树的示例，其中p r o d u c t ，p r o d u c t 3 , p r o d u c t 2 a , 是己知信息的结点 而p r o d u c t 2 a ，p r o d u e t l ，p r o d u e t 2 b ，p r o d u e t 2 e 是条件树类型，其具体的内容如图3 所 示，不完全树的生成算法在后面详细介绍。 4 _ l ”哆c 越m r“ 图4 不完全树 2 4 5 用户提交查询条件的表示方式 j 在对半结构化数据的查询的研究方面，已经有很多的成果4 2 】，在本论文中 使用 1 】中所研究的表示方式p s - q u e r y ( p r e f i x - s e l e e t t i o nq u e r y ) 。 首先介绍一个概念，数据树的前缀数据树，假设数据树t - ， t 。 ，如果数据树t 是数据树t 的前缀树，则其满足以下条件： t 是t 的子树，并且t 中也包含有根绪点 ! 竺! 墼塑壁! 墼塑堡鱼垫查塑型塑 塑! ! 墨苎翌堕 五，d 中的命名规则和值映射都来自于五，u p s q u e r y 是一个简单的查询语言，用它来选择输入信息树中满足条件的前缀 数据树，这个查询语言虽然有很多限制，但是它是有效的。它从输入树的根_ 丌始 浏览，读取指定名字的结点，选择符合条件的结点，它也可以指定查询不含有某 个给定名称的结点的信息。 p s - q u e r y 的正式定义： p s q u e r y 是一个带有标记的树 ，其中t 表示棵树，凡将树中的 每个结点都定义一个标记，内部兄弟结点的标记必须不同，c o n d 将每个结点加 上一个条件，它是以下几个形式的组合唧，v ，v ，v ， v 其中v q 。 铡如： g u b e a t 图5 查询树1 章d b 芒a t 兰c a h l 摹 图6 查询树2 其中图5 的查询树l 表示查询所有的价钱低于2 元的电器产品的名字和价 格，图6 的查询树2 表示查询所有的带有照片的照相机的名字和图片。 2 4 6 有p s q u e r y 和输入数据树所生成的查询结果的表示方式 下面看一下对于给定的输入树和提交的查询条件。它们所生成的查询结果 ( 也是不完全树的一部分) 是如何得到的。 假定给定p s - q u e r , jq - 喵，a c o n d 以及给定输入数据树r ，这查询的结果 树包含下面的凡部分： 1 每一个属于p s q u e r y 的边 都输入结果树 ： 2 每一个属于p s - q u e r y 的结点都在输入结果树中 # 3 包含t 中所有的d ( n ) 满足c o n d ( n ) 的结点n 例如在 1 1 中所列举的查询l 的返回结果( 图7 ) 和查询2 返回的结果( 囤8 、： 一。 复且大学硕士学位论文 x m l 数据库中数据缓存技术的研究第1 7 页共5 9 页 图7 查询i 返回的结果 c 争删：# 奄 图8 查询2 返回的结果 j 酶 ! 翌! 鍪塑壁主塑塑堡生垫查蝗业垫 望! ! 坚蔓! 生 第三章不完全树中相关算法定义 3 1 不完全树的生成算法 每当用户提出个新的查询，那么缓存了数据的不完全树就要根据用户提交 的查询条件生成一个新的不完全树，下面介绍不完全树的生成算法。 算法的输入是： t ：不完全树 q ：p s 。q u e r y a ：也就是q ( t ) ，q 的查询结果 算法的输出是： t7 ： 结合查询的结果a ，查询的条件q ，t 生成的新的不完全树 对于输入的查询结果a ，根据前面讨论的处理数据的o w a 方法，则可能还 存在的数据用g 。( a ) 表示，但是现在只关心在已经存在的得到缓存的不完全树中 可能含有的未知信患因此输出的新的t 应该满足以下条件： r e p ( t ) = r e p ( d n 一( a ) 为了，土成需要的新的不完全树t ，需要两部分的数据： c t t y p e ：条件树类型部分，其代表未知的数据部分。 t d a t a ： 已知的数据树结点部分。 3 1 1 如何获得c t t y p e 数据部分 3 1 1 1 计算对于查询q 返回空集的条件树。 首先举例说明对于一个具体的查询q 返回空集的所有条件树，然后对于任何 一个查询q ，j 下式定义如何得到返回空集的条件树。 举例说明：假设q 是要求查询所有的带有图片的照相机，其对应的查询树f 。 如图9 所示： 1 q 图9 查询所有带有图片的照相机 复星大学硕士 e g t 论文 兰坚! 墼堡塞! 墼塑堡堡垫查盟型塞塑j 旦堕苎! ! 旦 则g 。共分为三种情况，如图1 0 所示 第 况 盯叶 t 。= 仲d u c t c a t 5 e l e 。n 缸脏孙饿= d 赫略尊i j 图1 0 对于查询q 返回空集的条件树 薷兰种情 况 第一种情况：所有的带有图片，但是不属于电子仪器的商品。 第二种情况：所有的带有图片，属于电子仪器的，但是不是照相机的商品。 第三种情况：所有的不带有图片的照相机。 下面是对q - i 的具体定义： 对于蛮询树t q 中每一仑结点矗 生成瓶的类型t 。，己，乞，用l 表示在输入数 据树中结点a 的标记，则为这些新的类型规定了其标记映射，z 。盯( f 。) _ 仃7 ( l ) - - , r ( 乞) 。，。表示所有的以a 作为根结点，并且满足查询条件的子树，其不 包含在条件树中，表示接受结点a 的所有的后继结点，因为结点a 已经不满足 查询条件，乞表示结点a 满足查询象件，而必有一个a 的后继结点不满足查询的 条件。下面给出具体的定义： i 艺j f ：e ：表示接受所有的a 结点的后继结点 2 之一u ，t 0 2 i f 二，表示结点a 满足条件，而必有一个a 结点的后继结 点不满足查询的条件 计算q “的算法复杂度为o ( i q l i s l ) ，其中l q j 表示查询树的大小，而l sj 表示查 询书中结点的最大子结点数目。 3 1 。1 2 计算t ，中的条件树类型 如前面所讲，生成的新的不完全树| r 中的条件树类型部分是有q 所生成的 条件树类型和输入信息树t 中的条件树类型的结合，下面举例说明两者是如何i 结合的。 。 假设已知不完全树的条件树类型为p r o d u e t l ，p r o d u c t 2 ，如图1l 所示，p r o d u c t l 表示所有的不是电子仪器的产品，p r o d u c t 2 表示所有的价格大于等于2 0 0 的电 子仪器。 复旦大学磺士学位论文 兰竺! 塾墅堕茎塑堡堡垫_ 术塑坐壅 至上生堕苎! ! 生 s u b c a t s u b c a l 图11 已知不完全树的条件树类型 p r o d u c t l ，p r o d u c t 2 与结果的第一种情况相结合，生成的条件树类型如图1 2 所示的p r o d u c t l ，它表示所有的不是电子仪器的产品。p r o d u c t l ，p r o d u c t 2 与结 果的第二种情况相结合，生成的条件树类型如图1 2 中的p r o d u c t 2 b 所示，它表示 所有的价格大于等于2 0 0 元的不是照相机的电子仪器。p r o d u c t l ，p r o d u c t 2 与结 果的第三种情况想结合，生成的条件树类型如图1 2 的p r o d u c t 2 c 所示，它表示所 有的价格大于等于2 0 0 元，并且不带有图片的照相机。 p r o d u c t l s u b c a t p z o d u c t2 c ；：e l e c s u b c a t ! ：c 础r a s u b c a ：c a c r t 图1 2 p r o d u c t l ，p r o d u e l 2 与结果的三种情况相结合 因此新的不完全树t 的条件树类型为p r o d u c t l , p r o d u c t 2 b , p m d u c t 2 c ，并定义 映射盯，使f 寻 r ( p r o d u c t l ) = r ( p r o d u c t 2 b ) = r ( p r o d u c t 2 c ) = p r o d u e t 。 现在已经形成了新的不完全树t ，的条件树类型。下面进一步讨论如何生成 新的不完全树t 中的已知信息结点。 复虽大学硕士学位论文 x m i ，数据库中数据缓存技术的研究 3 1 2 计算t 中t d a t a 结点 t t 已知信息结点是t 中已知信息结点和a 的结合，它包含三类数据： 第一类：在t 中已知信息结点和a 中都存在的结点集合 例如，在上面的例子中的查询】和查询2 都返回的结点集合满足条件：价钱 小于2 0 0 元，并且具有图片。在查询1 中返回的结果中有c a n o n 结点，而查询2 中返回的结果中也有c a n o n 结点，假设这两个结点代表的照相机是一样的，那 么这两个结点可以合并到一起，形成新的不完全树中的数据结点如图1 3 中的 p r o d u c t 所示。 第二