计算机软件与理论毕业论文

1、分 类 号 学号 622100200672204 学校代码 10487 密级 硕硕士士学学位位论论 文文 嵌入式移动实时数据库管理系统的嵌入式移动实时数据库管理系统的 数据模型及预处理技术数据模型及预处理技术 学位申请人：学位申请人：胡胡 陆陆 军军 学科专业：学科专业：计算机软件与理论计算机软件与理论 指导教师：指导教师：徐丽萍徐丽萍 副教授副教授 答辩日期：答辩日期：20082008 年年 5 5 月月 2828 日日 a a thesisthesis submittedsubmitted inin partialpartial fulfillmentfulfillment ofof th

2、ethe requirementsrequirements forfor thethe degreedegree ofof mastermaster ofof engineeringengineering datadata modelmodel & & precompilerprecompiler technologytechnology inin embeddedembedded mobilemobile real-timereal-time dbmsdbms candidatecandidate : :huhu lujunlujun majormajor : :computercomput

3、er softwaresoftware andand theorytheory supervisorsupervisor : : associateassociate prof.prof. xuxu lipingliping huazhonghuazhong universityuniversity ofof sciencescience andand technologytechnology wuhanwuhan 430074,430074, p.p. r.r. chinachina may,may, 20082008 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的

4、研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

5、保密，在_年解密后适用本授权书。 本论文属于 不保密。 （请在以上方框内打“”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 华 中 科 技 大 学 硕 士 学 位 论 文 i 摘 要 在嵌入式移动实时数据库系统中，受移动特征和实时特征的影响，硬件资源受 到了严格限制，同时系统对响应时间有很高的要求，因此可裁减、微内核及高速可 靠的响应成为最主要的需求。这些关键特征，对嵌入式移动实时数据库的数据模型 和预处理提出了新的要求： 扩展的数据模型以及合适的预处理器。 由于嵌入式移动实时数据库的特点，目前，选择关系模型作为数据模型扩展的 基础最合适。为了满足嵌入式移动实

6、时数据库管理系统处理实时数据的需要，增加 新的数据类型：实时数据类型以及不变实时数据类型，并提供新数据类型的处理方 法。对于关系模型的语言 sql,已经有了各种标准，sql92 标准是被广泛支持的标准 之一，在 sql92 核心语句的基础之上，通过增加关键字，扩展其对实时数据类型以 及事务时间限制的支持。 形式语言与自动机包括很多用于计算机处理数据的计算模型，其中，正则表达 式、有穷自动机和上下文无关文法理论，是分析 sql 语言及其语句的基础。使用正 则表达式表示 sql 语言，有穷自动机则可以识别该语言，借助他们可以完成词法分 析。用上下文无关文法描述 sql 语言，用下推自动机来识别，借

7、助他们可以完成语 法分析。实际上，语法分析总是以一个固定的流程完成，lemon 工具将这一流程自 动化，用上下文无关文法编写 sql 语言的文法，借助 lemon 指定的特殊申明符，形 成 lemon 语法文件，lemon 读入语法文件，就可以生成语法分析器。 为了描述预处理过程，结合 select 语句，分析了基本的实现过程。 结合 gcc 的结构，给出了针对嵌入式 sql 语句的处理策略，提出了让 gcc 支持 sql 语言的框架，对于构造功能强大的支持数据库的编译器有好的前景。 关键词：嵌入式移动实时数据库，数据模型，词法分析，语法分析，预处理 华 中 科 技 大 学 硕 士 学 位 论

8、 文 ii abstract in the embedded mobile real-time database management system (emrtdbms), the hardware resource is limited because of the feature of mobile and real-time enviroment.time restraints demand rapid and credible response.because of all of these we need enhanced data model and suited precompi

9、ler. analyzing existing data model,relational data model is the appropriate model who will be enhanced. emrtdbms deals with real time data.the enhanced data model must be able to define real time data type and operate real time data.sql has all kinds of standards，among which sql92 is widely used.the

10、 main sql statements of the sql92 have been listed. compiler principles have been developed perfectly.comparing to other languages,sql is easier to compile. formal language and automaton includes all kinds of basal computational theory.among them regular expressions,finite automaton and context free

11、 grammar will be used in our precompiler.lemon is a powerful tool.it can finish these work automatically .so we choose lemon as the compiler to yet sql precompiler. to describe how to precompile,select statement will be parsed. gcc is a powerful compiler,also.it can be enhanced to support sql langua

12、ge.so we can compile embedded sql statements.there is only a framework to be given.in the future,we need powerful compiler.all of these work will be more worth to do. keywordskeywords: embedded mobile real-time dbms, data model, tokenizer, parser, precompiler 华 中 科 技 大 学 硕 士 学 位 论 文 iii 目 录 摘摘 要要.i

13、i abstractabstract.iiii 1 1 绪论绪论 1.1 嵌入式移动实时数据库系统的特征 .(1) 1.2 嵌入式移动实时数据库的书局模型和预处理.(5) 1.3 本文主要研究内容与组织.(10) 2 2 基于关系模型的实时数据模型基于关系模型的实时数据模型 2.1 数据模型的基本数据类型 .(11) 2.2 在基本数据类型基础上扩充实时数据类型.(13) 2.3 实时数据类型的定义.(16) 2.4 对关系模型语言 sql 的扩展.(19) 2.5 嵌入式移动实时数据库系统的事务处理语句.(23) 2.6 小结.(25) 3 3 sqlsql 语言预处理技术语言预处理技术 3

14、.1 sql 语言预处理的理论基础和 lemon工具.(27) 3.2 词法分析设计.(35) 3.3 语法分析设计.(41) 3.4 在编译器 gcc 上扩展 sql.(50) 3.5 本章小结.(54) 4 4 仿真试验与性能评价仿真试验与性能评价 4.1 select语句语法分析.(55) 华 中 科 技 大 学 硕 士 学 位 论 文 iv 4.2 select语句实现.(56) 4.3 系统设计.(57) 4.4 数据结构.(58) 4.5 试验结果性能评价.(61) 4.6 本章小结.(62) 5 5 结束语结束语 5.1 本文总结.(64) 5.2 未来展望.(64) 致致 谢谢

15、.( (66) ) 参考文献参考文献.( (67) ) 附录附录 攻读学位期间参与的科研项目攻读学位期间参与的科研项目.( (71) ) 华 中 科 技 大 学 硕 士 学 位 论 文 1 1 1 绪论绪论 1.11.1 嵌入式移动实时数据库系统的特征嵌入式移动实时数据库系统的特征 随着移动计算技术的发展，各种各样移动设备得到大范围的普及，同时，实时 系统在各行各业需求旺盛，这两种技术的发展为信息服务系统以及工业控制系统打 造了便捷且功能强大的硬件平台。在交通领域，飞机、火车的实时调度，需要有效 的实时信息系统平台来保障安全；在航天领域，卫星的实时监测过程中，测量船、 观测站与指挥中心之间也需

16、要共享实时数据；在投资银行业，证券公司需要通过无 线网络，为客户提供实时信息，客户使用手机、笔记本电脑随时可以查询自己需要 的信息，还可以完成证券的交易；在军事应用中，舰队、雷达网络、战斗机群和后 勤物流等的指挥自动化平台 c4isr 系统要求实时共享情报，对情报的正确实时管理 可以极大的提升战争机器的效能。可以预见，在各个领域，基于移动平台的实时数 据管理系统有广阔的应用前景。 计算机系统发展至今天，数据库已经成了信息管理系统的代名词。然而，传统 的数据库系统是基于传统的硬件平台的，新的硬件平台的出现，提出了许多传统的 数据库未涉及的新的技术问题。于是，嵌入式移动实时数据库技术应运而生，到目

17、 前为止，数据库技术在移动数据库和实时数据库两个方面有较快的发展，有的移动 数据库（如 sybase anywhere）已经商业化并占领了部分市场，而实时数据库在工 业上也有大范围的应用。嵌入式移动实时数据库不是这两者简单的统一，而是依据 自己的系统结构提出了许多技术上要解决的不同的问题，参考文献1 2 3 4， 给出嵌入式移动实时数据库的系统模型如图 1.1。 在图中，固定网络由一组移动服务基站 mss（mobile server station）、信息 服务器 is（information server）、位置服务器 ls（location server）以及固定 主机 fh（fix ho

18、st）构成，它们通过广域网 wan 或其它有线网络连接，数据库分布 于 is 和 mss 中；移动网络由一系列相交或者不相交的无线广播单元 wbu（wireless broadcast unit）构成，每个 wbu 由一个 mss 支持，并且由一组移动客户 华 中 科 技 大 学 硕 士 学 位 论 文 2 mc（mobile client）组成，移动客户 mc 上存放 repdb(replication database),每 个 mc 为一个嵌入式移动设备，它可以跨单元移动。 .1 嵌入式移动实时数据库与嵌入式系统嵌入式移动实时数据库与嵌入式系统 嵌入式移动实时数据库系统的

19、设计是基于移动设备和实时 clinux 操作系统 的。 移动设备是指便携机、电台或者其他各种嵌入式系统设备。ieee 对于嵌入式系 统的定义是：“用于控制、监视或者辅助操作机器和设备的装置” 5。在中国嵌 入式系统领域，比较认同的嵌入式系统概念是：嵌入式系统是以应用为中心，以计 算机技术为基础，并且软硬件可裁剪，适用于应用系统对功能、可靠性、成本、体 积、功耗有严格要求的专用计算机系统5。它一般由嵌入式微处理器、外围硬件设 备、嵌入式操作系统以及用户的应用程序等四个部分组成，用于实现对其他设备的 控制、监视或管理等功能。 wbu 各种固定网络互联 is mss mss ertdbms ldb

