Database Systems (TODS)


Search Issue
enter search term and/or author name


ACM Transactions on Database Systems (TODS), Volume 31 Issue 3, September 2006

Introduction to special ICDT section
Thomas Eiter, Leonid Libkin
Pages: 769-769
DOI: 10.1145/1166074.1166075

Expressiveness and complexity of XML Schema
Wim Martens, Frank Neven, Thomas Schwentick, Geert Jan Bex
Pages: 770-813
DOI: 10.1145/1166074.1166076
The common abstraction of XML Schema by unranked regular tree languages is not entirely accurate. To shed some light on the actual expressive power of XML Schema, intuitive semantical characterizations of the Element Declarations Consistent (EDC)...

Theory of nearest neighbors indexability
Uri Shaft, Raghu Ramakrishnan
Pages: 814-838
DOI: 10.1145/1166074.1166077
In this article, we consider whether traditional index structures are effective in processing unstable nearest neighbors workloads. It is known that under broad conditions, nearest neighbors workloads become unstable---distances between data...

PATAXÓ: A framework to allow updates through XML views
Vanessa P. Braganholo, Susan B. Davidson, Carlos A. Heuser
Pages: 839-886
DOI: 10.1145/1166074.1166078
XML has become an important medium for data exchange, and is frequently used as an interface to (i.e., a view of) a relational database. Although a lot of work has been done on querying relational databases through XML views, the problem of updating...

Improving instruction cache performance in OLTP
Stavros Harizopoulos, Anastassia Ailamaki
Pages: 887-920
DOI: 10.1145/1166074.1166079
Instruction-cache misses account for up to 40% of execution time in online transaction processing (OLTP) database workloads. In contrast to data cache misses, instruction misses cannot be overlapped with out-of-order execution. Chip design...

Triggers over nested views of relational data
Feng Shao, Antal Novak, Jayavel Shanmugasundaram
Pages: 921-967
DOI: 10.1145/1166074.1166080
Current systems that publish relational data as nested (XML) views are passive in the sense that they can only respond to user-initiated queries over the nested views. In this article, we propose an active system whereby users can place...

Strategies for query unnesting in XML databases
Norman May, Sven Helmer, Guido Moerkotte
Pages: 968-1013
DOI: 10.1145/1166074.1166081
Queries formulated in a nested way are very common in XQuery. Unfortunately, their evaluation is usually very inefficient when done in a straightforward fashion. We present a framework for handling nested queries that is based on unnesting the...

XSKETCH synopses for XML data graphs
Neoklis Polyzotis, Minos Garofalakis
Pages: 1014-1063
DOI: 10.1145/1166074.1166082
Effective support for XML query languages is becoming increasingly important with the emergence of new applications that access large volumes of XML data. All existing proposals for querying XML (e.g., XQuery) rely on a pattern-specification language...

The role of domain ontologies in database design: An ontology management and conceptual modeling environment
Vijayan Sugumaran, Veda C. Storey
Pages: 1064-1094
DOI: 10.1145/1166074.1166083
Database design is difficult because it involves a database designer understanding an application and translating the design requirements into a conceptual model. However, the designer may have little or no knowledge about the application or task for...

An integrated efficient solution for computing frequent and top-k elements in data streams
Ahmed Metwally, Divyakant Agrawal, Amr El Abbadi
Pages: 1095-1133
DOI: 10.1145/1166074.1166084
We propose an approximate integrated approach for solving both problems of finding the most popular k elements, and finding frequent elements in a data stream coming from a large domain. Our solution is space efficient and reports both...

Probabilistic information retrieval approach for ranking of database query results
Surajit Chaudhuri, Gautam Das, Vagelis Hristidis, Gerhard Weikum
Pages: 1134-1168
DOI: 10.1145/1166074.1166085
We investigate the problem of ranking the answers to a database query when many tuples are returned. In particular, we present methodologies to tackle the problem for conjunctive and range queries, by adapting and applying principles of probabilistic...