（计算机软件与理论专业论文）基于多dtd的xml查询技术研究.pdf

摘要 摘要 x m l ( e x t e n s i b l e m a r k u pl a n g u a g e ) 已成为一种网上数据交换和信息集成的工 具。随着x m l 应用的普及，对x m l 文档查询的要求也就越来越高。本文对相关 领域遵循多d t d 的x m l 文档查询方法开展研究，主要解决以下几个方面的闯题： 1 ) 如何使用户在构造x m l 查询时无须了解待查x m l 文档的结构? 2 ) 如何实现 对相关领域遵循不同d t d 的多类x m l 文档的统一查询? 3 ) 如何实现x m l 文档 的结构相似性查询? 具体地，本文的主要研究结果有： 1 基于多d t d 的x m l 索引方法。为了提高x m l 路径查询的效率，人们致力于 x m l 索引的建立。本文提出一种x m l 索引方法d b x i ( d t d - b a s e dx m l i n d e x i n g ) ，其中心思想是发掘d t d 中隐含的结构信息，提高x m l 文档路径查 询的效率。d b x i 的主要特点是：1 ) 采用了新的x m l 编码方法，使x m l 文 档中每个元素，属性的编码携带了相应的d t d 结构信息；2 ) 对一个由n 个元素 ，属性组成的有一个谓词约束的路径表达式，d b x i 处理每个x m l 文档，由同 类系统x i s s 所需的至少n 1 次结构连接运算降低至0 次或2 次结构连接运 算；3 ) 如果查询路径在待查x m l 文档中不存在正确的匹配结构，d b x i 能够 在比国际上的s p h i n x 和x i s s 等x m l 索引方法较短的时间内给出无查询结果 的判断。实验表明，对莎士比亚戏剧和d b l p 等x m l 数据集，d b x i 的路径查 询效率较l o r e 、s p h i n x 和x i s s 有不同程度的提高。 2 基于多d t d 的x m l 查询方法的研究为了实现对相关领域基于不同d t d 的 多类x m l 文档的统一查询，本文对“候选d t d 定位”、“候选d t d 与用户查 询结构的距离排序”等技术进行了详细讨论。在对候选d t d 与用户查询结构的 距离进行接近线性时间复杂性的排序运算时，提出了以“树间亚距离律序”代 替“树间距离排序”的观点，即以查询结构与查询在候选d ) 中的上下文之间 的距离，代替查询结构与候选d t d 之间的距离参与排序，提高了候选d t d 排 序的准确性。 3 原型系统实现。本文给出了基于多d t d 的x m l 查询的原型系统s m a r tx m l q u e r y 。它利用上述技术，不仅能实现与待查文档结构完全匹配的查询。而且能 实现与待查文档结构达到一定相似度的查询 4 基于多d t d 的x m l 数据的关系数据库存储。在基于多d t d 的x m l 索引方法 的基础上，本文提出了一种利用d t d 的结构信息在关系型数据库系统中存储 x m l 文档的方法。与j s h a n m u g a s u n d a r a m 、y a hm e n - b i n 等人提出的基于d t d 的x m l 关系数据库存储方法相比，本文提出的存储方法具有如下特点：1 ) 文 档结构的变化，不需要修改相应的关系模式定义；2 ) 不同d t d 的x m l 文档 可以保存在相同模式的关系表中。仅需两张关系表，就能存储所有的d t d 和 x m l 数据，所以，适用于多d t d 的应用环境；3 ) 可以在线性时间内重组数据 - 库中的x m l 文档。 关键宇 x m l 、查询、d t d 、距离、路径表达式、编码、索弓 a b s l a a c t a b s t r a c t 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 ) h a sb e c o m ee x t r e m e l yp o p u l a ra saf l e x i b l e m e d i u mo f d a t a e x c h a n g e a n d s t o r a g eo n t h ew w w 1 1 嵋d e v e l o p m e n t o f x m 儿b r i n g s o n m o r er e q u i r e m e n t sf o r p e r f o r m a n c eo f x m l q u e r y t i l i 8p a p e rf o c u s e so nx m 儿q u e r i e s t h a ta r eb a s e do nm u l t i p l ed t d si nc e r t a i nd o m a i na n da i m sa t s o l v i n gf o l l o w i n g p r o b l e m s ：l 、h o w t oc o n s t r u c ta nx m l q u e r yw i t h o u tk n o w i n g t h ed e t a i l e ds t r u c t u r eo f x m ld o c u m e n t st ob es e a r c h e d 72 、h o wt oe x e c u t eaq u e r yo nx m ld o c u m e n t st h a ta 坞 b a s e do nm u l t i p l ed t d si nc e r t a i nd o m a i n ? 3 ) h o wt oe x e c u t eaq u e r yo nx m l d o c u m e n t st h a th a v es i m i l a rs t r u c t u r e st ot h eq u e r y ? m a i na c h i e v e m e n t so f t h er e s e a r c hi n c l u d e ： 1 i no r d e rt or e t r i e v et h er e s u l t st op a t hq u e r i e se f f i c i e n t l y , p e o p l ep a ym u c ha t t e n t i o n t ox m l i n d e x i n g t h i sp a p e rp r o p o s e sd b x i ( d t d - b a s e d x m l i n d e x i n g ) ，a x m l i n d e x i n gm e t h o dt h a tu t i l i z e st h ed t d i n f o r m a t i o nt os p e e du pt h ev a l u a t i o no f x m l p a t hq u e r y m a i nc h a r a c t e r i s t i c so f d b x ia r e ：1 ) an e wx m l n u m b e r i n g s c h d m ei s a d o p t e d w h i c he n a b l e se a c he l e m e n ti nx m ld o c u m e n t sc a 耐e s c o r r e s p o n d i n gd t d s t r u c t u r a li n f o r m a t i o n 2 ) ap a t hq u e r yw i t hne l e m e n t s ( o r a t t r i b u t e s ) a n dap r e d i c a t er e s t r i c t i o nc a n b e i m p l e m e n t e d w i t h 0 n l y 0o r2s t r u c t u r a l j o i no p e r a t i o n sp e r ) 口帆d o c u m e n tw h i l ea t l e a s tn 1t i m e so fs t r u c t u r a lj o i n o p e r a t i o n sa r cn e e d e di nx i s s ( x i s si sak i nx m li n d e x i n gs y s t e md e v e l o p e db y q l ia n db m o o n ) 3 ) f o r a p a t he x p r e s s i o n t h a ti sn o t c o m p l y i n g w i t h a n yp a t h s i n x m l d o c u m e n t s ，d b x i c a n g i v ea j u d g m e n to f n ok n s w e r i nm u c hs h o r t e rt i m et h a n t h a to f s p h i n x ，x i s s ，e t e e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a td b x i c a n p r o c e s s p a t he x p r e s s i o n sm u c h f a s t e rt h a n l o r e 、s p h i n x a n d s sd o 2 t e c h n i q u e so fx m lq u e r i e st h a ta r eb a s e do nm u l t i p l ed t d si nc e r t a i nd o m a i n , s u c ha s f i n d i n go fc a n d i d a t ed t d s ”， r a n k i n go fc a n d i d a t ed t d s a g a i n s tu s o r s q u e r ys t r u c t u r e ”，e t c ，a r ed i s c u s s e di nd e t a i l an e wi d e ao fu s i n gs u b - d i s t a b c e b e t w e e nt r c 冶si n s t e a do fd i 蛐l l l c eb e t w e e n 慨sw h e n r a n k i n gi sd o n ei sp r o p o s e d t h en e wi d e ag u a l r i r e e sam o r e p r e c i s e 均n i d i l go u t p u t r a n k i n ga l g o r i t h mt h a ti s c l o s et ol i n e a rt i m e c o m p l e x i t y i so f f e r e da n dm a i n a l g o r i t h m sa r ep r o v e d a b s t 扭c t 3 a p r o t o t y p eo fx m lq u e r i e sb a s e do nm u l t i p l ed t d s i nc e r t a i nd o m a i n ，n a m i n g s m a r tx m l q u e r y , i so f f e r e d s m a r tx m lq u e r y c a r ln o to n l yf u l f i l lq u e r i e sw h o s e s t r u c t u r e sm a t c ht h ed o c u m e n t st ob es e a r c h e de x a c t l y , b u ta l s o q u e r i e sw h o s e s l a u c t u r e sa r es i m i l a rt od o c u r n e n t st ob es e a r c h e d 4 t l l i sp a p e rp r o p o s e san e wm e t h o do fs t o r i n gx m l d a t ai nr e l a t i o n a ld b ，w h i c h m a k e su s eo fi n f o r m a t i o n o f d t d c o m p a r e d t om e t h o d s p r o p o s e d b y j s h a n m u g a s u n d a r a m 、y a nm e n - h i n , e t c ，w h i c hu t i l i z e d t ds i m i l a r l y , t h en e w s t o r a g em e t h o di s o ft h ef o l l o w i n gc h a r a c t e r i s t i c s ：1 ) s t r u c t u r a lc h a n g ei nx m l d o c u m e n t sw i l ln o tl e a dt oa n ys c h e m ac h a n g eo f m l a t i v er e l a t i o n a lt a b l e s 2 ) 札 d o c u m e n t sb a s e do nd i f f e r e n td t d sc a r lb ek e p ti nas a m er e l a t i o n a lt a b l e a i ld t d s a r ck c c p c di nas a n l et a b l ea n ds od ox m ld o c u m e n t s 3 ) r e c o n s t r u c t i o no f x m l d o c u m e n t sc a nb ed o n e 谳l i n e a rt i m ec o m p l e x i t y x m l ，q u e r y , d t d ，d i s t a n c e ，p a t he x p r e s s i o n , n u m b e r i n gs c h e m e ，i n d e x i n g 第1 章绪论 第1 章绪论 随着i n t e m e t 的迅速发展，互联网已经成为新经济时代的标志，它极大地影响 了人类的生活方式、商业模式，并将在新世纪继续对人类社会的进步起着巨大的推 动作用。随着w e b 上数据的激增，面对庞大的信息海洋，人们却遇到了w 曲上存 在的大问题：虽然可以在线获得各种信息，但是找到所需要的信息常常极为困难。 其中虽然有硬件方面的原因，但是主要是由目前w e b 语言_ h n m ，的性质引起 的。尽管h t m l 从发明以来，己成为最成功的电子发布语言，但是它仅注重信息的 表现形式，它的标记仅仅反映了信息应该如何在页面上表现，并没有对信息本身进 行描述，并且它的标记集合是固定的，不能够根据需要进行扩展。随着w e b 应用的 日益广泛，它的局限性越来越明显。不适于作为i n t e m c t 上信息交换和标识的工具 对w e b 上大量半结构化数据的访问成为近年来数据库界研究的一个热点 m a g + 9 7 b d h s 9 6 k s 9 5 m m m 9 7 f f l s 9 7 c _ j s 9 9 。半结构化的数据通常没有 严格的类型定义，描述数据结构的信息包含在数据当中。为此，在很多研究中采用 了基于有向图的半结构化数据模型如o e m p g w 9 5 g p q 9 7 f k l 9 7 、e d g e l a b e l e d g r a p h b d h s 9 6 1 b u n 9 7 、h y p e r t r e e a m 9 8 和l a b e l e dm u l t i g r a p h s k s 9 5 等等按照 这样的模型，半结构化数据可以用标注的有向图表示，图中节点表示对象，边表示 对象之间的联系。还有不少研究采用了关系或嵌套的关系( n e s t e d - r e l a t i o n ) 模型如 a d m a m m 9 7 ，r e l a t i o n a l m o d e lu n d e r w e b s q l m m m 9 7 1 等借鉴传统数据库系统 中模式的概念可以定义并建立半结构数据的模式，在此基础上实现查询的表达和查 询处理。 采用半结构化的数据模型处理w e b 数据时，首先要从文本格式的数据中抽取结 构信息。由于目前在w e b 上普遍使用的h t m l 是面向显示的( p r e s e n t a t i o n - o r i e n t e d ) ，主要用于描述数据的格式、显示样式以及数据的位置等，无法直接定义 数据的结构，因此从基于h t m l 的w e b 数据中抽取结构信息的难度很大，通常只 能根据数据的格式( 段落、字体、缩进距离等) 并结合启发性规则来进行推测 a k 9 7 h g c + 9 7 】 k w d 9 7 】，在可抽取的数据类型、正确性以及通用性等方面都不 够理想。 基于上述原因，虽然在半结构化数据的处理方面已取得了大量研究成果，但对 w e b 上数据的查询问题仍然没有很好解决，时至今日，网上数据的访问还要依赖于 导航与搜索引擎。可扩展标记语言( e x t e n s i b l e m a r k u pl a n g u a g e ，简称x m l 4 b p s + 9 8 1 b p s 0 0 】) 正是为了解决这类问题而提出的1 9 9 8 年2 月，w 3 c ( w o r l dw i d ew e b c o n s o r t i u m 全球互联网联盟) 给出了其正式的x m l l 0 版本，并正式推荐x m l 第1 章绪论 成为下一代互联网标准。x m l 从提出到现在不过只有几年时间，但是它作为一种 跨产品、跨界面、跨平台的互联网的世界语，具有极大的应用前景，正引起政府、 企业和各大软件厂商的极大兴趣。关于x m l 实际上有一系列标准，x m l l o b p s 0 0 】 只是其基本的语言规范。其他标准包括x l i n k ( 用于描述将超链接加入x m l 文档 的方法的标准) 、x p o i n t e r ( 关于x m l 文档中特定部分的定位的标准) w h 0 0 2 、 x s l ( 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 ，有关x m l 文档的显示样式的标准) f r o u 0 2 、 d o m ( d o c u m e n to b j e c tm o d u l e ，供应用程序处理x m l 文档的对象模型及接口标准 的定义) l i n 9 0 2 、x m l n a m e s p a c e s ( 关于如何将x i v l l 文档中的元素标识、属性与 u r l 相关联的标准) b h l 9 9 、x m l s c h e m a sla n d2 ( 供应用开发者精确地定义基 于x m l 的类型) f a l l o l l 以及x m l q u e r y ( 关于x m l 数据的查询的标准) m a r 0 2 】 等等，其中很多标准还正在制定中 q u i n 0 2 。总之，对于x m l 的深入研究将有力 促进企业的信息化和电子商务。具有巨大的应用前景和经济效益 1 1x m l 简介 x m l 是w 3 c 提出的一种用于w e b 网络上的数据和文档结构的通用标记语言。 w 3 c 原意是用来解决h t m l 信息的不确定性和网站之间的数据交流问题，但随着 它的应用深入。特别是与j a v a 语言配合，在软件开发、网站运营、移动互联等方面 逐渐呈现出它的优秀性能很多技术专家和商业人士都预言它的出现将引发互联网 技术发展的又一次浪潮。x m l 可以解决网络中跨平台的数据交流问题，使不同的 网络信息可以以精确的、可供人和机器分析再加工的结构化、半结构化数据的形式 向外界提供。 x m l 是标准通用标记语言( s g m l ) 的一种变体它采用了优化浏览器显示 文档视图的严格的规则集合。从s g m l 中经过精心修剪而来的x m l 既保持了 s g m l 的功能，同时又减少了s g m l 的复杂性与h t m l 不同，x m l 允许文档开 发人员创建描述数据的标记，并使开发人员可以创建被称为文档类型定义( d 1 巾) 的规则集合。任何标准的x m l 语法分析器都可以读取、解码和检验这种基于文本 的自描述文档，并以独立于平台的方式提取数据元素，因此使应用程序可以通过另 一种名为文档对象模型( d o m ) 的标准访问数据对象对于电子商务软件厂商和 行业集团来说，x m l 的通用数据交换格式提供了可以与其它基于标准的协议( 如 h t t p 、t c p i p ) 以及i n t e m e t 一起使用的基于标准的构件。各公司已经开始支持 x m l 数据库厂商o r a c l e 公司和m m 从一开始就支持x m l ：m i c r o s o f t 的i e 5 0 以 及n e t s c a p ew e b 浏览器支持x m l ；s u n 公司考虑将此标准作为用于j a v a 的可移植 2 第1 章绪论 数据语言。此外，像o b j e c td e s i g n 公司的e x e e l o n 这类应用服务器提供了x m l 来 支持应用集成、数据交换和电子商务。 一个x m l 文档包含了从根元素开始的嵌套元素结构。每个元素有一个标签 ( t a g ) 与之相对应，除了字符串数据，它还可以包含属性值对和嵌套子元素。同 时包含字符串数据和嵌套子元素的元素被称为具有混合内容( m i x e dc o n t e n t ) 。x m l 中的元素标签必须良好嵌套，这样的x m l 文档是良构的( w e l l - f o r m e d ) 图1 1 给 出了一个描述出版信息的x m l 文档。其中根元素t u b l i c a t i o n s 包含b o o k 子元素和 属性y e a r 。，并且。b o o k 元素还包括自己的子元素集。t i t l e 。和 a u t h o r 值得注意的是， 一个p u b l i c a t i o n s 元素包含了多个b o o k 子元素( 集合) ，即p u b l i c a t i o n s 元素( 父 元素) 与b o o k 。元素( 子元素) 之间是一对多的关系。同样的关系出现在元素b o o k t 和a u t h o r 之间。 a u t h o r _ _ 2 蚰脚 t i t i e2 讥1 l c ! e l e m e n t b o o k ( t i t l e ，a l i l l i o np 妇妒 她u l h 咿a u t h o rl 蚍u p 硼0 0 k i e l e m e n t a u t o # p c d a t a p 图1 1 描述出版信息的x m l 文档片断图1 2 描述出版信息的d t d d t d ( d o c u m e n tt y p ed e s c r i p t i o n ) b p s 9 8 规定了x m l 文档的结构，可以视 为x m l 文档的模式。d t d 通过描述子元素和属性的名字及类型来定义x m l 元素 的结构嵌套予元素的出现次数用类似正则表达式的如下符号规定：( 包含零或 多个元素的集合) ，+ ( 至少包含一个元素的集合) ，? ( 包含零或一个元素) 和没有 修饰( 包含且仅包含一个元素) 。同时d t d 也严格规定了x m l 文档中元素的子元 素的出现顺序，即按照元素定义的正则表达式顺次展开。正如前一小节所述，元素 允许包含至多一个类型为i d 的属性，由该属性在文档域内唯一标识该元素。同时 3 第1 章绪论 其他元素也可以通过类型为i d r e f 的属性对其加以引用。i d r e f 属性并没有指明 该属性所指向的元素类型，在这一意义上说，i d r e f 属性是没有类型的。属性定义 中可以用# r e q u i e d 和# i m p l i e d 等修饰符类似描述其在出现次数上的约束，同时 属性的取值范围也可在d t d 中定义。一个良构且符合d t d 的定义的x m l 文档被 称为是有效的( v a l i d ) 。 图1 2 给出了描述出版信息的d t d 。根据定义， p u b l i c a t i o n s 。元素可包含一个 y e a r i 属性和多个b o o k 元素，b o o k 元素可包含多个a u t h o r 元素和一个t i t l e 元素， 而t p r i c e 元素则是可选的( 这在符合该定义的x m l 文档( 图1 1 ) 中已有所表现) 1 2x m l 查询研究的主要领域 由于越来越多的结构化或半结构化的数据采用x m l 格式存储和交换，因此对 x m l 数据的查询变得日益重要 m 缸9 8 】。w 3 c 为此专门成立了x m l 查询工作组 ( x m l q u e r yw o r k i n gg r o u p ) ，负责制订有关查询的数据模型、查询语言等方面的 规范。x m l 数据与此前研究中所提出的半结构化数据非常相似，因此，有关半结 构化数据方面的研究成果可以比较方便地应用于x m l 数据的查询，包括查询语言、 查询处理技术和索引方法等同时，很多研究人员对利用传统数据库系统查询x m l 数据的方法进行了研究。在这些研究中主要涉及以下一些问题： 数据模型x m l 数据是非常灵活的，表现为有些数据具有明确的数据类型定义( 如 按照x m ls c h e r n a 建立的数据) ，而另外一些数据则缺乏严格的类型定义或根本就 没有类型定义。为便于实现结构化数据查询，应将x m l 数据映射到某种数据模型。 由于关系数据库系统目前处于主导地位，因此很多研究和实现方案采用了关系模型 ( 如 d f s 9 9 s h t + 9 9 f k 9 9 s k w w 0 0 等，以及主流的数据库产品如o r a c l e 、 d b 2 等) 。将x m l 数据映射到关系模型的一个明显缺点是缺乏直观性。因此不少 研究采用了关系对象模型( 如 k m 0 0 1 ) 或面向对象的半结构化数据模型( 如 【g m w 9 9 】) 以及o o d b 的数据模型( 如 l a w 9 8 f e 0 1 等) 。w 3 c 的x m l 查询工 作组提出的数据模型t r m n o h 综合考虑了表示结构化数据( 简单类型或复杂类型) 与半结构化数据的需要。 模式建立与维护在传统的数据库中，数据的定义、查询表达、查询的处理与优化 等都依赖于模式。对于x m l 数据的查询，模式同样是非常重要的。文档类型定义 描述了x m l 文档中元素的结构信息，因此可以看作x m l 数据的模式，不过d t d 4 第1 章绪论 缺乏精确的类型定义，引用定义机制也不完善，为此，可以针对所采用的数据模型 ( 关系的或面向对象的等) 根据d t d 建立相应的数据库模式 s h t + 9 9 ，、i d 9 9 】。 由于无d t d 的x m l 文档也是合法的，因此，在w e b 上可能存在大量无d t d 的文 档，对于这样的文档，需要通过抽取其中的元素结构建立模式 g w 9 7 ，w i d 9 9 】。 w e b 数据是易交的，随着x m l 数据的交化，相应的模式也应随之更新。文献 s h t + 9 9 ，g w 9 7 ，w i d 9 9 等分别讨论了关系模式、半结构化的数据库模式的更新 问题。 查询语言合适的查询语言是必不可少的，这样的查询语言应该有足够的表达力来 满足对结构化数据查询和从文档中检索信息的需要。自x m l l 0 推出后，有关各方 先后提出了很多查询语言的方案，有的是在以前半结构化数据的查询语言的基础 上，针对x m l 的特点作了必要的扩展，如l o r e i a q m + 9 7 】 g m w 9 9 、o q l s l a w 9 8 】 及w e b o q l a m 9 8 1 等。另外一些则是专门为x m l 的查询而提出的如 x m l q l d f f + 9 8 、x q l r l s 9 8 、y a t l c j s 9 9 及q u i l t c r f 0 0 等等w 3 c x m l 查询工作组提出的查询语言x q u e r y 田c f + 0 1 借鉴了结构化、半结构化数据查询语 言的很多特性，并且较多地考虑了对不同类型数据源( 包括传统的数据库系统及文 档系统等) 的访问能力以及在小型化、易实现以及可读性0 r o m a n - r e a d a b l e ) 等方面的 要求。 查询处理在传统的数据库系统中，结构化数据的查询处理已经得到了广泛深入的 研究 g r a 9 3 ，这为x m l 数据的查询奠定了基础，很多方面( 如查询计划的生成、 代价估算的方法、优化规则等) 都值得借鉴。不过，x m l 数据具有新的特点和查 询需求，原有的方法应根据x m l 数据的特点进行改进，还要考虑与其他方法( 如 全文索引) 的结合。在l o r e 系统中采用了多种索引来提高查询效率，建立了基于 磁盘i o 和c p u 时间的代价模型，结合多种统计数据来实现查询优化 m w 9 9 a , m w 9 9 b 。s t r u d e l 中使用存储描述符( s t o r a g ed e s c r i p t o r s ) 来表示数据的存储格式， 查询处理器根据描述符计算查询代价 f l s 9 8 。由于w e b 上的x m l 数据常常是不 规则的和易变的，因此基于一般路径表达式( g e n e r a lp a t he x p r e s s i o n ) 的查询将非 常有用不少工作( f l s 9 8 m w 9 9 c g t 0 0 l m 0 1 】【c s f + o i 】 p h 0 1 】 b b m + 0 1 等) 对一般路径查询的优化问题进行了研究。 x m l 数据的存储x m l 数据的物理存储格式对查询处理的效率有很大的影响，日 前主要有三种方案：1 ) 文本格式，这是存储咀数据的标准格式为了提高查询 效率可以建立索引，索引的维护是需要解决的关键闯题。2 ) 将x m l 数据存储于传 s 第1 章绪论 统数据库中，如 d f s 9 9 s h t + 9 9 f k 9 9 l a w g $ b o u o h s k c o h 等。利用传统数 据库系统的查询处理机制可以获得较高的效率，但x m l 数据与传统数据库之间的 转换可能导致信息损失。3 ) 使用对象管理器保存x m l 数据 t d c z o h 。这类系统目 前缺乏类似s q l 或o q l 的通用的查询语言。 视图的建立与维护视图在传统数据库中是一种重要的机制，同一物理数据上的多 个视图可以满足用户不同的需要视图还可以控制用户对数据的访问，有利于数据 库的安全。对于x m l 数据的查询来说，视图很可能同样重要不过，m 数据的 不规则性也给视图的定义、维护及查询重写等带来了更多的困难，近年来在半结构 化数据的视图方面已有不少研究( 见 a m r + g s g r l s + 0 0 c w 0 0 等等) 。 1 3 本文的研究内容及主要成果 本文对相关领域基于多d t d 的x m l 查询方法进行了的研究，具体解决以下问 题：1 ) 使用户在构造x m l 查询时，无须了解待查x m l 文档的结构；2 ) 实现对 相关领域的基于不同d t d 的多类咀，文档的统一查询；3 ) 不仅能实现与待查文 档结构完全匹配的查询，而且能实现与待查文档结构达到一定相似度的查询。 需要指出的是，x m l 并不强制性地依赖于d t d 。对于不带有相关d t d 的x m l 文档，不在本论文的研究之列。对于这类文档，可以利用现存的多种d t d 提取方 法，例如 g g r 0 0 等文介绍的方法，在获得d t d 之后，便能被本文提出的方法高效 管理和查询。 本文的主要研究成果如下： 1 基于d t d 的x m l 索引方法 通过路径表达式实现对x m l 文档的路径查询，是现已提出的x m l 查询语言 的一个共同的特点。为了提高x m l 路径查询的效率，本文提出一种儿索引的 方法d b x i ( d t d b a s e d x m l i n d e x i n g ) ，该方法充分利用d t d 的信息提高路径查询 的效率。d b x i 采用了新的x m l 编码方法，使x m l 文档中每个元素，属性的编码 携带了相应的d t d 结构信息。对一个由n 个元素，属性组成的有一个谓词约束的路 径表达式，d b x i 处理每个x m l 文档仅需0 次或2 次结构连接运算。如果查询路 径在待查x m l 文档中不存在正确匹配，d b x i 能够在比s p h i n x 、x i s s 等x m l 索 引方法较短的时间内给出无查询结果的判断。在d b x i 的基础上，我们给出了基于 多d t d 的x m l 文档索引方法一m d b x i ( m u l t i - d t d b a s e dx m l i n d e x i n g ) 。 6 第1 章绪论 2 基于多d t d 的x m l 查询方法的关键技术研究 目的是利用d t d 的信息，实现相关领域基于不同d t d 的多类x m l 文档的统 一查询，即不仅能实现与待查文档结构完全匹配的查询，而且能实现与待查文档有 相似结构的查询。本文对“候选d t d 的定位”、“d t d 与用户查询结构的距离排序” 等技术进行了详细讨论，在对候选d t d 与用户查询结构的距离进行接近线性时间 复杂性的排序运算时，提出了以“树间亚距离排序”代替“树间距离排序”的观点， 即以查询结构与查询在候选d t d 中的上下文之间的距离，代替查询结构与候选 d t d 之间的距离参与排序，可提高候选d t d 排序的准确性。本文还给出了基于多 d t d 的x m l 查询的原型系统。 3 基于多d t d 的x m l 数据的关系数据库存储和查询 本文提出一种利用d t d 的结构信息对x m l 进行存储的方法该方法仅需两张 关系表，就能存储所有的d t d 和x m l 数据。x m l 文档结构的变化不会引起相应 关系模式定义的变化，遵循不同d t d 的x m l 文档可以保存在相同模式的关系表中。 该方法还可以在线性时间内重组数据库中的x m l 文档。 1 4 论文结构 本文共分为六章：第一章对x m l 进行了简单介绍，论述了本论文的研究背景、 研究现状、研究内容和研究成果。第二章论述了x m l 文档的模型、查询操作以及 x m l 查询语言具有的特征。探讨了x m l 查询语言应当具有的一些基本特性，如简 单路径表达式、一般路径表达式等，并简要介绍了现今已提出的主要的查询优化方 法和x m l 存储方法。第三章讨论了x m l 路径查询的查询优化问题，提出了基于 单d t d 的x m l 索引方法d b ，详细介绍了d b x i 的编码方法、d b 的主要结 构及路径查询的实现过程给出了相应的实验结果及分析。在d b x i 的基础上，本 章还给出了基于多d t d 的v 儿索引方法m d b x i 。第四章对基于多d t d 的x m l 查询方法进行了研究，详细介绍了“候选d t d 的定位”、“候选d t d 的排序以及查 询重构”等技术，并给出了原型系统s m a r tx m l q u e r y 第五章讨论了基于多d t d 的x m l 数据的关系数据库存储和查询方法，提出一种新的存储方法，并详细介绍 了该方法的x m l 路径查询的实现过程。第六章为总结和展望，总结本文的工作以 及未来的研究方向。 7 第2 章x m l 查询语言、查询优化和存储 第2 章x m l 查询语言、查询优化和存储 进入9 0 年代以来，数据库应用环境发生了巨大的变化，i n t e m e t 向数据库领域 提出了前所未有的挑战。w 曲上的数据是不规则的和不完全的数据，并且它的结构 是隐含的、快速变化以及不可预料的，例如h t m l 构成的w e b 页、电子邮件、l a t e x 文档等都属于这一类。传统数据库管理系统( 指基于关系、面向对象和关系一对象 模型的数据库) 使用的是基于结构化的数据模型，其特征就是数据库预先都有一个 固定的模式，数据遵守严格的类型定义。模式的作用在于检验数据和查询优化，而 半结构化数据的模式却是隐含的、不可预料的。随着w e b 的发展，这类数据会越来 越多，因此对于这类数据的模型和查询的研究具有迫切性和重要性。国际上从9 0 年代中叶就已经开始了这类数据的研究，并且取得了很多成果。 x m l 可以看作是半结构化数据的一个通用的逻辑表示。它的模型和查询语言 的研究可以借鉴半结构化数据研究的已有成果，同时又要结合x m l 自身的特点 对于x m l 模型和查询语言的研究将有力地促进数据库技术应用于海量的w e b 数据 管理和半结构化数据的研究。数据库界在半结构化数据领域的工作是使用基于树或 图的数据模型，而这个模型对于x m l 也很适合。这样在半结构数据方面的研究结 果现在可以应用于x m l 之中。 2 i 数据结构 文档类型定义( 简称d t d ) ，描述了文档中对象( 在x m l 术语中称为元素) 的内容和结构，是描述x m l 数据模式的模式定义语言。符合d t l 5 的x m l 文档被 称为是有效的x m l 文档。具体的说，一个d t d 就是一组规则，它使我们可以规定 自己的元素、属性、实体的集合。因此，d t d 基本上就是一种语法，它表明怎样的 标记是允许的，它们出现的顺序，它们怎样被嵌套从形式语言的角度看，d t d 是 语言的词汇表和结构，描述了允许使用什么样的标记( 郎定义新的标记语言) 、标 记元素之间如何相互嵌套，这样使x m l 成为一种元标记语言，可以用来描述其它 标记语言各个组织或者个人都可以定义各自的d t d ，近年来，在几个特定专业的 领域己经开发出相应的d 1 r i 卜咆括大范围的商业、工程、金融、工业和科学领域。 这些d t d 有助于程序员编写能够理解标记并智能处理标记的软件、不同的人们和 程序互相阅读文件，同时为数据交换提供了中间模式。帆文档的一个d t d ，可 以把它看作数据库系统中的一个模式，然而，它们加在文档上结构的多少又是易变 8 第2 章x 地查询语言、查询优化和存储 的。一个结构化的极端是，它们也许可以添加同关系数据相同的严格结构。另外一 个极端是，它们可以允许任何元素类型包含任何元素类型。作为一种中间状态，它 添加不是很严格的结构，对于数据实例，允许具有比传统模式更多的变化。虽然 x m l 标准并不要求必须使用d t d ，但绝大多数x m l 文档都将使用d t d 。这是因 为当x m l 文档含有d t d 时，对于x m l 文档的存储、查询和交换都有重要作用 2 1 id t d 的简化 通常说来，d t d 比较复杂，如元素之间可以组成正则表达式、一对括号可以把 数个元素合为一个独立元素。但是，d t d 越复杂，就越难编写出满足要求的合法的 文档，维护d t d 更为困难。- 简化d t d 的缺点在于该过程是不可逆的，这是因为在简化的过程中丢失了原 始d t d 中的部分语义信息，主要是元素问的相对顺序对于这个缺点，一方面它 并不影响一般x m l 文档的存储和查询：另一方面，如果需要反映这种顺序，可以 在存储时加入一个域来反映元素间的相对顺序。 d t d 的复杂性主要来源于元素定义的复杂性。假定