采用了剪枝优化的子类型关系判定算法

静态类型化XML处理语言为处理XML数据提供了新的途径,但现有的此类语言大多数效率较低.研究此类语言的一个重要问题——子类型关系的判定,并使用剪枝优化策略对XDuce的子类型关系判定算法进行优化.实验数据显示,优化后算法的执行效率平均提高20%.该策略具有普遍性,对所有使用类似算法的静态类型化XML处理语言都有效.     

基于树自动机的XQuery子类型关系和值-域关系

XQuery是W3C提出的一种对XML结构文档或数据进行查询的语言规范,该语言规范对其类型系统仅做了功能性的描述,而没有涉及在编译实现中遇到的两个类型之间子类型关系和值-域关系的判断方法.本文描述和分析了这两种关系,基于树自动机,给出了XQuery类型系统中子类型关系和值-域关系的判断算法.     

图结构XML文档上子图查询的高效处理算法

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.     

基于规则的数据类型重构技术研究

为恢复变量的数据类型信息并提高反编译的质量,提出一种基于规则的数据类型重构方法.采用静态和动态相结合的分析方式,将可执行代码转化为中间语言,在优化中间语言的基础上为每条指令制定约束规则,并给出相应的求解算法,从而推导出变量的数据类型信息.实验结果表明,该方法能对简单数据变量类型和复杂数据变量类型进行恢复,具有较高的准确性.     

基于XML Schema抽象模型的XML模式验证方法

XML模式验证作为处理XML数据的前提和保证有着重要的地位,XML Schema作为XML的定义语言,其本身并不能保证XML数据的有效性.利用XML Schema抽象模型,定义了XML Schema中每个复杂类型的模式信息,并用非终节点序对集描述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相似性数据并行检测效率,利用波函数对粒子群优化算法进行优化。仿真实验表明,与其他XML数据清洗算法相比,该方法的白适应学习能力强、人工参与程度低、计算量小,时间性能有94％左右的提升。     

基于任务抢占与数据分区的XML多核查询优化

在XML查询处理中,目前普遍的算法仍然使用传统的串行处理模式,无法充分利用多核资源的优势.针对此问题,设计了一种基于任务抢占与数据分区的XML多核优化策略(Imp-NBPP),它对XML文档进行数据分区,以达到负载平衡,让各个线程独立处理分区内的数据,减少了线程之间同步与通信带来的开销.同时还探讨了任务抢占在多核查询中的应用.实验表明,对于不同大小的XML文档,基于节点数(NBP),基于文档大小(SBP)与本文所提策略,这三种策略与单核查询相比均能有效的节约查询时间;使用Imp-NBPP策略时,在节约查询时间和负载平衡方面均优于NBP、SBP策略.     

用C++中的子类型实现软件再用之探讨

本文讨论了 Ｃ＋＋中通过公有继承实现的子类型关系。 阐述了通过对类型子类型化提高了程序的灵活性和软件的重用率,并结合例子说明了子类型化在程序设计中的应用。     

Efficient processing of XPath queries using indexes

A number of indexing techniques have been proposed in recent times for optimizing the queries on XML and other semi-structured data models. Most of the semi-structured models use tree-like structures and query languages (XPath, XQuery, etc.) which make use of regular path expressions to optimize the query processing. In this paper, we propose two algorithms called Entry-point algorithm (EPA) and Two-point Entry algorithms that exploit different types of indices to efficiently process XPath queries. We discuss and compare two approaches namely, Root-first and Bottom-first in implementing the EPA. We present the experimental results of the algorithms using XML benchmark queries and data and compare the results with that of traditional methods of query processing with and without the use of indexes, and ToXin indexing approach. Our algorithms show improved performance results than the traditional methods and Toxin indexing approach.     

基于XPath的XML查询优化

随着XML作为Internet上数据表示和交换的标准,如何高效地进行XML数据的查询己经变得越来越重要,许多XML查询语言也随之出现。这些查询语言虽然种类繁多,但都有个共同特征:使用基于XPath数据模型下规则路径表示来查询XML数据。研究表明,当前的关系数据库技术在处理规则路径表示的查询时通常效率不高。文章在介绍了传统的基于遍历树的方法的基础上重点讨论了基于路径分解的查询处理算法,并对选择连接顺序算法提出了基于动态规划思想的改进。     

