基于键的XML模式到关系模式的规范化转换

本文针对XML模式向关系模式转换过程中形成的冗余和不规范,提出一种基于XML键的XML模式到关系模式的规范化转换算法。该算法以键为基础,根据XML函数依赖的一组推理规则,扩充函数依赖的集合,避免XML模式向关系模式转换过程中语义丢失的情况;再利用一组消解规则,消除冗余的函数依赖,使其满足极小函数依赖集;最后以键为中心划分关系属性,得到关系表,并且保证得到的关系模式满足3NF。     

数据集成中XML Schema到关系模式的转换方法

根据XML Schema中组件的定义及组件之间的嵌套关系,建立一系列从XML Schema转换成关系模式的结构映射规则和语义映射规则。基于这些规则实现一种转换算法,从Schema中提取出关系模式,并且证明映射得到的关系模式满足4NF。结果表明得到的关系模式不仅包含了XML Schema中所有的结构和内容信息,还能保留大部分语义约束信息,减少存储冗余。     

Propagating XML constraints to relations

We present a technique for refining the design of relational storage for XML data. The technique is based on XML key propagation: given a set of keys on XML data and a mapping (transformation) from the XML data to relations, what functional dependencies must hold on the relations produced by the mapping? With the functional dependencies one can then convert the relational design into, e.g. 3NF, BCNF, and thus develop efficient relational storage for XML data. We provide several algorithms for computing XML key propagation. One algorithm is to check whether a functional dependency is propagated from a set of XML keys via a predefined mapping; this allows one to determine whether or not the relational design is in a normal form. The others are to compute a minimum cover for all functional dependencies that are propagated from a set of XML keys and hold on a universal relation; these provide guidance for how to design a relational schema for storing XML data. These algorithms show that XML key propagation and its associated minimum cover can be computed in polynomial time. Our experimental results verify that these algorithms are efficient in practice. We also investigate the complexity of propagating other XML constraints to relations. The ability to compute XML key propagation is a first step toward establishing a connection between XML data and its relational representation at the semantic level.     

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

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

Constraint Preserving Transformation from Relational Schema to XML Schema

XML has become the standard for publishing and exchanging data on the Web. However, most business data is managed and will remain to be managed by relational database management systems. As such, there is an increasing need to efficiently and accurately publish relational data as XML documents for Internet-based applications. One way to publish relational data is to provide virtual XML documents for relational data via an XML schema which is transformed from the underlying relational database schema such that users can access the relational database through the XML schema. In this paper, we discuss issues in transforming a relational database schema into the corresponding XML schema. We aim to preserve all integrity constraints defined in a relational database schema, to achieve high level of nesting and to avoid introducing data redundancy in the transformed XML schema. In the paper, we first propose a basic transformation algorithm which introduces no data redundancy, then we improve the algorithm by exploring further nesting of the transformed XML schema.     

基于树元组的XML函数依赖研究

与关系数据库一样,XML文档可能由于函数依赖而产生数据冗余或操作异常,在关系数据库中对于函数依赖的理论体系的研究已经比较完善,但对XML函数依赖的研究才刚刚起步.结合XML文档类型定义DTD进行探讨,提出基于树元组的XML函数依赖的概念,并结合Armstrong公理系统推导出函数依赖的推理规则集.     

XML函数依赖研究

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

XML DTD的一种范式

研究了XML DTD的规范化问题。由于DTD在设计上存在不足之处，DTD中可能包含类似于关系数据库模式中存在的异常依赖，从而导致XML文档包含冗余的数据和各种操作异常。提出了关于DTD的多值依赖的概念，然后基于多值依赖的概念，提出了一种XML的范式XNF，并且用DTD的关系表示形式给出了关于DTD的无损联接分解的概念。最后给出了把DTD无损联接地分解成XNF的一种算法。     

消除结构冗余的XML数据库模式规范化设计

XML数据库模式规范化设计是给出一个能很好地表示数据间依赖关系并消除了冗余的XML模式或DTD的集合．目前这一领域的研究并没有对XML数据库模式中的数据依赖和冗余进行专门的分析．引人标识符分别表示XML模式中的元素和属性，分析XML数据库模式的结构冗余：局部冗余、传递冗余和不规则；并在此基础上，定义XML数据库模式第3范式(3NF)，给出并验证其规范化设计算法．     

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

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

