Constructing a transaction serialization order based on parallel or distributed database log files
First Claim
1. A method for constructing a list having a transaction serialization order using at least two local log files in a parallel or distributed database system comprising the steps of:
- creating a network of log files by identifying each commit symbol of each transaction in a first local log file with a concomitant commit symbol of said transaction in other local log files having a commit symbol associated with said transaction to thereby designate merge points;
traversing said network; and
merging said network into a single sequence, using the designated merge points.
1 Assignment
0 Petitions
Accused Products
Abstract
A method to construct a transaction serialization order based on parallel or distributed database log files that connects the log files into a network and merges the network into a sequence. Only vote symbols and commit symbols are considered in the construction and a protocol of a transaction'"'"'s vote appearing before a transaction'"'"'s commit is enforced. The log files are connected by making links between commit symbols of the same transactions in different log files. The method identifies ambiguities in the orders of the individual log files, called commit symbol cycles, and resolves them by breaking an unsupported segment of the cycle and sliding the segment'"'"'s forwardmost commit symbol backward to a position immediately prior to the first commit symbol on that segment. By doing so, the serialization implication of an individual log file may be changed, but the overall serialization implication of the database remains intact. Using an iterative process, this method can order the log files in one pass-through.
132 Citations
13 Claims
-
1. A method for constructing a list having a transaction serialization order using at least two local log files in a parallel or distributed database system comprising the steps of:
-
creating a network of log files by identifying each commit symbol of each transaction in a first local log file with a concomitant commit symbol of said transaction in other local log files having a commit symbol associated with said transaction to thereby designate merge points; traversing said network; and merging said network into a single sequence, using the designated merge points. - View Dependent Claims (2, 3)
-
-
4. A method for constructing a list having a transaction serialization order using a database log file comprising the steps of:
-
requiring a vote symbol of a transaction in said log file to occur at a time earlier than a commit symbol of said transaction in said log file; examining the placement of a commit symbol of a first transaction and a vote symbol of a second transaction and a commit symbol of a second transaction; wherein said first transaction is ordered before said second transaction if said commit symbol of said first transaction occurs at a time earlier than said vote symbol of said second transaction.
-
- 5. A method for adjusting the position of a type of operation symbol of a first transaction of a database log file relative to the position of said type of operation symbol of a second transaction of said database log file wherein said type of operation symbol of said first transaction occurs later in time than said type of operation symbol of said second transaction comprising the step of moving said position of said type of operation symbol of said first transaction to a position earlier than that of said type of operation symbol of said second transaction.
-
8. A method for identifying a commit symbol cycle in database log files comprising the steps of:
-
identifying a first local log file and at least a second local log file; identifying a commit symbol of a first transaction and a commit symbol of a second transaction on said first local log file and denominating a connection between said two commit symbols as a first segment; identifying a commit symbol of said first transaction and a commit symbol of said second transaction on said second local log file and denominating a connection between said two commit symbols as a second segment; connecting via a first temporary connection said commit symbol of said first transaction on said first local log file to said commit symbol of said first transaction on said second local log file; connecting via a second temporary connection said commit symbol of said second transaction on said first local log file to said commit symbol of said second transaction on said second local log file; wherein traversing in a forward direction on said first segment from the beginning of said first segment to the end of said first segment and then traversing via a said second temporary connection from the end of said first segment to the end of said second segment and then traversing in a forward direction on said second segment leads to said commit symbol of said first transaction on said second local log file.
-
-
9. A method for resolving a commit symbol cycle in database log files comprising the steps of:
-
identifying a commit symbol cycle and a first segment thereof; determining an unsupported segment by examining if said first segment is unsupported and, if said first segment is not unsupported, continuing to each next segment of said commit symbol cycle until an unsupported segment is found; breaking said unsupported segment between a commit symbol of a first transaction and a commit symbol of a second transaction wherein said commit symbol of said second transaction is in a position earlier in said unsupported segment than said commit symbol of said first transaction; and sliding said commit symbol of said first transaction backward to a position immediately prior to said commit symbol of said second transaction. - View Dependent Claims (10, 11, 12, 13)
-
Specification