一种适用连续不确定XML数据的索引

针对连续不确定XML数据概率阈值范围查询,提出一种新的CUXI索引树。该索引树的构建方法是借鉴U树对空间数据自顶向下递归构建索引树的思想,将连续不确定XML文档中具有相同父亲的叶子节点构建二维数据矩形,在聚类的基础上来构建相应的CUXI索引树,其中叶子节点存储连续不确定数据辅助信息。为了提高查询效率,对连续不确定数据制定了过滤策略,通过遍历索引树过滤掉不满足查询范围的子树。理论和实验结果表明,此索引技术可提高查询处理的性能。     

以目标节点为导向的XML路径查询处理

XML查询语言将复杂路径表达式作为核心内容.为了加速路径表达式处理,基于路径分解和结构连接操作的处理策略需要更深入的研究.以目标节点为导向的XML路径查询处理框架被提了出来.该方法利用了扩展基本操作来减少连接操作的数目.在路径分解和查询计划选择的过程中,利用查询树中的目标节点来避免中间结果的传递.除了分解规则和策略以外,提出了一组扩展的基本操作和实现算法.初步的实验结果显示,该方法具有良好的性能.它为路径查询处理提供了更多的选择.     

基于XPath的XML查询优化

随着XML作为Internet上数据表示和交换的标准,如何高效地进行XML数据的查询己经变得越来越重要,许多XML查询语言也随之出现。这些查询语言虽然种类繁多,但都有个共同特征：使用基于XPath数据模型下规则路径表示来查询XML数据。研究表明,当前的关系数据库技术在处理规则路径表示的查询时通常效率不高。 文章在介绍了传统的基于遍历树的方法的基础上重点讨论了基于路径分解的查询处理算法,并对选择连接顺序算法提出了基于动态规划思想的改进,     

Boolean operations and inclusion test for attribute–element constraints

The history of schema languages for XML is (roughly) an increase of expressiveness. While early schema languages mainly focused on the element structure, Clark first paid an equal attention to attributes by allowing both element and attribute constraints in a single constraint expression (we call his mechanism “attribute–element constraints”). In this paper, we investigate intersection and difference operations and inclusion test for attribute–element constraints, in view of their importance in static typechecking for XML processing programs. The contributions here are (1) proofs of closure under intersection and difference as well as decidability of inclusion test and (2) algorithm formulations incorporating a “divide-and-conquer” strategy for avoiding an exponential blow-up for typical inputs.     

Foundations of Fast Communication via XML

Communication with XML often involves pre-agreed document types. In this paper, we propose an offline parser generation approach to enhance online processing performance for documents conforming to a given DTD. Our examination of DTDs and the languages they define demonstrates the existence of ambiguities. We present an algorithm that maps DTDs to deterministic context-free grammars defining the same languages. We prove the grammars to be LL(1) and LALR(1), making them suitable for standard parser generators. Our experiments show the superior performance of generated optimized parsers. Our results generalize from DTDs to XML schema specifications with certain restrictions, most notably the absence of namespaces, which exceed the scope of context-free grammars.     

基于XML的可继承BIRCH研究

针对BIRCH算法过分依赖内存且无法高效处理新增数据的问题,提出一种BIRCH算法的可继承性处理模型。该模型利用XML技术存储聚类特征树,并通过解析XML文档来还原聚类特征树,增强了BIRCH算法的灵活性,解决了BIRCH算法中处理新增数据的效率问题。实验结果表明,该模型是有效的。     

一种基于层次栈的XML数据小枝查询算法研究

当前针对小枝模式的XML查询是XML文档查询的研究热点。文章在分析XML数据小枝查询处理常用算法的基础上,提出了一种高灵活性的、易确定结点对之间结构关系的EDiezt-P编码,并基于EDiezt-P编码和层次栈结构提出了一种自底向上的小枝查询算法。实验表明,该算法在一定程度上减少了查询处理时间,提高了查询效率。