ASSOCIATIVE CACHING IN CLIENT-SERVER DATABASES
                                 Julie Basu
                             Stanford University
 
The client-server configuration is  a popular architecture for modern computing
systems,  and for  databases  in particular.   Such  a  database  configuration
involves  one or  more server processes  that  manage  a  shared repository  of
persistent  data,  and  handle  requests  for  data  retrieval and update  from
multiple clients.  It  is  common for  client transactions to  run  on  desktop
workstations, and to communicate with the database server using explicit
messages across a local-area or a wide-area network.

 
A traditional assumption in the design of client-server databases has been that
the  clients  have  limited  resources.  Accordingly, client  functionality has
often been restricted to transmission of queries and updates across the network
to the  server,  and  presentation of the received results to  the  user.   The
server is a potential bottleneck in such systems, especially for large database
sizes and many clients.  Due to significant  advances  in  computer technology,
today's  client   workstations   are  often   high-performance   machines  with
substantial CPU and memory.  It  is now  possible to  use the resources of such
capable clients for data caching and query evaluation purposes, so as to reduce
the server workload and improve system performance and scalability.
 

In this dissertation, we propose and  study an associative caching scheme, that
we call  A*Cache, for  client-server databases.   A*Cache supports  client-side
data  buffering and local evaluation  of  associative queries.  The cache at  a
client dynamically loads query  results during transaction  execution, and uses
query predicates to formulate  descriptions of the cache contents.  New queries
are compared against  the  cache description using predicate-based reasoning to
determine  if the  query can be evaluated locally.  In contrast to navigational
data  access using object or page identifiers, A*Cache provides predicate-based
access  to the  cached  data, thereby improving  data reuse.   Descriptions  of
client  caches are also maintained at the server, which generates notifications
for updates committed at the  central  database.  The clients use these  update
notifications to maintain the validity of their respective  caches, and also to
detect conflicting updates of shared data.
 

 
The  A*Cache  system requires  dynamic  reasoning  with  predicates,  naturally
raising questions  about  its  performance and  scalability.  The focus of this
dissertation is on the feasibility and performance of  our caching scheme  in a
practical  environment.   We  first  describe  the  architectural framework  of
A*Cache and its  execution model for  transactions, and examine various  design
issues.   We then  develop  new optimization techniques  for  A*Cache that  can
potentially improve its  performance.  The  behavior of  the A*Cache scheme  is
investigated through detailed  simulation of  a  client-server  database system
under several different workloads and data contention profiles.  We compare the
performance  of A*Cache with a system  with no  client caching, with a  caching
scheme based on  tuples, and  with  an optimized version  of A*Cache.  Using an
extended version of a standard  database benchmark, we identify scenarios where
the A*Cache schemes are beneficial, resulting in lower query response times and
better scalability, thus demonstrating the effectiveness of associative caching.