Dynamic Web applications are becoming increasingly popular and represent the future landscape of Web applications. Currently there is no effective way to increase the scalability of such applications without significant investment in infrastructure and in-house management capability. In this thesis we develop the foundations of a Database Scalability Service (DBSS) that is able to offer scalability as a plug-in subscription service to dynamic Web applications. A DBSS works by caching application's data and answering queries on their behalf. We present the overall architecture of a DBSS, and address two key issues in designing a DBSS: (1) the privacy concerns of applications in allowing the DBSS to cache their data, and (2) the performance concerns due to the high latency applications face in accessing their data. There is an important privacy-scalability tradeoff in the DBSS setting, which requires careful consideration. To help applications manage this tradeoff, we propose: (1) a scalability-conscious security design methodology that achieves good scalability while adhering to a security policy, and (2) invalidation clues, a general technique that enables applications to balance their privacy and scalability needs at a fine granularity. To address the performance concerns, we present two transformations that reduce the latency applications face in accessing their data. Our experiments with three realistic benchmark applications we study confirm the effectiveness of our methods.