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

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

基于关系代数的XML数据查询

XML渐已成为Web上数据表示和交换的通用语言。为了有效地利用大量的XML文档，需要研究XML数据查询技术。提出了基于关系代数的XML数据查询方法。XML子句可以用关系代数表达式表示，并通过关系代数操作得到查询结果。该方法为查询XML数据提供了一种简洁和有效的手段。     

XQAD:一种XML查询的算法

目前已经提出的XML查询的方法大都是直接进行实例一级的查询,如XML文档树遍历及嵌套连接等。这些方法忽视了对XML格式信息的利用,当XML文档较大时,性能就会有明显下降。论文给出了一种直接利用DTD的格式信息对XML进行查询的算法XQAD。根据DTD和路径表达式的特点来减少对实例的访问次数,从而提高性能。XQAD还支持多谓词查询,包括结构谓词和值谓词。最后,用实验的方法同其它算法作比较,并对试验结果进行了分析。     

基于正则路径表达式的XML查询优化技术研究

支持正则路径表达式的查询技术，被认为是半结构化数据模式下的XML查询研究领域中一种颇具有研究价值的XMI。查询计算方法。本文对基于正则路径表达式的XML查询计算方法及其特点进行了分析，在此基础上详尽地介绍了目前所提出的各种查询优化技术，最后讨论了XML查询优化技术研究中存在的问题以及今后的研究方向。     

一种基于完整性约束的路径表达式的查询优化策略

利用路径表达式导航 XML 查询是 XML 查询语言的共同特点。目前对 XML 路径表达式的计算有两种方法:一种是基于树遍历的方法,一种是路径连接方法。在路径连接方法中路径表达式的计算效率很大程度上依赖于路径表达式的长度。在对 XML 模式反映的完整性约束研究的基础上,本文提出了排他性包含约束的概念;给出了利用排他性包含约束缩短路径表达式的策略和算法,从而降低了路径连接的代价。通过分析比较,这种路径缩短策略是有效可行的。     

基于三叉链表的XML文档存储模型

XML文档进行高效编码、索引、查询的前提是数据的存储模型.针对XML的典型树状结构,文章提出一种基于三叉链表的XML文档存储模型.在此基础上,讨论了XML数据的查询、更新、插入、删除、结点关系判断等运算的实现,分析了相关算法的效率.     

处理XML文档查询的高效结构连接方法

结构索引和倒排表在处理XML文档查询时，有不足之处。该文提出了一种结合结构索引、倒排表的策略、连接路径表达式的查询算法，有效地降低了实际执行的代价，提高了查询速度。     

以XML文档发布关系数据

本文对以XML文档发布关系数据的新技术进行了综述，主要分析了两种发布关系数据到XML文档的语言描述及其实现技术，以及它们的优缺点，一种是利用并扩展SQL的功能来描述这种转换，嵌套的SQL表达式被利用来描述嵌套，扩展的SQL标量及聚集函数被利用来描述XML元素构造，实现将关系数据转换为XML文档，另一种是利用RXL（Relational to XML Transformation Language)语言来定义一个关系数据库的XML视图，该XML视图是虚的，其它应用可再利用XML查询语言XML－QL在虚拟的视图上构造一个查询，抽取XML视图中的数据片断并对抽取的部分进行物化，实现将关系数据转换为XML文档。     

XML结构完整性约束下的路径表达式的最小化

引入了一个XML结构完整性约束体系.这个体系描述了XML文档中节点或路径之间的5种结构关系,包括路径蕴涵、路径同现、路径互斥、必需性包含和排他性包含.给出了这些结构完整性约束的语法和语义定义,并研究了它们在XML查询优化中的作用.基于子路径的概念,提出了有结构完整性约束的路径表达式的最小化算法.该算法以路径蕴涵闭包为工具,不仅可以删除路径表达式的冗余,还可以识别无效路径表达式.实验结果表明了该算法的正确性和有效性.     

一种XML数据库上谓词“Contain”的实现方法

路径表达式查询是XML数据查询处理的核心研究问题之一,研究者开展了大量的研究工作.但这些研究更多关注XML数据上路径表达式的匹配,忽略了谓词"包含".研究XML查询处理中谓词"包含"的查询处理方法.采用了两种方法,第一种是采用跳跃表的方法,在XML分枝模式匹配时动态地对结点数据进行读取和关键字匹配.第二种是为XML文档中的词语建立倒排索引,来实现关键字的匹配.并从分枝模式路径长度、查询关键的数量和"包含"谓词判断结点的类型,对两种方法进行了分析和比较.     

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

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

