Source: http://www.google.com/patents/US7647334?dq=U.S.+Patent+
Timestamp: 2017-02-25 19:29:56
Document Index: 243594666

Matched Legal Cases: ['art 210', 'art 220', 'art 210', 'art 210', 'art 220', 'art 210', 'art 210', 'art 220', 'art 210', 'art 210', 'art 210', 'art 96', 'art 98', 'art 108', 'art 110', 'art 108', 'art 110', 'art 108', 'art 110']

Patent US7647334 - Method for checking index consistency in database - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsThe present invention provides a system, a method, and a program for checking index consistency online in a database that includes a main database storing a plurality of data segments and an index database storing a plurality of index segments. A system according to an aspect of the present invention...http://www.google.com/patents/US7647334?utm_source=gb-gplus-sharePatent US7647334 - Method for checking index consistency in databaseAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7647334 B2Publication typeGrantApplication numberUS 12/180,492Publication dateJan 12, 2010Filing dateJul 25, 2008Priority dateDec 28, 2006Fee statusLapsedAlso published asUS7650354, US20080162585, US20080313218Publication number12180492, 180492, US 7647334 B2, US 7647334B2, US-B2-7647334, US7647334 B2, US7647334B2InventorsToshikazu TakahashiOriginal AssigneeInternational Business Machines CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (35), Non-Patent Citations (8), Classifications (6), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetMethod for checking index consistency in database
US 7647334 B2Abstract
1. A method for checking index consistency in a database that includes a main database storing a plurality of data segments and an index database storing a plurality of index segments, comprising the steps of:
creating a pointer record that contains pointer values and key values by sequentially reading out the index segments from the index database, by a record creating unit in a computer;
creating a segment record that contains storage addresses and search field values of index target segments pointed by the pointer values of the index segments by sequentially reading out the data segments from the main database, by the record creating unit;
setting scan points that indicate how much the creation of the pointer record and the segment record proceeds by a scan point setting unit in the computer, respectively;
writing, in response to the update of the index segment in the index database or the update of the index target segment in the main database, an update log of the updated segment by an update log writing unit in the computer, on condition that the updated segment is located at a point that precedes the scan point set by the scan point setting unit, while the record creation unit creates the pointer record or a segment record;
modifying the pointer record and the segment record by a record modifying unit in the computer on the basis of the update log after the record creation unit creates the pointer record or a the segment record; and
verifying index consistency by comparing record entries of the modified pointer record with corresponding record entries of the modified segment record, a consistency verifying unit in the computer.
2. A program for checking index consistency in a database that includes a main database storing a plurality of data segments and an index database storing a plurality of index segments, causing a computer to execute the steps of the method according to claim 1.
Hitherto, a check of database consistency has been performed by comparing a storage address of each segment contained in a database with each pointer value contained in the database. Such a consistency check is implemented and employed in, for example, a database management system developed by the assignee of this application (see, IMS High Performance Pointer Checker User's Guide, which may be viewed on the World Wide Web page at URL publibfi.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/fabp1b10/CCONTENTS.
FIG. 3 shows an example of a specific configuration of the main database 22. The main database 22 stores a plurality of data segments represented by data segments 200-1 to 200-3. In the illustrated example, the data segment 200-1 serves as a root segment, and can be designated with a root anchor point (RAP). The data segment 200-1 contains a prefix part 210-1 and a data part 220-1. In addition, a storage address of the data segment 200-1 is 1000. Here, the storage address means, for example, a location of a starting address (a relative byte address: RBA) of the data segment 200-1 relative to a predetermined reference address or origin address of the main database 22. The prefix part 210-1 includes a pointer 230-1 that points a storage address 1100 of the data segment 200-2, a pointer 240-1 that points a storage address of another data segment, and a segment code (SC) 250-1. The segment code 250-1 is a number assigned sequentially from the root segment in order to identify a segment type. In the illustrated example, the segment code 250-1 is set to, for example, “01” since the data segment 200-1 is the root segment.
As in the case of the data segment 200-1, the data segment 200-2 contains a prefix part 210-2 and a data part 220-2. The prefix part 210-2 includes a pointer 230-2 that points a storage address 1200 of the data segment 200-3, a pointer 240-2 that points a storage address of still another data segment, and a segment code 250-2. The segment code 250-2 is set to, for example, “02” since the data segment 200-2 is a segment following the root segment.
The data segment 200-3 also contains a prefix part 210-3 and a data part 220-3. The data segment 200-3 is located at a terminal of a series of hierarchical segments that starts from the data segment 200-1. Accordingly, the prefix part 210-3 does not have a pointer for pointing a lower-layer segment but has only pointers for pointing sibling segments having the same parent segment. In practice, the prefix part 210-3 may include predetermined data indicating no address (for example, Null) as the pointer 240-3. In addition, a segment code 250-3 of the prefix part 210-3 is set to, for example, “03”.
The index database 24 simply stores index segments 300 in a format shown in FIG. 4, and does not employ a hierarchical structure. The illustrated index segment 300 contains a pointer value (for example, an RBA) 310 that points a storage address of a corresponding data segment, a key value 320 for retrieving the corresponding data segment, and a segment code (SC) 330. A value of a given indexed field in the corresponding data segment is used as the key value 320. For example, in the case where there is a name field in a data segment in which a name “SMITH” is written and it is desirable to use this name as a key for indexing, “SMITH” may be used as the key value 320. However, a value to be actually recorded as the key value 320 is a hexadecimal coded value of “SMITH”. For example, in the case of an extended binary coded decimal interchange code (EBCDIC) employed in a mainframe, “SMITH” is represented as “XE2D4C9E3C8”. The segment code 330 contains a code value assigned to the root segment for convenience, for example, “01”. In the index segment 300, the pointer value 310 and the segment code 330 constitute a prefix part, while the key value 320 constitutes a data part.
At step S5, the update log writing unit 54 writes the update log of the updated segment. FIGS. 9 and 10 show examples of structures of an update log for index segments and an update log for index target segments, respectively. Referring to FIG. 9, an update log for index segments 90 has four fields 92-98 including log numbers, segment IDs, pre-update prefix parts, and post-update prefix parts, respectively. The log number may be a serial number in ascending order. The segment ID 94 may be any value as long as the value allows identification of the updated segment. Since the index segments are not necessarily arranged in fixed locations (RBAs) in the index database 24 in MS according to the embodiment, the index segment cannot be identified with an RBA value. Instead of the RBA, since the key value is uniquely assigned in the index database 24, the index segment can be identified with this value. The pre-update prefix part 96 and the post update prefix part 98 include contents, namely, the pointer values and the segment code, of the prefix part before and after the update, respectively.
Referring to FIG. 10, an update log for index target segments 100 has six fields 102-112 including log numbers, segment IDs, log types, pre-update prefix parts, post-update prefix parts, and indexed field values. The log number 102 may be a serial number in ascending order. The segment ID 104 may be any value as long as the value allows identification of the updated index target segment. In this embodiment, since the index target segment occupies a fixed location (RBA) in the main database 22, the RBA can be employed as the segment ID. The log type 106 indicates the type of changed data held by the log. In this embodiment, three types, namely, “prefix and indexed field parts” (type 1), “prefix part only” (type 2), and “indexed field part only” (type 3), are considered. The information held in the update log differs depending on the type. The pre-update prefix part 108 and the post update prefix part 110 include contents of the index target segment before and after the update, respectively. The indexed field value 112 is a value of the indexed field of the updated index target segment. If the indexed field is updated, the updated part of the indexed field or the entity thereof is recorded. For example, if the indexed field value is updated from “ABC” to “ADE”, only the updated part “DE” may be recorded in the indexed field value 112 together with a starting location of the updated part and a length of the updated part. Alternative, the entire indexed field may be recorded.
As described above, the information held in the update log differs depending on the log type. For example, an update log entry (type 1) involving addition of a segment includes the pre-update prefix part 108, the post-update prefix part 110, and the indexed field value 112. On the other had, an update log entry (type 2) involving deletion of a segment does not include the indexed field value 112 (indicated by “N/A”) since only the pointer value included in the deleted segment needs to be known. An update log entry (type 3) involving the update of only the indexed field of a segment does not includes field the pre-update prefix part 108 and the post-update prefix part 110 since only the update indexed field value needs to be known.
At step S7, the record modifying unit 56 of the database management system 30 modifies the pointer record 70 and the segment record 80 created by the record creating unit 50 on the basis of the update logs 90 and 100 written by the update log writing unit 54, respectively. More specifically, the record modifying unit 56 reflects the contents of the update logs 90 and 100 in the pointer record 70 and the segment record 80 one by one. For example, a case where the pointer record 70 includes an entry “pointer value=1000, key value=A”, the segment record 80 includes an entry “storage address=1000, an indexed field value=A”, and the update logs 90 and 100 are formed as shown in FIG. 11 will be considered.
The update logs 90 and 100 of FIG. 11 indicate the followings. Firstly, a data segment at an address 1000 and a corresponding index segment are deleted from the main database 22 and the index database 24, respectively. Next, a data segment having an indexed field value B is added at an address 7000 of the main database 22 and a corresponding segment having a key value B is also added to the index database 24. Lastly, the indexed field value is updated to b in the added data segment located at the address 7000, due to which the index segment having the key value B is deleted in the index database 24, and an index segment having a key value B′ is added instead. Accordingly, firstly, the entry “pointer value=1000, key value=A” is deleted in the pointer record 70. Then, an entry “pointer value=7000, key value=B” is added and then this added entry is deleted. Lastly, an entry “pointer value=7000, key value=B” is added. In the segment record 80, the entry “storage address=1000, indexed field value=A” is deleted. Next an entry “storage address=7000, index field value=B” is added. Lastly, this entry is updated to an entry “storage address=7000, indexed field value=B”. The new entry may be added by overwriting information in the deleted entry.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4751702Feb 10, 1986Jun 14, 1988International Business Machines CorporationImproving availability of a restartable staged storage data base system that uses logging facilitiesUS5155678Oct 29, 1985Oct 13, 1992International Business Machines CorporationData availability in restartable data base systemUS5778387May 19, 1995Jul 7, 1998Sprint Communications Co., L.P.Database automated recovery systemUS5881379 *May 20, 1996Mar 9, 1999International Business Machines CorporationSystem, method, and program for using duplicated direct pointer sets in keyed database records to enhance data recoverability without loggingUS6052799 *May 15, 1998Apr 18, 2000International Business Machines CorporationSystem and method for recovering a directory for a log structured arrayUS6073129 *Dec 29, 1997Jun 6, 2000Bull Hn Information Systems Inc.Method and apparatus for improving the performance of a database management system through a central cache mechanismUS6185569 *Jun 29, 1998Feb 6, 2001Microsoft CorporationLinked data structure integrity verification system which verifies actual node information with expected node information stored in a tableUS6411964 *Dec 23, 1998Jun 25, 2002International Business Machines CorporationMethods for in-place online reorganization of a databaseUS6430626Aug 1, 2000Aug 6, 2002Compaq Computer CorporationNetwork switch with a multiple bus structure and a bridge interface for transferring network data between different busesUS6516380 *Feb 5, 2001Feb 4, 2003International Business Machines CorporationSystem and method for a log-based non-volatile write cache in a storage controllerUS6792418 *Mar 29, 2000Sep 14, 2004International Business Machines CorporationFile or database manager systems based on a fractal hierarchical index structureUS7085787 *Jul 19, 2002Aug 1, 2006International Business Machines CorporationCapturing data changes utilizing data-space trackingUS7107258Sep 30, 2002Sep 12, 2006Integrated Silicon Solution, Inc.Search engine for large database search using CAM and hashUS7133884 *Nov 26, 2003Nov 7, 2006Bmc Software, Inc.Unobtrusive point-in-time consistent copiesUS7299249 *Aug 4, 2006Nov 20, 2007International Business Machines CorporationApparatus, system, and program for determining consistency of a databaseUS7440936Oct 7, 2004Oct 21, 2008International Business Machines CorporationMethod for determining an access mode to a datasetUS20010047360 *Jan 29, 2001Nov 29, 2001Huras Matthew A.Online database table reorganizationUS20020091675 *Feb 28, 2002Jul 11, 2002Takayoshi ShimokawaData structure in database, database system for managing database and database managing method and systemUS20040122842 *Dec 19, 2002Jun 24, 2004Friske Craig AlanMethod and Apparatus for Building One or More Indexes on Data Concurrent with Manipulation of DataUS20040148284Jan 23, 2003Jul 29, 2004Aurilab,LlcWord recognition consistency check and error correction system and methodUS20050223043Mar 31, 2004Oct 6, 2005Randal Paul SSystem and method for a consistency check of a database backupUS20070118547 *Nov 22, 2005May 24, 2007Monish GuptaEfficient index versioning in multi-version databasesUS20080162585Aug 31, 2007Jul 3, 2008International Business Machines CorporationSystem, method, and program for checking index consistency in databaseUS20080313218Jul 25, 2008Dec 18, 2008International Business Machines CorporationMethod for checking index consistency in databaseJP2001142765A Title not availableJP2004013228A Title not availableJP2005190047A Title not availableJP2006139619A Title not availableJPH096653A Title not availableJPH0581110A Title not availableJPH0675840A Title not availableJPH06139124A Title not availableJPH06243011A Title not availableJPH08249222A Title not availableJPH10312329A Title not available* Cited by examinerNon-Patent CitationsReference1 *An effective recovery under fuzzy checkpointing in main memory databases. Elsevier Science BV All rights reserved.SK Woo, MH Kim, YJ Lee-Information and Software Technology, 2000.2 *An effective recovery under fuzzy checkpointing in main memory databases. Elsevier Science BV All rights reserved.SK Woo, MH Kim, YJ Lee—Information and Software Technology, 2000.3 *Data Blocks, Extents, and Segments. Oracle Database Concepts. Copyright Oracle Corp. 2003.4IBM, "IBM IMS High Performance Pointer Checker for z/OS," User Guide vol. 1, Version 2 Release 1, First Addition (Jun. 2003), Copyright International Business Machines Corporation, 302 pages.5Notice of Allowance from U.S. Appl. No. 11/849,246 dated May 15, 2009.6Office Action from U.S. Appl. No. 11/268,910 dated Apr. 16, 2008.7Office Action from U.S. Appl. No. 11/849,246 dated Dec. 16, 2008.8 *Relaxed Index Consistency for a Client-Server Database. IEEE 1996. Vibby Gottemukkala et al.* Cited by examinerClassifications U.S. Classification1/1, 707/999.101International ClassificationG06F17/30Cooperative ClassificationG06F17/30336, Y10S707/99942European ClassificationG06F17/30S2P9Legal EventsDateCodeEventDescriptionAug 23, 2013REMIMaintenance fee reminder mailedJan 12, 2014LAPSLapse for failure to pay maintenance feesMar 4, 2014FPExpired due to failure to pay maintenance feeEffective date: 20140112RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services