An Efficient Algorithm for Processing Multi-Relation Queries in Relational Databases

After a relation scheme R is decomposed into the set of schemes ρ={R1，…，Rn},we may pose queries as if Rexisted in the database,taking a join of Ri‘s,when it is necessary to implement the query,Suppos a query involves a set of attributes S R，we want to find the smallest subset of ρ whose union includes.S.We prove that the problem is NP-complete and present a polynomial-bounded approximation algorithm.A subset of ρ whose union includes S and has a decomposition into 3NF with a lossless join and preservation of dependencies in given in the paper.     

Semantic-distance based evaluation of ranking queries over relational databases

Traditional database search uses pattern match in the comparison process. For a query with some search words, tuples are selected only if the words of the tuples exactly match the query words. In this paper, we propose a new method for evaluating relational ranking queries (or top-N queries) with text attributes. This method defines semantic distance functions and utilizes semantic match between words in database search. The attempt is that tuples, not only exactly matching, but also close to the query according to semantic distances, can both be fetched. The basic idea of the method is to create an index based on WordNet to expand the tuple words semantically. The candidate results for a query are retrieved by the index and a simple SQL selection statement, and then top-N answers are obtained. Extensive experiments are carried out to measure the performance of this new strategy for the evaluation of ranking queries over relational databases.     

Reliability of answers to queries in relational databases

The author studies the problem of determining the reliability of answers to queries in a relational database system, where the information in the database comes from various sources with varying degrees of reliability. An extended relational model is proposed in which each tuple in a relation is associated with an information source vector which identifies the information source(s) that contributed to that tuple. The author shows how relational algebra operations can be extended, and implemented using information source vectors, to calculate the vector corresponding to each tuple in the answer to a query, and hence, to identify information source(s) contributing to each tuple in the answer. This also enables the database system to calculate the reliability of each tuple in the answer to a query as a function of the reliability of information sources     

About projection-selection-join queries addressed to possibilistic relational databases

This work deals with databases containing ill-known attribute values represented by possibility distributions. Any such database has a canonical interpretation as a set of regular databases, but it is well known that their manipulation raises a number of problems, in particular with respect to the soundness of querying operations and the tractability of the evaluation process. In This work, we propose a query language including three operators which are soundly defined on extended possibilistic (compact) relations, which is the key for tractability. The originality of the approach is twofold: 1) a nesting mechanism is introduced in the data model in order to support the expression of the result of some of the operations allowed, and 2) a joint operation enables to compose possibilistic relations under some reasonable hypotheses.     

Measuring the quality of queries in the fuzzy relational databases

In this paper, we develop a new method to measure the quality of each tuple as an answer with respect to Select‐Project‐Join (SPJ) queries so that we can determine which answers are better answers to the given query in a fuzzy relational database. The quality of an answer is viewed as how much sure information is provided, and how much extra information is needed so that it will be a sure answer to the query. The less extra information that is required and the more sure information that is provided by an answer, the higher the quality of that answer is, and in consequence, it will be more reliable. © 2001 John Wiley & Sons, Inc.     

Mining frequent conjunctive queries in relational databases through dependency discovery

We present an approach for mining frequent conjunctive in arbitrary relational databases. Our pattern class is the simple, but appealing subclass of simple conjunctive queries. Our algorithm, called Conqueror $^+$ , is capable of detecting previously unknown functional and inclusion dependencies that hold on the database relations as well as on joins of relations. These newly detected dependencies are then used to prune redundant queries. We propose an efficient database-oriented implementation of our algorithm using SQL and provide several promising experimental results.     

A graph-theoretic approach to optimize keyword queries in relational databases

Keyword search can provide users an easy method to query large and complex databases without any knowledge of structured query languages or underlying database schema. Most of the existing studies have focused on generating candidate structured queries relevant to keywords. Due to the large size of generated queries, the execution costs may be prohibitive. However, existing studies lack the idea of a generalized method to optimize the plan of the large set of generated queries. In this paper, we introduce a graph-theoretic optimization approach. We propose a general graph model, Weighted Operator Graph, to address the costs of keyword query evaluation plans. The proposed model is flexible to integrate all of the cost-based plans in a uniform way. We define a Keyword Query Optimization Problem based on a theoretical cost model as a graph-theoretic problem and show it to be a NP-hard problem. We propose a greedy heuristic Maximum Propagation that reduces the size of the intermediate result as early as possible. The proposed algorithm allows us to achieve efficiency in terms of query evaluation costs. The experimental studies on both synthetic and real data set results show that our work outperforms the existing work.     

