Word版可编辑-数据库系统设计期末考总结精心整理.docx

数据库系统设计期末考总结 什么是数据库？数据库是被一个系统所使用的所有数据的集合数据库管理员(Database Administrator) 什么是数据库管理系统？（DBMS）数据库管理系统就是帮助存储，管理和使用数据库的程序的集合，对数据库进行统一的管理和控制，以保证数据库的安全性和完整性 DBMS（database management system）数据库管理系统环境组成硬件，软件，数据，程序（procedures），人 数据库系统开发生命周期(database system development lifecycle) 数据库设计的三个主要步骤:概念设计逻辑设计物理设计 C/S vs B/SC/S即Client/Server(客户机/服务器) 结构，通过将任务合理分配到Client端和Server端，降低了系统的通讯开销，需要安装客户端才可进行管理操作。客户端和服务器端的程序不同，用户的程序主要在客户端，服务器端主要提供数据管理、数据共享、数据及系统维护和并发控制等，客户端程序主要完成用户的具体的业务。开发比较容易，操作简便，但应用程序的升级和客户端程序的维护较为困难。三层C/S构架在三层架构中，客户端接受用户的请求，客户端向应用服务提出请求，应用服务从数据库服务中获得数据，应用服务将数据进行计算并将结果提交给客户端，客户端将结果呈现给用户。 两层和三层的区别？两层架构Client side presented two problems preventing true scalability: Fat client, requiring considerable resources on clients computer to run effectively. Significant client side administration overhead. By 1995, three layers proposed, each potentially running on a different platform.客户端提出的两个问题阻止真正的可伸缩性:脂肪”客户端,需要相当大的客户端电脑上的资源有效地运行。重大的客户端管理开销。三层架构Advantages: Thin client, requiring less expensive hardware. Application maintenance centralized. Easier to modify or replace one tier without affecting others. Separating business logic from database functions makes it easier to implement load balancing. Maps quite naturally to Web environment.优点:瘦”客户机,需要更少的昂贵的硬件。应用程序维护集中。容易修改或替换一个层而不影响其他。将业务逻辑与数据库函数分开使其容易实现负载平衡。很自然地映射到Web环境。Three main types of transactions（三种主要类型的事务）: retrieval transactions检索事务update transactions更新交易处理 mixed transactions混合事项B/S即Browser/Server (浏览器/服务器) 结构,用户界面完全通过WWW浏览器实现。客户端基本上没有专门的应用程序，应用程序基本上都在服务器端。由于客户端没有程序，应用程序的升级和维护都可以在服务器端完成，升级维护方便。由于客户端使用浏览器，使得用户界面“丰富多彩”，但数据的打印输出等功能受到了限制。 SQLSQL分类：DDL数据定义语言(CREATE，ALTER，DROP，DECLARE)DML数据操纵语言(SELECT，DELETE，UPDATE，INSERT)DCL数据控制语言(GRANT，REVOKE，COMMITn Query（查询）n Security(安全)n Index（索引）n View（视图） ERDA five-step process for ERD construction :ERD构建五个步骤的过程:n Step1: Represent Entities as Tables（将实体转换成表）n Step2: Determine Relationships（确定关系） In most cases, a record in one table will correspond to multiple records in another table.在大多数情况下,一个表的记录将对应于另一个表中的多条记录。 For many-to-many relationships, a new associative table must be created between two tables. 多对多关系,必须创建一个新的关联表两个表之间的关系。n Step3:List Fields（确定表的属性）n Step4: Identify Keys（确定键，主键和外键）n Step5: Determining Data Types确定数据类型 Primary and foreign keys must match in data type and size. 主键和外键必须匹配的数据类型和大小。2.主键A primary key uniquely identifies each record in a table.主键唯一标示表中的每一条记录。n Uniquen Minimaln Not Nulln Nonupdateable3.外键如果公共关键字在一个关系中是主关键字，那么这个公共关键字被称为另一个关系的外键。4.完整性实体完整性：每个表一定要有一个合法主键。（主键值唯一）参照完整性规则（Referential Integrity）：若属性组F是关系模式R1的主键，同时F也是关系模式R2的外键，则在R2的关系中，F的取值只允许两种可能：空值或等于R1关系中某个主键值。（外键，的值在主键中没有出现）5.范式第一范式：（1NF）强调的是列的原子性，即列不能够再分成其他几列。Definition: A table in which all fields contain a single value.第二范式：（2NF）属性完全依赖于主键Definition: A table in which each non-key field is determined by the whole primary key and not part of the primary key by itself.没有包含在主键中的列必须完全依赖于主键，而不能只依赖于主键的一部分。第三范式：（3NF）属性不依赖于其它非主属性首先是 2NF，另外非主键列必须直接依赖于主键，不能存在传递依赖。即不能存在：非主键列 A 依赖于非主键列 B，非主键列 B 依赖于主键的情况。6.Normalization规范化没有进行规范化的数据存在插入（表没有分开，插入数据是产生异常），更新（数据冗余，更新时产生异常），删除异常（表没有分开，数据间存在依赖关系）同一张表自身设计不合理导致异常规范化的优缺点优点: 消除更新异常 减少数据冗余 解决了数据完整性问题 节省存储空间 缺点: 涉及多表的子查询和表之间的联接，需要更复杂的SQL语句 DBMS的额外工作使应用程序变慢7.关系型数据库优点n 依赖逻辑,而不是物理、相关记录之间的联系n 使用第四代语言(4 gl) n 备抵高度的数据独立性 n Weak Entity（弱实体）一个实体对于另一个实体具有很强的依赖关系，而且该实体主键的一部分或者全部都是从其他强实体中获得，则称该实体为弱实体n Derived attribute（派生属性）Attribute that represents a value that is derivable from value of a related attribute, or set of attributes, not necessarily in the same entity. 属性代表了一个值从一个相关属性中派生出来的,或一组属性的值引出，,不一定在同一个实体。n recursive relationship（递归关系）添加一个外键，使得有一对多的关系，多对多关系n complex relationship(复杂关系)Multiplicity is the number (or range) of possible occurrences of an entity type in an n-ary relationship when other (n-1) values are fixed. n problems in an ER modelOften due to a misinterpretation of the meaning of certain relationships.通常由于特定的意义关系的误解。connection traps. (连接陷阱)俩个主要的连接陷进：扇形陷进和深坑陷进扇形陷进：两个实体有一个一对多的关系，从而扇出第三个实体，两个实体键本该有一个直接关系提供必要信息深坑陷进：一个模型显示实体之间的存在关系,但某些实体出现之间的路径不存在。n Supertype/Subtype Hierarchies（超类和子类）某个实体类型中所有实体同时也是另一个实体类型的实体.此时,我们称前一实体类型是后一实体类型的子类(Subtype),后一实体类型称为超类(Supertype).但是子类有一个很重要的性质:继承性。子类继承其超类上定义的所有属性,其本身还可以包含其他另外的属性.第九章：磁盘的性能指标：磁盘的容量，存取时间，数据传输速度，可靠性磁盘的总容量记录盘面数*每记录盘面的磁道数*每磁道的扇区数*每扇区的字节数扇区：扇区是磁盘寻址的最小单位，其大小通常是512字节数据在磁盘上的定位信息：柱面号，磁头号，扇区号编址方法：柱面从外向内编址（如：0199），磁道按柱面编号（如：0号柱面从上向下编号019，再给1号柱面磁道编号），盘块号（假设每个磁道有17个扇区，0号柱面0号磁道0号扇区的盘块号为0,0号柱面1号磁道0号扇区的盘块号为17）Access time (存取时间) the time it takes from when a read or write request is issued to when data transfer begins. (一个读或写请求发出到数据开始传输的时间) Consists of: Seek time （寻道时间） time it takes to reposition the arm over the correct track. 4 将磁头移到柱面的时间：约230msRotational latency （旋转等待时间） time it takes for the sector to be accessed to appear under the head. 4 约1020msl 总时间：1040msData-transfer rate the rate at which data can be retrieved from or stored to the disk. （从磁盘上读取数据或存储数据到磁盘的时间）Mean time to failure (MTTF) （平均失效时间） the average time the disk is expected to run continuously without any failure.（磁盘无故障连续运行的时间Typically 3 to 5 years）Block a contiguous sequence of sectors from a single track data is transferred between disk and main memory in blocks sizes range from 512 bytes to several kilobytes内存和外存的一次数据交换称为一次I/O操作，每次交换的数据量是一个Block内存中开辟的缓冲区大小至少要等于一个blockBlock的大小通常由DBMS厂商决定廉价磁盘冗余阵列（RAID） Redundant Arrays of Independent Disks 通过冗余提高可靠性是一种利用大量廉价磁盘进行磁盘组织的技术价格上，大量廉价的磁盘比少量昂贵的大磁盘合算得多性能上，使用大量磁盘可以提高数据的并行存取可靠性上，冗余数据可以存放在多个磁盘上，因此一个磁盘的故障不会导致数据丢失冗余（Redundancy）存储额外的信息，以便当磁盘故障时能从中重建磁盘还是内存？l 5-minute rule：如果一个被随机访问的页面的使用频率超过每5分钟一次，那么它应该被驻留在内存l minute rule：如果被顺序访问的页面的使用频率超过每1分钟一次，那么它应该被驻留在内存文件存储：The database is stored as a collection of files. Each file is a sequence of records. A record is a sequence of fields数据库是存储为文件的集合。每个文件都是一个序列的记录。字段的记录是一个序列。第十章：Basic Steps in Query Processing（查询处理的基本步骤）：1. Parsing and translation解析和翻译2. Optimization最优化3. Evaluation评估RDBMS查询处理阶段 ： 1. 查询分析2. 查询检查3. 查询优化 4. 查询执行 选择操作典型实现方法：1. 简单的全表扫描方法 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出 适合小表，不适合大表2. 索引(或散列)扫描方法 适合选择条件中的属性上有索引(例如B+树索引或Hash索引) 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组 排序n 原因n SQL查询可以指定对输出进行排序n 关系运算的某些操作，如连接运算，排序后实现高效n 对于可放进内存的关系，使用如快排序之类的技术。对不能放进内存的关系，使用外排序n 内排序n 当数据集小于可用内存时，采用快速排序算法n 快速排序的思想来源于分治策略。将数据块划分为两个序列，第一个序列的值小于第二个序列，在两个序列中按照递归排序的思想再次进行上述的划分，这样直到没有办法划分为止n 外排序n 创建有序段N路归并n 所有的输入数据最初分成许多有序的归并段文件，然后不断归并成许多更大的归并段文件，直到剩下一个文件为止 Join Operation几种不同的连接算法Nested-loop join（嵌套循环连接）Block nested-loop join（块嵌套循环连接）Indexed nested-loop join（索引嵌套循环连接）Merge-join（合并连接）Hash-join（哈希或散列连接）Choice based on cost estimate（根据成本估算选择连接方式）关系型数据库优点 依赖逻辑,而不是物理、相关记录之间的联系 使用第四代语言(4 gl) 备抵高度的数据独立性 关系数据库系统的查询优化 v 查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好 (1) 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的(3)优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术v RDBMS关系型数据库管理系统（Relational Database Management System）通过某种等价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案 集中式数据库 执行开销主要包括： 磁盘存取块数(I/O代价) 处理机时间(CPU代价) 查询的内存开销 I/O代价是最主要的 分布式数据库 总代价=I/O代价+CPU代价+内存代价通信代价 v 查询优化的总目标： 选择有效的策略 求得给定关系表达式的值 使得查询代价最小(实际上是较小) 实际系统的查询优化步骤：1. 将查询转换成某种内部表示，通常是语法树2. 根据一定的等价变换规则把语法树转换成标准（优化）形式3. 选择低层的操作算法对于语法树中的每一个操作 计算各种执行算法的执行代价 选择代价小的执行算法4. 生成查询计划(查询执行方案) 查询计划是由一系列内部操作组成的。2 代 数 优 化v 代数优化策略：通过对关系代数表达式的等价变换来提高查询效率 v 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的v 两个关系表达式E1和E2是等价的，可记为E1E2 具体方法 笛卡尔积v 查询树的启发式优化v 典型的启发式规则：1. 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条2. 把投影运算和选择运算同时进行如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系3. 把投影同其前或其后的双目运算结合起来4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算5. 找出公共子表达式如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的当查询的是视图时，定义视图的表达式就是公共子表达式的情况6. 在执行连接操作前对关系适当进行预处理 按连接属性排序 在连接属性上建立索引v 索引：v Search Key（检索关键字） - attribute to set of attributes used to look up records in a file.（设置属性用于查找在一个文件中的记录）An index file consists of records (called index entries) of the form（一个索引文件包括记录表格即索引项表）Index files are typically much smaller than the original file (索引文件比源文件小很多)v Two basic kinds of indices（两种基本索引）:Ordered indices（指令索引）: search keys are stored in sorted order（按照顺序搜索密钥存储）Hash indices（哈希索引）: search keys are distributed uniformly across “buckets” using a “hash function”.（检索关键字均匀分布哈希函数的桶中）v clustering index聚簇索引：Primary index: in a sequentially ordered file, the index whose search key specifies the sequential order of the file.初级索引:在一个顺序文件、索引的搜索键指定文件的顺序。Also called clustering index聚簇索引The search key of a primary index is usually but not necessarily the primary key.主索引的检索关键字通常但不一定是主键。v non-clustering index.非聚簇索引Secondary index: an index whose search key specifies an order different from the sequential order of the file. 索引的检索关键字指定一个顺序不同于文件中的顺序。 Also called non-clustering index.非聚簇索引v Dense Index Files（密集索引文件）指向行 Index record appears for every search-key value in the file. 索引记录对应每个检索关键字的值（一一对应）v Sparse Index Files（稀疏索引文件）指向页contains index records for only some search-key values. 只包含一些search-key值索引记录。Applicable when records are sequentially ordered on search-key适用于记录顺序记录检索关键字v Multilevel Indexv 冲突可串行化n 冲突指令当两条指令是不同事务在相同数据项上的操作，并且其中至少有一个是write指令时，则称这两条指令是冲突的如在、情况下，Ii与Ij 是冲突的非冲突指令交换次序不会影响调度的最终结果n 冲突等价如果调度S可以经过一系列非冲突指令交换转换成调度S，则称调度S与S是冲突等价的v B+-treeB+-tree indices are an alternative to indexed-sequential files（B+ 树索引是连续索引文件的替换）v Disadvantage of indexed-sequential files（顺序索引文件的缺点） performance degrades as file grows, since many overflow blocks get created. （随着文件的增多，性能会有所下降，因为创建了许多溢出块） Periodic reorganization of entire file is required.（必须定期重组整个文件）v Advantage of B+-tree index files（B+-tree的优点）: automatically reorganizes itself with small, local, changes, in the face of insertions and deletions.（在进行插入和删除的时候，能自动对备份和更改进行整理） Reorganization of entire file is not required to maintain performance.（对于性能的维护，不需要对整个文件进行重组）v (Minor) disadvantage of B+-trees（缺点）: extra insertion and deletion overhead, space overhead.（额外的插入和删除开销,空间开销。）Advantages of B+-trees outweigh disadvantages，B+-trees are used extensively（B+-trees优点大于缺点，被广泛使用）v A B+-tree is a rooted tree satisfying the following properties（B+-tree具备以下属性）:All paths from root to leaf are of the same length（所有树枝从根到叶的长度相同）Each node that is not a root or a leaf has between n/2 and n children.（每个不是根节点也不是叶子节点的节点有n/2到n个孩子节点）A leaf node has between (n1)/2 and n1 values特殊情况: 如果根不是一片叶子,它至少有两个孩子。如果根是叶(即没有其他节点树),它可以有0到(n - 1)之间的值。B+-Tree Node Structure（节点结构）P1是指针，指向子节点（非叶子结点）或指向记录内容（叶子结点）Ki are the search-key values K1是关键字检索值B+-Tree中的叶子结点 ACID properties of a Transaction（事务的ACID属性）n 原子性（Atomicity）：一个事务中的所有操作要么全部成功，要么全部失败。原子性由恢复机制实现。n 一致性（Consistency）：事务完成后，所有数据处于应有的状态，所有内部结构正确，能够准确反映事务所作的工作。基于隔离性实现。n 隔离性（Isolation）：一个事务不会干扰另一个事务的进程，事务交叉调度执行的结果与串行调度执行的结果是一致的。隔离性由并发控制机制实现。n 持久性（Durability）：事务提交后，对数据库的影响是持久的，即不会因为系统故障影响事务的持久性。持久性由恢复机制实现。 事务调度：p 事务的执行顺序称为一个调度，表示事务的指令在系统中执行的时间顺序p 一组事务的调度必须保证n 包含了所有事务的操作指令n 一个事务中指令的顺序必须保