20、ertdbms ldb ertdbms ldb ertdbms repdb ertdbms repdb 图 1.1 嵌入式移动实时数据库的系统模型 is ls mss disconnect fh mc mc mc mc mc wireless 华 中 科 技 大 学 硕 士 学 位 论 文 3 实时操作系统（ertdbms 基于实时 clinux）是构建实时系统的基础，实时操 作系统性能的优劣直接影响着整个实时系统的基本性能。实时系统是特指一类计算 结果的正确性不仅取决于其输出逻辑功能的正确性，而且还取决于其输出能否满足 一定时限要求的计算机系统6。根据计算结果超出时限所造成影响的大小，实时系

21、 统又可分为软实时系统和硬实时系统。软实时系统对响应时间虽然有一定要求，但 并不十分严格，即使偶尔超过了任务的执行时限也不会引发严重后果7。 与嵌入式移动实时数据库系统密切相关的，首先是嵌入式系统采用的嵌入式微 处理器和独立内存。微处理器的速度和内存的大小受到了限制，嵌入式移动实时数 据库系统必须满足内核占用空间小、运行速度满足实时应用的要求。其次是数据库 系统和操作系统的相关性。嵌入式移动实时数据库系统在运行中，要求实时 clinux 操作系统提供相关的服务，重要的有任务调度、缓冲区管理、文件系统管 理和恢复等。 .2 嵌入式移动实时数据库的移动特征嵌入式移动实时数据库的移动

22、特征 随着移动通信技术的迅速发展和投入使用，许多计算结点已经可以在自由移动 的过程中保持网络连接，由此产生移动计算的概念。分布式计算环境也进一步扩展 为包含各种移动设备、具有无线通信能力的服务网络，演变为移动计算环境8。移 动计算的出现和计算环境的改变，促使移动数据库技术的诞生。 与传统的分布式数据库系统相比，移动数据库系统具有如下特点9：(1)移动 性及位置相关性；(2)频繁的断接性；(3)网络条件的多样性；(4)系统规模庞大； (5)系统的安全性及可靠性较差；(6)资源的有限性；(7) 网络通信的非对称性。 移动数据库的上述特点，给系统提出了许多新的问题10。包括解决移动客户端 过区切换问

23、题，并实现位置相关的处理；要确保移动数据库系统中的事务在断接情 况下仍能继续运行，或者自动进入休眠状态，而不会因网络断接而撤销；必须提供 充分的灵活性和适应性，提供多种系统运行方式和资源优化方式，以适应网络条件 的变化；移动数据库系统应该提供比普通数据库系统更强的安全机制；要考虑移动 设备受电源、通信带宽、存储容量和处理能力的限制，移动数据库系统要在查询优 华 中 科 技 大 学 硕 士 学 位 论 文 4 化、事务处理和存储管理等诸环节提高资源的利用效率。 移动查询需要在传统分布式数据库查询优化技术的基础上进行改良与扩展，以 适应无线网络的特殊要求。在查询操作时应尽量减少传输的数据量。在优化

24、时间较 长的查询时，考虑减少通信连接的次数，增加每次连接的时间，达到降低通信成本 的效果。在无线网络中使用位置服务器来对移动节点的位置进行跟踪和管理，以满 足许多与位置信息有关的查询问题。 关于移动事务处理技术，传统事务处理准则和技术并不能有效工作在移动数据 库系统中。移动事务具有如下的特点11：事务可能会在执行期间由一个工作区域移 动到另一个工作区域；有限电源、有限资源、移动和断接等决定移动事务通常是可 以和其他事务共享它们的状态和部分结果的长事务；通信不稳定以及子事务的协调 难度大导致移动事务容易出错。 .3 嵌入式移动实时数据库的实时特征嵌入式移动实时数据库的实时特征 实

25、时数据库技术是实时系统和数据库技术相结合的产物，研究人员希望利用数 据库技术来解决实时系统中的数据管理问题，同时利用实时技术为实时数据库提供 时间驱动调度和资源分配算法。概括地讲，实时数据库（rtdb ：real time database）就是其数据或事务有显式定时限制的数据库，系统的正确性不仅依赖于 事务的逻辑结果，而且依赖于该逻辑结果所产生的时间12。 实时数据库在概念、理论、技术、方法和机制方面具备自身特点。如：数据和 数据库的结构与组织；数据处理的优先级控制、调度和并发控制协议与算法；数据 和事务特性的语义及其与一致性、正确性的关系；数据查询事务处理算法与优化； i/o 调度、恢复和

26、通信的协议与算法等，这些问题之间彼此高度相关。需要针对不 同的应用需求和应用特点，对实时数据模型、实时事务调度与资源分配策略、实时 数据查询语言和实时数据通信等大量问题作深入的理论研究。 rtdbs 的实时特征，主要表现在数据或事务的时间相关上。实时数据具有的时 间特征主要包括内部一致性、外部一致性、相互一致性；外部一致性和相互一致性 统称时间一致性。传统意义下的数据正确性是指数据当前值满足预先定义的数据库 华 中 科 技 大 学 硕 士 学 位 论 文 5 内部状态的完整性和一致性限制13；在 rtdbs 中，数据正确性是指数据既是内部一 致又是时间一致的。传统的“原子的、平淡的数据库操作序

