数据库系统概论

Size: px

Start display at page:

Download "数据库系统概论"

奎赵
7 years ago
Views:

1 第 2 章关系数据库孟小峰 xfmeng@ruc.edu.cn 信息学院 2014/3/4

2 上节课关系完整性实体完整性 / 主码完整性参照完整性 / 外码完整性函数依赖用户定义完整性关系代数基本运算 : 选择, 投影, 笛卡尔积, 并, 差导出运算 : 交, 连接, 除

3 Additional Relational Algebra Operators The new operators are all derivable from the six operators we have introduced previously 交 set intersection Format: R1 R2 Semantics: Return all tuples that belong to both R1 and R2. Formally: R1 R2 = { t t R1 and t R2 } Derivation from existing operators: R1 R2 = R1 - (R1 - R2) = R2 - (R2 - R1)

4 交 set intersection (2) Example: R1 R2 R1 - R2 A B C A B C A B C a1 b1 c1 a0 b0 c0 a3 b3 c3 a2 b2 c2 a1 b1 c1 A B C R1 R2 a3 b3 c3 a2 b2 c2 a1 b1 c1 a4 b4 c4 a2 b2 c2 R1 R2 = R1 - (R1 - R2)

5 join Format: R1 连接 Join (1) join-condition R2 Semantics: Return all tuples in R1 R2 which satisfy the join condition. Derivation from existing operators: R1 join-condition R2 = σ join-condition (R1 R2) Format of join condition: R1.A op R2.B R1.A1 op R2.B1 and R1.A2 op R2.B2...

6 连接 Join (2) Example: Find the names of all employees and their department locations. Employees: SSN Name Age Dept-Name John 34 Sales Mary 42 Service Bill 39 null Departments: Name Location Manager Sales Binghamton Bill Inventory Endicott Charles Service Vestal Maria

7 连接 Join (3) π Employees.Name, Location ( Employees Dept-Name = Departments. Name Departments) Result Name Location John Binghamton Mary Vestal

8 连接 Join (4) Example: Find the names of all employees who earn more than his/her manager. Employees: SSN Name Salary Manager-SSN John 34k Bill 40k null Mary 38k null Mike 41k π Employees.Name (Employees Employees.Manager-SSN = EMP2.SSN and Employees.Salary > EMP2.Salary ρ EMP2 (Employees))

9 等值连接 Equijoin Definition: A join is called an equijoin if only equality operator is used in all join conditions. R1 R2 R1 R1.B = R2.B R2 A B B C A R1.B R2.B C a b b c a b b c d b c d d b b c b c a d b c c d Most joins in practice are equijoins.

10 自然连接 Natural Join (1) Definition: A join between R1 and R2 is a natural join if There is an equality comparison between every pair of identically named attributes from the two relations. Among each pair of identically named attributes from the two relations, only one remains in the result. Natural join is denoted by with no join conditions explicitly specified.

11 自然连接 Natural Join (2) Example: R1(A, B, C) R2(A, C, D) has attributes (A, B, C, D) in the result. Questions: (1) How to express natural join in terms of equijoin and other relational operator? R1 R2 = π R1.A, B, R2.C, D(R1 R1.A = R2.A and R1.C = R2.C R2)

12 自然连接 Natural Join (3) (2) If there are no common attributes between R1 and R2, what is R1 R2? R1(A, B, C), R2(D, E) R1 R2 = π A, B, C, D, E (R1 φ R2) = π A, B, C, D, E (R1 R2) = R1 R2

13 A motivating example: 除 Division (1) Emp# Proj# Proj# Which employee participates in all projects? {1}

14 division Format: R1 R2 除 Division (2) Restriction: Every attribute in R2 is in R1. Consider: R1(A1,..., An, B1,..., Bm) R2(B1,..., Bm) Let T = π A1,..., An (R1). Semantics: Return those tuples in T such that for every tuple t returned, the concatenation of t with every tuple in R2 is in R1.

15 除 Division (3) E.g.: R1 R2 T R1 R2 A B C D C D A B A B a b c d c d a b a b a b e f e f b c e d b c e f e d e d c d e d e f a b d e T = π A1,..., An (R1) Derivation from existing operators: R1 R2 = T - π A1,..., An (T R2 - R1).

