第2章嵌入数据库_数据库相关

PPT 内容

1. 第2章嵌入式移动数据库 2.1 引言 2.2 嵌入式数据库系统的关键技术 2.3 移动信息访问的关键技术 2.4 经典嵌入式数据库产品
2. 2.1 引言数据库技术伴随计算机技术而发展。随着主机时代，个人计算机时代，移动计算时代。相对应，数据库系统出现集中式、分布式和嵌入式移动数据库系统。嵌入式移动数据库（Embedded Moving database, EMDB）是支持移动计算环境的分布式数据库，它可视为分布式数据库系统的扩展，通常应用于掌上电脑、车载设备、移动电话等移动智能设备中。
3. 2.1 引言 EMDB的体系结构Sync Server: Synchronization Server(同步服务器) DBSVR：Database Server(数据库服务器) Rep: Replica(数据库副本)
4. 2.2 嵌入式数据库系统的关键技术嵌入式数据库存储嵌入式数据库索引嵌入式数据库查询移动存取控制和隐私保护嵌入式数据库管理系统
5. 2.2.1 嵌入式数据库存储考虑到存取时间、存储空间利用率和维护代价等因素，通常嵌入式系统的存储结构分为两个层次：（1）第一层为内存，整个嵌入式数据库系统的高性能以内存数据库为底层支持，用于程序运行和实时数据的处理，存取速度快，无需磁盘的I/O操作，（2）第二层为外存，通常采用一些永久存储设备，需要进行读写I/O操作，用于存储系统中的历史数据
6. 2.2.1 嵌入式数据库存储嵌入式数据库的三种存储模型：（1）Flat存储（flat storage）,简称FS存储，它是一种最简单的存储模型，它存储无重复的属性值。元组按顺序进行存储，属性值嵌入到元组中。它的优点是访问的局部性。缺点是空间消耗严重，而且效率低，所有的操作顺序计算。 *元组是关系数据库中的基本概念，关系是一张表，表中的每行（即数据库中的每条记录）就是一个元组，每列就是一个属性。在二维表里，元组也称为记录。
7. 2.2.1 嵌入式数据库存储嵌入式数据库的三种存储模型：（2）基于指针的域存储（domain storage, DS） DS是对数据的一种压缩模型，它对域中对值进行分组，元组通过指针来引用它们的值，一个域也能在多个属性之间进行共享。
8. 2.2.1 嵌入式数据库存储嵌入式数据库的三种存储模型：（3）基于指针的环存储（ring storage, RS） RS存储模型是一种索引压缩模型，是对DS存储模型的一种修改。主要思想是在元组里存储值到元组的指针，这样索引就形成了从域中值到元组的环。
9. 2.2.2 嵌入式数据库索引嵌入式数据库中数据的查找与更新相当频繁，必须建立良好的索引结构以加速各种操作的执行速度并确保数据结构的紧凑性。嵌入式数据库索引特点：（1）实时性： ---嵌入式数据库的很多应用具有很强的实时性，因此要求嵌入式数据库库具备非常高的数据处理速率； ---同时数据库的单一处理过程的持续时间应该十分短暂（单一处理过程指的是对数据进行的一次基本操作，包括只读、写入和读写）。 ---传统的索引机制不能满足这种实施应用的需求，需要一些高实时性的索引机制。
10. 2.2.2 嵌入式数据库索引嵌入式数据库索引特点：（2）高空间利用率： ----嵌入式数据库通常运行在有限资源的嵌入式设备上，其存储空间较小，因此嵌入式数据库占用的存储空间成为了需要解决的首要问题。 ----传统的索引（如B树）通常提供较高的效率，进行较快的随机查找和顺序查找，且动态调整平衡，但空间利用率较差。 B树
11. 2.2.2 嵌入式数据库索引由于嵌入式数据库的实时数据全部驻留类存，系统很少进行磁盘I/O操作，因此其索引结构需要重点解决时间和空间上的开销，其建立原则是快速定位，节省空间。通常采用的数据库索引结构为：顺序结构、B树和AVL树结构。（1）顺序结构：采用数组方式存储，优点存取方便，但不便于动态维护，进行插入、删除操作时；（2） B树：使用最为广泛，操作性好，动态维护方便，但每个结点的数据覆盖率仅为55%，存储效率太低；（3）AVL树（最先发明的自平衡二叉查找树）：具有较高的存取性能，当每个结点需要两个指针域和一些附加的控制信息，查询效率不高。它们均不是嵌入式环境下的最佳选择。
12. 2.2.2 嵌入式数据库索引出现多种改进的适用于嵌入式数据库的索引结构。如适合嵌入式数据库系统的索引结构T树。 T-树是一种面向内存数据库的索引结构，它是从AVL 树(自平衡二叉查找树)和B 树演化而来的，从本质上是一颗节点内包含多个关键字的平衡二叉树，因此它既具有B 树查找速度快的特性，又具有二叉树良好的更新和存储性能。
13. 2.2.2 嵌入式数据库索引 T树比AVL树和B树具有更高的空间利用率，虽然查找时间复杂度稍高于AVL树，单内存中的操作使得其查找时间足以满足实时性要求。这种结构大大减少了结点间元素的移动和平衡处理的次数，较好地考虑了时间和空间的关系，是一种适合嵌入式系统的索引结构。
14. 2.2.3 嵌入式数据库查询传统的查询处理技术是为了利用大量的主存来存储一些临时数据和中间结果，当主存不满足数据存储需求时，采用一些复杂算法利用磁盘来避免内存溢出。嵌入式数据库系统中的内存非常有限，向主机内存写操作很慢；且很难提前估计出内存需求。适合嵌入式数据库系统通常采用自适应的查询处理技术，整个数据都存储在内存中，查询优化的目的是减少从内存中读数据的次数。
15. 2.2.3 嵌入式数据库查询一个基本的查询执行通常分为两个步骤：（1）选择可行的查询执行计划（query execution plan, QEP）。 (2) 查询引擎通过一种执行模型，利用关系操作符库来执行QEP。内存必须在全部操作符之间选择内存分配。
16. 2.3 移动信息访问的关键技术移动事务处理移动数据复制移动数据缓存移动数据广播移动查询处理与优化
17. 2.3.1 移动事务处理事务处理是数据库管理系统的一个基本功能，主要用于维护数据的一致性，支持多用户的并发访问，使用户可以可靠地查询和更新数据库。一般来说，用户对数据库系统的访问都是通过事务来完成的。传统数据库中，一个事务由一系列读写操作组成。事务处理必须满足四个准则，即原子性（atomicity)、一致性(consistency)、隔离性（isolation）、持久性（durability）,简称ACID
18. 2.3.1 移动事务处理事务处理必须满足四个准则: (1)原子性（atomicity): 整个事务中的所有操作，要么全部完成，要么全部不完成，不可能停滞在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样; (2) 一致性(consistency):在事务开始之前和事务结束以后，数据库的完整性约束没有被破坏；
19. 2.3.1 移动事务处理事务处理必须满足四个准则， (3)隔离性(isolation)：隔离状态执行事务，使它们好像是系统在给定时间内执行的唯一操作。如果有两个事务，运行在相同的时间内，执行相同的功能，事务的隔离性将确保每一事务在系统中认为只有该事务在使用系统。这种属性有时称为串行化，为了防止事务操作间的混淆，必须串行化或序列化请求，使得在同一时间仅有一个请求用于同一数据; (4)持久性(durability)：在事务完成以后，该事务所对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。
20. 2.3.1 移动事务处理移动计算环境的特殊性使传统数据库中的事务处理技术不能满足移动事务处理的要求。移动终端发出的事务叫做移动事务，它属于分布式事务。移动事务处理解决在移动环境中频繁的、可预见的断接情况下的事务处理。移动事务的部分计算放在移动终端上完成，其余部分的计算提交给固定服务器上。移动事务可以通过弱连接性的无线方式存取远程数据，也可在断开条件下存取本地数据副本。
21. 2.3.1 移动事务处理移动事务处理和分布式事务处理的区别是明显的，因为它们的目标不一致：分布式事务处理：在满足原子性、一致性、隔离性和永久性条件下，获得最大可用性。移动事务处理：达到一定程度的一致性的同时获得最大的可靠性。移动事务在执行时，不仅发出事务的终端是移动的，事务本身也是移动的。由于无线网络的低带宽、高延迟和移动终端机的间断性，移动事务一般是长事务。显然移动事务与传统事务之间的区别是显著的，传统的ACID模型已经不适用。
22. 2.3.1 移动事务处理新的移动事务处理模型：（1）移动嵌套事务模型：把移动事务定义为相对独立的事务集合。这些事务交替执行。事务本身可进一步分解成多个嵌套的事务，称为复合事务。复合事务由多个子事务构成，子事务的终止可导致复合事务的终止。（2）Kangaroo事务模型：基于全局事务和拆分事务模型。在跨区切换的位置上，通过拆分事务来实现事务的重定位。（3）簇模型：建立在完全分布式系统之上。数据库被分成多个簇。一个簇定义了一组相互一致的数据。不同簇之间允许一定范围内的不一致。
23. 2.3.2 移动数据复制一般采用某种数据复制模式（上载、下载或混合方式）与服务器数据库进行映射，满足人们在任何地点、任意时刻访问任意数据的需求。传统数据复制技术是服务器之间复制数据，且假定服务器之间的连接是固定不间断的。传统复制策略是静态的。
24. 2.3.2 移动数据复制移动数据库需要在移动终端之间以及服务器之间的弱连接（低带宽、长延迟、不稳定）环境下，操作数据库。一个理想的移动复制机制应达到以下四个目标：（1）可用性和可伸缩性（2）移动性（3）可串行性（4）收敛性
25. 2.3.2 移动数据复制提出多种移动数据复制算法，包括：两级复制算法、虚拟主副本算法、多版本冲突解决算法、三级复制算法等。两级复制算法最具代表性：它把数据库视为数据对象的集合，每个数据对象有一个主版本和多个副本。主版本存储在被称为主结点的基结点上，副本同时存放在基结点和移动结点上。移动结点上的数据对象副本有两个版本信息，即移动主版本和暂态版本。移动主版本来自数据对象主版本所在的主结点，暂态版本是移动结点上被临时更新的对象值，只有对主版本更新后才能永久化。
26. 2.3.3 移动数据缓存移动计算环境的通信带宽和电池容量有限，造成移动数据库存取的瓶颈。解决方法：（1）数据缓存（data caching）（2）数据广播 (data broadcasting) 数据缓存：把经常访问的数据缓存到移动结点本地。客户缓存中存放的是数据库的副本，是整体数据库的子集。在终端断接的情况下，用户可以从客户缓存中查询到全部或部分数据。
27. 2.3.3 移动数据缓存移动环境下的数据缓存方法：（1）缓存失效报告广播技术；（2）服务器定期或异步广播缓存失效报告；（3）基于语义的缓存策略基于语义的缓存策略：（1）首先确定与当前查询作用在相交关系上的缓存项，再从这些相关的缓存项中判断有无查询的精确匹配或包含可导出匹配。（2）如果完全匹配，进行查询操作；如果部分匹配，对查询进行裁剪，将裁剪后的查询发送给服务器。
28. 2.3.4 移动数据广播移动数据广播是移动数据管理的一个重要内容，它解决了移动计算环境中的间断性问题。移动设备通信的非对称性：（1）无线单元内部，从服务器到移动终端的下行通信带宽一般要远大于从移动客户端到服务器的上行带宽。（2）移动客户端从服务器端接收数据的开销要远小于发送的开销。
29. 2.3.4 移动数据广播移动数据广播技术的优点：（1）很好的可伸缩性。服务器广播数据的开销与接收广播的终端机无关，可以很小的代价支持大量移动终端同时访问数据。（2）移动终端可以不需要数据缓存。（3）承担对热点数据的需求。（4）便于终端机预取。（5）可广播最新的数据。
30. 2.3.4 移动数据广播数据广播的研究可分为服务器和终端机两个方面：（1）服务器：主要考虑如何组织广播数据，使之适合移动终端访问。这个问题称为数据广播的调度问题。（2）终端机：主要考虑如何利用本地缓存进一步减少查询广播数据的时间。
31. 2.3.4 移动数据广播对广播调度的研究可以根据不同的角度分类：（1）按被广播数据库的覆盖范围分为：全集、子集；（2）按广播内容的实时性分为：静态、动态（3）按是否广播索引分为：带索引广播、无索引广播；（4）按广播数据流的组织形式分为：平坦调度、偏斜调度、多盘调度；（5）按终端机的查询方式可分为：主动、被动。
32. 2.3.4 移动数据广播衡量数据广播调度算法好坏的参数有两个：（1）访问时间（access time）:从移动终端提出数据访问请求开始，到终端机从数据广播中得到结果为止所需的时间。访问时间决定了移动用户查询的相应时间。（2）调谐时间（tuning time）:在完成一个访问请求期间，移动终端保持接听广播的时间。调谐时间决定了移动终端机的电源消耗，因为在不接听广播的时间里，移动终端可以转入睡眠模式，此时消耗的电源相对于激活状态可以忽略不计。
33. 2.3.5 移动查询处理与优化在移动数据库中，存在与位置相关信息的查询与更新，如“最近的医院在哪里”。移动查询处理与优化：（1）基于传统分布式数据库查询处理与优化技术，消除带宽多样性、断接等因素造成的影响，使查询引擎能够根据当前可用网络条件采取适当的优化策略；（2）针对移动终端机有限电源的能力，合理组织本地数据库管理、远程数据库访问等耗电能较多的操作。
34. 2.3.5 移动查询处理与优化多谓词时空查询优化（1）谓词：指查询条件表达式的求值返回真或假的过程（2）谓词的分类：包括范围、k邻近。多谓词查询优化问题：（1）缺乏时空管道操作；（2）时间问题；（3）空间问题；（4）时空问题；
35. 2.3.5 移动查询处理与优化优化的目标：（1）多谓词时空查询需要特殊处理，不能仅仅通过简单堆砌已有时空操作来实现；（2）不同查询操作的选择性随时间和空间会不断变化；（3）自适应查询优化技术
36. 2.4 经典嵌入式数据库产品在嵌入式数据库领域，各大数据库厂商竞争激烈，Oracle、IBM、Sybase、日立等均有所行动。 Berkeley DB: Berkeley DB 是一款工业级开源的嵌入式数据库管理系统。源代码有C和Java两种，库函数本身只有300KB左右，但能管理多达256TB的数据。 Berkeley DB的应用程序和数据库管理系统运行在相同的进程空间当中，进行数据操作时可以避免繁琐的进程间通信，降低了通信开销。 Berkeley DB使用简单的函数调用接口（非SQL）来完成所有的数据库操作，避免了对结构化查询语言进行解析和处理所需的开销。
37. 2.4 经典嵌入式数据库产品 SQLite: SQLite的源代码是C，完全开源。 SQLite有以下特性：（1）支持ACID事务；（2）零配置-无须安装和管理配置；（3）存储在单一磁盘文件中的一个完整数据库；（4）数据库可以在不同字节顺序的机器间自由共享；（5）支持数据库的规模2TB；（6）提供对事务功能和并发处理的支持；其他产品：eXtremeDB、SQL Anywhere Studio、Micrsoft SQL Server 2000 WINCE等。

第2章嵌入数据库

yamara

贡献于2015-05-20

第2章嵌入数据库

PPT 内容

PPT 图集

相关PPT

yamara

贡献于2015-05-20

第2章 嵌入数据库

PPT 内容

PPT 图集

相关PPT

第2章嵌入数据库