27、列”的事务概念及模型 对实时事务不适合。rtdbs 的事务标识性特征包括定时性以及语义相关性。定时性 涉及事务的生成的时间、最坏情况执行时间、完成的最后期限以及事务要能够按指 定的时间要求正确执行。语义相关性是指要考虑实时数据库事务之间的结构关系、 数据与通信关系、时间关系等。 1.21.2 嵌入式移动实时数据库的数据模型和预处理嵌入式移动实时数据库的数据模型和预处理 这里涉及的内容，是在嵌入式移动实时数据库的移动特征和实时特征的基础之 上，探讨其数据模型和预处理技术。 .1 目前流行的数据模型目前流行的数据模型 层次模型、网状模型在数据模型的发展中有重要地位，但是没有模式转换

28、、操 作复杂以及维护困难等特点决定了它们不适合于嵌入式移动实时数据库。 目前应用的都是关系模型或者在其基础之上发展出来的数据模型，关系模型、 面向对象模型和面向对象关系模型是当前被广泛讨论的数据库模型。 关系模型是用二维表格表示实体集的结构数据模型，基本的数据结构是表格， 表格由行和列组成。用“键”而不是用指针导航数据，记录之间联系通过表格中的 键实现。集合论与数理逻辑的理论与方法被引入到关系模型中来，关系模型就成为 一种数学化的模型。 关系模型的数据操作主要包括查询和更新(插入、删除和更新)两类。关系数据 操作是集合操作，即数据操作的对象和操作结果均为若干元组的集合(关系)；关系 模型将操作

29、中存取路径向用户屏蔽起来，大大提高数据独立性和用户进行数据操作 的效率。 对关系模型中的数据操作必须满足关系完整性约束条件，这些约束条件可以分 为三类：实体完整性、参照完整性和用户定义的完整性。 华 中 科 技 大 学 硕 士 学 位 论 文 6 传统的 rdbms 只支持某一固定的类型集，不能依据某一应用所需的特定数据类 型来扩展其类型集。例如，不能定义包含三个实数分量的数据类型 vector 来表示 三维向量。传统数据库只能支持非嵌套事务，对长事务的响应较慢且在事务发生故 障时的恢复比较困难。 为了表示客观世界中的结构复杂、相互联系、语义复杂的对象，数据库研究人 员借鉴和吸收了面向对象的方

30、法和技术，提出了面向对象数据模型(简称对象模型)。 面向对象数据库是其中最重要发展的方向之一。没有面向对象数据库的单个定 义，然而在大多数面向对象数据库中，任何事物都是一个对象，任何事物作为对象 来操作14，一个数据库表的行/字段组织都被对象集概念所取代，通常一个对象集 它自身是一个对象，能像其他对象一样进行操作；用类和子类的层次概念取代功能 强大的数据类型的关系概念；对象继承来自他们类和其他他们所属的更高一级类的 特征；对象拥有的特征可以被它的属性模型化，它们以大致相同的方式来描述与对 象相联系的属性和与表字段相联系的行；对象通过发送和接受消息与其他对象进行 通信，当接收到消息时，对象通过执

31、行一个方法作出反应，该方法是对象中的一个 存储过程，由其决定如何处理消息15。因此一个对象包括一系列的由它的方法描述 的行为，通常一个对象和其他在更高一级的类中的对象共享许多相同方法；对象的 内部结构和数据对外界来说是隐藏(被封装)于被定义好的有限集的界面之后；通过 特定的对象识别器，可以从其他对象中区别出想要的对象，这是通过作为一个叫对 象句柄(handle)的抽象指针来执行的，句柄经常用于表达对象之间的关系16。可见， 面向对象数据库是用一种自然方式去表达产生在复杂数据中的数据层次。一个面向 对象数据库系统是一个持久的可共享的对象库的存储和管理者，而一个对象库是由 一个面向对象数据模型所定

32、义的对象的集合体，这些对象支持面向对象程序设计中 对象的语义。 面向对象数据库缺乏形成关系数据库的最基本的数学理论，同时它缺乏标准。 但是，面向对象数据库更好地适应涉及到复杂数据类型的应用程序，如计算机辅助 设计或组合文本、图形和电子表格的复合文档。 华 中 科 技 大 学 硕 士 学 位 论 文 7 另一种是对象关系数据库。典型地是以关系数据库为基础开始的，并增加了提 供面向对象功能的可选择特性，这种方法为主要的 rdbms 提供商简化了对象功能的 附加部分17。 对象关系数据库中的扩展支持大型数据对象、结构化的/抽象的数据类型、用 户自定义类型数据、表内表、序列/集/数组在单字段中存储、存

