基于移动Agent的查询优化技术研究
|
摘要
目前，移动数据库技术的研究与应用是数据库领域和移动计算领域的一个研究热点，伴随着集成电路技术、移动通信技术等领域的发展，移动数据库产品具有巨大的用户需求。
移动数据库的研究主要包括复制与缓存技术、位置管理、查询及其优化技术、数据广播、安全机制、移动事务处理以及人机界面技术，其中查询优化技术是移动数据库关键技术之一。
本文首先介绍了近年来移动计算模型、移动计算的适应性技术等方面的进展，以及移动Agent技术的应用现状，然后对移动查询的相关工作做了详细的介绍。最后在分析国内外查询处理技术的基础上，提出了一种基于移动Agent的查询优化处理模型，主要工作包括：
1、提出了一种新的查询处理模式—基于区域管理的移动查询处理模式ZQTM(Zone-based Query Transaction Model)，该模式把分布式查询与移动查询融合在一起统一处理，使得查询处理简单化。
2、提出了一种基于包含与归并的移动查询优化算法，该算法可以优化查询处理，减少查询工作量。
3、在上述工作的基础上设计了一种基于移动Agent的查询优化处理模型，并详述了其实现过程。
4、给出了对查询结果的不同处理方法，以增强模型的灵活性和适应性。
Mobile database is a research and implementation hotspot in the fields of database and mobile computing. With the development of integrated circuit and mobile communication technologies, mobile database products will have great growth in user demands.
Relative research is mainly focus on replication caching, location management, query optimizing, data broadcast, security, mobile transaction and human-machine interface technologies. Among these topics, research of query optimizing is one of the key technologies.
In this thesis we first introduced the development of mobile computing model and adaptation techniques in recent years, and the application of mobile agent. Then we discussed the status of mobile query in detail. After analyzing some existing technique, we present our new mobile query model based on mobile agent. The main contribution of this thesis includes:
1. We proposed a new distributed query transaction model based on mobile computing, that is Zone-based Query Transaction Model ,in which distributed query and mobile query unite and are managed together.
2. We designed a query optimizing algorithm- A Mobile Query Optimization Algorithm based on Containment and Merging, which can reduce query workload.
3. We depicted a query optimizing transaction model based on mobile agent and mentioned its process in details.
4. We showed two different methods of dealing with query results contributed to reinforcing the flexibility and adaptation.
移动数据库的研究主要包括复制与缓存技术、位置管理、查询及其优化技术、数据广播、安全机制、移动事务处理以及人机界面技术，其中查询优化技术是移动数据库关键技术之一。
本文首先介绍了近年来移动计算模型、移动计算的适应性技术等方面的进展，以及移动Agent技术的应用现状，然后对移动查询的相关工作做了详细的介绍。最后在分析国内外查询处理技术的基础上，提出了一种基于移动Agent的查询优化处理模型，主要工作包括：
1、提出了一种新的查询处理模式—基于区域管理的移动查询处理模式ZQTM(Zone-based Query Transaction Model)，该模式把分布式查询与移动查询融合在一起统一处理，使得查询处理简单化。
2、提出了一种基于包含与归并的移动查询优化算法，该算法可以优化查询处理，减少查询工作量。
3、在上述工作的基础上设计了一种基于移动Agent的查询优化处理模型，并详述了其实现过程。
4、给出了对查询结果的不同处理方法，以增强模型的灵活性和适应性。
Mobile database is a research and implementation hotspot in the fields of database and mobile computing. With the development of integrated circuit and mobile communication technologies, mobile database products will have great growth in user demands.
Relative research is mainly focus on replication caching, location management, query optimizing, data broadcast, security, mobile transaction and human-machine interface technologies. Among these topics, research of query optimizing is one of the key technologies.
In this thesis we first introduced the development of mobile computing model and adaptation techniques in recent years, and the application of mobile agent. Then we discussed the status of mobile query in detail. After analyzing some existing technique, we present our new mobile query model based on mobile agent. The main contribution of this thesis includes:
1. We proposed a new distributed query transaction model based on mobile computing, that is Zone-based Query Transaction Model ,in which distributed query and mobile query unite and are managed together.
2. We designed a query optimizing algorithm- A Mobile Query Optimization Algorithm based on Containment and Merging, which can reduce query workload.
3. We depicted a query optimizing transaction model based on mobile agent and mentioned its process in details.
4. We showed two different methods of dealing with query results contributed to reinforcing the flexibility and adaptation.
引文
[1] M. Satyanarayanan, Pervasive computing:vision and challenges, IEEE Personal Communicaions, Vol. 8, No. 4, August 2001, pp. 10-17.
[2] M. Weiser, The computer for the 21St Century, Scientific American, Sept. 1991
[3] Douglas B. Terry, Systems Issues in Mobile Computing, http://www. ubiq. com/hypertext/weiser/DougTerryEE250Lecture. ps
[4] D. Terry, A. Demers, K. Petersen, M. Spreitzer, M. Theimer, B. Welch. Session Guarantees for Weakly Consistent Replicated Data. Proc. Parallel and Distributed Information System, September 1994, pages 140-149.
[5] Mark Weiser, Some Computer Science Problems in Ubiquitous Computing, Communications of the ACM, July 1993.
[6] Margaret H. Dunhan, Abdelsalam(Sumi)Helal, Mobile Computing and Database:Angthing New?, SIGMOD Record Vol 24 No4 December 1995 p5-9.
[7] Chander Dhawan, Mobile Computing, MaGraw-Hill Book Co. 1997.
[8] Forman G. H., Zahorjan J. The challenges of Mobile Computing, IEEE Computer, 1994,17(4):38-47.
[9] Tomasz Imielinski, B.R. Badrinath, Mobile Wireles Computing Solution and Chanllenges in Data Management, Technical Report DCS-TR-296/WINLAB TR-49, Rutgers University, 1993.
[10] Alan Demes, Karin Petersen, Mike Spreitzer, Douglas Terry, Marvin Theimer, Brent Welch, The Bayou Architecture: Support for Data Sharing among Mobile Users, Proc. Of the IEEE Workshop on Mobile Computing System and Applications, IEEE Press, Piscataway, NJ.
[11] D.B. Terry, K. Petersen, Mike J. Spreitzer, M. M. Theimer, The Case for Non-transparent Replication: Examples from Bayou, Bulletin of the Technical Committee on Data Engineering, Vol. 21 No. 4, December 1995.
[12] Jin Jing, Abdelsalam Helal, Ahmed Elmagarmid, Client-Server Computing in Mobile Environment, ACM Computing Surveys, 1999, p117-157.
[13] Satyanarayanan M., Kistler J. J., Kumar P., et. al., Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transaction of Computer, 39(4),pp. 447-459, April 1990.
[14] Satyanarayanan M., Mobile Information Access, IEEE Personal Communications, 3(1):26-33, Feb, 1996.
[15] 谭海平，新一代分布式计算，电子周刊，2001．3．22
[16] Antonio Puli/Eato *,Orazio Tomarchio, Lorenzo Vita. MAP:Design and implementation of a mobile agents' platform, Journal of Systems Architecture 46(2000) 145-162
[17] 许慧虹，杨传厚，网络管理的新进展，数据通信，1999 No．3
[18] M. Dalmeijer, O.K. Hammer, A.T.M. Aerts." Mobile Software Agents", Computers in Industry 41(2000)251-260
[19] 邹涛，张福炎，基于移动Agent技术的信息服务与搜索模式，计算机科字，1999．Vol．26：No．4
[20] 徐练，周龙骧，王翰虎，基于Internet的移动Agent，计算机科学，2000，8：1-14
[21] 高波，费奇，陈学广。交互层次模型。计算机科学，2001，8
[22] 郑淑丽，扬敬安，骆祥峰，信息的体系结构与行为设计，计算机科学，2002，1
[23] Ouri Wolfson. et al. Moving Objects Databases: Issues and Solutions, EECS Department, University of Illinois at Chicago, 1998
[24] Fox, A. Gribble, S.D., Chawathe, Y., and Brewer, E.A., Adopting to Network and Client Variation Using Active Proxies: Lessons and Perspectives, IEEE Personal Communications, 5(4):10-19, August 1998
[25] Ouri Wolfson. et al. DOMINO: Databases for MovINg Objects tracking, EECS Department, University of Illinois at Chicago, 1999
[26] N. Pissinou, C. Dunu, A new Framework for handling Mobile Clients in a Client-Server database system the University of Southwestern Louisiana, Computer Communications , 1 MAY 2000
[27] Fox, A., S.D., Chawathe, Y., and Brewer, E.A., Adapting to Network and Client Variation Using Infrastructural Proxies : Lessons and Perspectives, IEEE Personal Communications, 5(4):10-19, August 1998
[28] Omran Bukhres and Stuart Morton. Mobile Computing Architecture for a Battlefield Environment, Computer Science Department of Purdue University. 1997
[29] O. Bukhres, S. Morton et al. A Proposed Mobile Architecture for Distributed Database Environment. Computer Science Department, Purdue University, Indianapolis, In. 1996
[30] A. Massari, S. Weissman, and P. K. Chrysanthis. Supporting Mobile Database Access through Query by Icons. Distributed and Parallel Database
Journal(Special issue on databases and mobility),Vol 4. Pp. 1-21,1996
[31] T. Imielinski, S. Viswanathan, B.r. Badrinath, Power Efficient Filtering of Data on Air, 4th Intl. Conf. On Extending Database Technology, Mar. 1994
[32] T. Imielinski, et al., Energy Efficient Indexing on Air, SIGMOD' 94, May 1994
[33] Geoffrey H. Kuenning, Seer: Predictive File Hoarding for Disconnected Mobile Operation, University of California, Los Angeles, 1997
[34] 李霖，周兴铭，移动数据库系统的三级复制体系结构，计算机学报第20卷增刊，1997年10月
[35] Chandra Chekuri, Anand Rajaraman, Conjunctive query containment revisited, Theoretical Computer Science 239 (2000) 211- 229.
[36] Guozhu Dong, Jianwen Su, Conjunctive query containment with respect to views and constraints, Information Processing Letters 57(1996) 95 -102.
[37] Jarek Gryz, Query rewriting using views in presence of functional and inclusion dependencies, Information System Vol. 24, No. 7, PP. 597-612,1999.
[38] 洪晓，光李晖，多查询之间的包含判断，计算机工程与应用，2003．19，194-195．
[39] 吴婷婷，周兴铭，基于语义缓存的移动查询导出，计算机学报，2002．10，1104-1110．
[40] 张德，董逸生，多播环境下的增量式查询归并，计算机学报，2000．4，404-409．
[41] Labrou Y, Finin T. A Proposal for a New KQML Specification[R]. Technical Report CS-97-03, Computer Science Department, UMBC, 1997.
[42] 何新贵，唐常杰，李霖，刘云生，特种数据库技术，科学出版社，2000。
[43] Dianlong Zhang, Werner Zorn. Developing Network Management Applications in an Application-oriented Way Using Mobile Agent[J]. Computer Networks and ISDN Systems, 1998,30:1551-1557.
[2] M. Weiser, The computer for the 21St Century, Scientific American, Sept. 1991
[3] Douglas B. Terry, Systems Issues in Mobile Computing, http://www. ubiq. com/hypertext/weiser/DougTerryEE250Lecture. ps
[4] D. Terry, A. Demers, K. Petersen, M. Spreitzer, M. Theimer, B. Welch. Session Guarantees for Weakly Consistent Replicated Data. Proc. Parallel and Distributed Information System, September 1994, pages 140-149.
[5] Mark Weiser, Some Computer Science Problems in Ubiquitous Computing, Communications of the ACM, July 1993.
[6] Margaret H. Dunhan, Abdelsalam(Sumi)Helal, Mobile Computing and Database:Angthing New?, SIGMOD Record Vol 24 No4 December 1995 p5-9.
[7] Chander Dhawan, Mobile Computing, MaGraw-Hill Book Co. 1997.
[8] Forman G. H., Zahorjan J. The challenges of Mobile Computing, IEEE Computer, 1994,17(4):38-47.
[9] Tomasz Imielinski, B.R. Badrinath, Mobile Wireles Computing Solution and Chanllenges in Data Management, Technical Report DCS-TR-296/WINLAB TR-49, Rutgers University, 1993.
[10] Alan Demes, Karin Petersen, Mike Spreitzer, Douglas Terry, Marvin Theimer, Brent Welch, The Bayou Architecture: Support for Data Sharing among Mobile Users, Proc. Of the IEEE Workshop on Mobile Computing System and Applications, IEEE Press, Piscataway, NJ.
[11] D.B. Terry, K. Petersen, Mike J. Spreitzer, M. M. Theimer, The Case for Non-transparent Replication: Examples from Bayou, Bulletin of the Technical Committee on Data Engineering, Vol. 21 No. 4, December 1995.
[12] Jin Jing, Abdelsalam Helal, Ahmed Elmagarmid, Client-Server Computing in Mobile Environment, ACM Computing Surveys, 1999, p117-157.
[13] Satyanarayanan M., Kistler J. J., Kumar P., et. al., Coda: A Highly Available File System for a Distributed Workstation Environment, IEEE Transaction of Computer, 39(4),pp. 447-459, April 1990.
[14] Satyanarayanan M., Mobile Information Access, IEEE Personal Communications, 3(1):26-33, Feb, 1996.
[15] 谭海平，新一代分布式计算，电子周刊，2001．3．22
[16] Antonio Puli/Eato *,Orazio Tomarchio, Lorenzo Vita. MAP:Design and implementation of a mobile agents' platform, Journal of Systems Architecture 46(2000) 145-162
[17] 许慧虹，杨传厚，网络管理的新进展，数据通信，1999 No．3
[18] M. Dalmeijer, O.K. Hammer, A.T.M. Aerts." Mobile Software Agents", Computers in Industry 41(2000)251-260
[19] 邹涛，张福炎，基于移动Agent技术的信息服务与搜索模式，计算机科字，1999．Vol．26：No．4
[20] 徐练，周龙骧，王翰虎，基于Internet的移动Agent，计算机科学，2000，8：1-14
[21] 高波，费奇，陈学广。交互层次模型。计算机科学，2001，8
[22] 郑淑丽，扬敬安，骆祥峰，信息的体系结构与行为设计，计算机科学，2002，1
[23] Ouri Wolfson. et al. Moving Objects Databases: Issues and Solutions, EECS Department, University of Illinois at Chicago, 1998
[24] Fox, A. Gribble, S.D., Chawathe, Y., and Brewer, E.A., Adopting to Network and Client Variation Using Active Proxies: Lessons and Perspectives, IEEE Personal Communications, 5(4):10-19, August 1998
[25] Ouri Wolfson. et al. DOMINO: Databases for MovINg Objects tracking, EECS Department, University of Illinois at Chicago, 1999
[26] N. Pissinou, C. Dunu, A new Framework for handling Mobile Clients in a Client-Server database system the University of Southwestern Louisiana, Computer Communications , 1 MAY 2000
[27] Fox, A., S.D., Chawathe, Y., and Brewer, E.A., Adapting to Network and Client Variation Using Infrastructural Proxies : Lessons and Perspectives, IEEE Personal Communications, 5(4):10-19, August 1998
[28] Omran Bukhres and Stuart Morton. Mobile Computing Architecture for a Battlefield Environment, Computer Science Department of Purdue University. 1997
[29] O. Bukhres, S. Morton et al. A Proposed Mobile Architecture for Distributed Database Environment. Computer Science Department, Purdue University, Indianapolis, In. 1996
[30] A. Massari, S. Weissman, and P. K. Chrysanthis. Supporting Mobile Database Access through Query by Icons. Distributed and Parallel Database
Journal(Special issue on databases and mobility),Vol 4. Pp. 1-21,1996
[31] T. Imielinski, S. Viswanathan, B.r. Badrinath, Power Efficient Filtering of Data on Air, 4th Intl. Conf. On Extending Database Technology, Mar. 1994
[32] T. Imielinski, et al., Energy Efficient Indexing on Air, SIGMOD' 94, May 1994
[33] Geoffrey H. Kuenning, Seer: Predictive File Hoarding for Disconnected Mobile Operation, University of California, Los Angeles, 1997
[34] 李霖，周兴铭，移动数据库系统的三级复制体系结构，计算机学报第20卷增刊，1997年10月
[35] Chandra Chekuri, Anand Rajaraman, Conjunctive query containment revisited, Theoretical Computer Science 239 (2000) 211- 229.
[36] Guozhu Dong, Jianwen Su, Conjunctive query containment with respect to views and constraints, Information Processing Letters 57(1996) 95 -102.
[37] Jarek Gryz, Query rewriting using views in presence of functional and inclusion dependencies, Information System Vol. 24, No. 7, PP. 597-612,1999.
[38] 洪晓，光李晖，多查询之间的包含判断，计算机工程与应用，2003．19，194-195．
[39] 吴婷婷，周兴铭，基于语义缓存的移动查询导出，计算机学报，2002．10，1104-1110．
[40] 张德，董逸生，多播环境下的增量式查询归并，计算机学报，2000．4，404-409．
[41] Labrou Y, Finin T. A Proposal for a New KQML Specification[R]. Technical Report CS-97-03, Computer Science Department, UMBC, 1997.
[42] 何新贵，唐常杰，李霖，刘云生，特种数据库技术，科学出版社，2000。
[43] Dianlong Zhang, Werner Zorn. Developing Network Management Applications in an Application-oriented Way Using Mobile Agent[J]. Computer Networks and ISDN Systems, 1998,30:1551-1557.