数据库系统-学习记录5
ch5.代数与逻辑查询语句
包（Bag）的关系运算
包与集合的区别：包允许重复，比较高效（省掉了去重的过程）
并集、交集与差集
与集合的运算基本一致。值得注意的是，进行差集计算的时候，对于重复元组，包R和S有相同的有n个时，R-S运算时，就从R中减去n个，剩余的保留下来
投影
与集合的投影的不同点在于：包的投影不消去重复元组
选择
与集合的操作一致，最后同样保留重复元组
笛卡尔积、自然连接
与集合的操作一致
扩展的关系代数运算
去除重复元组
符号表示：
δ
(
R
)
\delta(R)
δ(R)
使得包R内不存在两个相同的元组
聚集
SUM：求和
AVG：求平均
MIN/MAX：求最小/最大值
COUNT：求总数
分组运算
在有些时候，会有分别求各类元素的聚集函数的需求（例如求出编号为x的学生的考试平均成绩）。因此，在此处，就引出了分组的概念：
符号表示： γ a t t r i b u t e s o r A g g r e g a t i o n O p ( a t t r i b u t e ) ( R ) \gamma_{attributes\ or\ AggregationOp(attribute)}(R) γattributes or AggregationOp(attribute)(R)
两种参数分别为：
1、分组属性
2、聚集函数操作
此运算能够先对指定的属性进行分组，将相同的属性分为一组，随后再对各个组单独进行聚集函数运算
去除重复元组的操作是分组运算的特例：
δ
(
R
)
=
γ
A
1
,
A
2
,
…
,
A
n
(
R
)
\delta (R)=\gamma_{A_1,\ A_2,\ \dots\ ,\ A_n}(R)
δ(R)=γA1, A2, … , An(R)
其中，关系R：
R
(
A
1
,
A
2
,
…
,
A
n
)
R(A_1,\ A_2,\ \dots\ ,\ A_n)
R(A1, A2, … , An)
扩展投影
类似于集合上的扩展投影运算。
使用
→
\rightarrow
→表示重命名，例如：
π
x
→
y
(
R
)
\pi_{x\rightarrow y}(R)
πx→y(R)表示将包R中的x属性重命名为y
排序
符号表示：
τ
L
(
R
)
\tau_L(R)
τL(R)
按列表L中的顺序，逐属性进行排序
外连接
符号表示：
⋈
∘
\mathop\Join\limits^\circ
⋈∘
类似于集合的外连接，连接后的空值用
⊥
\perp
⊥表示
左外连接：
⋈
∘
L
\mathop\Join\limits^\circ\ _L
⋈∘ L
右外连接：
⋈
∘
R
\mathop\Join\limits^\circ\ _R
⋈∘ R
θ
\theta
θ外连接：
⋈
∘
C
o
n
d
i
t
i
o
n
\mathop\Join\limits^\circ\ _{Condition}
⋈∘ Condition
查询树
类似于编译原理中的语法树，数据库系统中的关系操作，也可以用树的形式表示。例如： σ C ( ( S ⋈ S C ) ⋈ C ) \sigma_C((S\Join SC)\Join C) σC((S⋈SC)⋈C)这样的操作，可以表示为如图1所示：
关系的逻辑
谓词和原子（关系原子）
定义：关系在Datatog中由谓词（predicate）表示。每个谓词拥有固定数目的参数，一个谓词和它的参数一起被称为原子（atom）。谓词是一个返回布尔值的函数名
如果R是一个包含n个固定顺序的属性的关系，那么也可以用作为对应这个关系的谓词名。如果
(
a
1
,
a
2
,
…
,
a
n
)
(a_1,\ a_2,\ \dots\ ,a_n)
(a1, a2, … ,an)是满足R的元组，那么原子
R
(
a
1
,
a
2
,
…
,
a
n
)
R(a_1,\ a_2,\ \dots\ ,a_n)
R(a1, a2, … ,an)的值为TRUE，否则原子的值为FALSE
例如：关系R(A, B)含有两个元组(1, 2)、(3, 4)，则R(1, 2)和R(3, 4)的值为TRUE，其他的R(x, y)值为FALSE
算术原子
对两个算术表达式作比较
Datalog规则与查询
定义：
与经典关系代数类似的操作在Datalog中称作规则（rule)，它包括：
1、一个称为头部（head）的关系原子
2、符号
←
\leftarrow
←，经常读作“if”
3、主体（body）部分，由一个或多个称为子目标（subgoal）的原子组成。原子可以是关系原子或算术原子。子目标之间由AND连接，任何子目标之前都可随意添加逻辑算子NOT
例如：LongMovie(t, y)
←
\leftarrow
←Movies(t, y, l, g, s, p) AND l
≥
\ge
≥ 100
这个规则的头部是LongMovie(t, y)，主体包括Movies(t, y, l, g, s, p)和l
≥
\ge
≥ 100这两个原子。该规则表示，对于给出的元组(t, y)，如果这个元组属于Movies的前两个分量，并且其对应的l大于或等于100，则LongMovie(t, y)的值为TRUE
扩展谓词和内涵谓词
扩展谓词：这种谓词的关系存放在数据库中
内涵谓词：这种谓词的关系由一个或多个Datalog规则计算而来
关系代数与Datalog
布尔操作
包含并、交、差，可以简单地用Datalog表达
并：
A
n
s
w
e
r
(
a
1
,
a
2
,
…
,
a
n
)
Answer(a_1,\ a_2,\ \dots\ ,\ a_n)
Answer(a1, a2, … , an)
交：
A
n
s
w
e
r
(
a
1
,
a
2
,
…
,
a
n
)
←
R
(
a
1
,
a
2
,
…
,
a
n
)
A
N
D
S
(
a
1
,
a
2
,
…
,
a
n
)
Answer(a_1,\ a_2,\ \dots\ ,\ a_n)\leftarrow R(a_1,\ a_2,\ \dots\ ,\ a_n)\ \mathrm{AND}\ S(a_1,\ a_2,\ \dots\ ,\ a_n)
Answer(a1, a2, … , an)←R(a1, a2, … , an) AND S(a1, a2, … , an)
差：
A
n
s
w
e
r
(
a
1
,
a
2
,
…
,
a
n
)
←
R
(
a
1
,
a
2
,
…
,
a
n
)
A
N
D
N
O
T
S
(
a
1
,
a
2
,
…
,
a
n
)
Answer(a_1,\ a_2,\ \dots\ ,\ a_n)\leftarrow R(a_1,\ a_2,\ \dots\ ,\ a_n)\ \mathrm{AND}\ \mathrm{NOT}\ S(a_1,\ a_2,\ \dots\ ,\ a_n)
Answer(a1, a2, … , an)←R(a1, a2, … , an) AND NOT S(a1, a2, … , an)
投影
只使用单个子目标，例如：P(t, y, l) ← \leftarrow ←Movies(t, y, l, g, s, p)
选择
当选择条件是对一个或多个算术比较来作AND操作时，是一个比较简单的情况。对于更为复杂的选择条件，可以由逻辑算子AND、OR和NOT按照任意顺序组成
积
R × \times ×S：P(a, b, c, x, y, z) ← \leftarrow ←R(a, b, c) AND S(x, y, z)
连接
R ⋈ \Join ⋈S：J(a, b, c, d) ← \leftarrow ←R(a, b) AND S(b, c, d)