崔明义
（ mycui369@126.com)
计算机应用技术 2007级研究生
1,分布式数据库系统设计概述
2,自顶向下设计分布式数据库
3.DATAID-D方法
4,实例研究：飞机订票系统
5,自底向上设计分布式数据库分布式数据库系统设计第 2章分布式数据库设计概述1
创建方法1.1
组合法
1,剖析网络功能
2,剖析原有数据库系统
3,解决数据的一致性、
完整性和可靠性
4,难度较大通常是异构或者同构异质
DDBS
用户 1 用户 2 用户 n
分布式协调管理系统
DBMS1 DBMS2 DBMSm
网络分布式数据库设计概述1
DDBS创建方法1.1
重构法
1,根据实现环境和用户需求
2,按照 DDBS的设计思想和方法
3,从总体设计做起，包括
LDBS,重新建立一个 DDBS
4,可有效解决数据一致性、完整性和可靠性问题。
通常是同构异质或同构同质
DDBS
用户 1 用户 2 用户 n
分布式数据库管理系统网络
1.2 DDBS设计内容
1 分布式数据库设计概述
DDBS设计
DDB设计应用设计全局模式设计局部数据库设计相关应用需求各个应用的原发站点各个应用在每个站点的激活频率各个应用对要求访问数据对象的访问次数、类型和统计分布分片和分布
1.3 DDBS设计目标
1 分布式数据库设计概述
DDBS
设计目标本地性或近地性存储能力和费用尽量减少通信次数和通信量,90/10准则分片和分布方案（ 本地和远程访问次数 ）择优控制数据适当冗余冗余增加了可靠性、可用性，提高了效率维护数据一 致性开销增加工作负荷分布各站点可以分担整个工作任务本地性降低
1.4 DDBS设计方法
1 分布式数据库设计概述
DDBS
设计方法自顶向下方法（重构法）
混合方法自底向上方法（组合法）
2.1 步骤和内容
2 自顶向下设计 DDB
需求分析概念设计 视图设计分布设计物理设计观察与监视系统需求全局概念模式 访问模式 外部模式定义局部概念模式物理模式用户输入视图集成用户输入反馈反馈自顶向下设计过程
假若有全局关系 R 被分片为子关系 (片段 )集合
R = {R1,R2,…,R n},则 R满足
– 完整性
x? R,? Ri?R 必有 x?Ri,i=1,2,…,n
– 可重构性存在函数 g 使得 R = g(R1,R2,…,R n)
即,R=∪ Ri (水平分片）,R=∞ Ri （垂直分片）
– 不相交性
Ri ∩ Rj =空集,i≠j,i,j=1,2,…,n( 水平分片 )
Ri ∩ Rj =主键属性,i,j=1,2,…,n( 垂直分片 )
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 QbSa Sb
2.2 数据的分片设计
2 自顶向下设计 DDB
举例
e# NM Loc Sal
E 5
7
8
Sa 1000
Sally Sb 2500
Tom Sa 500
Joe
e# NM Loc Sal e# NM Loc Sal
5
8
Sa 1000
Tom Sa 500
Joe 7 Sb 2500Sally
..
..
..
..
F
站点 Sa 站点 Sb
2.2 数据的分片设计
2 自顶向下设计 DDB
举例
基本水平分片以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。
R = { R1,R2 }
R1 =?loc=Sa(E) R2 =?loc=Sb(E)
2.2 数据的分片设计
2 自顶向下设计 DDB
基本水平分片
若 R = {R1,R2,…,R n},则
– 完整性 对于每一个元组 t?R,? Ri?R 使得 t?Ri
– 不相交性 对?t?Ri, Rj 使得 t?Rj,i? j
– 可重构性 操作是 ∪ (可以忽略,因为完整性就蕴含着 )
R = ∪ {R1,R2,…,R n}
P = {p1,p2,…,p n}是一简单谓词集合，为保证分片的正确性,P必须是：
– 完整的：同一分片中的任意两个元组被应用同样概率访问。
– 最小的：集合 P中的所有谓词与应用密切相关。
– 具有完整性和最小性不是必要条件,但是对于简化分配问题有好处
2.2 数据的分片设计
2 自顶向下设计 DDB
基本水平分片
例子
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} （完整的，不是最小的）
2.2 数据的分片设计
2 自顶向下设计 DDB
基本水平分片如何保证分片原则
,手工”检查 !
e.g.,R1 =?loc=‘Sa’ E ; R2 =? loc=‘Sb’ E
生成具有满足分段原则的限定谓词
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 或是?p k
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)
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.2 数据的分片设计
2 自顶向下设计 DDB
小项谓词选择
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
分片结果
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
2.2 数据的分片设计
2 自顶向下设计 DDB
小项选择率（ minterm selectivity） 对某一给定小项谓词用户查询可能选择到的元组数
访问频率（ Access frequency） 用户应用访问数据的频率
– 小项访问频率可以通过用户查询频率获得
2.2 数据的分片设计
2 自顶向下设计 DDB
分片数量信息
例子
E(#,NM,LOC,SAL,…)
有查询应用
Qa,select * Qb,select *
from E from E
where LOC=Sa where LOC=Sb
and … and,..
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 }
三种选择
2.2 数据的分片设计
2 自顶向下设计 DDB
Loc=Sa?
sal < 1000
Loc=Sa?
sal? 1000
Loc=Sb?
sal < 1000
Loc=Sb?
sal? 1000
R1 R3R2
Qa,Select … loc = S a,..
Qb,Select … loc = S b,..
R2 是好的 …
( R1,R3不好 )
2.2 数据的分片设计
2 自顶向下设计 DDB
图示
Loc=Sa?
sal < 1000
Loc=Sa?
sal? 1000
Loc=Sb?
sal < 1000
Loc=Sb?
sal? 1000
R1
Qa,Select … loc = S a,..
Qb,Select … loc = S b,..此处元组有较高的选择概率此处元组选择概率较低分段内元组选择概率不等因此 R1 不好,..
2.2 数据的分片设计
2 自顶向下设计 DDB
理由
Loc=Sa?
sal < 1000
Loc=Sa?
sal? 1000
Loc=Sb?
sal < 1000
Loc=Sb?
sal? 1000
R2
Qa,Select … loc = S a,..
Qb,Select … loc = S b,..元组选择概率相等因此 R2好,..
R3不好,..
理由
2.2 数据的分片设计
2 自顶向下设计 DDB
导出分片从另一个关系的属性性质或水平分片推导出来
例子
SC(S#,C#,GRADE)
S ( S#,SNAME,AGE,SEX)
要求：
将 SC划分为男生各门课成绩和女生的各门成绩
2.2 数据的分片设计
2 自顶向下设计 DDB
导出水平分片
按 S的属性导出
Define fragment SC1 as
Select SC.S#,C#,GRADE From SC,S
Where SC.S#=S.S# and SEX=‘M’
Define fragment SC2 as
Select SC.S#,C#,GRADE From SC,S
Where SC.S#=S.S# and SEX=‘F’
按 S的水平分片（ SF/SM）导出
– Define fragment SC1 as
Select * From SC Where S# in (Select SF.S from SF)
Define fragment SC2 as
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的一个 垂直群集 。
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
垂直分片 /垂直群集例子
2.2 数据的分片设计
2 自顶向下设计 DDB
E1
# NM Loc S a l
5 J o e Sa 1000
7 S a lly Sb 2500
8 F r e d Sa 1500
…
# NM Loc
5 J o e Sa
7 S a lly Sb
8 F r e d Sa
…
# S a l
5 1000
7 2500
8 1500
…
E
E2
垂直分片例子例子,E1(#,NM,LOC)
E2(#,SAL)
E(#,NM,LOC,SAL) E1(#,NM)
E2(#,LOC)
E3(#,SAL)
2.2 数据的分片设计
2 自顶向下设计 DDB
垂直分片设计
非键属性 A1,A2,…,A n
应用 Q1,Q2,….,Q m
freq(Qi) = Qi 的访问频率
2.2 数据的分片设计
2 自顶向下设计 DDB
属性的亲和关系
)A,u s e ( Q )A,u s e ( Q|k kji jkik )f r e q ( Q)A,a f f ( A
7578021A4
7975400A5
40974845A3
024810050A2
01455096A1
A5A4A3A2A1
R1[K,A1,A2,A3] R2[K,A4,A5]
2.2 数据的分片设计
2 自顶向下设计 DDB
属性和矩阵
0787521A4
97044845A3
4757900A5
482010050A2
45105096A1
A3A4A5A2A1
行列调整寻找分割点
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
分片小结混合分段的重构
R11 R12 R21 R22
水平垂直
U
2.2 数据的分片设计
2 自顶向下设计 DDB
分片小结
在满足用户需求的前提下,把设计好的数据片段分配到相应的站点上存储
例子,E(#,NM,LOC,SAL)?
R1 =?loc=Sa E ; R2 =?loc=Sb E
Qa,select … where loc=Sa...
Qb,select … where loc=Sb…
Site a Site b
R1,R2 存放在哪?
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的概念
2.3 数据的分配设计
2 自顶向下设计 DDB
分配方法分配方法非冗余分配设计方法最佳适应法其他方法冗余分配的设计方法所有得益站点法附加复制法应用需求确定非复制问题的解确定一组站点分配副本确定非复制问题的解从最有益处增加副本到附加复制无好处为止
什么是段的最好配置 /什么是最好的冗余副本数,
– 极小化查询响应时间
– 极大化吞吐量
– 极小化,代价”
–,..
约束?
– 有效的存储空间
– 有效的带宽,站点处理能力,…
– 保持 90% 的响应时间低于 X（如 0.5秒）
–,..
2.3 数据的分配设计
2 自顶向下设计 DDB
优化问题单个片段 F 站点 S1,… S m
变量 X1,…,X m
0 如果 F 不在 Sj上存储
1 如果 F 在 Sj上存储
Total cost = Read Cost + Write Cost +
Storage Cost
确定 Xj 的值,1? j? m,使总代价极小
Xj =
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型读代价
Read cost =? [ti? MIN Cij]
i,读申请源站点
ti,站点 Si上的读申请激活次数
Cij,从 Si读 Sj站点分段 F的代价
i=1
m
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型
.
.
.
3
i
ci,3
ci,1 ci,2
tiF
F F
.
1 2
j
写代价
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
m m
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型
.,
.,
i
F
F F
Updates
ui
存储代价
Store Cost =? Xi di
Xi,0 if F not stored at Si
1 if F stored at Si
di,站点 Si 存储分段 F 的代价
i=1
m
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型目标函数
min? [ti?MIN Cij +? Xj? ui?C’ij ]
+? Xi? di
ji=1 j=1
i=1
m m
m
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型
即使最简单的公式也是 NP-完全问题
通常,使用方法
– 尽可能将片段分配在被局部访问位置
,最佳适应” 方法（非冗余分配）
Bij =?k Fkj? Nk
,所有得益站点” 方法（冗余分配）
Bij =?k Fkj? Rki - ck?j’?jFkj’? Uki
i 片段下标 j 站点下标
k 应用下标 Fkj 应用 k 在站点 j上激活的频率
Rki 应用 k被激活一次,对片段 i读的次数
Uki 应用 k被激活一次,对片段 i写的次数
Nki 应用 k被激活一次,对片段 i读写的总次数
2.3 数据的分配设计
2 自顶向下设计 DDB
分配方法
最佳适应法
– 将片断 Ri分配到访问 Ri次数最多的那个站点上
– Bij=?kFkj*Nki
所有得益站点法
– 将片断 Ri的副本分配到 所有得益站点 j上
– Bij=?kFkj*Rki -c*?k?j’≠j Fkj’*Uki
– 如 Bij ＞ 0，则站点 j是得益站点，放置 Ri的一个副本
附加复制法
– Di表示片断 Ri的冗余度（副本个数）,Fi表示 Ri在所有站点都复制的得益
–
2.3 数据的分配设计
2 自顶向下设计 DDB
水平分片情况
iDi FD i )21()( )1(?
)(' ' ik jj kikjk kikjij DUFcRFB
假设关系 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
垂直分片情况
2.3 数据的分配设计
2 自顶向下设计 DDB
垂直分片情况
r
s
其他站点
tRt
R
Rs
网络
A1
A2
As
At
A3
分布式数据库设计阶段
– 需求分析
– 概念设计
– 分布要求设计
– 全局逻辑设计
– 分布设计
– 局部逻辑设计
– 局部物理设计
3.1 与集中式数据库的异同
3 DATAID-D方法收集分布信息
1,水平分片谓词
2,每一应用在各站点激活频率
3,概念设计之后进行收集分布信息
1,分布要求和全局逻辑模式作为输入
2,形式为全局数据库模式和逻辑访问表
3,输出为分片模式和分配模式
4,全局逻辑设计之后进行说明：
1.设计数据字典；
2.全局数据模式；
3.全局操作模式；
4.简化全局模式；
5.逻辑访问表；
6.各站点逻辑模式；
7.各站点访问表；
8.局部逻辑模式
（关系或 Codasyl）；
9.局部物理模式
（关系或 Codasyl）
全局逻辑设计分布设计局部逻辑设计逻辑设计需求分析概念设计分布要求分析局部物理设计
1
8
76
54
32
9
要求频率表 划分表极化表
3.2 设计步骤
3 DATAID-D方法
分布要求分析阶段
– 频率表：各站点上每一应用激活次数（假设所有应用在所有站点上都能执行）
– 划分表：可用于模式中各实体的潜在水平分片规则
– 极化表：指明由一个站点发出的一给定应用访问一给定片段的频率（定量分析方法）
分布要求分析用户分布要求全局数据概念模型全局数据操作模式应用频率表实体划分表应用极化表
3.3 分布要求分析阶段
3 DATAID-D方法
分布设计阶段
– 分片设计
– 非冗余分配
– 冗余分配
– 局部模式的重新构造分布设计全局数据模式逻辑访问表分布要求站点逻辑模式站点逻辑访问表
3.4 分布设计阶段
3 DATAID-D方法
三个站点
– 站点 1：丹佛机场（ CO）
– 站点 1：纽约机场（ NY）
– 站点 1：亚特兰大机场（ GA）
数据库存储内容
– 机场规程
– 班机调度
– 班机可用情况
– 旅客订票情况
三个应用
– 订票应用
– 登记应用
– 起飞应用
4.1 实例研究概述
4 实例研究：飞机订票系统
4.2 数据库的全局数据模式
4 实例研究：飞机订票系统班机 订票从 到机场登记旅客到达时间机号日期可用座位起飞时间符号城市进入口座位图延期区域安全规则种类座位号 检查行李名字 电话权力
4.3 订票应用全局操作模式
4 实例研究,飞机订票系统
1,实体左下角和右下角的数字表示：示例总数和应用选择的平均示例数
2,访问数据库中的 ① 起飞与到达机场,② 起飞与到达时间和 ③ 班机日期，以 k表示这些关键词
3,确定班机后，建立旅客的一个新的示例及联系“订票”的一个示例，把用户的信息（名字、电话写入数据库
4,O表示输出,w表示写入种类 [w]
电话 [w]
240
机场
320000
班机日期 [k]
起飞时间 [k]
符号 [k]
从可用座位 [o、
w]
到到达时间 [k]
名字 [w]
1100000
旅客订票
4.4 登记应用全局操作模式
4 实例研究,飞机订票系统
1100000
旅客
120000
班机机号 [k]
日期 [k]
座位图 [o,w] 座位号 [w] 检查行李 [w]
订票登记种类 [o] 名字 [k]
1,根据数据库中的 ①旅客名字，②班机号，③ 班机日期，查明有关旅客和班机的示例，显示“种类”信息。
2,根据“种类”信息和座位图，将一个座位号分配给旅客，并写入座位图和座位号属性，以及旅客的检查行李号
4.5 起飞应用全局操作模式
4 实例研究,飞机订票系统
140
机场
3020000
班机
3040
机场日期
[k]
符号 [k]
起飞时间 [k,
o]
机号 [o]
从到出入口 [o]延期 [o]
城市 [o]
符号 [o]
到达时间 [k,
o]
1,产生即将离开机场的 30架班机的信息显示在 TV监视器上 。
2,根据数据库中的①机场符号，②当前日期，③起飞时间,④ 到达时间，查明
①班机号,②起飞时间,③出入口,④ 延期,⑤ 目的地机场符号,⑥ 目的地城市，显示出来。
4.6 实体逻辑访问表
4 实例研究,飞机订票系统属性 操作
a（ 订票） b（登记） c（起飞）
机号 k o
日期 k k k
座位图 o/w
进入口 o
延期 o
可用座位 o/w
实体访问表：班机
4.6 实体逻辑访问表
4 实例研究,飞机订票系统属性 操作
a（ 订票） b（登记） c（起飞）
符号 k k/o
城市 o
权力区域安全规则实体访问表：机场
4.6 实体逻辑访问表
4 实例研究,飞机订票系统属性 操作
a（ 订票） b（登记） c（起飞）
名字 w k
电话 w
实体访问表：旅客
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
检查行李 w
联系访问表：登记
4.7 分布要求分析
4 实例研究,飞机订票系统站点 1：丹佛（ CO）
站点 2：纽约（ NY）
站点 3：亚特兰大（ GA）
应用 a：订票应用 b：登记应用 c：起飞
4.7 分布要求分析
4 实例研究,飞机订票系统
1,将机场的区域属性选作为机场实体的划分准则
2,将旅客电话号码前三位（区域码）作为旅客实体的划分属性
3,谓词选择性表示按照该准则划分各类元组所占的百分数
4.7 分布要求分析
4 实例研究,飞机订票系统
1,两种方法划分班机实体，应用不同的联系“从”或“到”和机场划分区域于同一基本划分，结果不同。
2,根据第一订票地点和班机起飞区域做导出划分
3,机场 —— 〉 班机 —— 〉 乘客
4.7 分布要求分析
4 实例研究,飞机订票系统
4.7 分布要求分析
4 实例研究,飞机订票系统极化表 a b c
1 2 3 1 2 3 1 2 3
按区域划分机场
P1 80 × 100
P2 75 × 100
P3 80 × 100
按出发机场划分航班
P1 70 100 80
P2 75 100 80
P3 70 100 80
..,… … … … … … … …
4.8 分布设计
4 实例研究,飞机订票系统分四步：
1,对每一实体选择分片原则
2,确定非冗余分配
3,在非冗余分配上引入冗余
4,在每一站点上重新构造局部模式
机场实体,基于区域的水平分段机场 1,机场 2,机场 3
班机实体：基于起飞机场的导出水平分段班机 1，班机 2,班机 3
旅客实体,基于旅客预定的所有班机起飞的导出水平分段旅客 1，旅客 2，旅客 3，旅客 4，旅客 5，旅客 6，旅客 7，
4.8 分布设计
4 实例研究,飞机订票系统
1,分片设计根据分片原则
站点 1：机场 1,班机 1,旅客 1
站点 2：机场 2,班机 2,旅客 2
站点 3：机场 3,班机 3,旅客 3
根据极化表和频率表
站点 2：旅客 4，旅客 5，旅客 6，旅客 7
站点 3：旅客 5
4.8 分布设计
4 实例研究,飞机订票系统
2,确定非冗余分配冗余超出了同一实体所有片断的效益
机场实体：不进行冗余分配
班机实体：不进行冗余分配有限冗余
旅客实体：
– 预定离开两个区域的乘客：，旅客 4，旅客 5，旅客 6，
放到两个站点上
– 预定离开三个区域的乘客：旅客 7，放到三个站点上
4.8 分布设计
4 实例研究,飞机订票系统
3,冗余分配班机 1
从 到订票登记到机场 1
旅客 1u
旅客 4u
旅客 5u
旅客 7
BC 站点 1的局部模式
4.8 分布设计
4 实例研究,飞机订票系统
4,局部逻辑模式自然分配班机 2
从 到订票登记到机场 2
旅客 2u
旅客 4u
旅客 6u
旅客 7
AC
站点 2的局部模式
4.8 分布设计
4 实例研究,飞机订票系统
4,局部逻辑模式自然分配班机 3
从 到订票登记到机场 3
旅客 3u
旅客 5u
旅客 6u
旅客 7
AB 站点 3的局部模式
4.8 分布设计
4 实例研究,飞机订票系统
4,局部逻辑模式自然分配
将现有的各种不同的数据库模式集成为全局模式,
三个问题
– 选择公用数据库模型来描述数据库的全局模式
– 把每个站点上的本地模式翻译成公用数据模型
– 把各站点上的本地数据模式集成为一公用的全局模式
5.1 自底向上方法要解决的问题
5 自底向上设计分布式数据库
自底向上方法主要问题是构造一个全局模式（超视图）,
– 把各站点上的数据库模式看成是全局模式的一个视图
– 这个问题就可看作是视图综合问题
概括分层结构支持视图综合
经典方法就是生成三个实体：一个具有共同属性
（超类型），两个具有不相交属性（子类型）
视图综合次序
– 一次把一个视图和全局模式进行综合，逐步构造起全局视图
– 通常，最好首先综合最大的或最重要的视图，然后跟着综合小的或者不重要的视图
5.2 构造全局模式设计问题
5 自底向上设计分布式数据库班机机号日期可用座位出入口座位图延期班机机号日期可用座位机型座位图班机班机 1 班机 2
机号日期可用座位座位图出入口延期机型
5.2 构造全局模式设计问题
5 自底向上设计分布式数据库
5.3 识别相似性和识别冲突
5 自底向上设计分布式数据库
识别相似性
– 模式命名相似性
– 模式结构相似性
– 不同 Site上有相似应用,使用各自 DB的数据副本,则这两 Site之间有某些相似点,
识别冲突
– 命名冲突：同物异名（ EMP,EMPLOYEE），异物同名
– 域差异
– 定标差异：计量单位不同 (天、小时、分钟、秒）
– 结构差异：同一对象有的用实体描述,有的用属性描述,
处理操作期间不一致的数据策略（ 5种,p64-65）
从 到机场登记起飞时间 到达时间符号城市权力区域安全规则座位号 检查行李班机 订票旅客机号日期可用座位进入口座位图延期种类名字 电话系统 A概念模式
5.4 自底向上综合的一个例子
5 自底向上设计分布式数据库系统 B概念模式班机 订票旅客标识符起飞起飞时间座位图可用座位种类名字 电话到达 到达时间
5.4 自底向上综合的一个例子
5 自底向上设计分布式数据库班机班机 B 班机 A
飞机符
(机号 )
日期
(1,3)
可用座位座位图出入口登记订票从 到机场到达时间到达机场起飞时间起飞机场起飞时间到达时间座位号检查行李旅客种类名字电话综合后建立的全局模式
5.4 自底向上综合的一个例子
5 自底向上设计分布式数据库数据集成数据源 1 数据源2 数据源 3
包装器 包装器 包装器协调器用户应用
XML
Ontology
View
5.4 数据集成实现方法
5 自底向上设计分布式数据库
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记录,并仍以本地应用为其设计目标,则那个分配方案较优?
站点 1 站点 2 站点 3
站点 3站点 2站点 1
A1
R1
A3
R2
A2
R3
A1
R1,R2
A3 A2
R2,R3
方案
A
方案
B
读取 更新
10
10
10
55
图 2-12 COMPANY关系数据库模式,主码用下划线标出
EMPLOY
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
Exercise 2
三个站点 A,B,C
部门 1（总部），部门 2，部门 3
在站点 B上频繁访问 EMPLOYEE,PROJECT中有关工作在部门 2的雇员和该部门管辖的项目信息
在站点 C上频繁访问 EMPLOYEE,PROJECT中有关工作在部门 3的雇员和该部门管辖的项目信息
雇员信息主要是指 EMPLOYEE表中的
FNAME,ESSN,SALARY,SUPERSSN属性
A,B,C站点上频繁访问本站点所在部门的项目工时信息
站点 A供公司总部使用，经常存取为保险目的而纪录的
DEPENDENT信息外，还定期地存取所有雇员和项目的信息
FNAME MINIT LNAME ESSN SALARY SUPERSSN DNO
Alicia J Zelaya 999887777 25000 987654321 2
Jennifer S Wallace 987654321 43000 888665555 2
Ahmad V Jabbar 987987987 25000 987654321 2
EMPD2
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
999887777 10 10.0
987987987 10 35.0
987987987 30 5.0
987654321 30 20.0
987654321 30 15.0
DEP2
_PROJECT
PNAME PNO PLOCATION DNO
Computer 10 Startlond 2
Newbenef 30 Startlond 2
图 2-13 站点的片段分配（ b）站点 B上的对应于部门 2的关系片段
FNAME MINIT LNAME SSN SALARY SUPERSSN DNO
John B Smith 123456789 30000 333445555 3
Franklin T Wong 333445555 40000 888665555 3
Ramesh K Narayan 666884444 38000 333445555 3
Joyce A English 453453453 25000 333445555 3
EMPD3
DEP3 DNAME DNO MGRSSN MGRSTARTDATE
Research 3 333445555 2003-05-22
DEP3_LOCS DNO DLOCATION
3 Bellaire
3 Sugarlnd
3 HoustonDEP3
_WORKSON
ESSN PNO HOURS
123456789 1 32.5
123456789 2 7.5
666884444 3 40.0
453453453 1 20.0
453453453 2 20.0
333445555 2 10.0
333445555 3 10.0
DEP3_PROJECT
PNAME PNO PLOCATION DNO
Product X 1 Bellaire 3
Product Y 2 ugarlnd 3
Product Z 3 Houston 3
图 2-13 站点的片段分配（ a）站点 C上的对应于部门 3的关系片段图 2-15 站点 A上的对应于部门 1（总部）的片断
EMPLOYEE
PROJECT
PNAME PNUMER PLOCATION DNUM
DEPENDENT
ESSN DEPENDENT_NAME SEX BDATE RELATIONSHIP
FNAME MINIT LNAME SSN SALARY SUPERSSN DNO
Alicia J Zelaya 999887777 25000 987654321 2
Jennifer S Wallace 987654321 43000 888665555 2
Ahmad V Jabbar 987987987 25000 987654321 2
John B Smith 123456789 30000 333445555 3
Franklin T Wong 333445555 40000 888665555 3
Ramesh K Narayan 666884444 38000 333445555 3
Joyce A English 453453453 25000 333445555 3
Exercise 3
建立百货连锁店分布式数据库系统,
1,由一个总部和多个远程连锁店组成
2,总部和各个连锁店之间有数据交换，局域网和广域网
3,总部负责产生各类汇总表，如销售汇总表
4,各站点系统相对独立
5,总部统一管理各门店商品的业种和品牌信息，各门店也经常使用这两类信息
6,供应商、合同、商品和销售信息等经营基础数据都由各门店单独管理和使用，门店之间互不相关
7,整个连锁店的职员信息由总部管理，各门店只可以查询本部门的职员信息
8,该连锁店的会员卡实行全国联网消费，会员可以经常异地消费基本关系模式（初步）
DEPARTMENT
EMPLOYEE
CUSTOMER
PRODUCT（ p#,YEZHONG,PINPAI,… ）
CONTRACT
SALES
SUPPLIER
大作业之一（实验）
题目：
飞机订票系统
集团公司管理系统（习题 2.9）
连锁店管理系统（习题 2.10）
自选（鼓励）
大作业之一（实验）
要求：
小组：自由组合,2~3一组,4人一组要我批准
时间：期末考试之前完成
提交内容：设计报告，代码，开发总结报告
设计主要内容：基本关系模式，分片情况，分布情况，系统功能设计
开发内容：能够在至少两个站点上实现应用的功能，可以使用远程访问的模式。
提交时检查运行情况。
提交任务表格
1,项目名称
2,项目组组成：组长、组员
3,项目分工情况：设计、开发、总结之一或者其中两类工作
4,每个人信息：姓名、培养单位,E-mail，组长的电话。
5,任务简单描述
6,见 Word文件：分布式数据库实验任务书
7,于 3月 28日之前填好任务书发送到
xujg_courseware@126.com
总 结
分布式数据库的创建方法（重构法 /组合法）
自顶向下的设计方法
数据分片
数据分配
DATAID-D方法（分布要求分析和分布设计阶段）
实例研究：飞机订票系统
自底向上方法
（ mycui369@126.com)
计算机应用技术 2007级研究生
1,分布式数据库系统设计概述
2,自顶向下设计分布式数据库
3.DATAID-D方法
4,实例研究：飞机订票系统
5,自底向上设计分布式数据库分布式数据库系统设计第 2章分布式数据库设计概述1
创建方法1.1
组合法
1,剖析网络功能
2,剖析原有数据库系统
3,解决数据的一致性、
完整性和可靠性
4,难度较大通常是异构或者同构异质
DDBS
用户 1 用户 2 用户 n
分布式协调管理系统
DBMS1 DBMS2 DBMSm
网络分布式数据库设计概述1
DDBS创建方法1.1
重构法
1,根据实现环境和用户需求
2,按照 DDBS的设计思想和方法
3,从总体设计做起，包括
LDBS,重新建立一个 DDBS
4,可有效解决数据一致性、完整性和可靠性问题。
通常是同构异质或同构同质
DDBS
用户 1 用户 2 用户 n
分布式数据库管理系统网络
1.2 DDBS设计内容
1 分布式数据库设计概述
DDBS设计
DDB设计应用设计全局模式设计局部数据库设计相关应用需求各个应用的原发站点各个应用在每个站点的激活频率各个应用对要求访问数据对象的访问次数、类型和统计分布分片和分布
1.3 DDBS设计目标
1 分布式数据库设计概述
DDBS
设计目标本地性或近地性存储能力和费用尽量减少通信次数和通信量,90/10准则分片和分布方案（ 本地和远程访问次数 ）择优控制数据适当冗余冗余增加了可靠性、可用性，提高了效率维护数据一 致性开销增加工作负荷分布各站点可以分担整个工作任务本地性降低
1.4 DDBS设计方法
1 分布式数据库设计概述
DDBS
设计方法自顶向下方法（重构法）
混合方法自底向上方法（组合法）
2.1 步骤和内容
2 自顶向下设计 DDB
需求分析概念设计 视图设计分布设计物理设计观察与监视系统需求全局概念模式 访问模式 外部模式定义局部概念模式物理模式用户输入视图集成用户输入反馈反馈自顶向下设计过程
假若有全局关系 R 被分片为子关系 (片段 )集合
R = {R1,R2,…,R n},则 R满足
– 完整性
x? R,? Ri?R 必有 x?Ri,i=1,2,…,n
– 可重构性存在函数 g 使得 R = g(R1,R2,…,R n)
即,R=∪ Ri (水平分片）,R=∞ Ri （垂直分片）
– 不相交性
Ri ∩ Rj =空集,i≠j,i,j=1,2,…,n( 水平分片 )
Ri ∩ Rj =主键属性,i,j=1,2,…,n( 垂直分片 )
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 QbSa Sb
2.2 数据的分片设计
2 自顶向下设计 DDB
举例
e# NM Loc Sal
E 5
7
8
Sa 1000
Sally Sb 2500
Tom Sa 500
Joe
e# NM Loc Sal e# NM Loc Sal
5
8
Sa 1000
Tom Sa 500
Joe 7 Sb 2500Sally
..
..
..
..
F
站点 Sa 站点 Sb
2.2 数据的分片设计
2 自顶向下设计 DDB
举例
基本水平分片以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。
R = { R1,R2 }
R1 =?loc=Sa(E) R2 =?loc=Sb(E)
2.2 数据的分片设计
2 自顶向下设计 DDB
基本水平分片
若 R = {R1,R2,…,R n},则
– 完整性 对于每一个元组 t?R,? Ri?R 使得 t?Ri
– 不相交性 对?t?Ri, Rj 使得 t?Rj,i? j
– 可重构性 操作是 ∪ (可以忽略,因为完整性就蕴含着 )
R = ∪ {R1,R2,…,R n}
P = {p1,p2,…,p n}是一简单谓词集合，为保证分片的正确性,P必须是：
– 完整的：同一分片中的任意两个元组被应用同样概率访问。
– 最小的：集合 P中的所有谓词与应用密切相关。
– 具有完整性和最小性不是必要条件,但是对于简化分配问题有好处
2.2 数据的分片设计
2 自顶向下设计 DDB
基本水平分片
例子
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} （完整的，不是最小的）
2.2 数据的分片设计
2 自顶向下设计 DDB
基本水平分片如何保证分片原则
,手工”检查 !
e.g.,R1 =?loc=‘Sa’ E ; R2 =? loc=‘Sb’ E
生成具有满足分段原则的限定谓词
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 或是?p k
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)
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.2 数据的分片设计
2 自顶向下设计 DDB
小项谓词选择
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
分片结果
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
2.2 数据的分片设计
2 自顶向下设计 DDB
小项选择率（ minterm selectivity） 对某一给定小项谓词用户查询可能选择到的元组数
访问频率（ Access frequency） 用户应用访问数据的频率
– 小项访问频率可以通过用户查询频率获得
2.2 数据的分片设计
2 自顶向下设计 DDB
分片数量信息
例子
E(#,NM,LOC,SAL,…)
有查询应用
Qa,select * Qb,select *
from E from E
where LOC=Sa where LOC=Sb
and … and,..
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 }
三种选择
2.2 数据的分片设计
2 自顶向下设计 DDB
Loc=Sa?
sal < 1000
Loc=Sa?
sal? 1000
Loc=Sb?
sal < 1000
Loc=Sb?
sal? 1000
R1 R3R2
Qa,Select … loc = S a,..
Qb,Select … loc = S b,..
R2 是好的 …
( R1,R3不好 )
2.2 数据的分片设计
2 自顶向下设计 DDB
图示
Loc=Sa?
sal < 1000
Loc=Sa?
sal? 1000
Loc=Sb?
sal < 1000
Loc=Sb?
sal? 1000
R1
Qa,Select … loc = S a,..
Qb,Select … loc = S b,..此处元组有较高的选择概率此处元组选择概率较低分段内元组选择概率不等因此 R1 不好,..
2.2 数据的分片设计
2 自顶向下设计 DDB
理由
Loc=Sa?
sal < 1000
Loc=Sa?
sal? 1000
Loc=Sb?
sal < 1000
Loc=Sb?
sal? 1000
R2
Qa,Select … loc = S a,..
Qb,Select … loc = S b,..元组选择概率相等因此 R2好,..
R3不好,..
理由
2.2 数据的分片设计
2 自顶向下设计 DDB
导出分片从另一个关系的属性性质或水平分片推导出来
例子
SC(S#,C#,GRADE)
S ( S#,SNAME,AGE,SEX)
要求：
将 SC划分为男生各门课成绩和女生的各门成绩
2.2 数据的分片设计
2 自顶向下设计 DDB
导出水平分片
按 S的属性导出
Define fragment SC1 as
Select SC.S#,C#,GRADE From SC,S
Where SC.S#=S.S# and SEX=‘M’
Define fragment SC2 as
Select SC.S#,C#,GRADE From SC,S
Where SC.S#=S.S# and SEX=‘F’
按 S的水平分片（ SF/SM）导出
– Define fragment SC1 as
Select * From SC Where S# in (Select SF.S from SF)
Define fragment SC2 as
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的一个 垂直群集 。
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
垂直分片 /垂直群集例子
2.2 数据的分片设计
2 自顶向下设计 DDB
E1
# NM Loc S a l
5 J o e Sa 1000
7 S a lly Sb 2500
8 F r e d Sa 1500
…
# NM Loc
5 J o e Sa
7 S a lly Sb
8 F r e d Sa
…
# S a l
5 1000
7 2500
8 1500
…
E
E2
垂直分片例子例子,E1(#,NM,LOC)
E2(#,SAL)
E(#,NM,LOC,SAL) E1(#,NM)
E2(#,LOC)
E3(#,SAL)
2.2 数据的分片设计
2 自顶向下设计 DDB
垂直分片设计
非键属性 A1,A2,…,A n
应用 Q1,Q2,….,Q m
freq(Qi) = Qi 的访问频率
2.2 数据的分片设计
2 自顶向下设计 DDB
属性的亲和关系
)A,u s e ( Q )A,u s e ( Q|k kji jkik )f r e q ( Q)A,a f f ( A
7578021A4
7975400A5
40974845A3
024810050A2
01455096A1
A5A4A3A2A1
R1[K,A1,A2,A3] R2[K,A4,A5]
2.2 数据的分片设计
2 自顶向下设计 DDB
属性和矩阵
0787521A4
97044845A3
4757900A5
482010050A2
45105096A1
A3A4A5A2A1
行列调整寻找分割点
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
分片小结混合分段的重构
R11 R12 R21 R22
水平垂直
U
2.2 数据的分片设计
2 自顶向下设计 DDB
分片小结
在满足用户需求的前提下,把设计好的数据片段分配到相应的站点上存储
例子,E(#,NM,LOC,SAL)?
R1 =?loc=Sa E ; R2 =?loc=Sb E
Qa,select … where loc=Sa...
Qb,select … where loc=Sb…
Site a Site b
R1,R2 存放在哪?
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的概念
2.3 数据的分配设计
2 自顶向下设计 DDB
分配方法分配方法非冗余分配设计方法最佳适应法其他方法冗余分配的设计方法所有得益站点法附加复制法应用需求确定非复制问题的解确定一组站点分配副本确定非复制问题的解从最有益处增加副本到附加复制无好处为止
什么是段的最好配置 /什么是最好的冗余副本数,
– 极小化查询响应时间
– 极大化吞吐量
– 极小化,代价”
–,..
约束?
– 有效的存储空间
– 有效的带宽,站点处理能力,…
– 保持 90% 的响应时间低于 X（如 0.5秒）
–,..
2.3 数据的分配设计
2 自顶向下设计 DDB
优化问题单个片段 F 站点 S1,… S m
变量 X1,…,X m
0 如果 F 不在 Sj上存储
1 如果 F 在 Sj上存储
Total cost = Read Cost + Write Cost +
Storage Cost
确定 Xj 的值,1? j? m,使总代价极小
Xj =
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型读代价
Read cost =? [ti? MIN Cij]
i,读申请源站点
ti,站点 Si上的读申请激活次数
Cij,从 Si读 Sj站点分段 F的代价
i=1
m
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型
.
.
.
3
i
ci,3
ci,1 ci,2
tiF
F F
.
1 2
j
写代价
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
m m
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型
.,
.,
i
F
F F
Updates
ui
存储代价
Store Cost =? Xi di
Xi,0 if F not stored at Si
1 if F stored at Si
di,站点 Si 存储分段 F 的代价
i=1
m
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型目标函数
min? [ti?MIN Cij +? Xj? ui?C’ij ]
+? Xi? di
ji=1 j=1
i=1
m m
m
2.3 数据的分配设计
2 自顶向下设计 DDB
分配的简化模型
即使最简单的公式也是 NP-完全问题
通常,使用方法
– 尽可能将片段分配在被局部访问位置
,最佳适应” 方法（非冗余分配）
Bij =?k Fkj? Nk
,所有得益站点” 方法（冗余分配）
Bij =?k Fkj? Rki - ck?j’?jFkj’? Uki
i 片段下标 j 站点下标
k 应用下标 Fkj 应用 k 在站点 j上激活的频率
Rki 应用 k被激活一次,对片段 i读的次数
Uki 应用 k被激活一次,对片段 i写的次数
Nki 应用 k被激活一次,对片段 i读写的总次数
2.3 数据的分配设计
2 自顶向下设计 DDB
分配方法
最佳适应法
– 将片断 Ri分配到访问 Ri次数最多的那个站点上
– Bij=?kFkj*Nki
所有得益站点法
– 将片断 Ri的副本分配到 所有得益站点 j上
– Bij=?kFkj*Rki -c*?k?j’≠j Fkj’*Uki
– 如 Bij ＞ 0，则站点 j是得益站点，放置 Ri的一个副本
附加复制法
– Di表示片断 Ri的冗余度（副本个数）,Fi表示 Ri在所有站点都复制的得益
–
2.3 数据的分配设计
2 自顶向下设计 DDB
水平分片情况
iDi FD i )21()( )1(?
)(' ' ik jj kikjk kikjij DUFcRFB
假设关系 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
垂直分片情况
2.3 数据的分配设计
2 自顶向下设计 DDB
垂直分片情况
r
s
其他站点
tRt
R
Rs
网络
A1
A2
As
At
A3
分布式数据库设计阶段
– 需求分析
– 概念设计
– 分布要求设计
– 全局逻辑设计
– 分布设计
– 局部逻辑设计
– 局部物理设计
3.1 与集中式数据库的异同
3 DATAID-D方法收集分布信息
1,水平分片谓词
2,每一应用在各站点激活频率
3,概念设计之后进行收集分布信息
1,分布要求和全局逻辑模式作为输入
2,形式为全局数据库模式和逻辑访问表
3,输出为分片模式和分配模式
4,全局逻辑设计之后进行说明：
1.设计数据字典；
2.全局数据模式；
3.全局操作模式；
4.简化全局模式；
5.逻辑访问表；
6.各站点逻辑模式；
7.各站点访问表；
8.局部逻辑模式
（关系或 Codasyl）；
9.局部物理模式
（关系或 Codasyl）
全局逻辑设计分布设计局部逻辑设计逻辑设计需求分析概念设计分布要求分析局部物理设计
1
8
76
54
32
9
要求频率表 划分表极化表
3.2 设计步骤
3 DATAID-D方法
分布要求分析阶段
– 频率表：各站点上每一应用激活次数（假设所有应用在所有站点上都能执行）
– 划分表：可用于模式中各实体的潜在水平分片规则
– 极化表：指明由一个站点发出的一给定应用访问一给定片段的频率（定量分析方法）
分布要求分析用户分布要求全局数据概念模型全局数据操作模式应用频率表实体划分表应用极化表
3.3 分布要求分析阶段
3 DATAID-D方法
分布设计阶段
– 分片设计
– 非冗余分配
– 冗余分配
– 局部模式的重新构造分布设计全局数据模式逻辑访问表分布要求站点逻辑模式站点逻辑访问表
3.4 分布设计阶段
3 DATAID-D方法
三个站点
– 站点 1：丹佛机场（ CO）
– 站点 1：纽约机场（ NY）
– 站点 1：亚特兰大机场（ GA）
数据库存储内容
– 机场规程
– 班机调度
– 班机可用情况
– 旅客订票情况
三个应用
– 订票应用
– 登记应用
– 起飞应用
4.1 实例研究概述
4 实例研究：飞机订票系统
4.2 数据库的全局数据模式
4 实例研究：飞机订票系统班机 订票从 到机场登记旅客到达时间机号日期可用座位起飞时间符号城市进入口座位图延期区域安全规则种类座位号 检查行李名字 电话权力
4.3 订票应用全局操作模式
4 实例研究,飞机订票系统
1,实体左下角和右下角的数字表示：示例总数和应用选择的平均示例数
2,访问数据库中的 ① 起飞与到达机场,② 起飞与到达时间和 ③ 班机日期，以 k表示这些关键词
3,确定班机后，建立旅客的一个新的示例及联系“订票”的一个示例，把用户的信息（名字、电话写入数据库
4,O表示输出,w表示写入种类 [w]
电话 [w]
240
机场
320000
班机日期 [k]
起飞时间 [k]
符号 [k]
从可用座位 [o、
w]
到到达时间 [k]
名字 [w]
1100000
旅客订票
4.4 登记应用全局操作模式
4 实例研究,飞机订票系统
1100000
旅客
120000
班机机号 [k]
日期 [k]
座位图 [o,w] 座位号 [w] 检查行李 [w]
订票登记种类 [o] 名字 [k]
1,根据数据库中的 ①旅客名字，②班机号，③ 班机日期，查明有关旅客和班机的示例，显示“种类”信息。
2,根据“种类”信息和座位图，将一个座位号分配给旅客，并写入座位图和座位号属性，以及旅客的检查行李号
4.5 起飞应用全局操作模式
4 实例研究,飞机订票系统
140
机场
3020000
班机
3040
机场日期
[k]
符号 [k]
起飞时间 [k,
o]
机号 [o]
从到出入口 [o]延期 [o]
城市 [o]
符号 [o]
到达时间 [k,
o]
1,产生即将离开机场的 30架班机的信息显示在 TV监视器上 。
2,根据数据库中的①机场符号，②当前日期，③起飞时间,④ 到达时间，查明
①班机号,②起飞时间,③出入口,④ 延期,⑤ 目的地机场符号,⑥ 目的地城市，显示出来。
4.6 实体逻辑访问表
4 实例研究,飞机订票系统属性 操作
a（ 订票） b（登记） c（起飞）
机号 k o
日期 k k k
座位图 o/w
进入口 o
延期 o
可用座位 o/w
实体访问表：班机
4.6 实体逻辑访问表
4 实例研究,飞机订票系统属性 操作
a（ 订票） b（登记） c（起飞）
符号 k k/o
城市 o
权力区域安全规则实体访问表：机场
4.6 实体逻辑访问表
4 实例研究,飞机订票系统属性 操作
a（ 订票） b（登记） c（起飞）
名字 w k
电话 w
实体访问表：旅客
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
检查行李 w
联系访问表：登记
4.7 分布要求分析
4 实例研究,飞机订票系统站点 1：丹佛（ CO）
站点 2：纽约（ NY）
站点 3：亚特兰大（ GA）
应用 a：订票应用 b：登记应用 c：起飞
4.7 分布要求分析
4 实例研究,飞机订票系统
1,将机场的区域属性选作为机场实体的划分准则
2,将旅客电话号码前三位（区域码）作为旅客实体的划分属性
3,谓词选择性表示按照该准则划分各类元组所占的百分数
4.7 分布要求分析
4 实例研究,飞机订票系统
1,两种方法划分班机实体，应用不同的联系“从”或“到”和机场划分区域于同一基本划分，结果不同。
2,根据第一订票地点和班机起飞区域做导出划分
3,机场 —— 〉 班机 —— 〉 乘客
4.7 分布要求分析
4 实例研究,飞机订票系统
4.7 分布要求分析
4 实例研究,飞机订票系统极化表 a b c
1 2 3 1 2 3 1 2 3
按区域划分机场
P1 80 × 100
P2 75 × 100
P3 80 × 100
按出发机场划分航班
P1 70 100 80
P2 75 100 80
P3 70 100 80
..,… … … … … … … …
4.8 分布设计
4 实例研究,飞机订票系统分四步：
1,对每一实体选择分片原则
2,确定非冗余分配
3,在非冗余分配上引入冗余
4,在每一站点上重新构造局部模式
机场实体,基于区域的水平分段机场 1,机场 2,机场 3
班机实体：基于起飞机场的导出水平分段班机 1，班机 2,班机 3
旅客实体,基于旅客预定的所有班机起飞的导出水平分段旅客 1，旅客 2，旅客 3，旅客 4，旅客 5，旅客 6，旅客 7，
4.8 分布设计
4 实例研究,飞机订票系统
1,分片设计根据分片原则
站点 1：机场 1,班机 1,旅客 1
站点 2：机场 2,班机 2,旅客 2
站点 3：机场 3,班机 3,旅客 3
根据极化表和频率表
站点 2：旅客 4，旅客 5，旅客 6，旅客 7
站点 3：旅客 5
4.8 分布设计
4 实例研究,飞机订票系统
2,确定非冗余分配冗余超出了同一实体所有片断的效益
机场实体：不进行冗余分配
班机实体：不进行冗余分配有限冗余
旅客实体：
– 预定离开两个区域的乘客：，旅客 4，旅客 5，旅客 6，
放到两个站点上
– 预定离开三个区域的乘客：旅客 7，放到三个站点上
4.8 分布设计
4 实例研究,飞机订票系统
3,冗余分配班机 1
从 到订票登记到机场 1
旅客 1u
旅客 4u
旅客 5u
旅客 7
BC 站点 1的局部模式
4.8 分布设计
4 实例研究,飞机订票系统
4,局部逻辑模式自然分配班机 2
从 到订票登记到机场 2
旅客 2u
旅客 4u
旅客 6u
旅客 7
AC
站点 2的局部模式
4.8 分布设计
4 实例研究,飞机订票系统
4,局部逻辑模式自然分配班机 3
从 到订票登记到机场 3
旅客 3u
旅客 5u
旅客 6u
旅客 7
AB 站点 3的局部模式
4.8 分布设计
4 实例研究,飞机订票系统
4,局部逻辑模式自然分配
将现有的各种不同的数据库模式集成为全局模式,
三个问题
– 选择公用数据库模型来描述数据库的全局模式
– 把每个站点上的本地模式翻译成公用数据模型
– 把各站点上的本地数据模式集成为一公用的全局模式
5.1 自底向上方法要解决的问题
5 自底向上设计分布式数据库
自底向上方法主要问题是构造一个全局模式（超视图）,
– 把各站点上的数据库模式看成是全局模式的一个视图
– 这个问题就可看作是视图综合问题
概括分层结构支持视图综合
经典方法就是生成三个实体：一个具有共同属性
（超类型），两个具有不相交属性（子类型）
视图综合次序
– 一次把一个视图和全局模式进行综合，逐步构造起全局视图
– 通常，最好首先综合最大的或最重要的视图，然后跟着综合小的或者不重要的视图
5.2 构造全局模式设计问题
5 自底向上设计分布式数据库班机机号日期可用座位出入口座位图延期班机机号日期可用座位机型座位图班机班机 1 班机 2
机号日期可用座位座位图出入口延期机型
5.2 构造全局模式设计问题
5 自底向上设计分布式数据库
5.3 识别相似性和识别冲突
5 自底向上设计分布式数据库
识别相似性
– 模式命名相似性
– 模式结构相似性
– 不同 Site上有相似应用,使用各自 DB的数据副本,则这两 Site之间有某些相似点,
识别冲突
– 命名冲突：同物异名（ EMP,EMPLOYEE），异物同名
– 域差异
– 定标差异：计量单位不同 (天、小时、分钟、秒）
– 结构差异：同一对象有的用实体描述,有的用属性描述,
处理操作期间不一致的数据策略（ 5种,p64-65）
从 到机场登记起飞时间 到达时间符号城市权力区域安全规则座位号 检查行李班机 订票旅客机号日期可用座位进入口座位图延期种类名字 电话系统 A概念模式
5.4 自底向上综合的一个例子
5 自底向上设计分布式数据库系统 B概念模式班机 订票旅客标识符起飞起飞时间座位图可用座位种类名字 电话到达 到达时间
5.4 自底向上综合的一个例子
5 自底向上设计分布式数据库班机班机 B 班机 A
飞机符
(机号 )
日期
(1,3)
可用座位座位图出入口登记订票从 到机场到达时间到达机场起飞时间起飞机场起飞时间到达时间座位号检查行李旅客种类名字电话综合后建立的全局模式
5.4 自底向上综合的一个例子
5 自底向上设计分布式数据库数据集成数据源 1 数据源2 数据源 3
包装器 包装器 包装器协调器用户应用
XML
Ontology
View
5.4 数据集成实现方法
5 自底向上设计分布式数据库
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记录,并仍以本地应用为其设计目标,则那个分配方案较优?
站点 1 站点 2 站点 3
站点 3站点 2站点 1
A1
R1
A3
R2
A2
R3
A1
R1,R2
A3 A2
R2,R3
方案
A
方案
B
读取 更新
10
10
10
55
图 2-12 COMPANY关系数据库模式,主码用下划线标出
EMPLOY
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
Exercise 2
三个站点 A,B,C
部门 1（总部），部门 2，部门 3
在站点 B上频繁访问 EMPLOYEE,PROJECT中有关工作在部门 2的雇员和该部门管辖的项目信息
在站点 C上频繁访问 EMPLOYEE,PROJECT中有关工作在部门 3的雇员和该部门管辖的项目信息
雇员信息主要是指 EMPLOYEE表中的
FNAME,ESSN,SALARY,SUPERSSN属性
A,B,C站点上频繁访问本站点所在部门的项目工时信息
站点 A供公司总部使用，经常存取为保险目的而纪录的
DEPENDENT信息外，还定期地存取所有雇员和项目的信息
FNAME MINIT LNAME ESSN SALARY SUPERSSN DNO
Alicia J Zelaya 999887777 25000 987654321 2
Jennifer S Wallace 987654321 43000 888665555 2
Ahmad V Jabbar 987987987 25000 987654321 2
EMPD2
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
999887777 10 10.0
987987987 10 35.0
987987987 30 5.0
987654321 30 20.0
987654321 30 15.0
DEP2
_PROJECT
PNAME PNO PLOCATION DNO
Computer 10 Startlond 2
Newbenef 30 Startlond 2
图 2-13 站点的片段分配（ b）站点 B上的对应于部门 2的关系片段
FNAME MINIT LNAME SSN SALARY SUPERSSN DNO
John B Smith 123456789 30000 333445555 3
Franklin T Wong 333445555 40000 888665555 3
Ramesh K Narayan 666884444 38000 333445555 3
Joyce A English 453453453 25000 333445555 3
EMPD3
DEP3 DNAME DNO MGRSSN MGRSTARTDATE
Research 3 333445555 2003-05-22
DEP3_LOCS DNO DLOCATION
3 Bellaire
3 Sugarlnd
3 HoustonDEP3
_WORKSON
ESSN PNO HOURS
123456789 1 32.5
123456789 2 7.5
666884444 3 40.0
453453453 1 20.0
453453453 2 20.0
333445555 2 10.0
333445555 3 10.0
DEP3_PROJECT
PNAME PNO PLOCATION DNO
Product X 1 Bellaire 3
Product Y 2 ugarlnd 3
Product Z 3 Houston 3
图 2-13 站点的片段分配（ a）站点 C上的对应于部门 3的关系片段图 2-15 站点 A上的对应于部门 1（总部）的片断
EMPLOYEE
PROJECT
PNAME PNUMER PLOCATION DNUM
DEPENDENT
ESSN DEPENDENT_NAME SEX BDATE RELATIONSHIP
FNAME MINIT LNAME SSN SALARY SUPERSSN DNO
Alicia J Zelaya 999887777 25000 987654321 2
Jennifer S Wallace 987654321 43000 888665555 2
Ahmad V Jabbar 987987987 25000 987654321 2
John B Smith 123456789 30000 333445555 3
Franklin T Wong 333445555 40000 888665555 3
Ramesh K Narayan 666884444 38000 333445555 3
Joyce A English 453453453 25000 333445555 3
Exercise 3
建立百货连锁店分布式数据库系统,
1,由一个总部和多个远程连锁店组成
2,总部和各个连锁店之间有数据交换，局域网和广域网
3,总部负责产生各类汇总表，如销售汇总表
4,各站点系统相对独立
5,总部统一管理各门店商品的业种和品牌信息，各门店也经常使用这两类信息
6,供应商、合同、商品和销售信息等经营基础数据都由各门店单独管理和使用，门店之间互不相关
7,整个连锁店的职员信息由总部管理，各门店只可以查询本部门的职员信息
8,该连锁店的会员卡实行全国联网消费，会员可以经常异地消费基本关系模式（初步）
DEPARTMENT
EMPLOYEE
CUSTOMER
PRODUCT（ p#,YEZHONG,PINPAI,… ）
CONTRACT
SALES
SUPPLIER
大作业之一（实验）
题目：
飞机订票系统
集团公司管理系统（习题 2.9）
连锁店管理系统（习题 2.10）
自选（鼓励）
大作业之一（实验）
要求：
小组：自由组合,2~3一组,4人一组要我批准
时间：期末考试之前完成
提交内容：设计报告，代码，开发总结报告
设计主要内容：基本关系模式，分片情况，分布情况，系统功能设计
开发内容：能够在至少两个站点上实现应用的功能，可以使用远程访问的模式。
提交时检查运行情况。
提交任务表格
1,项目名称
2,项目组组成：组长、组员
3,项目分工情况：设计、开发、总结之一或者其中两类工作
4,每个人信息：姓名、培养单位,E-mail，组长的电话。
5,任务简单描述
6,见 Word文件：分布式数据库实验任务书
7,于 3月 28日之前填好任务书发送到
xujg_courseware@126.com
总 结
分布式数据库的创建方法（重构法 /组合法）
自顶向下的设计方法
数据分片
数据分配
DATAID-D方法（分布要求分析和分布设计阶段）
实例研究：飞机订票系统
自底向上方法