16 除 (Division) 除运算的含义给定关系 R (X,Y) 和 S (Y,Z), 其中 X,Y,Z 为属性组 R 中的 Y 与 S 中的 Y 可以有不同的属性名, 但必须出自相同的域集 R 与 S 的除运算得到一个新的关系 P(X),P 是 R 中满足下列条件的元组在 X 属性列上的投影 : 元组在 X 上分量值 x 的象集 Y x 包含 S 在 Y 上投影的集合 R S = {t r [X] t r R π Y (S) Y x } Y x :x 在 R 中的象集,x = t r [X]

17 除 (Division)( 续 ) 除操作是同时从行和列角度进行运算举例 [ 例 6] R: 图 2.7(a);S: 图 2.7(b); R S: 图 2.7(c) R A B C a1 b1 c2 S B C D b1 c2 d1 a2 b3 c7 b2 c1 d1 a3 b4 c6 b2 c3 d2 a1 b2 c3 a4 b6 c6 a2 b2 c3 a1 b2 c1

18 除 (Division)( 续 ) 分析 : 在关系 R 中,A 可以取四个值 {a 1,a 2,a 3,a 4 } 其中 : a 1 的象集为 {(b 1,c 2 ),(b 2,c 3 ),(b 2,c 1 )} a 2 的象集为 {(b 3,c 7 ),(b 2,c 3 )} a 3 的象集为 {(b 4,c 6 )} a 4 的象集为 {(b 6,c 6 )} S 在 (B,C) 上的投影为 {(b 1,c 2 ),(b 2,c 1 ),(b 2,c 3 ) } 显然只有 a 1 的象集 (B,C) a1 包含了 S 在 (B,C) 属性组上的投影, 所以 R S ={a 1 }

19 除 (Division)( 续 ) A sno s1 s1 s1 s1 s2 s2 s3 s4 s4 pno p1 p2 p3 p4 p1 p2 P2 p2 p4 pno p2 pno P2 p4 pno P1 p2 p4 B1 B2 B3 sno s1 s2 s3 s4 sno s1 s4 sno s1 A B1 A B2 A B3

20 除 (Division)( 续 ) 除的实际含义 : 有一个现实意义的集合, 希望在另一个集合中找出包含该集合的元组集例, 找出选修了所有课程的学生所有课程学生学生所有课程例, 找出选修了所有张三所选课的学生张三所选课学生学生张三所选课