Efficiently Querying Large XML Data Repositories: A Survey

Extensible markup language (XML) is emerging as a de facto standard for information exchange among various applications on the World Wide Web. There has been a growing need for developing high-performance techniques to query large XML data repositories efficiently. One important problem in XML query processing is twig pattern matching, that is, finding in an XML data tree D all matches that satisfy a specified twig (or path) query pattern Q. In this survey, we review, classify, and compare major techniques for twig pattern matching. Specifically, we consider two classes of major XML query processing techniques: the relational approach and the native approach. The relational approach directly utilizes existing relational database systems to store and query XML data, which enables the use of all important techniques that have been developed for relational databases, whereas in the native approach, specialized storage and query processing systems tailored for XML data are developed from scratch to further improve XML query performance. As implied by existing work, XML data querying and management are developing in the direction of integrating the relational approach with the native approach, which could result in higher query processing performance and also significantly reduce system reengineering costs.     

Indexing and querying XML using extended Dewey labeling scheme

Finding all the occurrences of a tree pattern in an XML database is a core operation for efficient evaluation of XML queries. The Dewey labeling scheme is commonly used to label an XML document to facilitate XML query processing by recording information on the path of an element. In order to improve the efficiency of XML tree pattern matching, we introduce a novel labeling scheme, called extended Dewey, which effectively extends the existing Dewey labeling scheme to combine the types and identifiers of elements in a label, and to avoid the scan of labels for internal query nodes to accelerate query processing (in I/O cost). Based on extended Dewey, we propose a series of holistic XML tree pattern matching algorithms. We first present TJFast to answer an XML twig pattern query. To efficiently answer a generalized XML tree pattern, we then propose GTJFast, an optimization that exploits the non-output nodes. In addition, we propose TJFastTL and GTJFastTL based on the tag + level data partition scheme to further reduce I/O costs by level pruning. Finally, we report our comprehensive experimental results to show that our set of XML tree pattern matching algorithms are superior to existing approaches in terms of the number of elements scanned, the size of intermediate results and query performance.     

GA-Diff:一种快速XML文档变化检测算法

XML文档的变化检测可以广泛应用于构建XML数据仓库中的数据存储、文档模式提取以及增量查询等方面。随着被检测的数据规模的增加,对检测算法的效率也提出了更高的要求。利用遗传算法(GA),论文提出了一种新的XML文档的变化检测方法GA-Diff,针对XML文档树给出了树编辑距离的定义、实现算法并验证了该算法的效率。     

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

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

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

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

扩展哈弗曼前缀编码实现XML数据与关系数据转换

为从企业生产线上XML半结构化数据中抽取富有意义数据,分析了XML半结构化数据和关系数据库中结构化数据特点,以及XML半结构化数据在关系数据库中的存储方法。针对实际应用,提出采用扩展哈弗曼前缀编码方法,对XML文档树进行唯一编码,实现XML文档与关系数据库映射,同时给出最长前缀匹配策略,支持数据查询,以提高查询效率。     

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

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

CSBTT:一种基于二叉树遍历的XML文档编码模式

XML文档数据编码模式是XML文档查询处理的基础, 好的文档编码模式有利于提高文档的查询效率. 为了解决XML数据查询效率低、支持动态更新等问题. 本文在二叉树遍历的编码基础上, 引入二叉树的三叉链表存储结构对XML文档结点进行编码. 该编码利用自然数作为编码序号, 因此编码长度较短; 引入结点双亲指针, 方便结点之间结构关系的判定, 结点采用三叉树链式存储, 方便文档的更新操作.     

使用DTD优化XML数据流上的XPath查询

如何在XML数据流上高效地执行XPath查询,是XML数据流管理的关键问题。DTD结构信息对提高XML查询效率有很大帮助,已有的大部分算法没有利用这一资源。提出了一种使用DTD进行XML数据流查询处理的方法,具有以下特征:利用树自动机表示XPath;通过XPath树自动机与DTD树匹配,预先标识不匹配查询结构的DTD节点;给出一种利用DTD的XML流索引方法DBXSI;执行查询时,根据流索引信息直接跳过某些与查询不匹配的节点及子树。实验结果表明:该方法可有效支持Xpath查询,效率优于传统算法。