XML数据库并发加锁协议的研究

针对XML数据动态树型结构的特点,定义了内容操作集和结构操作集.在此基础上,提出一种基于此操作集的动态加锁协议以及锁模型,并证明了此加锁协议下的调度是可串行化调度,从而实现了XML原生数据库的事务并发控制.     

基于关系数据库的XML分解存储方案

本文给出了一个基于关系数据库的XML分解存储方案。首先,通过对XML语法的分析,定义了XML树,XML树是一棵结构规则的树：所有的节点都具有相同的格式。通过XML树可以把结构不规则的XML文档映射成结构规则的XML树。其次,通过定义关系XSR,将XML树存储到关系数据库中去。该方案可以保证数据的完整性。在分解存储时,一个XML文档只需映射到一个关系表,而其它分解方案一般需要映射到多个关系表。该方案是一个通用方案,可以处理任意的XML文档。     

XML文档到关系数据库映射方法的研究*

针对现有映射方法对XML文档格式要求过严等不足,在模型映射方法基础上提出一种XML文档映射关系数据库的新方法。通过给XML文档树做标志,将映射算法转换后的数据放到两张预先定义结构的表进行存储。给出了逻辑数据模型、详细设计、映射算法和实验。实验结果表明,该方法能有效地保持XML文档的结构,能够对存储的数据进行语义检索,适用于任何树型数据结构。     

Active XML文档有效性检验

文档有效性检验是XML领域的一个基本问题.Active XML(AXML)文档在XML文档中引入Web服务,传统用于解决XML文档有效性的检验方法并不适用于AXML文档,为文档有效性检验提出了新的挑战.研究了AXML文档有效性检验问题,在原始树自动机的基础上,定义了AXML模式树自动机-ASTA机,该树自动机能够有效地描述满足AXML模式约束的文档集合.基于ASTA机,提出了一种多项式时间的AXML文档有效性检验算法.实验数据表明,基于提出的算法能够有效的完成对AXML文档的有效性检验.     

基于XML和关系数据库的树形结构的研究

本文介绍了一种树型结构的存储、显示和维护方法。以二叉链表的数据结构将树的信息存储在数据库中，服务器端将数据库中树的信息转化成XML，客户端将其加载到浏览器的（DOM）实例中，并采用深度优先搜索算法对该实例中的结点进行递归遍历，生成浏览器端树的HTML代码，它是一个与上述XML文档逻辑相同的树型结构。同时在各结点上设置JS事件，可以对该树进行维护，生成针对结点维护的XML，服务器解析该XML并生成一系列SQL提交到数据库中。     

BSC：一种高效的动态XML树编码方案

确定一篇XML文档中任意两个节点之间是否存在某种结构关系,是XML查询处理过程的一个重要组成部分.XML树编码方案为每个节点分配唯一编号,仅通过比较节点编号而不必访问原XML文档,就可以快速有效地确定节点间的结构关系.随着XML应用不断普及,能否高效地支持更新操作,已成为XML树编码方案研究的一个重要课题.本文基于二进制小数的特性,提出了一种新的XML树编码方案-BSC,它可以完全高效地支持XML更新操作而不需要重新编码.实验结果证明,与已有的动态编码方案相比,BSC编码无论在静态编码方面还是在动态更新方面都具有很好的性能.     

基于Java的DOM解析技术

DOM是一个针对XML数据的应用编程接口，它本质上是一个XML解析器，它将一个XML文档看作一棵节点树，对节点可以进行各种遍历、查询、修改操作：本文主要介绍使用基于Java的解析器来实现对XML文档的解析技术.     

基于形式语言理论的Active XML重写算法

主动XML（AXML）是指一部分数据直接给出,另一部分数据以Web Services调用方式隐含给出XML文档。研究AXML重写问题,给出AXML重写系统的形式化定义,提出一个基于树自动机理论的AXML文档重写算法,并证明该算法的正确性及有效性。实验数据表明,基于树自动机的AXML文档交换方法具有良好的执行效率。     

基于BFS树的XML文档图结构相似性计算

