johnz@latcs1.lat.oz.au (John Zeleznikow) (06/11/91)
Followup-To:johnz@latcs1.lat.oz.au
Keywords: Databases, B-Trees, Spatial Databases, Concurrency
Sender: johnz@latcs1.lat.oz.au (John Zeleznikow)
Organization: Comp Sci, La Trobe Uni, Australia
Distribution: aus
Date: Tue, 11 Jun 1991 09:28:06 GMT
Summary:Database Seminars at La Trobe Unversity
DATABASE RESEARCH LABORATORY
APPLIED COMPUTING RESEARCH INSTITUTE
LATROBE UNIVERSITY
SEMINARS
********************************************************************************
On Thursday 19 June 1991, we will be holding two seminars by:
Betty Salzberg,
Department of Computer Science
Notheastern University
Boston Massachusetts
PRACTICAL SPATIAL DATABASE ACCESS METHODS
Although many solutions to the problem of representing spatial data have
been proposed, most are not practical. They cannot be guaranteed to perform
well with large and arbitrarily distributed data collections. They may not
be easily integrated with concurrency and recovery software already
written for database systems. However, two proposed structures do have some
guarantees, similar to those which have made the B+-tree so successful for
one-dimensional data. These analytic guarantees include worst case space
utilization in index and data pages, a minimal fan-out and exact match search
time bounded by the height of the tree. The two methods are the holey brick
tree (Lomet and Salzberg) and bit interleaving using a B+-tree (Orenstein and
Merrett). Both can also be integrated with concurrency and recovery in the
same way that B+-trees are.
11a.m. - noon
===============================================================================
THE TIME-SPLIT B-TREE
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 characterize the amount of redundancy and the space
utilization for a spectrum of different rates of insertion versus update.
We use a special case of Markov chains called fringe analysis (due to
Eisenbarth, Ziviani, Gonnet, Mehlhorn and Wood) for our analysis.
This is joint work with Dr. David Lomet of Digital Equipment Corporation's
Cambridge (Mass) Research Laboratory. Recent extensions to this work
enabling the Time-Split B-tree to be used as a backup for media recovery
will also be outlined.
2-3 p.m.
===============================================================================
Both Lectures will be held in the Martin Lecture Theatre, Room 141 Martin
Building.
For further information contact John Zeleznikow, johnz@latcs1
Phone: 479-1003 or 479-2598 or 571-5475
N.B. Visitors to LaTrobe University should obtain a visitor's parking permit
from Central Control before parking in the visitors car park.