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

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

一种可扩展的XPath查询最小化算法框架

XPath是XML的基本查询语言,XPath查询最小化对于提高XML数据库的查询性能具有重要意义.但是,由于XPath查询最小化是一个coNP完备问题,大部分已有的算法局限于处理简单的XPath片段.本文从一个新的角度入手,综合考虑完备性和高效性,提出了一个新的查询最小化框架,与已有算法"面向结点",即逐个删除冗余结点的解决思路不同,本文提出"面向树模式"的方式,即通过计算树模式的自同态映射,寻找目标结点集最小的自同态映射,进而求解最小等价查询树的方法.该方法具有较高的效率,而且在--Z..情况下是完备的,尤其是可以进一步扩展到更复杂的XPath片段.本文以此框架为基础,给出一个可以计算复杂查询模式的算法.     

DTD约束下的树模式查询的一致性判断

树模式查询被广泛地应用XML数据查询中。树模式查询的一致性判断可以避免不必要的计算,节省查询时间,从而提高查询效率。给出了查询一致性的定义,基于子路径的概念,提出文档类型定义(DTD)约束下的树模式查询的一致性判断算法,并对算法的时间复杂度进行了分析。通过分析比较,该算法是有效的。     

基于模型检查的XML树模式优化动作生成

针对XML数据查询的核心操作-树模式查询,提出基于XML Schema约束来优化树模式查询的方法。该方法提出了统一的优化规则描述语言ORS的语法与语义。ORS描述的优化规则中包括对树模式条件的描述、对XML Schema条件的描述以及在满足前两个条件下应该输出的动作。根据ORS语言描述的优化规则以及待处理的树模式,系统会自动输出该树模式的优化动作。该方法一方面简化了树模式优化的过程,另一方面把模型检查技术运用到XML树模式查询优化上,利用时态逻辑公式描述优化规则中的约束条件,利用模型检查的方法提取XML Schema的约束,对ORS语法和语义的严格定义确保了生成的优化动作的正确性。     

一种查询XML异构数据源的新方法

由于异构数据源存在结构差异和结构不兼容等问题,在其上进行查询是一个挑战.本文根据XML树的特点,对其进行了外延,设计了一种新的XML树的查询方法.通过样式图获得XML树的结点间的语义关系,查询条件可以表示为XML样式图模式,查询不被限定于特定的XML树,给出了基于样式图模式的查询算法.用例说明了该方法如何应用于异构数据源的查询.     

存在完整性约束时最小化树模式查询的算法

树模式是查询树型结构数据如XML和LDAP的天然模型。在一个给定的数据库上进行查询，查询的效率很大程度上依赖于查询的大小。因此，在查询前删除查询中的冗余分支，使查询最小化是非常重要的。在树型结构数据库中，存在孩子必需、后代必需和子类3种完整性约束是十分普遍的。针对存在这3种完整性约束的情况，基于扩展的模拟概念提出了一种复杂度为O（n^2）的最小化树模式查询算法（n为树模式查询的节点数）。分析结果表明这个算法的效率要远高于同类算法。     

基于部分求值和热踪编译的Twig查询优化方法

XML树模式查询又称为Twig查询,是XML查询处理中最核心的操作。在Twig查询算法的研究中,TreeMatch算法由于极大程度上减少了中间结果的产生,被认为是最好的Twig查询算法之一。然而,在TreeMatch算法的核心操作getNext中,存在不少仅依赖Twig模式的计算。当getNext调用次数很多时,这种冗余的重复计算会影响TreeMatch算法的性能。为了进一步改进该算法,提出了一种基于部分求值和热踪编译的Twig查询优化方法,该方法以Twig模式作为不变量进行部分求值,把查询请求翻译成一种Twig查询机指令序列,避免了查询过程中对Twig模式的重复计算;并且针对这种查询机指令序列的解释过程,利用热踪编译技术进行了优化。对比实验说明基于部分求值和热踪编译的优化方法能够将Twig查询效率提高到20%到60%。     

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

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

一种基于扩展区间编码的结构连接算法TwigELM

由于XML具有格式良好,自描述,可扩展等优点,使得XML成为网络上信息表达和数据交换事实上的标准。随着XML格式数据的广泛应用,如何有效地存储和查询XML格式数据成为当前研究的热点。为了有效支持XML结构查询,研究者已经提出了XML数据的各种编码方案。通过编码的方式将XML结构查询的计算转化为结构连接的计算。该文提出了一种新的XML文档树编码方案,并基于该编码方案给出了一种新的小枝模式查询算法TwigELM,实验表明,该算法可有效提高结构连接操作的效率。     

一种GML文档的Twig模式查询算法

GML文档是XML技术在GIS方面的应用,成为空间数据在Internet上的实际表示、传输和交换的标准。目前,GML文档的查询是GIS领域的研究热点。对这一问题,研究了GML文档的数据特点和结构特点,设计了一种新的索引结构--GB树,GB树是专门针对GML文档中空间数据节点的索引结构。将XML Twig模式查询思想引入GML文档查询,借助GB树的索引特点,提出了GML文档的Twig模式查询算法--GMLTwigStackGB。GMLTwigStackGB算法保留了XML文档Twig模式查询算法的优势和特点,具有完整的空间查询功能。测试实验表明,该算法能够高效地满足GML文档上的各种数据查询。     

基于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...     

