（计算机软件与理论专业论文）xml数据存储、转换和索引.pdf

摘要 摘要 x ml正在取代 h t m l成为互联网上信息发布和交换的标准。与 h t m l相 比，x ml简单，自我描述，实现了内容、结构和表现三者的分离，更适合于数 据表示和交换。近来，x ml在各种应用中得到了广泛的使用，w e b 上涌现了海 量的x ml数据。为了有效地加工、分析和处理 x ml数据，研究者们己经提出 了各种x ml的查询语言和存储管理技术。在存储管理x ml的各种可能的方式 中， 基于关系数据库的x m l数据存储和文件系统存储成为了两种最为流行的方 式， 受到了 广泛的关注。 然而， x m l和传统的关系数据与文本信息在数据模型、 查询语言和应用场景等方面存在着较大的差异， 处理x ml数据给传统的存储和 查询技术带来了许多新的问题和挑战。针对x m l数据管理带来的新问题， 本文 研究了x ml数据在关系数据库中保持语义的存储模式、x ml数据在关系数据 库中的路径索引、 x ml数据转换和相关索引 等关键技术， 提出了 有效的算法并 在原型系统中加以实现。本文的主要贡献总结如下: 1 )在结构化映射的基础上综合的考虑了d t d和x m l 键， 得出映射到可保 持键约束的关系模式的规则，并在此规则上把 x m l键保持约束关系地 映射成关系数据库上的函数依赖。从而可以 把x m l文档保持约束完整 性地存储到关系数据库中。 2 )为了降 低关系数据库中构建结构化映射的空间开销， 提出了基于给定查 询负载的查询代价，设计最优的路径索引 模式的方法。 3 )定义了e x t g 一 种灵活的x m l 转换方 法， 并且实 现了 在w e b 服务 环 境中转换的x ml数据到指定的模式。 4 )提出在x m l转换中为中间结果建立索引。因为在许多查询过程中中间 结果会被反复查询， 所以建立中间结果的索引可以很好的提高查询的执 行效率。 5 )设计了一种新的适用于x ml 转换查询的索引结构， f i x t 。 该索引不但 能有效的加快查询效率，而且易于抽取和重构子索引。提出了在 x ml 转换中应用 f i x t的一些优化方法。这些方法也同样适用于其它的转换 语言。 关键字: x m l语义保持 路径索引 转换 柔性索引 ab s t r a c t x ml h a s b e e n b e c o m i n g t h e d e f a c t o s t a n d a r d f o r i n f o r m a t i o n p u b l i c a t i o n a n d e x c h a n g e o n t h e we b , s u b s t i t u t in g f o r h t m l . c o m p a r i n g t o h t m l , x m l i s s i m p l e , s e l f - d e s c r i b i n g , a n d t h e c o n t e n t , s t r u c t u r e a n d r e p r e s e n ta t i o n o f x m l d o c u m e n t s a r e in d e p e n d e n t , w h i c h m a k e s x m l m o r e s u i t a b l e f o r d a t a r e p r e s e n t a t i o n a n d e x c h a n g e o n th e i n t e r n e t . r e c e n t l y , x ml h a s b e e n w i d e ly u s e d i n v a r i o u s a p p l i c a t i o n s , a n d v e ry l a r g e v o l u m e s o f x ml d a t a h a v e b e e n a p p e a r e d i n t h e we b . t o o r g a n i z e a n d m a n a g e x m l d a t a e f f i c i e n t ly , d i f f e r e n t q u e ry la n g u a g e s a n d s t o r a g e a p p r o a c h e s h a v e b e e n p r o p o s e d . a m o n g t h e s e a p p r o a c h e s , u s i n g r d b ms a n d f i l e s y s t e m b e c o m e t h e m o s t t w o p o p u l a r w a y s . h o w e v e r , d u e t o t h e d i f f e r e n c e s b e t w e e n d a t a m o d e l s , x m l d a t a p r o c e s s i n g b r i n g s u p n u m e ro u s c h a l l e n g e s f o r t r a d i t io n a l t e c h n i q u e s f o r x ml d a t a i n r d b ms , t h i s d i s s e r t a t i o n s t u d i e s t h e i s s u e s o n x ml s t o r a g e w i t h c o n s t r a i n t s , a n d b u i l d i n g p a t h i n d e x e s ; f o r x ml d o c u m e n t s i n f i l e s y s t e m s , s t u d i e s o n x ml t r a n s f o r m a t i o n a n d fl e x i b l e i n d e x s t r u c t u r e . t o t a l l y , t h e c o n t r i b u t i o n s o f t h i s d i s s e r t a t i o n c a n b e s u m m a r i z e d a s f o l l o w i n g : 1 ) a d d r e s s e s t h e p r o b l e m o n h o w t o k e e p t h e i n t e g r i t y o f x ml d o c u m e n t s w i t h d t d s a n d x m l k e y s w h i le s t o r i n g t o r e l a t i o n a l d a t a b a s e s . t o t h i s e n d , w e f i r s t d e v e l o p a n a l g o r i t h m t h a t t a k e s i n a c c o u n t b o t h d t d a n d x ml k e y c o n s t r a i n t s t o g e t t h e c o r r e s p o n d i n g r e l a t i o n a l s c h e m a . a n d u n d e r t h i s s c h e m a x ml k e y c o n s t r a i n t s a r e m a p p e d i n t o f d s . t h u s w e h a v e s t o r e d x m l d o c u m e n t w i t h d t d s a n d x m l k e y c o n s t r a in t s t o r e l a t i o n a l d a t a b a s e a n d k e e p t h e i n t e g r i t y c o n s t r a i n t s . 2 ) s t u d i e s a n e w i n d e x s t r u c t u r e , s t r u c t u r a l ma p , f o r e f f i c i e n t e v a l u a t i o n o f p a t h e x p r e s s i o n s q u e r i e s o f x m l . w e p r e s e n t a c o s t m o d e l f o r t h e s p a c e c o n s u m p t i o n o f i n d e x e s a n d t h e i r r e s u l t i n g b e n e f i t t o x ml q u e r i e s . f o r a g i v e n w o r k l o a d , w e a d o p t g r e e d y a l g o r i t h m t o s e l e c t s o m e m a p i n d e x e s t o b e c r e a t e d . t h a t i s , u n d e r c e rt a i n c o n s t r a i n t o f d i s k s p a c e , t h e s e s e l e c t e d m a p i n d e x e s c a n b r i n g t h e m o s t b e n e f i t . t h i s r e s e a r c h p l a c e a s o l i d b a s e f o r d e s i g n o f q u e ry o p t i m i z e r a n d i n d e x o f x ml d a t a . 3 ) c o n s i d e r s d t d - d i r e c t e d x m l i n t e g r a t i o n i n t h e p re s e n c e o f w e b s e r v i c e s . we e x t e n d xml t r a n s f o r ma t i o n g r a mma r x t g t o e xt g . 4 ) i l l u s t r a t e s b u i l d i n g i n d e x f o r i n t e r m e d i a te r e s u l t s f r o m t h e s o u r c e i n d e x i n ab s t r a ct x ml t o x ml t r a n s f o r m a t i o n . s i n c e i n t e r m e d i a t e re s u l t s w o u l d b e q u e r i e d fr e q u e n t l y d u r i n g t h e p ro c e s s , i n d e x in g t h e m c a n m a k e s i g n i f ic a n t i m p r o v e m e n t 5 ) d e s i g n s a n e w i n d e x s t r u c t u r e , f i x t , w h i c h i s s u i t a b l e f o r x ml t o x ml t r a n s f o r ma t i o n . t h e i n d e x s t r u c t u re i s e f f c i e n t i n n o t o n l y q u e ry e v a l u a t i o n b u t a l s o i n d e x r e c o n s t r u c t i o n . t h e d i s s e rt a t i o n a l s o d e v e l o p s s o m e t e c h n i q u e s t o u s e o u r i n d e x i n x t g p r o c e s s i n g . a n d t h e s e t e c h n i q u e s a r e a p p l i c a b l e t o o t h e r q u e ry l a n g u a g e s . k e y wo r d s : x ml , c o n s t r a i n t s - p re s e r v e d , s t r u c t u r a l m a p , t r a n s f o r m a t i o n , f l e x i b l e i n d e x 第一章 绪论 第一章 绪论 1 . 1研究背景 在过去的十年里。数据库研究在查询优化、对象一 关系数据库、 主动数据库、 并行数据库和数据挖掘等领域取得了突破性的进展。 许多研究成果己被成功地转 化到商业产品中。同时，在过去的十年中，i n t e r n e t技术和计算机硬件的发 展使得我们有必要进一步拓展数据库理论，研究新的问题，开发新的技术。 今天， 任何人都可以在国际互联网上轻易地发布和获取信息。 w e b己 经变成 了 信息制造、 发布、 加工和处理的主要平台。同时， 随着因特网 ( i n t e r n e t ) 的迅 速发 展，网 站 和静态h t m l ( h y p e r - t e x t m a r k u p l a n g u a g e , 超文 本标记 语言) 页面也急剧膨胀，到 1 9 9 9 年底， i n t e rn e t 上的静态页面有3 5 0百万，同时每天以 i 百 万的 速度增加 c h a 9 9 ， 信息的 数 量 级从9 0 年代 初的m b过 渡到g b 、 现在 已上升到t b . 尽管 h t ml从发明以来，己成为最成功的电子发布语言，但是它仅注重信 息的表现形式， 它的标记仅仅反映了信息应该如何在页面上表现， 而没有对信息 本身进行描述，同时它的标记集合是固定的， 不能够根据需要进行扩展。 使用传 统的基于关键字的信息检索方法在 we b这样一个无限的信息海洋中往往会迷失 方向， 用户得到的是无穷无尽的 链接， 且绝大多数链接所包含的文档并不包含用 户所需要的内容，而用户却为此耗费了大量的时间和金钱。随着 w e b应用的日 益广泛，它 的局限性越来越明显，己 经不再适应下一代更复杂的 w e b应用。因 此，在未来的w e b 发展中，如何提高信息检索的准确性和效率成为关键问题。 可 扩展标记语言 ( e x t e n s i b l e m a r k u p l a n g u a g e ， 简称x m l ) 的出 现改 变了 we b 的基本面貌。 1 9 9 8 年2 月， w3 c ( 全球互联网联盟) 给出了其正式的x ml l 0 版本，并正式推荐x m l成为下一代互联网标准。与h t m l 相比， x ml 具有许 多优点: 1 ) x m l 简单，自 我描述且易于解析。 使得x m l 具有机器可读性， 一个应 用可以按照各种方式解析、过滤、重构x ml文档。 2 ) h t m l中的标记是固定的，不能扩展，而x m l的标记由 用户定义，可 以任意地扩展。 x ml的嵌套结构可以表示现实世界中各种复杂的对象， 各种格式的数据都可以比较容易地转化为 x ml数据，这使得 x ml非 常适于we b 信息的发布和集成。 3 ) h t m l中的 标记表示的 是数据的显示格式， 没有任何语义， 而x m l 的 标记则明确指出了数据的含义， 使得细粒度的x ml数据处理成为可能。 6 第一章 绪论 4 ) x m l实现了内容、结构和表现二者的分离。文档类型定义 ( d t d ) 描 述了文档中元素和子元素间的嵌套结构，不同的用户可以通过 x s l按 不同的显示方式显示全部或部分的文档内容。 x m l自 发布以来受到了各界的广泛关注。各计算机厂商们竞相推出了 支持 x m l的产品( 如: o r a c l e 9 i 中的x m l s q l u t i l it y , i b m d b 2中的x m l e x t e n d e r m i c r o s o f t s q l s e r v e r 2 0 0 0 中的x m l a n d i n t e r n e t s u p p o rt 等) : 学术和研究机构纷纷采用x m l 来表示各种科学数据， 并展开了对x m l的 深入研究。 联合国正逐步加大制订全球性x ml 标准的力度， 它的u n / e d i f a c t 与o a s i s 组织共同发展了e b x ml 。各个行业如金融机构、 海关、 媒体产业正制 订各自 行 业的x m l d t d ( d o c u m e n t t y p e d e f i n it i o n ， 文 档 类型定义) ， 以 利于 数 据以公认的格式交换和集成. 目 前， i n t e r n e t上己 经涌现了大量的x m l 页面、 站点和应用开发工具。可以预见， x ml将成为w e b 信息发布和交换的事实上的 标准。国外己 形成了x m l的一系列标准. 如c x m l , x c b l , b i z t a l k , e b x ml 0 在我国， 中国科学院电子商务研究中心也正联合国内 软件厂商制定c n x m l 标准。 总之， 对 x ml的深入研究将有力促进企业的信息化和电子商务，具有巨大的应 用前景和经济效益。 在x ml引起的w e b 变革中， 数据库技术将扮演关键的角色。 从数据处理的 角度来说，传统的 w e b信息处理主要采用的是信息检索技术。 检索信息的主要 方式是关键字搜索。 关键字搜索极不准确， 检索的结果将返回包含关键字的整个 文档， 网络传输量大。 x m l 使得我们可以采用数据库技术来存储、 检索、 分析、 加工和处理we b 信息。具体地说: 1 )传统的w e b 信息管理主要处理的是 静态的w e b 页面， 利用数据库中的 成熟技术可以 保证动态更新的w e b 页面的数据一致性。 2 )利用数 据库 技术可以 及时、 有效 地分 析 和加工 在线的x m l数 据， 从中 发现有用的知识，辅助企业决策。 在今天的w e b 环境中，大的w e b 站点和搜索引擎却主要用文件系统来存储 信息，利用信息检索 ( i n f o r m a t io n r e t ri e v a l , 简称i r ) 技术 ( 如:关键字搜索) 来检索静态的 h t ml页面， 效率低下而且极不准确。随着 w e b页面数量的快 速增长，新的w e b 应用要求w e b 能够管理动态的内容，w e b 用户需要在浩如烟 海的w e b 信息海洋中快速、准确地发现所需的信息。 x ml由于自身具有结构信 息， 可以 很好的满足这种需求: 使用类似于数据库的查询语言的方式来检索x m l 文档， 搜索引擎的功能将变的更加强大而准确。 此外， 查询结果将只返回与查询 匹配的部分而非整个文档，大大降低了网络传输量。 第一章 绪论 1 . 2研究现状 x ml与传统数据库中的结构化数据不同，x ml数据是自 我描述的，没有 预先固定的模式。 x m l 与数据库界近年来研究的 半结 构化数据( s e m i - s t r u c t u r e d d a t a ) b u n 9 7 , s u c 9 8 极为 相 似。 半结构 化数据己 有的 理 论和原 型系 统可以 作为 x ml研究的基础。同时，x ml所具有的独特特性又为我们带来了新的研究课 题。 由于x ml与半结构化数据的相似性，人们可以将x ml看作是半结构化数 据的标准，并借鉴半结构化数据的研究成果来管理 x m l数据。目 前，数据库 界在半结 构化数据的 研究方 面己 取得了 一定的 进展。 这包 括数 据 模型 p g w 9 5 , 查询语言 b f s 0 0 , g w 9 7 ，半结构化的模式 g w 9 7 ，查询和查询优化技术 f m l 9 9 , h g i + 9 5 , m w 9 9 a , b d h + 9 6 ， 索引 技术 m w a 十 9 8 , m s 9 9 a ， 半结构 化 路 径 约束 b f w 9 8 , a v 9 7 , f a n 9 9 ， 半结 构化中间 件和 视图 机制 l y v + 9 8 , m p q + 9 7 , p v 9 9 ， 半结构化 模式 抽 取【 a a c + 9 9 , n a m 9 8 , m s 9 9 b ， 半结 构化 数 据管理系 统 q w g + 9 6 , h g i 十 9 5 , m a g 十 9 7 , w e b 站点 管理 f y l + 9 9 , f y v + 0 0 , f f k + 9 8 等。 关于半结构化数据研究的综述见【 b u n 9 7 , a b i 9 7 , 但是，目前的半结构化数据的研究尚不成熟， 并且x ml与半结构化数据相 比又存在一些差别， 这主要表现在: 从数据特点上看， x ml文档中的元素有次 序， x ml文档可带有描述其结构的 d t d :从应用领域来说，x ml不但被用 于表示w e b 数据，也面向电 子数据交换。因此，需要对x m l 数据作进一步深 入的研究。国外的许多大学、研究机构和各种基金都己经或正在开展 x ml数 据处理技术的研究。目 前国际上正在开展的 x ml数据管理的主要研究项目如 表1 .2 所示。 另 外， i b m , m i c r o s o ft , o r a c l e 等各大数 据库厂商的研究 机构也都有 对x ml技术的专项研究 ( 未在表 1 . 1 中列出) 表l . l : x ml 致据管理的研究项目 项目 名称 研究机构或院校 研究重点we b 地址u r l ni agarawi s c o n s i n ma d i s o n 大学 x ml 的查询和搜索 引孚 h 仰: l / w w w .c s .w i s c . e d w n i a g a r a i m i x加州 大学 s a n d ie g o 分校 ( u c s d ) x m l数据中间件h t t p :/ / f e a s t . u c s d . e d u / p r o j c c t s / mi x / x ml d a t a m a n a g e m e n t wi s c o n s i n ma d i s o n大学 存储， 管理x m l 数据h ttp :/ / d a t a .c s .w a s h i n g to n .e d u / x ml l t u k wi l awa s h in g t o n 大 学 基于x m l 的数据 集 成 h t t p j / d a m c s m a s h in g t o m e d u / x ml / x ml . ql a t 2 .3 节讨论几种目 前最有 代表 性的基于关系的x ml 数据存储方法. x m l m . f r a n k li n f r a n k l i n f u d a n . e d u . c n m . f a n k l i n q u e ryx m l . . 2 0 0 1 i . s mit h d a t a m i n i n g p r o j e d / . s mit h a n a l g o r it h m. . . 1 9 9 9 图2 . 1 :一个x ml文档样例 2 . 1 x ml和 d t d w3 c提出的标准超文本标记语言 x m l ( e x t e n s i b l e m a r k u p l a n g u a g e ) b p s + 9 8 是一 种用于i n t e rn e t 上交换和表 示数据的 格式。 一 个x m l文 档由 嵌套 的元素层次结构构成。 每个文档有一个唯一的根结点。 一个元素有一个标记( t a g ) , 描述该元素的含义。 一个元素由从起始标记到终止标记的区域构成。 该区域可以 是嵌套的子元素，也可以是属性或文本申值。图2 . 1 显示了一个描述一个研究项 目 信息的x i v ii , 文档样例。 该 文 档的 根为 项目p o rj e c t 元素， p o rj e c t 元 素 包 括 从 起始 标记 到 终 止标记 部分的文档区 域。 图中 描 述的 项目 有 3 个子元素， 一个为 描述 第二 章 x m l 及相关技术 项目 名的 元素p r o j e c t n a m e ， 另 两个为 描述 项目 成员的m e m b e r 元素. 其中， 第一 个m e m b e r 成员由描述成员名的子元素n a m e 、 描述成员的电子邮件的e m a i l 子元 素、 和描述该成员发表的 论文信息的子元素 p u b li c a t i o n构成。 这里的子元素 p u b l i c a t i o n 又由 子元 素a u t h o r , t it le 和y e a r 构成， 分别 表示 该论文的 作者、 标 题 和出版的日期。第二个成员则仅由描述成员名的子元素n a m e 和描述该成员所参 与的 项目 信息的 子元素p r o j e c t 构成。 注意 在每个 成员m e m b e r 的 起始标记内 都有 一个属性m e m b e r i d ， 表示该成员的标识、 从图2 . 1 中， 我们可以看出x m l文档 的如下几个特点:1 ) 一个元素可以由 其一个或多个子元素描述，如:第一个 m e m b e r 元素， 也可以 为一个字符串 构成的文本， 如: p r o j e c t n a m e ， 在后边的 章 节中，我们有时也将这两种元素分别称为复合元素和原子元素: 2 ) x m l数据是 半结构化的数据， 一个元素可以 有多个标记相同的子元素， 且标记相同的子元素 可能具 有不同 的 结构， 如: p r o j e c t 有两 个异构的m e m b e r 子 元素。 一 个x m l 文 档 可以 解 析( p a r s e ) 为 一 棵 树。 d o m模 型 ( w w w .w 3 .o r g / d o m o 定义了一个x m l文档在内存中的树型表示方式和遍历文档的基本操作的接口。 应用程序可以通过 d o m接口方便地处理x ml文档。 文 档类型 定 义d t d ( d o c u m e n t t y p e d e f i n i t i o n ) 描 述x m l 文 档的结 构， 我 们可以 将 d t d看作是x m l数据的模式或类型。与传统数据库中的模式相比， d t d的定义要灵活和复杂得多。d t d以上下文无关文法的方式描述文档中的元 素和属性间的嵌套关系。 d t d使用几个操作符: *( 表示0 个或多个) 、 十( 表示 1 个或多 个) 、?( 表示0 个或i 个) 和 ( 表示 选 择) 来描 述元素和子元素间的 关系。 d t d描述中的所有值类型均被假定为是字符串 值， 除非由关键字a n y定 义 ( 此时，值类型可以是任意的文档片段) 。一个元素类型可以由多个子元素类 型或属性定义。其中， i d和i d r e f 是两种特殊的属性类型，一个元素至多只能 有一个i d属性，而一个i d属性唯一标识了一个元素.一个元素的i d属性可以 被同一文档中的另一个元素的i d r e f 属性引用。 i d r e f 属性没有类型。 在d t d 描述中没有根的概念，符合于一个d t d描述的x m l 文档的根结点可以为d t d 中的任意一个元素。 例如， 图2 .2 给出了图2 . 1 中的文档的d t d描述。 可以看出， 图2 . 1 中的文档片 段的 根结点为图2 .2 中的d t d中定义的 ( 非根) p o r j e c t 元素。 一个符合x m l的标记规范的文档被称为良 构 ( w e l l- f o r m e d ) 的文档。 一个良 构 x m l文档可以没有d t d定义。一个符合于某个给定的d t d定义的文档被称为 有效 ( v a l i d ) 的文档。 例如，图2 . 1 中x m l文档的相对于图2 .2 中的d t d是有 效的. 图2 .2 的d t d样例定义了 一个实 验室的文档类型。 一个la b o r a t o ry元素有一 个 子元素la b n a m e , 0 或多 个 子元素m e m b e r 。 一个p r o j e c t 有3 个子 元素p r o j n a m e . 第二章 x m l及相关技末 0 或多个m e m b e r , 0 或多个p u b l i c a t i o n 子元素。m e m b e r 由一个子元素n a m e , 0 或一个e m a i l , 。 或多 个p u b l ic a t i o n , 0 或多个p r o j e c t 子元素和m e m b e r i d属性构 成。 这里的m e m b e r i d属 性由 关 键字 # r e q u i r e d描 述， 表示 每个m e m b e r 必 须 有一 个 b e r i d 属性。 p u b l i c a t i o n 又由0 或多 个a u t h o r , 一个t i t le 和一个y e a r 子 元素定义。其它元素都为原子元素，被定义为文本串# p c d a t a 。关于 x m l和 d t d规范的详细描述见w3 c的相关标准 ( h tt p :/ / w w w .w 3 .o r g / x m l / ) . 图2 .2 :一个d t d样例 2 . 2 x ml查询语言 研究者们 已提出了各种 x m l 的查询语言，如:u n q l b d h 9 6 , l o r e l a q m+ 9 7 、x q l r l s 9 8 、x ml - q l d f f + 9 8 、x ml - g l s c d + 9 9 、 q u i l t c r f 0 0 和x q u e ry c f r + 0 1 。 所有的 查询语言均使用路径表达式来遍历 x m l文档中的元素嵌套结构，有的查询语言还使用元素构造语句来生成嵌套的 结果文档。 在本节中， 仅简要介绍3 种有代表性的查询语言: l o r e l m a c + 9 7 , x m l - q l d f f + 9 8 和x q u e ry c f r + o l 。 关 于x m l 查 询语言的比 较 分析见 b 0 0 0 , l c 0 0 o 让我们首先考虑一个查询 “ 检索参与 x ml项目的成员发表的文章” 。该查 询的l o r e l 语句描述如图2 .3 ( a ) 所示。 可以 看出 ， 一 个l o r e l 查 询 包含 “ s e l e c t , 竺 加rn ” 和 “ w h e r e ” 三个部分。 其中， 加， ” 语句绑定实验室的所有 m e m b e r 成员，变量 x表示这些成员， w h e r e ”设置在这些 m e m b e r上的条件 x .p ro j e c t p ro j n a m e = x m l ， 而“ s e l e c t 描述 输出 项为 成员 的p u b l i c a t i o n . 图2 .3 ( b ) 显示了 该查 询的x q u e ry语句。 一 个x q u e ry语 句是 一个f l w r ( f o r - l e t - wh e r e - r e t u rn) 表达式。 f o r ”语句用于描述目 标元素( 用变量表示) ， 第二章 x ml 及相关技术 l e t 语句用于描述对整个路径表达式的变量绑定， w h e r e 语句设置在目 标 元素上的条件， r e t u r n 语句构造返回的结果。 在图2 .3 ( c ) 中， f o r 语句 中的变量$ p首先绑定 m e m e b r ，然后， w h e r e ” 语句在变量$ p上设置条件 $ p / p r o j e c t/p r o j n a m e = x m l ，最后， r e t u r n 语句构造返回的结果 $ p o f o r 和 l e t 语 句 都 是可 缺省的 ， 如: 图2 .3 ( b ) 中的x q u e r y 查询就没有 l e t ” 语句。 s e t e d x . p u b l ic a t i o n f r o m l a b o r a t o ry. me mb e r x wh e r e x . p r o j e c t . p roj n a me = x m l ( a ) l o r e l查询 f o r $ p i n / la b o r a t o ry/ me mb e r wh e r e $ p / p r o j e c t / p r o j n a me = x m l r e t u r n $ p / p u b l ic a t io n ( b ) x o u e r v查询 wh e r e $ p x m l c o n s t r u d $ p ( c ) x m l - q l查询 图2 .3 : 三种查询语言样例 图2 . 3 ( c ) 给出了同 一查询的x m l - q l语句。 可以 看到， 一个x m l - q l语句 由一个 “ w h e r e ， 语句和一个 “c o n s t r u c t ” 语句构成。 w h e r e 语句绑定待检索 项所处的文档片段， 而 c o n s t r u c t 语句描述输出 项及其输出 方式。图2 .3 ( b ) 中 的 “ w h e r e ” 语句中的 变量 助绑定l a b o r a t o ry中 参与x m l 项目 的m e m b e r 成员， c o n s t r u c t 语句输出这些成员发表的文章，并用标记 显示输出 项. 注 意 c o n s t r u c t ” 语 句 通过t a g 标 记 语 句可以 构 造 任 意 层次 嵌 套的 元素 结 构， 而l o r e l不具有重构文档的功能。 x m l查询语言的基本成分是路径表达式。而在这三种查询语言中的路径表 达式具有不同的形式， 在l o r e l中，路径表达式是由点号 “ . ” 连接的结点标记 系列， x q u e ry使用x p a t h c d 9 9 a 表达式，一条路径是由“ /连接的结点标记 系列，而 x m l - q l 则隐式地用标记的嵌套结构表示路径，例如， ”实际上相当于 l o r e l中的路径表达式 第二章 x m l 及相关技术 m e m b e r p ro j e c t p ro j n a m e” 和x q u e ry 中 的 路 径 表 达 式 m e m b e r /p ro j e c t/p ro j n a m e 。本文将在后边相关的章节中详细地讨论路径表达 式。 2 . 3基于关系的x ml数据存储方法 本节介绍两种在后边的章节中将要用到的几种经典的关系存储模式。 其中两 种为 独立于文 档的x m l关 系 存储映 射: e d g e 和b i n a ry方 法， 另 外两 种为 依赖 于文档的关系存储映射:s h a r e d 和h y b r i d 方法。 2 .3 . 1 e d g e 和a t t r i b u t e 映射 f l o r e c u 和k o s s m a n 在 f k 9 9 1 中提出了 两种将x m l 文档映射为关系数据库 的 存储方法e d g e 和b i n a ry存储， 及其6 个变种。 方便起见， 我们在本章中 介绍 其中的 两种基 本方 法: e d g e 存储和a t t r i b u t e 存 储。 e d g e 映 射将整个x m l 文 档模型 化为 一个 有向 图， 再 将整个有向图 存储在 一个关 系 表 “ e d g e ” 中。 x m l 文 档中 的 每 个结点首 先 被赋 予 一个唯一的 标识( i d ) . e d g e 表中 的 每个元组 存储有向 图中的 一 条边， 包含 边两 端的结点 标识 ( 分别 存 储为s o u r c e 和t a r g e t ) ，目 标结点的 标记， 和一 个 表示结 点 在有向 图中的 次 序的 属性。 r d i n a l 。此外，原子结点的文本串也被存储为一个属性v a lu e( 详细映射过 程见 f k 9 9 1 ) 。 例如，图2 . 1 中 的x m l 文 档被映 射为图2 .4 所示的 关系 表， 其中 的结点标识即深度优先遍历x m l的d o m树的次序， 如: 元组 ( 1 , m e m b e r , 1 , 3 , n u l l ) 存储了图2 . 1 中的第一个m e m b e r 元素。 e d g e 映射与x m l文档的结构无关， 在x m l 存储映 射时 不需要d t d或模 式信息。 然而， e d g e 映射 重复 存储x m l 文 档中 的 元 素和 属性的 标记名， 包 含大 量的冗余信息，同时， 我们将在后边的章节中看到， 将整个文档存储在一个关系 的查询处理效率十分低下。 b i n a ry方 法中的a t t r i b u t e 映 射将e d g e 表按 照 标记 名 水平划分成多 个关系 表， 每个关系表对应一个元素/ 属性类型。例如，图2 . 1 中的x m l文档将产生 t o 个 关系: p r o j e c t , p r o j n a m e , m e m b e r , m e m b e r i d , n a m e , e m a i l , p u b l i c a t i o n , a u t h o r , t i t l e 和y e a r 。 每个关系 包含结点 的i d ， 文 本值及其 在兄弟结点中 次 序。 与e d g e 方法相比，a t t r i b u t e 映射更加简洁。 然而，由 于没有保存边的信息， a t t r ib u te 方 法在查询处理时需要用到文档的d t d来确定元素间的父子关系。同时，对于元 素类型较多的文档，a t t r i b u t e 映射将产生大量的关系表。 第二 章 x m l 及相关 技术 s our ce t a g o r d i n a l t r a g e t v a l u e 0 p r o j e c t 0 1n u l l ip r o j n a me 02. , xnm ime mb e r 13n u l l 1me mb e r 21 1n u l l 3me mb e r i d 04 2 )*结点的 儿子结点( 即将值集元素作为单独的关系保存) ; 3 ) 出现在环上的入度为 1 结点。 映射生成的关系以这些结点的元素标记命名。d t d 图中的其它 ( 入度为 1 的)结点被内联为其最近祖先结点对应的关系的某个属性。为了 保存边的信息， 每个关系中保留被映射为关系的结点的 i d 标识作为关系的主键，并增加一个 p a r e n t l d列保存其父结点