关系数据库系统而言需要从两个方面讨.ppt

1、第11章关系代数任务的实现有效处理用算法高级查询语言编写的用户查询是数据库管理系统的主要任务。对于关系数据库系统，需要从两个茄子方面讨论查询处理。第一个方面是各种关系代数操作的算法和复杂性分析。第二个方面是生成逻辑优化的关系代数表达式或其他形式的查询计划。牙齿章节介绍了任务的第一个方面。下一章将讨论第二个方面。第一节查询处理流程第二节选择任务实施算法第三节笛卡尔乘积实施算法第五节投影任务实施算法第六节集合和交叉实施算法。k，第一节查询处理流程查询是以高级查询语言(如SQL)表示的数据库操作序列。以下是处理查询的基本过程：扫描和解析；查询最优化；生成查询代码；执行查询；查询；查询的内部表示；查询

2、的执行计划；查询计划的执行代码；查询结果；1)语法检查2)语义验证；3)完整性安全检查；4)创建查询的内部表示法(树、图)。确定优化的执行战略、创建优化的执行计划、合并DBMS提供的各种操作算法、生成计划的执行代码、控制执行查询计划、生成查询结果、K1、层次结构和网格数据库查询、以下假设：每个关系存储在一个文档中。每个文档仅保存一个关系。以下参数在牙齿章节中经常用到：TR关系R的元组数BR磁盘块数IR每个元组的字节数M主内存缓冲区的块数B每个磁盘块字节数，K11，关系代数分析每个操作的算法时，我们用磁盘的访问块数来衡量算法的复杂性。第二节选择操作的实施算法选择操作是从关系r中提取满足条件c的元

3、组。SQL表示法k2，select * from r where C1 and C2 or C3，表示法的第一个子项(select)返回指定的属性，第二个子项(where)返回操作选择条件。选择条件可以是简单条件，也可以是复杂条件。即，用逻辑运算符and/or/not连接一组简单条件的条件。如果逻辑运算符为and，则复合条件称为并集条件。一般DBMS提供多种算法选项。徐璐适合其他使用环境的算法。有些算法需要参与运算的关系中指定的存储结构或访问方法。以下是选择操作的实施算法说明。下一页，具有简单条件的选择算法1。线性搜索：按原始顺序扫描关系，删除符合条件的元组。2.2等分搜索：关系必须排序，选择

4、条件是排序字段的等效比较。搜索时间复杂性为O(log2N)的N元组的关系3。基本索引或散列搜索：选择标准必须是与基本索引属性或散列属性相对应的比较。4.使用基本索引查找多个元组。如果条件是基本属性的沸腾比较，则使用对等比较查找所有沸腾满足比较条件的元组。5.使用聚集索引按等效比较条件查找多个元组。6.使用b树索引搜索。联合条件(一组简单的条件用and连接)牙齿的选择算法7。联合选择算法：首先作为简单的条件，按照前面介绍的方法进行选择，然后确保满足其他条件。8.组合索引算法：如果组合条件全部是对等比较，则考虑在相关属性中使用组合索引。9.指针交叉算法：如果并集条件是等效比较，则使用每个索引字段的

5、辅助索引获取元组指针集，然后获取该集的交集。，K21，设置第三个笛卡尔乘积的实现算法：如果关系r和s的元组字节数分别为IR和IS，元组数分别为TR和TS，则笛卡尔乘积RS的元组字节数为IRIS，元组数为TRTS，空间字节数为TRTS(IRIS)，磁盘块数为bris，因此笛卡尔乘积是一项耗时的任务以下是笛卡儿积的四个茄子实现算法的介绍。选择算法时，分析访问磁盘时的各种算法复杂性和内存缓冲区要求。1简单算法2主内存算法3半主内存算法4对关系算法，K3，1笛卡尔乘积的简单算法这种算法必须提供主内存可容纳两个磁盘块数据的缓冲区。关系R和S分别读取一片主存储器缓冲区，并参与笛卡尔乘积运算。使用嵌套循环完

6、成RS。算法定义是、R、S、K31、输出RS、结果关系result初始化；For R每个RB do读取RB主内存；For S每个SB do读取SB主内存；在主内存中完成RB和SB的元组笛卡尔乘积，将元组存储在result中。EndforEndfor返回Result。因为每次读取R片时都扫描一次S，所以整个过程中R读一次，S读回BR。磁盘访问是BR BRBS BRS。其中BRS=TRTS(IR IS)/b是输出结果中的写入磁盘块数。动画，2笛卡尔乘积的主内存算法这种算法假设内存缓冲区有足够的容量，关系R和S可以一次读取到主内存中，完成笛卡尔乘积运算。在整个过程中，两种关系各读了一遍。牙齿算法磁盘

7、访问是BR BS BRS。其中BRS=TRTS(IR IS)/b是写入磁盘块数。算法格式为、RS、For主内存中r的每个元组r do for主内存中s的每个元组s do生成元组(RS)存储在牙齿result中。EndforEndfor返回result。动画，3笛卡尔乘积的伴奏内存算法这种算法家庭内存缓冲区比较大。将关系S一次读取到主内存中，而R一次一片地去主内存中参加笛卡尔乘积运算。主内存算法，整个过程，重读两种关系是一样的。磁盘访问是BR BS BRS。其中BRS=TRTS(IR IS)/b是写入磁盘块数。算法格式定义为、RS、R、S、K33和result初始化。将s读为主内存SB。For

8、R每个RB do读取RB主内存；在主内存中完成RB和SB的元组笛卡尔乘积，将元组存储在result中。EndforResult .返回。牙齿算法必须能够在主内存缓冲区中容纳一个BS磁盘块。从磁盘访问方程看，R和S是对称的。匹配关系R和S的位置不会更改磁盘访问量，但主内存缓冲区要求不同。、2的资源优势，比简单的算法效率更高的算法。大关系算法分配R和S的主要内存空间分别为1和M-1。算法：RS、R、S、S除以BS/将For j=1 to BR do r的j块读取到主内存中。在主内存中，RS完成结果元组存储在result中。EndforEndfor由于s读了一次，R读完了BS/(M-1)，因此磁盘访

9、问是BRBS/(M-1) BS BRS。其中，BRS=TRTS(IR IS)/b不会改变读取的复杂性，但会在一定程度上减少生成的输出量，因为写入磁盘块数、动画选择操作和两个元组的连接都来自主内存。例如，在笛卡尔乘积关系算法连接操作中，读取板的块数仍然是BR BS /(M-1) BS，但是连接结果的写入磁盘块数是BBRS。作为对等比较器的连接操作称为对等连接。同名的两个属性的对等连接称为自然连接。您可以修改关系的某些属性名称，从而将对等连接转换为自然连接。牙齿部分仅考虑自然连接。1.估计连接操作结果2。连接操作实施算法，第4部分连接操作的实施算法考虑关系R，S条件C的连接操作RcS。我们用作连接

10、运算符。关系r，s连接操作的SQL表达式如图所示。其中是关系r的属性a和关系s的属性b之间的算术比较。select R.*，S.* from R，S where R.a S.b，K4，用于分析牙齿页面的符号：关系R S属性a b c值域DA E DB DC元素数IA J IB IC元组数tr ts，以下是关系R的属性是A和B，关系S的属性是B和C。连接结果RS的属性为A、B、C。在下面的分析中，使用右侧表格中的符号。K41，设置(a，b，c) DADBDC，连接结果RS的元组数size(RS)=size(RS)PAB CRS=size(RS)pabr pbe PBC连接操作实施算法下常用的四个

11、茄子连接操作算法。在讨论中，tA1、A2、AK表示元组T位于属性A1、A2、AK中的值。1.回路复叠算法2。SORT-MERGE连接算法3。HASH连接算法4。索引连接算法后，所有三个茄子算法都需要对运营关系进行一些茄子额外处理。需要按SORT-MERGE连接算法连接域字典处理生产关系。必须预先为HASH连接算法连接域的HASH存储结构设置操作关系。索引连接需要算法连接域的字典操作关系聚合索引结构。K42，1。RA=BS的循环嵌套算法笛卡尔乘积的简单算法，算法扫描操作关系R和S的元组，形成双环。区别在于必须确定连接条件。只能输出满足连接条件的元组。将a，b分别设置为r，s的属性子集。RA=BS

12、的算法：K42a，初始化resultFor rR do for sS do if rA=sB then (rs)写result endif endfor endfor end for算法访问的估计值为BR BRBS U。其中BR和BS分别是关系r和s中的磁盘块数，u是连接结果result中的数据块数。要减少访问开销，请使用较小的关系R作为外部循环。、RS、r、s按排序顺序扫描两个关系的元组，检查连接条件，然后连接相应的元组。牙齿算法访问块数为BR BS U。其中u是连接结果中的磁盘块数。2)通常，每个关系首先按连接域排序，然后使用上述算法连接。这就是SORT-MERGE连接算法。排序操作是多路

13、复用算法，如果主内存缓冲区容量为m块，则关系R的磁盘访问(BRlogMBR)是关系S的磁盘访问(BSlogMBS)，因此SORT-MERGE连接算法磁盘访问块数为(brlogmbr bslogmbs)，端口号为0 - 1根据RS的散列连接算法1)连接属性，R和S的HASH档案HR和HS 2设置)元组分布均匀，每个桶连接上循环重叠、算法、I桶连接的访问块数为cost (br/n，bs/n)=(br/n) (br)对于r，按元组循环，根据连接的域值检查IS指针，获取S记录，然后用大元组连接以创建结果关系。在“连接域值”字段中，s为均匀分布，算法访问块数为BR TRBS/I U，其中成绩块针脚900 - 880 - 864 - 822 - 822成绩单编号名称900 -.880 -.864-.864 -.822-.822 -扫描S对群集索引IS、关系S、主内存、缓冲区、R的元组的块数的估计为BS/I、K42d、关系R、