关系查询处理和查询优化

第一章（选择、简答、填空）DB(数据库)，数据库是长期存储在计算机内，有组织的、可共享的大量数据的集合。

数据库中的数据按一定的数据模型组织、描述和储存，具有较小的冗余度、较高的数据独立性和易扩展性，并可为各种用户共享。

DBMS(数据库管理系统)，数据库管理系统是一种操纵和管理数据库的大型软件，是用于建立、使用和维护数据库，它对数据库进行统一的管理和控制，以保证数据库的安全性和完整性。

DBS(数据库系统)，数据库系统是由数据库、数据库管理系统(及其应用程序开发工具),应用程序和数据库管理员组成的存储、管理和维护数据的系统。

DB、DBMS、DBS之间的关系:DBS里面包括DB和DBMS.（简答）数据库系统的特点：1.数据结构化 2.数据的共享性高，冗余度低，易扩充3.数据独立性高 4.数据由DBMS统一管理和控制数据模型是数据库系统中用于提供信息表示和操作手段的形式构架，是现实世界的模拟和抽象数据模型三要素：数据结构、数据操作、数据的约束条件。

三级模式结构：外模式、模式和内模式一、模式（Schema）定义：也称逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。

理解：①一个数据库只有一个模式；②是数据库数据在逻辑级上的视图；③数据库模式以某一种数据模型为基础；④定义模式时不仅要定义数据的逻辑结构（如数据记录由哪些数据项构成，数据项的名字、类型、取值范围等），而且要定义与数据有关的安全性、完整性要求，定义这些数据之间的联系。

二、外模式（External Schema）定义：也称子模式（Subschema）或用户模式，是数据库用户（包括应用程序员和最终用户）能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。

理解：①一个数据库可以有多个外模式；②外模式就是用户视图；③外模式是保证数据安全性的一个有力措施。

三、内模式（Internal Schema）定义：也称存储模式（Storage Schema），它是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式（例如，记录的存储方式是顺序存储、按照B树结构存储还是按hash方法存储；索引按照什么方式组织；数据是否压缩存储，是否加密；数据的存储记录结构有何规定）。

单选题(共40道题)收起1.（2.5分）关系代数的基本操作组成关系代数的完备操作集，其他操作均可以由基本操作来表达。

具体而言，关系代数的基本操作有（）。

••••我的答案：C 此题得分：2.5分2.（2.5分）在具有非过程性查询语言的数据库系统中，（）是查询处理的核心。

••••我的答案：B 此题得分：2.5分3.（2.5分）关系数据库系统的查询处理包括两个方面的内容：查询优化和（）。

••••我的答案：A 此题得分：2.5分4.（2.5分）（）是选择操作中的线性搜索算法。

•进行排序•••如果满足，则作为一个结果元组输出我的答案：D 此题得分：2.5分5.（2.5分）（）是选择操作中的主索引搜索算法。

•进行排序•••如果满足，则作为一个结果元组输出我的答案：B 此题得分：2.5分6.（2.5分）设关系R和S的属性个数分别为r和s，则(R×S)操作结果的属性个数为（）。

••••我的答案：A 此题得分：2.5分7.（2.5分）查询处理最终可转化成基本的（）代数操作。

••C、空值•D、集合我的答案：A 此题得分：2.5分8.（2.5分）计算笛卡尔乘积的最简单算法称为（）。

•A、大关系算法•B、主存算法•C、嵌套循环算法•D、半主存算法我的答案：C 此题得分：2.5分9.（2.5分）在SQL中，表示选择操作的语句为（）。

•A、SELECT * FROM R WHERE C1 AND C2 OR C3•B、SELECT R.*,S.* FROM R,S WHERER.A S.B •C、INSERT INTO R VALUE（a,b,c,d）•D、UPDATE R SET A=a WHEREC1 AND C2 OR C3我的答案：A 此题得分：2.5分10.（2.5分）在SQL中，表示连接操作的语句为（）。

•A、SELECT * FROM R WHEREC1 AND C2 OR C3•B、SELECT R.*,S.* FROM R,S WHERER.A S.B •C、INSERT INTO R VALUE（a,b,c,d）•D、UPDATE R SET A=a WHEREC1 AND C2 OR C3我的答案：B 此题得分：2.5分11.（2.5分）投影操作中不包含主键，需要去除重复（）。

数据库系统原理福州大学计算机系郭红G u o h o n g @f z u .e d u .c n第10-11章习题课第三篇系统篇*第九章关系查询处理和查询优化第十章数据库恢复技术第十一章并发控制*第十二章数据库管理系统查询处理步骤查询优化是查询处理的核心，只在具有非过程性查询语言的D B M S 才具有此功能。

在这样系统中，用户使用数据库语言定义查询要求，而无需要说明怎样去查询，因此查询优化是完全必要而且非常重要的。

查询优化包括：1、代数优化——关系代数表达式优化改变表达式中操作的次序和组合，提高查询效率2、物理优化——存取路径和低层操作算法的选择。

