ACM Transactions on Database Systems

Công bố khoa học tiêu biểu

* Dữ liệu chỉ mang tính chất tham khảo

Sắp xếp:  
A linear-time probabilistic counting algorithm for database applications
ACM Transactions on Database Systems - Tập 15 Số 2 - Trang 208-229 - 1990
Kyu-Young Whang, Brad T. Vander-Zanden, Howard M. Taylor
We present a probabilistic algorithm for counting the number of unique values in the presence of duplicates. This algorithm has O ( q ) time complexity, where q is the number of values including duplicates, and produces an estimation with an arbitrary accuracy prespecified by the user using only a small amount of space. Traditionally, accurate counts of unique values were obtained by sorting, whic... hiện toàn bộ
Efficient Sorting, Duplicate Removal, Grouping, and Aggregation
ACM Transactions on Database Systems - Tập 47 Số 4 - Trang 1-35 - 2022
Thanh Do, Goetz Graefe, Jeffrey F. Naughton
Database query processing requires algorithms for duplicate removal, grouping, and aggregation. Three algorithms exist: in-stream aggregation is most efficient by far but requires sorted input; sort-based aggregation relies on external merge sort; and hash aggregation relies on an in-memory hash table plus hash partitioning to temporary storage. Cost-based query optimization chooses which algorith... hiện toàn bộ
Join indices
ACM Transactions on Database Systems - Tập 12 Số 2 - Trang 218-246 - 1987
Patrick Valduriez
In new application areas of relational database systems, such as artificial intelligence, the join operator is used more extensively than in conventional applications. In this paper, we propose a simple data structure, called a join index, for improving the performance of joins in the context of complex queries. For most of the joins, updates to join indices incur very little overhead. Some proper... hiện toàn bộ
Implications of certain assumptions in database performance evauation
ACM Transactions on Database Systems - Tập 9 Số 2 - Trang 163-186 - 1984
Stavros Christodoulakis
The assumptions of uniformity and independence of attribute values in a file, uniformity of queries, constant number of records per block, and random placement of qualifying records among the blocks of a file are frequently used in database performance evaluation studies. In this paper we show that these assumptions often result in predicting only an upper bound of the expected system cost. We the... hiện toàn bộ
Optimizing object queries using an effective calculus
ACM Transactions on Database Systems - Tập 25 Số 4 - Trang 457-516 - 2000
Leonidas Fegaras, David Maier
Object-oriented databases (OODBs) provide powerful data abstractions and modeling facilities, but they generally lack a suitable framework for query processing and optimization. The development of an effective query optimizer is one of the key factors for OODB systems to successfully compete with relational systems, as well as to meet the performance requirements of many nontraditional application... hiện toàn bộ
A foundation for representing and querying moving objects
ACM Transactions on Database Systems - Tập 25 Số 1 - Trang 1-42 - 2000
Ralf Hartmut Güting, Michael H. Böhlen, Martin Erwig, Christian S. Jensen, Nikos A. Lorentzos, Markus Schneider, Michalis Vazirgiannis
Spatio-temporal databases deal with geometries changing over time. The goal of our work is to provide a DBMS data model and query language capable of handling such time-dependent geometries, including those changing continuously that describe moving objects . Two fundamental abstractions are moving point and moving region , describing objects for which only the time-dependent position, or position... hiện toàn bộ
A homogeneous relational model and query languages for temporal databases
ACM Transactions on Database Systems - Tập 13 Số 4 - Trang 418-448 - 1988
Shashi K. Gadia
In a temporal database, time values are associated with data item to indicate their periods of validity. We propose a model for temporal databases within the framework of the classical database theory. Our model is realized as a temporal parameterization of static relations. We do not impose any restrictions upon the schemes of temporal relations. The classical concepts of normal forms and depende... hiện toàn bộ
Join and Semijoin Algorithms for a Multiprocessor Database Machine
ACM Transactions on Database Systems - Tập 9 Số 1 - Trang 133-161 - 1984
Patrick Valduriez, Georges Gardarin
This paper presents and analyzes algorithms for computing joins and semijoins of relations in a multiprocessor database machine. First, a model of the multiprocessor architecture is described, incorporating parameters defining I/O, CPU, and message transmission times that permit calculation of the execution times of these algorithms. Then, three join algorithms are presented and compared. It is sh... hiện toàn bộ
Set query optimization in distributed database systems
ACM Transactions on Database Systems - Tập 11 Số 3 - Trang 265-293 - 1986
Bezalel Gavish, Arie Segev
This paper addresses the problem of optimizing queries that involve set operations (set queries) in a distributed relational database system. A particular emphasis is put on the optimization of such queries in horizontally partitioned database systems. A mathematical programming model of the set query problem is developed and its NP-completeness is proved. Solution procedures are proposed and comp... hiện toàn bộ
Query processing in a system for distributed databases (SDD-1)
ACM Transactions on Database Systems - Tập 6 Số 4 - Trang 602-625 - 1981
Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie
This paper describes the techniques used to optimize relational queries in the SDD-1 distributed database system. Queries are submitted to SDD-1 in a high-level procedural language called Datalanguage. Optimization begins by translating each Datalanguage query into a relational calculus form called an envelope , which is essentially an aggregate-free QUEL query. This paper is primarily concerned w... hiện toàn bộ
Tổng số: 24   
  • 1
  • 2
  • 3