R
(
A
1
,
A
2
,
.
.
.
,
A
n
)
R(A_1,A_2,...,A_n)
R(A1,A2,...,An)表示关系的名称是
R
R
R,其属性是
A
1
,
A
2
,
.
.
.
,
A
n
A_1,A_2,...,A_n
A1,A2,...,An。
例如link关系中有两个属性From和To，一个元组
(
u
r
l
1
,
u
r
l
2
)
(url1,url2)
(url1,url2)表示从链接1指向链接2。
选择(selection) 筛选关系R中符合条件C的元组，记为： σ C ( R ) sigma_C(R) σC(R)。投影(projection) 得到每个元组中仅包含属性S的原色，记为： π S ( R ) pi_S(R) πS(R) 。并(union)交(intersection)和差(difference)自然连接(natural join) 给定两个关系，如果两个元组的公共属性的属性值一致，则两个元组取并生成一个新的元组。记为 R ⋈ S RJoin S R⋈S分组和聚合(grouping and aggregation) 给定关系R，分组是按照属性集合G对元组进行分割。常见的聚合运算有SUM,COUNT,AVG,MIN,MAX。记为 γ X ( R ) gamma_X(R) γX(R)，其中 X X X是一个元素表，每个元素可以是一个分组属性，也可以是表达式 θ ( A ) theta(A) θ(A)，其中 θ theta θ是聚合运算， A A A是一个非分组属性。 例子
- 使用link关系寻找Web中长为2的路径。
L1和L2分别是link的副本，计算 L 1 ⋈ L 2 L1Join L2 L1⋈L2,产生一个连接后的关系，(U1,U2,U3)，只取首尾的属性，写作 π U 1 , U 3 ( L 1 ⋈ L 2 ) pi_{U1,U3}(L1Join L2) πU1,U3(L1⋈L2)计算社交网络中的朋友个数。关系：Friends(User,Friend)
先按照User字段进行分组，每一个组内统计Friend字段的数量。
具体的运算为 γ U s e r , C O U N T ( F r i e n d ) ( F r i e n d s ) gamma_{User,COUNT(Friend)}(Friends) γUser,COUNT(Friend)(Friends)。
Map函数： 对R中的每个元组t，检测它是否满足C。如果满足，则产生一个键-值对(t,t)。
Reduce函数： 作用类似恒等式，仅仅传递结果至输出部分。
Map函数： 对R中的每个元组t，剔除不在S中的字段得到t‘，输出键-值对(t’,t’)。
Reduce函数： (t’.t’)有可能重复，Reduce函数将(t’,[t’,t’,…,t’])转换成(t’,t’)。
考虑R和S的并，将R或S中的文件块分配给Map任务。
Map函数： 将每个输入元组变成键-值对(t,t)。
Reduce函数： 剔除冗余，保证每个键只有一个值。
只输出有两个值对键
Map函数： 将每个输入元组变成键-值对(t,t)。
Reduce函数： 如果键t的值表为[t,t],则输出(t,t)。
R-S，只有出现在R中但不出现在S中的元组，计算时需要告知每个元组来自R还是S。
Map函数： 对R中的元组t，产生键-值对(t,R)，同理产生(t,S)。
Reduce函数： 对每个键t，值表是[R]，则输出(t,t)。
Map函数： 对于R中的每个元组(a,b)，生成键-值对(b,(R,a))，对S中的每个元组(b,c),生成键-值对(b,(S,c))。
Reduce函数： 每个键值b会与一系列对相关联，输出三元组(a,b,c)。
假定对关系
R
(
A
,
B
,
C
)
R(A,B,C)
R(A,B,C)施加运算
γ
A
,
θ
(
B
)
(
R
)
gamma_{A,theta(B)}(R)
γA,θ(B)(R)，Map函数主要负责分组运算，而Reduce函数则负责聚合运算。
Map函数： 对每个元组(A,B,C)生成键-值对(a,b)。
Reduce函数： 每个键a代表一个分组，关联的键值[b1,b2,…,bn]施加
θ
theta
θ运算，输出结果
(
a
,
x
)
(a,x)
(a,x)对，x是应用运算后对结果。