33、储过程以及句柄和 对象识别器18。大型数据对象能存储文件、音频和视频文件夹、web 页以及其他 “新的多媒体”数据类型；结构化的数据类型允许成群的单个数据项目集中起来进 入到被他们认为更高级的实体结构中；表中表允许字段去容纳复杂的数据项目；传 统的关系数据库存储过程提供基于集的接口，如 sql 用来存储、选择和检索数据， 对象关系数据库提供过程接口，如存储过程，它封装了数据并提供了严格定义的相 互作用；句柄和对象识别器的引入，使得对象关系数据库为行识别器和其他对象独 特的识别器提供内置支持。 尽管面向对象数据库和面向对象关系数据库有诸多优点，它们“庞大”的对象 以及众多的类的函数，会消耗大量内

34、存资源和处理时间，考虑嵌入式移动实时数据 库系统现状的最重要两个方面：资源受限和实时特性，在当前阶段，这两种数据库 暂时都不适合采用。 较好的解决办法，是在关系模型的基础上，增加可以用来表示定时或时间限制 的数据类型，提供可以表达事务时间限制的 sql 语句。 .2 关系数据模型的扩展关系数据模型的扩展 数据模型是指逻辑数据模型，又称为结构数据模型。 一个关系数据模型主要由数据结构、数据操作和完整性约束组成。 数据结构是计算机数据组织方式和数据之间联系的框架描述，而数据文件中的 数据就按照这种框架描述进行组织。这种框架描述可以分为两类: (1) 与数据类型、内存和性质有关的描述

35、:例如关系模型中的域、属性和关系 等。 (2) 与数据之间联系有关的描述:例如关系模型中的外键。 华 中 科 技 大 学 硕 士 学 位 论 文 8 数据操作是指对数据库中各种对象的实例(或取值)所允许执行的操作的集合， 其中包括操作方法及相应操作规则，它是对数据库动态特性的描述。在数据库中， 数据操作主要有数据查询和数据更新插入、删除和修改)两大类。数据模型需要 定义这些操作的语义、操作符号、操作规则(例如优先级)以及实现操作的相关语句。 数据的约束条件是一组完整性规则(约束条件)的集合。完整性规则是给定的数 据模型中数据及其联系所具有的制约和储存规则，用以限定符合数据模型的数据库 状态以及

36、状态的变化，以保证数据的正确、有效、相容19。此外，数据模型还应该 提供定义完整性约束条件的机制。完整性规则是给定的数据模型中数据及其联系所 具有的制约和依存规则，用以限定数据库中数据的状态以及状态的变化，目的是保 证数据的正确性、有效性和相容性。在这一方面，每种数据模型都应包含下面两个 内容: (1)规定数据模型必须遵守的基本的和通用的完整性约束条件。 (2)提供用户定义完整约束条件的机制。 在嵌入式移动实时数据库系统中，考虑对于实时数据的处理需求，增加实时数 据类型和基本的处理函数；支持的 sql 语言主要参照 sql92 标准核心的语句系列， 增加表示时间限制的关键字；完整性约束则与实时

37、数据对象的外部一致性、内部一 致性和相互一致性相关。 .3 预处理方法预处理方法 预处理可以采用多种不同的方法，通常有全解释执行的方法和半解释执行的方 法，预编译是被广泛采用的半解释执行的方法。 所有数据库管理系统都须将描述型的数据库语言程序转换成可执行的单元组基 本存取动作序列。存取动作和编译时的目录和存取路径是密切相关的。当存取路径 改变了，就应重新优选存取路径，重新编译。这种编译策略可保证数据库语言独立 于存取路径20。 编译过程从数据库语言的语句即符号串转换为一串可执行的存取动作的加工过 华 中 科 技 大 学 硕 士 学 位 论 文 9 程就是一个逐步束缚的过程。同确

38、定的数据结构、存取路径和存贮结构束缚起来， 构成一串确定的存取动作。 按照束缚时间的早晚，翻译和执行的方法不同，从而其效率各异，灵活性也大 不相同。束缚时间愈早则效率愈高，但灵活性和适应性愈小。束缚时间愈晚，则应 变能力愈强但效率愈低21。因此在设计系统时应根据应用的目的不同而采用适当的 设计策略。 对于完全的解释执行其束缚时间是最晚的。直至执行之前符号串均以原始形式 保存在源程序中。在真正调用 dbs（数据库系统）时才利用解释程序去完成编译的 全部动作。这种全解释的方法很灵活，应变性强，加工过程中发生的数据结构和存 取路径的变化均能适应，故能保持高度的数据独立性。但是由于每调用一次 dbs

