Self-monitoring query execution for adaptive query processing

Adaptive query processing generally involves a feedback loop comprising monitoring, assessment and response. So far, individual proposals have tended to group together an approach to monitoring, a means of assessment, and a form of response. However, there are many benefits in decoupling these three phases, and in constructing generic frameworks for each of them. To this end, this paper discusses monitoring of query plan execution as a topic in its own right, and advocates an approach based on self-monitoring algebraic operators. This approach is shown to be generic and independent of any specific adaptation mechanism, easily implementable and portable, sufficiently comprehensive, appropriate for heterogeneous distributed environments, and more importantly, capable of driving on-the-fly adaptations of query plan execution. An experimental evaluation of the overheads and of the quality of the results obtained by monitoring is also presented.     

Using snapshot query fidelity to adapt continuous query execution

This paper explores the fidelity of queries issued in pervasive computing networks. A query’s fidelity, or how well its results reflect the state of the environment, can be significantly impacted by dynamics that occur during its distributed execution. We focus on continuous queries that can be built out of sequences of consecutive snapshot queries and show how the fidelity of snapshots can be used to determine the fidelity of continuous queries. This simple notion of continuous query fidelity can be used to adapt query processing to impact quality and cost tradeoffs given the current state of the environment.     

The CQL continuous query language: semantic foundations and query execution

CQL, a continuous query language, is supported by the STREAM prototype data stream management system (DSMS) at Stanford. CQL is an expressive SQL-based declarative language for registering continuous queries against streams and stored relations. We begin by presenting an abstract semantics that relies only on “black-box” mappings among streams and relations. From these mappings we define a precise and general interpretation for continuous queries. CQL is an instantiation of our abstract semantics using SQL to map from relations to relations, window specifications derived from SQL-99 to map from streams to relations, and three new operators to map from relations to streams. Most of the CQL language is operational in the STREAM system. We present the structure of CQL's query execution plans as well as details of the most important components: operators, interoperator queues, synopses, and sharing of components among multiple operators and queries. Examples throughout the paper are drawn from the Linear Road benchmark recently proposed for DSMSs. We also curate a public repository of data stream applications that includes a wide variety of queries expressed in CQL. The relative ease of capturing these applications in CQL is one indicator that the language contains an appropriate set of constructs for data stream processing. Edited by M. Franklin     

Optimization of parallel query execution plans in XPRS

In this paper, we describe our approach to optimization of query execution plans in XPRS, a multiuser parallel database system based on a shared memory multiprocessor and a disk array. The main difficulties in this optimization problem are the compile-time unknown parameters such as available buffer size and number of free processors, and the enormous search space of possible parallel plans. We deal with these problems with a novel two phase optimization strategy which dramatically reduces the search space and allows run time parameters without significantly compromising plan optimality. In this paper we present our two phase optimization strategy and give experimental evidence from XPRS benchmarks that indicate that it almost always produces optimal or close to optimal plans.     

Exploiting parallelism across program execution: a unificationtechnique and its analysis

A new technique for source-to-source transformation of sequential programs is described. It is shown that the transformed programs so generated provide significant speedups over the original program on vector processors and vector multiprocessors. The parallelism that arises when multiple instances of a program are executed on simultaneously available data sets is exploited. This is in contrast to the existing approaches that aim at detecting parallelism within a program. The analytic model is used to prove the optimality of the complete first policy for block selection for a class of program graphs known as nonregressive graphs. Analytic and simulation models of the technique clearly indicate the speedups that could be achieved when several data sets are available simultaneously, as is the case in many fields of interest     

Example-based graphical database query languages

Several user-friendly graphical database query languages that let users formulate a query by specifying a graphically aided example on the screen are compared. One of the earliest such languages, M.M. Zloof's (1977) Query-by-Example, is described. Other languages discussed are Aggregates-by-Example, Summary-Table-by-Example, and Query-by-Statistical-Relational-Table for statistical and scientific databases; Time-by-Example for historical databases; Generalized-Query-by-Example for relational, network, and hierarchical databases; Office-by-Example, Formanager, the Natural Forms Query Language, and System-for-Business-Automation for office environments; and Picquery and Query-by-Pictorial-Example for pictorial (image) databases. The basic features, query specification and interpretation, object manipulation, query language constructs, and query processing techniques used in each of the languages are discussed     

