XML文档结构索引的更新维护

XML作为一种数据表示方式,越来越为人们所接受.最近,基于XML/半结构化数据的索引的查询引起了人们的广泛关注.有人提出来用结构索引来支持基于XML/半结构化数据的查询.由于XML/半结构化数据的结构不严格、不规则,结构索引会随着数据的增加或删除而变化,维护结构索引就成了首要问题.在本文中,我们研究了在XML文档集合上增加多个文档和删除一个文档时结构索引的更新,提出了在这两种情况下的索引维护算法,这两种算法比现在已知的其他算法的性能要更优秀.     

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

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

基于复杂模式索引的XML查询优化*

分析了XML模式与XML文档之间的关系以及XML查询的特点,提出了一种基于复杂模式索引的XML查询优化方法.该方法对XML模式中的节点建立索引,查询时考虑XML模式中带有环的情况.首先对查询树进行去除重复元素的预处理,并将查询树分解成主路径和分支路径;然后利用索引查找潜在目标节点的XML模式编号;最后在XML文档中对对应节点进行筛选,找到目标节点.该方法可以减少连接操作的次数,提高查询操作的效率,能处理较复杂的XML模式.     

基于Schema的XML索引方法研究

针对XML文档路径查询中无效扫描量大、分支路径连接操作复杂等问题,提出一种基于Schema的XML索引方法。通过Schema与查询路径匹配,确定需要扫描的XML文档。利用编码方法减少结点连接次数。实验结果表明,该方法较已有索引方法有更高的查询效率,具有较好的实用性及可扩展性。     

一种新的基于Dewey编码的XML路径索引

建立高效的索引来快速定位满足要求的节点是提高XML数据查询效率的一个必要手段.文中以降低复杂度和提高查询效率为目标,以基于路径的XML索引原理为基础,提出了一种新型的基于Dewey编码的索引结构RTL-Index.RTL-Index通过对文档节点编码来表示结构信息,利用前缀路径匹配操作完成结构查询,支持含通配符" 和后代轴"//"的查询以及兄弟节点无序的模式树的查询.仿真实验结果表明RTL-Index索引具有较低的时间和空间复杂度,解决了XML文档分支路径查找问题,是一种较为有效的XML索引结构.     

一种基于DTD的XML索引方法

路径查询是XML查询的一个主要特征,现已提出了多种XML索引方法．DTD的结构信息对于XML索引的建立及查询效率的提高很重要,但现有的大部分索引方法没有利用DTD这一有效资源,提出一种利用DTD的XML索引方法——DBXI(DTD-based XML indexing),该方法采用了新的编码方法,可使路径查询具备如下特征：对于由N个元素／属性组成的具有1个谓词约束的路径表达式,DBXI处理每个XML文档仅需0次或1次元素／属性结点集的结构连接操作;对于在XML文档中不存在匹配结构的路径查询,DBXI能够在比现有的XML索引方法较短的时间内给出无查询结果的判断．实验表明,与Lore,SphinX和XISS等索引方法相比,DBXI能够缩短路径查询的响应时间．     

基于素数编码Schema的XML索引结构的研究

针对XML文档查询,提出了一种基于素数编码Schema的XML索引技术.该索引是对XML模式采用素数编码,对XML文档采用Li-Moon编码,这样在建立XML文档的节点索引时,也可对该节点的路径信息进行记录.在节点类索引的基础上,记录路径信息,既可以很好地支持正则路径表达式,同时又避免了节点类索引在处理长路径表达式时可能造成高昂的连接操作代价.实验结果表明,该索引的性能总体上要好于传统的节点类索引.     

XML数据路径索引技术研究与分析

XML路径索引技术是XML数据管理的关键技术之一,根据构建机制的不同,XML路径索引可以分为基于XML文档内容建立的和基于XML文档模式建立的两类。随着XML在各领域中的应用,发展相对成熟的XML数据管理技术将是相关领域中数据管理的很好借鉴。对两类XML路径索引机制分别进行了研究和分析,并对XML路径索引技术在GML文档索引技术研究中的应用作出了探讨。     

XML文档的相似测度和结构索引研究

提出了一个可用于定量度量XML文档间差异的方法(称为XED距离)。利用结点间的模拟关系，一个XML文档可以表示为一棵精简的、带权重的结构索引树，两个XML文档间的相似度可以通过计算它们的索引树间的编辑距离来测定，利用索引树可以大大提高判定两个XML文档结构相似度的效率，XED距离测度可用于XML文档的结构搜索、XML文档聚类、XML文档结构抽取、XML文档的变换检测以及XML视图的增量计算和维护等。     

基于F&B索引的XML查询处理算法

XML已成为信息交换和表示的标准.对XML数据的查询将返回满足特定约束的XML节点子集.对于大文件的XML数据的查询处理通常分为两步:1.为该XML数据建立一个索引;2.在索引上完成查询处理无需访问源文档.XML索引为查询处理提供了高效的帮助,其中F&B索引是已知的处理分枝查询最小的索引,但快速创建F&B索引和利用F&B索引完成查询处理的算法却很少有人研究.提出了一种素数序列标记法,这种标记法不仅有助于快速地建立F&B索引,更可以高效地完成F&B索引上的查询处理.此外,还给出了F&B索引上的区间标记法与CCPI的创建过程,这两种编码创建过程无需在建立F&B索引后二次创建,仅需与F&B索引创建过程一起对文档使用SAX解析器分析一次即可得到.这样,可以在F&B索引的区间标记法上使用TwigStack算法执行查询处理,在F&B索引的CCPI标记法上使用关联路径连接算法执行查询处理.还给出了基于素数序列标记法的查询处理算法,即素数整除匹配算法,该算法可以高效地判定某节点是否有某分枝子结构.实验表明基于素数序列标记法的F&B索引创建方法比SAM算法快,在多个数据集F&B索引上素数整除匹配算法优于关联路径连接算法和Twi...     

