ACM DL

Database Systems (TODS)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Database Systems (TODS) - Special Issue: SIGMOD/PODS 2004, Volume 30 Issue 4, December 2005

Foreword
Dan Suciu, Gerhard Weikum
Pages: 887-887
DOI: 10.1145/1114244.1114245

Wavelet synopses for general error metrics
Minos Garofalakis, Amit Kumar
Pages: 888-928
DOI: 10.1145/1114244.1114246
Several studies have demonstrated the effectiveness of the wavelet decomposition as a tool for reducing large amounts of data down to compact wavelet synopses that can be used to obtain fast, accurate approximate query answers. Conventional...

Conditional XPath
Maarten Marx
Pages: 929-959
DOI: 10.1145/1114244.1114247
XPath 1.0 is a variable free language designed to specify paths between nodes in XML documents. Such paths can alternatively be specified in first-order logic. The logical abstraction of XPath 1.0, usually called Navigational or Core XPath, is not...

Graph indexing based on discriminative frequent structure analysis
Xifeng Yan, Philip S. Yu, Jiawei Han
Pages: 960-993
DOI: 10.1145/1114244.1114248
Graphs have become increasingly important in modelling complicated structures and schemaless data such as chemical compounds, proteins, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database...

Composing schema mappings: Second-order dependencies to the rescue
Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, Wang-Chiew Tan
Pages: 994-1055
DOI: 10.1145/1114244.1114249
A schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). A fundamental problem is composing schema mappings:...

Optimization of query streams using semantic prefetching
Ivan T. Bowman, Kenneth Salem
Pages: 1056-1101
DOI: 10.1145/1114244.1114250
Streams of relational queries submitted by client applications to database servers contain patterns that can be used to predict future requests. We present the Scalpel system, which detects these patterns and optimizes request streams using...

Synopses for query optimization: A space-complexity perspective
Raghav Kaushik, Jeffrey F. Naughton, Raghu Ramakrishnan, Venkatesan T. Chakravarthy
Pages: 1102-1127
DOI: 10.1145/1114244.1114251
Database systems use precomputed synopses of data to estimate the cost of alternative plans during query optimization. A number of alternative synopsis structures have been proposed, but histograms are by far the most commonly used. While histograms...