（计算机应用技术专业论文）嵌入式数据库的设计与实现.pdf

嵌入式数据库的设计与实现 中文摘要 嵌入式数据库是近些年才兴起的一项新的数据库技术，它以目前成熟的数据库 技术为基础，针对嵌入式设备的具体特点，实现对移动设备和嵌入式设备上数据的 存储、组织和管理。 传统的数据库系统一般都是运行在大型的计算机设备上，包括主机系统和各种 各样的服务器，随着计算设备的日益小型化，数据库的小型化也日益迫切。与大型 计算机设备相比，这些小型的计算设备内存较小，硬盘也较少，因此简单地将原来 的大型数据库移植到小型设备上效果并不好，必须依据这些设备的特点专门设计相 应的数据库系统。 针对嵌入式系统的需求，文章主要在两个方面进行了研究。首先，本文在综合 分析当前嵌入式数据库系统的主要功能和发展现状的基础上，以实用、体积小、便 于嵌入式应用为主要追求目标，针对嵌入式设备的具体特点，完成了词法分析器、 语法分析器以及索引机制优化等方面的研究与设计，并在l i n u x 下用c 语言设计了 一款能有效存储、操作和管理实时数据信息的嵌入式数据库，用以实现对嵌入式设 备数据的统一管理。此数据库具有微小内核、系统尺寸可剪裁、良好的跨平台性以 及灵活的应用编程接口等特点，支持a c i d 事务，支持s q l 9 2 标准子集，无须独立运 行的数据库引擎，由程序直接调用相应的a p i 函数就可以实现对数据的存取操作。 通过与s q l i t e 的测试比较可以看出，本文设计的数据库在操作涉及的数据量较小的 情况下，插入、查找和删除性能均有较大提高，比较适合于应用到数据操作较少的嵌 入式设备。其次，基于a r m 硬件平台，采用l i n u x 操作系统，在已开发完成的嵌入 式数据库进行数据管理的基础上，设计了一个嵌入式实时数据采集系统。此系统很 好的解决传统数据采集系统存在的数据管理混乱、存储效率低下等不足，在复杂环 境下能够对多种数据信息进行实时采集、高效存储管理和快速传输。 关键词：嵌入式系统；嵌入式数据库；a r m ；l i n u x t h er e s e a r c ha n dd e s i g no fe m b e d d e dd a t a b a s e g r a d u a t en a m e ：x i eh u i m a j o r ： c o m p u t e ra p p l i e dt e c h n o l o g y d i r e c t e db y ：x uy u b i n l ij i a n - w e i a b s t r a c t e m b e d d e dd a t a b a s ei san e wt e c h n o l o g yo fd a t am a n a g e m e n tr i s i n gi n r e c e n ty e a r s b a s e do nm a t u r ed a t a b a s et e c h n o l o g ya n ds p e c i a le m b e d d e d d e v i c e ，i ti m p l e m e n t st h ed a t a ss t o r a g e ，o r g a n i z a t i o na n dm a n a g e m e n to n m o b i l ed e v i c e sa n de m b e d d e dd e v i c e s t r a d i t i o n a l l y , d a t a b a s es y s t e m sr u no nl a r g e s c a l ec o m p u t e re q u i p m e n t i n c l u d i n gh o s tc o m p u t e rs y s t e m sa n da l lk i n d so fs e r v e r s a st h ec o m p u t e r e q u i p m e n tg os m a l l e ra n ds m a l l e r , t h ed a t a b a s e sm i n i a t u r i z a t i o ni su r g e n t l y c o m p a r e dw i t hl a r g e s c a l ec o m p u t e r s ，t h e s es m a l l s c a l ec o m p u t a t i o n a lu n i t s a r ec h a r a c t e r i z e db ys m a c km e m o 巧a n dm i n o rh a r d w a r ee v e nt h e yh a v en o h a r d w a r es u c ha sh a n d h e l dd e v i c e sa n di n t e l l i g e n th o u s e h o l de l e c t r o n i c s s o ， i ti sn o tf e a s i b l et oi u s tt r a n s p l a n tl a r g e s c a l ed a t a b a s et os m a l l - s c a l ed e v i c e s w em u s ts p e c i a l l y d e s i g n e d d a t a b a s e s y s t e m s t of i tf o rt h ed e v i c e s c h a r a c t e r s c o n s i d e r i n gt h ed e m a n do ft h ee m b e d d e ds y s t e m s ，t h ep a p e rw i l ls h o w t h ep r o je c ti nt w op a r t s f i r s t l y , t h r o u g ha n a l y z i n gt h em a i nf u n c t i o na n dt h e a c t u a ls t a t eo fc u r r e n te m b e d d e dd a t a b a s es y s t e ms y n t h e t i c a l l y , t h e e m b e d d e dd a t a b a s e ，t h eg o a lo fw h i c hi sa v a i l a b i l i t y , s m a l ls i z e a n d c o n v e n i e n c ef o re m b e d d e da p p l i c a t i o n s i s ，d e s i g n e dr e f e r st oa c c i d e n c e a n a l y z e r , s y n t a xa n a l y z e ra n dt h eo p t i m i z a t i o no fi n d e xm e c h a n i s ma n d s oo n a i m i n ga tt h ec o n c r e t ef e a t u r e so f e m b e d d e dd e v i c e s ，t h ee m b e d d e dd a t a b a s e s y s t e md e s i g n e di nl i n u x ，w h i c hc o u l ds t o r e ，o p e r a t ea n dm a n a g e t h ed a t ao f i n f o r m a t i o na p p l i a n c e s e f f e c t i v e l y i ts u p p o r t s t h ea c i da f f a i r , s q l 9 2 i i i s t a n d a r ds u b s e t ，i n t e g r a t e dw i t hi t sc o n c r e t ea p p l i c a t i o na n dt h ee m b e d d e d l i n u xa n dd o e s n tn e e du n a t t a c h e dr u n n i n g e n g i n e ，t h ep r o g r a mc a l l si t s r e l e v a n ta p if u n c t i o nt or e a l i z et h ea c c e s s o p e r a t i o n t h r o u g hc o m p a r i n g w i t ht h es q l i t e ，t h ed a t a b a s e sp e r f o r m a n c eh a si m p r o v e dg r e a t l v w h i l e i n v o l v i n gr e l a t i v e l ys m a l la m o u n to fd a t a ，w h i c hi sf i tf o rt h ee m b e d d e d d e v i c e sw h i c ht r e a tl e s sd a t a s e c o n d l y , t h ea r t i c l eb a s e do na r m a n dl i n u x o p e r a t i o ns y s t e m ，u s i n gt h ee m b e d d e dd a t a b a s ed e s i g n e di nt h ef i r s tp a r tt o m a n a g et h er e a l _ d a t at od e s i g nar e a l t i m ed a t aa c q u i s i t i o ns y s t e m t h e s y s t e mc a nc o n q u e rt h ed e f e c ti nt r a d i t i o n a ld a t aa c q u i s i t i o ns y s t e m s u c ha s d a t am a n a g e m e n tc h a o sa n d1 0 ws t o r a g e e f f i c i e n c y , a n dh a v eag o o d p e r f o r m a n c eo fe f f i c i e n ts t o r a g ea n dr a p i dt r a n s m i s s i o nw h i l eb e i n gi n c o m p l e xe n v i r o n m e n t k e y w o r d s ：e m b e d d e ds y s t e m ；e m b e d d e dd a t a b a s e ；a r m ；l i n u x i v 承诺书水话吊 本人郑重声明：所呈交的学位论文，是在导师指 导下独立完成的，学位论文的知识产权属于太原科技 大学。如果今后以其他单位名义发表与在读期间学位 论文相关的内容，将承担法律责任。除文中已经注明 引用的文献资料外，本学位论文不包括任何其他个人 或集体已经发表或撰写过的成果。 学位论文作者( 签章) ： 2 0 0 年月日 第一章绪论 第一章绪论 1 1 研究背景及意义 随着计算环境的发展，数据库系统也从集中式、分布式发展到今天的嵌入式数 据库系统。与通用的桌面系统不同，由于嵌入式系统没有充足的内存和磁盘资源， 因此，不论是嵌入式的操作系统还是数据库管理系统，都要占用最小的内存和磁盘 空间。若采用大型的商用数据库管理系统，则不可避免的占用大量的内存和磁盘空 间，同时会产生大量的冗余数据，因此，它不能应用于嵌入式系统的数据管理。长 期以来，商业数据库行业都在不停的追逐高性能的事务处理以及复杂的查询处理能 力，并制定了相应的行业标准。但是对嵌入式数据库系统来说，嵌入式应用系统之 间差别很大，因此它们对嵌入式数据库系统的要求较高，这主要表现在：易于维护、 高度可靠性和小巧性。嵌入式系统内存较小，c p u 速度慢，因此，在嵌入式数据库 系统中数据的结构和算法以及数据查询处理算法非常关键，必须采用合适的策略和 特殊的数据结构、算法才能满足用户的需求。 1 2 国内外研究现状 嵌入式数据库( e d b ) 在移动计算平台、家庭信息环境、通讯计算平台、电子商务 平台等领域得到广泛的应用。正是基于这一事实，各国研究机构纷纷展开了对嵌入 式数据库的研究，各大数据库厂商也将开发相应主打数据库系统的嵌入式数据库系 统作为一个重要的发展方向。 在国外，i b m 公司在d b 2 通用数据库中推出了i b md b 2s a t e l l i t e 和e v e r y p l a c e 版本，它所提供的移动计算功能使移动办公用户获得了与企业数据保持同步的能力。 同时i n f o r m i x 公司也由旗下的c l o u d s c a p e 公司推出了其移动解决方案旗舰产品的 最新版本c l o u d s c a p e3 0 ，可以对包括从服务器到笔记本电脑，甚至到轻型信息设 备，进行数据管理。而作为移动计算的市场领先者s y b a s e 公司多年前就敏锐地预见 到计算设备小型化的发展趋势，投入了大量的人员和资金对小型数据库进行研究与 开发工作，并且在全球最早推出了移动与嵌入数据库产品包- s y b a s es o la n y w h e r e s t u d i 0 在国内，面对着嵌入式数据管理领域新的市场需求，东北大学软件中心凭借着多 年积累的数据库系统和嵌入式系统的开发经验，在大型数据库管理系统o p e n b a s e 的 基础上，研制开发了嵌入式数据库管理系统o p e n b a s em i n i 。北京人大金仓信息技术 嵌入式数据库的设计与实现 有限公司也凭借其强大的研发实力，推出了具有自主知识版权的小金灵嵌入式移动 关系数据库系统k i n g b a s el i f e 硷1 。 以上这些嵌入式数据库系统在功能和性能上具有一定的共性，比如说一般对资源 要求较低，占用内存空间较小，从几十k 到几百k 不等，支持c 编程接口和标准s q l 子集的开发接口，支持o d b c 或j d b c ，能与支持其标准的任意数据库交换数据，支持 双向数据交换能力，实现了中央数据库与嵌入式数据库间的数据双向流动等。但这 些数据库系统也有各自不同的特点，鉴于嵌入式领域的特点，对嵌入式数据库产品 还很难形成统一的标准，对嵌入式数据库管理系统的研究，也还有很多工作要做。 1 3 本文的研究目标和研究内容 目标是在研究现有嵌入式数据库的基础上设计和实现一个具有如下特征的嵌入 式数据库： 1 ) 零配置，程序驱动。 2 ) 实现部分的s q l 9 2 标准。 3 ) 数据库完整存储在磁盘文件中。 4 ) 提供简单明了的a p i 。 本文的研究内容主要包括以下几方面： 1 第一章主要介绍了嵌入式数据库系统研究的意义、国内外的研究现状以及本 文研究的主要内容。 2 第二章主要介绍了嵌入式系统，嵌入式操作系统和嵌入式数据库的特点和体 系结构。 3 第三章对嵌入式数据库进行概要设计和详细设计并初步实现一个可运行的嵌 入式数据库。 4 第四章基于第三章开发完成的e d b 的基础上，设计并实现嵌入式数据采集系 统。 5 第五章对第三章开发的e d b 和第四章开发的数据采集系统进行测试。 6 第六章进行总结与展望。 2 第二二章嵌入式系统与嵌入式数据库 第二章嵌入式系统与嵌入式数据库 2 1 嵌入式系统 2 1 1 嵌入式系统的定义 嵌入式系统( e m b e d d e ds y s t e m ) 是以应用为中心，以计算机技术为基础，并且 软硬件可裁剪，适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的 专用计算机系统3 。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及 用户的应用程序等四个部分组成，用于实现对其他设备的控制、监视或管理等功能。 2 1 2 嵌入式系统的特点 嵌入式系统的核心是嵌入式微处理器，嵌入式微处理器一般具备以下4 个特点h 3 ： ( 1 ) 对实时多任务有很强的支持能力，能完成多任务并且有较短的中断响应时 间，从而使内部的代码和实时内核的执行时间减少到最低限度。 ( 2 ) 具有功能很强的存储区保护功能。这是由于嵌入式系统的软件结构已模块 化，而为了避免在软件模块之间出现错误的交叉作用，需要设计强大的存储区保护 功能，同时也有利于软件诊断。 ( 3 ) 可扩展的处理器结构，以能最迅速地开展出满足应用的最高性能的嵌入式 微处理器。 ( 4 ) 嵌入式微处理器必须功耗很低，尤其是用于便携式的无线及移动的计算和 通信设备中靠电池供电的嵌入式系统更是如此。 2 1 3 嵌入式系统的应用 嵌入式系统的应用前景是非常广泛的，人们将会无时无处不接触到嵌入式产品， 从家里的洗衣机、电冰箱，到作为交通工具的自行车、小汽车，到办公室里的远程 会议系统等等。当嵌入式的无线电芯片的价格可被接受时，它的应用可能会无所不 在。在家中、办公室、公共场所，人们可能会使用数十片甚至更多这样的嵌入式无 线电芯片，将一些电子信息设备甚至电气设备构成无线网络，在车上、旅途中，人 们利用这样的嵌入式无线电芯片可以实现远程办公、远程遥控，真正实现把网络随 身携带瞄3 。 2 2 嵌入式操作系统 2 2 1 嵌入式操作系统的定义 嵌入式操作系统是一种支持嵌入式系统应用的操作系统软件，它是嵌入式系统 3 嵌入式数据库的设计与实现 ( 包括硬、软件系统) 极为重要的组成部分，通常包括与硬件相关的底层驱动软件、 系统内核、设备驱动接口、通信协议、图形界面、标准化浏览器等b r o w s e r 6 。嵌 入式操作系统具有通用操作系统的基本特点，如能够有效管理越来越复杂的系统资 源；能够把硬件虚拟化，使得开发人员从繁忙的驱动程序移植和维护中解脱出来； 能够提供库函数、驱动程序、工具集以及应用程序。 2 2 2 嵌入式操作系统的特点 嵌入式操作系统具有以下一些特点哺1 ： ( 1 ) 体积小。嵌入式系统有别于一般的计算机处理系统，它不具备像硬盘那样 大容量的存储介质，而大多使用闪存( f l a s hm e m o r y ) 作为存储介质。这就要求嵌 入式操作系统只能运行在有限的内存中，不能使用虚拟内存，中断的使用也受到限 制。因此，嵌入式操作系统必须结构紧凑，体积微小。 ( 2 ) 实时性。大多数嵌入式系统都是实时系统，而且多是强实时多任务系统， 要求相应的嵌入式操作系统也必须是实时操作系统( r t o s ) 。实时操作系统作为操作 系统的一个重要分支已成为研究的一个热点，主要探讨实时多任务调度算法和可调 度性、死锁解除等问题。 ( 3 ) 特殊的开发调试环境。提供完整的集成开发环境是每一个嵌入式系统开发 人员所期待的。一个完整的嵌入式系统的集成开发环境一般需要提供的工具是编译 连接器、内核调试跟踪器和集成图形界面开发平台。其中的集成图形界面开发平台 包括编辑器、调试器、软件仿真器和监视器等。 2 3 嵌入式数据库 2 3 1 嵌入式数据库定义 嵌入式数据库是指运行在本机上、不用启动服务端的轻型数据库，它与应用程序 紧密集成，被应用程序所启动，并伴随应用程序的退出而终止。 2 3 2 嵌入式数据库的特点 嵌入式数据库系统有如下主要特点n ：( 1 ) 占用存储空间小( 2 ) 可靠性、可管理 性和安全性( 3 ) 互操作性和可移植性。 2 3 3 嵌入式数据库的关键技术 为了使嵌入式系统能更好地发挥其作用，主要涉及以下几种关键技术发展方向： ( 1 ) 系统的高可靠性技术( 2 ) 系统整体的微型化( 3 ) 数据同步复制技术( 4 ) 系统可定 制能力( 5 ) 系统可移植性与多平台支持( 6 ) 网络支持与数据。 4 第三章嵌入式数据库的分析与设计 第三章嵌入式数据库的分析与设计 本章将讨论如何分析和设计一个嵌入式数据库系统，包括数据库的功能需求、 性能需求、运行环境、开发环境、系统架构以及各模块和模块间的关系等。 3 1 嵌入式数据库的体系结构 嵌入式e d b 是指可在嵌入式设备中独立运行的一种数据库系统，用以处理大量 的、时效性强且有严格时序的数据，它以高可靠性、高实时性和高信息吞吐量为目 标，其数据的正确性不仅依赖于逻辑结果，而且依赖于逻辑结果产生的时间随1 ，嵌入 式系统基本结构如图3 - 1 所示。 图3 - 1 嵌入式系统基本结构 目前嵌入式系统开发中，在嵌入式数据库问题上的多数看法是，嵌入式数据库从 本质上说是一个“内存数据库”，是一个由应用程序管理的内存缓冲池，它在系统 中的作用就是一个供多个实时任务共同使用的共享数据区。这种数据库实际上是一 个嵌入在用户应用软件中的与应用程序不可分割的部分，其功能主要是数据的存和 取，不具有独立性，不是一个真正意义上的数据库系统睁1 。一个完整的嵌入式实时数 据库系统除了包括内存数据库外，还应当含有历史数据库和数据库管理系统d b m s 及 提供给用户的接口函数，整个数据库可由d b m s 完成对数据库的具体配置及各种操作， 例如系统运行前根据实际需要对内存数据库中的记录节点进行增减等配置操作，嵌 入式数据库库的模块结构如图3 - 2 所示。 5 嵌入式数据库的设计与实现 图3 2 嵌入式e d b 的模块结构 3 2 嵌入式数据库的数据模型 嵌入式数据库的关键是数据模型的确立，它决定了数据被访问和操作的方式，应 用程序的性能和可靠性也大部分取决于此。目前嵌入式环境下的数据库系统多数采 用了关系模型结构，这也是商用数据库系统的数据模型，该模型结构是利用二维表 来实现数据存储，利用索引访问和查询数据，这种模型结构是建立在严格的数学基 础上的，结构简单灵活，独立性好，但在嵌入式环境下的内存开销和数据冗余较大， 用户必须对其进行优化，增加了开发数据库系统的难度；有些嵌入式数据库则采用 了网状模型结构，该模型通过指针来确定数据间的显式连接关系，它比关系模型中 利用冗余数据和索引文件要节约大量的存储空间，具有一定的数据独立性和共享特 性，运行效率较高，而且由于它避免了索引操作，比关系型数据库模式要节省存储 空间，数据操作速度也更快n 0 1 。但是这种模型结构比较复杂，尤其当嵌入式系统规 模增大时，其数据库的结构变得非常庞大，可能会影响到系统的实时性能。图3 3 所示的是在相同数目的记录下，关系模型和网状模型的系统开销比较，从图中可以 得知，网状模型因为避免了索引操作使得其开销要小于关系模型n u 。 6 7 嵌入式数据库的设计与实现 3 4 嵌入式数据库的运行过程和开发过程 3 4 1 运行过程 e d b 的运行过程是一个在数据库引擎总控模块的控制下进行的有序协调的过程。 e d b 的运行过程分为5 个步骤n 别。 ( 1 ) 数据库系统初始化 e d b 的初始化调用a p i 的初始化函数启动，初始化数据库系统的全局控制结构， 取数据库的运行状态信息，分配数据库内存空间，e d b 系统初始化时还将对数据字典 表进行确认n 朝。 ( 2 ) 打开或创建字典表 在数据库系统第一次启动时，即数据库第一次被装入时，该字典表是不存在的， 在这里初始化时将创建字典表，为后续操作做好准备。在数据库系统以后的启动过 程中，如果该字典己经存在，数据库系统初始化时将确认字典表是否已存在，此时 如果检查到字典表不存在，将重新打开一个字典表。 ( 3 ) 数据库具体操作 e d b 系统及其具体的字典表操作初始化后就可以在数据库操作引擎控制下调用数 据存取模块或数据库维护模块对数据库进行各种操作了。对基本表的主要操作有： 创建基本表、插入记录、删除记录、修改记录、查找、排序、备份和恢复以及碎片 整理等，我们将在第四章对重要功能的操作流程和实现进行详细介绍。 ( 4 ) 关闭字典表 关闭字典表后可以释放已经分配的输出缓冲区空间、结果集结构空间、控制头结 构、列定义信息等内部结构变量空间，并可以释放该字典表占用的类信息结构。 ( 5 ) 关闭数据库系统 通过调用a p i 的关闭函数实现。主要工作是关闭数据库，释放e b d 系统申请的 全局结构变量空间即d b 结构，释放并分配给e d b 的空间。 实际运行过程中，数据库系统初始化后，若字典表创建成功或己存在的条件下， 可对字典表进行多次的打开操作和关闭操作n 4 1 。 3 4 2 开发过程 e d b 的开发过程是按照软件工程的思想来组织实施的。开发过程依次经历了原型 阶段，需求分析阶段，概要设计阶段，详细设计阶段，编码阶段，测试阶段，以及 维护阶段。 8 第三章嵌入式数据库的分析与设计 在原型阶段，主要是在台式机上围绕着e d b 的一些基本功能，如表创建，记录的 插入、删除、修改等操作，在p c 机上予以实现，以获得对将要开发的系统的一个初 步的认识。实际开发的原型是在l i n u x 环境下实现的。 在需求分析阶段，主要是根据用户的要求，进一步细化系统应该具有的功能和性 能要求，和用户达成一致，并为下一步的系统概要设计打好基础。 在概要设计阶段，基本上确定了系统的体系结构，确定了系统向用户所提供的 a p i 接口，确定了系统各个组成模块之间的关系，确定了系统的一些核心数据结构。 在详细设计阶段，主要是设计各个模块具体函数的伪代码或流程图实现。 在编码阶段，主要工作就是编码并调试，以实现系统预定的功能n 朝。 在测试阶段，测试工作非常重要，除了在系统开发的各个阶段都贯穿了一些测试 的内容外，还专门安排了一个比较长时间的测试阶段。测试阶段包含了功能测试， 健壮性测试，性能测试等多个测试环节，经过测试阶段，系统的质量和稳定性都得 到了比较大的提高。 3 5 概要设计 3 5 1 功能需求 嵌入式数据库系统作为d b b l s ，它应当具备以下功能： ( 1 ) 数据定义和数据存储 这部分内容包括元组的表示，属性的表示，索引的表示，元组和属性的关系， 各种数据类型的表示和存储，如整型( 长整型、短整型) 、字符型、实型、日期类型、 时间类型等。数据文件表的格式和组织，索引文件表的格式和组织，元数据的组织 和存储等等n 钔。 ( 2 ) 数据存取 能实现对数据库的基本操作，如建立表，建立索引，删除表，删除索引，对元 组的检索和更新操作( 插入、删除、修改) ，其它的操作还包括排序、压缩、整理等 功能。必须支持s o ld d l 和d m l 一个较完备的子集。 ( 3 ) 访问接口 嵌入式数据库系统需要提供共应用程序开发人员使用的访问接口，而且应当是 符合s o l 标准的访问接口。 ( 4 ) 缓冲区管理 为提高系统性能，减少磁盘i o 操作，对数据表文件的读写必须提供缓冲机制， 9 嵌入式数据库的设计与实现 操作系统的文件系统提供的文件缓冲是远为不够的，嵌入式数据库系统自身应该有 出色的缓冲区管理功能n 引。 ( 5 ) 内存管理 占用最少的内存资源和内存资源可控制是嵌入式数据库的首要目标。合适的内 存管理策略，不仅有助于达到这个目标，而且有助于保护系统的堆空间，增强系统 的可靠性。 ( 6 ) 数据库管理工具 嵌入式数据库还需要一组实用工具，供用户在线或离线管理数据库，这样的工 具包括数据库元数据的报表打印、数据库一致性的检查、数据库表的数据导入导出 工具、碎片整理和压缩等。 3 5 2 性能需求 衡量嵌入式数据库的性能要求有两个方面，一是作为d b m s 系统，其性能如何， 数据库中最多数据表的个数，数据表的最大文件长度，每个表的最大元组个数，每 元组的最多属性个数，每个表上建立的最多索引数等等，二是作为嵌入式系统软件， 其性能如何，包括内存资源占用，c p u 开销等。前文我们说过，嵌入式数据库和应用 密切相关，所以有些性能指标比如响应时间或事务处理平均时间就难以确定，我们 只能给出合理的参考值要求( 针对特定的硬件平台) 。当然，大多数的指标还是可以 确定的。其它性能要求还包括对可靠性的要求，嵌入式数据库系统要保证在无人管 理的情况下长时间的无故障运行n6 1 。而且，在系统发生故障不能恢复的时候，也不 可干扰或破坏设备中其它部件的正常工作。 嵌入式数据库系统还应当具备良好的可伸缩性，根据不同的应用能够为系统进 行定制，比如定制所需的子模块，定制缓冲区的大小等。嵌入式数据库系统还应满 足较好的可移植性，能够提供开放的接口和其它系统互操作。 3 5 3 运行环境和开发环境 e d b 目前支持的平台是各种嵌入式l i n u x ，具体产品包括各种高端的消费类电子 设备，需要为e d b 搭建嵌入式开发交叉平台，这个平台需要的部件包括：主机( h o s t ) ： 它是开发人员的工作机，一般是桌面系统，分析、设计和文档撰写以及代码编写、 大部分的调试工作等都在主机上完成n 7 1 。目前的主机是r e d h a tl i n u x7 3 ，目标机 ( t a r g e t ) ：它是e d b 实际运行的平台，该平台必须运行嵌入式l i n u x 操作系统。当 e d b 系统基本成型后就需要从主机下载到目标机进行进一步的调试，本系统的目标机 是基于a r m 9 平台的嵌入式l i n u x 系统。 1 0 第三章嵌入式数据库的分析与设计 3 6 详细设计 嵌入式数据库设计流程如图3 - 4 所示，主要包括s q l 解析、词法分析、语法分 析、s q la p i 设计、事物的调度和执行策略、脱机移动事物、日志回滚和故障恢复几 个方面。由于嵌入式数据库系统中的功能较多，限于篇幅，仅对嵌入式数据库系统 中的重要功能设计和实现进行介绍。 d d l 模式文件 d d l 语法解析模块 数据定义模块 数据访问模块 d m l 语法 解析模块 s q l a p i 晶僻荔 兰塑至竖堡苎ll ；苗芝 _ 广i 簇菇“。 缓冲区内部数据结构 图3 4e d b 的体系结构 3 6 1s o l 解析 s q l 语句中具有独立意义的单词，称之为单位体，有时也称为原予。词法分析 的主要目的就是分隔单位体，并将这些单位体按照先后顺序插入单位体链表。每种 单位体的规则和意义各不相同，比如单引号，在单引号内的其他符号都失效，而两 个连续的单引号才表示一个单引号字符。从功能上分析，单位体可以分成7 类：括 号、子查询、数值运算、比较运算、逻辑运算、变量以及其他控制符号。若从可见 性分析，单位体可以分成两类，即可见单位体和非可见单位体。非可见单位体主要 是一些抽象的单位体，比如逻辑单位体。任意一条合法w h e r e 子句，最后经过运算 必须得到一个唯一的抽象的非可见单位体，即逻辑单位体n8 | 。若为1 ，则表示当前 记录符合要求，需要写入结果集：反之，则不符合要求，需要跳过。 解析s q l 语句总体目标是将s q l 语句转换成系统可以理解的格式，这就是语法 分析的工作。这里所谓系统可以理解的格式，是指按照s q l 9 2 标准，判别该s q l 语 句的类型( 查询、删除、修改记录等) ，并根据不同的类型作不同的语法分析。比如 查询语句，总体而言可以分成三个部分。s e l e c t 与f r o m 之间的部分主要描述结果集 嵌入式数据库的设计与实现 输出格式，而f r o m 与w h e r e ( 若无w h e r e 子句，则到s q l 语句结尾) 之间的部分描述 本s q l 语句所涉及的表，w h e r e 子句则是表示查询的条件。语法分析的任务之一就是 将这三个部分分开并留给以后的系统使用，这也是语法分析的结果之一。在语法分 析的过程中，系统需要检查当前s q l 语句的合法性，若不合法则报错退出，并给出 出错信息。 每当语法分析程序解析出一条语句时，就向语句执行列表中插入一个节点，这 个节点的内容包括了该条语句的类型及相应的参数信息。如识别出是c r e a tt a b l e 语句，就将插入节点的t y p e 域设置为s q l c r e a t e t a b l e ( 为每一种语句都定义了一 个标记以标识) ，并将c r e a tt a b l e 的相关参数信息转换为相应的数据结构放入节点 的s t m t 域中。这样当整个脚本文件解析完毕后，所有的语句就会按顺序组成一个语 句执行列表。执行时，遍历这个语句执行列表。通过判断每个节点的类型，就能知 道所要执行的具体函数。如判断到该节点的t y p e 为s q l c r e a t e t a b l e ，相应的建 表函数为e d b _ c r e a t e ( ) 。 3 6 2 语法解析 语法解析是数据库实现要面对的重要问题，此数据库中采用的语法是s q l 语法， 符合采用b n f 范式。显然，语法解析属于编译的范畴，虽然有关课程中已经详细介 绍了词法分析和语法分析的理论，但是离开具体的实现还是有相当的距离，特别是 对于s q l 这样复杂庞大的语法，为了构建完善且可靠的词法分析器和语法分析器有 一定的难度和工作量。可喜的是，在u n i x 世界存在着相关的优秀工具，这些工具能 够帮助我们实现一个专业的词法和语法分析器，这便是f l e x 和y a c c 。 有了这些自动工具，数据库开发者要做的主要工作便是为s q l 语法寻找合适的数 据结构，以及为f l e x 和y a c c 书写正确的脚本。一般的，树型的数据结构对于表示 s q l 语法是合适的，当然考虑到每个语法的特点，我们可能需要为树做某种程度的变 形，而不是标准的树结构。有了合适的数据结构，下一步的工作就是在f l e x 和y a c c 的脚本中指示它们该如何一步一步的生成s q l 解析树。 3 6 3 存储管理 嵌入式数据库的存储管理有两个方面，其一是外部存储管理，即如何组织数据 文件、索引文件，二是内部存储管理。由于嵌入式系统内存资源的紧张，如何使用 内存资源必然是嵌入式软件的热门话题和重要技术点。对于e d b ，内部存储管理涉及 到两个关键问题。 第一个问题是缓冲区管理，它也和外部存储管理密切相关。缓冲区机制是指为 1 2 第三章嵌入式数据库的分析与设计 减少f l a s h 或磁盘i 0 在e d b 和二级存储器之间架设了一块内存空间，其职责是在 查询处理过程中让数据存取模块得到所需的元组，数据存取模块通过某种访问方法 从这些缓冲区读写元组，写入元组也是写到缓冲区上，而不需要直接访问f l a s h 文 件或磁盘系统。这种机制可以大大减少对磁盘的访问，其原因是很多时候我们要访 问的元组就己经在缓冲区上了。 当e d b 初始化时，缓冲区数目将是一个可以设置的参数，不同的应用能够灵活 的设置缓冲区的大小。我们为每个关系都设置一定大小的缓冲区( 本数据库设为8 k ) ， 由于页长度固定，这样此关系对应的缓冲区能够装入8 个页。当需要访问不在缓冲 区中的页时，需要将缓冲区中的某个页写回f l a s h 或磁盘，并调入待访问的页。这 样，为尽量减少颠簸，本系统采用l r u 算法。 第二个问题涉及到动态内存的申请和释放。本数据库是用c c + + 实现的，不可避 免的牵涉到大量的m a l l o c 和f r e e 操作，从系统堆中取得或还出内存。嵌入式系统 中堆是一种需要特别慎重对待的重要系统资源。系统的m a l l o c 允许用户指定任意大 小的区块，在系统堆频繁的分配和释放动态内存，特别是长度各异的内存，容易造 成堆支离破碎，甚至可能使系统崩溃。系统堆越杂乱，区块大小越是参差不等，找 出一个适当的空闲区块的时间更长，效率更低，所谓的通用性必然牺牲效率。另 外，e d b 的动态内存占用需要处于可控制的范围。鉴于这些考虑，本数据库使用了动 态内存管理办法取代了系统的m a l l o c 和f r e e ，它就是所谓的预分配+ 内存池技术。 其主要思想如下：在e d b 初始化时，根据应用规模我们为e d b 预先分配一定数量的 内存，以后e d b 所有的动态内存申请都只从这块内存中取得，这样做一个明显的好 处是基本上不会干扰系统堆。这块内存除非e d b 系统退出，否则这块内存将一直为 e d b 所占。然后，我们在这块内存上使用内存池技术，即将它分成若干个块( c h u n k ) 每个块由一定数量的等长的内存片断( f r a g m e n t ) 组成，比如某个块，它由2 0 个片断 组成，每个片断都是8 字节长，我们称该块为“8 字节一块。通过分析e d b 内部各 个动态数据结构的长度，以及数据库表的属性字段长度和元组长度等因素，我们将 内存池分成如下2 0 种块：”8 字节一块”，1 6 字节一块 ，”2 4 一字节块”，依 8 字节为步进( s t e p ) 一直到“1 2 8 字节一块”，然后是“2 5 6 字节一块”，”5 1 2 字 节一块”， 1 0 2 4 字节一块”和“2 0 4 8 字节一块”。超过2 0 4 8 字节的片断在嵌入 式数据库应用中很少出现，我们简单的将它交由系统堆处理。需要说明的是，这加 块并不是静态的在系统初始时被划分死的，而是在需要它的时候才建立，有些情况 下内存池中可能就只活跃着2 种块，比如“8 字节一块 和“1 6 字节一块”。 嵌入式数据库的设计与实现 将块中的空闲片断由一个链表连接起来，并由一个指针指向表头，这个链表称 为空闲表( f r e el i s t ) 。一共需要2 0 个空闲表。值得注意的是，在实现中无须担心 空闲表会消耗掉可观的内存，我们可以直接在空闲片断上建立这种链表。当然，我 们需要存储这2 0 个空闲表的表头，空闲表带来的额外内存开销也仅限于此。图3 5 给出了空闲表和块的示意图。 图3 5 空闲表和和空闲块不葸图 图3 - 5 中4 号链表表头指向一个“6 4 字节一块 ，该块含有4 个片断，某个片 断中含有一个0 指针表示链表的结束。当e d b 中的某个模块提出动态内存申请时， 内存池将视其大小从特定块中取出一个合适的空闲片断交付给该模块，同时修改空 闲链表的表头指针。“合适”尊循的原则是：如果申请的长度n 在1 2 8 字节以下的， 那么总是交付长度为l 的空闲片断，l 是8 的整数倍值中大于n 的最小数；若申请的 长度大于1 2 8 且小于等于2 5 6 ，那么交付2 5 6 字节的片断，大于2 5 6 小于等于5 1 2 则 交付5 1 2 字节的片断，更大长度的依此类推，直至2 0 4 8 字节。 3 6 4s q l 预处理及简单优化 通过上面的算法，可以得到计算机能够理解的单位体栈( 也称为单位体链表、原 子链表) ，这样就具备了执行该s q l 语句的必要条件。为了提高效率，需要对s q l 语 句做部分预处理，将冗余信息去除掉。冗余的信息是指可以直接计算出结果的信息， 比如无效括号、子查询、数值运算、比较运算、集合运算以及逻辑运算等等。具体 为：( 1 ) 无效括号是指括号内只含有一个单位体：这样就可以把该单位体前后的左 括号和右括号删除；( 2 ) 子查询必须要在扫描之前获得其结果，这样做的好处是避 免在扫描每条记录时再去计算其结果，其优化结果为一个集合单位体；( 3 ) 数值运 1 4 第三章嵌入式数据库的分析与设计 算包括混合运算，若这些运算符前后不是变量，则可提前计算；比较运算主要包括 、 = 、 ； s t r u c ti n d e x c h a r * z n a m e ； 卜n a m eo ft h i si n d e x | i n tn c o l u m n ；l 蠢n u m b e ro fc o l u m n si nt h et a b l eu s e db yt h i si n d e x | i n t * a i c o l u m n ；| 肆w h i c hc o l u m n sa r eu s e db yt h i si n d e x 1 s ti s0 | t a b l e p t a b l e ；| 嶙t h es q l t a b l eb e i n gi n d e x e d | h a tm u m ；| 鼻p a g ec o n t a i n i n gr o o to ft h i si n d e xi nd a t a b a s ef i l e 囊| u 8a u t o i n d e x ；严t r u ei fi sa u t o m a t i c a l l yc r e a t e d ( e x ： b yu n i q u e ) 幸 i n d e x * p n e x t ； 产t h en e x ti n d e xa s s o c i a t e dw i t ht h es a m et a b l e 宰 ) ； “。 一 s t r u c tt o k e n c o n s tc h a r 木z ：严t e x to ft h et o k e n n o tn u l l - t e r m i n a t e d t 宰 ) ； ( 1 ) 创建基本表 创建基本表通过a p i 调用c r e a t et a b l e 实现。由使用者输入基本表名和该基本 表的属性列定义，在接口处理层将用户的输入转变为e d b 系统能识别和操作的创建 表结构。 当遇到c r e a t e ，t a b l e 和表名以后，c r e a t e t a b l e 函数被调用。此函数首先用新 建表的表名与字典记录表中的表名比较，如果新建表表名已经存在，则提示错误退 1 6