News Column

Patent Issued for Generalized Reconciliation in a Distributed Database

August 26, 2014



By a News Reporter-Staff News Editor at Information Technology Newsweekly -- Tagged, Inc. (San Francisco, CA) has been issued patent number 8805810, according to news reporting originating out of Alexandria, Virginia, by VerticalNews editors.

The patent's inventor is Lucas, Jason (Burlingame, CA).

This patent was filed on August 1, 2012 and was published online on August 12, 2014.

From the background information supplied by the inventors, news correspondents obtained the following quote: "A distributed database is a database in which storage devices are not all attached to a common central processing unit (CPU). A distributed database may be stored in multiple computers located in the same physical location, or may be dispersed over a network of interconnected computers at multiple physical locations. The locations or sites of a distributed system may be spread over a large area (such as the United States or the world) or over a small area (such as a building or campus). The collections of data in the distributed database can also be distributed across multiple physical locations.

"Typically, it is an object of a distributed database system to allow many users (clients or applications) use of the same information within the collection of data at the same time while making it seem as if each user has exclusive access to the entire collection of data. The distributed database system should provide this service with minimal loss of performance (latency) and maximal transaction throughput. That is, a user at location A must be able to access (and perhaps update) data at location B. If the user updates information, the updates must be propagated throughout the resources of the distributed database system to maintain consistency in the distributed database system.

"The updates (or database transactions) must be serialized in the distributed database system to maintain consistency. If transactions were executed in serial order, concurrency conflicts would never occur because each transaction would be the only transaction executing on the system at a given time and would have exclusive use of the system's resources. The new transactions would see the results of previous transactions, plus changes made by that transaction, but would never see the results of transactions that had not yet started. In operation, transactions typically execute concurrently and require simultaneous access and modification to the same resources. Thus, maintaining consistency in a distributed database system can be very complex and often results in unacceptable response times.

"Various concurrency control schemes currently exist such as, for example, optimistic concurrency control schemes, which operate by detecting invalid use after the fact. The basic idea of these types of schemes is to divide a database transaction's lifetime into three phases: read, validate and publish. During the read phase, a transaction acquires resources without regard to conflict or validity, but it maintains a record of the set of resources it has used (a ReadSet) and the set of resources it has modified (a WriteSet). During the validation phase, the optimistic concurrency control scheme examines the ReadSet of the transaction and decides whether the current state of those resources has since changed. If the ReadSet has not changed, then the optimistic assumptions of the transaction are proved to have been right, and the system publishes the WriteSet, committing the transaction's changes. If the ReadSet has changes, then the optimistic assumption of the transaction are proved to be wrong, and the system aborts the transaction resulting in a loss of all changes.

"In order to avoid the unnecessary abortion of transactions whose assumptions are proven to be wrong, prior art systems have been designed to reconcile incorrect assumptions. Unfortunately, to date, these mechanisms require that a specific reconciliation procedure be individually coded for each possible irresolvable event."

Supplementing the background information on this patent, VerticalNews reporters also obtained the inventor's summary information for this patent: "Systems and methods for generalized consistency control of database transactions in a distributed database are described herein. As discussed above, in distributed database systems a specific reconciliation procedure is typically needed and coded for each possible irresolvable event. It is an object of the present disclosure to enable a general characterization of multiple types of irresolvable events and thus eliminate and/or reduce the need to write individual code for every specific irresolvable event.

"In accordance with various embodiments, a database management system (DBMS) can generalize consistency control of database transactions in a distributed database by receiving a plurality of database transactions associated with a plurality of transaction sequences from a plurality of client systems in the distributed database system, wherein each transaction sequence indicates one or more uncommitted database transactions and each uncommitted database transaction includes one or more assertions that require consensus among a plurality of resources in the distributed database system to reconcile. The DBMS can detect an inconsistency among assertions associated with two or more uncommitted database transactions from two or more transaction sequences of the plurality of transaction sequences, wherein the inconsistency indicates a lack of consensus among the plurality of resources with respect to the validity of one or more of the assertions. The DBMS can process the two or more assertions associated with the two or more transaction sequences to generate a semantic preserving transform, wherein the semantic preserving transform, when applied to one or more of the two or more assertions, eliminates the inconsistency.

"In one embodiment, the DBMS can generalize consistency control by reconciling the database transactions by applying the semantic preserving transform to the one or more of the assertions.

"In one embodiment, the semantic preserving transform indicates a modification that, when applied to the one or more assertions, eliminates the inconsistency.

"In one embodiment, the two or more transaction sequences of the plurality of transaction sequences are reconciled into a global transaction sequence.

"In one embodiment, the DBMS can generalize consistency control by processing a set of rules to generate the semantic preserving transform. The set of rules can comprise generalized instructions for processing the two or more assertions associated with the two or more transactions sequences to generate the semantic preserving transform.

"In one embodiment, the DBMS can generalize consistency control by sending a message to one or more of the client systems associated with the two or more assertions associated with the two or more transaction sequences to solicit user input for resolving the inconsistency, and receiving a response indicating the user input.

"In one embodiment, the DBMS can generalize consistency control by processing the user input and the two or more assertions associated with the two or more transaction sequences to generate the semantic preserving transform.

"In one embodiment, the resources comprise other database management systems in the distributed database system or storage management systems in the distributed database system.

"In accordance with various embodiments, a DBMS can generalize consistency control of database transactions in a distributed database by detecting an inconsistency among assertions associated with two or more database transactions from two or more transaction sequences of a plurality of transaction sequences, wherein the inconsistency indicates a lack of consensus among the plurality of resources with respect to the validity of one or more of the assertions. The DMBS can process the two or more assertions associated with the two or more transaction sequences to generate a semantic preserving transform, wherein the semantic preserving transform, when applied to one or more of the two or more assertions, eliminates the inconsistency. The DBMS can reconcile the uncommitted database transactions by applying the semantic preserving transform to the one or more assertions.

"In accordance with various embodiments, a DBMS can generalize consistency control of database transactions in a distributed database. The DBMS can include a processing unit, an interface, and a memory unit. The interface can be configured to receive a plurality of database transactions associated with a plurality of transaction sequences from a plurality of client systems in the distributed database system, wherein each transaction sequence indicates one or more uncommitted database transactions and each uncommitted database transaction includes one or more assertions that require consensus among a plurality of resources in the distributed database system to reconcile. The memory unit can have instructions stored thereon, wherein the instructions, when executed by the processing unit, cause the processing unit to detect an inconsistency among assertions associated with two or more uncommitted database transactions from two or more transaction sequences of the plurality of transaction sequences, and process the two or more assertions associated with the two or more transaction sequences to generate a semantic preserving transform, wherein the semantic preserving transform, when applied to one or more of the two or more assertions, eliminates the inconsistency."

For the URL and additional information on this patent, see: Lucas, Jason. Generalized Reconciliation in a Distributed Database. U.S. Patent Number 8805810, filed August 1, 2012, and published online on August 12, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8805810.PN.&OS=PN/8805810RS=PN/8805810

Keywords for this news article include: Tagged Inc, Information Technology, Information and Data Management.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Information Technology Newsweekly


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters