一个嵌入式移动实时数据库管理系统查询优化的代价模型

《一个嵌入式移动实时数据库管理系统查询优化的代价模型》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一个嵌入式移动实时数据库管理系统查询优化代价模型徐丽萍周露（华中科技大学计算机学院武汉430074）摘要嵌入式flash存储器、数据广播以及数据实时性导致传统代价模型在嵌入式移动实时数据库管理系统中并不适用。新的代价模型考虑到了嵌入式实时移动数据库管理系统中数据来源的选择、flash的I/O代价、数据广播开销以及数据有效期等影响查询代价的因素。一个类似于动态规划的执行计划选择算法能够在此代价模型的基础上完成逻辑优化和执行计划选择的过程。关键词flash存储器，数据广播，数据有效期，代价模型ACost-modelofQueryOptimizationf

2、orEmbeddedMobileReal-TimeDatabaseManagementSystemXuLi-PingandZhouLu(ComputerInstitute,HuazhongUniversityofScienceandTechnoloy,Wuhan430074)AbstractEmbeddedflashstorage,databroadcastandthedataeffectivetimerequiredbythereal-timefeatureleadtothatwecan’tusetraditionalcostmodelintheE

3、RTMDBMS.AnewcostmodelconsidersallthefactorswhichcanaffectthecostofthequeryinEMRTDBMS,includingdatasourcechoosing,flashI/Ocost,broadcastcostanddatadeadline,andanalgorithmlikedynamicprogrammingwhichbaseonthenewcostmodelcanfinishtheprocessingoflogicoptimizationandexecutionplanchoo

4、sing.KeyWordsflashmemory,databroadcast,dataeffectivetime,costmodel1引言嵌入式移动实时数据库管理系统是指在移动计算环境下，支持实时、移动数据管理和操纵，应用于工业控制、移动通信、掌上电脑、PDA等嵌入式设备上的数据库管理系统。系统不仅具备数据存储和操纵等传统数据库管理系统功能，而且满足嵌入式系统体系结构，移动计算环境，以及实时性等特点[1]。与传统集中式数据库管理系统类似，嵌入式移动实时数据库管理系统的查询优化器也使用启发式规则与代价模型相结合的技术[2]。但是，由于应用环境的改变，以

5、往的代价模型可能不再适用，需要一个新的代价模型来进行查询代价评估。2嵌入式移动实时数据库管理系统的数据特征2.1嵌入式flash存储器的I/O参数嵌入式设备一般采用flash作为其外部存储设备。系统中的应用程序代码的存储主要采用NOR类型的flash，而数据的存储则多数使用NAND类型的flash，这两种flash存储的I/O参数与硬盘和SDRAM的比较如表1所示。表1硬盘、SDRAM、NOR型flash和NAND型flash比较存储器读取（块）写入（块）容量特点硬盘15ms15msGB容量大，速度慢，笨重，功耗大SDRAM100ns100nsMB容

6、量较大，速度较快，易逝NOR0.12us750msMB容量较小，读取速度块，擦除慢NAND25us2msMB容量较小，擦写速度快，读取速度相对较慢由表1的数据，对于NAND型flash芯片。数据读取速度比硬盘提高了至少三个数量级，写入速度也有所提高。因此，在嵌入式环境下，数据读取时间对查询开销的影响相对减弱。但是，对比硬盘，flash芯片的存储容量减小，嵌入式数据库管理系统难以存储查询所需的全部数据，这一特点会对嵌入式数据库管理系统的数据分布造成影响。2.2移动数据库的数据广播在移动计算环境中，移动客户端（MC）与移动服务基站（MSS）通信的下行带宽

7、一般远大于上行带宽，MC从MSS接收数据的开销也远小于发送开销[3]。因此，MSS利用无线网络的非对称性，把大多数MC频繁访问的数据组织起来，周期性地广播出去[4]。数据广播的页面平均存取时间与广播周期、数据访问频率和数据广播频率有关，如果使用基于启发式的多盘数据广播策略[5]，移动信道为GPRS（60Kbps），当页面大小分别4K和8K，广播数据的分盘数、访问概率和相对访问频率不同时，页面的平均等待时间如表2所示：表2基于启发式的多盘广播技术的平均等待时间页面大小盘数盘中页面数量盘中数据访问概率相对广播频率广播周期(页面)平均等待时间2K31/2/

8、80.6/0.3/0.14:2:1160.85s41/4/16/320.75/0.2/0.04/0.018: