Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-02-03
2003-10-07
Mizrahi, Diane D. (Department: 2184)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06631385
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a recovery method for a high-dimensional index structure; and more particularly, to a recovery method for a high-dimensional index structure employing a reinsert operation, and also relates to a recording medium on which a program for carrying out the above method is recorded, the program being readable by a computer.
DESCRIPTION OF THE PRIOR ART
In the conventional recovery method for a high dimensional index structure, basically, a page oriented redo and a logical undo are carried out based on the WAL (write ahead logging) protocol. The logical undo refers to a method in which when carrying out the undo operation, the index structure is opened and traversed from the root. Thus the node is found out, and then, the undo operation is carried out at the found node. In the page-oriented redo, the index structure is not opened, and the redo operation is carried out at the node which is recorded in the log record.
In a recovery technique which is shown in the R
link
-tree, there are separately handled: a content modification operation which carry out an insert/delete of an entry to/from a leaf node; and a tree structure modification operation(SMO) which carry out a split of node, a deletion of node, or a minimum bounding region(MBR) alteration of non-leaf node. The modification of the leaf node due to the entry insertion or deletion is undone if the transaction is rolled back, while it is redone if the transaction is completed.
On the other hand, the SMO is treated as an Atomic Action which is a separate recoverable unit, thereby excluding the dependencies which occur when the recovery is performed among the transactions. And even if the transactions are not completed, other transactions are made to see this alteration. That is, the pages which have participated in the SMO are not required to be locked until the transaction is completed.
Researches on the framework by which the index structure based on GIST (generalized search tree) can be easily developed are being carried out. In this method also, a concurrency control technique and a recovery technique are proposed. The recovery technique presented here is also based on the WAL protocol, and is also based on the page-oriented redo and the logical undo.
Meanwhile, the modification operation is divided into two: a SMO including the node deletion and the modification of the MBR; and a simple modification operation.
However, unlike the method of the R
link
-tree, the SMO is handled in the form of NTA (nested top action). The greatest difference lies in the following fact. That is, the SMO in the R
link
-tree includes only the split of the leaf
on-leaf nodes. In the GIST, however, the SMO includes the other splits which can occur when the split contents of the leaf
on-leaf nodes are reflected on the upper node as well as the split of the leaf
on-leaf nodes.
In the above described recovery method for the conventional high dimensional index structure, the page-oriented redo and the logical undo are carried out based on the WAL protocol. The modification operations that occur in the index structure are classified into SMOs and general modification operations. The SMOs are handled as a NTA or an Atomic Action. If the SMO is completed, then other transactions are made to see this alteration, thereby improving the simultaneity. However, these recovery techniques do not present any method by which the reinsert operation can be carried out in an efficient manner. If this recovery method is applied to each of the reinsert operations, a lot of time is required to recover from the rollback of operation or the system failure.
SUMMARY OF THE INVENTION
Therefore, it is an object of the present invention to provide a recovery method for a high-dimensional index structure employing a reinsert operation which is based on ARIES (algorithm for recovery and isolation exploiting semantics) and a page oriented redo and a logical undo, and also to provide a recording medium on which a program for carrying out the above method is recorded, the program being readable by a computer.
In accordance with an aspect of the present invention, there is provided a method for recovering a high-dimensional index structure employing a reinsert operation, comprising the steps of: a) inserting an entry into a node, adjusting a MBR, processing an overflow, and storing a log record; and b) recovering the log record thus stored.
In accordance with another aspect of the present invention, there is provided a computer readable and executable recording medium having a program for performing a method for recovering a high-dimensional index structure, the method comprising the steps of: a) inserting an entry into a node, adjusting a minimum bounding region, processing an overflow, and storing a log record; and b) recovering the log record thus stored.
REFERENCES:
patent: 5717921 (1998-02-01), Lomet et al.
patent: 5758356 (1998-05-01), Hara et al.
patent: 5799300 (1998-08-01), Agrawal et al.
patent: 5956705 (1999-09-01), Stevens et al.
patent: 6026406 (2000-02-01), Huang et al.
patent: 6282546 (2001-08-01), Gleichauf et al.
patent: 6374235 (2002-04-01), Chen et al.
patent: 6397204 (2002-05-01), Liu et al.
Kornacker, et al.;High-Concurrency Locking in R-Trees; 1995; Proceedings of the 21stVLDB Conference, Zurich, Switzerland.
Kornacker, et al;Concurrency and Recovery in Generalized Search Trees.
Kim June
Kim Myung Joon
Lee Hun Soon
Lee Jang Sun
Oh Gil Rok
Electronics and Telecommunications Research Institute
Jacobson & Holman PLLC
LandOfFree
Efficient recovery method for high-dimensional index... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient recovery method for high-dimensional index..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient recovery method for high-dimensional index... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3131889