论文部分内容阅读
XML已经成为Internet上数据表示和数据交换的标准格式。为了直接存储和访问大量出现的XML文档,原生XML数据库逐步发展起来,许多XML处理技术(如XQuery,XML Schema)也正在日益成熟。为了更加有效地组织和使用XML数据,XML中需要包含更为丰富的语义信息。数据语义约束是一类重要的语义信息,对维护数据一致性,有效地使用数据有着重要的作用,其在关系数据库中得到了深入的研究,是关系数据库理论的基础。将数据语义约束引入XML中,可以促进原生XML数据库技术的发展,完善相应的理论,并为其他相关的XML数据处理技术(如XML视图更新,XML概念建模)提供必要的支持。因此,本文的研究在XML数据处理的理论和实践中都有着重要的意义。
XML数据语义约束的现有研究中,大多采用基于路径的表示方法,但碍于路径的表达方式与求值语义的限制,对于描述XML树形结构数据中多层次信息的需求具有一定的局限性,很难灵活地表达规定数据语义约束的需求。现有对于XML数据语义约束蕴涵问题的研究大都基于关系数据库中已有技术,对XML数据模型特有的问题分析得还不够深入。此外,对于基于XML数据语义约束进行XML模式规范化等基础理论的研究在深度与广度上都还存在着不足。
本文提出了一种XML数据语义约束的层次化表示方法(HierarchicalRepresentation for XML Data Semantics Constraint,简写为HR-XDSC),支持更为丰富的XML函数依赖,XML多值依赖和XML包含依赖关系的描述,并将该方法扩展到XML Schema中。针对HR-XDSC所描述的XML函数依赖(XFDs)和XML多值依赖(XMVDs),提出了XML数据语义约束蕴涵问题的判定方法与公理体系。同时,根据所发展的XML函数依赖给出了XML范式(XML-BCNF和XML-3NF)的概念,提出XML模式规范化方法并且深入分析了规范化的性质。本文还研究了XML视图更新问题及XML概念建模问题,说明和强调了XML数据语义约束在其中所起的作用,从侧面表明开展XML数据语义约束技术研究的重要意义。
本文的创新性成果和主要贡献如下:
(1)本文为XML数据语义约束的描述,提出了一种新型的层次化表示方法,简称HR-XDSC。HR-XDSC方法采用层次化的路径组织结构,为灵活地描述XML文档树形结构中各层的信息项提供支持,能够描述更为丰富的XML函数依赖、XML多值依赖与XML包含依赖关系。在三种依赖关系的满足性检验算法的研究中,提出了匹配树的概念,解决了复杂类型值比较问题；并发展了空值比较问题的处理策略。这些研究说明HR-XDSC方法和传统方法相比,能够有效地描述更丰富的XML函数依赖、XML多值依赖和XML包含依赖关系。
(2)针对HR-XDSC所描述的XML函数依赖和XML多值依赖,本文提出了相应蕴涵问题的判定方法与公理体系。对于只包含XML函数依赖的蕴涵问题,分析了声明于不同元素中的XML函数依赖对蕴涵问题的影响,并基于路径闭包的概念给出了线性时间复杂度的判定方法,以及一组用于推导的公理,同时说明了XML函数依赖蕴涵问题与Horn子句的逻辑蕴涵问题的等价关系。对于只包含XML多值依赖的蕴涵问题,本研究给出了基于路径依赖基的判定方法及相应推导公理。对于既包含XML函数依赖,又包含XML多值依赖的蕴涵判定问题,本研究发展了相应的chase技术。和传统方法相比,这些蕴涵判定方法和公理体系的适用范围更广,足以支持HR-XSDC所描述的XML函数依赖和XML多值依赖。
(3)基于HR-XDSC所描述的XML函数依赖,本文给出了XML范式的概念,包括XML-BCNF和XML-3NF。本文证明了XML数据中不包含XML函数依赖引入的数据冗余当且仅当其对应的模式满足XML-BCNF。本研究提出了XML-BCNF的规范化算法,其时间复杂度为O(n2),同时证明了算法的终止性和正确性。本研究发展了信息无损和依赖保持的概念,并证明了XML-BCNF规范化算法是信息无损的,但不是依赖保持的。本文还提出了XML-3NF的规范化方法,对该方法的分析说明XML-3NF的规范化是依赖保持的,但不能确保消除可能存在的冗余。和既有XML范式研究相比,上述规范化算法针对HR-XDSC方法所描述的XML函数依赖引入的数据冗余,能够在更广的范围内避免数据冗余和更新异常。
(4)分析了XML视图更新和概念建模等相关问题。针对XML视图更新问题,提出了扩展更新语义的设想,即允许XML数据语义约束引入的副作用,并给出了一种视图更新框架,其中应用一种三层模型(概念层,逻辑层,物理层)构建XML视图。在这种视图更新框架中,视图定义阶段和视图更新阶段,都可以捕获XML数据语义约束的信息,使视图定义包含更多的语义信息而不只是简单的查询定义。针对XML概念建模问题,依据XML数据自身的特点提出了Object-Relationship-Constraint(ORC)模型,采用一种两阶段建模方法,可以捕获XML数据语义约束信息,为解决XML视图更新等问题提供支持。