An asymptotically optimal multiversion B-tree

In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage structures are an absolute necessity. We propose a multiversion B-tree that supports insertions and deletions of data items at the current version and range queries and exact match queries for any version, current or past. Our multiversion B-tree is asymptotically optimal in the sense that the time and space bounds are asymptotically the same as those of the (single-version) B-tree in the worst case. The technique we present for transforming a (single-version) B-tree into a multiversion B-tree is quite general: it applies to a number of hierarchical external access structures with certain properties directly, and it can be modified for others.     

Overlapping B-trees: An implementation of a transaction time access method

A new variation of Overlapping B⁺-trees is presented, which provides efficient indexing of transaction time and keys in a two dimensional key-time space. Modification operations (i.e. insertions, deletions and updates) are allowed at the current version, whereas queries are allowed to any temporal version, i.e. either in the current or in past versions. Using this structure, snapshot and range-timeslice queries can be answered optimally. However, the fundamental objective of the proposed method is to deliver efficient performance in case of a general pure-key query (i.e. ‘history of a key’). The trade-off is a small increase in time cost for version operations and storage requirements.     

基于区域聚类的查询流处理

提出一种处理区域查询流的新方法。选择并保存一些处理后的查询,将其进行区域聚类,构成较大的区域并检索和保存其元组。对新的查询,尽量使用内存中的元组,以减少对数据库I/O操作次数,进而加快查询速度。该方法对低维和高维数据都有效,实验证明该方法与朴素方法相比,其性能更高。     

应用分布式索引提高海量数据查询性能

在电信领域的精准化营销、即席查询业务中,存在着大量针对一张宽表或几张宽表（超过50字段）的随机查询场景. 传统处理模式（直接查询数据库）在数据量不大（〈;1000万）时,查询响应时间可优化到几秒至数十秒级,而当数据量到达几千万、上亿甚至十亿记录以上时,此处理模式无论如何优化或更改索引机制,都无法满足秒级并发查询要求.新的处理模式通过引入分布式Solr索引层解决上述问题.索引层预先对数据库记录建立索引,查询不再作用于数据库而直接查询索引层,如此,可大幅提高查询性能.经过对两种处理模式的对比验证,在相同环境下,数据量到达5000万,每秒20并发访问的宽表查询场景,传统处理模式的查询全部超时失败,而使用分布式索引层的查询可以在2秒以内返回,查询全部成功.     

面向城轨线网的海量数据查询优化方法

城轨线网数据中心汇集多条线路数据,单表记录量达数十亿条,当前系统数据查询响应时间过长、效率低下.提出利用数据库集群及中间件优化系统架构突破单库存储与处理瓶颈,多节点并行处理提升查询速度.按线路水平切分数据等方法,保证JOIN操作的局部性,满足新线路扩展需求;利用表分区、索引、物化视图、SQL语句优化等技术优化单机查询.其中,针对集群数据透明访问系统架构,设计专用数据库访问中间件,解决查询解析、路由及结果合成等关键问题.以广州城轨线路数据为例进行实验,结果表明通过本文方法各类查询响应时间至少降低90%.     

Voronoi-based multi-level range search in mobile navigation

Due to the universality and importance of range search queries processing in mobile and spatial databases as well as in geographic information system (GIS), numerous approaches on range search algorithms have been proposed in recent years. But ordinary range search queries focus only on a specific type of point objects. For queries which require to retrieve objects of interest locating in a particular region, ordinary range search could not get the expected results. In addition, most existing range search methods need to perform a searching on each road segments within the pre-defined range, which decreases the performance of range search. In this paper, we design a weighted network Voronoi diagram and propose a high-performance multilevel range search query processing that retrieves a set of objects locating in some specified region within the searching range. The experimental results show that our proposed algorithm runs very efficiently and outperforms its main competitor.     

数据库多表查询优化技术

利用面向对象语言C＋＋作为开发语言,采用了ADO数据库访问技术、Socket网络通信技术进行了仓库信息管理系统的开发. 设计了一种改进混合蛙跳算法对关系数据库的多表查询进行优化,使其通信费用和响应时间都显著降低. 该系统使用C/S架构,具有登录权限管理,数据库访问,数据库操作,数据库查询管理,报表及打印等功能模块. 最后实验证明所设计的系统查询效率有显著提高,能够准确完成各种查询管理任务,提高了仓库管理效率并节约了成本,具有较强的实际意义.     

Indexing spatiotemporal archives

Spatiotemporal objects – that is, objects that evolve over time – appear in many applications. Due to the nature of such applications, storing the evolution of objects through time in order to answer historical queries (queries that refer to past states of the evolution) requires a very large specialized database, what is termed in this article a spatiotemporal archive. Efficient processing of historical queries on spatiotemporal archives requires equally sophisticated indexing schemes. Typical spatiotemporal indexing techniques represent the objects using minimum bounding regions (MBR) extended with a temporal dimension, which are then indexed using traditional multidimensional index structures. However, rough MBR approximations introduce excessive overlap between index nodes, which deteriorates query performance. This article introduces a robust indexing scheme for answering spatiotemporal queries more efficiently. A number of algorithms and heuristics are elaborated that can be used to preprocess a spatiotemporal archive in order to produce finer object approximations, which, in combination with a multiversion index structure, will greatly improve query performance in comparison to the straightforward approaches. The proposed techniques introduce a query efficiency vs. space tradeoff that can help tune a structure according to available resources. Empirical observations for estimating the necessary amount of additional storage space required for improving query performance by a given factor are also provided. Moreover, heuristics for applying the proposed ideas in an online setting are discussed. Finally, a thorough experimental evaluation is conducted to show the merits of the proposed techniques. Edited by B. Seeger A short version of this article appeared as “Efficient indexing of spatiotemporal objects” in the Proceedings of Extending Database Technology 2002 [19]. This work was partially supported by NSF grants IIS-9907477, EIA-9983445, NSF IIS 9984729, NSF ITR 0220148, NSF IIS-0133825, NRDRP, and the U.S. Department of Defense.     

Uncertain Distance-Based Range Queries over Uncertain Moving Objects

Distance-based range search is crucial in many real applications. In particular, given a database and a query issuer, a distance-based range search retrieves all the objects in the database whose distances from the query issuer are less than or equal to a given threshold. Often, due to the accuracy of positioning devices, updating protocols or characteristics of applications (for example, location privacy protection), data obtained from real world are imprecise or uncertain. Therefore, existing approaches over exact databases cannot be directly applied to the uncertain scenario. In this paper, we redefine the distance-based range query in the context of uncertain databases, namely the probabilistic uncertain distance-based range (PUDR) queries, which obtain objects with confidence guarantees. We categorize the topological relationships between uncertain objects and uncertain search ranges into six cases and present the probability evaluation in each case. It is verified by experiments that our approach outperform Monte-Carlo method utilized in most existing work in precision and time cost for uniform uncertainty distribution. This approach approximates the probabilities of objects following other practical uncertainty distribution, such as Gaussian distribution with acceptable errors. Since the retrieval of a PUDR query requires accessing all the objects in the databases, which is quite costly, we propose spatial pruning and probabilistic pruning techniques to reduce the search space. Two metrics, false positive rate and false negative rate are introduced to measure the qualities of query results. An extensive empirical study has been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.     

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

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

Optimizing sort order query execution in balanced and nested gridfiles

Disk input/output (I/O) efficient query execution is an important topic with respect to DBMS performance. In this context, we elaborate on the construction of disk access plans for sort order queries in balanced and nested grid files. The key idea is to use the order information contained in the directory of the multiattribute search structure. The presented algorithms are shown to yield a significant decrease in the number of disk I/O operations by appropriate use of the order information. Two algorithms for the construction of appropriate disk access plans are proposed, namely a greedy approach and a heuristic divide-and-conquer approach. Both approaches yield considerable I/O savings compared to straightforward query processing without consideration of any directory order information. The former performs well for small buffer page allocations, i.e., for a small number of buffer pages relative to the number of data buckets processed in the query. The latter is superior to the greedy algorithm with respect to the total number of I/O operations and with respect to the overall maximum of buffer pages needed to achieve the minimal number of disk I/O operations. Both approaches rely on a binary trie as a temporary data structure. This trie is used as an explicit representation of the order information. The storage consumption of the temporary data structure is shown to be negligible in realistic cases, Even for pathological cases with respect to degenerated balanced and nested grid files, reasonable upper bounds can be given     

内存数据库中一种改进的图论存取方法及其性能分析

内存数据库是支持高性能信息处理的一种方法，对于内存数据库而言，数据库的存储结构与存取方法是关键。本文给出了一种内存数据库组织与存取的改进图论方法，并对该方法给几个基本的查询处理操作所能带来的优势进行了探讨，最后从存储空间和操作执行时间两方面进行了性能分析，结果显示改进的图论方法能提供很好的性能。     

一种基于共享执行策略的间隔查询优化技术

间隔查询作为重要的查询类型,广泛应用在社交网络、信息检索和数据库领域.为了支持高效的间隔查询,涌现出多种优化技术.尽管已有方法能够快速响应单个间隔查询,然而当查询负载超过服务器的处理能力时,70%的查询均不能在期望时间内得到响应.针对这一问题,提出采用共享执行策略优化间隔查询的方法SESIQ（shared execution strategy for interval queries）.SESIQ对间隔查询进行批处理,分析一组间隔查询间可共享的操作,减少重复数据的访问,从而降低磁盘I/O和网络传输代价,提高检索性能.理论分析并实验验证了SESIQ的可行性,基于两种真实数据集的大量实验结果表明,SESIQ是有效的,间隔查询的检索性能可提升数十倍.     

A form-based query interface for complex queries

