高级数据类型和新型应用

1、Copyright: Silberschatz, Korth and Sudarshan1Silberschatz, Korth and Sudarshan23.2Database System Concepts2n时态数据n空间与地理数据库n多媒体数据库n移动与个人数据库Silberschatz, Korth and Sudarshan23.3Database System Concepts3n多数数据库只刻画现实世界在某个时间点(当前时间)的状态, 而时态时态数据库数据库刻画现实世界在时间流中的所有状态.n时态关系中的事实具有关联的表达其有效性(即在现实世界中为真)的有效时间有效时间, 通

2、常表示为时间段(interval, 有开始和结束时刻)的集合.n事实的事务时间事务时间是指该事实出现在数据库系统中的时间段. n时态关系时态关系: 每条元组都具有关联的表达其何时为真的时间; 该时间可以是有效时间或事务时间.n双时态关系双时态关系既存储有效时间也存储事务时间.Silberschatz, Korth and Sudarshan23.4Database System Concepts4n时态关系例:n人们提出了时态查询语言以便简化对时间的建模以及与时间有关的查询.Silberschatz, Korth and Sudarshan23.5Database System Concept

3、s5ndate: 四位表示年(1-9999), 两位表示月(1-12), 两位表示日(1-31).ntime: 两位表示小时, 两位表示分钟, 两位(加可选的小数位)表示秒.ntimestamp: 包含date和 time的域, 秒域可另加六位小数位.n时间规范为世界协调时(Universal Coordinated Time), 简称为UTC (源自法语); 还支持time with time zone和timestamp with time zone.ninterval: 指一段时间(例如2天, 5小时), 不用说明这段时间的特定开始时刻和结束时刻; 更准确地应称为span.Silbers

4、chatz, Korth and Sudarshan23.6Database System Concepts6n作用于时间段上的谓词precedes, overlaps, 和contains.nIntersect 可作用于两个时间段, 产生单个(可能为空)时段; 但两个时段的 union可能是也可能不是单个时段.n时态关系在时刻 t 的快照快照由那些在时刻 t有效的元组组成, 并去掉时间段属性. n时态选择时态选择: 涉及时间属性的选择操作n时态投影时态投影: 投影结果中的元组继承其在原关系中的时间段.n时态连接时态连接: 连接结果中元组的时间段是导致产生该元组的诸元组的时段的交集. 若该交集

5、为空, 则从连接结果中去掉该元组.Silberschatz, Korth and Sudarshan23.7Database System Concepts7n函数依赖必须小心使用: 增加时间域可能使函数依赖失效n时态函数依赖时态函数依赖X Y 在关系模式在关系模式R上成立, 如果对R的所有合法实例r , r 的所有快照都满足函数依赖X Y.nSQL:1999 Part 7 (SQL/Temporal) 是扩充SQL:1999以改善对时态数据的支持的建议标准.Copyright: Silberschatz, Korth and Sudarshan8Silberschatz, Korth and

6、 Sudarshan23.9Database System Concepts9n空间数据库存储与空间位置有关的信息, 并支持对空间数据的高效存储, 索引和查询.n专门的索引结构对存取空间数据以及处理空间连接查询非常重要.n计算机辅助设计计算机辅助设计(CAD) 数据库存储关于物体如何构造的设计信息. 例如: 建筑设计, 飞机设计, 集成电路布局设计n地理数据库存储地理信息(如地图): 常称为地理信息地理信息系统系统(GIS).Silberschatz, Korth and Sudarshan23.10Database System Concepts10n各种几何结构都可在数据库中以规范的方式表

7、示.n线段表示为端点的坐标.n曲线近似为一系列相连线段顶点的有序列表, 或每个线段表示为单独的元组, 附上曲线的标识符.n封闭多边形有序顶点列表, 开始顶点与结束顶点相同, 或者每条边表示为单独元组, 附上多边形的表识符, 或者通过三角形化三角形化 多边形划分成若干三角形注意每个三角形需附上多边形标识符. Silberschatz, Korth and Sudarshan23.11Database System Concepts11Silberschatz, Korth and Sudarshan23.12Database System Concepts12n三维点和线段的表示类似于二维, 除

8、了点具有z分量之外n任意多面体可通过分割成四面体来表示, 类似三角形化多边形.n另一种方法: 列出它的面(都是多边形), 附带指示该面的哪一侧属于多面体的内部.Silberschatz, Korth and Sudarshan23.13Database System Concepts13nOODB的一个主要动机是CAD系统的需求设计部件表示为对象(一般是几何对象); 对象之间的连接表明了设计结构.n简单二维对象: 点, 线, 三角形, 矩形, 多边形.n复杂二维对象: 由简单对象通过并, 交, 差运算形成.n复杂三维对象: 由简单对象(如球体,柱体, 长方体)通过并, 交, 差运算形成.n三维

