（计算机软件与理论专业论文）xml不完全信息的动态发现.pdf

山东大学硕士学位论文 摘要 随着互联网络时代的到来，数据越来越多地开始以网络在线的方式进行存 储、集成、发布和交换。由于x m l 具有跨平台，简单易用等特性，在很短的时 间内就获得了广泛认同，在众多应用领域中，已成为主要的数据表示和交换的标 准。x m l 作为一种半结构化数据的表示模型，具有很强的信息表现力，它既可 以表示结构化的数据又可以表示非结构的数据。但在现实世界中常常存在一些不 完全的信息，特别是在数据交换过程中，经常会因为x m l 模式不同而产生不完 全信息。这些不完全信息会对x m l 数据库中的连接、查询等操作造成不良影响。 因此，如何及时的发现x m l 文档中出现的这些不完全信息，并进行相应处理就 变得尤为重要。 目前，国内外的研究者针对x m l 中不完全信息所展开的科研工作主要集中 在理论研究上，重点是进行不完全信息函数依赖的规则推理。对于有效的发现有 价值的函数依赖以及通过这些函数依赖来补全这些不完全信息，还没有深入的研 究。基于目前的研究基础，本文将如何有效的发现及补全x m l 中的不完全信息 作为了研究的重点。通过我们的这些研究，可以进一步增强x m l 文档表示现实 世界的能力，进而推动理论和实际相结合，产生巨大的经济效益。 本文通过对一个典型的例子展示了如何对x m l 文档本身进行分析，找出其 中所包含的对于发现不完全信息有帮助的函数依赖，然后使用这些函数依赖发现 x m l 数据中的不完全信息，并进行相应的补全。我们所做的主要工作如下： 1 在x m l 中引入不完全信息的相关概念，即当树节点中存在一些节点的值 为空值的情况下，形成一棵不完全信息树，并由此引入了树元组、元组类等一系 列概念。 。2 比较了x m ls c h e m a 与d t d 的优劣，对于为何选择x m ls c h e m a 作为研 究的基础进行了重点阐述。 3 针对如何发现有价值的函数依赖问题，本文提出了d i s c o v e r f d s 算法，这 一算法关注于不完全信息，通过对于x m l 文档进行属性划分的比较，动态的发 现有价值的函数依赖。d i s c o v e r f d s 算法是我们进行相关研究的有力工具，是本 山东大学硕士学位论文 文进行论述的重点。 4 利用上述有价值的x m l 函数依赖，在x m l 数据库中可以通过对其数据 进行比较分析，使用x m l c h a s e 算法进行不完全信息的追赶补全。 关键词：x m l 、函数依赖、不完全信息、划分 j 1 山东大学硕士学位论文 a b s t r a c t n o w a d a y s ，m o r ea n dm o r ed a t ai ss t o r i n g ，i n t e g r a t i n g ，p u b l i s h i n ga n d e x c h a n g i n go n l i n e a sx m l h a st h ef e a t u r eo fc r o s sp l a t f o r m ，e a s yt ou s e ， e t c ，i ti sw i d e l ya c c e p t e di nas h o r tt i m e i nm a n yf i e l d s ，x m lh a sb e c o m e al e a d i n gs t a n d a r do fd a t ae x p r e s sa n de x c h a n g e x m l ，a sar e p r e s e n t a t i o n m o d e lo fs e m i s t r u c t u r e d d a t a ，h a ss t r o n g a b i li t yo f p e r f o r m a n c e i n f o r m a t i o n i tc a ne x p r e s ss t r u c t u r e dd a t aa n dn o n - s t r u c t u r a lo n e b u ti n t h er e a lw o r l d ，t h e r ei sa l w a y ss o m ei n c o m p l e t ei n f o r m a t i o n ，e s p e c i a l l yi n t h ed a t ae x c h a n g ep r o c e s s ，w h i c hi sc a u s e db yt h ed i f f e r e n c eo fx m l m o d e l s t h i si n c o m p l e t ei n f o r m a t i o nw i l la d v e r s e l ya f f e c to nt h ex m l d a t a b a s e sc o n n e c t i o n sa n dq u e r i e s s o ，i tb e c o m e se s p e c i a l l yi m p o r t a n tt o d i s c o v e r yo fi n c o m p l e t ei n f o r m a t i o na p p e a r i n gi nt h e s ex m ld o c u m e n t s a n dt r e a t m e n ti tc o r r e c t l y c u r r e n t l y ，r e s e a r c h e r s w o r k sf o c u so n t h et h e o r e t i c a lr e s e a r c ho f i n c o m p l e t ei n f o r m a t i o ni nx m l t h e yp a yal o to fa t t e n t i o nt or e a s o nt h e r u l e so ff u n c t i o nd e p e n d e n c e s ( f d ) b u t ，f o rt h ee f f e c t i v ed i s c o v e r yo ff d s a b o u ti n c o m p l e t ei n f o r m a t i o na n dc o m p l e t ei tb yt h o s ef d s ，t h e r ei sn o t m u c hd e e p l yr e s e a r c h b a s e do nc u r r e n tr e s e a r c hs t a t e ，t h i sp a p e rf o c u so n e f f e c t i v ef i n da n dc o m p l e t et h ei n c o m p l e t ei n f o r m a t i o ni nx m ld a t a t h r o u g ho u rs t u d i e s ，x m ld o c u m e n t sc a nf u r t h e re n h a n c et h ea b i l i t yt o e x p r e s st h er e a lw o r l d t h e np r o m o t et h ec o m b i n a t i o no ft h e o r e t i c a la n d p r a c t i c a la n dg e n e r a t ee n o r m o u se c o n o m i cb e n e f i t s i nt h i sp a p e r ，t h ea d o p t i o no fac o m p l e t ee x a m p l es h o w sh o wt oa n a l y z e t h ex m ld o c u m e n ti t s e l f , t oi d e n t i f yi n t e r e s t i n gf d s t h e nu s et h e s ef d st o d i s c o v e rt h ei n c o m p l e t ei n f o r m a t i o ni nx m ld a t aa n dc o m p l e t ei t o u r r e s e a r c hw o r k sa r es h o w na sb e l o w ： 1 w ei n t r o d u c et h ei n c o m p l e t ei n f o r m a t i o na n dt h er e l a t e dc o n c e p t s i i i 山东大学硕士学位论文 i n t ox m l ，t h a ti st os a y ，w h e nat r e eh a v es o m en o d e sw h i c hv a l u e s a r en u l l ，t h i st r e eb e c o m eai n c o m p l e t et r e e ，a n df r o mt h i s ，w ec a n g e tt h ec o n c e p t so ft r e et u p l e ，t u p l ec l a s s ，e t c 2 b yc o m p a r et h ex m ls c h e m aa n dd t d 。ss t r e n g t h sa n dw e a k n e s s e s ， e x p l a i n e dw h yw es e l e c t e dx m l s c h e m aa st h eb a s i so ft h es t u d y 3 i no r d e rt of i n dt h ei n t e r e s t i n gf d s ，t h i sp a p e rp r e s e n t sd i s c o v e r f d s a l g o r i t h m t h i sa l g o r i t h mf o c u s e so ni n c o m p l e t ei n f o r m a t i o n b y c o m p a r i n g a t t r i b u t ep a r t i t i o n so fx m ld o c u m e n t s ，i td y n a m i c d i s c o v e r i e si n t e r e s t i n gf d s d i s c o v e r f d sa l g o r i t h mi sap o w e r f u l t o o lf o ro u rr e s e a r c h ，a n di st h ek e yp o i n to ft h i sp a p e r 4 a c c o r d i n gt ot h ei n t e r e s t i n gf d s ，w ec a na n a l y z ed a t ai nt h ex m l d a t a b a s e ，a n dc o m p l e t e t h e i n c o m p l e t e i n f o r m a t i o nb y u s i n g x m l c h a s ea l g o r i t h m k e y w o r d s ：x m l ，f u n c t i o nd e p e n d e n c e ，i n c o m p l e t ei n f o r m a t i o n ， p a r t i t i o n i v 山东大学硕士学位论文 索引 图片索引： 图1 ：一个x m l 文档的例子7 图2 ：对于图1 的简化的s c h e m a 2 3 图3 ：扩展树元组2 5 图4 ：将图1 按照元组类存储成平面的形式2 6 图5 ：c o m m o d i t y 的部分属性集格子3 3 图6 ：对应于图l 中数据的空值表3 4 图7 ：实验结果4 3 表格索引： 表1 ：h t m l 与x m l 的比较1 2 表2 ：属性划分的例子3 1 表3 ：追赶算法示例3 8 表4 ：第一轮追赶后的结果3 9 表5 ：追赶的最终结果3 9 表6 ：d b l p 的详细信息4 3 4 9 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写过的科研成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任 由本人承担。 论文作者签名： 日期：磁：鱼 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 导师签名龇日期： 山东大学硕士学位论文 1 1 研究背景 第一章绪论 经过十几年的发展，互联网( i n t e n r e t ) 己经成为新经济时代的标志，它极大地 影响了人类的生活方式、商业模式，并将在新世纪继续对人类社会的进步起着巨 大的推动作用。作为互联网最主要应用的w 曲正成为整个世界的窗口，它实现 了全球用户和机构信息的共享，可以预计，w 曲将成为人类社会的主要信息源、 媒体和商务的门户，而互联网将成为信息传播的介质和商务运作的基础平台。 随着互联网时代的到来，数据越来越多地开始以网络在线的方式进行存储、 发布和交换。1 9 9 8 年2 月，万维网协会w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) 推出了 可扩展的标记语言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 ) ，并将它作为一种互联网 数据表示和交换的标准。关于x m l 有一系列标准，x m l l 0 是其基本的语言规 范，还包括其他标准如：x l i n k ( 用于描述将超链接加入x m l 文档的方法的标准) 、 x p o i n t e r ( 关于x m l 文档中特定部分的定位的标准) 、x s l ( 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 ，有关x m l 文档的显示样式的标准) 、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 、x m ln a m e s p a c e s ( 关 于如何将x v i l 文档中的元素标识、属性与u r l 相关联的标准) 、x m l s c h e m a s l a n d 2 ( 供应用开发者精确地定义基于舭的类型) 以及x m lq u e r y ( 关于 x m l 数据的查询的标准) 等等。其中很多标准还正在制定，这些标准正意味着 x m l 文档的不断的发展和广泛的应用范围。 针对于x m l 的研究工作有很多，如x m l 的数据查询模型、基于x m l 的数 据库管理系统等。作为数据库的x m l 数据与关系数据库一样，也有自己的模式， 目前应用最多的就是x m l s c h e m a 2 1 和x m l d r o ( o o c u m e n tt y p ed e f i n i t i o n ) 1 3 1 等。这两种模式目前处于研究中，其中d t d 作为x m l 标准的一部分，它是x m l 文档使用最早、应用最多和最成熟的一种模型。但是这种模型具有很多的限制， d t d 不支持多种数据类型，只有“p c d a t a 一种数据类型，而在实际应用中常 常需要表达复杂的数据类型，像布尔、时间、日期等。并且标记集合固定且不易 山东大学硕士学位论文 扩充，扩充只有通过新的d t d 标准来定义，而x m l s c h e m a 作为新的描述方法， 它完善了d t d 的不足，对于文档的结构、数据的属性、类型的描述是全面的。 目前x m l 文档的研究主要是基于这两种描述方法来进行的【4 】。 x m l 作为一种半结构化数据的表示模型，从提出到现在只不过几年的时间， 但它作为一种跨产品、跨界面、跨平台的互联网的标准语言，已经显现出其强大 的应用前景，并受到了政府、企业和各大软件厂商的广泛关注。各个行业如金融 机构、海关、媒体产业多将x m l 数据作为公认的格式进行交换与集成。随着 x m l 数据的增多，人们也开始越来越多地希望以对待数据库的方式来处置和管 理x m l 文档。这样在处理x m l 文档时就存在同关系数据库类似的问题，尽量 减少插入修改等操作的异常及信息的冗余和不完全。 在现实世界中存在大量的不完全信息。例如：某校新成立了一个系，已经招 收了学生，但是系主任还没有最后任命。这时在记载这个系的信息的数据库中， 送入学生的姓名、性别等信息的同时，有关系主任的内容就只能空着。我们称这 些有关内容为“空值”。这就是一种不完全信息。这个例子中的不完全信息，最 终会被实际值取代而成为完全信息，只是在一定的时间内是有空值的，信息是不 完全的。还有一些不完全信息是由于受到科技水平的限制或者其他原因，将会在 很长一段时间内空着，什么时候能够用实际值替代还不好说。我们在数据库中处 理这些信息的时候，必须要对此做出考虑。关系数据库的创作人e e c o d d 就建 议将一个t m k ( 空值) 加入到数据库中。空值本身所固有的重要语义信息包括： 空值是否可以用非空值来取代；可用来取代空值的非空值实际值、实际值的 个数、实际值的范围。据此，我们把空值分为两类：相容空值和不相容空值，分 别用上u n k 和上妣表示1 5 1 。 x m l 作为数据库，同样需要表达现实世界中的不完全信息，因此我们在已 有的x m l 数据库研究的基础上在x m l 数据库中引入空值来进一步表达不完全 信息环境下x m l 数据的相关问题。目前x m l 已经成为i n t e m e t 上的数据表示和 数据交换的标准，需要通过i n t e m e t 交换和处理的x m l 数据会大大的增加。含 有不完全信息的x m l 数据也会越来越多，如果能够在大量的x m l 数据中动态 的发现不完全信息，并对这些信息进行一定的补全将会有力地促进企业的信息 化、电子商务以及电子政务的发展，因此具有巨大的应用前景和经济效益。 本文就是在这一背景下提出了一种关注于空值的x m l 函数依赖的算法，并 2 山东大学硕士学位论文 以这个算法的结果为基础，利用x m l c h a s e 算法尝试去补全x m l 数据中的不完 全信息。 1 2 研究现状 x m l 是标准通用语言s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ) 的一 个变体，从s g m l 中经过精心修剪而来的x m l 即保持了s g m l 的功能，同时 又减少了s g 池的复杂性。与h t m l 不同，x m l 允许文档开发人员创建描述数 据的标签，并使开发人员可以创建各种规则集合，比如d t d 或x m ls c h e m a 。 一个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 ) 。 在对x m l 文档的研究过程中，经常将它和关系数据库进行对比分析。这是 因为：首先，二者都具有描述数据结构的能力。关系数据库仅限于描述结构化数 据，而x m l 不仅可以描述结构化数据，还可以描述半结构化 6 1 1 7 1 甚至非结构化 数据；其次，关系数据库具有完备的理论基础，技术成熟且应用广泛。所以对 x m l 文档的理论研究离不开关系数据库理论知识作为基础。 但是x m l 文档和关系数据库在数据结构上存在显著差异，x m l 文档的数据 依赖和规范化问题比关系数据库的相应问题复杂，因此不能把关系数据库中的相 应理论直接应用到x m l 。依据关系数据库和x m l 文档的关系可将对x m l 的研 究大致分为以下三个方面： 1 、x m l 文档与关系数据库之间的转换【8 】：包括x m l 模式到关系模式的 转换 9 1 、利用关系数据库存储x m l 数据【l0 1 、从关系模式到x 池模 式保持约束传递【1 1 】等方面。 2 、x m l 数据库技术蚴【4 】：包括查询1 3 1 、数据库计划【14 1 、存储等方面。 3 、x m l 文档的研究：技术应用如w e b 数据集成【1 6 j 、电子商务1 7 1 、档案 馆数字化建设1 8 】、信息共享1 9 1 等方面；理论研究如查询语言2 0 1 、查 询方法【2 1 1 、路径与类型约束2 2 1 、一致性检查 2 3 1 、模式研列2 4 1 、数据 3 山东大学硕士学位论文 语义描述问题2 5 1 等方面。 正如关系数据库用模式定义语言定义概念模式，x m l 文档用模式语言定义 文档结构和内容限制。常见的模式语言有文档类型定义( d o c u m e n tt y p e d e f i n i t i o n ，简称d t d ) 和x m ls c h e m a 。其中，d t d 不仅使用最早、应用最多， 最成熟，而且是更复杂模式x m ls c h e m a 的基础。目前x m l 文档的研究大多数 都是以文档类型定义d t d 为基础进行的，m a r c e l oa r e n a s ，l e o n i dl i b k i n 在文献 中给出了关于d t d 定义的一个六元组d = ( e ，a ，只rr ) 。其中d 为文档类型定义 名；e 表示元素类型的有限集合；a 表示属性的有限集合；p 表示从e 到元素类 型定义的映射；r 表示从e 到a 的幂集p ( a ) 的映射2 5 1 。这一定义基本上是d t d 研究的基础。 在d t d 基础上定义x m l 树，x m l 树定义为给定d t dd = ( e ，a ，err ) ，称 七元组t = ( vl a b ，e l e ，a t - t , v a l ，r o o t ) 为满足( 或符合) d 的x m l 树，其中t 为x m l 树名，它是符号化的元组语义；v 是节点的有限集合；l a b 是从v 到e u a u s 的映射；e 是从v 到v 宰的部分映射；甜是从v 到a 的部分映射；v a l 是从v 到 字符串值的部分映射；r o o t 是v 中唯一的节点，l a b ( r o o t ) = r 称为t 的根。x m l 文档是一个节点标签树，以节点为单位，那么在x m l 树中存在着关于节点之间 的关系，节点值相等2 6 1 和节点相等【2 7 1 。 x m l 树是x m l 文档的半结构化数据的模型，所作的研究工作都是以树形结 构为基础的。在树的基础上定义x m l 路径( x p a t h ) 定义为给定d t dd = ( e ，a ，e rr ) 和满足d t d 的x m l 树t = ( vl a b ，e l e ，a r t ，v a l ，r o o t ) ，t 中的路径定义为 v l v n ) ，其中v l - - r o o t ，v i e e l e ( v i 1 ) ，i e ( 2 ，n 1 ) ；并进一步定义了根据节点v h 的类 型又可以分为的元素节点类型路径和值类型路径等，路径又分为绝对路径和相对 路径等【2 6 1 。 在此基础上很多研究者对基于d t d 标准的x m l 完整性约束研究较多，下面 两篇文献分别给出了比较完善的理论系统。 a m a u ds a h u g u e t 2 8 1 用路径表达式表示x m l 文档中元素、属性和元素的值之 间的函数依赖关系，从表达形式上区别绝对函数依赖和相对函数依赖，而且研究 了函数依赖的蕴含问题，给出了完备的推理规则集，并进一步讨论了x m l 文档 的函数依赖和键的关系。另外还研究了x m l 文档中的多值依赖问题及由此而引 起的数据冗余和操作异常现象，以及如何消除数据之间的异常依赖。 4 山东大学硕士学位论文 吕腾2 6 1 给出基于路径表达式的函数依赖定义，并根据函数依赖定义键，提出 逻辑蕴涵定义和正确、完备的推理规则集。函数依赖和键能够辅助判定d t d 设 计的优劣，据此提出规范化d t d 的概念，讨论规范化d t d 和b c n f 的关系， 并给出了相应的规范化算法。在此基础上讨论约束信息在从x m l 文档向关系数 据库转化过程中的重要作用。文章基于规范化d t d 来进行x _ m l 文档的关系数 据库的存储，借助于x m l 上键的定义信息组织关系模式，并利用数据库中的完 整性约束机制对键的维护。初步探讨如何基于x m ls c h e m a 来进行文档的数据库 存储，重点是使用关系数据库的机制来支持x m ls c h e m a 中有的约束定义。 相对地x m ls c h e m a 规范发布较晚，2 0 0 1 年5 月2 日，国际互联网联盟( w r o r l d w i d ew - e bc o n s o r t i u r n ，简称w 3 c ) 正式发布了w 3 cx m ls c h e m a 规范。基于 s c h e m a 标准的x m l 文档研究不多，主要集中在基于s c h e m a 标准的x m l 文档 的实际应用、与关系数据库的转换方面。 刘文远【2 9 】讨论当基于s c h e m a 标准的x m l 文档中存在多值依赖时，如何规 范x m l 文档，从而使x m l 文档有更小的冗余以及更新、删除、插入异常。在 此基础上提出一个规范化算法并给出算法的说明，来规范存在多值依赖的x m l 文档，但没有给出多值依赖的定义及推理规则。 对于不完全信息国内外的研究人员都在做着大量的研究，对于现实世界的不 确定信息即空值的语义进行分析。目前的国内外的研究者主要把空值引入到关系 数据库中这样形成了空值环境下的关系数据库的研究。主要研究工作有空值环境 下的关系数据库规范化问题的研究，介绍了空值环境下的函数依赖，增强关系数 据库的表达能力。由于空值的引入，使得函数依赖变得非常复杂，抽象地讲某个 关系是否满足空值环境下的函数依赖( n f d ) 是不行的，空值环境下研究函数依 赖要考虑函数依赖的强保持、亚强保持、弱保持，从保持条件入手研究函数依赖 定义空值环境下的部分函数依赖( n p f d ) 和空值环境下的完全函数依赖( 陌d ) 以及键的定义。同样，在关系数据库中，由于空值的存在而使得传统数据依赖公 理系统的存在性也受到了严重的挑战，有的公理在非空值环境下存在，但在空值 环境都不存在了，这样研究空值环境下关系数据库的函数依赖公理存在性和完备 性是必要的。 郝忠孝【3 0 】对含有空值的关系数据库研究其关系运算、数据更新、查询、数据 依赖和范式进行理论研究，其中数据依赖主要包括函数依赖、多值依赖、连接依 山东大学硕士学位论文 赖。 m a r kl e v e n e 3 1 1 称含有存在但暂时未知的值得关系为不完全关系，主要研究 不完全关系的定义、函数依赖、覆盖问题、键等问题。 s a b i t e b o u l l 3 2 1 主要研究含有不完全信息的基于d t d 标准的x m l 文档的表示 和查询。不完全信息通过连续的查询被不断丰富，参考关系数据库的表示方法， 提出一种表示方法描述通过连续查询获得的源文件的部分数据。 x m l 文档作为信息传输和交换的标准，希望x m l 文档中节点出现这些不完 全信息时能进行处理，这样我们就要考虑在x m l 文档中进入空值的概念，在空 值环境下对x m l 文档作进一步的研究。而能否通过x m l 文档中的数据发现那 些可以补全的不完全信息，这就需要对x m l 文档的函数依赖进行一定的研究， 这个问题到目前为止，国内外的研究者所做的工作还很有限。我们希望通过这些 研究来增强x m l 文档表达现实世界的能力，这样的模型才具有更大的实际意义。 1 3 研究内容及意义 1 3 1 研究内容 首先，我们可以先来看一个例子，某连锁超市其商品的内部管理系统使用的 是纯x m l 数据库，而且各个连锁店之间信息的交换使用的是x m l 文档。连锁 超市各个分店由于历史或者其他的原因，使用的x m l 模式不尽相同，这样在数 据汇总和分析的时候就难免会出现不完全信息的现象( 如图1 中所示) 。 下面我们来具体的看一下。s t o r e 0 2 在进行促销，对于分类为c a t e g o r y = 0 3 的体育用品进行8 5 折销售，而c o m m o d i t y 1 0 为新品，其商品信息是由厂商提 供的，还没有登记折扣信息，这样这个商品的d i s c o u n t 1 4 节点就成了包含不完 全信息的空值节点。而s t o r e 2 4 是最新加盟的连锁店，其原有的x m l 模式里面 不含有n a m e 属性。这样节点 2 8 】就成为了另一种具有不完全信息的空值节点。 最后，由于研究的需要我们可以将p r i c e 2 9 设成一个具有不完全信息的空值节 点。这些具有不完全信息的空值节点，我们在图1 中都使用上来表示，即： d i s c o u n t 14 = 上、n o d e 【2 8 】_ 上、p r i c e 2 9 = 上。 6 山东大学硕士学位论文 图l ：一个x m l 文档的例子 显示了一个连锁超市及其商品的基本信息。x m l 文档中每个元素都按照深度优先 顺序标记了一个键值( 用 n 表示) 。图中的j 一表示一个不完全信息。 这些不完全信息可以通过人工编写一些x m l 数据库操作语句来进行补全， 但是在日常生活中的经验可以帮助我们发现，只需要找出一些规律，这些内容就 是可以自动补全的。这里的经验，用我们数据库的语言来说，就是函数依赖 ( f u n c t i o nd e p e n d e n c e ) 。函数依赖是一个关系中各个属性之间的关系：一个函 数依赖表明了某个属性的值由其他属性唯一确定的。自动的数据库分析是知识发 现和数据挖掘所感兴趣的，并且函数依赖在数据库管理和查询优化领域也是大有 用途的。 本文的研究就是试图通过对x m l 数据进行属性划分的比较，发现其中对于 不完全信息的补全有价值的函数依赖，然后使用这些函数依赖进行x m l 数据中 不完全信息的发现工作。本文的主要内容为： 1 、在x m l 数据中引入不完全信息的概念，即在树节点中存在一些节点的值 为空值的情况，形成一棵不完全信息树。 2 、x m l 关于不完全信息树的模型，在不完全信息树中节点分为两类元素节 点、属性节点。其中元素节点没有值只有名称、属性节点既有名称又有节点值。 也就是说元素节点是树模型中枝节点即非叶子节点，属性节点在树模型中为叶子 节点。 7 山东大学硕士学位论文 3 、x m l 不完全信息的之间关系，在x m l 文档中引入不完全信息使得文档 树中节点的关系变得复杂化，扩展了完全信息树中节点值相等的单一关系进一步 定义了节点之间存在节点值等价、节点值相容及由此而产生的树元组之间的等价 和相容关系。 4 、关注于不完全信息的x m l 函数依赖是本文进行研究的有力工具，如何有 效的发现这些函数依赖是本文进行论述的重点。本文试图通过对x m l 数据进行 属性划分的比较，发现其中对于不完全信息的补全有价值的函数依赖，并通过一 系列的优化技术，减少比较多次数，提高了算法的效率。 5 、利用有价值的x m l 函数依赖，x m l 数据库可以通过对其数据的分析， 动态的追赶不完全信息的可能值，最终补全不完全信息。 1 3 2 研究的理论价值及现实意义 随着互联网络时代的到来，数据越来越多地开始以网络在线的方式进行存 储、集成、发布和交换。由于x m l 具有跨平台，简单易用等特性，在很短的时 间内就获得了广泛认同，在众多应用领域中，已成为一种被广泛使用的通用数据 格式。x m l 己经成为目前i n t e m e t 上主要的数据表示和交换的标准之一。x m l 作为一种半结构化数据的表示模型，具有很强的数据的信息表现力，它既可以表 示结构化的数据又可以表示非结构的数据。但在现实世界中常常存在一些不完全 的信息，如数据交换过程中出现的因为x m l 模式不同而产生的不完全信息。这 些不完全信息在现实世界中是普遍存在的，因此需要我们进行研究使得x m l 也 可以表达这些信息。 不完全的信息在关系数据库中给出了定义并进行研究。在经典的关系数据库 的应用理论研究中，引入空值就可以解决上述不完全信息的表达。在关系数据库 中引入了不存在型空值、存在型空值、占位型空值它们的语义分别为关系的某一 个元组在某一属性上不应该有任何实值、关系的某一个元组在某一属性上必然对 应着某个或几个实值、关系的某一个元组在某一属性上尚不知道是否存在某实 值，有了这三种类型的空值关系数据库就能更充分地表示现实世界。这样的关系 数据库称为不完全关系。 x m l 文档作为信息传输和交换的标准，希望x m l 文档中出现这些不完全信 山东大学硕士学位论文 息时能进行处理，而且希望能够动态的发现有价值的函数依赖并通过这些函数依 赖来补全这些不完全信息。这个问题到目前为止，国内外的研究者所作的工作还 大多数是在理论研究上，如何将其有效的放到应用当中是本文研究的重点。我们 希望通过这些研究来增强x m l 文档表示现实世界的能力，把原有关系数据库理 论应用到x m l 的研究中，推动理论和实际相结合从而产生巨大的效益。 1 4 本文结构 本文共分为七章，本文结构及各章节的内容组织如下： 第二章给出了相关的概念，这些概念是本文将要用到的和研究的基础，其中 2 1 是x m l 简单介绍；2 2 介绍了x m ls c h e m a 的基本定义，比较了x m ls c h e m a 与d t d 的不同，说明了为什么本文使用x m ls c h e m a 进行研究；2 3 给出了扩 展树的概念，将不完全信息引入到x m l 数据库当中；2 4 在扩展树的基础上定 义了扩展树元组和扩展树元组类，为函数依赖的概念作了铺垫；2 5 介绍了节点 相等的概念，节点相等时我们发现函数依赖以及利用函数依赖中最常用到的概 念，在这里给出了清晰的定义。 第三章给出了动态发现x m l 中有价值的函数依赖的算法。3 1 首先介绍x m l 函数依赖的概念。3 2 介绍的相容节点与不相容节点是我们处理空值信息时必须 要处理的问题。3 3 说明了属性划分和划分加细是验证函数依赖的重要手段。3 4 介绍了一个优化算法的工具- x 加，属性集格子，通过对边的约减可以大幅减 少运算量。3 5 是本章的重点，介绍了关注于不完全信息的函数依赖的动态发现 的两个相关算法( m a r k 、d i s c o v e r f d s ) 。 第四章是x m l 中不完全信息的动态发现。在第三章得到了有价值的函数依 赖之后，这一章要进行相应的补全工作。本章首先介绍了追赶算法的原理，然后 介绍了x m l c h a s e 算法。 第五章对前面的算法进行了可行性分析及实验。 第六章总结了本文的工作并对以后的研究方向进行了展望。 9 山东大学硕士学位论文 第二章研究基础 本章在己有的x m l 基本知识的基础上，形式化的描述了x m ls c h e m a ，x m l 扩展树和扩展树元组等基本定义，并进一步定义了节点值相等和扩展树元组类等 概念，为后面章节中的讨论作符号上的准备。为了便于x m l 数据库不完全信息 发现的研究，本章将从文献中引用来的定义和符号做了形式化上的统一描述。 2 1x m l 简介 2 1 1x m l 与标签 x m l 是一种把数据表示为一个文本字符串的语言，这个文本字符串包括用 于描述数据分布的“标签( t a g ) ”。使用标签可以把文本和与它的内容或形式相关 的信息聚集在一起。 标签用角括号“ ”包含字符( 例如，” ”) 来区别字符数据( 非标 签文本1 。因此，一个字符串、一个文档由标签和字符数据组成，这些结合起来 就形成了元素。一个元素以一个开始标签开始，以一个结束标签结束。结束标签 用角括号和一个用来区分开始标签的正斜杠，“”来表示，像“ ”。标签提 供一种机制来给文档添加元内容和结构信息。 第一个通用标记语言g m l ( g e n e r a lm a r k u pl a n g u a g e ) 发明于1 9 6 9 年，主要 用于支持文档处理应用。1 9 7 4 年出现了通用标记语言标准s g m l ( s t a n d a r df o r g e n e r a lm a r k u pl a n g u a g e ) ，并且从19 7 8 年到19 8 0 年它不断被国际化标准组织修 改和发展，以满足系统的独立性和国际交换的要求，这些要求使得用于处理当时 己有的异构系统的广泛选择成为必要。 谈到x m l ，不能不涉及超文本标记语言h t m l ( h y p e rt e x tm a r k u p l a n g u a g e ) 。h t m l 是符合s g m l 语法的一种固定格式的超文本标记语言，它是 最早应用于网络信息传输的标记语言，也是近几年网上最普及的一种网页制作通 用语言。因其格式固定所以难以扩展，它主要用于显示信息的内容，侧重于w e b 1 0 山东大学硕士学位论文 页面表现形式的描述，大大丰富了页面的视觉效果，为推动w w w 的蓬勃发展、 推动信息和知识的网上交流发挥了不可替代的作用。但是，它并没有反映出信息 的结构，它自身的特点使它蕴藏了许多危机，随着自身的不断发展，这些危机不 但没有减弱，反而越来越突出，甚至成为h t m l 继续发展应用的障碍。h t m l 的主要局限性在于；h t m l 不允许对页面上的个别元素进行语义性的标注； h t m l 只描述文件外貌，但无法涵盖任何实质内容，因此不适合用于明确的查询 方式：h t m l 无法延伸，因此无法根据特殊规格来定义自己的标签，也无法在文 件内部使用格式。h t m l 的标记集合完全可以用x m l 来定义。x m l 与h t m l 都是用一对互相匹配的标签来标记信息，但h t m l 描述的是数据的显示方式， 现在网上通用的文档语言是h t m l ，尽管这也是一个存储、显示数据的可行的办 法，但是它的效率和能力却非常有限，它至少存在以下三个严重的问题，首先， h t m l 的显示方式内嵌于数据之中，如果某个时候需要改用表格来表示这些数 据，那么它不得不重新编码所有的h t m l 文件；其次，在数据中寻找信息非常 困难，需要编写一个脚本程序；最后，数据自身的逻辑不得不让位于h t m l 的 语言规范的逻辑。而x m l 则侧重于描述数据本身，它遵循严格的语法要求，并 且便于不同系统间的信息传输，具有良好的保值性。最重要的是，x m l 的标签 集合不是固定的，x m l 不仅允许自定义一套标记，而且这些标记不必仅限于对 显示格式的描述。x m l 允许根据各种不同的规则来制定标记，用户可以根据自 己的需要定义任何一种标签来描述自己文档中的数据元素。因此x m l 作为w r e b 上的信息表示和交换的标准，而h t m l 作为在浏览器端显示的工具。从x m l 到 h t m l 的转换工具是可扩展样式表语言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 的出现并不是为了取代h t m l ，而是为了更好的在i n t e m e t 上进行数 据传输与交换。两者的详细比较见表1 。 x m l 是s g m ，的一个配置，设计于9 0 年代后期，它给s g m l 提供在w 曲 环境中的可扩展能力。x m l 不完全像s g m l ，它不允许自由选择，只支持为w e b 做出的选择，因此它就易于学习和使用。 山东大学硕士学位论文 表1 ：h t m l 与x m l 的比较 h t m lx m l 可扩展性不具有可扩展性是源标记语言，可用于定 义新的标记语言 侧重点侧重于如何表现信息侧重于如何结构化的描述 信息 语法要求不要求标记的嵌套、配对严格要求嵌套、配对等， 等