数据库系统概念-查询处理

数据库系统概念-查询处理
选择运算
  • A1:线性搜索,平均代价Br/2,最坏情况Br
  • A2: 二分搜索,属性有序,代价[logBr]

    索引选择
  • A3: (主索引,码属性等值比较)可以检索到唯一一条满足条件的记录,代价:B+树树高加上读取一条记录I/O代价
  • A4: (主索引,非码属性等值比较)主索引可以检索到多条满足条件的记录,且多条记录顺序存储,代价:B+树树高加上具有搜索码值的盘块数
  • A5: (辅助索引,等值比较)索引字段为码属性直接得到一条记录.索引字段为非码属性,得到多条记录

    比较选择
  • A6: (主索引,比较)B+树有序主索引
  • A7: (辅助索引,比较)有序辅助索引,小值从小段开始,大值从 大端开始

    比较选择
  • A8: 索引合取(取交)先现则满足一个条件的记录,加入缓冲区,在缓冲区中验证其他条件
  • A9: (组合所用合取)直接利用合适的符合索引查询
  • A10: (记录标识符的交)每个条件遍历标记一边,取所有被标记的交际
  • A11: (记录标识符的并)逐一扫描索引获取满足单个条件的元祖指针,将所有指针集做并集

连接运算
  • 嵌套循环(重名属性会出现)
  • 块嵌套循环,每次在块内循环嵌套检查元组匹配,有效减少比较次数
  • 索引嵌套循环连接:嵌套循环连接的内层如果有索引,使用索引代替循环
  • 归并链接:用于自然链接和等值连接
    • 双有序直接有序归并
    • 单有序,归并后,对索引项进行按地址排序,可实现有序
  • 消除重复: 代价高,明确声明是否去重
    • 归并/散列可直接在过程中消除重复
  • 集合
    • 并集: Hr建立散列索引,将Hs中元组加入到上诉散列索引中,条件是该元组不在散列索引中,散列索引最终即结果
    • 交集: Hr建立散列索引,对Hs中元组探查散列索引,出现在散列索引的记录放入结果
    • 差集: Hr建立散列索引,对Hs中元组探查散列索引,出现在散列索引的记录从索引中删除
外连接
- 计算连接法:
    - 左外连接:计算链接,将左集未参与链接集合扩展放入结果
    - 右外连接:计算链接,将右集未参与链接集合扩展放入结果
    - 全外连接:计算链接,将左右集未参与链接集合扩展放入结果
- 嵌套修改法
    - 左外连接:左边外循环,右表内循环,内外匹配加入结果,内部均不匹配的外记录也加入结果
    - 右外连接:右边外循环,左表内循环,内外匹配加入结果,内部均不匹配的外记录也加入结果
- 扩展归并连接获得自然链接和等值全外联
    - 归并完成,将不与另一关系任一记录匹配的记录加入结果
表达式计算
  • 实体化:中间结果实体化,供下一层运算,磁盘代价高,双缓冲降低磁盘代价
  • 流水线:生产者驱动流水线,需求驱动流水线
最新回复(0)
/jishuQ3P2TZ9gAjidR11OFxTMinbfY5Br_2B3GYzu3Y_2Fw_3D_3D4794877
8 简首页