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

《计算机软件与理论毕业论文》由会员分享，可在线阅读，更多相关《计算机软件与理论毕业论文（80页珍藏版）》请在装配图网上搜索。

1、分 类 号 学号 622100200672204学校代码 10487 密级 硕士学位论文嵌入式移动实时数据库管理系统的数据模型及预处理技术学位申请人：胡 陆 军学科专业：计算机软件与理论指导教师：徐丽萍 副教授答辩日期：2008年5月28日A Thesis Submitted in Partial Fulfillment of the Requirementsfor the Degree of Master of EngineeringData Model & Precompiler Technologyin Embedded Mobile Real-Time DBMSCandidate :H

2、u LujunMajor :Computer Software and TheorySupervisor :Associate Prof. Xu LipingHuazhong University of Science and TechnologyWuhan 430074, P. R. ChinaMay, 2008独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。

3、 学位论文作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密，在_年解密后适用本授权书。本论文属于 不保密。（请在以上方框内打“”）学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日华 中 科 技 大 学 硕 士 学 位 论 文摘 要在嵌入式移动实时数据库系统中，受移动特征和实时特征的影响，硬

4、件资源受到了严格限制，同时系统对响应时间有很高的要求，因此可裁减、微内核及高速可靠的响应成为最主要的需求。这些关键特征，对嵌入式移动实时数据库的数据模型和预处理提出了新的要求： 扩展的数据模型以及合适的预处理器。由于嵌入式移动实时数据库的特点，目前，选择关系模型作为数据模型扩展的基础最合适。为了满足嵌入式移动实时数据库管理系统处理实时数据的需要，增加新的数据类型：实时数据类型以及不变实时数据类型，并提供新数据类型的处理方法。对于关系模型的语言SQL,已经有了各种标准，SQL92标准是被广泛支持的标准之一，在SQL92核心语句的基础之上，通过增加关键字，扩展其对实时数据类型以及事务时间限制的支持

5、。 形式语言与自动机包括很多用于计算机处理数据的计算模型，其中，正则表达式、有穷自动机和上下文无关文法理论，是分析SQL语言及其语句的基础。使用正则表达式表示SQL语言，有穷自动机则可以识别该语言，借助他们可以完成词法分析。用上下文无关文法描述SQL语言，用下推自动机来识别，借助他们可以完成语法分析。实际上，语法分析总是以一个固定的流程完成，Lemon工具将这一流程自动化，用上下文无关文法编写SQL语言的文法，借助Lemon指定的特殊申明符，形成Lemon语法文件，Lemon读入语法文件，就可以生成语法分析器。为了描述预处理过程，结合Select语句，分析了基本的实现过程。结合GCC的结构，给

6、出了针对嵌入式SQL语句的处理策略，提出了让GCC支持SQL语言的框架，对于构造功能强大的支持数据库的编译器有好的前景。关键词：嵌入式移动实时数据库，数据模型，词法分析，语法分析，预处理IIAbstractIn 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 c

7、redible response.Because of all of these we need enhanced data model and suited precompiler. 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 op

8、erate real time data.SQL has all kinds of standards，among which SQL92 is widely used.The 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 bas

9、al computational theory.Among them regular expressions,finite automaton and context free 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

10、will be parsed. GCC is a powerful compiler,also.It can be enhanced to support SQL language.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.Keywords: Embedded Mobile Real-Time DBMS, Data

11、 model, Tokenizer, Parser, Precompiler目 录摘 要IAbstractII1 绪论1.1嵌入式移动实时数据库系统的特征(1)1.2 嵌入式移动实时数据库的书局模型和预处理(5)1.3 本文主要研究内容与组织(10)2基于关系模型的实时数据模型2.1数据模型的基本数据类型(11)2.2 在基本数据类型基础上扩充实时数据类型(13)2.3 实时数据类型的定义(16)2.4 对关系模型语言SQL的扩展(19)2.5 嵌入式移动实时数据库系统的事务处理语句(23)2.6 小结(25)3 SQL语言预处理技术3.1 SQL语言预处理的理论基础和Lemon工具(27)3

12、.2 词法分析设计(35)3.3 语法分析设计(41)3.4 在编译器GCC上扩展SQL(50)3.5 本章小结(54)4仿真试验与性能评价4.1 Select语句语法分析(55)4.2 Select语句实现(56)4.3 系统设计(57)4.4 数据结构(58)4.5 试验结果性能评价(61)4.6 本章小结(62)5 结束语5.1 本文总结(64)5.2 未来展望(64)致 谢(66)参考文献(67)附录 攻读学位期间参与的科研项目(71)IV华 中 科 技 大 学 硕 士 学 位 论 文1 绪论1.1嵌入式移动实时数据库系统的特征随着移动计算技术的发展，各种各样移动设备得到大范围的普及，

