摘要
作为移动计算、移动商务和信息电器的核心技术，嵌入式数据库管理系统是最近几年才兴起的一项新的数据管理技术。它以目前成熟的数据库技术为基础，针对具体的嵌入式设备与系统特点，结合实际应用需求，主要实现对嵌入式设备上数据的存储、组织和管理，以及同后台主数据源的数据交换。
本文分析了嵌入式数据库系统的特点和技术发展现状，并根据嵌入式系统的应用需求和嵌入式系统普遍特征指出：基于内存操作的嵌入式数据库性能的决定因素是系统运行时资源开销而非传统的数据I/O操作次数。在这个思想的指导下，本文重点考虑了基于内存的嵌入式数据库管理系统的体系结构，对嵌入式数据库系统的查询机制以及实现技术做了详细的探讨，以及对嵌入式数据系统查询优化技术进行了细致的讨论和研究。
针对具体的嵌入式系统环境及其应用特点，嵌入式数据库所提供的查询系统，在不同的嵌入式数据库系统中其处理的方式都不一样，本文提了一套类似于SQL 的面向对象的查询机制，采取该机制可以更加有效的、快速的对数据库中的数据进行查询。采取这样的一套机制不仅可以提高整个数据库的性能，另外对嵌入式系统开发人员也提供了很大的便利。
对于查询优化，与传统的关系数据库管理系统执行查询相比，当所有的数据存在内存中时，查询的执行速度时非常快速的。另外也不产生庞大的查询中间结果，只产生指向查询对象的指针，这样也大大提高了系
统性能。很显然对于传统数据库系统的查询优化技术在嵌入式数据库系统中不再适用。目前对于嵌入式数据库系统查询优化技术没有统一完备的查询优化算法。针对不同的数据库系统特别是存储方式的不同上一般会选择适合自身系统特点的查询优化机制。一个好的存储机制对查询速度的提高有很大的帮助。本文主要从查询实现上通过只取出指向查询结果的指针减少查询中间结果，以及采取一种智能索引的方式和通过并行查询这些技术来进行优化实现。
关键词：嵌入式数据库系统，查询，查询处理，查询优化
ABSTRACT
As the core technique of mobile-computing,mobile-commerce and informative electrical appliances,the Embedded Database Management System appears recently which is a newly data management technology.The EDBMS which based on the mature technology of DBMS and aimed at the idiographic embedded system and device, implements the embedded system data store,data organize,data management and data exchange with the background data source according practical requirement.
The particularity and the advanced technology of the embedded system and EDBMS are introduced firstly.This dissertation proposes that the capability of EDBMS is decided by the spending of system resource but not the traditional numbers of I/O operations according to the peculiarity of embedded sys
tem and the appliances requirement.In this dissertation,the system architecture of the EDBMS based on the EMS memory is pinpointed.Those pivotal techniques in the development of the system, including query process and query optimization are further discussed.
In view of the embedded system environment and its application characteristics, the embedded database system provides one set of query subsystems.Different EDBMS has its own way of query processing.An object-oriented query mechanism has proposed in this dissertation,which is similar to the SQL and can query data from the database rapidly and effectively.Not only enhance the entire database performance,this method also can provide the convenience to the developers of embedded application systems.
The execution of queries,when all data is present in memory,is very fast, compared with the time for query execution in a traditional RDBMS.But EDBMS even more increases the speed for query execution by applying several optimizations:using indices,inverse references and query parallelization.
Keywords:Embedded Database Management System(EDBMS),query,
query process,query optimization
1绪论
1.1研究背景
数据库技术是应数据管理任务的需要而产生的。60年代后期，随着计算机技术从科学计算向数据处理的扩展，数据库系统应运而生。数据库系统的出现使信息系统的重心发生了转移，从以加工数据的程序为中心转向以数据共享为核心。随后，不断涌现的新应用需求又推动着数据库技术向前发展，从第一代的网状、层次数据库系统，第二代的关系数据库系统，发展倒了第三代面向对象模型为主要特征的数据库系统。今天，新的数据管理需求推动着数据库技术向深度计算（deep computing）和“普及计算”（pervasive computing）两端发展。高端的超大型数据库系统（VLDB）解决复杂数据类型如视频音频数据、多媒体数据、军事上“过程”或“行为”数据的处理问题，满足海量数据的存储和存取，他们将运行在固定的下一代巨型主机服务器上，其特点使大、强、快；而低端的精小型设备中，其采用的嵌入式数据库系统的特是小、灵、易。
当今数据库技术的这两个发展方向的形成与数据仓库技术和嵌入式数据库技术的发展紧密相关。[1]
在深度计算方面，信息化浪潮使数据库的数量和容量越来越惊人，人们在拥有丰富数据的同时发现缺乏有用的信息和知识。数据仓库以数据库技术作为存储数据和管理资源的基本手段，以统计分析技术作为分析数据和提取信息的有效方法，以人工智能技术作为挖掘知识和发现规律的科学途径。因此，它是诸多学科相互结合、综合应用的技术。数据仓库的研究和创建，能充分利用已有的数据资源，把数据转换
为信息，从中挖掘出知识，提炼成智慧，最终创造出效益。数据仓库、联机分析处理和数据挖掘技术的研究方兴未艾，在深度计算领域发挥着重要作用。
在“普及计算”方面，微处理器和嵌入式软件的发展加上网络通信技术的进步适应了社会的需求，推动了嵌入式移动数据库技术的发展。微软中国研发中心总经理张湘辉博士曾说：如果说从1984年的PC/XT和DOS，发展到今天的奔腾和Win98/NT，计算机是经历了从原始初级到复杂而功能强大的过程的话，那么今天计算机的发展又开始了一个新的历程，即从复杂到更高层次的简单的回归，出现了微型化、家电化和专用化的趋势。张博士的话精辟的概括了计算机系统的发展历程，同时也揭示了数据库系统的发展趋势。近年来，嵌入式设备的市场快速增长，据IDC的统计，非PC的专用嵌入式设备目前销售401亿。当前的嵌入式设备种类繁多，用途各异。尽管如此，它们有一个共同的特点，就是需要一个精小型的
数据库管理系统嵌入其中来管理数据，以达到智能化的要求。这样随着嵌入式技术的发展和嵌入式设备的普及，数据库在“普及计算”方向上也得到迅猛发展。[1]在任何数据库系统中，不管是针对大型应用的数据仓库还是小型应用的嵌入式数据库，查询是其必不可少且及其关键的一个环节。本文结合我们提出的一个嵌入式数据库系统模型，命名为Tern，对嵌入式数据库查询机制进行深入探讨和研究。下面首先对嵌入式数据库及其主要特点、发展现状及发展方向做简单的介绍。
1.2嵌入式数据库系统
数据库简单吗
1.2.1概述
数据库技术总是与计算环境的一定发展阶段相适应，新的计算环境和需求促成数据库技术的形成和发展。计算环境从集中式、分布式、网络环境到目前深受瞩目的移动计算环境MCE(Mobile Computing Environment)和普遍化计算环境PCE(Pervasive Computing Enviroment)等多种计算环境。在分布计算的基础上，计算环境进一步扩展包含为各种移动设备、具有无线通信能力的服务网络，构成了移动计算环境。随着移动计算环境发展，数据库系统也从集中式、分布式、B/A/S 多层结构数据库系统发展到今天的嵌入式数据库系统。当前采用标准的关系数据库和数据同步/复制技术，嵌入式数据库管理系统己成为数据库领域的新焦点。[18]与通用的桌面系统不同，由于嵌入式系统没有充足的内存和磁盘资源(或者没有磁盘)，所以，不论是嵌入式的操作系统还是数据库管理系统，都要占用最小的内存和磁盘空间。如果采用文件系统或大型关系型数据库管理系统，都不可避免地产生大量的冗余数据、数据管理效率低下等，所以，他们不能应用于嵌入式系统的数据管理。而长期以来，商业数据库行业都在不停的追逐高性能的事务处理以及复杂的查询处理能力，并制定了相应的行业标准。但是对于嵌入式数据库系统来说，不同的嵌入式应用系统其自身的特点不一样，对于普通的系统一般只要求完成简单的数据查询和更新。但是随着移动计算技术发展。对于它性能的度量标准：易于维护、强壮性、小巧性，在现有的各个嵌入式数据库系统之间难以进行确切地比较，在这三个标准中，易于维护和健壮性是关键，用户除了在处理速度上的要求外，他们需要相信存储在设备的数据具有高度可靠性。易于维护性能够让他们的嵌入式设
备正确的完成任务，而不必进行复杂的人工干预。反过来，这两个特点也就促成了嵌入式系统的另外一个特征，小巧性的形成。嵌入式数据库系统可以支持移动用户在多种网络条件下有效地访问所需数据，完成数据查询和事务处理；通过数据库的同步技术或者数据广播技术，即使在断接的情况下用户也可以继续访问所需数据，这使得嵌入式数据库系统具有高度的可用性；它还可以充
分利用无线通信网络固有的广播能力，以较低的代价同时支持多移动用户对后台主数据源的访问，从而实现高度的可伸缩性，这是传统的客户/服务器或分布式数据库系统所难以比拟的。
同时，在嵌入式系统里，我们采用得最多的，是利用实时操作系统来实现系统的配置和快速的运行，如果在操作系统之上使用数据库管理系统，那么，数据库必须同样具备良好的实时性能，这样才能保证与操作系统结合以后，不会影响整个系统的实时性能。嵌入式数据库主要是管理存放在SRAM,ROM或Flash ROM 中的系统和用户数据。因为系统和用户的数据一般都在SRAM,ROM或Flash ROM 中，但由于系统内存小和CPU速度慢，因此，在嵌入式数据库系统中数据的结构和算法以及数据查询处理算法非常关键，必需采用特殊的数据结构、算法及相关的数据库精简技术。[9]
1.2.2嵌入式数据库系统特点
嵌入式数据库在某些方面与大型数据库相似，例如像大型数据库一样，嵌入式数据库可以是层次、网状或关系数据库，甚至可以是面向对象数据库。但从前面对嵌入式数据库的概述中我们已经看到，与大型
数据库相比，嵌入式数据库独具特，有其不同的特点。归纳起来，嵌入式数据库主要有如下特点:
● 占用磁盘空间小，占用内存资源少
为了使嵌入式数据库所需的磁盘空间减小，嵌入式数据库可不含大型数据库所具有的全部功能，这一特点可使开发者简化开发过程。除此之外，还可以通过限制数据结构的数量和大小，如数据表、记录行和列等其他技术来减少嵌入式数据库所需要的磁盘空间。
嵌入式设备的内存空间较小一般为几百K到几M之间，这就给嵌入式数据库提出了一个新的难题：必须能运行在有限的内存空间中。同时，有些嵌入式设备只有RAM和ROM，没有其它的磁盘空间存在，这样，又存在着另一种情况：要求嵌入式数据库能够在只存在内存的情况下运行。[32]
● 可靠性、可管理性和安全性
手持装置中的嵌入式数据库通常使用在移动环境下，信息技术支持人员无法对其提供现场技术支持。因此，嵌入式数据库必须可靠，而且能在无需人工管理的情况下运行。
鉴于嵌入式数据库的这一特点，对于嵌入式系统中使用的数据库来说，自身可靠性、可管理性和安全性显得特别重要。
● 互操作性和可移植性
一般嵌入式数据库都是针对具体的开发平台和操作系统设计和实现的，但为了保证能与其它的嵌入式数据或大型企业数据库进行通信，数据库开发人员在开