System and methods for invalidation to enable caching of dynamically generated content
First Claim
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+1Rnew,2 . . . Rnew,n)∪
. . . ∪
(Rnew,1 . . . R+j . . . Rnew,n)∪
. . . ∪
(Rnew,1 . . . Rnew,n-1R+n)]∪
[(R−
1Rold,2 . . . Rold,n)∪
. . . ∪
(Rold,1 . . . R−
j . . . Rold,n)∪
. . . ∪
(Rold,1 . . . Rold,n-1R−
n)]
where each Rn is a relation involved in the query Q, each Rold,n is a state of the relation Rn as of the beginning of a preceding processing cycle, each Rnew,n is a state of the relation Rn as of the beginning of the current processing cycle, each R−
n is a subset of tuples deleted from the relation Rn since the beginning of a preceding processing cycle, and each R+n is a subset of tuples added to the relation Rn since the beginning of a preceding processing cycle, and if said results set is non-empty, designating said query Q as one of said identified queries.
0 Assignments
0 Petitions
Accused Products
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.
106 Citations
16 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+1Rnew,2 . . . Rnew,n)∪
. . . ∪
(Rnew,1 . . . R+j . . . Rnew,n)∪
. . . ∪
(Rnew,1 . . . Rnew,n-1R+n)]∪
[(R−
1Rold,2 . . . Rold,n)∪
. . . ∪
(Rold,1 . . . R−
j . . . Rold,n)∪
. . . ∪
(Rold,1 . . . Rold,n-1R−
n)]
where each Rn is a relation involved in the query Q, each Rold,n is a state of the relation Rn as of the beginning of a preceding processing cycle, each Rnew,n is a state of the relation Rn as of the beginning of the current processing cycle, each R−
n is a subset of tuples deleted from the relation Rn since the beginning of a preceding processing cycle, and each R+n is a subset of tuples added to the relation Rn since the beginning of a preceding processing cycle, andif said results set 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+1Rnew,2 . . . Rnew,n)∪
. . . ∪
(Rnew,1 . . . R+j . . . Rnew,n)∪
. . . ∪
(Rnew,1 . . . Rnew,n-1R+n)]∪
[(R−
1Rold,2 . . . Rold,n)∪
. . . ∪
(Rold,1 . . . R−
j . . . Rold,n)∪
. . . ∪
(Rold,1 . . . Rold,n-1R−
n)]where each Rn is a relation involved in the query Q, each Rold,n is a state of the relation Rn as of the beginning of a preceding processing cycle, each Rnew,n is a state of the relation Rn as of the beginning of the current processing cycle, each R−
n is a subset of tuples deleted from the relation Rn since the beginning of a preceding processing cycle, and each R+n is a subset of tuples added to the relation Rn since the beginning of a preceding processing cycle, andif 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+1Rnew,2 . . . Rnew,n)∪
. . . ∪
(Rnew,1 . . . R+j . . . Rnew,n) ∪
. . . ∪
(Rnew,1 . . . Rnew,n-1 R+n)] ∪
[(R−
1(Rnew,2∪
R−
2) . . . (Rnew,1∪
R−
1))∪
. . . ∪
((Rnew,1∪
R−
1) . . . R−
j . . . (Rnew,n∪
R−
n))∪
. . . ∪
((Rnew,1∪
R−
1) . . . (Rnew,n-1∪
R−
n-1)R−
n) ∪
(Rold,1 . . . Rold,n-1 R−
n)]where each Rn is a relation involved in the query Q, each Rold,n is a state of the relation Rn as of the beginning of a preceding processing cycle, each Rnew,n is a state of the relation Rn as of the beginning of the current processing cycle, each R−
n is a subset of tuples deleted from the relation Rn since the beginning of a preceding processing cycle, and each R+n is a subset of tuples added to the relation Rn since the beginning of a preceding processing cycle, andif said results set is non-empty, designating the query Q as one of said identified queries. - View Dependent Claims (4)
-
-
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+1Rnew,2 . . . Rnew,n)∪
. . . ∪
(Rnew,1 . . . R+j . . . Rnew,n)∪
. . . ∪
(Rnew,1 . . . Rnew,n-1R+n)]∪
[(R−
1(Rnew,2∪
R−
2) . . . (Rnew,1∪
R−
1))∪
. . . ∪
((Rnew,1∪
R−
1) . . . R−
j . . . (Rnew,n∪
R−
n))∪
. . . ∪
((Rnew,1∪
R−
1) . . . (Rnew,n-1∪
R−
n-1)R−
n) ∪
(Rold,1 . . . Rold,n-1R−
n)]where each Rn is a relation involved in the query Q, each Rold,n is a state of the relation Rn as of the beginning of a preceding processing cycle, each Rnew,n is a state of the relation Rn as of the beginning of the current processing cycle, each Rn is a subset of tuples deleted from the relation Rn since the beginning of a preceding processing cycle, and each R+n is a subset of tuples added to the relation Rn since the beginning of a preceding processing cycle, and if said results set is non-empty, designating the query Q as one of said identified queries. - View Dependent Claims (6)
-
-
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+1(R′
2∪
R+2) . . . (R′
n∪
R+n))∪
. . . ∪
((R′
1∪
R+1) . . . R+j . . . (R′
n∪
R+n))∪
. . . ∪
((R′
1∪
R+1) . . . (R′
n-1∪
R+n-1)R+n)∪
(R−
1(R′
2∪
R−
2) . . . (R′
n∪
R−
n))∪
. . . ∪
((R′
1∪
R−
1) . . . R−
j . . . (R′
n∪
R−
n))∪
. . . ∪
((R′
1∪
R−
1) . . . (R′
n-1∪
R−
n-1)R−
n)where each Rn is a relation involved in the query Q, each R′
n is a state of the relation Rn as of the time of processing of the query Q, each R−
n is a subset of tuples deleted from the relation Rn since the beginning of a preceding processing cycle, and each R+n is a subset of tuples added to the relation Rn since the beginning of a preceding processing cycle, andif said results set is non-empty, 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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
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+1(R′
2∪
R+2) . . . (R′
n∪
R+n))∪
. . . ∪
((R′
1∪
R+1) . . . R+j . . . (R′
n∪
R+n)∪
. . . ∪
((R′
1∪
R+1) . . . (R′
n-1∪
R+n-1)R+n)∪
(R−
1(R′
2∪
R−
2) . . . (R′
n∪
R−
n))∪
. . . ∪
((R′
1∪
R−
1) . . . R−
j . . . (R′
n∪
R−
n))∪
. . . ∪
((R′
1∪
R−
1) . . . (R′
n-1∪
R−
n-1)R−
n)where each Rn is a relation involved in the query Q, each R′
n is a state of the relation Rn as of the time of processing of the query Q, each R−
n is a subset of tuples deleted from the relation Rn since the beginning of a preceding processing cycle, and each R+n is a subset of tuples added to the relation Rn since the beginning of a preceding processing cycle, andif said results set is non-empty, designating the query Q as one of said identified queries.
-
Specification