9、表面也可用线框(Wireframe)模型表示为简单对象(如线段, 三角形, 矩形)的集合.Silberschatz, Korth and Sudarshan23.14Database System Concepts14n设计数据库还存储对象的非空间信息 (如建造材料, 颜色等), 用标准数据建模技术即可.n空间完整性约束非常重要.例如, 管道不能相交, 线不能互相靠的太近, 等等.(a) 圆柱体的差(b) 圆柱体的并Silberschatz, Korth and Sudarshan23.15Database System Concepts15n栅格数据栅格数据由两维或更多维的位图或像素图组成.

10、2-D光栅图像: 卫星云图, 其中像素存储特定区域的云层可见度.其它维可包括不同高度不同区域的温度, 或者在不同时刻采集的测量值.n设计数据库一般不按栅格数据存储.Silberschatz, Korth and Sudarshan23.16Database System Concepts16n矢量数据矢量数据是从基本几何对象构造出的: 点, 线段, 三角形及其他二维多边形, 圆柱体, 球体, 长方体及其他三维多面体.n矢量格式常用于表示地图数据.道路可视为二维的并表示为直线和曲线.河流之类的特征可根据宽度是否重要而表示为复杂曲线或复杂多边形.象区域和湖泊之类的特征可表示为多边形.Silbers

11、chatz, Korth and Sudarshan23.17Database System Concepts17n地理数据例用于车辆导航的地图数据电力, 电话, 供水, 污水排放分布网信息n车辆导航系统存储道路和供司机使用的服务设施的信息:空间数据空间数据: 例如, 道路/饭馆/加油站的坐标非空间数据非空间数据: 例如, 单行道, 限速, 交通拥挤n全球定位系统全球定位系统(GPS) 装置 利用GPS卫星广播的信息确定用户的当前位置, 精度可达数十米.越来越多用于车辆导航系统以及公用事业维护应用.Silberschatz, Korth and Sudarshan23.18Database S

12、ystem Concepts18n邻近查询请求查找位于指定位置附近的对象.n最近邻查询, 给定一个点或对象, 找出满足给定条件的最邻近的对象.n区域查询涉及空间区域. 例如, 查询完全或部分位于指定区域中的对象.n需计算区域的并或交的查询.n两个空间关系的空间连接, 位置起到连接属性的作用.Silberschatz, Korth and Sudarshan23.19Database System Concepts19n对空间数据的查询一般是通过图形化的查询语言表达的; 结果也以图形方式显示.n图形界面构成前端nSQL扩展支持抽象数据类型, 如直线, 多边形和位图允许关系数据库有效存储和检索空间

13、信息查询中可使用空间条件 (例如包含或重叠)查询中可混合使用空间及非空间条件Silberschatz, Korth and Sudarshan23.20Database System Concepts20nk-d 树树 较早的对多维数据进行索引的一种结构.k-d 树的每一层将空间一分为二.在树的根节点处选择一维来划分.在下一层节点处选择另一维来划分, 如此循环使用各维.在每个节点处, 子树存储的点的应大致平分在两部分空间中.当一节点的点数少于给定最大值时划分终止.nk-d-B树树推广了k-d 树, 允许每个内节点具有多个子节点; 更适合次级存储器.Silberschatz, Korth and

14、 Sudarshan23.21Database System Concepts21n图中每条线(除了最外面的框)对应于k-d 树中的一个节点叶结点中的最大点数被设置成1.n图中线的编号表示对应节点出现在树中的层树.Silberschatz, Korth and Sudarshan23.22Database System Concepts22四叉树四叉树n四叉树的每个节点都与空间的一个矩形区域相关联; 根节点与整个目标空间相关联.n每个非叶结点将其区域等分成四个象限对应地, 每个节点有四个对应于各象限的子节点n叶结点具有零到某固定最大值的点数 (例中设置为1).Silberschatz, Kor

15、th and Sudarshan23.23Database System Concepts23nPR 四叉树四叉树: 存储点; 空间划分是基于区域的, 而不是基于实际点集的.n区域四叉树区域四叉树存储阵列(栅格)信息.若节点覆盖的区域中所有阵列元素值都相同, 则该节点是叶结点. 否则, 进一步划分成四个相等区域的子节点, 且该节点成为内节点.每个节点对应于一个值的子阵列.对应于叶节点的子阵列要么只包含单个阵列元素, 要么有多个具有相同值的阵列元素.n人们提出了k-d 树和PR四叉树的扩展来索引线段和多边形需要将线段/多边形在划分边界处分裂成碎片同一线段/多边形可能需在多个叶节点处表示Silbe

