分布式数据库系统及其应用

第2章 分布式数据库系统设计 分布式数据库系统设计概述 自顶向下设计分布式数据库 DATAID-D方法 实例研究：飞机订票系统 自底向上设计分布式数据库

分布式数据库设计概述 1 1.1 创建方法 网络 组合法 用户1 用户2 用户n 分布式协调管理系统 DBMS1 DBMS2 DBMSm 剖析网络功能 剖析原有数据库系统 解决数据的一致性、完整性和可靠性 难度较大 通常是异构或者同构异质DDBS

分布式数据库设计概述 1 1.1 DDBS创建方法 网络 重构法 用户1 用户2 用户n 分布式数据库管理系统 根据实现环境和用户需求 从总体设计做起，包括LDBS,重新建立一个DDBS 可有效解决数据一致性、完整性和可靠性问题。 通常是同构异质或同构同质DDBS 用户1 用户2 用户n 分布式数据库管理系统 网络

1 分布式数据库设计概述 1.2 DDBS设计内容 全局模式设计 分片和分布 局部数据库设计 DDB设计 各个应用的原发站点 DDBS设计 相关应用需求 各个应用在每个站点的激活频率 各个应用对要求访问数据对象的访问次数、类型和统计分布 应用设计

1 分布式数据库设计概述 1.3 DDBS设计目标 尽量减少通信次数和通信量，90/10准则 本地性或近地性 分片和分布方案（本地和远程访问次数）择优 冗余增加了可靠性、可用性，提高了效率 DDBS 设计目标 控制数据适当冗余 维护数据一致性开销增加 各站点可以分担整个工作任务 工作负荷分布 本地性降低 存储能力和费用

1.4 DDBS设计方法 1 分布式数据库设计概述 自顶向下方法（重构法） DDBS 设计方法 自底向上方法（组合法） 混合方法

2 自顶向下设计DDB 2.1 步骤和内容 自顶向下设计过程 需求分析 视图设计 概念设计 分布设计 物理设计 观察与监视 系统需求 全局概念模式 访问模式 外部模式定义 局部概念模式 物理模式 用户输入 视图集成 用户 输入 反馈 自顶向下设计过程

