XML模式中隐式冗余不存在的充分条件

XML数据库模式规范化设计是产生一组相关联的、能很好地表示数据间依赖关系、而且消除了冗余的XML模式或DTD,以更好地进行信息检索.XML数据库模式中某些数据依赖是冗余存在的原因.因此在XML数据库模式中数据依赖与冗余的性质以及关联是其规范化设计要解决的关键问题.XML数据库模式的数据依赖包括属性间数据依赖和元素间的数据依赖.在以往的工作中,已经给出XML数据库模式中元素间的数据依赖及其所关联的显式冗余的有关性质,并基于此实现和验证相应的XML数据库模式规范化设计算法.分析XML数据库模式中属性间的数据依赖、元素间的数据依赖及其关联,定义XML数据库模式数据依赖及其相关联的隐式冗余,并论证XML数据库模式中隐式冗余不存在的充分条件.     

XML模式中隐式冗余不存在的充要条件

XML数据库模式规范化设计是产生一组相关联的、能表示数据间依赖关系、而且消除了冗余的XML模式或DTD,以更好地进行信息检索.XML数据库模式中某些数据依赖的存在是冗余存在的原因,因此在XML数据库模式中数据依赖与冗余的关联是其规范化设计研究的关键问题,但对这一问题目前还没有专门的研究.XML数据库模式的数据依赖包括属性间数据依赖和元素间的数据依赖,给出综合了属性间和元素间数据依赖的XML数据库模式数据依赖的定义,分析与之关联的隐式冗余,并论证XML模式中隐式冗余不存在当且仅当该XML模式是规范的,为XML数据库模式规范化设计更深一层的研究奠定理论基础.     

XML数据库模式中的数据依赖、结构冗余和不规则

XML数据库模式规范化设计是产生一组相关联的、能表示数据间依赖关系、而且消除了冗余的XML模式或DTD,其目的是为了互联网上的信息检索能够避免异常. XML数据库模式中某些数据依赖的存在是冗余存在的原因,因此在XML数据库模式中数据依赖与冗余的关联是其规范化设计研究的关键问题. XML数据库模式的数据依赖包括属性间数据依赖和元素间的数据依赖,与之关联的结构冗余和不规则是指在XML模式的结构上存在冗余和不规则的情况.给出综合了属性间和元素间数据依赖的XML数据库模式数据依赖的定义,分析与之关联的结构冗余以及不规则的情况,基于此定义消除结构冗余和不规则的规范的XML模式森林作为范式,给出并验证其规范化设计算法.     

基于路径表达式的XML第四范式及无冗余性判定

随着XML应用越来越广泛,为避免冗余,XML模式设计也变成了越来越受关注的问题,因此XML规范化理论是一个重要的研究领域.类似于关系数据库,本文从数据库角度出发,以消除数据冗余为目的,研究DTD中以路径表达式为基础的基本定义;因函数依赖和多值依赖是数据语义的重要组成部分,将其引入到XML领域中,形式化定义了XML的函数依赖和多值依赖;基于XML树、函数依赖和多值依赖概念,给出了键、冗余的描述,进而在XML函数依赖和多值依赖并存情况下,提出了满足XML第四范式的条件;给出了满足XML第四范式条件的XML文档树无冗余的判定定理,并通过具体实例及实验证明了XML第四范式的有效性.     

用于XML模式和DTD规范化设计的层次模式设计

XML模式和DTD(document type definition)规范化设计是给出一个很好地表示数据间依赖关系并消除了冗余的XML模式或DTD的集合.目前在这一方面开展的研究还不多,而且才刚起步.Provost提出将关系数据库理论应用于XML模式规范化设计的思想,这一思想还没有付诸实施.在Provost思想的基础上给出用于XML模式和DTD规范化设计的层次模式设计的算法.首先分析了基于Provost思想的层次分解;然后给出用于消除冗余模式的分解树设计算法;最后给出用于XML模式和DTD规范化设计的层次     

XML多值依赖及其消除冗余模式的算法*

从消除XML文档内数据冗余的角度出发研究了文档的规范化问题.首先引入XML上的数据冗余及其消除处理示例,同时基于函数依赖,提出了规范化的DTD概念和XML DTD 规范化处理规则;其次通过XML多值依赖的定义,给出用于消除冗余模式的算法;最后给出用于XML模式及其消除冗余模式的算法.该算法相应于其他XML模式的研究,在算法产生的层次模式中,完全MVD和嵌入MVD的集合由给出的MVD集合导出;并且产生的XML模式具有消除冗余模式和满足无损连接的特性.     

消除XML键数据冗余的相关规则

XML数据已经成为Internet上的主流数据,但目前大部分XML规范化理论局限在层次的冗余上,从数据库的角度出发,以XML键为中心结合函数依赖FD和多值依赖MVD描述XML数据间的约束;基于主键、副键分析不同情况下的数据冗余,给出相应的规范化规则,得到消除数据冗余的XML模式。     

基于约束的XML文档规范化算法

XML模式设计是XML数据库设计的关键．基于XML文档的基本概念给出了XML部分函数依赖、传递函数依赖、XML范式、XML第1到第3范式以及DTD无损联接分解的相关定义，提出XML模式规范化转换规则，给出无损联接分解的两种规范化算法，对算法的正确性、可终止性和时间复杂性进行了证明分析，并实验证明了规范化后的文档查询和存储效率有明显的提高．这将对未来的XML函数依赖保持、XML多值依赖以及XML模式设计的进一步规范化研究奠定理论基础．     

基于函数依赖的XML冗余检测算法

XML保持语义下的冗余检测问题对于防止XML文档的更新异常和减少XML冗余信息的存储具有很大意义,是XML规范化理论的关键问题之一。对XML schema、树元组、XML键、XML范式等进行研究,定义基于schema的XML函数依赖形式化模型,并基于该定义模型设计一种新的XAP算法,可有效发现XML文档中的函数依赖和冗余,并对算法的复杂性进行分析。     

XML函数依赖研究

为了消除数据冗余，基于关系数据模型的函数依赖理论已经被广泛接受并应用于关系数据库的设计中。XML数据库中同样存在数据冗余。为了设计没有冗余的XML数据库，需要用一种简洁、易于理解的方法来定义XML数据问依赖关系。在无序的结点标记树数据模型上定义了XML子树间的函数依赖，并且给出了一套公理系统用来推导函数依赖，以解决函数依赖的蕴涵问题，最后证明了该公理系统是合理的。     

XML schema refinement through redundancy detection and normalization

As XML becomes increasingly popular, XML schema design has become an increasingly important issue. One of the central objectives of good schema design is to avoid data redundancies: redundantly stored information can lead not just only to a higher data storage cost but also to increased costs for data transfer and data manipulation. Furthermore, such data redundancies can lead to potential update anomalies, rendering the database inconsistent. One strategy to avoid data redundancies is to design redundancy-free schema from the start on the basis of known functional dependencies. We observe that XML databases are often “casually designed” and XML FDs may not be determined in advance. Under such circumstances, discovering XML data redundancies from the data itself becomes necessary and is an integral part of the schema refinement (or re-design) process. We present the design and implementation of the first system, DiscoverXFD, for efficient discovery of XML data redundancies. It employs a novel XML data structure and introduces a new class of partition-based algorithms. The XML data redundancies are defined on the basis of a new notion of XML functional dependency (XML FD) that (1) extends previous notions by incorporating set elements into the XML FD specification, and (2) maintains tuple-based semantics through the novel concept of Generalized Tree Tuple (GTT). Using this comprehensive XML FD notion, we introduce a new normal form (GTT-XNF) for XML documents, and provide comprehensive comparisons with previous studies. Given the set of data redundancies (in the form of redundancy-indicating XML FDs) discovered by DiscoverXFD, we describe a normalization algorithm for converting any original XML schema into one in GTT-XNF.     

不完全信息环境下存在XML强多值依赖的XML文档规范化研究

