article

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

Authors:

Hong V. LeongAuthors Info & Claims

Distributed and Parallel Databases, Volume 10, Issue 1

Pages 23 - 57

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

Published: 01 July 2001 Publication History

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.

References

[1]

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.

Digital Library

[2]

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.

[3]

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.

Digital Library

[4]

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

Digital Library

[5]

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

Digital Library

[6]

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.

Digital Library

[7]

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

Digital Library

[8]

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.

Digital Library

[9]

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.

Digital Library

[10]

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

[11]

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.

Digital Library

[12]

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]

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.

Digital Library

[14]

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.

Digital Library

[15]

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.

Digital Library

[16]

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.

Digital Library

[17]

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.

Digital Library

[18]

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.

Digital Library

[19]

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]

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.

Digital Library

[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.

Digital Library

[22]

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.

Digital Library

[23]

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

[24]

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.

Digital Library

[25]

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.

Digital Library

[26]

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.

Digital Library

[27]

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

[28]

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.

Digital Library

[29]

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

Digital Library

[30]

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

Digital Library

[31]

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.

Digital Library

[32]

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.

Digital Library

Cited By

Dzolkhifli ZIbrahim HAffendey L(2008)Data caching strategies for checking integrity constraints of mobile databaseProceedings of the 10th International Conference on Information Integration and Web-based Applications & Services10.1145/1497308.1497345(186-192)Online publication date: 24-Nov-2008
https://dl.acm.org/doi/10.1145/1497308.1497345
Tolia NSatyanarayanan MWolbach AKnightly EBorriello GCáceres R(2007)Improving mobile database access over wide-area networks without degrading consistencyProceedings of the 5th international conference on Mobile systems, applications and services10.1145/1247660.1247672(71-84)Online publication date: 13-Jun-2007
https://dl.acm.org/doi/10.1145/1247660.1247672
Yeung MKwok Y(2005)Wireless Cache Invalidation Schemes with Link Adaptation and Downlink TrafficIEEE Transactions on Mobile Computing10.1109/TMC.2005.144:1(68-83)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.1109/TMC.2005.14
Show More Cited By

Index Terms

A Framework for Cache Management for Mobile Databases: Design and Evaluation
1. Information systems
  1. Data management systems
    1. Database management system engines
2. Networks
  1. Network types
    1. Mobile networks
    2. Wireless access networks

Recommendations

Dynamic cache invalidation scheme for wireless mobile environments

The caching of frequently accessed data items on the client side is an effective technique to improve performance in a mobile environment. Caching data in a wireless mobile computer can significantly reduce the bandwidth requirement. However, cache ...
A Spatio-Temporal Cache Replacement Policy for Location Dependent Data in Mobile Environments

Data caching in mobile clients is an important technique to enhance data availability and improve data access time. Due to cache size limitations, cache replacement policies are used to find a suitable subset of items for eviction from the cache. In ...
Intelligent cache management techniques for reducing memory systemwaste

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed and Parallel Databases

Distributed and Parallel Databases Volume 10, Issue 1

July 2001

97 pages

ISSN:0926-8782

Issue’s Table of Contents

Copyright © Copyright © 2001 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 July 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dzolkhifli ZIbrahim HAffendey L(2008)Data caching strategies for checking integrity constraints of mobile databaseProceedings of the 10th International Conference on Information Integration and Web-based Applications & Services10.1145/1497308.1497345(186-192)Online publication date: 24-Nov-2008
https://dl.acm.org/doi/10.1145/1497308.1497345
Tolia NSatyanarayanan MWolbach AKnightly EBorriello GCáceres R(2007)Improving mobile database access over wide-area networks without degrading consistencyProceedings of the 5th international conference on Mobile systems, applications and services10.1145/1247660.1247672(71-84)Online publication date: 13-Jun-2007
https://dl.acm.org/doi/10.1145/1247660.1247672
Yeung MKwok Y(2005)Wireless Cache Invalidation Schemes with Link Adaptation and Downlink TrafficIEEE Transactions on Mobile Computing10.1109/TMC.2005.144:1(68-83)Online publication date: 1-Jan-2005
https://dl.acm.org/doi/10.1109/TMC.2005.14
Malik TBurns RChaudhary A(2005)Bypass CachingProceedings of the 21st International Conference on Data Engineering10.1109/ICDE.2005.30(94-105)Online publication date: 5-Apr-2005
https://dl.acm.org/doi/10.1109/ICDE.2005.30
Ng VChan B(2005)Quality assignments for WSDL-Based servicesProceedings of the 9th international conference on Computer Supported Cooperative Work in Design II10.1007/11686699_17(163-173)Online publication date: 24-May-2005
https://dl.acm.org/doi/10.1007/11686699_17
Li YGruenwald L(2005)A caching model for real-time databases in mobile ad-hoc networksProceedings of the 16th international conference on Database and Expert Systems Applications10.1007/11546924_19(186-196)Online publication date: 22-Aug-2005
https://dl.acm.org/doi/10.1007/11546924_19
Kumar MDas S(2004)Efficient information acquisition and dissemination in pervasive computing systems through cachingWireless communications systems and networks10.5555/1016648.1016666(513-530)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.5555/1016648.1016666
Ng BSi ALau RLi FShi JHodges LSun HPeng Q(2002)A multi-server architecture for distributed virtual walkthroughProceedings of the ACM symposium on Virtual reality software and technology10.1145/585740.585768(163-170)Online publication date: 11-Nov-2002
https://dl.acm.org/doi/10.1145/585740.585768
Lee KLeong HSi A(2002)Semantic Data Broadcast for a Mobile Environment Based on Dynamic and Adaptive ChunkingIEEE Transactions on Computers10.1109/TC.2002.103985151:10(1253-1268)Online publication date: 1-Oct-2002
https://dl.acm.org/doi/10.1109/TC.2002.1039851

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents