嵌入式移动数据库存储机制的研究与实现

重庆大学硕士学位论文嵌入式移动数据库存储机制的研究与实现姓名：乔旭峰申请学位级别：硕士专业：计算机系统结构指导教师：罗军20050501重庆大学硕士学位论文中文摘要I摘要随着微电子技术和移动通讯技术的发展，嵌入式设备和移动终端具有越来越强大的处理能力。这引发了人们要把嵌入式移动终端作为下一代个人工作平台和轻便的移动办公载体的遐想。一种新的应用模式——嵌入式移动应用开始引起人们的关注。传统的磁盘数据库系统曾强有力地支持了电子商务应用，同样，新的嵌入式移动应用的普及也必须得到嵌入式移动数据库系统的支持。但目前有关嵌入式移动数据库的研究还比较少，虽然有少数几个已经研发成功的类似产品，但由于未能完全适应嵌入式移动计算环境而未得到广泛应用。本文就嵌入式移动数据库的存储机制进行了较为系统的研究，并提出了一种实现的途径，为嵌入式移动数据库系统的整体实现打下了很好的基础。为了适应嵌入式移动计算环境的特点，数据库系统的设计必须遵循内核微型化、标准化、分层设计和部署的策略。存储层的设计尤其要注意对有限设备资源的合理利用，并采用缓存策略来提升系统性能。存储层采用关系模型作为数据模型，并考虑对PC兼容，以达到更强的适应性和为现有的开发社区所迅速接受的目的。本文提出了数据库系统的工作版本空间的概念，它是在运行时驻留内存的数据版本，是数据库系统完整数据版本的一个活跃度较高的子集。相应的存储于外存的数据版本称为数据库的持久性版本，它是数据库在某一时刻的符合一致性的完整数据快照。系统采用乐观的数据恢复策略，弱化对持久性版本的处理，重点对工作版本空间进行组织。这样的策略大大降低了数据的物理表示和存储空间管理的难度，且具有很好的运行效率。同时，为支持嵌入式移动数据库与中央服务器的数据一致性，本文提出了一种数据同步机制，并在数据库的存储层对这种机制予以支持。为了对存取性能进行优化，本文提出了MF－AVL索引结构和可以精确描述数据活跃度的工作版本空间的数据淘汰策略。前者是AVL树的变种，能很好地适应嵌入式移动数据库的存储组织方式并提供高效的存取路径；后者则能保证工作版本空间中存储的是高活跃性的数据，并阻止对空间需求的无限增长，有助于高效地利用存储空间并提升系统的存取性能。关键词：嵌入式移动数据库，存储机制,MF-AVL索引，工作版本空间，持久性版本空间重庆大学硕士学位论文英文摘要IIABSTRACTWiththedevelopmentofthemicro-electronicstechnologyandthemobilecommunicationtechnology，thecapabilityoftheembeddedfacilityandthemobilefacilityhasbecomeincreasinglypowerful.So,manypeoplehopethattheembeddedandmobileterminalwouldbeaprivateworkingplatformofnextgenerationandaportableplatformformobilebusiness.Anewapplicationmode,thatis,theembeddedandmobileapplicationmode,isgettingmoreandmoreattention.Aslikethee-businesswassupportedstronglybythetraditionaldiskDBMS,thenewapplicationmodemustgetsupportfromtheembeddedandmobileDBMS(Forshort,wecallitEMDBMS)beforeitwillbeacceptedbymostusers.ButthereislittleresearchonEMDBMSatpresent.Althoughthereareafewproductionsthathavebeendeveloped,theyhavenotbeenacceptedbecausetheycannotsatisfyallthecharacteristicsoftheembeddedandmobilecomputingenvironment.ThisdissertationhascarriedonsystemicresearchonthestoragepolicyofEMDBMS,andputforwardonewaytorealizeit.AllofthathaslaidagoodfoundationforthefullrealizationofEMDBMS.Inordertoadapttothecharacteristicsoftheembeddedandmobilecomputingenvironment,thedesignofthedatabasesystemshouldobeythefollowingpolicies:micro-kernel,standardization,beinglayereddesignedanddeployed.Inthestoragetier,itshouldpaymoreattentiontotherationalutilizationofthelimitedresources,andadoptthewayofmemorybuffertopromotesystematicfunction.Inordertoachievehighadaptabilityandbeacceptedrapidlybythecurrentdevelopmentcommunities,thestoragetier,whichisconsideredtobecompatibletoPC,usesrelationdatamodel.Inthisdissertation,theconceptofworkingeditionspace(WES)isputforwardwhichisthememory-residentdataversioninthedatabaseruntime,andisahigh-activenesssubsetofthecompletedataeditionofdatabase.ComparativelytoWES,thepermanenteditionspace(PES)isthedataeditionwhichisstoredintheexternalstorage,andatacertainmoment,itisanintactdatasnapshotofthedatabasewhichaccordswithconsistency.Thesystemadoptstheoptimistictacticsofdatarecovery,weakenthetreatmenttoPES,andpaymoreattentiontotheorganizationofWES.Suchtacticshavesimplifiedtheprocessofphysicalorganizationofdataandmemoryspacemanagementgreatly,andhavegoodefficiency.Meanwhile,inordertomaintainthedata重庆大学硕士学位论文英文摘要IIIconsistencybetweenEMDBMSandcentraldatabaseserver,thisdissertationproposesadatasynchronousmechanismwhichissupportedinthestoragetier.Inordertooptimizethedataaccessperformance,theMF-AVLindexstructureandthedataeliminationstrategyinWESwhichcanaccuratelydescribethedataactivityareproposed.TheformerisamutationofAVLtree,whichcanwellmeetthewayofdataorganizationofEMDBMSandofferhigh-efficientaccesspaths.ThelattercanguaranteewhatisstoredinWESishigh-activenessdata.Itcanpreventthelimitlessgrowthoftherequirementformemoryandbebeneficialtoutilizememoryefficientlyandpromotesystematicaccessperformance.Keywords:EMDBMS,StorageMechanism,MF-AVLIndex,WorkingEditionSpace,PermanentEditionSpace重庆大学硕士学位论文1绪论11绪论数据库管理系统和操作系统是当代应用的两大支撑性软件。数据库的出现大大简化了应用程序的开发，使得应用程序可以更关注于业务的实现而不是复杂而烦琐的数据的基本管理。数据库被应用于维护商业内部记录，在Internet上为客户显示数据；数据库用于支持科学研究，天文学家、人类基因研究者和探索蛋白质医药性质的生化学家以及其他很多科学家需要的数据都存储在数据库中。[1]信息技术的发展和现实社会的需求推动着数据库技术的不断进步，出现了诸如分布式数据库、地理信息数据库、数据仓库和数据挖掘、时实数据库以及嵌入式移动数据库、面向对象数据库等，同时，它们也推动了信息技术的发展，使得人们对计算机技术寄予了更高的期望。1.1信息社会的移动化趋势当今是一个高度信息化的社会，人们的生活与计算机技术密不可分。个人电脑成为办公室里的必备工具，在Internet上浏览新闻、搜索有价值的信息、与亲朋好友进行即时的通信、进行互连游戏等成为现代生活的一部分。[19]在上个世纪90年代中后期，当Internet走过萌芽期茁壮成长的时候，另一股新的信息化技术――移动通讯技术也走进了平常人的生活中。由于终端技术和移动带宽的原因，当时移动通讯技术仅限于语音通讯和简单文本的传输。但随着移动通讯技术的不断发展，移动终端的处理能力更加强大，可以在Internet上冲浪，浏览股市行情，进行网上交易，收看网上视频，拍照并传输照片等。企业和组织现在开始渴望能够进行移动办公，管理者希望能够在没有固定网络的环境中了解到千里之外的公司的最新信息；在偏远地区的高速公路的施工人员想像能够通过手机方便地向中央数据库提交路段的施工情况。[2]这种新的需求形成了一种强大的推动力，促使我们的社会向移动信息化的方向前进。固定网络里的网络连线已经成为不断流动的办公人群、甚至消费人群的束缚，成为现代人们快节奏生活，高效率工作的绊脚石。随着现在3G技术的成熟及部署、以至将来4G的实现，通讯技术的进步将更快地催生出一个移动信息化的社会。在这个社会里，人们将不受空间地域的限制，不受固定网络的束缚，更加快捷方便地处理各种事务，从而使整个社会的效率极大地提高。但实现这个目标的另一个重要前提是有更多成熟的、适应嵌入式移动计算环境的应用软件出现。重庆大学硕士学位论文1绪论21.2嵌入式移动计算环境的特点在众多类型的移动设备中，便携式计算机功能最为强大，和桌面PC的能力不相上下。但更多的移动设备是类似于手机这样的手持嵌入式设备。相对于便携式计算机，手持嵌入式设备更小巧、携带方便，必将成为未来移动应用终端的主流。但相对于传统PC，它们无论在CPU的处理能力还是主存、二级存储器的存储能力上都相差很多。也就是说，移动应用面临着设备资源紧张的问题。[9]其次，移动计算环境比传统的计算环境更为复杂和灵活。计算平台的移动性、连接的频繁断接性、网络条件的多样性、网络通讯的非对称性、系统的高