不完全信息环境下XML文档中的数据存在多值依赖时.为了避免在没有约束条件下XML文档数据出现冗余及更新异常,引入XML强多值依赖的概念和理论对XML文档的规范化进行了系统研究.基于节点信息等价、节点信息相容的概念给出了XML强多值依赖的定义;基于层次化的XML强多值依赖,提出了不完全XML文档树满足XML强多值依赖范式的条件;给出了满足该条件的不完全XML文档树无数据冗余的判定定理;提出了不完全XML文档树的规范化算法,对其时间复杂性进行了分析.理论研究和实例分析表明:研究成果较好地解决了在不完全信息环境下XML文档中存在层次化的XML强多值依赖引起的数据冗余问题.     

不完全信息环境下XML Schema规范化研究

为了解决不完全信息环境下XML模式设计中XML文档的数据冗余和操作异常,研究了不完全信息环境下XML Schema的规范化问题,提出了XML Schema和符合XML Schema的不完全XML文档树等概念;基于节点等价、节点相容、节点信息等价和节点信息相容等概念提出了XML强函数依赖的定义,给出了相应的推理规则;给出了求路径集强闭包和成员籍问题的算法,并对算法的正确性进行了证明,对其时间复杂度进行了分析。提出了不完全信息环境下XML范式和相应的规范化算法。研究成果较好地解决了数据冗余问题,避免了更新异常现象,更好地实现了XML Schema设计     

从DTD映射到关系模式:一种保持数据依赖的映射方法

XML正迅速成为互联网上数据表示和交换的标准．用关系数据库存储XML数据是XML存储策略之一．为了将XML数据存储到关系数据库中，人们研究了从DTD到关系模式的映射方法．提出了一种保持数据依赖的映射方法PDD．与已有的Shared—Inlining方法相比，PDD方法充分考虑了DTD蕴涵的数据依赖关系，保证了XML文档的完整性．通过对泛关系进行模式分解，得到的关系模式保持函数依赖，并且满足2NF．可以证明，这种方法是有效的．     

存在XML强多值依赖的XML Schema规范化研究

为了解决不完全信息环境下XML模式设计中XML文档的数据冗余和操作异常,研究了不完全信息环境下存在XML强多值依赖的XML Schema规范化问题;提出了XML Schema、符合XML Schema的不完全XML文档树等概念;基于子树信息等价和子树信息相容的概念给出了XML强多值依赖的定义;提出了弱键路径和XML强多值依赖弱范式的定义;通过实例分析了在XML Schema中XML强多值依赖引起数据冗余的原因,提出了转换规则,给出了规范化算法。研究成果可较好地处理XML文档中出现大量不完全信息时的数据冗余问题,实现不完全信息环境下更好的XML Schema设计。     

函数依赖和规范化在关系和XML间的传播

XML和关系的结合是一个重要的研究领域,讨论函数依赖和规范化在关系及XML间的传播问题.首先引入XML上函数依赖和键的定义,并进一步定义XML上的数据冗余和规范化DTD的概念.分别讨论在关系和XML相互转化的过程中,函数依赖的传播问题.针对一种一般化的关系模式DTD表示,证明原有关系中的函数依赖可以在生成的XML文档上得到表示.针对一种常见的XML关系存储方法,说明最终生成关系上的函数依赖与原有XML上函数依赖的对应关系.函数依赖传播的核心意义在于规范化的传播.证明使用上述方法时,若原有的关系是满足BCNF的,则发布得到的DTD也是规范化的;若原始的DTD是规范化的,则得到的关系存储也满足BCNF范式.     

存在多值依赖的XML DTD规范化研究

XML DTD文档中可能包含由非函数依赖引起的数据冗余和操作异常，首先从消除DTD文档内数据冗余的角度出发研究了文档的规范化的问题，讨论了在DTD文档中存在多值依赖的情况下，如何规范XML文档，提出了以DTD为模式的XML文档的多值依赖的概念。然后基于多值依赖的概念，提出了XML文档的一种多值依赖范式MXNF。最后在此基础上提出了把一个XML文档的DTD无损联接地分解成为符合MXNF的规范化算法，来规范存在多值依赖的XML DTD文档，并给出了该算法的分析说明。