We have developed log-based recovery for middleware servers that access back-end transaction systems (DBMSs). Transactional consistency is provided between in-memory state stored in middleware servers and persistent state stored in transaction systems. A new logging method called results logging is exploited to ensure coordinated recovery of in-memory state with persistent database state. Results logging incurs low logging overhead for middleware servers and requires little or no modification to existing transaction systems. This makes our approach a practical coordinated recovery technique.

We have developed new methods for log-based recovery for middleware servers which involve thread pooling, private in-memory states for clients, shared in-memory state and message interactions among middleware servers. Due to the observed rareness of crashes, relatively small size of shared state and infrequency of shared state read/write accesses, we are able to reduce the overhead of message logging and shared state logging while maintaining recovery independence. Checkpointing has a very small impact on ongoing activities while still reducing recovery time. Our recovery mechanism enables client private states to be recovered in parallel after a crash. On a commercial middleware server platform, we have implemented a recovery infrastructure prototype, which demonstrates the manageability of system complexity and shows promising performance results.

Many scenarios involve merging of two B-tree indexes, both covering the same key range. Increasing demand for continuous availability and high performance requires that such merging be done online, with minimal interference to normal user transactions. In this paper we present an online B-tree merging method, in which the merging of leaf pages in two B-trees are piggybacked lazily with normal user transactions, thus making the merging I/O efficient and allowing user transactions to access only one index instead of both. The concurrency control mechanism is designed to interfere as little as possible with ongoing user transactions. Merging is made forward recoverable by following a conventional logging protocol, with a few extensions. Should a system failure occur, both indexes being merged can be recovered to a consistent state and no merging work is lost. Experiments and analysis show the I/O savings and the performance, and compare variations on the basic algorithm.

Subsequence matching in time series databases is a useful technique, with applications in pattern matching, prediction, and rule discovery. Internal structure within the time series data can be used to improve these tasks, and provide important insight into the problem domain. This paper introduces our research effort in using the internal structure of a time series directly in the matching process. This idea is applied to the problem domain of respiratory motion data in cancer radiation treatment. We propose a comprehensive solution for analysis, clustering, and online prediction of respiratory motion using subsequence similarity matching. In this system, a motion signal is captured in real time as a data stream, and is analyzed immediately for treatment and also saved in a database for future study. A piecewise linear representation of the signal is generated from a finite state model, and is used as a query for subsequence matching. To ensure that the query subsequence is representative, we introduce the concept of subsequence stability, which can be used to dynamically adjust the query subsequence length. To satisfy the special needs of similarity matching over breathing patterns, a new subsequence similarity measure is introduced. This new measure uses a weighted L1 distance function to capture the relative importance of each source stream, amplitude, frequency, and proximity in time. From the subsequence similarity measure, stream and patient similarity can be defined, which are then used for offline and online applications. The matching results are analyzed and applied for motion prediction and correlation discovery. While our system has been customized for use in radiation therapy, our approach to time series modeling is general enough for application domains with structured time series data.

Summary form only given. Inventory snapshots tell us what was on the shelves of a store at a given moment in time. In this article, an indexing structure that could efficiently capture the inventory at any past time was outlined, the time splitting data structure. It keeps both storage costs and snapshot query costs low.

Subsequence similarity matching in time series databases is an important research area for many applications. This paper presents a new approximate approach for automatic online subsequence similarity matching over massive data streams. With a simultaneous on-line segmentation and pruning algorithm over the incoming stream, the resulting piecewise linear representation of the data stream features high sensitivity and accuracy. The similarity definition is based on a permutation followed by a metric distance function, which provides the similarity search with flexibility, sensitivity and scalability. Also, the metric-based indexing methods can be applied for speed-up. To reduce the system burden, the event-driven similarity search is performed only when there is a potential event. The query sequence is the most recent subsequence of piecewise data representation of the incoming stream which is automatically generated by the system. The retrieved results can be analyzed in different ways according to the requirements of specific applications. This paper discusses an application for future data movement prediction based on statistical information. Experiments on real stock data are performed. The correctness of trend predictions is used to evaluate the performance of subsequence similarity matching.

The CenSSIS image database is a scientific database that enables effective data management and collaboration to accelerate fundamental research. This paper describes the design and use of a state-of-the-art relational image database management system, accessible through a standard Web-browser interface. The application utilizes a robust security architecture and is designed for efficient data submission. Our database query engine provides complex query capabilities to facilitate fast and efficient data retrieval. The system offers a highly extensible metadata schema, with the option of storing data within a hierarchical format.

Describes a new method for dynamically clustering hierarchical data which maintains good clustering within disk pages in the presence of insertions and deletions. This simple but effective method, which we call Enc, encodes the insertion order of children with respect to their parents and concatenates the insertion numbers to form a compact key for the data. This compact key is stored only in the indexing structure and does not affect the logical database schema. Experimental results show that our Enc method is very efficient for hierarchical queries and performs reasonably well for random access queries.

DSDT is a proposed method for creating durable scripts which contain short ACID transactions as components. Workflow scripts are an example. The context of the script is made durable by writing a log record whenever an event occurs which cannot be replayed. Log checkpoints are used to minimize the recovery time. DSDT can be written in stand-alone mode, communicating with a DBMS by transactional remote procedure calls and maintaining its own logging system, or it can be made part of a DBMS by modifying the DBMS transaction manager source code. DSDT provides a panic button (signal-exit) and the ability to specify what action should be taken on restart after a system failure. The programmer can also specify actions, such as "compensation" transactions, to be taken after another signal (signal-cancel) arrives. DSDT enables most extended transaction models to be expressed in scripts modulo the guarantees of compensation. Recovery after system failure is shown to be correct.

In this paper, we present an efficient method to do online reorganization of sparsely-populated B+-trees. It reorganizes the leaves first, compacting in short operations groups of leaves with the same parent. After compacting, optionally, the new leaves may swap locations or be moved into empty pages so that they are in key order on the disk. After the leaves are reorganized, the method shrinks the tree by making a copy of the upper part of the tree while leaving the leaves in place. A new concurrency method is introduced so that only a minimum number of pages are locked during reorganization. During leaf reorganization, Forward Recovery is used to save all work already done while maintaining consistency after system crashes. A heuristic algorithm is developed to reduce the number of swaps needed during leaf reorganization, so that better concurrency and easier recovery can be achieved. A detailed description of switching from the old B+-tree to the new B+-tree is described for the first time.

Providing high concurrency in B+-trees has been studied extensively. But few efforts have been documented for combining concurrency methods with a recovery scheme that preserves well-formed trees across system crashes. We describe an approach for this that works for a class of index trees that is a generalization of the Blink-tree. A major feature of our method is that it works with a range of different recovery methods. It achieves this by decomposing structure changes in an index tree into a sequence of atomic actions, each one leaving the tree well-formed and each working on a separate level of the tree. All atomic actions on levels of the tree above the leaf level are independent of database transactions, and so are of short duration.

The Time-Split B-tree is an integrated index structure for a versioned timestamped database. It gradually migrates data from a current database to an historical database, records migrating when nodes split. Records valid at the split time are placed in both an historical node and a current node. This implies some redundancy. Using both analysis and simulation, we characterise the amount of redundancy, the space utilization, and the record addition (insert or update) performance for a spectrum of different rates of insertion versus update. Three splitting policies are studied which alter the conditions under which either time splits or key space splits are performed.

External single-input single-output sorts can use multiple processors each with a large tournament replacement-selection in memory, and each with private disks to sort an input stream in linear elapsed time. Of course, increased numbers of processors, memories, and disks are required as the input file size grows. This paper analyzes the algorithm and reports the performance of an implementation.

A new multiattribute index structure called the hB-tree is introduced. It is derived from the K-D-B-tree of Robinson [15] but has additional desirable properties. The hB-tree internode search and growth processes are precisely analogous to the corresponding processes in B-trees [1]. The intranode processes are unique. A k-d tree is used as the structure within nodes for very efficient searching. Node splitting requires that this k-d tree be split. This produces nodes which no longer represent brick-like regions in k-space, but that can be characterized as holey bricks, bricks in which subregions have been extracted. We present results that guarantee hB-tree users decent storage utilization, reasonable size index terms, and good search and insert performance. These results guarantee that the hB-tree copes well with arbitrary distributions of keys.

A multiattribute index structure called the hB-tree is introduced. The hB-tree internode search and growth processes are precisely analogous to the corresponding processes in B-trees. The intranode processes are unique. A k-d tree is used as the structure within nodes for very efficient searching. Node splitting requires that this k-d tree be split. This produces nodes which do not represent brick-like regions in k-space but that can be characterized as holey bricks, i.e. bricks in which subregions have been extracted. Results are presented that guarantee hB-tree users decent storage utilization, reasonable-size index terms, and good search and insert performance regardless of key distribution.>

We present an access method designed to provide a single integrated index structure for a versioned timestamped database with a non-deletion policy. Historical data (superceded versions) is stored separately from current data. Our access method is called the Time-Split B-tree. It is an index structure based on Malcolm Easton's Write Once B-tree.

We modify J. G. Fletcher's checksum algorithm (easily implemented by software) to place two check octets in an arbitrary place in a data unit, rather than at the end. This is useful if one wants the checksum information in the header of a data unit.