13、同时，实时系统在各行各业需求旺盛，这两种技术的发展为信息服务系统以及工业控制系统打造了便捷且功能强大的硬件平台。在交通领域，飞机、火车的实时调度，需要有效的实时信息系统平台来保障安全；在航天领域，卫星的实时监测过程中，测量船、观测站与指挥中心之间也需要共享实时数据；在投资银行业，证券公司需要通过无线网络，为客户提供实时信息，客户使用手机、笔记本电脑随时可以查询自己需要的信息，还可以完成证券的交易；在军事应用中，舰队、雷达网络、战斗机群和后勤物流等的指挥自动化平台C4ISR系统要求实时共享情报，对情报的正确实时管理可以极大的提升战争机器的效能。可以预见，在各个领域，基于移动平台的实时数据管理系统

14、有广阔的应用前景。计算机系统发展至今天，数据库已经成了信息管理系统的代名词。然而，传统的数据库系统是基于传统的硬件平台的，新的硬件平台的出现，提出了许多传统的数据库未涉及的新的技术问题。于是，嵌入式移动实时数据库技术应运而生，到目前为止，数据库技术在移动数据库和实时数据库两个方面有较快的发展，有的移动数据库（如Sybase Anywhere）已经商业化并占领了部分市场，而实时数据库在工业上也有大范围的应用。嵌入式移动实时数据库不是这两者简单的统一，而是依据自己的系统结构提出了许多技术上要解决的不同的问题，参考文献1 2 3 4，给出嵌入式移动实时数据库的系统模型如图1.1。在图中，固定网络由一

15、组移动服务基站MSS（Mobile Server Station）、信息服务器IS（Information Server）、位置服务器LS（Location Server）以及固定主机FH（Fix Host）构成，它们通过广域网WAN或其它有线网络连接，数据库分布于IS和MSS中；移动网络由一系列相交或者不相交的无线广播单元WBU（Wireless Broadcast Unit）构成，每个WBU由一个MSS支持，并且由一组移动客户MC（Mobile WBU各种固定网络互联ISMSSMSSERTDBMSLDBERTDBMSLDBERTDBMSLDBERTDBMSRepDBERTDBMSRepDB

16、图1.1 嵌入式移动实时数据库的系统模型ISLSMSSDisconnectFHMCMCMCMCMCWirelessClient）组成，移动客户MC上存放RepDB(Replication Database),每个MC为一个嵌入式移动设备，它可以跨单元移动。1.1.1嵌入式移动实时数据库与嵌入式系统嵌入式移动实时数据库系统的设计是基于移动设备和实时clinux操作系统的。移动设备是指便携机、电台或者其他各种嵌入式系统设备。IEEE对于嵌入式系统的定义是：“用于控制、监视或者辅助操作机器和设备的装置” 5。在中国嵌入式系统领域，比较认同的嵌入式系统概念是：嵌入式系统是以应用为中心，以计算机技术为基

17、础，并且软硬件可裁剪，适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机系统5。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用户的应用程序等四个部分组成，用于实现对其他设备的控制、监视或管理等功能。实时操作系统（ERTDBMS基于实时clinux）是构建实时系统的基础，实时操作系统性能的优劣直接影响着整个实时系统的基本性能。实时系统是特指一类计算结果的正确性不仅取决于其输出逻辑功能的正确性，而且还取决于其输出能否满足一定时限要求的计算机系统6。根据计算结果超出时限所造成影响的大小，实时系统又可分为软实时系统和硬实时系统。软实时系统对响应时间虽然有一定要求，但并不十

18、分严格，即使偶尔超过了任务的执行时限也不会引发严重后果7。与嵌入式移动实时数据库系统密切相关的，首先是嵌入式系统采用的嵌入式微处理器和独立内存。微处理器的速度和内存的大小受到了限制，嵌入式移动实时数据库系统必须满足内核占用空间小、运行速度满足实时应用的要求。其次是数据库系统和操作系统的相关性。嵌入式移动实时数据库系统在运行中，要求实时clinux操作系统提供相关的服务，重要的有任务调度、缓冲区管理、文件系统管理和恢复等。1.1.2嵌入式移动实时数据库的移动特征随着移动通信技术的迅速发展和投入使用，许多计算结点已经可以在自由移动的过程中保持网络连接，由此产生移动计算的概念。分布式计算环境也进一步

