Patent ID: 7228318

Claim:
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 new,2 . . . R new,n )∪ . . . ∪(R new,1 . . . R + j . . . R new,n )∪ . . . ∪(R new,1 . . . R new,n−1 R + n )]∪ [(R − 1 R old, 2 . . R old,n ) ∪ . . . ∪(R old,1 . R − j . . . R old,n )∪ . . . ∪(R old,1 . . . R old,n−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 sets is non-empty, designating said query Q as one of said identified queries.