使用模式树和物化视图进行XML查询

使用模式树解析XQuery查询，将经常被查询的XML节点信息存储到物化视图中，利用物化视图和用户查询的交叉部分，直接从物化视图中获取用户的查询内容。对于两者不完全匹配的部分，使用补充规则，使得能部分使用物化视图，以提高查询效率。文章还给出了模式树的匹配算法。     

基于语义缓存的移动查询导出

在移动环境下，客户缓存为提高客户－服务器数据库系统的整体性能，特别是保证客户端数据可用性提供了有效途径，该文针对如何从基于语义描述的缓存中导出当前查询（部分）结果的问题，研究了查询从缓存导出的充分条件，并在定义查询与缓存之间的精确匹配，包含匹配和相互匹配几种情况的基础上，给出缓存与查询，包含与相交匹配的判断条件和相应的算法，基于该文的研究，查询可以充分利用本地语义缓存的内容，从而降低网络开销，加快响应时间，并支持移动客户断接时的数据访问。     

基于XML的异构数据集成系统的查询处理

讨论了基于XML的Web异构数据源集成系统中的查询处理,并提出了针对全局视图的语义缓存的实现方法,包括查询与缓存入口的匹配算法,网络环境下缓存建立和淘汰算法;最后描述了Gav模式集成方式下的查询分解和优化方法。     

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

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

支持内存数据库索引缓存优化的CST树的设计与实现

针对目前内存数据库中索引缓存失配的问题,在分析了现有内存数据库索引结构基础上,提出了一种缓存敏感T树（CST树）的索引数据结构,详细数据结构描述和操作算法也已给出。通过CST树的缓存次数分析和进行查询、插入等操作性能测试,结果表明CST树能有效减少缓存敏感次数,并且在数据量较小时,CST树的插入、删除速度比T树略慢,而查询速度比T树要快。在数据量较大时,CST树的插入、删除、查询效率都比T树要高。     

基于T^＊树的RFID数据缓存的研究与实现

如何对RFID中的海量数据进行有效存储并支持高效查询已成为目前研究的难点和热点。根据RFID数据的访问特点,将RFID数据的存储分为缓存和数据仓库两部分。并设计实现了基于T^＊树内存索引结构的RFID数据缓存模块,最后对其中的查询算法特别是批量查询给出了具体实现。结果表明,T^＊树比T树更节省存储空间,具有更高的cache效率以及更短的平均查询时间。     

基于粗糙集的查询与规则不精确匹配近邻算法

针对专家系统中用于用户查询和规则之间不精确匹配问题,提出了一种包含规则的权重和条件属性重要性的近邻算法。该算法部分匹配用户查询和规则左部,计算用户查询与规则之间的距离,找出与用户查询近邻的规则。规则的权重由规则的支持度和置信度决定,而条件属性的重要性在粗糙集理论的基础上客观地计算得出。近邻规则右部就是提供给用户查询的求解方案。该算法的可行性通过一个简单实例进行了论证。     

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

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

语义缓存的聚集查询匹配研究

为提高海量数据库系统的查询效率，围绕海量数据库系统中的聚集查询技术，把通常应用于小型数据库查询的语义缓存技术拓展到海量数据库的聚集查询中．首先研究了面向聚集查询的语义缓存形式化描述，在此基础上讨论了利用缓存处理查询的条件并对查询匹配进行了分类，提出并实现了包含匹配判定算法和相交匹配判定算法，最后给出了相应的实验结果．在某大型实际工程中的应用表明上述判定算法是有效的．     

语义缓存技术的研究

语义缓存技术一直以来是数据库研究的热点之一。语义缓存是指将用户向服务器端提交的查询语句和查询实际得到的结果数据同一存储在指定的缓存中,因而其不仅包含有数据,还有对数据的相关描述信息,从而可以提高查询效率。在语义缓存之前,还存在页面缓存,元组缓存,块缓存等缓存技术。本文首先介绍语义缓存的模型,然后阐述和分析语义缓存查询匹配算法和缓存替换策略,最后对语义缓存技术进行总结,从而为语义缓存技术的进一步研究提供一定的理论基础。     

Finding hot query patterns over an XQuery stream

Caching query results is one efficient approach to improving the performance of XML management systems. This entails the discovery of frequent XML queries issued by users. In this paper, we model user queries as a stream of XML query pattern trees and mine the frequent query patterns over the query stream. To facilitate the one-pass mining process, we devise a novel data structure called DTS to summarize the pattern trees seen so far. By grouping the incoming pattern trees into batches, we can dynamically mark the active portion of the current batch in DTS and limit the enumeration of candidate trees to only the currently active pattern trees. We also design another summary data structure called ECTree that provides for the incremental computation of the frequent tree patterns over the query stream. Based on the above two constructs, we present two mining algorithms called XQSMinerI and XQSMinerII. XQSMinerI is fast, but it tends to overestimate, while XQSMinerII adopts a filter-and-refine approach to minimize the amount of overestimation. Experimental results show that the proposed methods are both efficient and scalable and require only small memory footprints.Received: 17 October 2003, Accepted: 16 April 2004, Published online: 14 September 2004Edited by: J. Gehrke and J. Hellerstein.     

基于语义贡献值的XML查询缓存替换策略

