Conversion of queries to monotonically increasing incremental form to continuously query a append only database

• US 5,495,600 A
• Filed: 06/03/1992
• Issued: 02/27/1996
• Est. Priority Date: 06/03/1992
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Oki, Brian M., Terry, Douglas B., Goldberg, David, Nichols, David A.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US07/892,869
• Time in Patent Office: 1,364 Days
• Field of Search: 395/600, 364/DIG. 1, 364/DIG. 2, 364/974.6, 364/974, 364/282.1
• US Class Current: 707/754
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

To produce a continuous query for an append-only database, a client defined query first is converted into its minimal bounding non-decreasing monotone (hereinafter referred to as "monotonic increasing" query. This monotonic query, in turn, is converted into an incremental query, The resulting monotonically increasing incremental query then is installed on the database as a stored procedure that takes two date/time parameters (hereinafter referred to as "time" parameters), one of which (τ) identifies the last time the procedure was executed, and the other of which (t) identifies the current time. All database records are timestamped as of the time that they are entered into the database. Thus, in operation, more or less standard procedure calls periodically invoke each of the stored query procedures, thereby periodically executing the incremental queries over database records that have timestamps spanning successive time slots.

Claims

1. A method for repetitively filtering an append-only database to find any database records that match user specified search queries, including any matching records that are appended to said database after said filtering has been initiated;

said method comprising the steps of

time stamping said records with respective running time values as the records are being appended to said database, whereby each of said database records has a time value that indicates when the record was appended to said database;

converting said user specified queries into respective incrementalized monotonic queries; and

repetitively running said incrementalized monotonic queries over said database to identify records that match said monotonic queries during successive non-overlapping increments of time, including a first increment that covers back to before said database existed and a final increment that covers up to current time.

2. The method of claim 1 wherein

each of said monotonic queries is bounded by recorded and current time parameters;

the recorded time parameter of each given one of said monotonic queries is initialized when the given monotonic query is first run to a time value predating all of said database records and is thereafter reset each time said given monotonic query is subsequently run to a time value indicating when the given monotonic query was last run; and

the current time parameter of each given monotonic query is reset each time said given monotonic query is run to current time.

3. The method of claim 2 wherein

NOT EXIST expressions with arbitrary time dependent subexpressions are permissible elements of said user specified queries.

4. The method of any of claims 2 or 3 wherein

said database is managed by a host computer.

5. The method of claim 4 wherein

each of said monotonic queries is stored by said host computer as a stored procedure which takes a recorded time parameter and a current time parameter as variables.