Method and mechanism for dependency tracking

Details Method and mechanism for dependency tracking Method and mechanism for dependency tracking

2001-01-31

2004-10-12

Alam, Shahid (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000, C709S205000

Reexamination Certificate

active

06804672

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 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 tracking dependencies at low granularity levels in a database system.
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: 5408653 (1995-04-01), Josten et al.
patent: 5577240 (1996-11-01), Demers et al.
patent: 5737601 (1998-04-01), Jain et al.
patent: 5761660 (1998-06-01), Josten et al.
patent: 5781912 (1998-07-01), Demers et al.
patent: 5794229 (1998-08-01), French et al.
patent: 5806076 (1998-09-01), Ngai et al.
patent: 5870760 (1999-02-01), Demers et al.
patent: 5870761 (1999-02-01), Demers 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
patent: 6560606 (2003-05-01), Young
patent: 6701345 (2004-03-01), Carley et al.
Almeida, et al., “Panasync: Dependency tracking among file copies”, ACM, pp. 7-12, 1997.
Baldoni, et al., “A Communication-Induced Checkpointing Protocol that Ensures Rollback-Dependency Trackability”, IEEE, pp. 68-77, 1997.
Baldoni, et al., “Rollback-Dependency Trackability: Visible Characterizations”, ACM, pp. 33-42, 1999.
Damani, et al, “Optimistic Distributed Simulation Based on Transitive Dependency Tracking”, IEEE, pp. 90-97, 1997.
Elnozahy, “On the Relevance of Communication Costs of Rollback-Recovery Protocols”, ACM, pp. 74-79, 1995.
Garcia, et al., “On the Minimal Characterization of the Rollback-Dependency Trackability Property”, IEEE, pp. 342-349, 2001.
Louboutin, et al., “Comprehensive Distributed Garbage Collection by Tracking Causal Dependencies of Relevant Mutator Events”, IEEE, pp. 516-525, 1997.
Sadri, “Integrity Constraints in the Information Source Tracking Method”, IEEE, pp. 106-119, 1995.
Sreenivas, et al., “Independent Global Snapshots in Large Distributed Systems”, IEEE, pp. 462-467, 1997.

Affiliated with

Also associated with

Rating

Method and mechanism for dependency tracking 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 dependency tracking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and mechanism for dependency tracking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3292832