嵌入式移动实时数据库管理系统的数据模型及预处理技术硕士学位论文文档格式.docx
《嵌入式移动实时数据库管理系统的数据模型及预处理技术硕士学位论文文档格式.docx》由会员分享，可在线阅读，更多相关《嵌入式移动实时数据库管理系统的数据模型及预处理技术硕士学位论文文档格式.docx（75页珍藏版）》请在冰点文库上搜索。
本人完全意识到本声明的法律结果由本人承担。
学位论文作者签名：
日期：
年月日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：
学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。
本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
保密□，在_______年解密后适用本授权书。
本论文属于
不保密
。
（请在以上方框内打“√”）
学位论文作者签名：
指导教师签名：
日期：
日期：
摘要
在嵌入式移动实时数据库系统中，受移动特征和实时特征的影响，硬件资源受到了严格限制，同时系统对响应时间有很高的要求，因此可裁减、微内核及高速可靠的响应成为最主要的需求。
这些关键特征，对嵌入式移动实时数据库的数据模型和预处理提出了新的要求：
扩展的数据模型以及合适的预处理器。
由于嵌入式移动实时数据库的特点，目前，选择关系模型作为数据模型扩展的基础最合适。
为了满足嵌入式移动实时数据库管理系统处理实时数据的需要，增加新的数据类型：
实时数据类型以及不变实时数据类型，并提供新数据类型的处理方法。
对于关系模型的语言SQL,已经有了各种标准，SQL92标准是被广泛支持的标准之一，在SQL92核心语句的基础之上，通过增加关键字，扩展其对实时数据类型以及事务时间限制的支持。
形式语言与自动机包括很多用于计算机处理数据的计算模型，其中，正则表达式、有穷自动机和上下文无关文法理论，是分析SQL语言及其语句的基础。
使用正则表达式表示SQL语言，有穷自动机则可以识别该语言，借助他们可以完成词法分析。
用上下文无关文法描述SQL语言，用下推自动机来识别，借助他们可以完成语法分析。
实际上，语法分析总是以一个固定的流程完成，Lemon工具将这一流程自动化，用上下文无关文法编写SQL语言的文法，借助Lemon指定的特殊申明符，形成Lemon语法文件，Lemon读入语法文件，就可以生成语法分析器。
为了描述预处理过程，结合Select语句，分析了基本的实现过程。
结合GCC的结构，给出了针对嵌入式SQL语句的处理策略，提出了让GCC支持SQL语言的框架，对于构造功能强大的支持数据库的编译器有好的前景。
关键词：
嵌入式移动实时数据库，数据模型，词法分析，语法分析，预处理
Abstract
Intheembeddedmobilereal-timedatabasemanagementsystem（EMRTDBMS）,thehardwareresourceislimitedbecauseofthefeatureofmobileandreal-timeenviroment.Timerestraintsdemandrapidandcredibleresponse.Becauseofalloftheseweneedenhanceddatamodelandsuitedprecompiler.
Analyzingexistingdatamodel,relationaldatamodelistheappropriatemodelwhowillbeenhanced.EMRTDBMSdealswithrealtimedata.Theenhanceddatamodelmustbeabletodefinerealtimedatatypeandoperaterealtimedata.SQLhasallkindsofstandards，amongwhichSQL92iswidelyused.ThemainSQLstatementsoftheSQL92havebeenlisted.
Compilerprincipleshavebeendevelopedperfectly.Comparingtootherlanguages,SQLiseasiertocompile.Formallanguageandautomatonincludesallkindsofbasalcomputationaltheory.Amongthemregularexpressions,finiteautomatonandcontextfreegrammarwillbeusedinourprecompiler.Lemonisapowerfultool.Itcanfinishtheseworkautomatically.SowechooseLemonasthecompilertoyetSQLprecompiler.
Todescribehowtoprecompile,selectstatementwillbeparsed.
GCCisapowerfulcompiler,also.ItcanbeenhancedtosupportSQLlanguage.SowecancompileembeddedSQLstatements.Thereisonlyaframeworktobegiven.Inthefuture,weneedpowerfulcompiler.Alloftheseworkwillbemoreworthtodo.
Keywords:
EmbeddedMobileReal-TimeDBMS,Datamodel,Tokenizer,Parser,Precompiler
1绪论
1.1嵌入式移动实时数据库系统的特征
随着移动计算技术的发展，各种各样移动设备得到大范围的普及，同时，实时系统在各行各业需求旺盛，这两种技术的发展为信息服务系统以及工业控制系统打造了便捷且功能强大的硬件平台。
在交通领域，飞机、火车的实时调度，需要有效的实时信息系统平台来保障安全；
在航天领域，卫星的实时监测过程中，测量船、观测站与指挥中心之间也需要共享实时数据；
在投资银行业，证券公司需要通过无线网络，为客户提供实时信息，客户使用手机、笔记本电脑随时可以查询自己需要的信息，还可以完成证券的交易；
在军事应用中，舰队、雷达网络、战斗机群和后勤物流等的指挥自动化平台C4ISR系统要求实时共享情报，对情报的正确实时管理可以极大的提升战争机器的效能。
可以预见，在各个领域，基于移动平台的实时数据管理系统有广阔的应用前景。
计算机系统发展至今天，数据库已经成了信息管理系统的代名词。
然而，传统的数据库系统是基于传统的硬件平台的，新的硬件平台的出现，提出了许多传统的数据库未涉及的新的技术问题。
于是，嵌入式移动实时数据库技术应运而生，到目前为止，数据库技术在移动数据库和实时数据库两个方面有较快的发展，有的移动数据库（如SybaseAnywhere）已经商业化并占领了部分市场，而实时数据库在工业上也有大范围的应用。
嵌入式移动实时数据库不是这两者简单的统一，而是依据自己的系统结构提出了许多技术上要解决的不同的问题，参考文献[1][2][3][4]，给出嵌入式移动实时数据库的系统模型如图1.1。
在图中，固定网络由一组移动服务基站MSS（MobileServerStation）、信息服务器IS（InformationServer）、位置服务器LS（LocationServer）以及固定主机FH（FixHost）构成，它们通过广域网WAN或其它有线网络连接，数据库分布于IS和MSS中；
移动网络由一系列相交或者不相交的无线广播单元WBU（WirelessBroadcastUnit）构成，每个WBU由一个MSS支持，并且由一组移动客户MC（Mobile
Client）组成，移动客户MC上存放RepDB（ReplicationDatabase）,每个MC为一个嵌入式移动设备，它可以跨单元移动。
1.1.1嵌入式移动实时数据库与嵌入式系统
嵌入式移动实时数据库系统的设计是基于移动设备和实时μclinux操作系统的。
移动设备是指便携机、电台或者其他各种嵌入式系统设备。
IEEE对于嵌入式系统的定义是：
“用于控制、监视或者辅助操作机器和设备的装置”[5]。
在中国嵌入式系统领域，比较认同的嵌入式系统概念是：
嵌入式系统是以应用为中心，以计算机技术为基础，并且软硬件可裁剪，适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机系统[5]。
它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用户的应用程序等四个部分组成，用于实现对其他设备的控制、监视或管理等功能。
实时操作系统（ERTDBMS基于实时μclinux）是构建实时系统的基础，实时操作系统性能的优劣直接影响着整个实时系统的基本性能。
实时系统是特指一类计算结果的正确性不仅取决于其输出逻辑功能的正确性，而且还取决于其输出能否满足一定时限要求的计算机系统[6]。
根据计算结果超出时限所造成影响的大小，实时系统又可分为软实时系统和硬实时系统。
软实时系统对响应时间虽然有一定要求，但并不十分严格，即使偶尔超过了任务的执行时限也不会引发严重后果[7]。
与嵌入式移动实时数据库系统密切相关的，首先是嵌入式系统采用的嵌入式微处理器和独立内存。
微处理器的速度和内存的大小受到了限制，嵌入式移动实时数据库系统必须满足内核占用空间小、运行速度满足实时应用的要求。
其次是数据库系统和操作系统的相关性。
嵌入式移动实时数据库系统在运行中，要求实时μclinux操作系统提供相关的服务，重要的有任务调度、缓冲区管理、文件系统管理和恢复等。
1.1.2嵌入式移动实时数据库的移动特征
随着移动通信技术的迅速发展和投入使用，许多计算结点已经可以在自由移动的过程中保持网络连接，由此产生移动计算的概念。
分布式计算环境也进一步扩展为包含各种移动设备、具有无线通信能力的服务网络，演变为移动计算环境[8]。
移动计算的出现和计算环境的改变，促使移动数据库技术的诞生。
与传统的分布式数据库系统相比，移动数据库系统具有如下特点[9]：
（1）移动性及位置相关性；
（2）频繁的断接性；
（3）网络条件的多样性；
（4）系统规模庞大；
（5）系统的安全性及可靠性较差；
（6）资源的有限性；
（7）网络通信的非对称性。
移动数据库的上述特点，给系统提出了许多新的问题[10]。
包括解决移动客户端过区切换问题，并实现位置相关的处理；
要确保移动数据库系统中的事务在断接情况下仍能继续运行，或者自动进入休眠状态，而不会因网络断接而撤销；
必须提供充分的灵活性和适应性，提供多种系统运行方式和资源优化方式，以适应网络条件的变化；
移动数据库系统应该提供比普通数据库系统更强的安全机制；
要考虑移动设备受电源、通信带宽、存储容量和处理能力的限制，移动数据库系统要在查询优化、事务处理和存储管理等诸环节提高资源的利用效率。
移动查询需要在传统分布式数据库查询优化技术的基础上进行改良与扩展，以适应无线网络的特殊要求。
在查询操作时应尽量减少传输的数据量。
在优化时间较长的查询时，考虑减少通信连接的次数，增加每次连接的时间，达到降低通信成本的效果。
在无线网络中使用位置服务器来对移动节点的位置进行跟踪和管理，以满足许多与位置信息有关的查询问题。
关于移动事务处理技术，传统事务处理准则和技术并不能有效工作在移动数据库系统中。
移动事务具有如下的特点[11]：
事务可能会在执行期间由一个工作区域移动到另一个工作区域；
有限电源、有限资源、移动和断接等决定移动事务通常是可以和其他事务共享它们的状态和部分结果的长事务；
通信不稳定以及子事务的协调难度大导致移动事务容易出错。
1.1.3嵌入式移动实时数据库的实时特征
实时数据库技术是实时系统和数据库技术相结合的产物，研究人员希望利用数据库技术来解决实时系统中的数据管理问题，同时利用实时技术为实时数据库提供时间驱动调度和资源分配算法。
概括地讲，实时数据库（RTDB：
realtimedatabase）就是其数据或事务有显式定时限制的数据库，系统的正确性不仅依赖于事务的逻辑结果，而且依赖于该逻辑结果所产生的时间[12]。
实时数据库在概念、理论、技术、方法和机制方面具备自身特点。
如：
数据和数据库的结构与组织；
数据处理的优先级控制、调度和并发控制协议与算法；
数据和事务特性的语义及其与一致性、正确性的关系；
数据查询／事务处理算法与优化；
I/O调度、恢复和通信的协议与算法等，这些问题之间彼此高度相关。
需要针对不同的应用需求和应用特点，对实时数据模型、实时事务调度与资源分配策略、实时数据查询语言和实时数据通信等大量问题作深入的理论研究。
RTDBS的实时特征，主要表现在数据或事务的时间相关上。
实时数据具有的时间特征主要包括内部一致性、外部一致性、相互一致性；
外部一致性和相互一致性统称时间一致性。
传统意义下的数据正确性是指数据当前值满足预先定义的数据库内部状态的完整性和一致性限制[13]；
在RTDBS中，数据正确性是指数据既是内部一致又是时间一致的。
传统的“原子的、平淡的数据库操作序列”的事务概念及模型对实时事务不适合。
RTDBS的事务标识性特征包括定时性以及语义相关性。
定时性涉及事务的生成的时间、最坏情况执行时间、完成的最后期限以及事务要能够按指定的时间要求正确执行。
语义相关性是指要考虑实时数据库事务之间的结构关系、数据与通信关系、时间关系等。
1.2嵌入式移动实时数据库的数据模型和预处理
这里涉及的内容，是在嵌入式移动实时数据库的移动特征和实时特征的基础之上，探讨其数据模型和预处理技术。
1.2.1目前流行的数据模型
层次模型、网状模型在数据模型的发展中有重要地位，但是没有模式转换、操作复杂以及维护困难等特点决定了它们不适合于嵌入式移动实时数据库。
目前应用的都是关系模型或者在其基础之上发展出来的数据模型，关系模型、面向对象模型和面向对象关系模型是当前被广泛讨论的数据库模型。
关系模型是用二维表格表示实体集的结构数据模型，基本的数据结构是表格，表格由行和列组成。
用“键”而不是用指针导航数据，记录之间联系通过表格中的键实现。
集合论与数理逻辑的理论与方法被引入到关系模型中来，关系模型就成为一种数学化的模型。
关系模型的数据操作主要包括查询和更新（插入、删除和更新）两类。
关系数据操作是集合操作，即数据操作的对象和操作结果均为若干元组的集合（关系）；
关系模型将操作中存取路径向用户屏蔽起来，大大提高数据独立性和用户进行数据操作的效率。
对关系模型中的数据操作必须满足关系完整性约束条件，这些约束条件可以分为三类：
实体完整性、参照完整性和用户定义的完整性。
传统的RDBMS只支持某一固定的类型集，不能依据某一应用所需的特定数据类型来扩展其类型集。
例如，不能定义包含三个实数分量的数据类型vector来表示三维向量。
传统数据库只能支持非嵌套事务，对长事务的响应较慢且在事务发生故障时的恢复比较困难。
为了表示客观世界中的结构复杂、相互联系、语义复杂的对象，数据库研究人员借鉴和吸收了面向对象的方法和技术，提出了面向对象数据模型（简称对象模型）。
面向对象数据库是其中最重要发展的方向之一。
没有面向对象数据库的单个定义，然而在大多数面向对象数据库中，任何事物都是一个对象，任何事物作为对象来操作[14]，一个数据库表的行/字段组织都被对象集概念所取代，通常一个对象集它自身是一个对象，能像其他对象一样进行操作；
用类和子类的层次概念取代功能强大的数据类型的关系概念；
对象继承来自他们类和其他他们所属的更高一级类的特征；
对象拥有的特征可以被它的属性模型化，它们以大致相同的方式来描述与对象相联系的属性和与表字段相联系的行；
对象通过发送和接受消息与其他对象进行通信，当接收到消息时，对象通过执行一个方法作出反应，该方法是对象中的一个存储过程，由其决定如何处理消息[15]。
因此一个对象包括一系列的由它的方法描述的行为，通常一个对象和其他在更高一级的类中的对象共享许多相同方法；
对象的内部结构和数据对外界来说是隐藏（被封装）于被定义好的有限集的界面之后；
通过特定的对象识别器，可以从其他对象中区别出想要的对象，这是通过作为一个叫对象句柄（handle）的抽象指针来执行的，句柄经常用于表达对象之间的关系[16]。
可见，面向对象数据库是用一种自然方式去表达产生在复杂数据中的数据层次。
一个面向对象数据库系统是一个持久的可共享的对象库的存储和管理者，而一个对象库是由一个面向对象数据模型所定义的对象的集合体，这些对象支持面向对象程序设计中对象的语义。
面向对象数据库缺乏形成关系数据库的最基本的数学理论，同时它缺乏标准。
但是，面向对象数据库更好地适应涉及到复杂数据类型的应用程序，如计算机辅助设计或组合文本、图形和电子表格的复合文档。
另一种是对象关系数据库。
典型地是以关系数据库为基础开始的，并增加了提供面向对象功能的可选择特性，这种方法为主要的RDBMS提供商简化了对象功能的附加部分[17]。
对象关系数据库中的扩展支持大型数据对象、结构化的/抽象的数据类型、用户自定义类型数据、表内表、序列/集/数组在单字段中存储、存储过程以及句柄和对象识别器[18]。
大型数据对象能存储文件、音频和视频文件夹、Web页以及其他“新的多媒体”数据类型；
结构化的数据类型允许成群的单个数据项目集中起来进入到被他们认为更高级的实体结构中；
表中表允许字段去容纳复杂的数据项目；
传统的关系数据库存储过程提供基于集的接口，如SQL用来存储、选择和检索数据，对象关系数据库提供过程接口，如存储过程，它封装了数据并提供了严格定义的相互作用；
句柄和对象识别器的引入，使得对象关系数据库为行识别器和其他对象独特的识别器提供内置支持。
尽管面向对象数据库和面向对象关系数据库有诸多优点，它们“庞大”的对象以及众多的类的函数，会消耗大量内存资源和处理时间，考虑嵌入式移动实时数据库系统现状的最重要两个方面：
资源受限和实时特性，在当前阶段，这两种数据库暂时都不适合采用。
较好的解决办法，是在关系模型的基础上，增加可以用来表示定时或时间限制的数据类型，提供可以表达事务时间限制的SQL语句。
1.2.2关系数据模型的扩展
数据模型是指逻辑数据模型，又称为结构数据模型。
一个关系数据模型主要由数据结构、数据操作和完整性约束组成。
数据结构是计算机数据组织方式和数据之间联系的框架描述，而数据文件中的数据就按照这种框架描述进行组织。
这种框架描述可以分为两类:
（1）与数据类型、内存和性质有关的描述:
例如关系模型中的域、属性和关系等。
（2）与数据之间联系有关的描述:
例如关系模型中的外键。
数据操作是指对数据库中各种对象的实例（或取值）所允许执行的操作的集合，其中包括操作方法及相应操作规则，它是对数据库动态特性的描述。
在数据库中，数据操作主要有数据查询和数据更新〔插入、删除和修改）两大类。
数据模型需要定义这些操作的语义、操作符号、操作规则（例如优先级）以及实现操作的相关语句。
数据的约束条件是一组完整性规则（约束条件）的集合。
完整性规则是给定的数据模型中数据及其联系所具有的制约和储存规则，用以限定符合数据模型的数据库状态以及状态的变化，以保证数据的正确、有效、相容[19]。
此外，数据模型还应该提供定义完整性约束条件的机制。
完整性规则是给定的数据模型中数据及其联系所具有的制约和依存规则，用以限定数据库中数据的状态以及状态的变化，目的是保证数据的正确性、有效性和相容性。
在这一方面，每种数据模型都应包含下面两个内容:
（1）规定数据模型必须遵守的基本的和通用的完整性约束条件。
（2）提供用户定义完整约束条件的机制。
在嵌入式移动实时数据库系统中，考虑对于实时数据的处理需求，增加实时数据类型和基本的处理函数；
支持的SQL语言主要参照SQL92标准核心的语句系列，增加表示时间限制的关键字；
完整性约束则与实时数据对象的外部一致性、内部一致性和相互一致性相关。
1.2.3预处理方法
预处理可以采用多种不同的方法，通常有全解释执行的方法和半解释执行的方法，预编译是被广泛采用的半解释执行的方法。
所有数据库管理系统都须将描述型的数据库语言程序转换成可执行的单元组基本存取动作序列。
存取动作和编译时的目录和存取路径是密切相关的。
当存取路径改变了，就应重新优选存取路径，重新编译。
这种编译策略可保证数据库语言独立于存取路径[20]。
编译过程从数据库语言的语句即符号串转换为一串可执行的存取动作的加工过程就是一个逐步束缚的过程。
同确定的数据结构、存取路径和存贮结构束缚起来，构成一串确定的存取动作。
按照束缚时间的早晚，翻译和执行的方法不同，从而其效率各异，灵活性也大不相同。
束缚时间愈早则效率愈高，但灵活性和适应性愈小。
束缚时间愈晚，则应变能力愈强但效率愈低[21]。
因此在设计系统时应根据应用的目的不同而采用适当的设计策略。
对于完全的解释执行其束缚时间是最晚的。
直至执行之前符号串均以原始形式保存在源程序中。
在真正调用DBS（数据库系统）时才利用解释程序去完成编译的全部动作。
这种全解释的方法很灵活，应变性强，加工过程中发生的数据结构和存取路径的变化均能适应，故能保持高度的数据独立性。
但是由于每调用一次DBS都要全部执行编译的所有步骤，当在应用程序的某循环体中出现对DBS的调用时则重复开销甚大。
每次返回调用程序时，所有临时的内部进程均不复存在，下一次调用时又得重复全部步骤：
词法，语法分析；
目录查询；
存取审核；
完整性检查及存取优化构造内部控制表格等。
当用户接口的高级程度愈高，即系统须干的事愈多时则解释执行的成本愈高。
就是说数据独立性愈高，代价愈高，效率愈受影响[22]。
半解释方法就是对此所作的一种改进，即以适当降低数据独立性要求为代价，适当提前束缚时间，以换取效率的提高，若到执行时发现加工时间中发生了数据结构或存取路径的变化，则令前面所作的转换失效，重新进行。
预编译方法就是这样一种方法。
按照这种方法，由描述型语言表达的任一询问都可作为一个被命名的确定的视图处
升级会员 