For their scalability needs, data-intensive Web applications can use a Database Scalability Service (DBSS), which caches applications' query results and answers queries on their behalf. To address security/privacy concerns while retaining the scalability benefits of a DBSS, applications would like to encrypt all their cached query results yet somehow enable the DBSS to invalidate these results when data updates render them obsolete. Without adequate information the DBSS is forced to invalidate large regions of its cache on an update. In this paper, we present {\em invalidation clues}, a general technique that enables applications to reveal little data to the DBSS, yet limit the number of unnecessary invalidations. Compared with previous approaches, invalidation clues provide applications significantly improved tradeoffs between security/privacy and scalability. Our experiments using three Web application benchmarks, on a prototype DBSS we have built, confirm that invalidation clues are indeed a low-overhead, effective, and general technique for applications to balance their privacy and scalability needs.