Many database applications implement caching of data from a back-end database server to avoid repeated round trips to the back-end and to improve response times for end-user requests. For example, consider a web application that caches dynamic web content in the mid-tier [3, 2]. The content of dynamic web pages is usually assembled from data stored in the underlying database system and subject to modification whenever the data sources are modified. The workload is ideal for caching query results: most queries are read-only (browsing sessions) and only a small portion of the queries are actually modifying data. Caching at the mid-tier helps off-load the back-end database servers and can increase scalability of a distributed system drastically. Figure 1 shows a typical 3-tier architecture of a web services provider including database servers, a farm of web servers which generate the dynamic content, and clients. Servers of the mid-tier layer maintain individual caches. While caching at the mid tier is very attractive from a scalability perspective, applications cannot arbitrarily trade cache consistency for performance. Depending on the application, stale cache entries may cause user frustration at the least and incorrect application behavior at the worst. Periodically polling the back-end for changes is in many cases inadequate—if not done frequently enough then data in the cache becomes stale, but if done too frequently then unnecessary processing overhead is incurred. Different commercial products have addressed this problem by making different trade-offs, but typical solutions tend to be targeted towards specific application scenarios and they cannot easily be re-used. At the same time, some of the techniques could perform in a more robust and

Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.