19、扩展为包含各种移动设备、具有无线通信能力的服务网络，演变为移动计算环境8。移动计算的出现和计算环境的改变，促使移动数据库技术的诞生。与传统的分布式数据库系统相比，移动数据库系统具有如下特点9：(1)移动性及位置相关性；(2)频繁的断接性；(3)网络条件的多样性；(4)系统规模庞大；(5)系统的安全性及可靠性较差；(6)资源的有限性；(7) 网络通信的非对称性。移动数据库的上述特点，给系统提出了许多新的问题10。包括解决移动客户端过区切换问题，并实现位置相关的处理；要确保移动数据库系统中的事务在断接情况下仍能继续运行，或者自动进入休眠状态，而不会因网络断接而撤销；必须提供充分的灵活性和适应性，提

20、供多种系统运行方式和资源优化方式，以适应网络条件的变化；移动数据库系统应该提供比普通数据库系统更强的安全机制；要考虑移动设备受电源、通信带宽、存储容量和处理能力的限制，移动数据库系统要在查询优化、事务处理和存储管理等诸环节提高资源的利用效率。移动查询需要在传统分布式数据库查询优化技术的基础上进行改良与扩展，以适应无线网络的特殊要求。在查询操作时应尽量减少传输的数据量。在优化时间较长的查询时，考虑减少通信连接的次数，增加每次连接的时间，达到降低通信成本的效果。在无线网络中使用位置服务器来对移动节点的位置进行跟踪和管理，以满足许多与位置信息有关的查询问题。关于移动事务处理技术，传统事务处理准则和技

21、术并不能有效工作在移动数据库系统中。移动事务具有如下的特点11：事务可能会在执行期间由一个工作区域移动到另一个工作区域；有限电源、有限资源、移动和断接等决定移动事务通常是可以和其他事务共享它们的状态和部分结果的长事务；通信不稳定以及子事务的协调难度大导致移动事务容易出错。1.1.3嵌入式移动实时数据库的实时特征 实时数据库技术是实时系统和数据库技术相结合的产物，研究人员希望利用数据库技术来解决实时系统中的数据管理问题，同时利用实时技术为实时数据库提供时间驱动调度和资源分配算法。概括地讲，实时数据库（RTDB ：real time database）就是其数据或事务有显式定时限制的数据库，系统的

22、正确性不仅依赖于事务的逻辑结果，而且依赖于该逻辑结果所产生的时间12。实时数据库在概念、理论、技术、方法和机制方面具备自身特点。如：数据和数据库的结构与组织；数据处理的优先级控制、调度和并发控制协议与算法；数据和事务特性的语义及其与一致性、正确性的关系；数据查询事务处理算法与优化；I/O调度、恢复和通信的协议与算法等，这些问题之间彼此高度相关。需要针对不同的应用需求和应用特点，对实时数据模型、实时事务调度与资源分配策略、实时数据查询语言和实时数据通信等大量问题作深入的理论研究。RTDBS的实时特征，主要表现在数据或事务的时间相关上。实时数据具有的时间特征主要包括内部一致性、外部一致性、相互一致

23、性；外部一致性和相互一致性统称时间一致性。传统意义下的数据正确性是指数据当前值满足预先定义的数据库内部状态的完整性和一致性限制13；在RTDBS中，数据正确性是指数据既是内部一致又是时间一致的。传统的“原子的、平淡的数据库操作序列”的事务概念及模型对实时事务不适合。RTDBS的事务标识性特征包括定时性以及语义相关性。定时性涉及事务的生成的时间、最坏情况执行时间、完成的最后期限以及事务要能够按指定的时间要求正确执行。语义相关性是指要考虑实时数据库事务之间的结构关系、数据与通信关系、时间关系等。1.2 嵌入式移动实时数据库的数据模型和预处理这里涉及的内容，是在嵌入式移动实时数据库的移动特征和实时特

24、征的基础之上，探讨其数据模型和预处理技术。1.2.1目前流行的数据模型层次模型、网状模型在数据模型的发展中有重要地位，但是没有模式转换、操作复杂以及维护困难等特点决定了它们不适合于嵌入式移动实时数据库。目前应用的都是关系模型或者在其基础之上发展出来的数据模型，关系模型、面向对象模型和面向对象关系模型是当前被广泛讨论的数据库模型。关系模型是用二维表格表示实体集的结构数据模型，基本的数据结构是表格，表格由行和列组成。用“键”而不是用指针导航数据，记录之间联系通过表格中的键实现。集合论与数理逻辑的理论与方法被引入到关系模型中来，关系模型就成为一种数学化的模型。关系模型的数据操作主要包括查询和更新(插

25、入、删除和更新)两类。关系数据操作是集合操作，即数据操作的对象和操作结果均为若干元组的集合(关系)；关系模型将操作中存取路径向用户屏蔽起来，大大提高数据独立性和用户进行数据操作的效率。对关系模型中的数据操作必须满足关系完整性约束条件，这些约束条件可以分为三类：实体完整性、参照完整性和用户定义的完整性。传统的RDBMS只支持某一固定的类型集，不能依据某一应用所需的特定数据类型来扩展其类型集。例如，不能定义包含三个实数分量的数据类型vector来表示三维向量。传统数据库只能支持非嵌套事务，对长事务的响应较慢且在事务发生故障时的恢复比较困难。为了表示客观世界中的结构复杂、相互联系、语义复杂的对象，数

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

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

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