可扩展链接语言将XML文档从树状结构扩展到图状结构,其结构相似性比较对文档查询、聚类意义重大.现存的比较XML树状结构相似性以及比较图结构相似性的方法忽视了文档结构特点,比较的结果与实际存在较大差异.基于BFS树的XML文档图结构相似性计算方法运用广度优先搜索算法找到最小代码树,重新定义了编辑距离的概念.比较结果表明,该方法更符合实际文档相似程度,因此在比较XML文档图结构相似性上有很大的可行性.     

基于EXN-Tree编码的XML结构连接算法研究

提出了EXN-Tree的概念，将XML文档树的节点映射到EXN-Tree，依据EXN-Tree的节点编码生成XML文档树节点数据结构。基于此新型的节点编码结构，就无序无索引节点集和有序有索引节点集两种情况下的XML结构连接算法展开研究，提出了一系列的结构连接算法，解决了无序无索引节点集和有序有索引节点集两种情况下的XML结构连接。分析表明该算法的I/O复杂性优于已有算法，具有良好的性能。     

一种基于结构索引的XML模式匹配方法

XML文档采用了树型的数据模型,对其查询通常是用带有选择谓词的模式树在XML数据中进行匹配.因此,找出XML文档中所有符合模式树结构的元素集,是XML查询处理的核心操作.本文提出了结构索引JoinGuide,并在此基础上提出了一种新的XML模式匹配方法.它使用JoinGuide来对模式树进行预匹配,这样在XML文档上查询时可以利用索引上的匹配结果来忽略部分连接谓词和不必要的候选XML元素序列.本文还提出了三种具体算法来利用索引匹配结果进行进一步的查询.实验结果表明本文中的模式树匹配方法优于以往的匹配方法,并且索引所需的空间很小.     

基于扩展字节进位的动态XML树编码方案

为提高可扩展标记语言(XML)文档树编码的效率、支持XML数据动态更新,提出一种基于扩展字节进位的动态XML树编码方案(EBCL)。结合前缀编码和加法运算的思想,采用分段与分节的方式组成编码,给出静态前缀编码与动态前缀编码的算法流程。对编码大小与静态动态性能进行测试,实验结果表明,EBCL编码性能较优,能高效地支持XML文档的动态更新。     

Computational complexity of the problem of tree generation under fine-grained access control policies

We consider the problem of deciding whether a fine-grained access control policy for tree updates allows a particular document to be constructed. This problem arises from a number of natural questions related to document security, authenticity, and verifiability. Fine-grained access control is the problem of specifying the set of operations that may be performed on a complex structure. For tree-structured databases and documents, particularly XML, a rule-based approach is most common. In this model, access control policies consist of rules that select the allowed or disallowed targets of queries or updates based on their hierarchical relationships to other nodes.We show that, for a typical form of rule-based fine-grained access control policies based on a simple fragment of XPath, this problem is undecidable. We also prove lower bounds on the complexity of various restrictions of this problem, and demonstrate deterministic and nondeterministic polynomial-time algorithms for two restrictions in particular.These results show that, for sufficiently complex access control languages, certain forms of analysis are very difficult or even impossible, limiting the ability to verify documents, audit existing policies, and evaluate new policies. Thus rule-based access control policies based on XPath are, in some sense, too powerful, demonstrating the need for a model of access control of tree updates that bridges the gap between expressive and analyzable policies.     

DTD约束下的XML树模式查询最小化