39、都 要全部执行编译的所有步骤，当在应用程序的某循环体中出现对 dbs 的调用时则重 复开销甚大。每次返回调用程序时，所有临时的内部进程均不复存在，下一次调用 时又得重复全部步骤：词法，语法分析；目录查询；存取审核；完整性检查及存取 优化构造内部控制表格等。当用户接口的高级程度愈高，即系统须干的事愈多时则 解释执行的成本愈高。就是说数据独立性愈高，代价愈高，效率愈受影响22。 半解释方法就是对此所作的一种改进，即以适当降低数据独立性要求为代价， 适当提前束缚时间，以换取效率的提高，若到执行时发现加工时间中发生了数据结 构或存取路径的变化，则令前面所作的转换失效，重新进行。 预编译方法就是这样一种

40、方法。按照这种方法，由描述型语言表达的任一询问 都可作为一个被命名的确定的视图处理。视图法给了用户以选择数据结构的最大的 自由。每一视图的定义都用预优化包来实现。预优化包中包含了语句的分解树和执 行语句的方案，它们称为该语句的充实。这样一来分析询问并将询问转换为可执行 串的内部表示的工作统统在编译时一次完成。仅仅对存取系统提出存取申请的动作 才在执行时完成。执行时若主程序涉及某个数据库询问，则统在编译时一次完成。 执行时若主程序涉及某个数据库询问，则解释执行该询问对应的预优化包。如果在 数据库语句中涉及主程序变量，则可以生成带参数的视图，从而进一步增强了视图 法的可用性，把询问作为视图处理也简

41、化了存取控制问题。 华 中 科 技 大 学 硕 士 学 位 论 文 10 预编译方法的目的是尽可能将一些处理步骤放在编译时进行，使得执行时的间 题简化从而加快执行速度，减少开销。 预编译所做的工作即是给编译作准备。它对嵌入有数据库语言语句的宿主语言 程序进行变换，将所嵌入的各个数据库语言语句替换成对相应的专用存取模块的调 用。以后该源程序中所有对数据库的询问就都经由调用存取模块来执行。经过预编 译处理后的源程序就只剩下主语言的合法语句了，可以由标准的编译程序进行编译。 预编译方法把束缚时间提前到编译时进行，所生成的存取模块已建立了各种联 系，从而节省了执行开销。这种方法也可用于和属性值相关的存

42、取检查及完整性检 查，以尽量减少执行时的解释。 预编译方法的优点是既利用了编译时进行束缚(应用程序和数据库存取的束缚) 带来的提高效率的好处，又兼顾了执行时束缚所具有的高度数位独立性的良好特性。 在嵌入式移动实时数据库系统中，实时性对运算效率的高要求，决定了预编译方法 是很理想的编译策略23。 预编译是编译过程系列动作的第一步，它必须完成词法和语法分析。利用词法 和语法分析程序对描述型语言的语句进行词法和语法分析。词法和语法分析程序的 生成可以直接构造，也可以通过使用词法语法分析器的自动产生程序来自动生成 例如使用 lex 和 yacc 或者著名的 lemon)。这里将采用 lemon 作为自

43、动生成语法 分析器的工具。 1.31.3 本文主要研究内容与组织本文主要研究内容与组织 本文研究嵌入式实时移动数据库系统的数据模型和预处理技术。 本文首先对嵌入式移动实时数据库的特点做了总结，针对系统特点提出的要求， 对传统的关系数据模型作了必要的扩展。对于预处理技术，由于扩展后的语句与传 统预处理的设计没有大的差别，所以重点不是在对扩展语句的预处理，而是采用的 华 中 科 技 大 学 硕 士 学 位 论 文 11 预处理技术要能满足系统可裁减、微内核的设计目标。经过对 yacc（或 bison）和 lemon 的比较，选用了在移动数据库 sqlite 中得到应用的 lemon 语法分析生成器

44、， 它生成的语法分析器允许多个分析器同时运行，能够达到设计目标。由于它是开源 的，开发者甚至可以修改 lemon 本身来满足自己的要求，对于要求更高或者新要求 不断出现的语法分析器，lemon 都有好的适应性。 华 中 科 技 大 学 硕 士 学 位 论 文 12 2 2 基于关系模型的实时数据模型基于关系模型的实时数据模型 2.12.1 数据模型的基本数据类型数据模型的基本数据类型 支持什么数据类型是数据模型中要考虑的基本问题，传统的关系模型支持的数 据类型不能满足描述数据或事务时间限制的需要，所以要在基本数据类型的基础上 进行必要的扩充，增加新的数据类型来满足这种需要。 .

45、1 基本数据类型的分类基本数据类型的分类 sql92 标准支持两种数据类型24，25: 预定义数据类型和用户定义的数据类型。 其中，预定义数据类型是最为通用的一种数据类型。每个预定义数据类型都是 一个指定的元素(使用 sql 关键字)，它把值限制在定义的限制内。sql 包括 5 种预 定义数据类型:串、数字、日期、间隔和布尔值。 用户定义的数据类型是基于预定义数据类型或属性定义，并且作为模式对象添 加到 sql 环境中。sql 支持两种用户定义的数据类型，即相异类型和结构化类型。 相异类型基于预定义数据类型，结构化类型基于属性定义。 sql-1999 标准中增加了构造数据类型，它们也是指定的元

