System for accessing shared data using a serialization graph constructed from a history file showing completed locking dependencies between transactions
First Claim
Patent Images
1. Apparatus for scheduling at least two concurrent transactions accessing shared data, comprising:
- means for constructing a history file for said shared data showing the intended effect of each accessing transaction to be scheduled;
means for constructing a serialization relationship from said history file, said serialization relationship showing completed locking dependencies between said transactions;
means for detecting a cycle in said serialization relationship and formed by said transactions;
means for aborting said scheduling of said transactions in response to detecting said cycle; and
aborting said scheduling of said transactions in said cycle in response to said detection of said cycle.
1 Assignment
0 Petitions
Accused Products
Abstract
Apparatus for scheduling at least two concurrent transactions accessing a shared data is provided. When a lock request is granted, the apparatus provides for constructing a history file for the shared data to show each data accessing transaction, and also provides for constructing a serialization graph with each node denoting an active transaction, and each directed edge denoting a dependency between two transactions. The serialization graph is searched for a cycle formed by transactions, and if any is found, the transactions are aborted and restarted.
82 Citations
28 Claims
-
1. Apparatus for scheduling at least two concurrent transactions accessing shared data, comprising:
-
means for constructing a history file for said shared data showing the intended effect of each accessing transaction to be scheduled; means for constructing a serialization relationship from said history file, said serialization relationship showing completed locking dependencies between said transactions; means for detecting a cycle in said serialization relationship and formed by said transactions; means for aborting said scheduling of said transactions in response to detecting said cycle; and aborting said scheduling of said transactions in said cycle in response to said detection of said cycle. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A method for scheduling at least two concurrent transactions accessing shared data, comprising the steps of:
-
forming a history file associated with said shared data and forming each accessing transaction sequentially; constructing from said history file a serialization relationship including completed locking dependencies between said transactions; searching for a cycle in said serialization relationship; detecting said cycle formed by said transactions in response to said searching step; and aborting said transactions in said cycle and any transaction dependent therefrom after said cycle is detected. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. A locking scheme for shared database access control of a shared database having at least two concurrent transactions to be committed, comprising the steps of:
-
requesting a data item to be locked in said shared database; locking said data item in response to said data item being available; recording locking said transaction in a history file associated with said data item; constructing a serialization relationship from said history file; accessing said data item; releasing said locked data item immediately after said data item accessing step; searching said serialization relationship for the presence of a cycle after said locked data item is released; and committing said transaction in response to the absence of said cycle. - View Dependent Claims (28)
-
Specification