关系数据库中分组查询的模糊扩展及去模糊机制

当前关系数据库模糊查询的研究中,涉及到分组查询having子句中的模糊条件或相对语言量词的较少。在模糊理论的基础上对having子句进行了模糊扩展,并利用模糊集合隶属函数的α截集将模糊的having子句转化为标准的SQL语句,因此可以利用RDBMS对记录进行筛选,保证了查询的效率。利用模糊集合基数的非模糊表示法来计算带量词的having语句,计算简单,结果简洁。     

Partial evaluation of queries in deductive databases

This paper presents some applications of partial evaluation method to a query optimization in deductive database. A Horn clause transformation is used for the partial evaluation of a query in an intensional database, and its application to multiple query processing is discussed. Three strategies are presented for the compatible case, ordered case and crossed case. In each case, partial evaluation is used to preprocess the intensional database in order to obtain subqueries which direct access to an extensional database.     

Efficient evaluation of specific queries in constraint databases

Let F₁,…,Fs∈R[X₁,…,Xn] be polynomials of degree at most d, and suppose that F₁,…,Fs are represented by a division free arithmetic circuit of non-scalar complexity size L. Let A be the arrangement of Rn defined by F₁,…,Fs.For any point x∈Rn, we consider the task of determining the signs of the values F₁(x),…,Fs(x) (sign condition query) and the task of determining the connected component of A to which x belongs (point location query). By an extremely simple reduction to the well-known case where the polynomials F₁,…,Fs are affine linear (i.e., polynomials of degree one), we show first that there exists a database of (possibly enormous) size sO(L+n) which allows the evaluation of the sign condition query using only (Ln)^O(1)log(s) arithmetic operations. The key point of this paper is the proof that this upper bound is almost optimal.By the way, we show that the point location query can be evaluated using dO(n)log(s) arithmetic operations. Based on a different argument, analogous complexity upper-bounds are exhibited with respect to the bit-model in case that F₁,…,Fs belong to Z[X₁,…,Xn] and satisfy a certain natural genericity condition. Mutatis mutandis our upper-bound results may be applied to the sparse and dense representations of F₁,…,Fs.     

A motion-aware approach for efficient evaluation of continuous queries on 3D object databases

With recent advances in mobile computing technologies, mobile devices can render 3D objects realistically. Users of these devices such as tourists, mixed-reality gamers, and rescue officers, often need real-time retrieval of 3D objects over wireless networks. Due to bandwidth and latency restrictions in mobile settings, efficient continuous retrieval of 3D objects is a major challenge. In this paper, we present a motion-aware approach to this problem in a client-server model. Specifically, we propose: (i) representing 3D objects in multiple resolutions through wavelets to facilitate motion-aware incremental retrieval, (ii) motion-aware buffer management schemes for both client and server, (iii) an efficient index structure for 3D objects represented by wavelets, and (iv) techniques for processing group queries exploiting group motion behavior of clients. The results of our extensive experimental study demonstrate the effectiveness of our solution.     

Answers to queries concerning uncertain and imprecise information in fuzzy relational databases

A model of an extended fuzzy relational database was proposed to accommodate uncertain and imprecise information. We use two supplementary measurements, satisfactory degree and extra degree, for determining the quality of answers to Select‐Project‐Join (SPJ) queries. The method of measurement determines how much satisfactory information is provided and how much truth information is required for a query. The answers to the query thus contain sure answers and maybe answers. The core of this study is the detailed discussion on the quality of answers in an extended fuzzy relation to query processing. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 647–668, 2005.     

MINDEX: An efficient index structure for salient-object-based queries in video databases