NP-miner: A real-time recommendation algorithm by using web usage mining

Web usage mining is widely applied in various areas, and dynamic recommendation is one web usage mining application. However, most of the current recommendation mechanisms need to generate all association rules before recommendations. This takes lots of time in offline computation, and cannot provide real-time recommendations for online users. This study proposes a Navigational Pattern Tree structure for storing the web accessing information. Besides, the Navigational Pattern Tree supports incremental growth for immediately modeling web usage behavior. To provide real-time recommendations efficiently, we develop a Navigational Pattern mining (NP-miner) algorithm for discovering frequent sequential patterns on the proposed Navigational Pattern Tree. According to historical patterns, the NP-miner scans relevant sub-trees of the Navigational Pattern Tree repeatedly for generating candidate recommendations. The experiments study the performance of the NP-miner algorithm through synthetic datasets from real applications. The results show that the NP-miner algorithm can efficiently perform online dynamic recommendation in a stable manner.     

一种基于XML的树型代数

为了解决Web仿真中,关系代数这种数据模型的查询功能的局限性.介绍了一种形式化的集合代数(bulk algebra)称为TAX(Tree Algebra for XML,基于XML的树型代数).TAX的数据模型为有标签的有序树组成的森林,它把关系代数和簇聚融合在一起,提出了树节点和完整树,并构造了模式树和证据树,在此基础上定义了一些数据查询操作.通过对TAX的仿真研究,仿真结果表明TAX不仅可以作用于XML的数据,而且还能有效的把这些面对用户的XML查询语言转换成面对XML数据库的高效的查询语言.同时满足数据的直观性、高效的计算性和有效的优化,而且表达了最多的XML查询.     

一种无候选集产生的并行关联规则挖掘算法

FPT(模式增长树)算法是一种不产生候选项集的串行关联规则挖掘算法,在效率上都优于基于Apriori的系列算法,因此该文利用FPT算法思想提出一种无候选集生成的并行关联规则算法PFPT,并与CD算法进行比较,结果表明该算法效率较CD算法优。     

有效的不确定数据概率频繁项集挖掘算法

针对已有概率频繁项集挖掘算法采用模式增长的方式构建树时产生大量树节点,导致内存空间占用较大以及发现概率频繁项集效率低等问题,提出了改进的不确定数据频繁模式增长(PUFP-Growth)算法。该算法通过逐条读取不确定事务数据库中数据,构造类似频繁模式树(FP-Tree)的紧凑树结构,同时更新项头表中保存所有尾节点相同项集的期望值的动态数组。当所有事务数据插入到改进的不确定数据频繁模式树(PUFP-Tree)中以后,通过遍历数组得到所有的概率频繁项集。最后通过实验结果和理论分析表明:PUFP-Growth算法可以有效地发现概率频繁项集;与不确定数据频繁模式增长(UF-Growth)算法和压缩的不确定频繁模式挖掘(CUFP-Mine)算法相比,提出的PUFP-Growth算法能够提高不确定数据概率频繁项集挖掘的效率,并且减少了内存空间的使用。     

改进的多数据流协同频繁项集挖掘算法

针对已有的多数据流协同频繁项集挖掘算法存在内存占用率高以及发现频繁项集效率低的问题,提出了改进的多数据流协同频繁项集挖掘（MCMD-Stream）算法。首先,该算法利用单遍扫描数据库的字节序列滑动窗口挖掘算法发现数据流中的潜在频繁项集和频繁项集;其次,构建类似频繁模式树（FP-Tree）的压缩频繁模式树（CP-Tree）存储已发现的潜在频繁项集和频繁项集,同时更新CP-Tree树中每个节点生成的对数倾斜时间表中的频繁项计数;最后,通过汇总分析得出在多条数据流中多次出现的且有价值的频繁项集,即协同频繁项集。相比A-Stream和H-Stream算法,MCMD-Stream算法不仅能够提高多数据流中协同频繁项集挖掘的效率,并且还降低了内存空间的使用率。实验结果表明MCMD-Stream算法能够有效地应用于多数据流的协同频繁项集挖掘。     

The XML Tree Model – toward an XML conceptual schema reversed from XML Schema Definition

XML Schema Definition (XSD) is the logical schemas of an XML model, but there is no standard format for the conceptual schema of an XML model. Therefore, we propose an XML Tree Model (XTM) as an XML conceptual schema for representing data semantics in a diagram, and also as an XML data model validator for confirming the data semantics required by users. An XTM consists of hierarchical nodes representing all the elements, and the data relationships among elements within the XSD. A rule-based algorithm and an information capacity with pre- and post-conditions are developed as the methodology for reverse engineering. The proposed algorithm consists of two rules: General Information Transformation and Data Semantic Recovering to construct an XTM. Users can draw an XTM with data relationships among elements as a result of the reverse engineering.     

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

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

XML结构聚类

针对当前XML文档结构聚类算法的一些不足,提出采用段匹配的概念来计算两棵XML文档树中的路径相似性,并在此基础上得出两棵树整体的相似度量。在整个聚类过程中,算法还把一组相关文档与一个XML聚类代表相关联,该聚类代表就包含了一个文档集合中所有文档的最相关的特征。为了构建聚类代表,算法通过构造最佳匹配树,合并树,修剪树三步来实现。通过比较聚类代表,发现新的聚类时更新聚类代表来完成文档聚类。实验结果就充分展现了算法的有效性。