Database Systems (TODS)


Search Issue
enter search term and/or author name


ACM Transactions on Database Systems (TODS), Volume 37 Issue 4, December 2012

Z. Meral Özsoyoǧlu
Article No.: 23
DOI: 10.1145/2389241.2389242

Maximizing Conjunctive Views in Deletion Propagation
Benny Kimelfeld, Jan Vondrák, Ryan Williams
Article No.: 24
DOI: 10.1145/2389241.2389243

In deletion propagation, tuples from the database are deleted in order to reflect the deletion of a tuple from the view. Such an operation may result in the (often necessary) deletion of additional tuples from the view, besides the intentionally...

Determining the Currency of Data
Wenfei Fan, Floris Geerts, Jef Wijsen
Article No.: 25
DOI: 10.1145/2389241.2389244

Data in real-life databases become obsolete rapidly. One often finds that multiple values of the same entity reside in a database. While all of these values were once correct, most of them may have become stale and inaccurate. Worse still, the...

Worst-Case I/O-Efficient Skyline Algorithms
Cheng Sheng, Yufei Tao
Article No.: 26
DOI: 10.1145/2389241.2389245

We consider the skyline problem (aka the maxima problem), which has been extensively studied in the database community. The input is a set P of d-dimensional points. A point dominates another if the coordinate of...

SCALLA: A Platform for Scalable One-Pass Analytics Using MapReduce
Boduo Li, Edward Mazur, Yanlei Diao, Andrew McGregor, Prashant Shenoy
Article No.: 27
DOI: 10.1145/2389241.2389246

Today’s one-pass analytics applications tend to be data-intensive in nature and require the ability to process high volumes of data efficiently. MapReduce is a popular programming model for processing large datasets using a cluster of...

WHAM: A High-Throughput Sequence Alignment Method
Yinan Li, Jignesh M. Patel, Allison Terrell
Article No.: 28
DOI: 10.1145/2389241.2389247

Over the last decade, the cost of producing genomic sequences has dropped dramatically due to the current so-called next-generation sequencing methods. However, these next-generation sequencing methods are critically dependent on fast and...

Finding Alternative Shortest Paths in Spatial Networks
Kexin Xie, Ke Deng, Shuo Shang, Xiaofang Zhou, Kai Zheng
Article No.: 29
DOI: 10.1145/2389241.2389248

Shortest path query is one of the most fundamental queries in spatial network databases. There exist algorithms that can process shortest path queries in real time. However, many complex applications require more than just the calculation of a...

On Provenance Minimization
Yael Amsterdamer, Daniel Deutch, Tova Milo, Val Tannen
Article No.: 30
DOI: 10.1145/2389241.2389249

Provenance information has been proved to be very effective in capturing the computational process performed by queries, and has been used extensively as the input to many advanced data management tools (e.g., view maintenance, trust assessment,...

Expressive Languages for Path Queries over Graph-Structured Data
Pablo Barceló, Leonid Libkin, Anthony W. Lin, Peter T. Wood
Article No.: 31
DOI: 10.1145/2389241.2389250

For many problems arising in the setting of graph querying (such as finding semantic associations in RDF graphs, exact and approximate pattern matching, sequence alignment, etc.), the power of standard languages such as the widely studied...

Partial Evaluation for Distributed XPath Query Processing and Beyond
Gao Cong, Wenfei Fan, Anastasios Kementsietsidis, Jianzhong Li, Xianmin Liu
Article No.: 32
DOI: 10.1145/2389241.2389251

This article proposes algorithms for evaluating XPath queries over an XML tree that is partitioned horizontally and vertically, and is distributed across a number of sites. The key idea is based on partial evaluation: it is to send the whole query...