Dataflow query execution in a parallel main-memory environment

In this paper, the performance and characteristics of the execution of various join-trees on a parallel DBMS are studied. The results of this study are a step into the direction of the design of a query optimization strategy that is fit for parallel execution of complex queries.Among others, synchronization issues are identified to limit the performance gain from parallelism. A new hash-join algorithm is introduced that has fewer synchronization constraints than the known hash-join algorithms. Also, the behavior of individual join operations in a join-tree is studied in a simulation experiment. The results show that the introduced Pipelining hash-join algorithm yields a better performance for multi-join queries. The format of the optimal join-tree appears to depend on the size of the operands of the join: A multi-join between small operands performs best with a bushy schedule; larger operands are better off with a linear schedule. The results from the simulation study are confirmed with an analytic model for dataflow query execution.     

Efficient query execution on broadcasted index tree structures

The continuous broadcast of data together with an index structure is an effective way of disseminating data in a wireless mobile environment. The index allows a mobile client to tune in only when relevant data is available on the channel and leads to reduced power consumption for the clients. This paper investigates the execution of queries on broadcasted index trees when query execution corresponds to a partial traversal of the tree. Queries exhibiting this behavior include range queries and nearest neighbor queries. We present two broadcast schedules for index trees and two query algorithms executed by mobile clients. Our solutions simultaneously minimize tuning time and latency and adapt to the client’s available memory. Experimental results using real and synthetic data compare results for a broadcast with node repetition to one without node repetition and they show how a priority-based data management can help reduce tuning time and latency.     

Adaptive selection of query execution strategies by learning automata

The traditional approach to evaluate query execution strategies using approximate cost models may be inadequate for particular environments. For instance, if the environment does not satisfy the assumptions made by the cost model, the cost estimates can be so distorted that expensive strategies will be chosen. We propose a new approach for choosing execution strategies based on the actual cost history of query execution under various strategies, rather than on assumption-loaded estimates of these costs. Adaptive selection automatically changes the strategies selected, tracking cost variations caused by changes in the database state and query load. Furthermore, it does not require any assumptions about internal database structures, data characteristics, or distribution of queries. Queries are divided into query classes, where all queries in a class share the same execution strategies. A learning automaton is then used for each class to infer over time which are the current best strategies, based on actual query execution costs. We show the results of running the adaptive selector using real query loads for an existing database.     

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     

Video-graphic query facility for database retrieval

The goal of this project was to develop a prototype to demonstrate the use of video and graphic techniques applied to the human-machine interface for data retrieval from a typical computerized database. Data is presented to a user via video and graphic means; queries are formulated in one of several graphic formats; control operations are handled through joystick, touch panel, or single-keystroke maneuvers. To accomplish this, we made use of videodisc, interactive computer graphics, and relational database technologies. Still pictures, video segments, and pictures of text are used as visual cues to a user who indicates interest in a data item in a pointing gesture by touching the panel through which the item may be seen. The user may find the actual data item s/he desires, then pose a query for additional information in one of four graphic query formats. A specially designed database was developed to handle the video and graphic data needed for this user facility.     

Semantic interpretation of a database query language

In this paper, we will discuss a system that semantically interprets a formal database accessing language and generates natural language from this interpretation. In the past, the major way of communication between a user and a database was by means of a formal language. One such language is the SQL query language. Even though constructed as a user friendly language, SQL exemplifies the same difficulties for users as do other formal languages, namely a fairly rigid syntax, the necessity of variable binding, the lack of pronouns, and in the case of erroneous queries error messages that do not provide much insight. To alleviate some of the formal language problems, yet utilize the power of the formal language, we set out to build a natural language ‘umbrella’ for the SQL user. Our goal was not to build a natural language query system, but rather to use semantic knowledge and natural language for paraphrasing the formal language (SQL) and producing error messages as a feedback mechanism. In this way we build a genuine help facility, which would not only aid the user in dealing with SQL, but also trap erroneous queries.     

Fuzzy database query languages and their relational completenesstheorem

