Database Systems (TODS)


Search Issue
enter search term and/or author name


ACM Transactions on Database Systems (TODS) - Invited Articles Issue, SIGMOD 2013, PODS 2013 and ICDT 2013, Volume 39 Issue 4, December 2014

Section: Invited Articles Issue

Foreword to Invited Articles Issue
Christian S. Jensen
Article No.: 26
DOI: 10.1145/2697050

Section: Invited Articles Issue

I/O-Efficient Algorithms on Triangle Listing and Counting
Xiaocheng Hu, Yufei Tao, Chin-Wan Chung
Article No.: 27
DOI: 10.1145/2691190.2691193

This article studies I/O-efficient algorithms for the triangle listing problem and the triangle counting problem, whose solutions are basic operators in dealing with many other graph problems. In the former problem, given an...

Discovering XSD Keys from XML Data
Marcelo Arenas, Jonny Daenen, Frank Neven, Martin Ugarte, Jan Van Den Bussche, Stijn Vansummeren
Article No.: 28
DOI: 10.1145/2638547

A great deal of research into the learning of schemas from XML data has been conducted in recent years to enable the automatic discovery of XML schemas from XML documents when no schema or only a low-quality one is available. Unfortunately, and in...

A Scalable Lock Manager for Multicores
Hyungsoo Jung, Hyuck Han, Alan Fekete, Gernot Heiser, Heon Y. Yeom
Article No.: 29
DOI: 10.1145/2691190.2691192

Modern implementations of DBMS software are intended to take advantage of high core counts that are becoming common in high-end servers. However, we have observed that several database platforms, including MySQL, Shore-MT, and a commercial system,...

Lightweight Query Authentication on Streams
Stavros Papadopoulos, Graham Cormode, Antonios Deligiannakis, Minos Garofalakis
Article No.: 30
DOI: 10.1145/2656336

We consider a stream outsourcing setting, where a data owner delegates the management of a set of disjoint data streams to an untrusted server. The owner authenticates his streams via signatures. The server processes continuous queries on...

Section: Invited Articles Issue

Naïve Evaluation of Queries over Incomplete Databases
Amélie Gheerbrant, Leonid Libkin, Cristina Sirangelo
Article No.: 31
DOI: 10.1145/2691190.2691194

The term naïve evaluation refers to evaluating queries over incomplete databases as if nulls were usual data values, that is, to using the standard database query evaluation engine. Since the semantics of query answering over...

The Complexity of Mining Maximal Frequent Subgraphs
Benny Kimelfeld, Phokion G. Kolaitis
Article No.: 32
DOI: 10.1145/2629550

A frequent subgraph of a given collection of graphs is a graph that is isomorphic to a subgraph of at least as many graphs in the collection as a given threshold. Frequent subgraphs generalize frequent itemsets and arise in various...

Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP
Meghyn Bienvenu, Balder Ten Cate, Carsten Lutz, Frank Wolter
Article No.: 33
DOI: 10.1145/2661643

Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database...

Section: Invited Articles Issue

A Theory of Pricing Private Data
Chao Li, Daniel Yang Li, Gerome Miklau, Dan Suciu
Article No.: 34
DOI: 10.1145/2691190.2691191

Personal data has value to both its owner and to institutions who would like to analyze it. Privacy mechanisms protect the owner's data while releasing to analysts noisy versions of aggregate query results. But such strict protections of the...

Top-k and Clustering with Noisy Comparisons
Susan Davidson, Sanjeev Khanna, Tova Milo, Sudeepa Roy
Article No.: 35
DOI: 10.1145/2684066

We study the problems of max/top-k and clustering when the comparison operations may be performed by oracles whose answer may be erroneous. Comparisons may either be of type or of value: given two data elements, the answer to...