Application-specific conflict detection for weakly consistent replicated databases

• US 5,671,407 A
• Filed: 12/07/1994
• Issued: 09/23/1997
• Est. Priority Date: 12/07/1994
• Status: Expired due to Term

• Current Assignee: Yoranso Consulting LLC (Intellectual Ventures LLC)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Terry, Douglas B., Theimer, Marvin M., Spreitzer, Michael J., Welch, Brent B., Demers, Alan J., Petersen, Karin
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Homere, Jean Raymond
• Application Number:
  US08/351,841
• Time in Patent Office: 1,021 Days
• Field of Search: 395/600, 395/200.03, 395/200.12, 395/827, 395/840, 395/608, 395/610, 395/617, 395/620, 395/182.09, 395/182.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Write operations for weakly consistent replicated database systems have application-specific embedded dependency queries and related descriptions of the results that are expected to be returned when the respective dependency queries are run against the database. The dependency queries are arbitrary queries that are provided by the application to satisfy the requirements of the application. Write operations that conflict with the current state of any given instance of such a database are detected by comparing (a) the results that are returned when the dependency queries for those writes are run against the given instance of the database with (b) the results that are expected to be returned.

Claims

1. An application-specific process for detecting write operations which conflict with whatever state a database is found to have whenever any of said write operations is presented for updating said database;

said process comprising

embedding at least one dependency query in each of said write operations, together with a corresponding description of any results which are expected to be produced when said query is run against said database, where said dependency query is an arbitrary query on the database that is provided by the application as required to satisfy requirements of the application;

running each of the embedded dependency queries for any given write operation against said database whenever said given write operation is presented for updating said database until a conflict is detected or all of said queries have been applied;

collecting all results produced when any given dependency query for said given write operation is run against said database;

comparing the results produced by running said given dependency query against said database with the expected results of so doing; and

identifying a given write operation as being in conflict with the state of said database whenever the results produced by running any given one of the dependency queries for the given write fail to match the expected results.