Two fuzzy database query languages are proposed. They are used to query fuzzy databases that are enhanced from relational databases in such a way that fuzzy sets are allowed in both attribute values and truth values. A fuzzy calculus query language is constructed based on the relational calculus, and a fuzzy algebra query language is also constructed based on the relational algebra. In addition, a fuzzy relational completeness theorem such that the languages have equivalent expressive power is proved     

正则表达式在数据库查询中的应用

SQL语句在数据库查询中具有非常重要的地位,但是标准的SQL语句在复杂的数据库查询中却存在着诸多不足。而正则表达式有着强大的查询功能,通过对正则表达式特殊字符以及数据库查询语言中谓词的分析,提出了将正则表达式运用于数据库查询当中的新查询方法,并对该方法在实际查询应用当中会遇到的几个普遍问题进行了探讨。从而证明该方法不仅可以降低查询语句的复杂程度而且还能简化对出错语句的修改工作。     

用ISAPI和ODBC实现Web数据库的通用查询

ISAPI是因特网信息服务的应用程序编程接口,它提供了运行在WindowsNT上的IIS的一整套函数,阐述了利用ISAPI和ODBC来访问WEB数据库的基本方法,同时给出了WEB数据库的通用查询的程序实现。     

Modeling and analysis of transaction execution in database systems

The controlled-generator model of P.J. Ramadge and W.M. Wonham (1988) is used to formulate the concurrent execution of transactions in database systems as a control problem for a partially observed discrete-event dynamical system. The control objectives of this problem (for concurrency control and recovery) and the properties of some important transaction scheduling techniques are characterized in terms of the language generated by the controlled process and in terms of the stage of an ideal complete-information scheduler. Results about the performance of these techniques are presented     

基于Web的工程物性数据库查询系统

物性数据库是进行化工计算的基础,网络工程物性数据库一方面给用户提供了一种方便快捷的查询途径,另一方面也给化工网络仿真协作实验提供了后台数据。根据三层B/S结构,采用Java语言和Access数据库系统,设计了基于Web的工程物性数据库查询系统的实现框架、具体的体系结构及技术方案,实现了常见的化学物质的26种工程物性的查询。用户可以通过网络查询各种物质的物性数据,化工网络仿真实验也能通过这一网络数据库实时的读取数据。     

Multiclass query scheduling in real-time database systems

In recent years, a demand for real-time systems that can manipulate large amounts of shared data has led to the emergence of real-time database systems (RTDBS) as a research area. This paper focuses on the problem of scheduling queries in RTDBSs. We introduce and evaluate a new algorithm called Priority Adaptation Query Resource Scheduling (PAQRS) for handling both single class and multiclass query workloads. The performance objective of the algorithm is to minimize the number of missed deadlines, while at the same time ensuring that any deadline misses are scattered across the different classes according to an administratively-defined miss distribution. This objective is achieved by dynamically adapting the system's admission, memory allocation, and priority assignment policies according to its current resource configuration and workload characteristics. A series of experiments confirms that PAQRS is very effective for real-time query scheduling     

Fuzzy query translation for relational database systems

The paper presents a new method for fuzzy query translation based on the alpha-cuts operations of fuzzy numbers. This proposed method allows the retrieval conditions of SQL queries to be described by fuzzy terms represented by fuzzy numbers. It emphasizes friendliness and flexibility for inexperienced users. The authors have implemented a fuzzy query translator to translate user's fuzzy queries into precise queries for relational database systems. Because the proposed method allows the user to construct his fuzzy queries intuitively and to choose different retrieval threshold values for fuzzy query translation, the existing relational database systems will be more friendly and more flexible to the users.     

并行数据库查询优化技术的最新进展

传统的查询树及基于多重加权树的查询优化方法,研究得比较成熟,语义查询优化方法将一个查询变换成一个或数个语义等价的查询,基于Agent的并行数据库查询优化采用Multi-Agent技术自动查找与给定查询有关的完整性约束条件,使得多个关系间连接操作的效率得到很大地提高.并行数据库的查询优化领域的3个重要方向为基于机群系统的并行数据库查询优化研究,将MAS技术及专家系统引入本领域,将模拟退火算法及神经网络算法引入本领域.