System and methods for invalidation to enable caching of dynamically generated content

• US 7,228,318 B2
• Filed: 05/04/2005
• Issued: 06/05/2007
• Est. Priority Date: 02/26/2001
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Li, Wen-Syan, Candan, Kasim Selcuk, Agrawal, Divyakant
• Primary Examiner(s): Alam; Shahid Al
• Application Number:
  US11/121,825
• Publication Number:
  US 20050192995A1
• Time in Patent Office: 762 Days
• Field of Search: 707/2, 707/3, 707/4, 707/9, 707/10, 707/104.1, 707/200, 707/201, 707/203, 709/203, 709/217, 709/219, 709/226, 709/244, 711/141, 711/144
• US Class Current: 707/704
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/252 between a Database Management System and a front-end application
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

Various systems and methods are describe for determining dynamically generated content to be invalidated as a result of changes to underlying data. In one method, invalidation processing is performed using a delayed version of the database that reflects the state of the database at the beginning of a preceding processing cycle, and an update log that reflects all updates since the beginning of the preceding processing cycle. In another method, invalidation processing is performed by locking a database which is locked during processing so as to reflect the state of the database at the beginning of processing, and an update log that reflects all updates to the database since the beginning of the preceding processing cycle. In another method, invalidation processing uses the database while it is freely updated during said processing, and the update log of the database.

Claims

1. In a system for producing dynamically generated content in response to user content requests that generate database queries, a method for invalidating dynamically generated content stored in caches of network devices, comprising:

receiving updates to a database of the system;

periodically performing processing on a set of received queries to identify queries for which corresponding dynamically generated content will be invalidated as a result of said updates; and

sending invalidation messages to devices storing said corresponding content of said identified queries,

wherein said processing comprises, for a given query Q,

determining whether a results set is empty or non-empty, the results set consisting of the results;

[(R⁺₁R_new,2 . . . R_new,n)∪

. . . ∪

(R_new,1 . . . R⁺_j . . . R_new,n)∪

. . . ∪

(R_new,1 . . . R<sub>new,n−

1</sub>R⁺_n)]∪

[(R⁻

₁R_{old, 2} . . R_old,n) ∪

. . . ∪

(R_old,1 . R⁻

_j . . . R_old,n)∪

. . . ∪

(R_old,1 . . . R<sub>old,n−

1</sub>R⁻

_n)]

where each R_n is a relation involved in the query Q, each R_old,n is a state of the relation R_n as of the beginning of a preceding processing cycle, each R_new,n is a state of the relation R_n as of the beginning of the current processing cycle, each R⁻

_n is a subset of tuples deleted from the relation R_n since the beginning of a preceding processing cycle, and each R⁺_n is a subset of tuples added to the relation R_n since the beginning of a preceding processing cycle, and

only when said results sets is non-empty, designating said query Q as one of said identified queries.

2. A system for producing dynamically generated content in response to user content requests that generate database queries, comprising:

a database management system;

a web server for receiving user requests for dynamically generated content and for providing said dynamically generated content; and

an application server coupled between the database management system and the web server for generating database polling queries corresponding to said requests and for supplying resulting data from the database to said web server,

the system performing an invalidation method to invalidate dynamically generated content generated by said system and stored in caches of network devices, said method comprising;

receiving updates to the database management system;

periodically performing processing on a set of received queries to identify queries for which corresponding dynamically generated content will be invalidated as a result of said updates; and

sending invalidation messages to devices storing said corresponding content of said identified queries,

wherein said processing comprises, for a given query Q,

determining whether a results set is empty or non-empty, the results set consisting of the results;

[(R⁺₁R_new,2 . . R_new,n)∪

. . . ∪

(R_new,1 . R⁺_j . . . R_new,n)∪

. . . ∪

(R_new,1 . . R<sub>new,n−

1</sub>R⁺_n)]

[(R⁻

₁R_old,2 . . R_old,n)∪

. . . ∪

(R_old,1 . R⁻

_j . . . R<sub>old,n−

1</sub>R_old,n)∪

. . . ∪

(R_old,1 . . . R⁻

_n)]

where each R_n is a relation involved in the query Q, each R_old,n is a state of the relation R_n as of the beginning of a preceding processing cycle, each R_new,n is a state of the relation R_n as of the beginning of the current processing cycle, each R⁻

_n is a subset of tuples deleted from the relation R_n since the beginning of a preceding processing cycle, and each R⁺_n is a subset of tuples added to the relation R_n since the beginning of a preceding processing cycle, and

only when said results set is non-empty, designating said query Q as one of said identified queries.

3. In a system for producing dynamically generated content in response to user content requests that generate database queries, a method for invalidating dynamically generated content stored in caches of network devices, comprising:

receiving updates to a database of the system;

periodically performing processing on a set of received queries to identify queries for which corresponding dynamically generated content will be invalidated as a result of said updates; and

sending invalidation messages to devices storing said corresponding content of said identified queries,

wherein said processing comprises, for a given query Q,

determining whether a results set is empty or non-empty, the results set consisting of the results;

