Browse Prior Art Database

Efficient Pipelining of Data Base Insertions

IP.com Disclosure Number: IPCOM000122102D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 5 page(s) / 202K

Publishing Venue

IBM

Related People

Nordstrom, ML: AUTHOR [+6]

Abstract

Disclosed is a software algorithm for the fast reuse of deleted entries in a table with the property that upon a system failure, incomplete or "dirty" data will not be reflected in the table.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 29% of the total text.

Efficient Pipelining of Data Base Insertions

      Disclosed is a software algorithm for the fast reuse of
deleted entries in a table with the property that upon a system
failure, incomplete or "dirty" data will not be reflected in the
table.

      FAST, CLEAN REUSE OF DELETED TABLE ENTRIES:  Described is a
method for fast reuse of deleted table entries in a computer system.
The following is assumed:
     1.  The table is stored on DASD and must be read into a volatile
RAM storage for manipulation.  It must be written back to DASD when
manipulations are complete.
      2.  The table consists of fixed length entries, part of which
is data, and part of which is control information. Different tables
may have different entry lengths, but within one table, all entries
are the same length.
      3.  The data portion of an entry is contiguous.
      4.  Entries in the table can be inserted, deleted, or
undeleted.
      5.  The entry length may be shorter than, equal to, or longer
than the sector size of the DASD unit.
      6.  When DASD sectors are written, partial sector writes cannot
occur, even at the time of a failure (or if they can, it can be
detected at the next read via a cyclic redundancy check of some
sort.)
      7.  The entries are allocated in simple contiguous allocation,
      8.  Table entries are normally identified as deleted by a
single bit within the control information.
      9.  Deleted entries can be reused (undeleted) to insert new
data.
     10.  If the computer system should fail, losing the contents of
volatile RAM, all entries must be recovered to a value that existed
at some time prior to the failure within that record.  In particular,
it is unacceptable to recover an entry as non-deleted where the data
portion is comprised of two different data values that occupied the
data portion prior to the failure.  (This is termed "dirty data".)
     11.  It is unacceptable to require every delete or every
undelete operation to wait for DASD I/O synchronously.

      The object of this disclosure is to permit many undelete
operations to be carried out by multiple tasks concurrently in a
multitasking system, and also to prevent dirty data after a failure
of the system.  The next section deals with preventing "dirty data"
from occurring.

      PREVENTING DIRTY DATA:  When an entry is deleted and then
undeleted, it is necessary that if a failure of the system occurs,
the entry is recovered either as deleted, or as the new undeleted
value, not a combination of the previous values.  If the entry length
is less than or equal to the DASD sector size plus one, then a method
known as the Bookend method is used.  If the entry is at least as
long as the sector size plus two, then the Flux method is used.

      THE BOOKEND METHOD:  In the Bookend method, the EntryLength <=
SectorSize+1.  This assures that, at most, two DASD sectors are
needed for...