假若有全局关系R 被分片为子关系(片段)集合 R = {R1, R2, …, Rn}, 则 R满足 完整性 2.2 数据的分片设计 2 自顶向下设计DDB 分片原则 假若有全局关系R 被分片为子关系(片段)集合 R = {R1, R2, …, Rn}, 则 R满足 完整性 ?x  R,  RiR 必有 xRi ，i=1,2,…,n 可重构性 存在函数 g 使得R = g(R1, R2, …, Rn) 即，R=∪ Ri (水平分片）,R=∞ Ri （垂直分片） 不相交性 Ri ∩ Rj =空集,i≠j,i,j=1,2,…,n(水平分片) Ri ∩ Rj =主键属性,i,j=1,2,…,n(垂直分片)

两个站点 : Sa, Sb Qa   Qb Sa Sb 职工关系 E (e#, name, loc, sal,…) 查询: 2.2 数据的分片设计 2 自顶向下设计DDB 举例 职工关系 E (e#, name, loc, sal,…) 查询: Qa: select * Qb: select * from E from E where loc=Sa where loc=Sb and… and ... 两个站点 : Sa, Sb Qa   Qb Sa Sb

e# NM Loc Sal E .. .. F .. .. e# NM Loc Sal e# NM Loc Sal 2.2 数据的分片设计 2 自顶向下设计DDB 举例 e# NM Loc Sal E 5 Joe Sa 1000 7 Sally Sb 2500 8 Tom Sa 500 .. .. F e# NM Loc Sal e# NM Loc Sal 5 Joe Sa 1000 7 Sally Sb 2500 .. 8 Tom Sa 500 .. 站点 Sb 站点Sa

R = { R1, R2 } 基本水平分片 以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。 2.2 数据的分片设计 2 自顶向下设计DDB 基本水平分片 基本水平分片 以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。 R = { R1, R2 } R1 = loc=Sa(E) R2 = loc=Sb(E)

P = {p1, p2, …, pn}是一简单谓词集合，为保证分片的正确性，P必须是： 2.2 数据的分片设计 2 自顶向下设计DDB 基本水平分片 若 R = {R1, R2, …, Rn}, 则 完整性 对于每一个元组 tR,  RiR 使得 tRi 不相交性 对tRi,  Rj 使得 tRj, i  j 可重构性 操作是∪ (可以忽略, 因为完整性就蕴含着) R = ∪{R1, R2, …, Rn} P = {p1, p2, …, pn}是一简单谓词集合，为保证分片的正确性，P必须是： 完整的：同一分片中的任意两个元组被应用同样概率访问。 最小的：集合P中的所有谓词与应用密切相关。(不同分片中的元组被访问的概率是不同的) 具有完整性和最小性不是必要条件, 但是对于简化分配问题有好处

例子 则可能有的水平分段限定 2 自顶向下设计DDB 2.2 数据的分片设计 基本水平分片 例子 EMP ( E#, NAME, DEPT, JOB, SAL, TEL, …) DEPT={1,2} JOB={‘P’, ‘-P’} 假定，应用经常查询的内容是属于部门1且是程序员的职员。 则可能有的水平分段限定 P={ DEPT=1} （不是完整的） P={DEPT=1, JOB=‘P’} （是完整的、最小的） P={DEPT=1, JOB=‘P’, SAL>500} （完整的，不是最小的）

如何保证分片原则 “手工”检查! e.g., R1 = loc=‘Sa’ E ; R2 =  loc=‘Sb’ E 2.2 数据的分片设计 2 自顶向下设计DDB 基本水平分片 如何保证分片原则 “手工”检查! e.g., R1 = loc=‘Sa’ E ; R2 =  loc=‘Sb’ E 生成具有满足分段原则的限定谓词

设有关系 E (e#,name,Loc,sal,A,…), 查询使用的简单谓词（Ai  Value）是: 2.2 数据的分片设计 2 自顶向下设计DDB 谓词生成举例 设有关系 E (e#,name,Loc,sal,A,…), 查询使用的简单谓词（Ai  Value）是: A<10, A>5, Loc = Sa, Loc = Sb 下一步: - 生成 “小项” 谓词 - 消除无用谓词 给定简单谓词集 Pr= { p1, p2,.. pn }, 则“小项”谓词（minterm predicate）形式: p1*  p2*  …  pn* 这里 pk* 是 pk 或是 ¬pk

(1) A<10  A>5  Loc=SA  Loc=SB 2.2 数据的分片设计 2 自顶向下设计DDB 小项谓词选择 (1) A<10  A>5  Loc=SA  Loc=SB (2) A<10  A>5  Loc=SA  ¬(Loc=SB) (3) A<10  A>5  ¬(Loc=SA)  Loc=SB (4) A<10  A>5  ¬(Loc=SA)  ¬(Loc=SB) (5) A<10  ¬(A>5)  Loc=SA  Loc=SB (6) A<10  ¬(A>5)  Loc=SA  ¬(Loc=SB) (7) A<10  ¬(A>5)  ¬(Loc=SA)  Loc=SB (8) A<10  ¬(A>5)  ¬(Loc=SA)  ¬(Loc=SB)

(9) ¬(A<10)  A>5  Loc=SA  Loc=SB 2.2 数据的分片设计 2 自顶向下设计DDB 小项谓词选择 (9) ¬(A<10)  A>5  Loc=SA  Loc=SB (10) ¬(A<10)  A>5  Loc=SA ¬(Loc=SB) (11) ¬(A<10)  A>5 ¬(Loc=SA)  Loc=SB (12) ¬(A<10)  A>5 ¬(Loc=SA) ¬(Loc=SB) (13) ¬(A<10) ¬(A>5)  Loc=SA  Loc=SB (14) ¬(A<10) ¬(A>5)  Loc=SA ¬(Loc=SB) (15) ¬(A<10) ¬(A>5) ¬(Loc=SA)  Loc=SB (16) ¬(A<10) ¬(A>5) ¬(Loc=SA) ¬(Loc=SB)

2 自顶向下设计DDB 2.2 数据的分片设计 R2: 5 < A < 10  Loc=SA 分片结果 R2: 5 < A < 10  Loc=SA R3: 5 < A < 10  Loc=SB R6: A  5  Loc=SA R7: A  5  Loc=SB R10: A  10  Loc=SA R11: A  10  Loc=SB

注:无用段的消除依赖于应用的语义 e.g.: 如果 LOC 可以是  SA,  SB, 则最终分段集合应该加上 2 自顶向下设计DDB 2.2 数据的分片设计 2 自顶向下设计DDB 注:无用段的消除依赖于应用的语义 e.g.: 如果 LOC 可以是  SA,  SB, 则最终分段集合应该加上 R4: 5 <A <10  Loc  SA  Loc  SB R8: A  5  Loc  SA  Loc  SB R12: A  10  Loc  SA  Loc  SB

小项选择率（minterm selectivity） 对某一给定小项谓词用户查询可能选择到的元组数 2.2 数据的分片设计 2 自顶向下设计DDB 分片数量信息 小项选择率（minterm selectivity） 对某一给定小项谓词用户查询可能选择到的元组数 访问频率（Access frequency）用户应用访问数据的频率 小项访问频率可以通过用户查询频率获得

Qa: select * Qb: select * 2.2 数据的分片设计 2 自顶向下设计DDB 如何选择小项谓词举例 例子 E(#, NM, LOC, SAL,…) 有查询应用 Qa: select * Qb: select * from E from E where LOC=Sa where LOC=Sb and … and ...

R2={  loc=Sa E,  loc=Sb E } (3) Pr = {LOC=Sa, LOC=Sb, Sal<1000} 2.2 数据的分片设计 2 自顶向下设计DDB 三种选择 (1) Pr = { } R1 ={ E } (2) Pr = {LOC=Sa, LOC=Sb} R2={  loc=Sa E,  loc=Sb E } (3) Pr = {LOC=Sa, LOC=Sb, Sal<1000} R3={ loc=Sa  sal<1000 E, loc=Sa  sal1000 E, loc=Sb  sal<1000E, loc=Sb  sal1000 E }

R3 R1 R2 R2 是好的… Qa: Select … loc = Sa ... Qb: Select … loc = Sb ... 2.2 数据的分片设计 2 自顶向下设计DDB Loc=Sa  sal < 1000 Qa: Select … loc = Sa ... Qb: Select … loc = Sb ... Loc=Sa  sal  1000 R2 是好的… ( R1 , R3不好 ) R3 R1 R2 Loc=Sb  sal < 1000 Loc=Sb  sal  1000 图示

R1 Qa: Select … loc = Sa ... Qb: Select … loc = Sb ... 2 自顶向下设计DDB 2.2 数据的分片设计 2 自顶向下设计DDB Loc=Sa  sal < 1000 Qa: Select … loc = Sa ... 此处元组有较 高的选择概率 Qb: Select … loc = Sb ... Loc=Sa  sal  1000 R1 Loc=Sb  sal < 1000 此处元组选 择概率较低 Loc=Sb  sal  1000 分段内元组选择概率不等 因此 R1 不好... 理由

R2 Qa: Select … loc = Sa ... Qb: Select … loc = Sb ... 因此 R2好... 2.2 数据的分片设计 2 自顶向下设计DDB Loc=Sa  sal < 1000 Qa: Select … loc = Sa ... 元组选择 概率相等 Qb: Select … loc = Sb ... Loc=Sa  sal  1000 R2 Loc=Sb  sal < 1000 因此 R2好... Loc=Sb  sal  1000 R3不好 ... 理由

从另一个关系的属性性质或水平分片推导出来 例子 SC(S#, C#, GRADE) S ( S#, SNAME, AGE, SEX) 要求： 2.2 数据的分片设计 2 自顶向下设计DDB 导出水平分片 导出分片 从另一个关系的属性性质或水平分片推导出来 例子 SC(S#, C#, GRADE) S ( S#, SNAME, AGE, SEX) 要求： 将SC划分为男生各门课成绩和女生的各门成绩

2 自顶向下设计DDB 2.2 数据的分片设计 按S的属性导出 按S的水平分片（SF/SM）导出 导出水平分片例子 Define fragment SC1 as Select SC.S#,C#,GRADE From SC, S Where SC.S#=S.S# and SEX=‘M’ Define fragment SC2 as Where SC.S#=S.S# and SEX=‘F’ 按S的水平分片（SF/SM）导出 Select * From SC Where S# in (Select SF.S from SF) Select * From SC Where S# in (Select SM.S from SM)

通过“投影”操作把一个全局关系的属性分成若干组，基本目标是将使用频繁的属性聚集在一起 2.2 数据的分片设计 2 自顶向下设计DDB 垂直分片和垂直群集 通过“投影”操作把一个全局关系的属性分成若干组，基本目标是将使用频繁的属性聚集在一起 全局关系R={Ri},i=1,2,…,n 如果属性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=Ap,i≠j，Ap为R的码或元组标识符，则称{Ri},i=1,2,…,n}是关系R的一个垂直分片。 如果属性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=（Ap, A-p),i≠j，A-p为R的一个或多个非码属性时，称{Ri},i=1,2,…,n}是关系R的一个垂直群集。

EMP(E#, NAME, SAL, TEL, MAGNUM, DEPT) 2.2 数据的分片设计 2 自顶向下设计DDB 垂直分片/垂直群集例子 EMP(E#, NAME, SAL, TEL, MAGNUM, DEPT) 假定 Key: E# 主要应用: Sa 站点查询NAME, SAL, TEL; Sb 站点查询NAME, MAGNUM, DEPT 垂直分片:EMP1(E#, NAME, SAL, TEL) EMP2(E#, MAGNUM, DEPT) 垂直群集:EMP1(E#, NAME, SAL, TEL) EMP2(E#, NAME, MAGNUM, DEPT)

2.2 数据的分片设计 2 自顶向下设计DDB 垂直分片例子 E E2 E1

例子: E1(#,NM,LOC) E2(#,SAL) E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) 2.2 数据的分片设计 2 自顶向下设计DDB 垂直分片设计 例子: E1(#,NM,LOC) E2(#,SAL) E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL) ?

非键属性 A1, A2,…,An 应用 Q1, Q2,….,Qm freq(Qi) = Qi 的访问频率 2 自顶向下设计DDB 2.2 数据的分片设计 2 自顶向下设计DDB 属性的亲和关系 非键属性 A1, A2,…,An 应用 Q1, Q2,….,Qm freq(Qi) = Qi 的访问频率

2.2 数据的分片设计 2 自顶向下设计DDB 属性和矩阵 75 78 2 1 A4 79 4 A5 97 48 45 A3 100 50 A2 96 A1 R1[K,A1,A2,A3] R2[K,A4,A5]

A1 A2 A5 A4 A3 行列调整寻找分割点 78 75 2 1 97 4 48 45 79 100 50 96 2 自顶向下设计DDB 2.2 数据的分片设计 2 自顶向下设计DDB 属性和矩阵 78 75 2 1 A4 97 4 48 45 A3 79 A5 100 50 A2 96 A1 行列调整寻找分割点

穷举属性亲和矩阵的列排列 发现好的 “分割点” 行与列要同时调整 极大化每个分割内的亲合力（affinity）, 极小化跨分割的访问 2.2 数据的分片设计 2 自顶向下设计DDB 垂直分片算法 穷举属性亲和矩阵的列排列 行与列要同时调整 发现好的 “分割点” 极大化每个分割内的亲合力（affinity）, 极小化跨分割的访问

2.2 数据的分片设计 2 自顶向下设计DDB 分片小结 水平 基本： R 根据 local属性 导出 根据外键关系 垂直 R

2.2 数据的分片设计 2 自顶向下设计DDB 分片小结 R 水平 R1 R2 垂直 R11 R12 R21 R22 混合分段

2.2 数据的分片设计 2 自顶向下设计DDB 分片小结 U 水平 垂直 R12 R21 R22 R11 混合分段的重构

在满足用户需求的前提下, 把设计好的数据片段分配到相应的站点上存储 例子: E(#,NM,LOC,SAL)  2.3 数据的分配设计 2 自顶向下设计DDB 分配的概念 在满足用户需求的前提下, 把设计好的数据片段分配到相应的站点上存储 例子: E(#,NM,LOC,SAL)  R1 = loc=Sa E ; R2 = loc=Sb E Qa: select … where loc=Sa... Qb: select … where loc=Sb… R1,R2 存 放在哪? Site b Site a ?

2 自顶向下设计DDB 2.3 数据的分配设计 分配方法 最佳适应法 非冗余分配设计方法 其他方法 应用需求 分配方法 确定非复制问题的解 确定一组站点分配副本 所有得益站点法 冗余分配的设计方法 附加复制法 确定非复制问题的解 从最有益处增加副本 到附加复制无好处为止

什么是段的最好配置/什么是最好的冗余副本数: 极小化查询响应时间 极大化吞吐量 极小化 “代价” ... 约束? 有效的存储空间 2.3 数据的分配设计 2 自顶向下设计DDB 优化问题 什么是段的最好配置/什么是最好的冗余副本数: 极小化查询响应时间 极大化吞吐量 极小化 “代价” ... 约束? 有效的存储空间 有效的带宽, 站点处理能力,… 保持 90% 的响应时间低于 X（如0.5秒）

Total cost = Read Cost + Write Cost + Storage Cost 2.3 数据的分配设计 2 自顶向下设计DDB 分配的简化模型 单个片段 F 站点 S1, … Sm 变量 X1, …, Xm 0 如果 F 不在 Sj上存储 1 如果 F 在 Sj上存储 Total cost = Read Cost + Write Cost + Storage Cost 确定 Xj 的值, 1  j  m, 使总代价极小 Xj =

. 读代价 3 ci,3 ci,1 ci,2 1 2 Read cost =  [ti  MIN Cij] F 2 自顶向下设计DDB 2.3 数据的分配设计 2 自顶向下设计DDB 分配的简化模型 . 3 i ci,3 ci,1 ci,2 ti F 1 2 读代价 m Read cost =  [ti  MIN Cij] i: 读申请源站点 ti: 站点Si上的读申请激活次数 Cij: 从 Si读Sj站点分段F的代价 i=1 j

. Write cost =  Xj ui C’ij 写代价 i i: 写申请源站点 j: 被更新站点 2.3 数据的分配设计 2 自顶向下设计DDB 分配的简化模型 . i F Updates 写代价 ui m m Write cost =  Xj ui C’ij i: 写申请源站点 j: 被更新站点 Xj: 0 if F not stored at Sj 1 if F stored at Sj ui: 站点 Si 上更新激活次数 C’ij: 从站点 Si 更新 Sj 分段 F 的代价 i=1 j=1

存储代价 Store Cost =  Xi di Xi: 0 if F not stored at Si 2.3 数据的分配设计 2 自顶向下设计DDB 分配的简化模型 存储代价 m Store Cost =  Xi di Xi: 0 if F not stored at Si 1 if F stored at Si di: 站点 Si 存储分段 F 的代价 i=1

目标函数 min  [ti MIN Cij +  Xj  ui  C’ij ] +  Xi  di 2.3 数据的分配设计 2 自顶向下设计DDB 分配的简化模型 目标函数 min  [ti MIN Cij +  Xj  ui  C’ij ] +  Xi  di m m i=1 j j=1 m i=1 即使最简单的公式也是 NP-完全问题 通常, 使用方法 尽可能将片段分配在被局部访问位置

“最佳适应” 方法（非冗余分配） Bij = k Fkj  Nki “所有得益站点” 方法（冗余分配） 2.3 数据的分配设计 2 自顶向下设计DDB 分配方法 “最佳适应” 方法（非冗余分配） Bij = k Fkj  Nki “所有得益站点” 方法（冗余分配） Bij = k Fkj  Rki - c  k j’jFkj’  Uki i 片段下标 j 站点下标 k 应用下标 Fkj 应用k 在站点j上激活的频率 Rki 应用k被激活一次,对片段i读的次数 Uki 应用k被激活一次,对片段i写的次数 Nki 应用k被激活一次,对片段i读写的总次数

2 自顶向下设计DDB 2.3 数据的分配设计 最佳适应法 所有得益站点法 附加复制法 水平分片情况 将片断Ri分配到访问Ri次数最多的那个站点上 Bij= kFkj*Nki 所有得益站点法 将片断Ri的副本分配到所有得益站点j上 Bij= kFkj*Rki -c*k j’≠j Fkj’*Uki 如Bij ＞0，则站点j是得益站点，放置Ri的一个副本 附加复制法 Di表示片断Ri的冗余度（副本个数）,Fi表示Ri在所有站点都复制的得益

假设关系R垂直分片R1和R2, R1分配到s站点, R2分配到t站点. 2.3 数据的分配设计 2 自顶向下设计DDB 垂直分片情况 假设关系R垂直分片R1和R2, R1分配到s站点, R2分配到t站点. 应用组As: 自站点s发出, 只使用Rs, 得益 BAs =  Fks Nki ( k  As) 应用组Ar: 自站点t发出, 只使用Rt, 得益 BAt =  Fkt Nki ( k  At) 应用组A1: 由站点r发出, 原先使用Rt或Rs(本地), 现在要一次远程，损失 BA1 =  Fkr Nki ( k  A1) 应用组A2: 由站点r发出, 原先使用R(本地), 现在要两次远程，损失 BA2 =  Fkr Nki ( k  A2) 应用组A3: 由不同于站点r,s,t的站点发出, 要访问Rt和Rs, 损失 BA1 =   Fkj Nki ( k  A3,j≠ r,s,t) 分配得益 Bist = BAs + BAt - BA1 - BA2 - BA3

2.3 数据的分配设计 2 自顶向下设计DDB 垂直分片情况 r s 其他 站点 t Rt R Rs 网络 A1 A2 As At A3

3 DATAID-D方法 3.1 与集中式数据库的异同 分布式数据库设计阶段 需求分析 概念设计 分布要求设计 全局逻辑设计 分布设计 局部逻辑设计 局部物理设计 收集分布信息 水平分片谓词 每一应用在各站点激活频率 概念设计之后进行 收集分布信息 分布要求和全局逻辑模式作为输入 形式为全局数据库模式和逻辑访问表 输出为分片模式和分配模式 全局逻辑设计之后进行

3 DATAID-D方法 3.2 设计步骤 说明： 1.设计数据字典； 2.全局数据模式； 3.全局操作模式； 4.简化全局模式； 5.逻辑访问表； 6.各站点逻辑模式； 7.各站点访问表； 8.局部逻辑模式 （关系或Codasyl）； 9.局部物理模式 （关系或Codasyl） 全局逻辑设计 分布设计 局部逻辑设计 逻辑设计 需求分析 概念设计 分布要求分析 局部物理设计 1 8 7 6 5 4 3 2 9 要求 频率表 划分表 极化表

分布要求分析阶段 频率表：各站点上每一应用激活次数（假设所有应用在所有站点上都能执行） 划分表：可用于模式中各实体的潜在水平分片规则 3.3 分布要求分析阶段 3 DATAID-D方法 分布要求分析 用户分布要求 全局数据概念模型 全局数据操作模式 应用频率表 实体划分表 应用极化表 分布要求分析阶段 频率表：各站点上每一应用激活次数（假设所有应用在所有站点上都能执行） 划分表：可用于模式中各实体的潜在水平分片规则 极化表：指明由一个站点发出的一给定应用访问一给定片段的频率（定量分析方法）

分布设计阶段 分片设计 非冗余分配 冗余分配 局部模式的重新构造 3 DATAID-D方法 3.4 分布设计阶段 全局数据模式 站点逻辑模式 3.4 分布设计阶段 3 DATAID-D方法 全局数据模式 分布设计 站点逻辑模式 逻辑访问表 站点逻辑访问表 分布要求 分布设计阶段 分片设计 非冗余分配 冗余分配 局部模式的重新构造

三个站点 数据库存储内容 三个应用 4 实例研究：飞机订票系统 4.1 实例研究概述 站点1：丹佛机场（CO） 站点2：纽约机场（NY） 站点3：亚特兰大机场（GA） 数据库存储内容 机场规程 班机调度 班机可用情况 旅客订票情况 三个应用 订票应用 登记应用 起飞应用

4 实例研究：飞机订票系统 4.2 数据库的全局数据模式 班机 订票 从 到 机场 登记 旅客 到达时间 机号 日期 可用座位 起飞时间 符号 城市 进入口 座位图 延期 区域 安全规则 种类 座位号 检查行李 名字 电话 权力

4 实例研究:飞机订票系统 4.3 订票应用全局操作模式 种类[w] 电话[w] 2 40 机场 3 20000 班机 日期[k] 从 可用座位[o、w] 到 到达时间[k] 名字[w] 1 100000 旅客 订票 实体左下角和右下角的数字表示：示例总数和应用选择的平均示例数 访问数据库中的①起飞与到达机场、②起飞与到达时间和③班机日期，以k表示这些关键词 确定班机后，建立旅客的一个新的示例及联系“订票”的一个示例，把用户的信息（名字、电话写入数据库） O表示输出，w表示写入

4 实例研究:飞机订票系统 4.4 登记应用全局操作模式 1 100000 旅客 20000 班机 机号[k] 日期[k] 座位图[o、w] 根据数据库中的①旅客名字，②班机号，③班机日期，查明有关旅客和班机的示例，显示“种类”信息。 根据“种类”信息和座位图，将一个座位号分配给旅客，并写入座位图和座位号属性，以及旅客的检查行李号

4 实例研究:飞机订票系统 4.5 起飞应用全局操作模式 1 40 机场 30 20000 班机 日期[k] 符号[k] 起飞时间[k, o] 机号[o] 从 到 出入口[o] 延期[o] 城市[o] 符号[o] 到达时间[k, o] 产生即将离开机场的30架班机的信息显示在TV监视器上。 根据数据库中的①机场符号，②当前日期，③起飞时间，④到达时间，查明①班机号、 ②起飞时间、 ③出入口、 ④延期、⑤目的地机场符号、⑥目的地城市，显示出来。

实体访问表：班机 属性 操作 a（订票） b（登记） c（起飞） 机号 k o 日期 座位图 o/w 进入口 延期 可用座位 4.6 实体逻辑访问表 4 实例研究:飞机订票系统 属性 操作 a（订票） b（登记） c（起飞） 机号 k o 日期 座位图 o/w 进入口 延期 可用座位 实体访问表：班机

实体访问表：机场 属性 操作 a（订票） b（登记） c（起飞） 符号 k k/o 城市 o 权力 区域 安全规则 4.6 实体逻辑访问表 4 实例研究:飞机订票系统 属性 操作 a（订票） b（登记） c（起飞） 符号 k k/o 城市 o 权力 区域 安全规则 实体访问表：机场

4.6 实体逻辑访问表 4 实例研究:飞机订票系统 属性 操作 a（订票） b（登记） c（起飞） 名字 w k 电话 实体访问表：旅客

4.6 实体逻辑访问表 4 实例研究:飞机订票系统 属性 操作 a（订票） b（登记） c（起飞） 起飞时间 k k/o 联系访问表：从

4.6 实体逻辑访问表 4 实例研究:飞机订票系统 属性 操作 a（订票） b（登记） c（起飞） 到达时间 k k/o 联系访问表：到

4.6 实体逻辑访问表 4 实例研究:飞机订票系统 属性 操作 a（订票） b（登记） c（起飞） 种类 w o 联系访问表：订票

4.6 实体逻辑访问表 4 实例研究:飞机订票系统 属性 操作 a（订票） b（登记） c（起飞） 座位号 w 检查行李 联系访问表：登记

4 实例研究:飞机订票系统 4.7 分布要求分析 站点1：丹佛（CO） 站点2：纽约（NY） 站点3：亚特兰大（GA） 应用a：订票 应用b：登记 应用c：起飞

4 实例研究:飞机订票系统 4.7 分布要求分析 将机场的区域属性选作为机场实体的划分准则 将旅客电话号码前三位（区域码）作为旅客实体的划分属性 谓词选择性表示按照该准则划分各类元组所占的百分数

4 实例研究:飞机订票系统 4.7 分布要求分析 两种方法划分班机实体，应用不同的联系“从”或“到”和机场划分区域于同一基本划分，结果不同。 根据第一订票地点和班机起飞区域做导出划分 机场——〉班机——〉乘客

4.7 分布要求分析 4 实例研究:飞机订票系统

极化表 a b c 1 2 3 80 × 100 75 70 ... … 4 实例研究:飞机订票系统 4.7 分布要求分析 P1 P2 P3 按区域划分机场 P1 80 × 100 P2 75 P3 按出发机场划分航班 70 ... …

分四步： 对每一实体选择分片原则 确定非冗余分配 在非冗余分配上引入冗余 在每一站点上重新构造局部模式 4 实例研究:飞机订票系统 4.8 分布设计 4 实例研究:飞机订票系统 分四步： 对每一实体选择分片原则 确定非冗余分配 在非冗余分配上引入冗余 在每一站点上重新构造局部模式

旅客实体： 基于旅客预定的所有班机起飞的导出水平分段 4.8 分布设计 4 实例研究:飞机订票系统 1. 分片设计 机场实体： 基于区域的水平分段 机场1， 机场2， 机场3 班机实体：基于出发机场的导出水平分段 班机1，班机2， 班机3 旅客实体： 基于旅客预定的所有班机起飞的导出水平分段 旅客1，旅客2，旅客3，旅客4，旅客5，旅客6，旅客7，

2. 确定非冗余分配 根据分片原则 站点1：机场1， 班机1， 旅客1 站点2：机场2， 班机2， 旅客2 4.8 分布设计 4 实例研究:飞机订票系统 2. 确定非冗余分配 根据分片原则 站点1：机场1， 班机1， 旅客1 站点2：机场2， 班机2， 旅客2 站点3：机场3， 班机3， 旅客3 根据极化表和频率表 站点2：旅客4，旅客6，旅客7 站点3：旅客5（放在站点1也可以）

3. 冗余分配 有限冗余 旅客实体： 冗余超出了同一实体所有片断的效益 机场实体：不进行冗余分配 班机实体：不进行冗余分配 4.8 分布设计 4 实例研究:飞机订票系统 3. 冗余分配 冗余超出了同一实体所有片断的效益 机场实体：不进行冗余分配 班机实体：不进行冗余分配 有限冗余 旅客实体： 预定离开两个区域的乘客：，旅客4，旅客5，旅客6，放到两个站点上 预定离开三个区域的乘客：旅客7，放到三个站点上

4. 局部逻辑模式 4 实例研究:飞机订票系统 4.8 分布设计 班机1 从 站点1的局部模式 机场1 旅客1u 订票 旅客4u 旅客5u 到 订票 登记 机场1 旅客1u 旅客4u 旅客5u 旅客7 自然分配 站点1的局部模式 BC

4. 局部逻辑模式 4 实例研究:飞机订票系统 4.8 分布设计 班机2 从 站点2的局部模式 机场2 AC 旅客2u 订票 旅客4u 旅客7 订票 班机2 登记 到 从 到 自然分配 站点2的局部模式 机场2 AC

4. 局部逻辑模式 4 实例研究:飞机订票系统 4.8 分布设计 班机3 从 站点3的局部模式 机场3 AB 旅客3u 订票 旅客5u 旅客7 订票 班机3 登记 到 从 到 自然分配 站点3的局部模式 机场3 AB

将现有的各种不同的数据库模式集成为全局模式. 三个问题 5.1 自底向上方法要解决的问题 5 自底向上设计分布式数据库 将现有的各种不同的数据库模式集成为全局模式. 三个问题 选择公用数据库模型来描述数据库的全局模式 把每个站点上的本地模式翻译成公用数据模型 把各站点上的本地数据模式集成为一公用的全局模式

自底向上方法主要问题是构造一个全局模式（超视图）. 5.2 构造全局模式设计问题 5 自底向上设计分布式数据库 自底向上方法主要问题是构造一个全局模式（超视图）. 把各站点上的数据库模式看成是全局模式的一个视图 这个问题就可看作是视图综合问题 概括分层结构支持视图综合 经典方法就是生成三个实体：一个具有共同属性（超类型），两个具有不相交属性（子类型） 视图综合次序 一次把一个视图和全局模式进行综合，逐步构造起全局视图 通常，最好首先综合最大的或最重要的视图，然后跟着综合小的或者不重要的视图

5 自底向上设计分布式数据库 5.2 构造全局模式设计问题 班 机 班 机 班机 班机1 班机2 机号 出入口 机号 座位图 座位图 日期 机型 日期 可用座位 延期 可用座位 班机 班机1 班机2 机号 日期 可用座位 座位图 出入口 延期 机型

处理操作期间不一致的数据策略（5种，p64-65） 5.3 识别相似性和识别冲突 5 自底向上设计分布式数据库 识别相似性 模式命名相似性 模式结构相似性 不同Site上有相似应用, 使用各自DB的数据副本, 则这两Site之间有某些相似点. 识别冲突 命名冲突：同物异名（EMP,EMPLOYEE），异物同名 域差异 定标差异：计量单位不同(天、小时、分钟、秒） 结构差异：同一对象有的用实体描述, 有的用属性描述. 处理操作期间不一致的数据策略（5种，p64-65）

系统A概念模式 5 自底向上设计分布式数据库 5.4 自底向上综合的一个例子 订票 班机 登记 到 从 机场 旅客 起飞时间 到达时间 符号 城市 权力 区域 安全规则 座位号 检查行李 班机 订票 旅客 机号 日期 可用座位 进入口 座位图 延期 种类 名字 电话 系统A概念模式

系统B概念模式 5 自底向上设计分布式数据库 5.4 自底向上综合的一个例子 班机 订票 旅客 座位图 标识符 种类 起飞 可用座位 起飞时间 旅客 到达 到达时间 系统B概念模式 名字 电话

5 自底向上设计分布式数据库 5.4 自底向上综合的一个例子 订票 登记 综合后建立的全局模式 旅 客 班机 班机B 班机A 机场 可用座位 名字 飞机符(机号) 旅 客 订票 班机 日期 (1,3) 座位图 种类 出入口 电话 班机B 班机A 登记 起飞机场 起飞时间 到达机场 到达时间 座位号 从 到 检查行李 到达时间 起飞时间 机场 综合后建立的全局模式

5.4 数据集成实现方法 5 自底向上设计分布式数据库 XML Ontology View 数据集成

Exercise 1 已知有如下两种段分配: A> R1在Site1, R2在Site2, R3在Site3. B> R1和R2在Site1, R2和R3在Site3. 另已知有如下应用(所有应用的频率相同) A1: 在Site1上发出, 读5个 R1记录, 5个 R2记录 A2: 在Site3上发出, 读5个R3记录 , 5个R2记录 A3: 在Site2上发出, 读10个R2记录. 问: 1. 如果以本地应用为主要设计目标, 那个分配较优? 2. 假定A3改为要修改10个R2记录, 并仍以本地应用为其设计目标, 则那个分配方案较优?

A1 R1 A3 R2 A2 R3 方案A 5 5 站点1 站点2 站点3 A1 R1, R2 A3 A2 R2, R3 方案B 10 10 10 站点1 站点2 站点3 读取 更新

Exercise 2 图2-12 COMPANY关系数据库模式, 主码用下划线标出 EMPLOY DEPARTMENT FNAME MINIT LNAME ESSN BDATE ADDRESS SEX SALARY SUPERSSN DNO DEPARTMENT DNAME DNO MGRSSN MGRSTARTDATE DEPT_LOCATION DNO DLOCATION PROJECT PNAME PNO PLOCATION DNO WORKS_ON ESSN PNO HOURS DEPENDENT ESSN DEPENDENT_NAME SEX BDATE RELATIONSHIP 图2-12 COMPANY关系数据库模式, 主码用下划线标出

三个站点A,B,C 部门1（总部），部门2，部门3 在站点B上频繁访问EMPLOYEE,PROJECT中有关工作在部门2的雇员和该部门管辖的项目信息 在站点C上频繁访问EMPLOYEE,PROJECT中有关工作在部门3的雇员和该部门管辖的项目信息 雇员信息主要是指EMPLOYEE表中的FNAME,ESSN,SALARY,SUPERSSN属性 A，B，C站点上频繁访问本站点所在部门的项目工时信息 站点A供公司总部使用，经常存取为保险目的而纪录的DEPENDENT信息外，还定期地存取所有雇员和项目的信息

图2-13 站点的片段分配（b）站点B上的对应于部门2的关系片段 EMPD2 FNAME MINIT LNAME ESSN SALARY SUPERSSN DNO Alicia J Zelaya 999887777 25000 987654321 2 Jennifer S Wallace 43000 888665555 Ahmad V Jabbar 987987987 DEP2 DNAME DNO MGRSSN MGRSTARTDATE Administr 2 987654321 2003-01-01 DEP2_LOCS DNO DLOCATION 2 Statlond DEP2_ WORKSON ESSN PNO HOURS 333445555 10 10.0 999887777 30 30.0 987987987 35.0 5.0 987654321 20.0 15.0 DEP2 _PROJECT PNAME PNO PLOCATION DNO Computer 10 Startlond 2 Newbenef 30 图2-13 站点的片段分配（b）站点B上的对应于部门2的关系片段

图2-13 站点的片段分配（a）站点C上的对应于部门3的关系片段 EMPD3 FNAME MINIT LNAME SSN SALARY SUPERSSN DNO John B Smith 123456789 30000 333445555 3 Franklin T Wong 40000 888665555 Ramesh K Narayan 666884444 38000 Joyce A English 453453453 25000 DEP3 DNAME DNO MGRSSN MGRSTARTDATE Research 3 333445555 2003-05-22 DEP3_LOCS DNO DLOCATION 3 Bellaire Sugarlnd Houston DEP3 _WORKSON ESSN PNO HOURS 123456789 1 32.5 2 7.5 666884444 3 40.0 453453453 20.0 333445555 10.0 DEP3_PROJECT PNAME PNO PLOCATION DNO Product X 1 Bellaire 3 Product Y 2 ugarlnd Product Z Houston 图2-13 站点的片段分配（a）站点C上的对应于部门3的关系片段

图2-15 站点A上的对应于部门1（总部）的片断 EMPLOYEE PROJECT DEPENDENT FNAME MINIT LNAME SSN SALARY SUPERSSN DNO Alicia J Zelaya 999887777 25000 987654321 2 Jennifer S Wallace 43000 888665555 Ahmad V Jabbar 987987987 John B Smith 123456789 30000 333445555 3 Franklin T Wong 40000 Ramesh K Narayan 666884444 38000 Joyce A English 453453453 PROJECT PNAME PNUMER PLOCATION DNUM DEPENDENT ESSN DEPENDENT_NAME SEX BDATE RELATIONSHIP 图2-15 站点A上的对应于部门1（总部）的片断

Exercise 3 建立百货连锁店分布式数据库系统: 由一个总部和多个远程连锁店组成 总部和各个连锁店之间有数据交换，局域网和广域网 总部负责产生各类汇总表，如销售汇总表 各站点系统相对独立 总部统一管理各门店商品的业种和品牌信息，各门店也经常使用这两类信息 供应商、合同、商品和销售信息等经营基础数据都由各门店单独管理和使用，门店之间互不相关 整个连锁店的职员信息由总部管理，各门店只可以查询本部门的职员信息 该连锁店的会员卡实行全国联网消费，会员可以经常异地消费

基本关系模式（初步） DEPARTMENT EMPLOYEE CUSTOMER PRODUCT（p#，YEZHONG，PINPAI，…） CONTRACT SALES SUPPLIER

分布式数据库的创建方法（重构法/组合法） 自顶向下的设计方法 数据分片 数据分配 DATAID-D方法（分布要求分析和分布设计阶段） 总 结 分布式数据库的创建方法（重构法/组合法） 自顶向下的设计方法 数据分片 数据分配 DATAID-D方法（分布要求分析和分布设计阶段） 实例研究：飞机订票系统 自底向上方法