基于关系语法树的C/C++代码静态检测方法研究

为减少软件静态分析中信息冗余度并提高信息提取的准确率和效率,提出了一种基于关系存储模式的关系语法树模型,以终结符之间的依存关系建模,有效地减少了信息冗余度,并以可扩展标记语言(extensible markup language,XML)标准格式存储.利用了成熟的XML解析技术,设计了一种基于XML中间模型的静态检测方法,并将该方法应用于编程规范检测申.实验结果表明,该方法有效地提高了检测效率和精度.     

XQuery speedup by deploying structural redundancy in mapping XML into relations

In designing a relational schema, we often consider that an attribute of a table is replicated into other table to reduce the join cost. Maybe such a possible redundancy will be grasped through E/R model (i.e. semantic analysis). Similarly, in mapping XML into relations, we can consider some redundancies to enhance query performance and they can be grasped through the structural traits of DTD (or XML schema). Several practical structural redundancies are formulated in this paper. If given XML data and queries are very large and complex, finding essential replications may also be difficult, and two efficient search methods are introduced for helping the search. Since the search problem is NP-hard, the methods are heuristically designed. Finally, read and update query costs arising by employing the structural redundancy are analyzed experimentally and the efficiency of two search methods is analyzed. They showed that the replication strategy can be very useful.     

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已成为Internet上的技术趋势,在保留原有关系数据库的同时发展XML文档是目前的最佳选择,它需要在保持数据依赖约束基础上实现关系数据库与XML文档的转换.这一过程中,模式转换必须先于数据转换,因为现有的关系数据库通常是规范化的,重建XML文档树结构才能实现这一转换.为了达成此目的,首先依据已有的数据依赖约束将规范化的关系联合进一组表格,实现反向规范化,然后将这些联合表格映射为一组DOM,归并成XML文档树,根据用户选择的根结点,以及与它相连的结点形成一个期望的局部文档树,被选的XML文档树又映射为DTD格式的XML模式.这样就可以将联合表映射成一组DOM,并将其归并成单一DOM,最终转换成XML文档.     

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

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

Efficient queries over Web views

Large Web sites are becoming repositories of structured information that can benefit from being viewed and queried as relational databases. However, querying these views efficiently requires new techniques. Data usually resides at a remote site and is organized as a set of related HTML documents, with network access being a primary cost factor in query evaluation. This cost can be reduced by exploiting the redundancy often found in site design. We use a simple data model, a subset of the Araneus data model, to describe the structure of a Web site. We augment the model with link and inclusion constraints that capture the redundancies in the site. We map relational views of a site to a navigational algebra and show how to use the constraints to rewrite algebraic expressions, reducing the number of network accesses. We show that similar techniques can be used to maintain materialized views over sets of HTML pages.     

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

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

一种基于分层框架的XML发布方法

因特网的不断发展使得XML成为Web上数据交换和表示的标准格式,但是大量的商业数据仍然存储在关系数据库中。因此必须将关系数据发布成XML文档进行传输。提出了一种基于分层框架结构的关系数据库向XML的映射方法,并在分层结构中定义了一种XML模式图作为XML的概念模型。得到的XML文档能够很好地反映关系数据库的语义和各种约束并且没有引入数据冗余。初步实验结果表明方法具有较高的效率和较好的准确性。     

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

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

基于DTD的XML文档到关系模式的映射规则研究

近年来,XML已逐渐成为Internet上不同平台间数据表示及数据交换的标准。将XML数据存储到技术成熟的关系数据库中已是一种比较主流的选择。在XML文档到关系模式的映射规则这个领域已做的研究中,一些已经提出的映射规则虽然考虑到了映射过程中产生的数据冗余、数据语义以及约束保留等问题,但是解决上述问题有时会导致XML数据的查询效率的降低。文章针对上述问题,在基于结构、约束保持及语义保持等方面对映射规则进行了更深入的研究,提出相应一系列基于DTD的映射规则,并根据XML文档蕴涵的语义信息提出了建立对应的关系模式中的索引,以使其在XML数据的查询效率及数据冗余消除方面有所提高。该文还通过使用一些公用数据集,进行了实验与分析,验证了以上提出规则的有效性。