29、件夹、Web页以及其他“新的多媒体”数据类型；结构化的数据类型允许成群的单个数据项目集中起来进入到被他们认为更高级的实体结构中；表中表允许字段去容纳复杂的数据项目；传统的关系数据库存储过程提供基于集的接口，如SQL用来存储、选择和检索数据，对象关系数据库提供过程接口，如存储过程，它封装了数据并提供了严格定义的相互作用；句柄和对象识别器的引入，使得对象关系数据库为行识别器和其他对象独特的识别器提供内置支持。尽管面向对象数据库和面向对象关系数据库有诸多优点，它们“庞大”的对象以及众多的类的函数，会消耗大量内存资源和处理时间，考虑嵌入式移动实时数据库系统现状的最重要两个方面：资源受限和实时特性，在当

30、前阶段，这两种数据库暂时都不适合采用。较好的解决办法，是在关系模型的基础上，增加可以用来表示定时或时间限制的数据类型，提供可以表达事务时间限制的SQL语句。1.2.2关系数据模型的扩展数据模型是指逻辑数据模型，又称为结构数据模型。一个关系数据模型主要由数据结构、数据操作和完整性约束组成。数据结构是计算机数据组织方式和数据之间联系的框架描述，而数据文件中的数据就按照这种框架描述进行组织。这种框架描述可以分为两类:(1) 与数据类型、内存和性质有关的描述:例如关系模型中的域、属性和关系等。(2) 与数据之间联系有关的描述:例如关系模型中的外键。数据操作是指对数据库中各种对象的实例(或取值)所允许执

31、行的操作的集合，其中包括操作方法及相应操作规则，它是对数据库动态特性的描述。在数据库中，数据操作主要有数据查询和数据更新插入、删除和修改)两大类。数据模型需要定义这些操作的语义、操作符号、操作规则(例如优先级)以及实现操作的相关语句。 数据的约束条件是一组完整性规则(约束条件)的集合。完整性规则是给定的数据模型中数据及其联系所具有的制约和储存规则，用以限定符合数据模型的数据库状态以及状态的变化，以保证数据的正确、有效、相容19。此外，数据模型还应该提供定义完整性约束条件的机制。完整性规则是给定的数据模型中数据及其联系所具有的制约和依存规则，用以限定数据库中数据的状态以及状态的变化，目的是保证数

32、据的正确性、有效性和相容性。在这一方面，每种数据模型都应包含下面两个内容: (1)规定数据模型必须遵守的基本的和通用的完整性约束条件。(2)提供用户定义完整约束条件的机制。在嵌入式移动实时数据库系统中，考虑对于实时数据的处理需求，增加实时数据类型和基本的处理函数；支持的SQL语言主要参照SQL92标准核心的语句系列，增加表示时间限制的关键字；完整性约束则与实时数据对象的外部一致性、内部一致性和相互一致性相关。1.2.3预处理方法预处理可以采用多种不同的方法，通常有全解释执行的方法和半解释执行的方法，预编译是被广泛采用的半解释执行的方法。所有数据库管理系统都须将描述型的数据库语言程序转换成可执行

33、的单元组基本存取动作序列。存取动作和编译时的目录和存取路径是密切相关的。当存取路径改变了，就应重新优选存取路径，重新编译。这种编译策略可保证数据库语言独立于存取路径20。编译过程从数据库语言的语句即符号串转换为一串可执行的存取动作的加工过程就是一个逐步束缚的过程。同确定的数据结构、存取路径和存贮结构束缚起来，构成一串确定的存取动作。按照束缚时间的早晚，翻译和执行的方法不同，从而其效率各异，灵活性也大不相同。束缚时间愈早则效率愈高，但灵活性和适应性愈小。束缚时间愈晚，则应变能力愈强但效率愈低21。因此在设计系统时应根据应用的目的不同而采用适当的设计策略。对于完全的解释执行其束缚时间是最晚的。直至

