Algorithms for efficient transaction management and consistent queries in client -server semantic object-oriented parallel databases

Large read-only or read-write transactions with a large read set and a small write set constitute an important class of transactions used in such applications as data mining, data warehousing, statistical applications, and report generators. Such transactions are best supported with optimistic concurrency, because locking of large amounts of data for extended periods of time is not an acceptable solution. The abort rate in regular optimistic concurrency algorithms increases exponentially with the size of the transaction. The algorithm proposed in this dissertation solves this problem by using a new transaction scheduling technique that allows a large transaction to commit safely with significantly greater probability that can exceed several orders of magnitude versus regular optimistic concurrency algorithms. A performance simulation study and a formal proof of serializability and external consistency of the proposed algorithm are also presented.^ This dissertation also proposes a new query optimization technique (lazy queries). Lazy Queries is an adaptive query execution scheme which optimizes itself as the query runs. Lazy queries can be used to find an intersection of sub-queries in a very efficient way, which does not require full execution of large sub-queries nor does it require any statistical knowledge about the data.^ An efficient optimistic concurrency control algorithm used in a massively parallel B-tree with variable-length keys is introduced. B-trees with variable-length keys can be effectively used in a variety of database types. In particular, we show how such a B-tree was used in our implementation of a semantic object-oriented DBMS. The concurrency control algorithm uses semantically safe optimistic virtual "locks" that achieve very fine granularity in conflict detection. This algorithm ensures serializability and external consistency by using logical clocks and backward validation of transactional queries. A formal proof of correctness of the proposed algorithm is also presented. ^

EFFECTS OF A VISUAL HORIZON ON DROSOPHILA MELANOGASTER OBJECT-TRACKING RESPONSES

To navigate effectively in three-dimensional space, flying insects must approximate distances to nearby objects. Humans are able to use an array of cues to guide depth perception in the visual world. However, some of these cues are not available to insects that are constrained by their rigid eyes and relatively small body size. Flying fruit flies can use motion parallax to gauge the distance of nearby objects, but using this cue becomes a less effective strategy as objects become more remote. Humans are able to infer depth across far distances by comparing the angular distance of an object to the horizon. This study tested if flying fruit flies, like humans, use the relative position of the horizon as a depth cue. Fruit flies in tethered flight were stimulated with a virtual environment that displayed vertical bars of varying elevation relative to a horizon, and their tracking responses were recorded. This study showed that tracking responses of the flies were strongly increased by reducing the apparent elevation of the bar against the horizon, indicating that fruit flies may be able to assess the distance of far off objects in the natural world by comparing them against a visual horizon.