查询重写关系数据库查询优化技术

随着数据仓库技术应用越来越广泛,数据仓库中查询使用频率也越来越高,基于查询重写的关系数据库查询优化技术,通过视图重写、子查询合并、等价谓词替换、使用临时表、以及用集合运算UNION代替逻辑运算OR等技术的使用。本文详细讨论了数据库查询优化器中查询重写模块的设计与实现;探讨了XML、SQL语句等查询重写方法。     

Cbase查询优化的重写机制及其实现

Cbase是南京大学计算机系与南大谷元石油软件研究所有限公司研制的新一代商用关系数据库管理系统。为了提高查询效率,作者开发了Cbase数据库的查询优化器。文章详细论述了Cbase查询优化器中重写模块的设计思想与实现技术,并讨论了基于执行引擎特点引入的一组基于等价谓词的简单语句的重写规则。测试结果表明,所设计的重写器能够显著提高系统的查询效率。     

关系数据库系统的查询优化策略

主要讨论了基于SQL查询重写技术的数据库查询优化策略，通过查询重写可以把用户所写的效率不高的SQL语句重新优化组合，使之成为效率较高的查询语句。     

一种扩充语义的实视图重写查询技术

分组聚集查询已成为数据仓库领域研究的核心问题之一,实视图是提高分组聚集查询性能的有效手段。利用维属性间的层次关系,对一般意义上的实视图重写查询进行了扩展,讨论了单一视图重写查询的限制条件,并给出重写方法,在此基础上,提出了一种利用多个实视图重写查询的优化选择算法,并通过实验表明,该算法进一步提高了分组聚集查询效率。     

Key-Tree：一种增强目录索引接口有限查询能力的方法

限于目录索引接口的查询能力．为了优化采用这种接口的信息查询系统．讨论了通用的基于目录索引的信息查询系统，提出一种优化算法通过对查询条件和查询结果进行分析、提取．构造出相关文档的关键字树．并基于关键字树对查询进行重写．生成由关键字组成的新的查询序列．使用生成的关键字序列重新搜索文档．比较两次查询结果并对其进行优先级排序．输出优化后的查询结果。实验结果证明本文提出的查询优化方法能够获得具有更高查全率(recall)和查准率(precision)的查询结果。     

知识管理中语义与关键字相结合的检索方法

在泛化和聚集语义关系基础上生成大量的子查询语句，同时按照与原始语句的语义距离将权值传递给子查询语句．该方法能够由关键字匹配得到大量的结果，通过OWA(Ordered Weighted Averaging)操作给每个结果赋予权值，合并这两部分权值，排序最终结果，并按照重要程度呈现给用户．文中将查询重写与权值传递统一在查询重写模板的概念中．     

半结构化数据查询重写

查询重写是数据库研究的一个基本问题，它和查询优化，数据仓库，信息集成，语义缓存等问题紧密相关，目前Internet上存在海量的半结构化数据，在信息集成过程中产生了大量半结构化视图，如何利用物化半结构化视图来重写用户查询，减少响应时间成为研究热点问题，上述问题本质上是NP问题，提出了一种半结构化查询重写的新方法，该方法在保证算法正确性和完备性的基础上，利用半结构化数据特点和查询子目标之间的关系，减少了指数空间的查询重写候选方案生成，理论分析表明，它极大地降低了算法的代价。     

利用视图重写技术优化XML查询

规则路径查询，其长度是任意的，这就意味着对数据库的任意多次访问，这样的代价是很昂贵的。我们采用视图重写技术，通过对某些经常使用的路径查询定义视图。从而减少了对某些高频使用的路径查询的重复搜索，最终提高了查询效率。我们的视图不但可以对路径查询进行重写，而且还可以对树查询进行混合重写。我们设计了一个使用动态规划策略实现的视图重写算法。     

异构数据源集成应用模型及其查询处理方法

异构数据源联合使用的目的是屏蔽数据源的异构性，提供给用户一个使用多种数据源的统一接口，在实现联合使用的系统中的难点是用户查询的重写和分解。该文介绍了基于半结构化数据模型的异构数据源联合使用的实现，描述了其中的查询重写和查询分解的方法。     

基于物化视图的查询系统研究与实现

在数据库领域,如何加快查询的执行速度非常重要。查询重写技术能透明地利用物化视图回答查询,避免了直接访问大量的原始记录以及耗时的连接和聚集计算,提高了查询 的执行速度。本文讨论了基于数据库中的外键连接关系进行扩展的查询重写方法,以此为核心研究了针对小型数据库的物化视图查询系统,并通过实验证明了物化视图策略的有效性。     