34、执行之前符号串均以原始形式保存在源程序中。在真正调用DBS（数据库系统）时才利用解释程序去完成编译的全部动作。这种全解释的方法很灵活，应变性强，加工过程中发生的数据结构和存取路径的变化均能适应，故能保持高度的数据独立性。但是由于每调用一次DBS都要全部执行编译的所有步骤，当在应用程序的某循环体中出现对DBS的调用时则重复开销甚大。每次返回调用程序时，所有临时的内部进程均不复存在，下一次调用时又得重复全部步骤：词法，语法分析；目录查询；存取审核；完整性检查及存取优化构造内部控制表格等。当用户接口的高级程度愈高，即系统须干的事愈多时则解释执行的成本愈高。就是说数据独立性愈高，代价愈高，效率愈受影响

35、22。半解释方法就是对此所作的一种改进，即以适当降低数据独立性要求为代价，适当提前束缚时间，以换取效率的提高，若到执行时发现加工时间中发生了数据结构或存取路径的变化，则令前面所作的转换失效，重新进行。预编译方法就是这样一种方法。按照这种方法，由描述型语言表达的任一询问都可作为一个被命名的确定的视图处理。视图法给了用户以选择数据结构的最大的自由。每一视图的定义都用预优化包来实现。预优化包中包含了语句的分解树和执行语句的方案，它们称为该语句的充实。这样一来分析询问并将询问转换为可执行串的内部表示的工作统统在编译时一次完成。仅仅对存取系统提出存取申请的动作才在执行时完成。执行时若主程序涉及某个数据库

36、询问，则统在编译时一次完成。执行时若主程序涉及某个数据库询问，则解释执行该询问对应的预优化包。如果在数据库语句中涉及主程序变量，则可以生成带参数的视图，从而进一步增强了视图法的可用性，把询问作为视图处理也简化了存取控制问题。预编译方法的目的是尽可能将一些处理步骤放在编译时进行，使得执行时的间题简化从而加快执行速度，减少开销。预编译所做的工作即是给编译作准备。它对嵌入有数据库语言语句的宿主语言程序进行变换，将所嵌入的各个数据库语言语句替换成对相应的专用存取模块的调用。以后该源程序中所有对数据库的询问就都经由调用存取模块来执行。经过预编译处理后的源程序就只剩下主语言的合法语句了，可以由标准的编译程

37、序进行编译。 预编译方法把束缚时间提前到编译时进行，所生成的存取模块已建立了各种联系，从而节省了执行开销。这种方法也可用于和属性值相关的存取检查及完整性检查，以尽量减少执行时的解释。预编译方法的优点是既利用了编译时进行束缚(应用程序和数据库存取的束缚)带来的提高效率的好处，又兼顾了执行时束缚所具有的高度数位独立性的良好特性。在嵌入式移动实时数据库系统中，实时性对运算效率的高要求，决定了预编译方法是很理想的编译策略23。预编译是编译过程系列动作的第一步，它必须完成词法和语法分析。利用词法和语法分析程序对描述型语言的语句进行词法和语法分析。词法和语法分析程序的生成可以直接构造，也可以通过使用词法语

38、法分析器的自动产生程序来自动生成例如使用LEX和YACC或者著名的Lemon)。这里将采用Lemon作为自动生成语法分析器的工具。1.3 本文主要研究内容与组织 本文研究嵌入式实时移动数据库系统的数据模型和预处理技术。本文首先对嵌入式移动实时数据库的特点做了总结，针对系统特点提出的要求，对传统的关系数据模型作了必要的扩展。对于预处理技术，由于扩展后的语句与传统预处理的设计没有大的差别，所以重点不是在对扩展语句的预处理，而是采用的预处理技术要能满足系统可裁减、微内核的设计目标。经过对Yacc（或BISON）和Lemon的比较，选用了在移动数据库SQLite中得到应用的Lemon语法分析生成器，它

39、生成的语法分析器允许多个分析器同时运行，能够达到设计目标。由于它是开源的，开发者甚至可以修改Lemon本身来满足自己的要求，对于要求更高或者新要求不断出现的语法分析器，Lemon都有好的适应性。2基于关系模型的实时数据模型2.1数据模型的基本数据类型支持什么数据类型是数据模型中要考虑的基本问题，传统的关系模型支持的数据类型不能满足描述数据或事务时间限制的需要，所以要在基本数据类型的基础上进行必要的扩充，增加新的数据类型来满足这种需要。2.1.1 基本数据类型的分类SQL92标准支持两种数据类型24，25: 预定义数据类型和用户定义的数据类型。其中，预定义数据类型是最为通用的一种数据类型。每个预