16、rschatz, Korth and Sudarshan23.24Database System Concepts24nR-树树是B+-树的N-维推广, 用于索引矩形及其他多边形的集合.n很多现代数据库系统都支持R-树及其变种R+-树和R*-树.n基本思想: 将与B+树节点关联的一维区间的思想推广到N-维区间, 即N-维矩形.n我们只考虑二维的情况(N = 2) N 2 时的推广是直接的, 但R-树只适合较小的NSilberschatz, Korth and Sudarshan23.25Database System Concepts25n被索引的多边形存储在叶节点上 n树的每个节点都与一个矩

17、形的限定框限定框相关联.叶节点的限定框是包含所有存储于该叶节点的对象的最小矩形(边与坐标轴平行).非叶节点的限定框是包含它的所有子节点的限定框的最小矩形.一个节点的限定框相当于位于它的父节点(如果有的话)中的键一个节点的各子节点的限定框允许重叠n一个多边形只存储于一个节点, 而该节点的限定框必须包含该多边形R-树的存储效率比 k-d 树和四叉树都好, 因为一个多边形只存储一次Silberschatz, Korth and Sudarshan23.26Database System Concepts26n矩形集合 (实线)和限定框(虚线)n右边是为矩形集合建的R-树.Silberschatz,

18、Korth and Sudarshan23.27Database System Concepts27n为查找与给定查询点/区域相交(重叠)的数据项(矩形/多边形), 从根节点开始做以下步骤:如果是叶节点, 输出键与给定查询点/区域相交的数据项.否则,递归搜索当前节点的每一个其限定框与查询点/区域重叠的子节点n在最坏情况下可能效率很低, 因为可能需要搜索多条路经但实际上可接受.n对搜索过程进行简单扩展即可处理谓词contained-in 和 contains Silberschatz, Korth and Sudarshan23.28Database System Concepts28n为了插入

19、一个数据项:找到存储它的叶节点, 并将它加入该叶节点为找到叶节点, 沿着其限定框包含该数据项的限定框的子节点(若有的话)下行, 否则沿着其限定框与数据项限定框具有最大重叠的子节点下行通过分裂处理溢出(同B+ -树) 但分裂过程不同 (见下)从叶节点向上调整限定框n分裂过程:目标: 将溢出节点中的项分成两个集合, 使得限定框具有最小总面积这是启发式. 其他如最小重叠也是可能的寻求“最佳”分裂开销很大, 可用启发式见后Silberschatz, Korth and Sudarshan23.29Database System Concepts29n二次分裂二次分裂(Quadratic split):

20、 将节点中的项如下划分到两个新节点1.找出一对具有“最大间距”的项即, 使得两者的限定框具有最大浪费空间(限定框面积 两项的面积之和)2.将它们分别放入两个新节点3.重复为两个新节点之一找出具有 “最大选择机会”的项, 并将该项放入该节点H项对一节点的选择机会是指如果它加入到另一节点中会导致限定框面积的增加量4.当一半项已经加入到一个节点中时停止H再将剩余项加入到另一节点n更便宜的线性分裂线性分裂启发式导致开销与项数呈线性关系,便宜但分裂效果稍差.Silberschatz, Korth and Sudarshan23.30Database System Concepts30n从R-树中删除项类

21、似于B+-树的删除.如果导致节点项数不足, 如果可能的话从兄弟节点借一些项, 否则合并兄弟节点另一种方法是删除项数不足的节点中的所有项, 再删除该节点, 然后重新插入所有项Copyright: Silberschatz, Korth and Sudarshan31Silberschatz, Korth and Sudarshan23.32Database System Concepts32n为了提供索引和一致性等数据库功能, 需要将多媒体数据存储在数据库之中而不是将它们存储在数据库之外, 如文件系统中n数据库必须能处理大对象表示.n必须通过特殊索引结构提供基于相似性的检索.n对连续媒体数据必须

22、确保提供稳定的检索速率.Silberschatz, Korth and Sudarshan23.33Database System Concepts33n以压缩方式存储与传送多媒体数据JPEG和GIF是最广泛使用的图像数据格式.视频数据的MPEG标准利用一个帧序列之间的共同性来达到较高的压缩度.nMPEG-1的质量可与VHS录像带比较.存储一分钟的30帧每秒的视频和音频需要大约12.5 MB nMPEG-2是为数字广播系统和数字视盘而设计; 视频质量的损失可忽略.压缩1分钟音视频大约需要17MB.n音频编码的其他格式MPEG-1 Layer 3 (MP3)RealAudioWindowsMed

23、ia formatSilberschatz, Korth and Sudarshan23.34Database System Concepts34n最重要的类型是视频和音频数据.n特点是大数据量和实时信息发送的要求.数据必须发送的足够快以便音频或视频不出现间断.数据必须以不使系统缓冲溢出的速率发送.必须维护不同数据流之间的同步一个人正在讲话的视频必须将口形与音频同步Silberschatz, Korth and Sudarshan23.35Database System Concepts35nVideo-on-demand 系统从中央视频服务器通过网络将视频发送到终端必须保证点到点传送速率n当