DOM tree browsing of a very large XML document: Design and implementation

Browsing the DOM tree of an XML document is an act of following the links among the nodes of the DOM tree to find some desired nodes without any knowledge for search. When the structure of the XML document is not known to a user, browsing is the basic operation performed for referring the contents of the XML document. If the size of the XML document is very large, however, using a general-purpose XML parser for browsing the DOM tree of the XML document to access arbitrary node may suffer from the lack of memory space for constructing the large DOM tree. To alleviate this problem, we suggest a method to browse the DOM tree of a very large XML document by splitting the XML document into n small XML documents and generating sequentially the DOM tree of each of those small n XML documents. For later reference, the information of some nodes accessed from the DOM tree already generated has been also kept using the concept of their virtual nodes. With our suggested approach, the memory space necessary for browsing the DOM tree of a very large XML document is reduced such that it can be managed by a personal computer.     

Native XML数据库的文档编码机制研究

Native XML数据库快速查询的实现,可以采用基于XML文档编码的结构连接算法。而结构连接算法的实现需要对XML文档进行编码,以便于快速判断XML文档树结点之间的祖先后裔关系。在对现有编码机制进行综述的前提下,提出一种新的XML文档编码机制——前缀整除编码（PDIV）机制。该机制编码形式简单,只需要一个正整数即可充分表示结点在XML文档树中的位置信息;可以实现祖先后裔关系的快速查询;支持XML文档的更新操作;编码长度较短,编码长度约为o（ln（n））。     

XML文档在关系数据库中的存储方法

XML是网络中跨平台数据发布与交换的标准格式,它在数据库领域有着广阔的应用空间,然而XML文档的树型结构与关系数据库的二维表结构之间存在着巨大的差异,因此在关系数据库中存储XML文档需要进行一些特殊处理。本文分析了XML文件在数据库领域中的存储与管理方法,并重点就Oracle9i中XML相关技术在现代远程教育中的应用进行了讨论,针对以数据为中心和以文档为中心两类文档资料的存储给出了可行的存储方案。     

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

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

一种基于改进粒子群优化的XML结构聚类方法

在对XML文档进行数据挖掘时,很多结构语义信息没有被充分考虑进来.为了更好地进行大规模文档集的挖掘,本文首先给出一个新的基于语义和支持度的XML结构模型对每个文档建模.然后根据该模型,提出基于改进粒子群优化的结构聚类方法.实验中,为了增加算法的实用性,将粒子群优化的思想与传统的K均值算法相结合,其优点是能够跳出局部极值.实验结果表明提出的方法在聚类准确性和收敛程度方面都优于传统基于划分的聚类算法.     

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

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

一种基于RDBMS的XML数据的存储方法

XML作为一种数据交换的标准在互联网上推出,使得XML数据和数据库的相互交换成为必要:一是因为WEB中大量的多样化数据需要进行有效的存储和管理;二是因为在现有的数据库中存储有大量的数据并且需要将这些数据转换为XML发布到WEB中。论文提出了一个基于关系数据库的数据转换框架,基于数据的完整性讨论XML数据存储策略。建立一个XML通用数据模型,把文档树分解成多个节点,根据一定的映射规则存储到关系表中,从而不用考虑文档的模式信息(DTD、XMLSchema)。最后通过一个具体的文档实例来说明这种策略的有效性。     

一种基于结构特征的XML数据查询方法

针对XML数据特有的树型结构模式,提出了一种将树型结构的XML数据和查询语句转化为特定格式的字符串,基于串匹配原理对结构复杂的XML数据进行查询的方法,避免了传统的基于路径的查询方式所必需的路径之间的连接（join）操作,从而提高查询效率。利用本文提出的编码方式,可以建立关于XML数据结构和数据内容舍为一体的索引。实验显示,本文使用的针对XML数据查询的方法比传统的基于连接操作的数据查询方式高效,且本方法具有良好的扩展性。     

Efficient memory representation of XML document trees

Implementations that load XML documents and give access to them via, e.g., the DOM, suffer from huge memory demands: the space needed to load an XML document is usually many times larger than the size of the document. A considerable amount of memory is needed to store the tree structure of the XML document. In this paper, a technique is presented that allows to represent the tree structure of an XML document in an efficient way. The representation exploits the high regularity in XML documents by compressing their tree structure; the latter means to detect and remove repetitions of tree patterns. Formally, context-free tree grammars that generate only a single tree are used for tree compression. The functionality of basic tree operations, like traversal along edges, is preserved under this compressed representation. This allows to directly execute queries (and in particular, bulk operations) without prior decompression. The complexity of certain computational problems like validation against XML types or testing equality is investigated for compressed input trees.