40、定义数据类型都是一个指定的元素(使用SQL关键字)，它把值限制在定义的限制内。SQL包括5种预定义数据类型:串、数字、日期、间隔和布尔值。用户定义的数据类型是基于预定义数据类型或属性定义，并且作为模式对象添加到SQL环境中。SQL支持两种用户定义的数据类型，即相异类型和结构化类型。相异类型基于预定义数据类型，结构化类型基于属性定义。SQL-1999标准中增加了构造数据类型，它们也是指定的元素，但是它们可以保存多个值，因此它们要比预定义数据类型复杂。利用构造数据类型构造的结构比传统的数据类型要复杂。这里用自定义的结构化类型为嵌入式移动实时数据库构造新的数据类型-实时数据类型。2.1.2 字符串数

41、据类型字符串数据类型由基于字符集或数据位使用值的类型组成。由字符串类型许可的值在长度上既可以是固定的也可以是变化的，这取决于特定的类型。SQL定义4种字符串数据类型：字符串、全局字符串、位字符串和二进制字符串（BINARY LARGE OBJECT）。2.1.3 数字数据类型 由数字数据类型指定的值是数字。所有数字数据类型都具有精度，有些数字数据类型具有范围。SQL定义了两种数字数据类型：精确数字数据类型(NUMERIC、DECIMAL、 INTEGER和SMALLINT)和近似数字数据类型（REAL、DOUBLE PRECISION和FLOAT）。2.1.4 日期数据类型日期数据类型与跟踪日

42、期和时间有关。SQL定义了3种日期类型(DATE, TIME和TIMESTAMP)以及这些类型上的变体。这些变体与过去称为GMT(格林尼治标准时间)的UCT(世界协调时间)和不同的时区有关。日期数据类型包括：DATE、TIME、TIME WITH TIME ZONE、TIMESTAMP和TIMESTAMP WITH TIME ZONE。2.1.5 间隔数据类型间隔数据类型与日期数据类型紧密相关。间隔数据类型表示两个日期值之间的差别。SQL支持两种间隔数据类型：年-月间隔（只使用YEAR和MONTH字段）和日-时间隔（只使用DAY, HOUR, MINUTE和SECOND字段）。 不能把一种间隔

43、类型与另一种混合在一起。比如，不能定义使用YEAR字段和HOUR字段的间隔数据类型。间隔数据类型使用后面跟有子句的关键字INTERVAL。此外，可以使用精度(p)定义子句中的前置字段第一个单词)。当SECOND字段是后置字段(最后一个单词)时，可以指定一个附加精度(x),它定义小数点后面的数字的数目。可以定义的日-时间隔数据类型非常多。前置字段必须始终大于后置字段。2.1.6 布尔数据类型布尔数据类型(不同于间隔数据类型)非常简单，并且易于应用。布尔数据类型支持真/假构造，这种构造只许可3个值，即真、假或未知空值被看作未知值(在SQL中，空值表示一个值未定义或未知)。2.2 在基本数据类型基础

44、上扩充实时数据类型实时数据库系统的数据或事务都可能有定时特征或显式的定时限制。数据的正确性不仅依赖于逻辑结果(数据的内部一致性)，而且依赖于逻辑结果的产生时间和导出结果所使用数据的时间一致性26。RTDB由三大类型的数据对象组成:映像对象(Image Object, IMO)，导出对象(DerivedObject，DEO)和不变对象(Invariant Object，IVO)。 在RTDBS中，现实世界的对象(Real World Object, RWO)由传感器监视，其值周期性地被采样并写入数据库中，数据库中表示这个被写入的RWO值的数据对象就称为映像对象(IMO)。所以一个IMO就是一个R

45、WO在特定时刻的一个映像。由该定义可知，一个IMO有一个对应的RWO的最近采样时间和有效期与之相联，采样时间称为采样(或事件)时标(Sampling/Event Timestamp)或简称时标，有效期是指该IMO的有效时期(Validity Interval)，它是从采样时间到下一次采样发生的时间区间(Interval)，如tp, tp+evl，其中tp为采样时标，evl为有效期的时间长度(即采样周期)。有效期是用来反映一个IMO所能正确反映其对应的外部RWO的有效时间范围，即超出该有效期则该IMO就不能正确反映外部对象的当前状态，因此有效期亦称为外部有效期(External Validity

46、 Interval)。 一个IMO的值一旦记入数据库中，一般就不被更改，而将对应RWO在后来时刻的采样值写入数据库为一新的IMO，因此数据库中每一个IMO的值都是记录RWO经历的不同版本。RTDB维护这些IMO的档储记录，所以数据在不同时间点的瞬像是有效的。用户在使用数据库数据时，根据需要决定读取哪个版本。例如，执行控制系统为了监视被控系统的状态、协调和控制被控状态的活动所需要的数据一般应是最新版本的数据，而对被控系统状态的演化等进行研究和分析所需要的数据就不一定是最新版本的数据。 一个导出对象(DEO)在一个事务的执行过程中由一组IMO和/或其它数据对象计算而得，与DEO相联的时标是用来导出