传统缓存替换策略对语义缓存替换缺乏针对性,不能有效重用缓存中的数据,影响缓存命中率。为此,针对可扩展标记语言查询(XML)代数查询的特点,提出一种基于语义贡献值的XML查询缓存替换策略,根据用户历史查询的缓存项进行聚类分析,预测其对未来查询的语义贡献值,当缓存空间不足时替换语义贡献值最小的项,从而提高用户查询效率。实验结果表明,相比最不经常使用策略和最近最少使用策略,该策略能有效缩短查询时间,提高缓存命中率。     

Object-stack: An object-oriented approach for top-k keyword querying over fuzzy XML

Keyword search is the most popular technique of searching information from XML (eXtensible markup language) document. It enables users to easily access XML data without learning the structure query language or studying the complex data schemas. Existing traditional keyword query methods are mainly based on LCA (lowest common ancestor) semantics, in which the returned results match all keywords at the granularity of elements. In many practical applications, information is often uncertain and vague. As a result, how to identify useful information from fuzzy data is becoming an important research topic. In this paper, we focus on the issue of keyword querying on fuzzy XML data at the granularity of objects. By introducing the concept of “object tree”, we propose the query semantics for keyword query at object-level. We find the minimum whole matching result object trees which contain all keywords and the partial matching result object trees which contain partial keywords, and return the root nodes of these result object trees as query results. For effectively and accurately identifying the top-K answers with the highest scores, we propose a score mechanism with the consideration of tf*idf document relevance, users’ preference and possibilities of results. We propose a stack-based algorithm named object-stack to obtain the top-K answers with the highest scores. Experimental results show that the object-stack algorithm outperforms the traditional XML keyword query algorithms significantly, and it can get high quality of query results with high search efficiency on the fuzzy XML document.     

A Semantic Cache Framework for Secure XML Queries

Secure XML query answering to protect data privacy and semantic cache to speed up XML query answering are two hot spots in current research areas of XML database systems. While both issues are explored respectively in depth,they have not been studied together,that is,the problem of semantic cache for secure XML query answering has not been addressed yet. In this paper,we present an interesting joint of these two aspects and propose an efficient framework of semantic cache for secure XML query answering,which can improve the performance of XML database systems under secure circumstances. Our framework combines access control,user privilege management over XML data and the state-of-the-art semantic XML query cache techniques,to ensure that data are presented only to authorized users in an efficient way. To the best of our knowledge,the approach we propose here is among the first beneficial efforts in a novel perspective of combining caching and security for XML database to improve system performance. The efficiency of our framework is verified by comprehensive experiments.     

基于XML数据的通用路径表达式的查询

查询重写是数据库研究的一个基本问题,它和查询优化、数据仓库、数据集成、语义缓存等数据库问题密切相关。同时,查询重写也是在关系数据库中存储和查询XML数据的关键问题。由于XML数据是元素嵌套和元素引用的,嵌套层数可以任意,并且模式和数据混合,因此XML的查询会涉及到广义路径表达式(GPE)。文中着重研究了如何解决XML数据的查询重写的方案,把含有广义路径表达式的XML查询语句重写为含有简单路径表达式(SPE)的XML查询语句,再转化为基于关系数据库的SQL语句。     

改进的XML小枝模式匹配方法

近年来, XML数据查询成为一个重要的研究课题。处理小枝查询是XML查询实现的核心操作,针对小枝模式查询,提出了一种改进的小枝模式匹配算法。该算法通过剪去无用的数据流以减少待处理结点的数目,从而节省处理时间,提高查询的准确率。实验结果表明,该算法能够有效提高查询效率。     

Incremental sequence-based frequent query pattern mining from XML queries

Existing algorithms of mining frequent XML query patterns (XQPs) employ a candidate generate-and-test strategy. They involve expensive candidate enumeration and costly tree-containment checking. Further, most of existing methods compute the frequencies of candidate query patterns from scratch periodically by checking the entire transaction database, which consists of XQPs transferred from user query logs. However, it is not straightforward to maintain such discovered frequent patterns in real XML databases as there may be frequent updates that may not only invalidate some existing frequent query patterns but also generate some new frequent query patterns. Therefore, a drawback of existing methods is that they are rather inefficient for the evolution of transaction databases. To address above-mentioned problems, this paper proposes an efficient algorithm ESPRIT to mine frequent XQPs without costly tree-containment checking. ESPRIT transforms XML queries into sequences using a one-to-one mapping technique and mines the frequent sequences to generate frequent XQPs. We propose two efficient incremental algorithms, ESPRIT-i and ESPRIT-i ⁺, to incrementally mine frequent XQPs. We devise several novel optimization techniques of query rewriting, cache lookup, and cache replacement to improve the answerability and the hit rate of caching. We have implemented our algorithms and conducted a set of experimental studies on various datasets. The experimental results demonstrate that our algorithms achieve high efficiency and scalability and outperform state-of-the-art methods significantly.     

用后缀树构造XML路径字典加快路径查询评价速度

后缀树的重要性可以为多年来学术界对它总是有新的发现而印证．它的结构简单，但可以在线性的时间里解决许多复杂的问题，被大量的使用在字符串及树的模式匹配中，对于XML标准，有很多基于关系库和对象库的索引技术和查询方案被提出来，我们试图给出一种基于后缀树进行路径导航的查询机制：用后缀树构造XML路径字典加速路径查询评价速度，我们提出可以在线地建立一个trie树的后缀树，讨论了XML路径字典中的后缀树建树算法，阐述了整个索引方案和查询机制，并探讨了包括RPE在内的它所支持的各种查询操作，XML路径字典被用于加快路径查询的评价速度．