The emergence of several new application domains for databases has introduced the need for more efficient complex query handling than databases currently support. These application domains include On-Line Analytical Processing (OLAP), Geographical Information Systems (GIS), and scientific databases. This paper focuses attention on a form of selection query, expressible in SQL but not evaluated efficiently by current DBMSs, with wide applicability in these new problem domains. We introduce a processing strategy for this class of queries, which we call queries by linear constraints (QBLC). This processing strategy can be implemented with a wide variety of multidimensional indexing structures that include the R-Tree variants, the k-d-B-Tree, the Buddy-Tree, and many more. Note that any processing strategy meant for general database use must guarantee that all correct answers are returned. Therefore, all numerical techniques we employ uphold this guarantee. Thus the most distinguishing ch...

This paper presents a number of new techniques for parallelizing geo-spatial database systems and discusses their implementation in the Paradise object-relational database system. The effectiveness of these techniques is demonstrated using a variety of complex geo-spatial queries over a 120 GB global geo-spatial data set.

The focus of the Paradise project (D. DeWitt et al., 194; J. Patel et al., 1997) is to design and implement a scalable database system capable of storing and processing massive data sets such as those produced by NASA's EOSDIS project. The paper describes extensions to Paradise to handle the execution of queries involving collections of satellite images stored on tertiary storage. Several modifications were made to Paradise in order to make the execution of such queries both transparent to the user and efficient. First, the Paradise storage engine (the SHORE storage manager) was extended to support tertiary storage using a log structured organization for tape volumes. Second, the Paradise query processing engine was modified to incorporate a number of novel mechanisms including query pre execution, object abstraction, cache conscious tape scheduling, and query batching. A performance evaluation on a working prototype demonstrates that, together, these techniques can provide a dramatic improvement over more traditional approaches to the management of data stored on tape.

The authors develop and evaluate a number of storage reclamation algorithms for client-server persistent object stores. Experience with a detailed simulation and a prototype implementation in the Exodus storage manager shows that one of the proposed algorithms, the Incremental Partitioned Collector, is complete, maintains transaction semantics, and can be run incrementally and concurrently with client applications. Furthermore, it can significantly improve subsequent system performance by reclustering data, rendering it attractive even for systems that choose not to support automatic storage reclamation.>