Transformation of structure-shy programs with application to XPath queries and strategic functions

Various programming languages allow the construction of structure-shy programs. Such programs are defined generically for many different datatypes and only specify specific behavior for a few relevant subtypes. Typical examples are XML query languages that allow selection of subdocuments without exhaustively specifying intermediate element tags. Other examples are languages and libraries for polytypic or strategic functional programming and for adaptive object-oriented programming.In this paper, we present an algebraic approach to transformation of declarative structure-shy programs, in particular for strategic functions and XML queries. We formulate a rich set of algebraic laws, not just for transformation of structure-shy programs, but also for their conversion into structure-sensitive programs and vice versa. We show how subsets of these laws can be used to construct effective rewrite systems for specialization, generalization, and optimization of structure-shy programs. We present a type-safe encoding of these rewrite systems in Haskell which itself uses strategic functional programming techniques. We discuss the application of these rewrite systems for XPath query optimization and for query migration in the context of schema evolution.     

Improving Federated Database Queries Using Declarative Rewrite Rules for Quantified Subqueries

Transforming queries for efficient execution is particularly important in federated database systems since a more efficient execution plan can require many fewer data requests to be sent to the component databases. Also, it is important to do as much as possible of the selection and processing close to where the data are stored, making best use of facilities provided by the federation's component database management systems. In this paper we address the problem of processing complex queries including quantifiers, which have to be executed against different databases in an expanding heterogeneous federation. This is done by transforming queries within a mediator for global query improvement, and within wrappers to make the best use of the query processing capabilities of external databases. Our approach is based on pattern matching and query rewriting. We introduce a high level language for expressing rewrite rules declaratively, and demonstrate the use and flexibility of such rules in improving query performance for existentially quantified subqueries. Extensions to this language that allow generic rewrite rules to be expressed are also presented. The value of performing final transformations within a wrapper for a given remote database is shown in several examples that use AMOS II—an SQL3-like system.     

利用区间约束优化包含多个用户函数的查询

如何高效地处理说明性查询语言中嵌入的用户自定义函数,是查询优化的一个重要内容.以往的研究成果不能处理一条语句中的多个用户函数,并且难以实现.提出了分3个阶段进行优化的方案,能够对用户定义的多个函数进行处理.首先,把用户定义的函数以区间约束的形式等价地表述出来;然后,通过对区间约束进行分层筛选,去掉冗余;最后,选择最佳的执行策略.该方案易于实现,效率较高,特别是在用户定义的函数本身隐含多个表的连接条件时,更能取得明显的优化效果.     

Partial Evaluation of Views

Many database applications and environments, such as mediation over heterogeneous database sources and data warehousing for decision support, lead to complex queries. Queries are often nested, defined over previously defined views, and may involve unions. There are good reasons why one might want to remove pieces (sub-queries or sub-views) from such queries: some sub-views of a query may be effectively cached from previous queries, or may be materialized views; some may be known to evaluate empty, by reasoning over the integrity constraints; and some may match protected queries, which for security cannot be evaluated for all users.In this paper, we present a new evaluation strategy with respect to queries defined over views, which we call tuple-tagging, that allows for an efficient removal of sub-views from the query. Other approaches to this are to rewrite the query so the sub-views to be removed are effectively gone, then to evaluate the rewritten query. With the tuple tagging evaluation, no rewrite of the original query is necessary.We describe formally a discounted query (a query with sub-views marked that are to be considered as removed), present the tuple tagging algorithm for evaluating discounted queries, provide an analysis of the algorithm's performance, and present some experimental results. These results strongly support the tuple-tagging algorithm both as an efficient means to effectively remove sub-views from a view query during evaluation, and as a viable optimization strategy for certain applications. The experiments also suggest that rewrite techniques for this may perform worse than the evaluation of the original query, and much worse than the tuple tagging approach.     

基于HGAV的多源异构数据集成方法

针对信息系统中海量数据多源异构和难以共享的问题, 提出了多源异构数据虚拟集成框架. 数据集成系统中的GAV(Global-as-View)模式映射方法面对信息量分布不均匀的数据源时, 查询效率较低, 在对GAV改进的基础上, 提出了基于HGAV(Hierarchical-Global-as-view)的模式映射算法, 通过引入中间数据源模式, 形成分层的全局视图, 大大缩减了映射空间, 简化了映射集合, 便于查询的重写和优化. 利用宁东智慧环保项目中的五大类数据对本文所提出的算法加以验证, 实验结果表明该算法相较于GAV模式映射算法提高了数据集成效率, 缩短了查询时间.