It has been now well over thirty years since the advent of visual query systems (VQSs). Following a very active research period spanning from the late 1980s to the early 1990s, key research areas still remain, such as how to express complex queries in user-friendly fashion using a form-based query interface. A query is considered potentially complex from the user׳s point of view when it contains several entity sets and involves an aggregate operator and/or a many-to-many relationship set. This work examines such complex queries in the light of a form-based VQS, called OVI-2, and developed to handle the sophisticated query needs of users of the student records system at Aalto University, Otaniemi campus.Special emphasis is given to complex queries which involve existential quantification or its negation, such as finding students who have completed one given set of courses but who have not yet completed another given set of courses. User-friendliness was a key priority and was achieved mainly by using a two-phased approach for querying. The first stage focuses on retrieving all tuples and attributes that may be of interest, while in the second stage, users narrow down the set of tuples and select only the attributes that are actually needed.Although the presented VQS has been specifically developed for use with a student database, the key ideas are described in a generic way which should allow them to be used to query almost any database schema that has a many-to-many relationship set. Because OVI-2 was in active use for more than five years (over forty users had access to it), user feedback played a big role in this work. Many of the conclusions presented herein are based on observing users actually using OVI-2 to perform their timely query needs.     

Trustworthy keyword search for compliance storage

Intense regulatory focus on secure retention of electronic records has led to a need to ensure that records are trustworthy, i.e., able to provide irrefutable proof and accurate details of past events. In this paper, we analyze the requirements for a trustworthy index to support keyword-based search queries. We argue that trustworthy index entries must be durable—the index must be updated when new documents arrive, and not periodically deleted and rebuilt. To this end, we propose a scheme for efficiently updating an inverted index, based on judicious merging of the posting lists of terms. Through extensive simulations and experiments with two real world data sets and workloads, we demonstrate that the scheme achieves online update speed while maintaining good query performance. We also present and evaluate jump indexes, a novel trustworthy and efficient index for join operations on posting lists for multi-keyword queries. Jump indexes support insert, lookup and range queries in time logarithmic in the number of indexed documents.     

Space-efficient representations of rectangle datasets supporting orthogonal range querying

The increasing use of geographic search engines manifests the interest of Internet users in geo-located resources and, in general, in geographic information. This has emphasized the importance of the development of efficient indexes over large geographic databases. The most common simplification of geographic objects used for indexing purposes is a two-dimensional rectangle. Furthermore, one of the primitive operations that must be supported by every geographic index structure is the orthogonal range query, which retrieves all the geographic objects that have at least one point in common with a rectangular query region. In this work, we study several space-efficient representations of rectangle datasets that can be used in the development of geographic indexes supporting orthogonal range queries.     

Path dictionary: a new access method for query processing inobject-oriented databases

We present a new access method, called the path dictionary index (PDI) method, for supporting nested queries on object-oriented databases. PDI supports object traversal and associative search, respectively, with a path dictionary and a set of attribute indexes built on top of the path dictionary. We discuss issues on indexing and query processing in object-oriented databases; describe the operations of the new mechanism; develop cost models for its storage overhead and query and update costs; and compare the new mechanism to the path index method. The result shows that the path dictionary index method is significantly better than the path index method over a wide range of parameters in terms of retrieval and update costs and that the storage overhead grows slowly with the number of indexed attributes     

基于X-RESTORE查询XML视图

基于转换 XML文档到关系数据库中进行存储与查询的策略 ,研究了 XML视图查询的有效计算问题 .提出了XML 视图查询的合成重写技术 ,它能够消除视图查询中所有在视图结构上的路径导航操作 ,并将视图查询中所有在原文档结构上的路径导航操作以及所有谓词操作下推到视图定义中去 ,与视图定义中的路径导航操作相结合 ,形成统一的在原文档结构上的路径导航操作 .视图合成重写不仅避免了对视图中不出现在最后结果中的中间 XML 片段的构造 ,而且允许将查询中的所有内存密集型或数据密集型操作尽量下推到关系引擎中去执行 ,从而提高 XQuery查询的执行性能     

Query processing over object views of relational data

This paper presents an approach to object view management for relational databases. Such a view mechanism makes it possible for users to transparently work with data in a relational database as if it was stored in an object-oriented (OO) database. A query against the object view is translated to one or several queries against the relational database. The results of these queries are then processed to form an answer to the initial query. The approach is not restricted to a ‘pure’ object view mechanism for the relational data, since the object view can also store its own data and methods. Therefore it must be possible to process queries that combine local data residing in the object view with data retrieved from the relational database. We discuss the key issues when object views of relational databases are developed, namely: how to map relational structures to sub-type/supertype hierarchies in the view, how to represent relational database access in OO query plans, how to provide the concept of object identity in the view, how to handle the fact that the extension of types in the view depends on the state of the relational database, and how to process and optimize queries against the object view. The results are based on experiences from a running prototype implementation. Edited by: M.T. ?zsu. Received April 12, 1995 / Accepted April 22, 1996