Several salient-object-based data models have been proposed to model video data. However, none of them addresses the development of an index structure to efficiently handle salient-object-based queries. There are several indexing schemes that have been proposed for spatiotemporal relationships among objects, and they are used to optimize timestamp and interval queries, which are rarely used in video databases. Moreover, these index structures are designed without consideration of the granularity levels of constraints on salient objects and the characteristics of video data. In this paper, we propose a multilevel index structure (MINDEX) to efficiently handle the salient-object-based queries with different levels of constraints. We present experimental results showing the performance of different methods of MINDEX construction.     

An efficient query optimization strategy for spatio-temporal queries in video databases

The interest for multimedia database management systems has grown rapidly due to the need for the storage of huge volumes of multimedia data in computer systems. An important building block of a multimedia database system is the query processor, and a query optimizer embedded to the query processor is needed to answer user queries efficiently. Query optimization problem has been widely studied for conventional database systems; however it is a new research area for multimedia database systems. Due to the differences in query processing strategies, query optimization techniques used in multimedia database systems are different from those used in traditional databases. In this paper, a query optimization strategy is proposed for processing spatio-temporal queries in video database systems. The proposed strategy includes reordering algorithms to be applied on query execution tree. The performance results obtained by testing the reordering algorithms on different query sets are also presented.     

关系数据库中聚合代数约束的高效发现算法——AAC-Hunter

针对如何更好地维护关系数据库的数据完整性以及帮助审计员找出违规的报销记录的问题,提出了自动发现聚合代数约束(AAC)的算法AAC-Hunter.AAC是一种定义在数据库中两列的聚合结果之间的模糊约束,作用于大多数而非全部记录上.AAC-Hunter首先枚举连接、分组和代数表达式来产生候选AAC,然后分别计算这些候选AA...     

An efficient method for estimating null values in relational databases

Generally, a database system containing null value attributes will not operate properly. This study proposes an efficient and systematic approach for estimating null values in a relational database which utilizes clustering algorithms to cluster data, and a regression coefficient to determine the degree of influence between different attributes. Two databases are used to verify the proposed method: (1) Human resource database; and (2) Waugh's database. Furthermore, the mean of absolute error rate (MAER) and average error are used as evaluation criteria to compare the proposed method with other methods. It demonstrates that the proposed method is superior to existing methods for estimating null values in relational database systems. Jia-Wen Wang was born on September 5, 1978, in Taipei, Taiwan, Republic of China. She received the M.S. degree in information management from the National Yunlin University of Science and Technology, Yunlin, Taiwan, in 2003. Since 2003, she has been a PhD degree student in Information Management Department at the National Yunlin University of Science and Technology. Her current research interests include fuzzy systems, database systems, and artificial intelligence. Ching-Hsue Cheng received the B.S. degree in mathematics from Chinese Military Academy, Taiwan, in 1982, the M.S. degree in applied mathematics from the Chung Yuan Christian University, Taiwan, in 1988, and the Ph.D. degree in system engineering and management from National Defence University, Taiwan, in 1994. Currently, he is a professor of the Department of Information Management, National YunLin University of Technology & Science. His research interests are in decision science, soft computing, software reliability, performance evaluation, and fuzzy time series. He has published more than 120 refereed papers in these areas. He has been a principal investigator and project leader in a number of projects with government, and other research-sponsoring agencies.     

Top-k typicality queries and efficient query answering methods on large databases

Finding typical instances is an effective approach to understand and analyze large data sets. In this paper, we apply the idea of typicality analysis from psychology and cognitive science to database query answering, and study the novel problem of answering top-k typicality queries. We model typicality in large data sets systematically. Three types of top-k typicality queries are formulated. To answer questions like “Who are the top-k most typical NBA players?”, the measure of simple typicality is developed. To answer questions like “Who are the top-k most typical guards distinguishing guards from other players?”, the notion of discriminative typicality is proposed. Moreover, to answer questions like “Who are the best k typical guards in whole representing different types of guards?”, the notion of representative typicality is used. Computing the exact answer to a top-k typicality query requires quadratic time which is often too costly for online query answering on large databases. We develop a series of approximation methods for various situations: (1) the randomized tournament algorithm has linear complexity though it does not provide a theoretical guarantee on the quality of the answers; (2) the direct local typicality approximation using VP-trees provides an approximation quality guarantee; (3) a local typicality tree data structure can be exploited to index a large set of objects. Then, typicality queries can be answered efficiently with quality guarantees by a tournament method based on a Local Typicality Tree. An extensive performance study using two real data sets and a series of synthetic data sets clearly shows that top-k typicality queries are meaningful and our methods are practical.     

