Implementation of nested databases using flexible locking...

Details Implementation of nested databases using flexible locking... Implementation of nested databases using flexible locking...

2000-11-16

2004-08-03

Breene, John (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C710S200000

Reexamination Certificate

active

06772154

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to transaction models for data systems and, more particularly, to techniques for implementing nested databases using ignore conflicts relationships and lock delegation.
2. Description of the Related Art
A concurrency control approach based on nested databases was defined by Anfindsen (see generally, Ole Jorgen Anfindsen,
Apotram
-
An Application
-
Oriented Transaction Model,
Doctor Scient Thesis, UNIK Center for Technology at Kjeller, Department of Informatics, University of Oslo, Norway, Research Report 215, pp. 45-52, 1997) and has since been developed as the APOTRAM™ implementation of a transaction model. APOTRAM™ is a trademark of Telenor AS, Oslo, Norway.
In summary, the nested database techniques described by Anfindsen provided concurrency controls that facilitate update (generally, write access) to a given data item in a controlled manner. Execution of a nested transaction was viewed as a dynamically developing hierarchy of spheres of control (SOCs). Write spheres of control (WSOCs) were viewed as a special case of a database and, in particular, Anfindsen proposed allowing a write sphere of control (WSOC) to be dynamically converted to a database SOC at the will of the owning transaction. In doing so, the transaction in question created a subdatabase and could decide exactly which transactions should be allowed to access the subdatabase, and in which access modes. The subdatabase was converted back to a WSOC when no transactions were active inside it, and the owning transaction had control over the enclosed data item is if and when the contents of the subdatabase were committed to the enclosing database.
Anfindsen combined and integrated the notion of nested conflict serializability (NCSR) with conditional conflict serializability (CCSR) to provide a framework that dealt in a systematic way with read-write, write-read and write-write conflicts. In general, CCSR is a superset of the conflict serializability (CSR) correctness criterion that is enforced by the Atomicity, Consistency, Isolation and Durability (ACID) transaction model, the transaction model universally supported by OLTP and database systems. In transaction processing systems (TPSs) conforming to the CSR correctness criterion, conflicts between transactions are based on the commutativity of operations. In general, a conflict resulting from a request for a lock in mode M
1
against a lock held in mode M
2
can be described as an M
1
-M
2
conflict. For the typical case of operations categorized as reads or writes, the CSR correctness criterion prevents any read-write, write-read, and write-write conflict. The CCSR correctness criterion weakens constraints in an application-defined way by allowing read-write and write-read pairs of operations to conflict conditionally (i.e., according to some application-defined condition).
If subdatabases can be nested to arbitrary depths, transaction histories in subdatabases are CSR, and transactions in subdatabase histories commit to the subdatabase owner, then the resulting transaction history will be nested conflict serializable (NCSR). Nested databases and transaction histories that conform to the NCSR correctness criterion can provide a mechanism for handling write-write conflicts. An implementation in which nested databases individually conform to the CCSR correctness criterion is said to be nested conditional conflict serializable (NCCSR).
A transaction processing system that supports NCCSR or NCSR would be desirable for many applications in domains like collaborative authoring/editing, CASE, CAD, or other systems in which two or more users may perform collaborative work on a set of resources (e.g., database objects, records or data). Unfortunately, commercially available transaction processing systems do not typically provide native support for nested databases. Accordingly, techniques are desired whereby nested databases may be supported in the context of transaction processing system primitives and/or constructs that are, or are likely to become, commercially available.
SUMMARY OF THE INVENTION
Techniques have been developed whereby concurrency control mechanisms such as nested databases (e.g., as defined by Anfindsen or otherwise) can be expressed in terms of operations implemented by various flexible transaction processing systems. In particular, some realizations in accordance with the present invention implement nested databases in a framework that allows specification of ignore-conflict relationships between locking capabilities and which provides a lock delegation facility.
By providing techniques that support movement of objects from a database to a subdatabase thereof, as well as termination (e.g., commit or abort) of transactions and databases (including subdatabases), realizations in accordance with the present invention can facilitate adoption and use of advanced transaction models with unconventional concurrency control mechanisms. Some realizations in accordance with the present invention allow specification of uses of parameters with lock modes and facilitate transformation of such uses into a form suitable for utilization in execution environments that support ignore-conflict relationships.


REFERENCES:
patent: 5212788 (1993-05-01), Lomet et al.
patent: 5280612 (1994-01-01), Lorie et al.
patent: 5907848 (1999-05-01), Zaiken et al.
patent: 5983225 (1999-11-01), Anfindsen
patent: 6044370 (2000-03-01), Anfindsen
patent: 6058416 (2000-05-01), Mukherjee et al.
patent: 6182186 (2001-01-01), Daynes
patent: 6298478 (2001-10-01), Nally et al.
patent: 6343339 (2002-01-01), Daynes
patent: 6457065 (2002-09-01), Rich et al.
patent: 99/38095 (1999-07-01), None
Daynes et al. “Customizing Concurrency Controls using Graph of Locking Capabilities” in Persistent Object Systems (Proc. of the Sixth Int. Workshop on Persisten Object Systems), Workshops on Computing, Tarascon Provence, France, Sep. 1994, 14 pages..*
Anfindsen. “Apotram—an Application-Oriented Transaction Model”. Doctor Scient Thesis, UNIK Center for Technology at Kjeller, Department of Informatics, University of Oslo, Norway, Research Report 215, 1997, 124 pages.*
Daynes et al. “Lock Inheritance in Nested Transactions”. 1994.*
Daynes. “Extensible Transaction Management in PJava”.In the Pre-Proceedings of the 1st International Workshop on Persistence and Java, Sep. 1996.*
Ole Jorgen Anfindsen, “Apotram-An Application-Oriented Transaction Model,”Doctor Scient Thesis, UNIK Center for Technology at Kjeller, Department of Informatics, University of Oslo, Norway, Research Report 215, 1997, 124 pages.
P. K. Chrysanthis and K. Ramamritham, “Synthesis of Extended Transaction Models Using ACTA,”ACM Transactions on Database Systems, vol. 19, No. 3, Sep. 1994, pp. 450-491.
A. Biliris et al., “ASSET: A System Supporting Extended Transactions,” inProc. Of the ACM SIGMOD Int. Conf. on Management of Data, Minneapolis, MN, May 1994, pp. 44-54.
Laurent Daynes and Olivier Gruber, “Customizing Concurrency Controls Using Graph of Locking Capabilities,” inPersistent Object Systems(Proc. Of the Sixth Int. Workshop on Persistent Object Systems), Workshops on Computing, Tarascon, Provence, France, Sep. 1994, 14 pages.
Roger Barga and Carlton Pu, “A Practical and Modular to Implement Extended Transaction Models,”Proc. Of the 21st Int. Conf. on Very Large Databases, Zurich Switzerland, Sep. 1995, pp. 206-217.
George Heineman and Gail Kaiser, “The CORD Approach to Extensible Concurrency Control,”Advanced Research Project Agency, Rome Lab F30602-64-C-0197, WPI-CS-TR-96-1, 1996, pp. 1-22.
“Apotram AS—the Application-Oriented Transaction Management Company,” Telenor [printed on Apr. 24, 2000] Retrieved from the Internet <URL: http://www.apotram.com>, 3 pages.
“Technical Summary of Apotram,” Telenor [printed on Apr. 24, 2000] Retrieved from the Internet <URL: http://www.apotram.com/techsummary.html>, 3 pages.
Laurant Daynes and Ole Anfindsen, U.S. App. No. 09/663208, filed Sep. 15, 2000, “Implementation of Parameterized

Affiliated with

Also associated with

Rating

Implementation of nested databases using flexible locking... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Implementation of nested databases using flexible locking..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementation of nested databases using flexible locking... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3343391