MEADOW: a middleware for efficient access to multiple geographic databases through OpenGIS wrappers

With the proliferation of various geographic databases on the Internet, we have seen increasing needs for accessing them concurrently and remotely via the Web for high‐level decision making. In this paper, we present Middleware for Efficient Access to Databases through OpenGIS Wrappers (MEADOW), an object‐oriented middleware system we have developed to meet these needs. Current OpenGIS standard addresses many interoperability issues involved in such a global utilization of geographic databases. However, existing Simple Feature specification for CORBA (SFCORBA) implementations of OpenGIS proved to be insufficient for MEADOW. The main problems are the complexity of system development and maintenance, and the inefficiency of accessing remote data servers for processing region queries. We resolved the complexity problem by automatically generating a major portion of the application code, specifically wrappers on database servers and client library modules called transparent access providers. A MEADOW view definition language was developed as a high‐level specification language for this purpose. The efficiency problem was resolved by using a region‐based group prefetching of spatial objects from a geographic region. In addition, we implemented an OID‐based semijoin for efficient global query processing, and a region‐level locking to enhance the level of concurrency among region queries. Copyright © 2002 John Wiley & Sons, Ltd     

Designing access methods for bitemporal databases

By supporting the valid and transaction time dimensions, bitemporal databases represent reality more accurately than conventional databases. The authors examine the issues involved in designing efficient access methods for bitemporal databases, and propose the partial-persistence and the double-tree methodologies. The partial-persistence methodology reduces bitemporal queries to partial persistence problems for which an efficient access method is then designed. The double-tree methodology “sees” each bitemporal data object as consisting of two intervals (a valid-time and a transaction-time interval) and divides objects into two categories according to whether the right endpoint of the transaction time interval is already known. A common characteristic of both methodologies is that they take into account the properties of each time dimension. Their performance is compared with a straightforward approach that “sees” the intervals associated with a bitemporal object as composing one rectangle, which is stored in a single multidimensional access method. Given that some limited additional space is available, the experimental results show that the partial-persistence methodology provides the best overall performance, especially for transaction timeslice queries. For those applications that require ready, off-the-shelf, access methods, the double-tree methodology is a good alternative     

Path dictionary: a new access method for query processing inobject-oriented databases

We present a new access method, called the path dictionary index (PDI) method, for supporting nested queries on object-oriented databases. PDI supports object traversal and associative search, respectively, with a path dictionary and a set of attribute indexes built on top of the path dictionary. We discuss issues on indexing and query processing in object-oriented databases; describe the operations of the new mechanism; develop cost models for its storage overhead and query and update costs; and compare the new mechanism to the path index method. The result shows that the path dictionary index method is significantly better than the path index method over a wide range of parameters in terms of retrieval and update costs and that the storage overhead grows slowly with the number of indexed attributes     

Tree-based access methods for spatial databases: implementation andperformance evaluation

Experiences with the implementation of the cell tree dynamic access method for spatial databases are reported, and the results of an experimental performance comparison with the R-tree of A. Guttman (1984) and with the R-tree of T. Sellis et al. (1987) are given. Cell tree design and implementation are discussed. Although the cell tree often requires more storage space and more CPU time to answer a search query, it usually obtains the results with a lower number of disk accesses than the two rival structures     

Progressive content access to databases of JPEG-compressed images

Progressive content access provides a mode that allows a coarse version of an image being viewed at a lower computing cost and then gradually refined by subsequent resolution enhancement if required. This proves extremely useful when millions of compressed images and video sequences need to be browsed manually or processed in pixel domain, saving the cost and removing the necessity of full decompression. Such a progressive content access algorithm suitable for all discrete-cosine-transform-based (DCT-based) JPEG and MPEG-compressed files is proposed here. First a theoretical model in approximation of cosine function used in inverse discrete cosine transform (IDCT) with various orders is developed. Following that a progressive content access algorithm, which comprehends both the successive approximation and the spectral selection, is proposed. Further analysis and experiments are reported to show that our proposed algorithm saves computational cost in comparison with JPEG full decompression. Extensive experiments also support that the proposed algorithm achieves encouraging peak signal-to-noise ratio (PSNR) values for reconstructed images even with lower order approximation.     

Query languages for sequence databases: termination and complexity

This paper develops a query language for sequence databases, such as genome databases and text databases. Unlike relational data, queries over sequential data can easily produce infinite answer sets since the universe of sequences is infinite, even for a finite alphabet. The challenge is to develop query languages that are both highly expressive and finite. This paper develops such a language as a subset of a logic for string databases called Sequence Datalog. The main idea is to use safe recursion to control and limit unsafe recursion. The main results are the definition of a finite form of recursion, called domain-bounded recursion, and a characterization of its complexity and expressive power. Although finite, the resulting class of programs is highly expressive since its data complexity is complete for the elementary functions     

Object-oriented query language access to relational databases: A semantic framework for query translation

This research investigates and approach to query processing in a multidatabase system that uses an objectoriented model to capture the semantics of other data models. The object-oriented model is used to construct a global schema, defining an integrated view of the different schemas in the environment. The model is also used as a self-describing model to build a meta-database for storing information about the global schema. A unique aspect of this work is that the object-oriented model is used to describe the different data models of the multidatabase environment, thereby extending the meta database with semantic information about the local schemas. With the global and local schemas all represented in an object-oriented form, structural mappings between the global schema and each local schema are then easily supported. An object algebra then provides a query language for expressing global queries, using the structural mappings to translate object algebra queries into SQL queries over local relational schema. The advantage of using an object algebra is that the object-oriented database can be viewed as a blackboard for temporary storage of local data and for establishing relationships between different databases. The object algebra can be used to directly retrieve temporarily-stored data from the object-oriented database or to transparently retrieve data from local sources using the translation process described in this paper.     

Approximate regional sequence matching for genomic databases

Recent advances in computational biology have raised sequence matching requirements that result in new types of sequence database problems. In this work, we introduce an important class of such problems, the approximate regional sequence matching (ARSM) problem. Given a data and a pattern sequence, an ARSM result is an approximate occurrence of a region of the pattern in the data sequence under two conditions. First, the region must contain a predetermined area of the pattern sequence, termed core. Second, the allowable deviation between the region of the pattern and its occurrence in the data sequence depends on the length of the region. We propose the PS-ARSM method that processes holistically the regions of a pattern, taking advantage of their overlaps to efficiently identify the ARSM results. Its performance is evaluated with respect to existing techniques adapted to the ARSM problem.