[(R⁺₁R_new,2 . . . R_new,n)∪

. . . ∪

(R_new,1 . . . R⁺_j . . . R_new,n) ∪

. . . ∪

(R_new,1 . . . R<sub>new,n−

1</sub>R⁺_n)]∪

[(R⁻

₁(R_new,2∪

R⁻

₂) . . . (R_new,1∪

R⁻

)) ∪

. . . ∪

((R_new,1∪

R⁻

₁) . . . R⁻

_j. . . (R_new,n∪

R⁻

_n))∪

. . . ∪

((R_new,1∪

R⁻

₁) . (R<sub>new,n−

1</sub>∪

R⁻

<sub>n−

1</sub>)R⁻

_n)∪

(R_old,1 . . R<sub>old,n−

1</sub>R⁻

_n)]

where each R_n is a relation involved in the query Q, each R_old,n is a state of the relation R_n as of the beginning of a preceding processing cycle, each R_new,n is a state of the relation R_n as of the beginning of the current processing cycle, each R⁻

_n is a subset of tuples deleted from the relation R_n since the beginning of a preceding processing cycle, and each R⁺_n is a subset of tuples added to the relation R_n since the beginning of a preceding processing cycle, and

only when said results set is non-empty, designating the query Q as one of said identified queries.

4. The method claimed in claim 3, wherein said processing further comprises adjusting said results set to account for the over-invalidation term:

ⁿ_i(R⁻

_i∪

R⁺_i)−

(ⁿ_iR⁻

_i∪

ⁿ_iR⁺_i)

5. A system for producing dynamically generated content in response to user content requests that generate database queries, comprising:

a database management system;

a web server for receiving user requests for dynamically generated content and for providing said dynamically generated content; and

an application server coupled between the database management system and the web server for generating database polling queries corresponding to said requests and for supplying resulting data from the database to said web server,

the system performing an invalidation method to invalidate dynamically generated content generated by said system and stored in caches of network devices, said method comprising;

receiving updates to the database management system;

periodically performing processing on a set of received queries to identify queries for which corresponding dynamically generated content will be invalidated as a result of said updates; and

sending invalidation messages to devices storing said corresponding content of said identified queries,

wherein said processing comprises, for a given query Q,

determining whether a results set is empty or non-empty, the results set consisting of the results;

[(R⁺₁R_new,2 . . . R_new,n)∪

. . . ∪

(R_new,1 . . R⁺_j . . . R_new,n) ∪

. . . ∪

(R_new,1 . . . R<sub>new,n−

1</sub>R⁺_n)]

