Database Systems (TODS)


Search Issue
enter search term and/or author name


ACM Transactions on Database Systems (TODS), Volume 39 Issue 1, January 2014

Classification of annotation semirings over containment of conjunctive queries
Egor V. Kostylev, Juan L. Reutter, András Z. Salamon
Article No.: 1
DOI: 10.1145/2556524

We study the problem of query containment of conjunctive queries over annotated databases. Annotations are typically attached to tuples and represent metadata, such as probability, multiplicity, comments, or provenance. It is usually assumed that...

Indexing for summary queries: Theory and practice
Ke Yi, Lu Wang, Zhewei Wei
Article No.: 2
DOI: 10.1145/2508702

Database queries can be broadly classified into two categories: reporting queries and aggregation queries. The former retrieves a collection of records from the database that match the query's conditions, while the latter returns an aggregate,...

Pufferfish: A framework for mathematical privacy definitions
Daniel Kifer, Ashwin Machanavajjhala
Article No.: 3
DOI: 10.1145/2514689

In this article, we introduce a new and general privacy framework called Pufferfish. The Pufferfish framework can be used to create new privacy definitions that are customized to the needs of a given application. The goal of Pufferfish is to allow...

Strong simulation: Capturing topology in graph pattern matching
Shuai Ma, Yang Cao, Wenfei Fan, Jinpeng Huai, Tianyu Wo
Article No.: 4
DOI: 10.1145/2528937

Graph pattern matching is finding all matches in a data graph for a given pattern graph and is often defined in terms of subgraph isomorphism, an NP-complete problem. To lower its complexity, various extensions of graph simulation have...

Oblivious bounds on the probability of boolean functions
Wolfgang Gatterbauer, Dan Suciu
Article No.: 5
DOI: 10.1145/2532641

This article develops upper and lower bounds for the probability of Boolean functions by treating multiple occurrences of variables as independent and assigning them new individual probabilities. We call this approach dissociation and give...

Mining order-preserving submatrices from probabilistic matrices
Qiong Fang, Wilfred Ng, Jianlin Feng, Yuliang Li
Article No.: 6
DOI: 10.1145/2533712

Order-preserving submatrices (OPSMs) capture consensus trends over columns shared by rows in a data matrix. Mining OPSM patterns discovers important and interesting local correlations in many real applications, such as those involving...

Extending string similarity join to tolerant fuzzy token matching
Jiannan Wang, Guoliang Li, Jianhua Feng
Article No.: 7
DOI: 10.1145/2535628

String similarity join that finds similar string pairs between two string sets is an essential operation in many applications and has attracted significant attention recently in the database community. A significant challenge in similarity join is...

Deletion without rebalancing in multiway search trees
Siddhartha Sen, Robert E. Tarjan
Article No.: 8
DOI: 10.1145/2540068

Some database systems that use a form of B-tree for the underlying data structure do not do rebalancing on deletion. This means that a bad sequence of deletions can create a very unbalanced tree. Yet such databases perform well in practice....

Efficient range searching for categorical and plain data
Yakov Nekrich
Article No.: 9
DOI: 10.1145/2543924

In the orthogonal range-searching problem, we store a set of input points S in a data structure; the answer to a query Q is a piece of information about points in QS, for example, the list of all points in...