ACM DL

Database Systems (TODS)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Database Systems (TODS), Volume 31 Issue 1, March 2006

Optimizing bitmap indices with efficient compression
Kesheng Wu, Ekow J. Otoo, Arie Shoshani
Pages: 1-38
DOI: 10.1145/1132863.1132864
Bitmap indices are efficient for answering queries on low-cardinality attributes. In this article, we present a new compression scheme called Word-Aligned Hybrid (WAH) code that makes compressed bitmap indices efficient even for...

Topological relationships between complex spatial objects
Markus Schneider, Thomas Behr
Pages: 39-81
DOI: 10.1145/1132863.1132865
For a long time topological relationships between spatial objects have been a focus of research in a number of disciplines like artificial intelligence, cognitive science, linguistics, robotics, and spatial reasoning. Especially as predicates they...

B-tree concurrency control and recovery in page-server database systems
Ibrahim Jaluta, Seppo Sippu, Eljas Soisalon-Soininen
Pages: 82-132
DOI: 10.1145/1132863.1132866
We develop new algorithms for the management of transactions in a page-shipping client-server database system in which the physical database is organized as a sparse B-tree index. Our starvation-free fine-grained locking protocol combines adaptive...

Consensus on transaction commit
Jim Gray, Leslie Lamport
Pages: 133-160
DOI: 10.1145/1132863.1132867
The distributed transaction commit problem requires reaching agreement on whether a transaction is committed or aborted. The classic Two-Phase Commit protocol blocks if the coordinator fails. Fault-tolerant consensus algorithms also reach agreement,...

Integrating XML data sources using approximate joins
Sudipto Guha, H. V. Jagadish, Nick Koudas, Divesh Srivastava, Ting Yu
Pages: 161-207
DOI: 10.1145/1132863.1132868
XML is widely recognized as the data interchange standard of tomorrow because of its ability to represent data from a variety of sources. Hence, XML is likely to be the format through which data from multiple sources is integrated. In this article,...

Representing and querying XML with incomplete information
Serge Abiteboul, Luc Segoufin, Victor Vianu
Pages: 208-254
DOI: 10.1145/1132863.1132869
We study the representation and querying of XML with incomplete information. We consider a simple model for XML data and their DTDs, a very simple query language, and a representation system for incomplete information in the spirit of the...

Indexing the past, present, and anticipated future positions of moving objects
Mindaugas Pelanis, Simonas Šaltenis, Christian S. Jensen
Pages: 255-298
DOI: 10.1145/1132863.1132870
With the proliferation of wireless communications and geo-positioning, e-services are envisioned that exploit the positions of a set of continuously moving users to provide context-aware functionality to each individual user. Because advances in disk...

Sequencing XML data and query twigs for fast pattern matching
Praveen Rao, Bongki Moon
Pages: 299-345
DOI: 10.1145/1132863.1132871
We propose a new way of indexing XML documents and processing twig patterns in an XML database. Every XML document in the database can be transformed into a sequence of labels by prüfer's method that constructs a one-to-one correspondence...

Automatic complex schema matching across Web query interfaces: A correlation mining approach
Bin He, Kevin Chen-Chuan Chang
Pages: 346-395
DOI: 10.1145/1132863.1132872
To enable information integration, schema matching is a critical step for discovering semantic correspondences of attributes across heterogeneous sources. While complex matchings are common, because of their far more complex search space, most...

Approximation and streaming algorithms for histogram construction problems
Sudipto Guha, Nick Koudas, Kyuseok Shim
Pages: 396-438
DOI: 10.1145/1132863.1132873
Histograms and related synopsis structures are popular techniques for approximating data distributions. These have been successful in query optimization and a variety of applications, including approximate querying, similarity searching, and data...