嵌入式数据库技术研究.doc

嵌入式数据库技术研究Research Technology of EmbeddedDatabase SystemIV摘 要随着移动计算时代的到来，嵌入式操作系统对移动数据库系统的需求为数据库技术开辟了新的发展空间。嵌入式数据库技术目前已经从研究领域逐步走向了广泛的应用领域。随着移动终端的普及，人们对移动数据的实时处理和管理要求不断提高，嵌入式数据库也越来越显示出其优越性。本文阐述了嵌入式系统和嵌入式数据库系统在系统功能、性能、体系结构等方面的特点，同时详细分析了系统的实现过程。并着重对嵌入式数据库中的几项关键技术进行了分析、研究。首先，实现了嵌入式数据库的基本功能。其次对嵌入式数据库系统中的存储管理、查询管理和数据同步复制等几项关键技术进行了探究，经过大量的资料查阅、分析和探究，找出了影响系统性能的关键所在：(1)外存I/O的次数；(2)重复解析SQL语句的次数。对以上问题进行了深入分析和研究。关键词：嵌入式系统，嵌入式数据库，存储管理，查询管理；AbstractWhen mobile computing age comes,demand for embedded operating system to mobiledatabase system opens up a new field in database technology.At present,technology inembedded database system has developed from research stage into application.As mobileterminal becomes widespread,real-time process and management in this area enablesembedded database system to turn out to be more powerful.This paper explains the functions,performance,and structure of the embedded databasesystem.Its implementation is analyzed.And the key techniques of the embedded databasesystem are pinpointed.First of all,the basic function of the embedded database system is implemented.Secondly,the key techniques of the embedded database system in this experiment,such asmemorizer management,query management and data synchronization replication,are furtherresearched.The massive materials consult,the analysis and the research had been carried on and the key effects on the performance of the system had been discovered:(1)numbers of I/Oof external storage;(2)numbers of repetition of parse SQL.Through the analysis and theresearch on the questions above,this paper proposes and testifies the effective solutions on basis of experiment.Keywords: Embedded System，Embedded Database System，Memorizer Management ，Query Management；目 录第一章 引言11.1 选题背景11.2 研究目的和意义11.3 嵌入式数据库系统的发展现状和应用前景2第二章 嵌入式系统32.1 嵌入式系统概述和特点32.1.1 嵌入式系统概述32.1.2 嵌入式系统的发展32.1.3 嵌入式系统的特点42.2 嵌入式操作系统52.3 嵌入式应用软件6第三章 嵌入式数据库73.1 嵌入式数据库概述73.2 嵌入式数据库的特点73.3 嵌入式数据库的体系结构93.4 嵌入式数据库的关键技术103.5 嵌入式数据库的主流产品113.5.1 国外主流产品113.5.2 国内主流产品12第四章 嵌入式数据库的实现技术134.1 嵌入式数据库的存储管理134.1.1 存储数据模型134.1.2 数据的存储组织134.1.3 数据存取性能优化154.2 词法、语法分析及预处理技术164.2.1 词法分析174.2.2 语法分析194.2.3 预处理技术224.3 嵌入式数据库的查询管理234.3.1 查询语句的执行244.3.2 索引结构的设计与实现244.3.3 查询机制的优化274.3.4 嵌入式数据库的基本操作28第五章 结束语29致谢30参考文献31本科毕业论文第一章 引言1.1 选题背景数据库技术是应数据管理任务的需要而产生的。随着计算机技术从科学计算向数据处理的扩展，数据库系统应运而生。数据库系统的出现使信息系统的重心发生了转移，从以加工数据的程序为中心转向以数据共享为核心。随后，不断涌现的新应用需求又推动着数据库技术向前发展，从第一代的网状、层次数据库系统、第二代的关系数据库系统，发展到了第三代以面向对象模型为主要特征的数据库系统。今天，新的数据管理需求推动着数据库技术向“深度计算”和“普及计算”两端发展。高端的超大型数据库系统解决复杂数据类型如视频音频数据、多媒体数据或“行为”数据的处理问题，满足海量数据的存储和存取，它们将运行在固定的巨型主机服务器上，其特点是大、强、快；而低端的精小型数据库系统将解决个性化数据的存储和处理需求，它们将嵌入各种电子设备和移动设备中，其典型特色是小、灵、易。随着科技的发展和社会的进步，嵌入式计算机系统获得了越来越广泛的应用。在办公自动化领域，消费领域，通信领域，工业控制领域和军事领域等等领域中，都可以见到嵌入式系统的影子。尤其是在办公自动化、消费电子和通信领域中，可以说嵌入式系统应用得非常普遍。毫无疑问，伴随着嵌入式市场的蓬勃发展，会有越来越多的嵌入式设备希望得到嵌入式数据库管理系统的支持，进行数据的统一管理。1.2 研究目的和意义随着网络技术的迅速发展和不断渗透，在任何时候、任何地方都能接入信息网获取所需的信息将成为21世纪新型人类的普遍需求，而且也必将成为新的信息系统的显著特征。嵌入式数据库不仅具有传统数据库的主要功能，还具有嵌入式和支持移动技术两种特性，因此通常被用在诸如掌上电脑、PDA、车载设备、移动电话等嵌入式设备中。嵌入式数据库系统属于企业的核心产品，它能够提高嵌入式应用程序的开发效率，增加嵌入式应用的可移植性，节省的开发费用，缩短开发时间；设计并实现嵌入式数据库系统，有利于企业掌握核心技术，提高企业的核心竞争力。随着这种数据库技术的兴起，人们将不再受单一操作系统的限制，可以随时随地处理业务，传递信息。因此，如何高效的使用嵌入式数据库以及对嵌入式数据库的设计、实现都是非常值得我们去研究和探讨。1.3 嵌入式数据库系统的发展现状和应用前景嵌入式数据库技术目前已经从研究领域向广泛的应用领域发展，各种嵌入式数据库产品纷纷涌现。尤其是对移动数据处理和管理需求的不断提高，紧密结合各种智能设备的嵌入式数据库技术已经得到了学术界、工业界、军事领域、民用部门等各方面的重视，不断实用化。嵌入式数据库技术的许多特性都与信息时代的不断进步的需求相吻合,有着广阔的发展空间。嵌入式数据库技术配合GPS技术，可以用于智能交通管理、大宗货物运输管理和消防现场作业等。嵌入式数据库技术还在零售业、制造业、金融业、医疗卫生等领域展现了广阔的应用前景。随着移动计算、嵌入式数据库和无线数据通信等相关技术迅猛发展，嵌入式数据库将成为信息社会的重要支柱。基于嵌入式数据库的应用可划分为水平应用和垂直应用。水平应用，是指应用方案能够用于多种不同行业，只需要极少的定制工作；而垂直应用则是针对特定行业的应用，数据处理具有独特性。随着移动计算、普遍化计算向现实生活的迈进，各种嵌入设备或移动设备将成为人民生活中不可或缺的一部分，那时的嵌入式数据库技术将使得数据库成为无处不在的数据库。第二章 嵌入式系统2.1 嵌入式系统概述和特点2.1.1 嵌入式系统概述 进入后PC时代，嵌入式系统正向社会各个领域渗透，形形色色的嵌入式系统产品将拥有最大的市场。当前流行的嵌入式系统产品包括信息电器、移动计算设备、网络设备、工控与仿真设备等几种类型。嵌入式系统是指以应用为中心，以计算机技术为基础，软、硬件可裁剪，适应于应用系统对功能、可靠性、成本、体积和功耗严格要求，嵌入于各种设备及应用产品内部的专用的计算机系统。它是将先进的计算机技术、半导体技术及其电子技术与各个行业的具体应用相结合后的产物，一般由嵌入式处理器、外围硬件设备、嵌入式操作系统以及嵌入式应用软件等四个部分组成，如图2-1所示。随着电子集成技术、计算机技术、软件工程技术等的日趋成熟和完善，嵌入式系统正以其得天独厚的优势，广泛地应用于各个行业，其数量之大、种类之多，标志着嵌入式系统的应用发展浪潮己经来临。图2-1 嵌入式系统体系结构2.1.2 嵌入式系统的发展嵌入式系统至今已有30多年的历史了，其技术的发展大致分为以下四个时期：第一阶段是以单芯片为核心的可编程控制器形式的系统，同时具有与监测、伺服、指示设备相配合的功能。这种系统大部分应用于一些专业性极强的工业控制系统中，一般没有操作系统的支持，通过汇编语言编程对系统进行直接控制，运行结束后清除内存。这一阶段系统的主要特点是：系统结构和功能都相对单一，处理效率较低，存储容量较小，几乎没有用户接口。由于这种嵌入式系统使用简便、价格很低，以前在国内工业领域应用较为普遍，但是已经远远不能适应高效的、需要大容量存储介质的现代化工业控制和新兴的信息家电等领域的需求。第二阶段是以嵌入式CPU为基础、以简单操作系统为核心的嵌入式系统。这一阶段系统的主要特点是：CPU种类繁多，通用性比较弱，系统开销小，效率高。操作系统具有一定的兼容性和扩展性，应用软件较专业，用户界面不够友好；系统主要用来控制系统负载以及监控应用程序运行。第三阶段是以嵌入式操作系统为标志的嵌入式系统。这一阶段系统的主要特点是：嵌入式操作系统能运行于各种不同类型的微处理器上，兼容性好；操作系统内核精小、效率高，并且具有高度的模块化和扩展性；具备文件和目录管理、设备支持、多任务、网络支持、图形窗口以及用户界面等功能;具有大量的应用程序接口(API)，开发应用程序简单；嵌入式应用软件丰富。第四阶段是以基于Internet为标志的嵌入式系统，这是一个正在迅速发展的阶段。目前大多数嵌入式系统还孤立于Internet之外，但随着Internet的发展以及Internet技术与信息家电、工业控制技术等结合日益密切，嵌入式设备与Internet的结合将代表着嵌入式技术的真正未来。 2.1.3 嵌入式系统的特点嵌入式系统同通用型计算机系统相比具有以下特点：（1）嵌入式系统通常是面向特定应用的嵌入式CPU与通用型的最大不同就是嵌入式CPU大多工作在为特定用户群设计的系统中，它通常都具有低功耗、体积小、集成度高等特点，能够把通用CPU中许多由板卡完成的任务集成在芯片内部，从而有利于嵌入式系统设计趋于小型化，移动能力大大增强，跟网络的耦合也越来越紧密。（2）嵌入式系统是集成先进技术的嵌入式系统是将先进的计算机技术、半导体技术和电子技术与各个行业的具体应用相结合后的产物。这一点就决定了它必然是一个技术密集、资金密集、高度分散、不断创新的知识集成系统。（3）嵌入式系统是按需定制的嵌入式系统的硬件和软件都必须高效率地设计，量体裁衣、去除冗余，力争在同样的硅片面积上实现更高的性能，只有这样才能在具体应用中对处理器的选择更具有竞争力。（4）嵌入式系统具有较长的生命周期嵌入式系统和具体应用有机地结合在一起，它的升级换代也是和具体产品同步进行，因此嵌入式系统产品一旦进入市场，具有较长的生命周期。（5）嵌入式系统需要进行软件固化为了提高执行速度和系统可靠性，嵌入式系统中的软件一般都固化在存储器芯片或单片机本身中，而不是存贮于磁盘等载体中。（6）嵌入式系统需要独特的开发环境嵌入式系统本身不具备自举开发能力，即使设计完成以后用户通常也是不能对其中的程序功能进行修改的，必须有一套开发工具和环境才能进行开发。2.2 嵌入式操作系统操作系统是通用计算机系统必不可少的系统软件，是整个计算机系统的灵魂。它通常是一个复杂的计算机程序集，提供操作过程的协议或行为准则。以嵌入式处理器为中心，开发人员搭建好硬件电路时仅提供裸机运行平台，要使整个系统有限的硬件资源充分的利用起来，需要嵌入式操作系统的软件支持。嵌入式操作系统相对于普通操作系统而言，只相当于其最基本的内核部分，或者说只具有操作系统最基本的功能，如中断处理、进程调度、存储管理等，这是与嵌入式应用的体积小、重量轻的特点相适应的。一般来说，嵌入式操作系统具有如下特点。稳定性：嵌入式系统常常需要在几乎没有人工干预的情况下完成高度专业化和实时的工作，这就要求嵌入式操作系统的性能非常稳定。精练高效：嵌入式系统中的硬件条件一般比较苛刻，可用资源很少，要在如此紧张的资源下很好地完成预定功能，要求嵌入式操作系统必须尽可能地精练、高效，而一些嵌入式环境中用不到的复杂功能则应该取消，以减小系统开销。可裁剪：嵌入式操作系统作为操作系统，当然具有一定的通用性，能够适应多种平台和多种硬件环境，但是为了适应不同用户的不同应用环境而有能够避免冗余，就需要具有很好的可裁减性能，是用户可以根椐需要对各个组件进行裁剪和优化，得到一个具有针对性的操作系统。代码固化：嵌入式系统没有外存，其操作系统的代码需要固化在ROM中，系统加电后自动运行。此外嵌入式操作系统还常常具有一些其他的特点，包括：启动速度快，具有实时性，能够适应多种处理器平台等。近几年来，随着3G浪潮的影响，晶体管集成度的大幅度提高，市场对智能终端等具有复杂功能的嵌入式系统的需求日益高涨，嵌入式操作系统也在迅速发展。出现了不少短小精干、功能强大的嵌入式操作系统，它们几乎就是一个桌面型操作系统微缩版本，比如微软公司的WINCE以及后来的Embedded XP，各种嵌入式的Linux，3COM公司的Palm OS，Wind River公司的VxWorks，QNX等。2.3 嵌入式应用软件近几年来，伴随着计算技术的全面进步，网络技术的快速发展，嵌入式系统发展尤为迅速，一些嵌入式系统的功能比以前大大地增强了，嵌入式处理器的处理能力有比以前大大提高了，已经能够处理一些比较复杂的事务了，甚至可以作为一些大型服务器移动客户端了，简直就成了一台可随身携带的个人电脑。数字化产品要求强大的网络和多媒体处理能力、易用的界面和丰富的应用功能。嵌入式应用软件作为嵌入式系统的核心，己经成为数字化产品设计创新和软件增值的关键因素。当前，嵌入式浏览器、嵌入式多媒体套件、嵌入式GUI、嵌入式中文、嵌入式应用套件、嵌入式Java和嵌入式无线通讯软件己成为嵌入式应用软件的基本要素，能够单独或组合应用。在嵌入式应用程序的设计开发中，同样需要重点考虑实时性、可靠性、系统成本等方面的因素。第 6 页本科毕业论文第三章 嵌入式数据库3.1 嵌入式数据库概述从数据库技术的发展过程来看，计算环境和数据库技术基本保持着一种同步发展的态势，互相影响、互相促进。移动计算的概念是对“任何时间、任何地点的立即通讯”的扩展。在分布式计算的基础上，计算环境进一步扩展为包含各种移动设备、具有无线通信能力的服务网络，构成了一个新的计算环境，即移动计算环境。相应地，数据库系统先后出现了集中式数据库系统、分布式数据库系统、B/A/S多层结构的数据库系统、嵌入式数据库和移动数据库。当然，这些系统也可以共存在同一个计算环境中。嵌入式数据库系统的兴起可以归功于便携式计算设备的开发兴起。由于这些设备具有通讯能力，用户不仅用它们存储设备本身产生的大量数据，而且需要从中心企业下载以便脱线处理，因此，需要这些设备具备成熟的数据管理能力，所需功能常常如此复杂以至于平坦的文件系统不足以处理和操纵这些数据，这就促进了对嵌入式数据库的需求。嵌入式数据库还可以嵌入到大型软件系统或设备中，处理和存储来自所在设备和其他地方的数据。嵌入式数据库系统地设计目的，是在最小的干涉和最小的系统影响下进行数据存储和数据恢复。由于嵌入式数据库系统常常需要对环境做出实时反应，此概念建立在实时和近似实时的嵌入式计算中，应准确地称之为嵌入式实时数据库系统。一般说来，嵌入式数据库可以从系统的体系结构方面来定义：嵌入式数据库系统是支持移动计算或某种特定计算模式的数据库管理系统，数据库系统与操作系统、具体应用集成在一起，运行在各种智能型嵌入设备或移动设备上。其中，嵌入在移动设备上的数据库系统由于涉及数据库技术、分布式计算技术，以及移动通讯技术等多个学科领域，目前已经成为一个十分活跃的研究和应用领域嵌入式数据库或称为嵌入式移动数据库（EDBMS）。3.2 嵌入式数据库的特点嵌入式数据库系统是指支持移动计算或某种特定计算模式的数据库管理系统，它通常与操作系统和具体的应用集成在一起，运行在嵌入式或者移动设备上。嵌入式数据库技术涉及嵌入式、数据库以及移动通讯等多个学科，已经成为数据库技术发展的一个新方向，图3-1表示了嵌入式数据库在嵌入式系统中的位置。图3-1 嵌入式系统结构从上述嵌入式系统的特点可以看出，嵌入式数据库系统本质上是由通用数据库系统发展而来，在某些方面与大型数据库相似，它可以是层次、网状或是关系型的数据库，也可以是面向对象式的，但是嵌入式数据库系统和通用型数据库系统在运行环境、应用领域等许多方面都是不一样的，所以，不能简单地把嵌入式数据库系统看成是通用数据库系统在嵌入式设备上的缩微版。与大型数据库相比，嵌入式数据库有其不同的特点：（1）占用磁盘空间小，占用内存资源少为了使嵌入式数据库所需的磁盘空间小，嵌入式数据库不必包含大型数据库所具有的全部功能，这一特点可使开发者简化开发过程。除此之外，还可以通过限制数据结构的数量和大小，如数据表、记录行等其它技术来减少嵌入式数据库所需要的磁盘空间。嵌入式设备的内存空间较小，一般为几百K或者几M之间，这就给嵌入式数据库提出了一个新的难题：必须能运行在有限的内存空间中。同时，有些嵌入式设备只有RAM和ROM，没有其它的磁盘空间存在，这样，又存在着另一种情况：要求嵌入式数据库能够在只存在内存的情况下运行。（2）可靠性、可管理性和安全性手持装置中的嵌入式数据库通常使用在移动环境下；信息技术支持人员无法对其提供现场技术支持。因此，嵌入式数据库必须可靠，而且能在无需人工管理的情况下运行。鉴于嵌入式数据库的这一特点，对于嵌入式系统中使用的数据库来说，自身可靠性、可管理性和安全性显得特别重要。（3）互操作性和可移植性一般嵌入式数据库都是针对具体的开发平台和操作系统设计和实现的，但为了保证能与其它的嵌入式数据或大型企业数据库进行通信，数据库开发人员在开发系统的过程中应能提供一定的机制实现与其它数据库之间的互操作性。同时嵌入式应用的领域非常广泛，所采用的实时操作系统和硬件环境也千差万别，为了适应这种差异性，数据库开发人员还必须考虑嵌入式数据库的可移植性问题。（4）可剪裁性嵌入式应用对嵌入式数据库系统的要求常常差别很大。一个嵌入式应用一般不会使用嵌入式数据库系统所提供的所有功能，因此，为了节省磁盘空间和提高效率，嵌入式数据库必须支持可剪裁性，这样开发人员才能够根据特定的应用定制嵌入式数据库的功能。3.3 嵌入式数据库的体系结构基于嵌入式数据库系统功能、特点和需求，我们采用当前流行的三层体系结构。如图3-2。在这三个层次中，位于最上层的是移动终端的嵌入式数据库，它具有易用性和便携性，但数据容量最小；而位于最低层的是服务器端后台数据库，它的数据容量大且安全性好、可靠性高，但只能存放于台式机上，难以满足移动计算的需求；中间层的同步模块具有双向数据交换能力，通过数据同步使得嵌入式数据库和后台数据库中的数据保持一致。图3-2 嵌入式数据库体系结构通过这三层的相互配合，系统兼得了嵌入式数据库和海量数据库的特点，用户既用到了嵌入式数据库“无所不在”的计算能力，又避免了其容量小、功能不完备所带来的不便。这种三层体系结构在当前的几种主流嵌入式数据库系统中也得到普遍使用。3.4 嵌入式数据库的关键技术由于移动设备的资源限制，嵌入式数据库一般和应用系统集成在一起，作为整个应用系统的前端而存在，而它所管理的数据集可能是后端服务器中数据集的子集或子集的副本。嵌入式数据库系统必须完善解决下面各项关键问题中的技术：（1）备份恢复嵌入式数据库的备份和恢复与大型DBMS管理数据库不同，不能简单以独立的服务或类似形式进行，而要按照某种简化方式完成。（2）复制与同步嵌入式数据库一般采用某种数据复制模式（上载、下载或混合方式）与服务器数据库进行映射，满足人们在任意地点、任意时刻访问任意数据的需求。由于存在数据复制，则在系统中各个应用前端和后端服务器之间可能需要各种必要的同步控制过程，甚至某些或全部应用前端、中间也要进行数据同步。（3）事务处理嵌入式数据库系统中的事务处理在前端可以简单化，但在整个应用系统中可能需要结合移动计算环境的特征进行事务处理控制。（4）安全性许多应用领域的嵌入式设备是系统中数据管理或处理的关键设备，因此嵌入式设备上的数据库系统对存取权限的控制较严格。同时，许多嵌入式设备具有较高的移动性、便携性和非固定的工作环境，也带来潜在的不安全因素。同时，某些数据的个人隐私性又很高，因此在防止碰撞、磁场干扰、遗失、盗窃等对个人数据安全的威胁上需要提供充分的安全性保证。（5）系统快速启动嵌入/移动设备的系统可靠性和可用性相对于固定主机而言一般相对偏低，因此发生系统故障的概率可能大大提高。因此，在这样的计算环境或计算平台上必须保证系统在发生不可软件纠错的情况下能够通过硬件进行系统的快速启动。此外，如果系统所嵌入的某种移动设备支持实时应用，则嵌入式数据库系统还要考虑实时处理的要求。这是因为设备的移动性，如果应用请求的处理时间过长，任务就可能在执行完成后得到无效的逻辑结果，或有效性大大降低。因此，处理的及时性和正确性同等重要。3.5 嵌入式数据库的主流产品嵌入式数据库市场一般不是直接面向用户而是面向设备制造商，设备制造商将嵌入式数据库系统嵌入到设备和应用中，在应用初期，嵌入式数据库主要用于提供对大型、数据密集型应用的数据管理。如今设备中的嵌入式数据库可以与中心数据库通讯，具有与其他设备同步的功能。3.5.1 国外主流产品（1）Sybase公司Sybase iAnywhere就是一款优秀的嵌入式数据库，目前已经获得很广泛的应用，同时也提出了完整的解决方案，Sybase也是最早推出嵌入式数据库产品的厂商。（2）DB2 Satellite Edition和DB2Everywhere是IBM公司推出的嵌入式数据库系统，前者运行于膝上机，它包括数据复制工具，用于使嵌入式系统同集中的公司数据库保持同步；后者运行于Windows CE和PalmOS的手持设备。（3）Oracle推出了Oracle Lite的移动数据库，它也可以允许膝上机、手持PC和蜂窝电话用户同公司数据库方便地进行复制和同步。（4）Microsoft也有SQL Server for Windows CE产品，简称SSCE，可以运行于Windows CE之上，并且与桌面计算机上的SQL Server6.5/7.0/2000等版本保持兼容。（5）伯克利大学开发的Berkeley DB是一个开放源码的嵌入式数据库开发包，是一个可直接连接进程序的库文件。Berkeley DB的一个很重要的特点就是高速存储，在高流量、高并发的情况下，Berkeley DB的性能表现比较出色。（6）SQLite是PHP5中集成的一个轻巧的内嵌式数据库产品，与Berkeley DB相比，在操作语句上更类似于关系型数据库的产品。（7）Polyhedra是一款支持SQL的C/S数据库引擎，可以运行在桌面、服务器和嵌入式操作系统上。3.5.2 国内主流产品（1）小金灵嵌入式数据库系统（Kingbase Lite）是人大金仓研发的拥有自主知识产权的软件产品，目前也是人大金仓的核心产品。其系列产品包括支持移动计算的低端产品、移动计算的高端产品、信息电器的嵌入产品和掌上电脑通用数据库产品。此外，还包括一系列方便实用的应用开发与管理工具，包括小金灵应用开发构件库、小金灵数据库中心管理工具和小金灵同步应用管理器等。（2）OpenBASE Mini嵌入式数据库管理系统是东软集团研制、开发的OpenBASE产品系列中的一员。它与该产品系列中的其它成员（OpenBASE多媒体数据库管理系统、OpenBASE WEB应用服务器、OpenBASE Secure安全数据库系统）一起，涵盖了企业应用、Internet/Intranet、移动计算等多种应用领域，具有多样的应用模式，形成了OpenBASE而向各种应用的全方位解决方案。第四章 嵌入式数据库的实现技术4.1 嵌入式数据库的存储管理数据的存储、组织、查询和管理是数据库管理系统的最基本的功能，也是数据库管理系统中最为频繁和对可靠性要求最高的操作，因而数据库管理系统在存储管理上的设计思想、处理策略和实现算法不仅直接决定着存储管理子系统的性能和可靠性，也直接关系到整个数据库管理系统的性能和它的健壮性。4.1.1 存储数据模型当前流行的数据库管理系统基本上都采用关系数据模型。关系模型己经成为数据库中数据模型事实上的标准，采用关系数据模型有利于为广大开发社区接受。同时关系模型的描述能力比较强，效率高。关系模型具有完整的理论基础，已经非常成熟。嵌入式数据库还可以采用对象模型，以及类似XML的描述方式，但是与关系数据模型相比，无论是空间存储效率还是运行效率都要更低；其次，开发者所追求的丰富的表现力、易理解的数据描述方式，都不应该是数据库所应承担的上作。这些工作应该基于关系数据库，在数据库之上来实现，如现在出现的OR-Mapping技术，可以很好地实现对象模型到关系模型的映射，而且具有很高的效率。对于嵌入式计算，数据库应该是轻量级的，不宜采用面向对象模型。嵌入式设备的一个主要特征是其资源紧张性。另外，嵌入式数据库本质上还是面向个人服务的数据库管理系统，数据管理的功能相对于传统的企业级数据库来说要求相对较弱。基于上述原因，这里我们将采用效率更高的关系模型。4.1.2 数据的存储组织存储组织包括数据表示和存储空间管理两个方面。数据表示是数据库中应用数据的物理存储的表现方式，它受到数据库系统所采取的存储模型的制约。存储空间组织是对存储设备可用存储空间的应用组织策略，它的目标有两个：高效利用存储空间和为快速的数据存取提供便利。在关系型数据库管理系统中，数据字典、索引、应用数据是存储的主要内容。（1）数据字典对关系数据的描述存储在数据库的数据字典中。与数据本身相比，数据字典的特点是数据量比较小，使用的频率高，因为任何数据库操作都要参照数据字典的内容。数据字典在网状、层次数据库中常常用一个特殊的文件来组织。所有关于的数据的描述信息存放在一个文件中。关系数据库中数据字典的组织通常与数据本身的组织相同。数据字典按不同的内容在逻辑上组织为若干张表，在物理上就对应若干文件而不是一个文件。由于每个文件中存放数据量不大，可简单地用顺序文件来组织。（2）索引索引是关系数据库的存取路径。在网状和层次数据库中，存取路径是用数据之间的联系来表示的，因此己与数据结合并固定下来。关系数据库中，存取路径和数据是分离的，对用户是隐蔽的。存取路径可以动态建立、删除。存取路径的物理组织通常采用B树类文件结构和HASH文件结构。在一个关系上可以建立若干个索引。有的系统支持组合属性索引，即在两个或两个以上属性上建立索引。索引可以由用户用CREATE INDEX语句建立，用DELETE INDEX删除。在执行查询时EDBMS查询优化模块也会根据优化策略自动地建立索引，以提高查询效率。由此可见，关系数据库中存取路径的建立是十分灵活的。在嵌入式数据库中，工作版本常驻主存，数据的文件形式组织不是重点，但在主存中，仍然需要构建快速的存取路径才能取得高的存取效率；而且，在数据从外存调入主存时，文件型索引将加快这一过程。（3）应用数据关于数据自身的组织，EDBMS可以根据数据和处理的要求自己设计文件结构，也可以从操作系统提供的文件结构中选择合适的加以实现。目前，操作系统(包括嵌入式操作系统)提供的常用文件结构有：顺序文件、索引文件、索引顺序文件、HASH文件和B树类文件等。数据库中数据组织与数据之间的联系是紧密结合的。在数据的组织和存储中必须自接或间接、显示或隐含地体现数据之间的联系，这是数据库物理组织中主要考虑和设计的内容。在网状和层次数据库中，常用邻接法和链接法实现数据之间的联系。对应到物理组织方式中，就要在操作系统己有的文件结构上实现数据库的存储组织和存取方法。例如IMS数据库中，操作系统提供的低级的存取方法有SAM，ISAM，VSAM，OSAM。IMS数据库管理系统在此基础上设计了HSAM，HISAM，HDAM，HIDAM四种数据库的存储组织和相应的存取方法。其中HSAM层次顺序存取方法按照片段值的层次序列码的次序顺序存放各片段值。而层次序列码正体现了数据之间的父子和兄弟联系，这是一种典型的按物理邻接方式实现数据之间联系的方法。在这种存储方法中，整个数据库中不同片段型的数据均存储在一个SAM文件中。网状数据库中最常用的组织策略是：各记录型分别用某种文件结构组织，记录型之间的联系SET用指引元方式实现。即在每个记录型中，增加DBMS控制和维护的系统数据项指引元，它和用户数据项并存于同一个记录中。关系数据库中实现了数据表示的单一性。实体及实体之间的联系都用一种数据结构“表”来表示。在数据库的物理组织中，每一个表通常对应一种文件结构。因此数据和数据之间的联系两者组织方式相同。在嵌入式数据库中，数据将分为“永久版本”和“临时版本”。数据库在运行的大部分时间中都只关心临时版本，只在系统空闲或显式要求的情况下才将临时版本中的数据更新到永久版本中。这是一种乐观的持久化策略。因此，对嵌入式数据库来说，我们首先关注的是数据在主存中的高效的存取，其次，才会考虑数据的文件组织形式，尽可能地提高数据在内外存之间的调入、调出效率。4.1.3 数据存取性能优化数据库的一个重要作用就是存储数据，并且要求可重复读取，因此数据必须存储在具有永久存储能力的存储介质上。但数据库管理系统在运行时必须驻留在内存中，它对数据的操作不能通过自接操纵永久性存储介质来实现，必须将数据调入主存，处理完之后，再写回永久性存储介质。对于传统关系数据库系统来说，这是通过设立内存缓冲区来实现的。当需要某些数据时，便将数据交换进缓冲区。缓冲区是数据库的一种策略，可以有效减少外存I/O的次数。但缓冲区的管理尤其是缓冲区页面的调度、页面的替换以及页面的写出都相当的复杂，程序的代码量比较大，占用的内存页面也很多。对于一个计算能力有限，存储资源紧张的嵌入式移动终端来说，运行在其上的嵌入式数据库管理系统应采取不同于传统数据库的设计理念。它应当尽量利用操作系统提供的便利，避免提供与操作系统重复的机制，避免通过增加模块来强化某些操作系统本身已经提供的操作。这是嵌入式数据库内核微型化思想的体现。因此，嵌入式数据库避免直接操作外存，而使用操作系统提供的文件系统接口实现外存处理；同时，不再使用数据缓冲区，而使用高活跃度数据存储区域替代，两者的不同在于前者在内存中按页面来组织缓冲区，每个页面对应磁盘上的一个存储块，后者则以记录为单位存储频繁被存取的数据。同时，因为数据字典占用空间很小且存取频繁，所以将其常驻内存。实际上，操作系统也在内存中提供了文件缓冲区，用以减少外存I/O的次数，提高外存读取的效率。它与高活跃度数据存储区域的作用并不重合，后者直接针对数据库系统的特点而设计，可以根据数据库的特点为其设计调入调出算法。实践证明，数据经常访问的数据一般不到其数据总量的20%，因此高活跃度数据存储区域的存在可以极大地降低外存I/O的次数。操作系统的数据缓冲可在各方面都更类似于传统数据库系统的数据缓冲区，而且它不是为某种特定类型的应用而设计的，它是全局的内存缓冲区域，为运行在操作系统中的所有应用访问外存时提供频繁读取块的缓冲。在外存中，永久性地存储着数据库的数据字典、索引和应用数据。通过操作系统的文件系统，数据库将数据字典全部装入主存，并将活跃度高的那部分数据库数据也装入主存。对数据的操作都在内存中进行，当事务提交时，不马上将数据永久化到外存中，而是由数据写出线程负责周期性地将发生了变化的数据写回外存。我们采取了一种乐观的数据持久化策略。这是因为通常被更改了的数据很快会被再次修改，延迟写出可以有效减少外存I/O的次数；其次，由专门的数据写出线程负责写出上作简化了系统在事务处理过程中的复杂度，现在事务不必关心数据的持久化问题。最后，数据写出线程己经可以在一定程度上保护用户的工作不会被丢失。嵌入式数据库是轻量级的数据库系统，不会有大量的并发用户同时访问系统，事务发生的频率也比较小，数据写出线程周期性的写出策略使得在意外或灾难发生时而导致内存掉电，从而使数据丢失的机率非常小，可以满足实际的需求。4.2 词法、语法分析及预处理技术对SQL（结构化查询语言）的支持程度是一个嵌入式数据库执行效率的关键，优秀的嵌入式数据库不仅要能支持标准SQL语句，而且要有高的分析和执行效率，而高效安全的SQL编译器则是这个优秀嵌入式数据库的核心和基础。一直以来，编写一个编译器都是一个非常耗时、枯燥乏味的工作，我们每次必须手动编写各种语法处理的函数，这种情况直到1975年Lesk和Johnson发表了关于Lex和Yacc的论文后才得以改变，随后关于Lex和Yacc的应用研究使得开发一个编译器大大简化，利用Lex和Yacc，我们可以很方便地对一条语句进行词法和语法分析。4.2.1 词法分析SQL语句中具有独立意义的单词，我们称之为单位体，有时也称为原子。单位体共有32种，每种单位体的规则和意义各不相同。若从功能上分析，单位体可以分成7类：括号、子查询、数值运算、比较运算、逻辑运算、变量以及其他控制符号。若从可见性分析，单位体可以分成两类，即可见单位体和非可见单位体。非可见单位体主要是一些抽象的单位体，比如逻辑单位体。任意一条合法Where字句，最后经过运算必须得到一个唯一的抽象的非可见单位体，即逻辑单位体。编译程序中的程序模块叫词法分析器。词法分析的主要目的就是分隔单位体，就是负责把输入字符流分隔组成单词流(token)，并将这些单位体按照先后顺序插入单位体链表，其算法框图如图4-1所示。图4-1 词法分析流程图词法分析生成器lex是一个Unix下的实用工具，它将一个词法分析规则转换为C函数的实现。Lex的源程序中定义的单词采用正规表达式来描述，Lex对单词的扫描处理的基本原理采用FSA（finite state automation，有限状态自动操作处理）原理。词法分析器读入字符串，根据词法规则，将一个个的word或字符转换为合法的token。（1）正规表达式正规表达式是描述某些字符串的简单集合的很有用的工具。由于它在描述程序设计语言中使用的单词特别方便及其与有限自动机的密切关系，它已经作为扫描程序生成器的基本工具。Lex中正规表达式的定义是在实用的正规式上，引入一些操作符 （”?.*+|()$%），这些操作符称为元字符，然后递归地定义较复杂的正规表达式。有限字母表V上的正规表达式，可递归地定义如下：是一正规表达式，表示一个空集（不含任何串的集合）；是一正规表达式，表示一个只含空串的集合，这个集合不是空集，它含有一个元素；V中的字符构成的串S是一正规表达式，它表示一个仅含串S的集合，S也可以含元字符，但此时元字符要用两个单引号括起来，使其失去元字符的意义；如果r1和r2是正规表达式，则r1|r2，r|r2及A*，A+都是正规表达式，分别表示对应的正规集的并、链接、克林闭包与正则闭包；（2）有限自动机Lex使用有限自动机（FA）来识别正规表达式所描述的单词和词文。一个有限自动机M=（S，V，f，s0，F）是一个如下定义的五元组：有限状态集S=s0，s1，s2.sn输入字母表V=vl，v2，v3.vn状态转换函数f：SXVS f(si，vi)=sj其中si，sjS，viVs0S是一个初始状态F是一个终止态，FS有限自动机对输入进行读入，根据读入进行状态转移。有限自动机分为两种：确定的有限自动机（DFA)，DFA是这样一种状态机，其中每条转移弧都标有一个输入符号，且从任何状态不会发出两条以上的弧标有相同的输入符号到达不同的另一状态。另一种有限自动机是非确定的有限自动机（NFA），NFA对转移弧的条数与类型都没有限制，从一个状态，可以发出两条具有相同标号的弧到达不同的状态，转移弧可以标记为串。DFA其实是NFA的一种特例。相对比较而言，NFA从正规表达式构造自动机更自接、更简单。但使用的状态数比等价的DFA要多，难以直接利用NFA写出状态机的驱动程序。LEX用两步解决这个问题，第一步构造一个NFA表示正规表达式，第二步把NFA转化为DFA，再从DFA写出状态机驱动程序。（3）Lex对简单SQL语句的识别一条基本SQL语句包含的单词成分主要可分为：关键字：SELECT、FROM、WHERE等SQL语句中的关键字单词函数：COUNT、SUN等SQL语句中的函数单词普通标识：Neld等字段信息等操作符号：、=、+、-、*等操作符号信息数字和字符串常量：12、124、123等常量信息（4）Lex分析后的信息存储Lex按照规则分析出单词，将单词放在一个变量yytext（char*）中，然后转化为一个个用整数表示的token，最后将token传给Yacc构建语法树。但是，对于SQL语法分析执行，仅仅有几个token是远远不够的，比如对于任一个字段，Lex都返回一个token，这是不足以区分字段的，所以在Lex和Yacc之间需要定义一个全局变量来存放更多的信息，我们定义一个YYSTYPE类型的全局变量yyval来存放相应信息。Typedef union yystypeSTRTOK tstr；NUMTOK tnum；YYSTYPE；4.2.2 语法分析语法分析的目的就是解析SQL语句，如图4-2所示，将SQL语句转换成系统可以理解的格式，也就是指按照SQL92标准，判别该SQL语句的类型(查询、删除、修改记录等)，并根据不同的类型作不同的语法分析。比如查询语句，总体而言可以分成三个部分。“select”与“from”之间的部分主要描述结果集输出格式，而“from”与“where”(若无“where”子句，则到SQL语句结尾)之间的部分描述本SQL语句所涉及的表，“where”子句则是表示查询的条件。语法分析的任务之一就是将这三个部分分开并留给以后的系统使用，这也是语法分析的结果之一。在语法分析的过程中，系统需要检查当前SQL语句的合法性，若不合法则报错退出，并给出出错信息。图4-2 语法分析流程图在实际的系统实现中，这部分功能借助了语法分析自动生成工具yacc。语法分析器yacc能够识别的语法是BNF（Backus NaurForm）范式，用户定义一个BNF类型的语法规则，yacc将该规则转换为语法分析器，通过在BNF语法规则中嵌入语法动作，可以建立某种形式的语法树。Yacc语法分析器涉及的关键技术有如下几个方面：（1）上下文无关文法定义Yacc语法表示采用上下文无关文法（Context Free Grammar-CFG）的表示法，简称文法。这种表示法又称BNF范式。上下文无关文法的形式定义如下：上下文无关文法G是一个四元组G=（N，T，P，S），其中：N是非终结符的有限集合；T是终结符或单词的有限集合，它与N不相交；P是形如A-a的产生式的有限集合，其中AN，aV*，V=TNS是N中的区分符号，称为开始符号或句子符号。V=TN称为G的词汇表，V中的符号称为文法符号，包括终结符与非终结符。（2）用文法定义语言文法如何定义语言，有两种观点。一种观点就是推导的观点，它把定义的过程看成是从上而下推导分析树的精确描述。其核心是把产生式看成是一种改写规则，即用产生式右部的字符串替换左部的非终结符的规则。分析树中的根，也就是树的内部节点，都是文法的非终结符，子树本身是被代换的符号的产生式的右部。文法的开始符号总是整棵树的根。分析树的叶节点，或为终结符或为非终结符，从左向右读，就构