47、它的数据对象的最晚时标或事务时间，其有效期为各数据对象有效期之交。DEO的值在数据库中可能被更新，其档储式记录可以保存也可以不保存。一个不变对象(IVO)就是一个相对于时间不变的值。所以，一个实时数据对象是用来描述具有有效期（截止期）的数据的，它是一个三元组：d，d为标识，分量dv、dtp、devi分别为d的当前状态或值、时标、有效期（即自dtp算起dv有效的时间长度）12。传统关系模型无法描述实时数据对象，需要在实时数据模型中定义实时数据类型，来描述实时数据对象。定义1 实时数据类型是用来表示实时数据对象的，它基于数据对象的属性定义。一个实时数据可以用一个包含三个成员的结构体定义：struc

48、t dv，tp，evi ，其中，d是这个数据对象的名字，d.v描述它的当前状态或者值,d.tp描述d.v值的采样时标,d.evi指定d的有效期长度。实时数据对象有IMO、DEO和IVO, IMO和DEO是可以变化的，而IVO是不变的，为了处理方便，据此可以增加不变实时数据类型。定义2 对于一个实时数据struct dv，tp，evi ，如果它的值d.v不随d.tp的变化而变化，那么我们称之为不变实时数据类型。IVO对应的实时数据可以用它来表示。在实时数据库系统中，除了数据的时间限制，还包括事件的时间限制或事务的时间限制。有三种关于事件的时间限制：1、两事件间的最大时距；2、两事件间的最小时距；

49、3、限定事件在特定时间发生。事件的最大间隔（max_interval）、最小间隔（min_interval）和定时(timing)在系统中可以看作是某一个不变对象(IVO)，它们的作用如图2.1所示。实时事务由事件驱动，事件建模信息(数据)与时间之间的联系，事务的定时限制有的则表现为相联事件的限制。实时事务的定时限制有： 1、限定事务执行的开始；2、限定事务执行的结束。即事务的截止期；3、限定事务在指定期间执行。 实时事务的定时限制来自于外部环境的要求（指系统性能要求及数据的时间一致性要求），它们与实时数据一样，也表现出外部一致和相互一致性限制。现实世界的实际情况导致某类事件的发生对应事件的时

50、间限制max_intervalmin_intervaltimingIVOmax_interval_ IVOmin_interval_ IVOtiming_ IVO触发对应事务处理程序事务调度程序入事务队列图2.1事件时间限制中的不变实时数据类型按照时限的性质，实时数据库中的事务分为硬截止事务、软截止事务和固截止事务。事务处理系统依照截止期来调度事务的执行是目前被认为最有效、最合适的调度方法。目前常见的实时事务调度算法有27，28，29，30：最早放行最优先、截止期最早最优先、可达截止期最早最优先、空余时间最短最优先、价值最高最优先、价值密度最大最优先、速率单调分析、非精确调度和多标准调度。这些

51、算法需要的时间包括：当前时间（now_time）、放行时间（release_time）、事务到达时间(arrive_time)、事务接纳时间(admission_time)、绝对/相对截止期（absolute/ comparative_deadline_time）、事务的执行时间估算（estimate_time）和已执行时间（performed_time）。当前时间可以由时钟直接获得，其他时间都可以使用实时数据类型来声明，用d.v来表示这些时间的相对值（此时d.v的数据类型为时间类型），d.tp用来表示计算获得该时间的时标，d.evi用来表示这个值的生命期。2.3 实时数据类型的定义上一节定义

52、了实时数据类型和不变实时数据类型。实时数据类型对应三元组d。对应到用户自定义数据类型时，d对应了struct的名字，dv、dtp、devi分别构造成struct的三个成员；如图2.2示。dstruct rt_structtype rt_valuetimestamp tp_valueinterval evi_value图2.2 实时数据类型rt_struct 具体定义如下：1、实时数据类型：能够定义所有实时数据对象，存储实时数据，能够用于计算各种时间限制。:=REALTIME:=struct realtimevaluetype rt_value timestamp tp_valueinterva

53、l evi_value:=字符串|数字|日期|间隔|布尔:=（*）|（*）:=-:=:：:=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(REALTIME rt) Return