Preference queries in deductive databases

Traditional database query languages such as datalog and SQL allow the user to specify only mandatory requirements on the data to be retrieved from a database. In many applications, it may be natural to express not only mandatory requirements but also preferences on the data to be retrieved. Lacroix and Lavency¹⁰⁾ extended SQL with a notion of preference and showed how the resulting query language could still be translated into the domain relational calculus. We explore the use of preference in databases in the setting of datalog. We introduce the formalism of preference datalog programs (PDPs) as preference logic programs without uninterpreted function symbols for this purpose. PDPs extend datalog not only with constructs to specify which predicate is to be optimized and the criterion for optimization but also with constructs to specify which predicate to be relaxed and the criterion to be used for relaxation. We can show that all of the soft requirements in Reference¹⁰) can be directly encoded in PDP. We first develop anaively-pruned bottom-up evaluation procedure that is sound and complete for computing answers to normal and relaxation queries when the PDPs are stratified, we then show how the evaluation scheme can be extended to the case when the programs are not necessarily stratified, and finally we develop an extension of themagic templates method for datalog¹⁴) that constructs an equivalent but more efficient program for bottom-up evaluation. Kannan Govindarajan, Ph.D.: He obtained his bachelors degree in Computer Science and Engineering from the Indian Institute of Technology, Madras, and he completed his Ph.D. degree in Computer Science from the State University of New York at Buffalo. His dissertation research was on optimization and relaxation techniques for logic languages. His interests lie in the areas of programming languages, databases, and distributed systems. He currently leads the trading community effort in the E-speak Operation in Hewlett Packard Company. Prior to that, he was a member of the Java Products Group in Oracle Corporation. Bharat Jayaraman, Ph.D.: He is a Professor in the Department of Computer Science at the State University of New York at Buffalo. He obtained his bachelors degree in Electronics from the Indian Institute of Technology, Madras (1975), and his Ph.D. from the University of Utah (1981). His research interests are in programming languages and declarative modeling of complex systems. Dr. Jayaraman has published over 50 papers in refereed conferences and journals. He has served on the program committees of several conferences in the area of programming languages, and he is presently on the Editorial Board of the Journal of Functional and Logic Programming. Surya Mantha, Ph.D.: He is a manager in the Communications and Software Services Group of Pittiglio Rabin Todd & McGrath (PRTM), a management consulting firm serving high technology industries. He obtained a bachelors degree in Computer Science and Engineering from the Indian Institute of Technology, Kanpur, an MBA in Finance and Competitive Strategy from the University of Rochester, and a Ph.D. in Computer Science from the University of Utah (1991). His research interests are in the modeling of complex business processes, inter-enterprise application integration, and business strategy. Dr. Mantha has two US patents, and has published over 10 research papers. Prior to joining PRTM, he was a researcher and manager in the Architecture and Document Services Technology Center at Xerox Corporation in Rochester, New York.     

Optimizing join queries in distributed databases

A reduced cover set of the set of full reducer semijoin programs for an acyclic query graph for a distributed database system is given. An algorithm is presented that determines the minimum cost full reducer program. The computational complexity of finding the optimal full reducer for a single relation is of the same order as that of finding the optimal full reducer for all relations. The optimization algorithm is able to handle query graphs where more than one attribute is common between the relations. A method for determining the optimum profitable semijoin program is presented. A low-cost algorithm which determines a near-optimal profitable semijoin program is outlined. This is done by converting a semijoin program into a partial order graph. This graph also allows one to maximize the concurrent processing of the semijoins. It is shown that the minimum response time is given by the largest cost path of the partial order graph. This reducibility is used as a post optimizer for the SSD-1 query optimization algorithm. It is shown that the least upper bound on the length of any profitable semijoin program is N(N-1) for a query graph of N nodes