Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-01-31
2004-03-30
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06714943
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to computer systems, and more particularly to dependency tracking in a database system.
2. Background
The present invention pertains to dependency tracking in a database system. “Dependency” in a database system refers to the ordering in which operations may be performed against data items in the database. If a first operation is applied against a data item, and a second operation against that data item can only be applied after the first operation has been completed, then the second operation is said to be dependent upon the first operation. For example, consider a database statement to “UPDATE” a data item. That statement can only be processed after a prior statement to “INSERT” that data item into a database has completed (since the data item does not exist until the completion of the INSERT statement). Thus, the UPDATE statement in this example is dependent upon the INSERT statement.
A logical unit of work in a database system that comprises one or more database statements is often referred to as a transaction. When a database system executes a transaction, the transaction may perform a data operation upon a data item that was written or updated in response to the execution of previous transaction(s). Consequently, the results returned by the database system in response to executing any given transaction are dictated by changes made by a set of previously executed transactions. With respect to affected data items, the latest transaction is thus dependent upon previous transactions that have operated upon those data items.
For many reasons, it is useful to track dependencies between transactions in a database system. For example, assume that two transactions, TXA and TXB, must be reapplied to the database. This may occur, for example, if the database is recovering from a prior database failure and transactions are being reapplied to set the database back to its pre-failure state. As an another example, tracking dependencies is useful in determining the order in which transactions may be applied or propagated when replicating a database.
Dependency tracking is also useful with respect to database objects having uniqueness constraints. For a relational database table, a uniqueness constraint requires that every value in a column or set of columns to be unique—that is, no two rows of a table should have duplicate entries in a specified column or set of columns. For example, assume that a first transaction deletes a row from a table having a key value in a “uniqueness” column and a second transaction adds a new and different row to the table having the same key value in that column. The second transaction is dependent upon the execution and completion of the first transaction, since otherwise, there would be two rows in the table having the same key value in the column, which would violate the uniqueness constraint upon the column.
Dependency information can be extracted from log files in a database system. However, extracting and analyzing log files to determine/track dependencies is a very expensive to perform. Therefore, it is clearly desirable to provide a method and mechanism to track dependencies in a database statement.
SUMMARY OF THE INVENTION
The present invention is directed to a method and mechanism for dependency tracking in a database system. According to an embodiment of the invention, all dependencies for a transaction or operation can be characterized by a single value representing all prior transactions or database changes that it is dependent upon. This value can be calculated at various granularity levels, such as the granularity of the row level, based upon maintaining a data structure that records change or commit values for a specified granularity level for objects in a database. For granularity at the row level, a row_SCN value can be maintained according to an embodiment of the invention.
According to an aspect of an embodiment of the invention, dependency tracking is performed for uniqueness constrained objects by tracking change or commit values for a key range associated with the uniqueness constrained object. For uniqueness constrained tables, this type of key range can be associated with a particular column or set of columns in the uniqueness constrained table. If an index exists upon a uniqueness constrained column, then the key range can correspond to a range of index key values.
According to another aspect of an embodiment of the invention, dependency tracking for referentially constrained objects is performed by tracking change or commit values for certain key ranges as well as change or commit values at various granularities in the database. The combination of the various sets of change or commit values are employed to determine a single value representing all prior transactions or database changes that an operation or transaction is dependent upon.
Further aspects, objects, and advantages of the invention are described below in the detailed description, drawings, and claims.
REFERENCES:
patent: 5140685 (1992-08-01), Sipple et al.
patent: 5577240 (1996-11-01), Demers et al.
patent: 5737601 (1998-04-01), Jain et al.
patent: 5781912 (1998-07-01), Demers et al.
patent: 5794229 (1998-08-01), French et al.
patent: 5940826 (1999-08-01), Heideman et al.
patent: 6349310 (2002-02-01), Klein et al.
patent: 6397227 (2002-05-01), Klein et al.
patent: 6434568 (2002-08-01), Bowman-Amuah
patent: 6442748 (2002-08-01), Bowman-Amuah
patent: 6493701 (2002-12-01), Ponnekanti
patent: 6496850 (2002-12-01), Bowman-Amuah
Fereidoon Sadri, “Integrity constraints in the information Source tracking method”, IEEE, vol. 7, No. 1, pp. 106-119, Feb. 1995.*
Louboutin et al., “Comprehensive distributed garbage collection by tracking causal dependencies of relevant mutator events”, IEEE, pp. 516-525, Jan. 1997.*
Almeida et al., “Panasync: Dependency tracking among file copies” ACN, pp. 7-12, Jan. 1997.*
E.N. Elnozahy, “On the relevance of communications costs of rollback-recovery protocols”, CAN, pp. 74-79, Feb. 1995.*
Helary et al., “A communication-Induced checkpointing protocol that ensures rollback dependency trackability”, IEEE, pp. 68-77, Jan. 1997.*
Baldoni et al., “Rollback dependency tracability: Visible characterization”, ACN, pp. 33-42, 1999.*
Sreenivas et al., “Independent global snapshots in large distributed systems”, IEEE, pp. 462-467, 1997.*
Garcia et al., “On the minimal characterization of the rollback dependency trackability property”, IEEE, pp. 342-349, 2001.*
Damani et al., “Optimistic distributed simulation based on transitive dependency”, IEEE, pp. 90-97, 1997.
Ganesh Amit
Klein Jonathan D.
Bingham & McCutchen LLP
Corrielus Jean M.
Oracle International Corporation
LandOfFree
Method and mechanism for tracking dependencies for... 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 mechanism for tracking dependencies for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and mechanism for tracking dependencies for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3191076