54、TRUE/FALSE该函数用来判断实时数据rt是内部一致的，即rt.v满足预先定义完整性限制。为实时数据类型定义如下函数：CREAT FUNCTION IsExteriorConsistent(REALTIME rt) Return TRUE/FALSE该函数用来判断实时数据rt是外部一致的，即rt.v是在其有效范围rt.evi内。为实时数据类型定义如下函数：CREAT FUNCTION IsMutualConsistent(REALTIME rt1，REALTIME rt2，, REALTIME rtn) Return TRUE/FALSE该函数用来判断实时数据集R= rt1, rt2,rt

55、n内的实时数据rti（i=1，2，,n）是相互一致的，即R中任意元素rtj（j=1，2，,n）,有|rti.tp-rtj.tp|Rmvi, Rmvi是与相互一致集R相关的相互有效期。为实时数据类型定义如下操作符和相应的函数：CREAT FUNCTION AddDeadline(REALTIME rt1，REALTIME rt2,TIME comparative_deadline_time) RETURN comparative_deadline_timeCREAT OPERATOR ADD该函数和操作符用于计算两个实时数据相对截止期之和，计算时还与当前时间有关，在事务含两个子事务可以使用这个函

56、数。如果事务含多个子事务，可以配合GetDeadline函数，计算所有子事务的截止期之和。2、不变实时数据类型：对某一类实时数据进行定义，能够存储、计算所有值不随取值时间不变的实时数据。:=INVARIABLEREALTIME:=struct invariable_realtimevaluetype rt_value timestamp tp_valueinterval 0:=字符串|数字|日期|间隔|布尔:=（*）|（*）:=-:=:：:=2008.3000:=00.12:=00.31:=00.24:=00.60:=00.60:=000.1000由定义，一般实时数据类型的有效期不会为0，这里

57、通过将有效期置0作为不变实时数据的标志。不变实时数据类型还不用定义相应的函数。2.4 对关系模型语言SQL的扩展SQL事实上是关系数据库操作和检索的标准语言。SQL使编程者和数据库管理员可以做以下事情:1、修改数据库的结构；2、改变系统的安全性设置；3、增加用户访问数据库或表的权限；4、查询数据库的信息；5、更新数据库的内容。SQL作为标准语言，使得大家使用一种标准的访问数据库的方式，使用新的数据库系统时，不再需要使用者花很多的时间来学会和数据库系统交流。嵌入式移动实时数据库系统除了利用SQL语言的这种便利性，还要求扩展这种语言以满足自己能够处理时间限制的要求。最重要的是，嵌入式移动实时数据库

58、系统存储空间较小，可能要求无维护地运行或者维护量很小，这种环境下，就必须考虑数据操纵语言功能完备（或者说是标准语法的完全实现）与足够精简之间的折中。所以，涉及数据操纵语言时，既要提供功能，又要使操作尽量简单，同时所涉及的数据集尽量小。2.4.1插入语句INSERT语句是惟一允许将新记录添加到现存表中的SQL语句，标准的INSERT语句语法如下：INSERT INTO table_name(column_list)VALUES(value_list)其中，table_name指表名，column_list是要插入表table_name中的列名列表，value_list是一串与column_lis

59、t对应的值。如果要将实时数据插入到表中，也就是说，表中的一列或几列为实时数据类型，需要插入新的元组，元组中就会含有实时数据。例如，对于来自传感器的实时数据，传感器给出了d.v、d.tp和d.evi,通过分离转换，分别赋值给实时数据rt.rt_value、rt.tp_value、rt.evi_value。插入时就可以按如下格式插入(假定共5列，仅第三列c3为实时数据类型)：INSERT INTO table_name (c1，c3，c5)VALUES(value1,rt(rt_value ,tp_value,evi_value),value5)或者INSERT INTO table_nameVA

60、LUES(value1, value2，rt(rt_value ,tp_value,evi_value), value4，value5)表中仅有一列是实时数据类型，对于含多列实时数据类型的表，其格式是类似的。2.4.2查询语句查询语句SELECT用来检索存储在数据库中的数据，SELECT语句由大量子句组成，其中的一些是可选项。如果希望对查询结果作出限制，可以使用WHERE子句。WHERE子句通过保留基于具体某个字段的内容或基于字段的集合的内容的行来减少具体某个查询返回的行数。WHERE子句使用一些运算符，所有的运算符都可以用来比较数字数据、字符串数据和其他类型的数据，包括日期。运算符包括：=（等于），（不等于）,（大于）,=（不小于）,=（不大于）。对于空值，因无法比较，需要使用IS NULL和IS NOT NULL子句。WHERE子句中还会出现逻辑运算符AND、OR和NOT。其它子句因为在实时数据上的操作类似，不再列举。可见，SELECT语句复杂，如果完全支持标准，一次执行所需的时间延长，消耗