Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-05-23
2003-11-18
Coby, Frantz (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06651073
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data recovery in a database management system after an abnormal system termination and, more specifically, to a database management system recovery method and apparatus that does not use data recovery logging.
BACKGROUND OF THE INVENTION
Databases store data in a variety of manners depending on the internal organization. For example, a relational database system typically stores data in tables. The tables are comprised of rows, each of which contains a record. The record, in turn, contains fields and the fields contain the actual related data values for a data “object.” Each table may also be associated with one or more indexes, which provide rapid access to the rows in an order determined by the index and based on key data values contained in selected fields in each row. As an example, a row might be associated with each employee of an organization and contain fields that hold such information as the employee name, an identification number, and telephone numbers. One index might order the rows numerically by employee identification number, while another index might order the rows alphabetically by employee name.
Such a database conventionally includes methods that insert and delete rows and update the information in a row. When changes are made to the rows, any database indexes associated with the table may also need to be updated in order to keep the indexes synchronized with the tables. The rows in each table are mapped to a plurality of physical pages on the disk to simplify data manipulation. Such an arrangement is illustrated in FIG.
1
.
In
FIG. 1
, table
100
, which illustratively consists of rows
112
,
114
,
116
, and
118
, is mapped to a chain of pages which pages
120
,
138
, and
132
are shown. In the table illustrated, each row consists of five separate fields. For example, row
112
consists of fields
102
,
104
,
106
,
108
and
110
. The fields in each of rows
112
,
114
,
116
and
118
are mapped illustratively to page
138
, which can contain data for more than one row. For example, field
102
maps to location
126
in page
138
. Fields
104
maps to location
128
. Field
106
maps to location
130
. In a similar manner field
108
maps to location
124
and field
110
maps to location
134
. The fields in the next row
114
are mapped directly after the fields in row
112
. For example, field
111
is illustrated which maps to page location
136
. When the page is completely filled with data, field information is mapped to the next page in the page chain. The pages are chained together by means of page pointers. For example, page pointer
122
links pages
120
and
138
, whereas page pointer
140
links pages
138
and
132
. All of the pages used to store the data in table
100
are linked together in a similar manner in a page chain.
The data pages are normally kept in a page buffer pool located in system memory. In order to make such a database system persistent or “durable”, the data pages must be written to an underlying non-volatile storage system, such as disk storage. This storage operation takes place on a page level so that when a modification is made to data on a page the entire page is stored in the persistent storage. Each page could be copied to the persistent storage as soon as data on the page was modified. However, this immediate copying greatly slows the system operation since persistent storage is generally much slower than RAM memory. Alternatively, the information in modified pages in the buffer pool can be copied or “flushed” to the disk storage at intervals. For example, the information could be flushed periodically or when the number of changed pages in the buffer pool reaches some predetermined threshold. During this disk flushing operation, the data modifications are performed “in place” so that the old data is either overwritten or deleted from the disk and lost.
Since the data is lost during the modification process, in order to ensure data integrity in the case of a system failure, or crash, the actions performed on the database are grouped into a series of “transactions”. Each transaction is “atomic” which means that either all actions in the transaction are performed or none are performed. The atomic property of a transaction ensures that the transaction can be aborted or “rolled back” so that all of the actions that constitute the transaction can be undone. Database transactions commonly have a “commit” point at which time it can be guaranteed that all actions which comprise the transaction will complete properly. If the transaction does not reach the commit point, then it will be rolled back so that the system can return to its state prior to the initiation of the transaction. Consequently, if there is a system termination or crash prior to the commit point, the entire transaction can be rolled back.
The use of a buffer pool complicates transaction processing because although a transaction has committed, system operation could terminate after a page has been modified, but before the modified page is flushed to disk. In order to prevent data loss caused by such a system interruption, a logging system is used to permit data recovery. The logging system records redo and undo information for each data modification in a special file called a “recovery log” that is kept in non-volatile storage.
The recovery log consists of an ordered list of redo/undo actions and contains information such as a transaction ID, a page ID, an offset length and the old and new data constituting the update. Additional control information is often included to facilitate the logging operation. This control data includes a transaction table that includes one record per active transaction that contains the transaction state (for example, running, committed or aborted.) The control information also includes a dirty page table that contains one entry for each page in the buffer pool that has been modified.
In order to ensure both atomicity and persistence for each transaction, a “write ahead” logging protocol is used. According to this protocol a log record is written for an update before the corresponding modified data page is written to disk. In addition, all log records are written for a transaction before the transaction is committed.
In addition to the recovery logging of data update information, recovery logging is also performed during storage space management procedures that involve allocation and deallocation of data pages for each database row. For example, a set of pages is commonly maintained by the database system to handle storage space allocation and deallocation for each table. These pages are referred to as a space map, free space, a free space map or unused space. The term “space map” will be used herein to refer to all such space allocation areas and structures. In general, each space-map page manages space allocation for a range of data pages and contains status information that indicates whether a particular data page on disk storage has been used. When a new data row is inserted into a table, the space-map pages associated with that table are examined and updated to allocate space for a page, or the part of a page, which holds the row. A recovery log entry is written for each change made to the space-map pages. These recovery logs can be used to free the allocated space if a transaction roll back occurs before the transaction has been committed.
The recovery logs are used to restart processing if system operation is abnormally terminated, for example, due to a power failure. In a recovery operation, redo information in the recovery log is used to reconstruct all transactions at the time of the failure. The undo information is used to undo transactions that did not commit prior to the termination.
The conventional database system is somewhat complicated in a distributed database system such as shown in
FIG. 2
which illustrates, in schematic form, an example of such a distributed database system. The system consists of four database management systems
Lyle Robert W.
Teng James Z.
Yothers Jay A.
Coby Frantz
International Business Machines - Corporation
Kudirka & Jobse LLP
LandOfFree
Method and apparatus for insuring database data integrity... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for insuring database data integrity..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for insuring database data integrity... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3130383