[(R⁻

₁(R_new,2∪

R⁻

₂) . . (R_new,1∪

R⁻

₁))∪

. . . ∪

((R_new,1∪

R⁻

₁) . . . R⁻

_j . . . (R_new,n∪

R⁻

_n)∪

. . . ∪

((R_new,1∪

R⁻

₁) . . . (R<sub>new,n−

1</sub>∪

R⁻

<sub>n−

1</sub>)R⁻

_n)∪

(R_old,1 . . . R<sub>old,n−

1</sub>R⁻

_n)]

where each R_n is a relation involved in the query Q, each R_old,n is a state of the relation R_n as of the beginning of a preceding processing cycle, each R_new,n is a state of the relation R_n as of the beginning of the current processing cycle, each R⁻

_n is a subset of tuples deleted from the relation R_n since the beginning of a preceding processing cycle, and each R⁺_n is a subset of tuples added to the relation R_n since the beginning of a preceding processing cycle, and

only when said results set is non-empty, designating the query Q as one of said identified queries.

6. The system claimed in claim 5, wherein said processing further comprises adjusting said results set to account for the over-invalidation term:

ⁿ_i(R⁻

_i∪

R⁺_i)−

(ⁿ_iR⁻

_i∪

ⁿ_iR⁺_i)

7. In a system for producing dynamically generated content in response to user content requests that generate database queries, a method for invalidating dynamically generated content stored in caches of network devices, comprising:

receiving updates to a database of the system;

periodically performing processing on a set of received queries to identify queries for which corresponding dynamically generated content will be invalidated as a result of said updates; and

sending invalidation messages to devices storing said corresponding content of said identified queries,

wherein said processing comprises, for a given query Q,

determining whether a results set is empty or non-empty, the results set consisting of the results;

(R⁺₁∪

(R′

₂∪

R⁺₂) . . . (R⁻

_j . . . (R′

_n∪

R⁺_n))∪

. . . ∪

((R′

₁∪

R⁺₁) . . . R⁺_j . . . (R′

_n∪

R⁺_n)) ∪

. . . ∪

((R′

₁∪

R⁺₁) . . . (R′

<sub>n−

1</sub>∪

R⁺<sub>n−

1</sub>)R⁺_n)∪

(R⁻

₁(R′

₂∪

R⁻

₂) . . . (R′

_n∪

R⁻

_n))∪

. . . ∪

((R′

₁∪

R⁻

₁) . . . (R′

_n∪

R⁻

_n))∪

. . . ∪

((R′

₁∪

R⁻

₁) . . . (R′

<sub>n−

1</sub>∪

R⁻

<sub>n−

1</sub>) R⁻

_n)

where each R_n is a relation involved in the query Q, each R′

_n is a state of the relation R_n as of the time of processing of the query Q, each R⁻

_n is a subset of tuples deleted from the relation R_n since the beginning of a preceding processing cycle, and each R⁺_n is a subset of tuples added to the relation R_n since the beginning of a preceding processing cycle, and

only when said results, designating the query Q as one of said identified queries.

8. A system for producing dynamically generated content in response to user content requests that generate database queries, comprising:

a database management system;

a web server for receiving user requests for dynamically generated content and for providing said dynamically generated content; and

an application server coupled between the database management system and the web server for generating database polling queries corresponding to said requests and for supplying resulting data from the database to said web server,

the system performing an invalidation method to invalidate dynamically generated content generated by said system and stored in caches of network devices, said method comprising;

receiving updates to the database management system;

periodically performing processing on a set of received queries to identify queries for which corresponding dynamically generated content will be invalidated as a result of said updates; and

sending invalidation messages to devices storing said corresponding content of said identified queries,

wherein said processing is performed using said database, which is freely updated during said processing, and a portion of an update log of said database that reflects updates to the database made prior to the beginning of said processing.

9. The system claimed in claim 8, wherein said processing comprises:

determining whether respective results sets for subsets of said set of queries are empty or non-empty for tuples added to and deleted from said database since the beginning of a preceding processing cycle, using said freely updated database and said locked update log of said database; and

for each non-empty results set, designating the queries of the corresponding subset as ones of said identified queries.

10. The system claimed in claim 9, further comprising, if a results set for a given query Q is non-empty, designating as identified queries one or more additional queries that are dependent from said query Q in a positive query lattice.

11. The system claimed in claim 9, further comprising, if a results set for a given query Q is non-empty, skipping processing of one or more additional queries that are dependent from said query Q in a negative query lattice.

12. The system claimed in claim 8, wherein a subset of said queries comprises queries represented by a common query type, and

wherein processing of said subset comprises:

issuing polling queries to a query instance table of said query type for each of said updates; and

designating query instances identified through said polling queries as said identified queries.

13. The system claimed in claim 8, wherein a subset of said queries comprises queries represented by a common query type, and

wherein processing of said subset comprises:

issuing polling queries to a query instance table of said query type, and to update tables constructed from said update log and corresponding to relations utilized by queries of said query type, for each of said updates; and

designating query instances identified through said polling queries as said identified queries.

14. The system claimed in claim 8, wherein a subset of said queries comprises queries represented by a common query type and including a join operation, and

wherein processing of said subset comprises:

issuing polling queries to a query instance table of said query type, and to update tables constructed from said update log and corresponding to relations utilized by queries of said query type, and to relations of said database utilized by queries of said query type for which there have been no updates since the preceding invalidation cycle, for each of said updates; and

designating query instances identified through said polling queries as said identified queries.

15. The system claimed in claim 8, wherein said processing further comprises correcting an under-invalidation of a preceding processing cycle.

16. A system for producing dynamically generated content in response to user content requests that generate database queries, comprising:

a database management system;

a web server for receiving user requests for dynamically generated content and for providing said dynamically generated content; and

an application server coupled between the database management system and the web server for generating database polling queries corresponding to said requests and for supplying resulting data from the database to said web server,

the system performing an invalidation method to invalidate dynamically generated content generated by said system and stored in caches of network devices, said method comprising;

receiving updates to the database management system;

periodically performing processing on a set of received queries to identify queries for which corresponding dynamically generated content will be invalidated as a result of said updates; and

sending invalidation messages to devices storing said corresponding content of said identified queries,

wherein said processing comprises, for a given query Q,

determining whether a results set is empty or non-empty, the results set consisting of the results;

(R⁺₁(R′

₂∪

R⁺₂) . . . (R′

_n∪

R⁺_n))∪

. . . ∪

((R′

₁∪

R⁺₁) . . . R⁺_j . (R′

_n∪

R⁺_n))∪

. . . ∪

((R′

₁∪

R⁺₁) . . . R⁻

_j . . . (R′

<sub>n−

1</sub>∪

R⁺<sub>n−

1</sub>)R⁺_n)∪

(R⁻

₁(R′

₂∪

R⁻

₂) . . . (R′

_n∪

R⁻

_n))∪

. . . ∪

((R′

₁∪

R⁻

₁) . . . (R′

_n∪

R⁻

_n))∪

. . . ∪

((R′

₁∪

R⁻

₁) . . . (R′

<sub>n−

1</sub>∪

R⁻

<sub>n−

1</sub>)R⁻

_n)

where each R_n is a relation involved in the query Q, each R′

_n is a state of the relation R_n as of the time of processing of the query Q, each R⁻

_n is a subset of tuples deleted from the relation R_n since the beginning of a preceding processing cycle, and each R⁺_n is a subset of tuples added to the relation R_n since the beginning of a preceding processing cycle, and

only when said results set is non-empty, designating the query Q as one of said identified queries.