目前大部分XML查询语言都使用树模式来匹配待查询的XML文档树以得到所需要的、与模式树相吻合的查询结果,此效率在很大程度上取决于XML模式树的大小,那么尽可能快速地查找并删除查询模式树中的冗余节点就变得十分重要。重点讨论DTD约束下树模式的最小化问题,将DTD兄弟约束SC拓展成扩展兄弟约束ESC,使其能够表达DTD约束中的祖先-后代关系;并指出只包含{ESC,/,//,[],*}的查询树模式的最小化问题的复杂度是指数级的,且当模式树是分支受限的时候,其最小化问题的复杂度是多项式时间的;最后给出了一个多项式时间的受限分支的模式树最小化算法。     

概率XML文件树结点概率的查询算法

概率XML文件是概率数据的网络数据交换和表示标准,元素取值及其概率的查询与计算是概率XML文件的重要研究内容.概率XML文件树是一种有效的概率XML文件的数据模型,定义了概率XML文件树的基本路径和扩展路径,提出了根据可能世界原理将概率XML文件树分解为普通子XML树的集合的算法,根据路径分析原理将概率XML文件树分解为子概率XML树的集合的算法和相应的查询与计算结点及结点集合概率的算法,并通过实验进行了比较分析.实验结果表明:这两种方法是有效的;与前一种方法比较,后一种方法适合较大的概率XML文件树、结点及结点集合的概率的查询,计算过程较简单.     

一种并行XML数据库分片策略

主要研究XML文档的并行数据分片策略,以便能够并行处理XML查询.为了描述XML数据分片,提出了媒介节点的概念.一组媒介节点的集合可以将一棵XML数据树分割成一棵根树和一组子树的集合:根树将在所有站点中复制;而子树集合则可以根据用户查询的工作负载被均匀地分片到各个站点中.对于同一棵XML数据树,会有很多种媒介节点的集合;而不同的媒介节点集合会产生不同的数据分片结果.然后,依据各个数据分片中的用户查询工作量是否均衡,来衡量一个分片的好坏.选择一组最佳的媒介节点集合是一个NP-hard问题.为了解决此问题,设计了一组启发式优化规则.基于这一思想,提出并实现了一种基于媒介节点的XML数据分片算法WIN(workload-aware intermediary nodes data placement strategy).大量实验结果证明:WIN算法的性能要优于以往的并行XML数据分片策略.     

基于局部路径加锁的XML并发控制协议

传统XML数据库并发控制协议大多采用基于XML文档树的路径加锁方式,并发度不高。针对该问题,提出一种基于局部路径加锁模型的XML数据库并发控制协议。该协议基于XML的节点编码,利用查询函数对目标节点的祖先后裔加锁情况进行快速判断,并根据操作类型对目标节点或者其父节点进行加锁,从而减少对锁的频繁请求,提高事务并发度以及实现大规模XML数据的有效管理。     

利用关系表构建XML文档解析的树模型

在对XML文档的数据解析和查询操作研究中,发现树能较好地反映XML文档的层次结构,但其查询效率较低,而关系表是一种适合存储大量数据且有较好查询效率与操作功能的数据结构。给出了一个把树和关系表相结合构建一种存储XML文档的数据模型;在这个模型的解析过程中,采用回调事件式的分段解析方法以减少解析时间和存储空间。这样既能较好保存XML文档的结构特点,又能提高其查询的效率和操作的便利性。通过对大数据量XML文档的解析和操作实验,实验结果证明这种数据模型在处理大型XML文档中具有明显优势。     

保持数据约束的关系数据库至XML文档的转换

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

Tree pattern query minimization

Tree patterns form a natural basis to query tree-structured data such as XML and LDAP. To improve the efficiency of tree pattern matching, it is essential to quickly identify and eliminate redundant nodes in the pattern. In this paper, we study tree pattern minimization both in the absence and in the presence of integrity constraints (ICs) on the underlying tree-structured database. In the absence of ICs, we develop a polynomial-time query minimization algorithm called CIM, whose efficiency stems from two key properties: (i) a node cannot be redundant unless its children are; and (ii) the order of elimination of redundant nodes is immaterial. When ICs are considered for minimization, we develop a technique for query minimization based on three fundamental operations: augmentation (an adaptation of the well-known chase procedure), minimization (based on homomorphism techniques), and reduction. We show the surprising result that the algorithm, referred to as ACIM, obtained by first augmenting the tree pattern using ICs, and then applying CIM, always finds the unique minimal equivalent query. While ACIM is polynomial time, it can be expensive in practice because of its inherent non-locality. We then present a fast algorithm, CDM, that identifies and eliminates local redundancies due to ICs, based on propagating "information labels" up the tree pattern. CDM can be applied prior to ACIM for improving the minimization efficiency. We complement our analytical results with an experimental study that shows the effectiveness of our tree pattern minimization techniques.