[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A Framework for Cache Management for Mobile Databases: Design and Evaluation

  • Published:
Distributed and Parallel Databases Aims and scope Submit manuscript

Abstract

In a mobile computing environment, database servers disseminate information to multiple mobile clients via wireless channels. Due to the low bandwidth and low reliability of wireless channels, it is important for a mobile client to cache its frequently accessed database items into its local storage. This improves performance of database queries and improves availability of database items for query processing during disconnection. In this paper, we investigate issues on caching granularity, coherence strategy, and replacement policy of caching mechanisms for a mobile environment utilizing point-to-point communication paradigm.

We first illustrate that page-based caching is not suitable in the mobile context due to the lack of locality among database items. We propose three different levels of caching granularity: attribute caching, object caching, and hybrid caching, a hybrid approach of attribute and object caching. Next, we show that existing coherence strategies are inappropriate due to frequent disconnection in a mobile environment, and propose a cache coherence strategy, based on the update patterns of database items. Via a detail simulation model, we examine the performance of various levels of caching granularity with our cache coherence strategy. We observe, in general, that hybrid caching could achieve a better performance. Finally, we propose several cache replacement policies that can adapt to the access patterns of database items. For each given caching granularity, we discover that our replacement policies outperform conventional ones in most situations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, “Broadcast disks: Data management for asymmetric communication environments,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1995, pp. 199–210.

  2. S. Acharya, M. Franklin, and S. Zdonik, “Dissemination-based data delivery using broadcast disks,” IEEE Personal Communications, vol. 2, no. 6, pp. 50–60, 1995.

    Google Scholar 

  3. S. Acharya, M. Franklin, and S. Zdonik, “Prefetching from a broadcast disk,” in Proceedings of the 12th International Conference on Data Engineering, Feb. 1996.

  4. R. Agrawal and N. Gehani, “Ode: Object database & environment,” in ACM International Conference on Management of Data, 1989.

  5. T. Atwood, J. Dubl, G. Ferran, M. Loomis, and D. ade, The Object Database Standard: ODMG-93, Morgan Kaufmann, 1993.

  6. D. Barbara and T. Imielinski, “Sleepers and workaholics: Caching strategies in mobile environments,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1994, pp. 1–12.

  7. P. Bernstein, V. Hadzilacos, and N. Goodman, Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987.

  8. M. Carey, M. Franklin, M. Livny, and E. Shekita, “Data caching tradeoffs in client-server DBMS Architectures,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1991, pp. 357–366.

  9. M.J. Carey, M.J. Franklin, and M. Zaharioudakis, “Fine-grained sharing in a page server OODBMS,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1994, pp. 359–370.

  10. B.Y.L. Chan, “Cache consistency management in mobile distributed environment,” Master's thesis, The Hong Kong Polytechnic Unversity, July 1998.

  11. B.Y.L. Chan, H.V. Leong, A. Si, and K.F. Wong, “MODEC: A multi-granularity mobile object-oriented database caching mechanism, prototype and performance,” Journal on Distributed and Parallel Databases, Special Issues on Mobile Data Management and Applications, vol. 7, no. 3, pp. 343–372, 1999.

    Google Scholar 

  12. M. Choy, M. Kwan, and H.V. Leong, “On real-time distributed geographical database systems,” in 27th Hawaii International Conference on System Sciences, 1994, pp. 337–346.

  13. D. DeWitt and D. Maier, “A study of three alternative workstation-server architectures for object-sriented database systems,” in Proceedings of the 16th International Conference on Very Large Data Bases, 1990, pp. 107–121.

  14. W. Effelsberg and T. Haerder, “Principles of database buffer management,” ACM Transactions on Database Systems, vol. 9, no. 4, pp. 560–595, December 1984.

    Google Scholar 

  15. M. Franklin, M. Carey, and M. Livny, “Global memory management in client-server DBMS architectures,” in Proceedings of the 18th International Conference on Very Large Data Bases, 1992, pp. 596–609.

  16. C.G. Gray and D.R. Cheriton, “Leases: An efficient fault-tolerant mechanism for distributed file cache consistency,” in Proceedings of SOSP, 1989, pp. 202–210.

  17. Y. Huang, P. Sistla, and O. Wolfson, “Data replication for mobile computers,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1994, pp. 13–24.

  18. T. Imielinski and B. Badrinath, “Mobile wireless computing: Challenges in data management,” Communications of the ACM, vol. 37, no. 10, pp. 18–28, 1994.

    Google Scholar 

  19. J. Jannink, D. Lam, N. Shivakumar, J. Widom, and D.C. Cox, “Data management for user profiles in wireless communications systems,” Technical Report, Computer Science & Electrical Engineering Department, Stanford University, 1994.

  20. P. Keleher, A.L. Cox, and W. Zwaenepoel, “Lazy release consistency for software distributed shared memory,” in Proceedings of the 19th Annual International Symposium on Computer Architecture, IEEE, 1992, pp. 13–21.

  21. J.J. Kistler and M. Satyanarayanan, “Disconnected operation in the Coda file system,” in Proceedings of the 13th ACM Symposium on Operating System Principles, 1991, pp. 213–225.

  22. N. Krishnakumar and A.J. Bernstein, “Bounded ignorance: A technique for increasing concurrency in a replicated system,” ACM Transactions on Database Systems, vol. 19, no. 4, pp. 586–625, Dec. 1994.

    Google Scholar 

  23. H.V. Leong and A. Si, “Database caching over the air-storage,” The Computer Journal, vol. 40, no. 7, pp. 401–415, 1997.

    Google Scholar 

  24. C. Min, M. Chen, and N. Roussopoulos, “The implementation and performance evaluation of the ADMS query optimizer: Integrating query result caching and matching,” in Proceedings of International Conference on Extending Database Technology, 1994, pp. 323–336.

  25. E. O'Neil, P. O'Neil, and G. Weikum, “The LRU-K page replacement algorithm for database disk buffering,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 1993, pp. 297–306.

  26. C. Pu and A. Leff, “Replica control in distributed systems: An asynchronous approach,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, May 1991, pp. 377–386.

  27. H. Schwetman, CSIM Reference Manual (Revision 15), 1991. Microelectronics and Computer Technology Corporation.

  28. A. Si and H.V. Leong, “Query optimization for broadcast database,” Data and Knowledge Engineering Journal, Vol. 29, no. 3, pp. 351–380, 1999.

    Google Scholar 

  29. A. Silberschatz, H.F. Korth, and S. Sudarshan, Database System Concepts, 3rd edn., McGraw-Hill: New York, 1996.

    Google Scholar 

  30. A.S. Tanenbaum, Computer Networks, 3rd edn., Prentice Hall, 1996.

  31. M.H. Wong, D. Agrawal, and H.K. Mak, “Bounded inconsistency for type-specific concurrency control,” Journal on Distributed and Parallel Databases, vol. 5, no. 1, pp. 31–75, Jan. 1997.

    Google Scholar 

  32. M. Zaharioudakis and M.J. Carey, “Hierarchical, adaptive cache consistency in a page server OODBMS,” IEEE Transactions on Computers, vol. 47, no. 4, pp. 427–444, April 1998.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computing, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

    Boris Y. Chan & Hong V. Leong

  2. Department of Computing, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

    Antonio Si

Authors
  1. Boris Y. Chan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Antonio Si
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hong V. Leong
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chan, B.Y., Si, A. & Leong, H.V. A Framework for Cache Management for Mobile Databases: Design and Evaluation. Distributed and Parallel Databases 10, 23–57 (2001). https://doi.org/10.1023/A:1019297705159

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1019297705159