Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1997-06-05
2001-04-17
Breene, John (Department: 2777)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C709S241000, C709S201000, C709S203000
Reexamination Certificate
active
06219675
ABSTRACT:
TECHNICAL FIELD
The present invention relates to data processing systems and, more particularly, to the distribution of a centralized database.
BACKGROUND OF THE INVENTION
A Database Management System (DBMS) provides users and application programs with the ability to retrieve data from a database, such as a relational database. A relational database is a collection of tables of data. Each table contains records of a certain type, and each type of record contains fields in which the data is stored. In retrieving data from the database, a well-known query language like the Structured Query Language (SQL) can be used. SQL is both an interactive query language that can be used by a user and a database programming language that can be used by application programs. Many database management systems have been developed that utilize SQL.
SQL defines four basic statements for programmatically performing operations on a database: select, update, delete, and insert. The select statement retrieves specific records or fields of records that match a particular selection criteria. For example, in a table of employee information having records with fields for first names and addresses, the select statement can be utilized to retrieve the addresses for all employees with the first name “Joe.” The selection criteria of the select statement is referred to as the predicate of the statement. The update statement is used to update or modify records or fields of records that satisfy particular selection criteria. The delete statement deletes records that satisfy particular selection criteria, and the insert statement inserts a record into an identified table.
When issuing statements to a database, transactions containing a series of statements are typically used. A “transaction” contains a series of statements that together perform one logical unit of work and that satisfies the properties of atomicity, consistency, isolation, and durability as described in Date,
An Introduction to Database Systems,
Vol. II, Addison-Wesley (1983), at pp. 1-142. For example, a logical unit of work may retrieve employment information for all employees whose first name is Joe and increase their salaries by ten percent. The first statement contained in a transaction is typically the “Begin Transaction” statement, which indicates to the DBMS that a transaction is about to begin. The DBMS uses this indication to identify any updates requested during the transaction as being tentative only, not permanent, so that if an error occurs, the updates can be undone easily. The updates are considered to be tentative until such time as the caller issues a “Commit” statement. Upon receiving a “Commit” statement, the DBMS performs all updates in the transaction. However, if an error occurred during the processing of the transaction, the caller can issue a “Rollback” statement which cancels the transaction and returns the database to its pre-transaction state. Therefore, a transaction either executes in its entirety or is completely canceled. In either case, the transaction is said to have completed. In this manner, a transaction makes a sequence of operations that is non-atomic operate as though it were atomic.
When more than one transaction is being processed by a DBMS, concurrency problems can arise which lead to the unreliable execution of the transactions. An example of such a concurrency problem is depicted in FIG.
1
A.
FIG. 1A
depicts two transactions, transaction A and transaction B, which are being executed on a database simultaneously. Transaction A increments a field X and a field Y, and transaction B multiplies the value of field X by 2 and increments field Z. The processing of the transactions is depicted chronologically with respect to times T
1
-T
6
. At time T
1
, transaction A retrieves a field X of a record using a select statement and stores the value of the field into a variable “temp1.” At time T
2
, transaction B retrieves the value of field X and copies this value into a variable “temp2.” At time T
3
, transaction A updates field X with the original value of X incremented by 1. At time T
4
, transaction B updates field X with the original value of X multiplied by 2, which nullifies transaction A's processing with respect to this field. At time T
5
, transaction A retrieves field Y and transaction B retrieves field Z. At time T
6
, transaction A updates Y with Y+1 and transaction B updates Z with Z+1. The processing performed at times T
5
and T
6
do not pose any concurrency problems because the actions are performed on unrelated fields.
One technique used to solve concurrency problems is to serially execute the transactions so that only one transaction ever executes on the DBMS at a time. For example, transaction A executes completely and then transaction B executes. In this manner, concurrency problems are avoided. However, if the DBMS can only process a single transaction at a time, the DBMS becomes a bottleneck and transactions may have to wait a significant amount of time before being processed. Serial execution is an undesirable solution to concurrency problems because many transactions are sufficiently unrelated (i.e., the transactions do not operate on common data) such that they can execute concurrently and pose no concurrency problems. Having a transaction that is unrelated to an executing transaction wait before being executed is an unnecessary restriction and slows down both the performance of the DBMS and the performance of the programs that issue the transactions.
In order to simultaneously process database transactions and prevent concurrency problems from occurring, some conventional DBMSs execute transactions in a serializable manner. A serializable execution of transactions guarantees that a correct result occurs. A “correct” result is a result that would occur had the transactions been executed serially in some order. In the example of
FIG. 1A
, a correct result for field X is either (X*2)+1 or (X+1)*2. From the perspective of the database, either one of these results is a correct result. Serializable execution of transactions is an interleaved execution of the transactions that produces a correct result.
An example of two serializable transactions executing simultaneously is depicted in FIG.
1
B. In
FIG. 1B
, at time T
1
, transaction A retrieves field X and copies it into a variable. At time T
2
, transaction A updates field X with an incremented value. Although transaction B may attempt to retrieve field X after time T
1
and before time T
2
, transaction B is prevented from doing so by the database until transaction A updates field X so that concurrency problems do not arise. At time T
3
, transaction B is allowed to retrieve field X and copy it into a variable. Also at time T
3
, transaction A simultaneously retrieves field Y. At time T
4
, transaction B updates field X with its current value multiplied by 2, and transaction A updates field Y with an incremented value. At time T
5
, transaction B retrieves field Z, and at time T
6
, transaction B updates field Z. As can be seen from this example, transaction A and transaction B are performed simultaneously to improve performance, and since transaction B cannot access field X while transaction A is using it, concurrency problems are avoided.
Most DBMSs are centralized in nature. A “centralized DBMS” is a DBMS where all the data within the database is stored on a single computer, usually the secondary storage device of the computer. In a centralized DBMS, as the number of transactions executing on the DBMS increases, performance of the DBMS significantly decreases and becomes a drain on the overall performance of the computer. As a result, a centralized DBMS acts as a bottleneck which slows down performance of both the computer and programs executing on the computer. It is thus desirable to improve performance of a centralized DBMS.
SUMMARY OF THE INVENTION
A system that improves performance of a centralized DBMS is provided. The improved performance is realized by distributing part of the DBMS's functi
Bennett John G.
Pal Shankar
Breene John
Lewis Cheryl R.
Microsoft Corporation
Schwegman Lundberg Woessner & Kluth P.A.
LandOfFree
Distribution of a centralized database does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distribution of a centralized database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distribution of a centralized database will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2553123