46、素，但是它们可以保 存多个值，因此它们要比预定义数据类型复杂。利用构造数据类型构造的结构比传 统的数据类型要复杂。 这里用自定义的结构化类型为嵌入式移动实时数据库构造新的数据类型-实 时数据类型。 .2 字符串数据类型字符串数据类型 字符串数据类型由基于字符集或数据位使用值的类型组成。由字符串类型许可 的值在长度上既可以是固定的也可以是变化的，这取决于特定的类型。sql 定义 4 华 中 科 技 大 学 硕 士 学 位 论 文 13 种字符串数据类型：字符串、全局字符串、位字符串和二进制字符串（binary large object）。 .3 数字数据类型数字数

47、据类型 由数字数据类型指定的值是数字。所有数字数据类型都具有精度，有些数字数 据类型具有范围。sql 定义了两种数字数据类型：精确数字数据类型 (numeric、decimal、 integer 和 smallint)和近似数字数据类型（real、double precision 和 float）。 .4 日期数据类型日期数据类型 日期数据类型与跟踪日期和时间有关。sql 定义了 3 种日期类型(date, time 和 timestamp)以及这些类型上的变体。这些变体与过去称为 gmt(格林尼治标准时 间)的 uct(世界协调时间)和不同的时区有关。日期数据类型包括： da

48、te、time、time with time zone、timestamp 和 timestamp with time zone。 .5 间隔数据类型间隔数据类型 间隔数据类型与日期数据类型紧密相关。间隔数据类型表示两个日期值之间的 差别。sql 支持两种间隔数据类型：年-月间隔（只使用 year 和 month 字段）和日- 时间隔（只使用 day, hour, minute 和 second 字段）。 不能把一种间隔类型与另一种混合在一起。比如，不能定义使用 year 字段和 hour 字段的间隔数据类型。 间隔数据类型使用后面跟有子句的关键字 interval。此 外，可

49、以使用精度(p)定义子句中的前置字段第一个单词)。 当 second 字段是后置字段(最后一个单词)时，可以指定一个附加精度(x),它定义 小数点后面的数字的数目。可以定义的日-时间隔数据类型非常多。前置字段必须 始终大于后置字段。 华 中 科 技 大 学 硕 士 学 位 论 文 14 .6 布尔数据类型布尔数据类型 布尔数据类型(不同于间隔数据类型)非常简单，并且易于应用。布尔数据类型 支持真/假构造，这种构造只许可 3 个值，即真、假或未知空值被看作未知值(在 sql 中，空值表示一个值未定义或未知)。 2.22.2 在基本数据类型基础上扩充实时数据类型在基本数据类型基础上

50、扩充实时数据类型 实时数据库系统的数据或事务都可能有定时特征或显式的定时限制。数据的正 确性不仅依赖于逻辑结果(数据的内部一致性)，而且依赖于逻辑结果的产生时间和 导出结果所使用数据的时间一致性26。 rtdb 由三大类型的数据对象组成:映像对象(image object, imo)，导出对象 (derivedobject，deo)和不变对象(invariant object，ivo)。 在 rtdbs 中，现实世界的对象(real world object, rwo)由传感器监视，其值 周期性地被采样并写入数据库中，数据库中表示这个被写入的 rwo 值的数据对象就 称为映像对象(imo)。所

51、以一个 imo 就是一个 rwo 在特定时刻的一个映像。由该定 义可知，一个 imo 有一个对应的 rwo 的最近采样时间和有效期与之相联，采样时间 称为采样(或事件)时标(sampling/event timestamp)或简称时标，有效期是指该 imo 的有效时期(validity interval)，它是从采样时间到下一次采样发生的时间区 间(interval)，如tp, tp+evl，其中 tp 为采样时标，evl 为有效期的时间长度 (即采样周期)。有效期是用来反映一个 imo 所能正确反映其对应的外部 rwo 的有效 时间范围，即超出该有效期则该 imo 就不能正确反映外部对象的当

52、前状态，因此有 效期亦称为外部有效期(external validity interval)。 一个 imo 的值一旦记入数据库中，一般就不被更改，而将对应 rwo 在后来时刻 的采样值写入数据库为一新的 imo，因此数据库中每一个 imo 的值都是记录 rwo 经 历的不同版本。rtdb 维护这些 imo 的档储记录，所以数据在不同时间点的瞬像是有 效的。用户在使用数据库数据时，根据需要决定读取哪个版本。例如，执行控制系 统为了监视被控系统的状态、协调和控制被控状态的活动所需要的数据一般应是最 华 中 科 技 大 学 硕 士 学 位 论 文 15 新版本的数据，而对被控系统状态的演化等进行研