21 Division (4) Example: Find the names and GPAs of all students who take all courses taken by a student with SSN = Students (SSN, Name, GPA) Takes (SSN, Course#) Step 1: Find all courses that are taken by the student with SSN = TEMP1 := π Course# (σ SSN = ` (Takes))

22 Division (5) Step 2: Find the SSNs of those students who take all courses in TEMP1. TEMP2 := Takes TEMP1 Step 3: Obtain the final result. RESULT := π Name, GPA (Students TEMP2)

23 Division (5) Find the names of employees who participate in every project. Employees(SSN, Name, Department) Projects(Proj#, Name, Budget) Participation(SSN, Proj#) π Name (Employees Proj# (Projects))) (Participation π

24 Relational Algebra Example (1) Many relational algebra queries can be expressed using selection, projection and join operators by following steps: (1) Determine necessary relations to answer the query. If R1,..., Rn are all the relations needed, P are all conditions and T are all (target) attributes to be output, then form the initial query: π T (σ P (R1... Rn))

25 Relational Algebra Example (2) (2) If P contains a condition, say Ci, that involves only attributes in Ri, replace Ri by σ Ci (Ri) and remove Ci from P. (3) If P contains a condition, say C, that involves attributes from both Ri and Rj, replace Ri Rj by Ri C Rj (or a natural join) and remove C from P. Be careful when there are two or more joins.

26 Relational Algebra Example (3) Consider the following database schema: Students(SSN, Name, GPA, Age, Dept-Name) Enrollment(SSN, Course#, Grade) Courses(Course#, Title, Dept-Name) Departments(Name, Location, Phone) Query: Find the SSNs and names of all students who are CS major and who take CS532.

27 Relational Algebra Example (4) (1) Relations Students and Enrollment are needed. T = { Students.SSN, Students.Name } P = { Students.Dept-Name = CS, Enrollment.Course# = CS532, Students.SSN = Enrollment.SSN } The initial relational algebra query is: π Students.SSN, Name (σ Dept-Name = `CS and Course# = `CS532 and Students.SSN = Enrollment.SSN (Students Enrollment))

28 Relational Algebra Example (5) (2) Replace Students by σ Dept-Name = `CS (Students) and Enrollment by σ Course# = `CS532 (Enrollment). Remove the two conditions from the initial expression. (3) Replace Students Enrollment by Students Enrollment and remove Students.SSN = Enrollment.SSN from the initial expression. The final expression: π Students.SSN, Name (σ Dept-Name = `CS (Students) σ Course# = `CS532 (Enrollment))

29 Relational Algebra Example (6) Cartesian product is most expensive, followed by non-equijoin, followed by equijoin and natural join, followed by selection and projection. Query: Find the SSN and name of each student who is CS major together with the titles of the courses taken by the student.

30 Relational Algebra Example (7) π Students.SSN, Name, Title (σ Students.Dept-Name = `CS and Students.SSN = Enrollment.SSN and Enrollment.Course# = Courses.Course# (Students Enrollment Courses)) = π Students.SSN, Name, Title ((σ Students.Dept-Name = `CS (Students) Enrollment) Enrollment.Course# = Courses.Course# Courses) = π Students.SSN, Name, Title (σ Students.Dept-Name = `CS (Students) (Enrollment Courses) ) Students.SSN = Enrollment.SSN

31 Outerjoin (1) R1 R2 R1 R2 A B C C D E A B C D E a1 b1 c1 c1 d1 e1 a1 b1 c1 d1 e1 a4 b3 c2 c6 d3 e2 The second tuples of R1 and R2 are not present in the result (called dangling tuples). Applications exist that require to retain dangling tuples.

32 Outerjoin (2) 10. o --- outer join Format: R1 o R2 Semantics: like join except (a) it retains dangling tuples from both R1 and R2; (b) it uses null to fill out missing entries. R1 o R2 A B C D E a1 b1 c1 d1 e1 a4 b3 c2 null null null null c6 d3 e2

33 Left Outerjoin and Right Outerjoin left outer join Format: R1 R2 Semantics: like outerjoin but retains only dangling tuples of the relation on the left right outer join Format: R1 R2 Semantics: like outerjoin but retains only dangling tuples of the relation on the right.

34 Relational Algebra Summary (1) Relational algebra operators: Fundamental operators: σ C (R), π A (R), ρ S (R), R1 R2, R1 - R2, R1 R2 Other traditional operators: R1 R2, R1 C R2, R1 R2 New operators: R1 o R2, R1 R2, R1 R2

35 Relational Algebra Summary (2) Some identities: σ C1 (σ C2 (R)) = σ C2 (σ C1 (R)) = σ C1 and C2 (R) π L1 (π L2 (R)) = π L1 (R), if L1 L2 R1 R2 = R2 R1 R1 (R2 R3) = (R1 R2) R3 R1 R2 = R2 R1 R1 (R2 R3) = (R1 R2) R3 Either both joins are natural or are non-natural

36 Relational Algebra Operations 27

37 Relational Algebra Operations 28

38 第二章关系数据库 2.1 关系模型概述 2.2 关系数据结构 2.3 关系的完整性约束 2.4 关系代数 2.5 关系演算 2.6 小结关系的数据操作

39 关系演算 Relational Calculus Relational calculus query specifies what is to be retrieved rather than how to retrieve it. No description of how to evaluate a query. Based on a branch of symbolic logic called predicate calculus( 谓词演算 ). When applied to databases, relational calculus is in two forms: tuple-oriented ( 元组 )and domainoriented( 域 ). 54

40 关系演算 Relational Calculus In first-order logic or predicate calculus, a predicate is a truth-valued function with arguments. When we substitute values for the arguments, the function yields an expression, called a proposition, which can be either true or false. 55

41 关系演算 Relational Calculus If a predicate contains a variable, as in x is a member of students, there must be a range for x. When we substitute some values of this range for x, the proposition may be true; for other values, it may be false. If P is a predicate, then we write the set of all x such that P is true for x, as {x P(x)} Predicates can be connected using (AND), (OR), and (NOT) 56

42 元组关系演算 Tuple-oriented Relational Calculus Interested in finding tuples for which a predicate is true. Based on use of tuple variables. Tuple variable is a variable that ranges over a named relation: that is, a variable whose only permitted values are tuples of the relation. 57

43 元组关系演算 Tuple-oriented Relational Calculus To specify the range of a tuple variable S as the Student relation. RANGE OF S IS Student To find the set of all tuples S such that P(S) is true. {S P(S)} 58

44 元组关系演算 Tuple-oriented Relational Calculus To find the Sno, Sname, Ssex, Sage, Sdept of all student with age more than 20, we write RANGE OF S IS Students {S S.sage > 20} S.sage means the value of the Sage attribute for the tuple S. 59

45 元组关系演算 Tuple-oriented Relational Calculus To find a particular attribute, such as name, we write. RANGE OF S IS Students {S.sname S.age > 20} 60

46 元组关系演算 Tuple-oriented Relational Calculus We can use two quantifiers to tell how many instances the predicate applies to. Existential quantifier ( there exists ) Universal quantifier ( for all ) 61

47 举例用存在量词的检索 [ 例 8] 查询选修 2 号课程的学生名字 RANGE OF X is SC RANGE OF Y is STUDENT {Y.Sname X(X.Sno=Y.Sno X.Cno='2 } [ 例 9] 查询选修了其直接先行课是 6 号课程的这样课程的学生号 RANGE OF X is Course RANGE OF Y is SC {Y.Sno X (X.Cno=Y.Cno X.Pcno='6 }

48 举例 [ 例 10] 查询至少选修一门其先行课为 6 号课程的学生名字 RANGE OF CX is Course RANGE OF SCX is SC RANGE OF Y is Student {Y.Sname SCX (SCX.Sno=Y.Sno CX (CX.Cno=SCX.Cno CX.Pcno='6')} 可将元组关系演算公式变换为前束范式的形式 : {Y.Sname SCX CX(SCX.Sno=Y.Sno CX.Cno=SCX.Cno CX.Pcno='6 }

49 举例带有多个关系的表达式的检索 [ 例 11] 查询成绩为 90 分以上的学生名字与课程名字 RANGE OF SCX is SC RANGE OF Y is Student RANGE OF Z is Course {(Y.Sname,Z.Cname) SCX (SCX.Grade 90 SCX.Sno=Y.Sno Z.Cno=SCX.Cno}

50 举例用两种量词的检索 [ 例 13] 查询选修了全部课程的学生姓名 RANGE OF CX is Course RANGE OF SCX is SC RANGE OF SX is Student {XS.Sname CX SCX (SCX.Sno=XS.Sno SCX.Cno=CX.Cno) }

51 除 (Division) R S: 另一种定义 t 属于 R S, 当且仅当满足以下两个条件同时成立 : 1)t 在 π R-S (r) 中 2) 对 s 中的每一个元组 t s, 在 r 中都有元组 t r 同时满足以下条件 : t r [S] = t s [S] and t r [R-S] = t R1 R2 = T - π A1,..., An (T R2 - R1).

52 Relational algebra vs. Tuple-oriented Relational Calculus P66-67

53 2.5.1 元组关系演算语言 ALPHA 一种典型的元组关系演算语言, 但没有实际实现由 E.F.Codd 提出 INGRES 所用的 QUEL 语言是参照 ALPHA 语言研制的语句检索语句 :GET 更新语句 :PUT,HOLD,UPDATE,DELETE,DROP

54 检索操作语句格式 : GET 工作空间名 [( 定额 )]( 表达式 1) [: 操作条件 ] [DOWN/UP 表达式 2] 定额 : 规定检索的元组个数格式 : 数字表达式 1: 指定语句的操作对象格式 : 关系名关系名. 属性名元组变量. 属性名集函数 [, ] 操作条件 : 将操作结果限定在满足条件的元组中格式 : 逻辑表达式表达式 2: 指定排序方式格式 : 关系名. 属性名元组变量. 属性名 [, ]

55 检索操作 ( 续 ) [ 例 7] 查询信息系学生的名字 RANGE Student X GET W (X.Sname): X.Sdept='IS'

56 Domain-oriented Relational Calculus Uses variables that take values from domains instead of tuples of relations. If P(d 1, d 2,..., d n ) stands for a predicate with variables d 1, d 2,..., d n, then {d 1, d 2,..., d n P(d 1, d 2,..., d n )} Means the set of all domain variables d 1, d 2,..., d n for which the predicate, or formula, P(d 1, d 2,..., d n ) is true. 71

57 Domain-oriented Relational Calculus We often test for a membership condition, to determine whether values belong to a relation. The expression R(x, y) evaluates to true if and only if there is a tuple in relation R with values x, y for its two attributes. 72

58 Example - Domain-oriented Relational Calculus Find the names of all managers who earn more than 25,000. {fname, lname position, salary (Staff (lname, position, salary) position = Manager salary > 25000)} Each attribute has a (variable) name. Condition Staff (lname, position, salary) ensures domain variables are restricted to attributes of same tuple. 73

59 域关系演算语言 QBE 一种典型的域关系演算语言由 M.M.Zloof 提出的 QBE 1978 年在 IBM370 上得以实现 QBE 也指此关系数据库管理系统 QBE:Query By Example 基于屏幕表格的查询语言查询要求 : 以填写表格的方式构造查询即 : 用示例元素 ( 域变量 ) 来表示查询结果可能的情况查询结果 : 以表格形式显示

60 域关系演算语言 QBE ( 续 ) QBE 操作框架关系名属性名操作条件域值或查询条件

61 一检索操作操作步骤为 : (1) 用户提出要求 ; (2) 屏幕显示空白表格 ; (3) 用户在最左边一栏输入要查询的关系名, 例如 Student; student

62 检索操作 ( 续 ) (4) 系统显示该关系的属性名 ; Student Sno Sname Ssex Sage Sdept (5) 用户在上面构造查询要求 Student Sno Sname Ssex Sage Sdept P. T AO. C

63 检索操作 ( 续 ) 构造查询的几个要素 : T: 示例元素, 即域变量一定要加下划线示例元素是这个域中可能的一个值, 它不必是查询结果中的元素例如要求信息系的学生, 只要给出任意的一个学生名即可, 而不必真是信息系的某个学生名 C: 查询条件, 不用加下划线可使用比较运算符 >,,<,,= 和其中 = 可以省略 P.: 打印操作符, 指定查询结果所含属性列 AO./DO.: 排序要求

64 检索操作 ( 续 ) (6) 屏幕显示查询结果 Student Sno Sname Ssex Sage Sdept 李勇张立 C

65 关系演算与关系代数关系演算是描述性 (descriptive) 形式的, 而关系代数是说明性 (prescriptive) 形式的关系演算描述了问题是什么, 而关系代数说明了解决问题的过程或者, 可以说, 关系代数是过程化的 ( 诚然, 是高级的, 但仍然是过程化的 ); 而关系演算是非过程化的上述区别仅仅是表面上的实际上, 关系代数和关系演算在逻辑上是等价的即每一个代数表达式都有一个等价的演算表达式, 每一个演算表达式都有一个等价的代数表达式两者是一一对应关系所以两者的区别仅仅是形式上的可以证明, 关系演算更接近自然语言, 而关系代数更像程序语言特别地, 没有哪一种方法真正地比另外一种更加非过程化

66 比较举例元组关系演算域关系演算查询选修了全部课程的学生号码和姓名 RANGE OF CX is Course RANGE OF SCX is SC RANGE OF SX is Student {XS.Sname, XS.Sno CX SCX (SCX.Sno=XS.Sno SCX.Cno=CX.Cno) } {Sname, Sno sno,sname(student(sno,sname) ) Cno( Course(cname, cno) =>SC(sno,cno) } 关系代数 π Sno,Cno (SC) π Cno (Course) π Sno,Sname (Student) 74

67 关系演算与关系代数 Codd 认为, 至少关系代数跟关系演算一样, 具有强大的表达能力 ( 参看 [6.1]) 他给出了一算法证明了这一点这一算法叫 Codd 简约算法通过这个算法, 任意一个演算表达式都可以简约为在语法上等价的代数表达式如果一门语言具备了关系演算这样的功能, 那么可以说是满足关系完备性 (relational complete) 的由于关系代数具备关系完备性, 故为了表现某一给定语言 L 具备此特征, 就必须充分表现 : (a)l 包括类似八个代数操作符的操作 ( 实际上, 要充分表现关系代数的五个基本的操作 ), (b)l 语言的任一操作符的操作数可能是 L 的任一表达 SQL 是用这种方式表示关系完备的语言的一个例子

68 Other Languages Transform-oriented languages are non-procedural languages that use relations to transform input data into required outputs (e.g. SQL). Graphical languages provide the user with a picture or illustration of the structure of the relation. The user fills in an example of what is wanted and the system returns the required data in that format (e.g QBE). Natural Language Interface (NChiql) 76

69 第二章作业 3/1 习题 1,2,3 3/4 习题 4,5,6,7 思考题 : 补充作业 dbhw2 交作业时间 :3/11

70 Book Time 阅读 : 流失的岁月, 李新作者敢说真话实话, 文中揭露的某些史实在今人看来简直是匪夷所思

数据库系统概论

数据库系统概论 An Introduction to Database Systems 第三章 SQL 语言 ( 之基本查询部分 ) 2016, 3, 17 上节课 SQL: SQL86,SQL89,SQL92,SQL99 DDL,DML,DCL DDL 基本表, 索引, 视图 CREATE TABLE,CREATE INDEX ALTER TABLE, DROP TABLE, DROP INDEX