US5920857A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient optimistic concurrency control and lazy queries for B-trees and other database structures
Assignee: Hanger Solutions LLC
•
Filing: 1997-08-04
•
Granted: 1999-07-06
•
Expires: 2017-08-04
Abstract
Abstract The present invention relates to a system and methods for fine-granularity concurrency control in a parallel database. Very fine granularity (at the level of B-tree records) is implemented in a B-tree. Our method applies to B-trees, B-trees with variable keys, and their applications, such as semantic and object-oriented databases. Our method involves accumulating a transaction and then "optimistically" validating it, while attaining high efficiency with maximum semantic safety. "Lazy queries"-an efficient method for finding the intersection of two large queries-is provided for the system.
Inventors
- 👤 Naphtali David Rishe
- 👤 Artyom Shaposhnikov
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 05:18
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/22; G06F16/2228; G06F16/2246; G06F16/23; G06F16/2308; G06F16/2315; G06F16/2322; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99938
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
326 words
A concurrency control method for a multiserver database system comprising multiple server machines and multiple client machines, comprising the steps of: incrementing a logical time at each server machine during transaction execution at the server machine; accumulating a transaction T(I, D, V) at a client machine in three sets, an Insert set I, a Delete set D, and a Verify set V, the Insert set comprising a set of data items to be inserted, the Delete set comprising a set of data items to be deleted, and the Verify set comprising a set of descriptions P, each description P comprising information that identifies (a) data retrieval operations performed by the client machine with respect to a particular server machine, (b) the particular server machine subject to the client data retrieval operations, and (c) a logical timestamp at the particular server machine; delivering transaction T from the client machine to a selected server machine, the selected server machine being designated as the transaction's originator server machine; at the transaction's originator server machine, splitting transaction T into subtransactions T n per relevant servers and executing the subtransactions using a two-phase commit protocol; maintaining two logs of subtransactions at each server machine, a first log comprising a log of committed subtransactions (CL) and a second log comprising a log of subtransactions ready to commit (WL); and performing subtransaction verification at each server machine for each incoming subtransaction T n : (1) checking that the sets I n , D n , and V n do not intersect with the sets I k , D k , and V k for each subtransaction k in the set WL of the subtransactions ready to commit, (2) checking that each description P from the set V n does not intersect the sets I k or D k of any subtransaction k in the set CL of the committed subtransactions with the logical timestamp greater than or equal to the timestamp of P.
Claim 2
Dependent Claim
326 words
A concurrency control method for a multiserver database system comprising multiple server machines and multiple client machines, comprising the steps of: incrementing a logical time at each server machine during transaction execution at the server machine; accumulating a transaction T(I, D, V) at a client machine in three sets, an Insert set I, a Delete set D, and a Verify set V, the Insert set comprising a set of data items to be inserted, the Delete set comprising a set of data items to be deleted, and the Verify set comprising a set of descriptions P, each description P comprising information that identifies (a) data retrieval operations performed by the client machine with respect to a particular server machine, (b) the particular server machine subject to the client data retrieval operations, and (c) a logical timestamp at the particular server machine; delivering transaction T from the client machine to a selected server machine, the selected server machine being designated as the transaction's originator server machine; at the transaction's originator server machine, splitting transaction T into subtransactions T n per relevant servers and executing the subtransactions using a two-phase commit protocol; maintaining two logs of subtransactions at each server machine, a first log comprising a log of committed subtransactions (CL) and a second log comprising a log of subtransactions ready to commit (WL); and performing subtransaction verification at each server machine for each incoming subtransaction T n : (1) checking that the sets I n , D n , and V n do not intersect with the sets I k , D k , and V k for each subtransaction k in the set WL of the subtransactions ready to commit, (2) checking that each description P from the set V n does not intersect the sets I k or D k of any subtransaction k in the set CL of the committed subtransactions with the logical timestamp greater than or equal to the timestamp of P.
Claim 3
Dependent Claim
13 words
A database management system that uses the concurrency control method of claim 1.
Claim 4
Dependent Claim
20 words
The concurrency control method of claim 1, wherein the method is applied to database management systems storing facts about objects.
Claim 5
Dependent Claim
18 words
The concurrency control method of claim 1, wherein the method is applied in a semantic binary database system.
Claim 6
Dependent Claim
18 words
The concurrency control method of claim 1, wherein the method is carried out in a B-tree database structure.
Claim 7
Dependent Claim
323 words
A concurrency control method for a parallel B-tree comprising multiple server machines and multiple client machines, comprising the steps of: incrementing a logical time at each server machine during transaction execution at the server machine; accumulating a transaction T(I, D, V) at a client machine in three sets, an Insert set I, a Delete set D, and a Verify set V, the Insert set comprising a set of data items to be inserted, the Delete set comprising a set of data items to be deleted, and the Verify set comprising a set of descriptions P, each description P comprising information that identifies (a) boundaries of intervals of B-tree strings retrieved by the client machine with respect to a particular server machine, (b) the particular server machine subject to the client data retrieval operations, and (c) a logical timestamp at the particular server machine; delivering transaction T from the client machine to a selected server machine, the selected server machine being designated as the transaction's originator server machine; at the transaction's originator server machine, splitting transaction T into subtransactions T n per relevant servers and executing the subtransactions using a two-phase commit protocol; maintaining two logs of subtransactions at each server machine, a first log comprising a log of committed subtransactions (CL) and a second log comprising a log of subtransactions ready to commit (WL); and performing subtransaction verification at each server machine for each incoming subtransaction T n ; (1) checking that the sets In, Dn, and Vn do not intersect with the sets I k , D k , and V k for each subtransaction k in the set WL of the subtransactions ready to commit, (2) checking that each description P from the set V n does not intersect the sets I k or D k of any subtransaction k in the set CL of the committed subtransactions with the logical timestamp greater than or equal to the timestamp of P.
Claim 8
Dependent Claim
323 words
A concurrency control method for a parallel B-tree comprising multiple server machines and multiple client machines, comprising the steps of: incrementing a logical time at each server machine during transaction execution at the server machine; accumulating a transaction T(I, D, V) at a client machine in three sets, an Insert set I, a Delete set D, and a Verify set V, the Insert set comprising a set of data items to be inserted, the Delete set comprising a set of data items to be deleted, and the Verify set comprising a set of descriptions P, each description P comprising information that identifies (a) boundaries of intervals of B-tree strings retrieved by the client machine with respect to a particular server machine, (b) the particular server machine subject to the client data retrieval operations, and (c) a logical timestamp at the particular server machine; delivering transaction T from the client machine to a selected server machine, the selected server machine being designated as the transaction's originator server machine; at the transaction's originator server machine, splitting transaction T into subtransactions T n per relevant servers and executing the subtransactions using a two-phase commit protocol; maintaining two logs of subtransactions at each server machine, a first log comprising a log of committed subtransactions (CL) and a second log comprising a log of subtransactions ready to commit (WL); and performing subtransaction verification at each server machine for each incoming subtransaction T n ; (1) checking that the sets In, Dn, and Vn do not intersect with the sets I k , D k , and V k for each subtransaction k in the set WL of the subtransactions ready to commit, (2) checking that each description P from the set V n does not intersect the sets I k or D k of any subtransaction k in the set CL of the committed subtransactions with the logical timestamp greater than or equal to the timestamp of P.
Claim 9
Dependent Claim
130 words
A query optimization method for joining or intersecting large queries in databases based on B-trees or other structures of indexed blocks of ordered records, the method comprising the steps of: rather than fully retrieving a query result at once, allowing the user to perform a Seek operation on the query result to retrieve a record meeting a condition, prefetching and caching certain subsequent records; applying the Seek operation to find the intersection of two large queries comprising: retrieving a small subset of records from a first query; using the Seek operation to retrieve matching results of a second query; submitting the matching results of the second query to the Seek operation of the first query; and repeating the process of applying the Seek operation until all matching records are retrieved.
Claim 10
Dependent Claim
130 words
A query optimization method for joining or intersecting large queries in databases based on B-trees or other structures of indexed blocks of ordered records, the method comprising the steps of: rather than fully retrieving a query result at once, allowing the user to perform a Seek operation on the query result to retrieve a record meeting a condition, prefetching and caching certain subsequent records; applying the Seek operation to find the intersection of two large queries comprising: retrieving a small subset of records from a first query; using the Seek operation to retrieve matching results of a second query; submitting the matching results of the second query to the Seek operation of the first query; and repeating the process of applying the Seek operation until all matching records are retrieved.
Claim 11
Dependent Claim
17 words
The query optimization method in claim 7 applied to a database management systems storing facts about objects.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-05 | 2003-01-04 | 2003-07-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-05 | 2007-01-04 | 2007-07-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-05 | 2011-01-04 | 2011-07-06 | $7700.00 | Window Closed / Lapsed |