53、究和分析所需要的数据就不一定 是最新版本的数据。 一个导出对象(deo)在一个事务的执行过程中由一组 imo 和/或其它数据对象计 算而得，与 deo 相联的时标是用来导出它的数据对象的最晚时标或事务时间，其有 效期为各数据对象有效期之交。deo 的值在数据库中可能被更新，其档储式记录可 以保存也可以不保存。 一个不变对象(ivo)就是一个相对于时间不变的值。 所以，一个实时数据对象是用来描述具有有效期（截止期）的数据的，它是一 个三元组：d，d 为标识，分量 dv、dtp、devi 分别为 d 的当前状态 或值、时标、有效期（即自 dtp 算起 dv 有效的时间长度）12。 传统关系模型无法

54、描述实时数据对象，需要在实时数据模型中定义实时数据类 型，来描述实时数据对象。 定义 1 实时数据类型是用来表示实时数据对象的，它基于数据对象的属性定 义。一个实时数据可以用一个包含三个成员的结构体定义：struct dv，tp，evi ， 其中，d 是这个数据对象的名字，d.v 描述它的当前状态或者值,d.tp 描述 d.v 值的 采样时标,d.evi 指定 d 的有效期长度。 实时数据对象有 imo、deo 和 ivo, imo 和 deo 是可以变化的，而 ivo 是不变的， 为了处理方便，据此可以增加不变实时数据类型。 定义 2 对于一个实时数据 struct dv，tp，evi ，如

55、果它的值 d.v 不随 d.tp 的变化而变化，那么我们称之为不变实时数据类型。ivo 对应的实时数据可以 用它来表示。 在实时数据库系统中，除了数据的时间限制，还包括事件的时间限制或事务的 时间限制。 有三种关于事件的时间限制：1、两事件间的最大时距；2、两事件间的最小时 距；3、限定事件在特定时间发生。 事件的最大间隔（max_interval）、最小间隔（min_interval）和定时 (timing)在系统中可以看作是某一个不变对象(ivo)，它们的作用如图 2.1 所示。 华 中 科 技 大 学 硕 士 学 位 论 文 16 实时事务由事件驱动，事件建模信息(数据)与时间之间的联系

56、，事务的定时限 制有的则表现为相联事件的限制。实时事务的定时限制有： 1、限定事务执行的开 始；2、限定事务执行的结束。即事务的截止期；3、限定事务在指定期间执行。 实时事务的定时限制来自于外部环境的要求（指系统性能要求及数据的时间一 致性要求），它们与实时数据一样，也表现出外部一致和相互一致性限制。 按照时限的性质，实时数据库中的事务分为硬截止事务、软截止事务和固截止 事务。事务处理系统依照截止期来调度事务的执行是目前被认为最有效、最合适的 调度方法。 目前常见的实时事务调度算法有27，28，29，30：最早放行最优先、截止期最早最 优先、可达截止期最早最优先、空余时间最短最优先、价值最高最

57、优先、价值密度 最大最优先、速率单调分析、非精确调度和多标准调度。 这些算法需要的时间包括：当前时间（now_time）、放行时间 （release_time）、事务到达时间(arrive_time)、事务接纳时间(admission_time)、 绝对/相对截止期（absolute/ comparative_deadline_time）、事务的执行时间估 算（estimate_time）和已执行时间（performed_time）。当前时间可以由时钟直 现实世界的实际情况导致某类事件的发生 对应事件的时间限制 max_intervalmin_intervaltiming ivo max_in

58、terval_ ivo min_interval_ ivo timing_ ivo 触发对应事务处理程序 事务调度程序 入事务队列 图 2.1 事件时间限制中的不变实时数据类型 华 中 科 技 大 学 硕 士 学 位 论 文 17 接获得，其他时间都可以使用实时数据类型来声明，用 d.v 来表示这些时间的相对 值（此时 d.v 的数据类型为时间类型），d.tp 用来表示计算获得该时间的时标， d.evi 用来表示这个值的生命期。 2.32.3 实时数据类型的定义实时数据类型的定义 上一节定义了实时数据类型和不变实时数据类型。 实时数据类型对应三元组 d。 对应到用户自定义数据类型时，d 对应了

59、 struct 的名字，dv、dtp、devi 分别 构造成 struct 的三个成员；如图 2.2 示。 具体定义如下： 1、实时数据类型：能够定义所有实时数据对象，存储实时数据，能够用于计 算各种时间限制。 :=realtime :=struct realtime valuetype rt_value timestamp tp_value interval evi_value :=字符串|数字|日期|间隔|布尔 :=（*）|（*） d struct rt_struct type rt_value timestamp tp_value interval evi_value 图 2.2 实时数

60、据类型 rt_struct 华 中 科 技 大 学 硕 士 学 位 论 文 18 :=- :=:：: :=2008.3000 :=00.12 :=00.31 :=00.24 :=00.60 :=00.60 :=000.1000 := (*) |(*) 为实时数据类型定义getdeadline函数： creat function getdeadline(realtime rt) return deadline 事件/事务在定时限制中使用实时数据，该函数用于返回实时数据rt所表示的 事件/事务的截止期。 为实时数据类型定义如下函数： creat function isinnerconsistent