– 完整的：同一分片中的任意两个元组被应用同样概率 访问。
– 最小的：集合P中的所有谓词与应用密切相关。(不同分 片中的元组被访问的概率是不同的)
– 具有完整性和最小性不是必要条件, 但是对于简化分配 问题有好处
2 自顶向下设计DDB
2.2 数据的分片设计
基本水平分片
• 例子
EMP ( E#, NAME, DEPT, JOB, SAL, TEL, …) DEPT={1,2} JOB={‘P’, ‘-P’} 假定，应用经常查询的内容是属于部门1且是程序员 的职员。
e.g., R1 = loc=‘Sa’ E ; R2 = loc=‘Sb’ E
• 生成具有满足分段原则的限定谓词
2 自顶向下设计DDB 2.2 数据的分片设计
谓词生成举例
• 设有关系 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
2 自顶向下设计DDB 2.2 数据的分片设计
局部概念模式
物理设计
物理模式
观察与监视
自顶向下设计过程
视图设计
外部模式定义
用户 输入
反馈
2 自顶向下设计DDB
2.2 数据的分片设计
分片原则
• 假若有全局关系R 被分片为子关系(片段)集合 R = {R1, R2, …, Rn}, 则 R满足
– 完整性 ?x R, RiR 必有 xRi ，i=1,2,…,n
第2章 分布式数据库系统设计
1. 分布式数据库系统设计概述 2. 自顶向下设计分布式数据库 3. DATAID-D方法 4. 实例研究：飞机订票系统 5. 自底向上设计分布式数据库
1 分布式数据库设计概述
1.1 创建方法
组合法
1. 剖析网络 功能
2. 剖析原有 数据库系 统
3. 解决数据 的一致性、 完整性和 可靠性
4. 难度较大
通常是异 构或者同 构异质 DDBS
用户1 DBMS1
用户2 分布式协调管理系统 DBMS2
网络
用户n DBMSm
1 分布式数据库设计概述
1.1 DDBS创建方法
重构法
1. 根据实现环境 和用户需求
2. 按照DDBS的 设计思想和方 法
3. 从总体设计做 起，包括 LDBS,重新建 立一个DDBS
– 可重构性 ? 存在函数 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(垂直分片)
2 自顶向下设计DDB 2.2 数据的分片设计
• 则可能有的水平分段限定
– P={ DEPT=1} （不是完整的） – P={DEPT=1, JOB=‘P’} （是完整的、最小的） – P={DEPT=1, JOB=‘P’, SAL>500} （完整的，不是
最小的）
2 自顶向下设计DDB 2.2 数据的分片设计
基本水平分片
如何保证分片原则
• “手工”检查!
基本水平分片
• 基本水平分片
以关系自身的属性性质为基础，执行“选 择”操作，将关系分割成若干个不相交的 片段。
R = { R1, R2 }
R1 = loc=Sa(E)
R2 = loc=Sb(E)
2 自顶向下设计DDB
2.2 数据的分片设计
基本水平分片
• 若 R = {R1, R2, …, Rn}, 则
各站点可以分担整个工作任务
工作负荷分布
本地性降低
存储能力和费用
1 分布式数据库设计概述 1.4 DDBS设计方法
自顶向下方法（重构法）
DDBS 设计方法
自底向上方法（组合法）
混合方法
2 自顶向下设计DDB 2.1 步骤和内容
概念设计
全局概念模式
反馈
需求分析
系统需求
用户输入 视图集成
访问模式
分布设计
4. 可有效解决数 据一致性、完 整性和可靠性 问题。
通常是同构异 质或同构同质 DDBS
用户1
用户2 分布式数据库管理系统
网络
用户n
1 分布式数据库设计概述 1.2 DDBS设计内容
DDB设计
全局模式设计 局部数据库设计
分片和分布
各个应用的原发站点
DDBS设计
相关应用需求
各个应用在每个站点的激活频率
举例
e# NM Loc Sal E 5 Joe Sa 1000
7 Sally Sb 2500 8 Tom Sa 500
..
.. ..
e# NM Loc Sal
5 Joe Sa 1000 8 Tom Sa 500
站点Sa
..
F
e# NM Loc Sal
7 Sally Sb 2500
站点 Sb
2 自顶向下设计DDB 2.2 数据的分片设计
举例
职工关系 E (e#, name, loc, sal,…)
查询: select *
from E
from E
where loc=Sa
where loc=Sb
and…
and ...
两个站点 : Sa, Sb
Qa Sa
Sb Qb
2 自顶向下设计DDB 2.2 数据的分片设计
小项谓词选择
(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)
– 完整性 对于每一个元组 tR, RiR 使得 tRi – 不相交性 对tRi, Rj 使得 tRj, i j
– 可重构性 操作是∪ (可以忽略, 因为完整性就蕴含着)
R = ∪{R1, R2, …, Rn} • P = {p1, p2, …, pn}是一简单谓词集合，为保证分片
的正确性，P必须是：
应用设计
各个应用对要求访问数据对象的 访问次数、类型和统计分布
1 分布式数据库设计概述 1.3 DDBS设计目标
尽量减少通信次数和通信量，90/10准则
DDBS 设计目标
本地性或近地性
分片和分布方案（本地和远程访问次数）择优 冗余增加了可靠性、可用性，提高了效率
控制数据适当冗余
维护数据一致性开销增加