24、前的video-on-demand服务器基于文件系统; 现有数据库系统不能满足实时响应要求.n多媒体数据存储于若干磁盘上 (RAID), 或者将不常用数据存储在三级存储器上.n终端 用于观察多媒体数据与称为机顶盒的小型廉价计算机相连的PC或TV.Silberschatz, Korth and Sudarshan23.36Database System Concepts36基于相似性的检索例n图形数据: 两幅在数据库中的表示略有不同的图画或图像在用户看来视为相同.例如, 注册新商标时查找相似设计.n音频数据: 基于语音的用户界面允许用户通过说话来发命令或找数据项. 例如, 针对存储的命令测试用户

25、输入.n手写数据: 查找存储于数据库中的手写数据项或命令Copyright: Silberschatz, Korth and Sudarshan37Silberschatz, Korth and Sudarshan23.38Database System Concepts38n移动计算环境由移动计算机(称为移动主机移动主机)和计算机有线网络组成.n移动主机可以通过无线数字通信网络与有线网络通信无线局域网(一座建筑内)例如 Avayas Orinico Wireless LAN广域网蜂窝式数字包网 3 G 和 2.5 G 蜂窝式网Silberschatz, Korth and Sudarshan

26、23.39Database System Concepts39n移动通信的模型移动主机通过称为移动支持(基)站的计算机与有线网络通信.每个移动支持站管理在其cell 之内的移动主机.当移动主机在cell 之间移动时, 一个移动支持站将控制移交给另一个. n在邻近的移动主机之间的不经过移动支持站的直接通信也是可能的例如被蓝牙标准支持(最多10米, 721 kbps)Silberschatz, Korth and Sudarshan23.40Database System Concepts40n查询优化中的新问题连接时间收费及传送字节数能量(电池功率)是稀缺资源, 其使用必须极小化n移动用户的位置

27、可能是查询的一个参数GIS查询大量移动宿主的定位技术n广播数据可以不花费额外开销使任意数目的客户接收同一数据导致有趣的查询及数据缓存问题.n用户可能需要即使在移动计算机断开的情况下也能够执行数据库更新.例如, 移动推销员在数据库(局部拷贝)中登记产品销售记录.重新连接后可能导致检测出冲突, 这时需要手工解决.Silberschatz, Korth and Sudarshan23.41Database System Concepts41n必须考虑以下代价:用户时间通信代价连接时间 在某些蜂窝系统中是收费单位.字节数, 或传送的报文 在数字蜂窝系统中用于计算收费基于每天时段的收费 根据高峰或非高峰

28、时段而变化能量 通过极小化数据接收和传送来优化电池电量的使用. 接收无线电信号比发送无线电信号需要少得多的能量.Silberschatz, Korth and Sudarshan23.42Database System Concepts42n移动支持站可以广播被频繁请求的数据允许移动主机等待所需数据, 而不是花费能量来发送请求支持没有发送能力的移动主机n移动主机可通过确定一个查询是否可以只用缓存数据来回答来优化能量代价如果不可以则必须等待数据广播发送数据请求并且必须知道有关数据何时广播.n广播数据可能根据固定时间表或可变时间表来发送.对可变时间表: 广播时间表本身必须在周知的无线电频率和时间广

29、播n数据接收可能被噪声干扰使用类似于RAID的技术来发送冗余数据(奇偶校验)Silberschatz, Korth and Sudarshan23.43Database System Concepts43n移动主机经常处于断开连接状态, 但在断开期间仍可能进行操作.n断开期间如果移动主机用户对本地驻留的或本地缓冲的数据发出查询和更新, 则会产生问题:可恢复性可恢复性: 若移动主机发生故障, 则在断开的机器上发出的更新可能丢失. 由于移动主机代表single point of failure, 稳定存储器无法很好地模拟.一致性一致性: 本地缓存的数据可能过时, 但移动主机在重新连接以前不能发现.

30、 同样, 发生在移动主机的更新在重新连接之前也不能传播.Silberschatz, Korth and Sudarshan23.44Database System Concepts44n在移动计算中, 因断开连接而产生的网络分割是正常的操作方式.n对于只被一个移动主机更新的数据, 当移动宿主重新连接时传播更新即可n当一个移动主机缓存了能被其他计算机更新的只读数据, 则可用无效性报告通知重新连接的移动宿主已过时的缓存数据项但移动宿主可能因断开连接而漏掉这种报告.n当多处主机可更新, 则发现冲突更加困难基于版本号的方案只确保: 如果两个宿主相互独立地更新同一版本的文档, 则当两宿主直接或通过一公共宿主交换信息时冲突最终将被检测到.稍后还要讨论n不一致的数据拷贝的自动协调非常困难可能需要手工