选择的依据可以是基于规则，代价或语义。

关系查询处理与查询优化关系代数表达式优化的一般准则典型的启发式规则:1、选择运算应尽可能先做。

2、同时执行相同关系上的多个选择与投影操作，以免多次扫描关系。

3、把投影同其前或后的双目运算结合起来，以免多次扫描关系。

关系代数表达式优化的一般准则n4、某些选择运算＋在其前面执行的笛卡尔积===>等值连接运算例：бS t u d e n t.S n o=S C.S n o(S t u d e n t×S C)S t u d e n t∞S CS t u d e n t.S n o=S C.S n on5、提取公共子表达式关系代数表达式的内部表示查询的内部表示形式——查询树∏A(σp=‘IS’AND N=‘User’((R1×R2) ×R3))×∏AσP=‘IS’AND N=‘User’×R3R2R1优化的关系代数表达式∏C,CN ((∏SC.C#(∏S#(σSD=’IS’(S))∞S.S#=SC.S#∏S#.C#(SC))∞SC.C#=C.C#∏C#,CN (C))∏∞SC.C#=C.C#∏SC.C# ∏C.C#,∞S.S#=SC.S# C∏S.S# ∏SC.S#, SC.C#σSD=’IS’SCD B M S 的数据控制功能数据库系统中的数据是由D B M S 统一管理和控制的。

《数据库原理》第一章、绪论1.四个基本概念的掌握：数据——描述事物的符号记录数据库——长期存储在计算机内的有组织,可共享的数据集合。

例如：SQLServer2000中默认的数据库master。

DBMS——位于用户与操作系统之间的一层数据管理软件。

例如：SQLServer2000,Access,Orecal 等。

数据库系统——数据库、DBMS、应用程序等有关软件、硬件及各类人员（数据库管理员和用户）。

例如：学生个人信息管理系统。

数据库系统的核心是数据库管理系统。

2.四者的关系，核心，理解P6图1.13.数据管理的三个阶段——人工管理、文件系统、数据库系统，了解每个阶段的特点4.数据库系统的特点——数据整体结构化；数据冗余度低，共享性高，易扩充；数据的物理独立性与逻辑独立性强（物理、逻辑独立性的概念，体现在那些地方）；由DBMS统一管理控制的四个功能（P11四点）5.数据模型的组成要素——数据结构、数据操作、数据的完整性约束6.概念模型——实际上是现实世界到机器世界的一个中间层次（第一层抽象），表示方法——E－R图（能熟练掌握绘制方法）。

7.概念模型中的基本概念——实体、属性、码、域、实体型、实体集、联系（事物内部的联系、两个事物之间的联系【1：1，1：n，n：m】、多个事物之间的联系）P158.数据模型——层次、网状、关系（主流）9.关系模型中的概念——关系，元组，属性，码，域，分量，关系模式P2910.模式，外模式，内模式定义，有哪两种模式映像及其作用P31-P34书上习题回顾—— p.19-20 1.6.2和1.6.3（1、2题）第二章关系数据库1.关系模型的组成要素——关系数据结构（关系）、关系操作集合（选择、投影、连接、除、并、交、差等查询操作和增加、删除、修改操作，特别是某些关系操作的表达式）、关系完整性约束（后面具体介绍）2.基本概念——笛卡尔积、关系候选码、主码、主属性、非码属性、全码3.基本关系的性质——P45六点4.关系的完整性：实体完整性——规定关系中的所有主属性不能为空，而不仅是整体不能为空NULL的含义（不知道或者无意义的值）。

数据库原理与应用?课程教学大纲【说明部份】数据库技术是计算机科学技术中开展最快的领域之一，也是应用最广的技术之一。

数据库技术是计算机科学的重要分支，数据库技术和数据库系统已经成为计算机信息系统的核心技术和重要根底。

数据库原理与应用?是本科计算机专业和信息系统信息管理等相关专业的专业主干课程。

【正文部份】一、课程内容概述本课程系统讲述数据库系统的根底理论、根本技术和根本方法。

内容包括：数据库系统的根本概念、数据模型、关系数据库及其标准语言SQL、数据库平安性和完整性的概念和方法、关系标准化理论、数据库设计方法和步骤，数据库恢复和并发控制等事务管理根底知识，关系查询处理和查询优化等。

二、课程目标通过本课程学习，使学生系统地掌握数据库系统的根本原理和根本技术。

要求在掌握数据库系统根本概念的根底上，能熟练使用SQL语言在某一个数据库管理系统上进展数据库操作；握数据库设计方法和步骤，具有设计数据库模式以及开发数据库应用系统的根本能力。

三、先修课程* 计算机程序设计方法和语言* 数据构造* 离散数学* 操作系统四、教学内容和教学要求〔一〕绪论〔4课时〕内容概述：阐述数据库的根本概念，介绍数据管理技术的进展情况、数据库技术产生和开展的背景，数据模型的根本概念、组成要素和主要的数据模型，概念模型的根本概念及ER方法，数据库系统的3级模式构造以及数据库系统的组成。

本章目标：本章讲解的数据库根本概念和根本知识是学习后续各个章节的根底。

学习本章的目的在于了解根本知识，掌握根本概念，为以后的学习打好扎实的根底。

重点：结实掌握概念模型的根本概念及其主要建模方法ER方法；掌握关系数据模型的相关概念、数据库系统三级模式和两层映像的体系构造、数据库系统的逻辑独立性和物理独立性等；对于如何通过ER方法描述现实世界的概念模型要做到能够举一反三的程度。

难点：本章的难点是需要掌握数据库领域大量的根本概念。

有些概念一开场接触会感到比拟抽象，但不要紧，随着学习的逐渐推进，在后续章节中，这些抽象的概念会逐渐变得清晰具体起来。

关系查询优化关系查询优化是影响DBMS性能的关键因素，关系系统的查询优化即使DBMS实现的关键技术又是关系系统的有点所在。

查询优化的工作包括两个方面，一方面是关系数据库系统内部提供的优化机制，另一方面是用户通过改变查询的运算次序和建立索引等机制进行优化。

关系数据库系统查询优化的目标是：选择有效的策略，快速求得给定关系表达式的值，以减少查询执行的总开销。

总代价= I/O代价+CPU代价+(其他代价)我们先看一个简单的列子，说明为什么要进行查询优化。

一、举例说明我用Microsoft Visual foxPro建立三个数据库文件，他们的文件名分别是c#.dbf存储课程信息、S#.dbf存储学生的基本信息、sc#.dbf存储学生的学习成绩信息，通过对三个数据表的操作，可以了解学生的所修的全部课程和他们的各门课程的成绩。

数据表2 sc#.dbf当输入如下的查询的语句，运行结果为：系统可以用多种等价的关系代数表达式来完成这一查询：①Q1=∏s#.姓名(σs#.学号=sc#.学号(s#×sc#))②Q2=∏s#.姓名(σsc#.课程号=’01100002’③Q3=∏s#.姓名(σ课程号=’01100002’(sc#))二、从时间复杂度进行计算表达式（1）的查询执行时间分析：①计算广义笛卡尔积。

把S#和SC#的每个元组连接起来。

一般连接的做法是：在内存中尽可能多地装入某个表（如S#表）的若干个元组，留出一块存放另一个表（如SC#表）的元组。

然后把SC#中的每个元组和S#中每个元组连接，连接后的元组装满一块后就写到中间文件上，再从SC#中的读入一块和内存中的S#元组连接，直到SC#表处理完。

这时再一次读入若干块S#元组，读入一块SC#元组，重复上述处理过程，直到把S#表处理完。

设一个块能装10个S#元组或100个SC#元组，在内存中存放中存放5块S#元组和1块SC#元组，则读取总块数为：21001002010010010105101010433=⨯+=⨯⨯+ (块) 其中读S#表100块。

关系数据库查询优化策略研究摘要：作为数据的承载平台，数据库在各行各业都得到了广泛应用。

查询操作是数据库管理系统最重要的功能之一，使用频率最高。

以关系型数据库为基础，从不同的角度出发，对数据库查询优化策略进行了研究。

关键词：关系数据库；数据查询；查询优化0 引言随着社会经济的不断发展，人们已经进入了一个信息爆炸的时代，随之而来的则是大量数据的存储与操作。

如今，数据库管理系统已经深入到各行各业，具有代表性的是银行、证券行业。

存储在数据库里的数据存在巨大价值，对这些数据最频繁的操作就是查询。

如何从数据库里存储的海量数据中以最快的速度找到想要的数据，直接关系到以数据库服务器作为后台的各大信息系统的运行效率，该问题也即是如何对数据库的查询进行优化。

因此，在此背景下，通过对市场占有率最多的关系型数据库进行探讨，来研究查询优化[1]。

1 关系数据库介绍1.1 关系模型关系模型是美国IBM公司San Jose研究室的研究员E.F.Codd于1970年首次提出，而关系模式的诞生也开创了数据库关系方法和关系数据理论研究的历史。

简言之，关系模型是一种由二维表形式表示实体和实体间关系的数据模型，它是在集合代数的基础上发展的。

在关系模型中，一个关系就没有重复行和重复列的二维表，二维表的每一行在关系中称为元组，每一列在关系中称为属性。

关系运算作为关系模型的核心，主要有并（∪）、交（—）、差（∩）、笛卡尔积（×）、连接（）、投影（π）、选择（）、除（÷）八种。

1.2 关系数据库根据所使用数据模型的不同，可以将数据库进行分类，因此基于关系模型的数据库就是关系数据库。

所谓关系数据库，其数据组织的逻辑结构一定是采用关系数据模型，即使用二维表格方式描述实体及其相互间的关系，然后把这种关系逻辑结构采用一定方式向物理结构映射，并存储在某种存储设备上的数据库。

2 数据查询过程关系数据库主要有查询、插入、删除和修改这四大常用操作，其中，查询是最主要、使用最频繁的操作。