数据库与数据挖掘1-3

2019/12/291数据库与数据挖掘2019/12/292计算机专业研究生的专业成长1.培养目标（1）具有扎实的基础理论和专业知识课程学习、领域知识、知识面（2）开发能力（熟悉开发工具）（3）科研能力（创新能力）科研成果、论文2019/12/2932.科研方法与步骤（1）确定研究方向（2）收集阅读资料了解发展过程、现状、现有方法（3）确定课题（4）提出解决方案（5）方案实现（6）实验结果分析、性能测试（7）论文写作（8）学术交流2019/12/294本课程的任务1.数据库基础知识的回顾与整理2.数据库系统原理的深化与巩固3.数据仓库4.数据挖掘技术5.上机实验：某种数据挖掘算法的实现课程考核：笔试70%+上机实验30%（答辩）2019/12/295第1章基础知识一、数据库技术的发展历程1964年，第1个DBMS问世，IDS，网状数据库1960’末，推出IMS,层次数据库；1970’，推出SystemR,关系数据库；E.F.Codd:关系数据库之父；1980’,关系数据库典盛时期；1990’，面向对象数据库，特种数据库2019/12/296特种数据库：多媒体数据库，工程数据库，时态数据库，空间数据库，知识库2000年后，Web数据库，XML数据库数据组织的种类：无结构、结构化、半结构化2019/12/297二、DBMS的功能7个功能1.提供用户接口2.查询处理与优化3.数据目录管理4.并发控制5.数据恢复6.完整性约束7.访问控制2019/12/298三、数据模型与数据模式1.数据模型的含义数据结构、操作、完整性约束关系模型、层次模型、网状模型2.数据模式描述具体数据的方式例如：关系模型中二维表外模式、模式、内模式2019/12/299四、数据模型的种类与分析1.概念数据模型面向用户、面向现实世界、与DBMS无关E-R模型2.逻辑数据模型描述数据的逻辑关系关系、层次、网状、面向对象3.物理数据模型面向物理实现2019/12/2910•关系模型数据结构：二维表完整性约束：域完整性、实体完整性、引用完整性操作：бπ×÷∪∩–连接例：÷运算2019/12/2911五、数据库生命周期规划、设计、建立、运行管理和维护、扩充与重构六、数据库语言SQL组成：DDL、QL、DML、DCL•createtable…•createindex…•droptable…•dropindex…•createview…as…2019/12/2912•select…from…where…groupby…orderby…•insertinto…•deletefrom…•update…set…where…•嵌入式SQL——SQL嵌入到程序设计语言中•动态SQL——支持动态查询，执行的SQL语句不是事先确定。2019/12/2913•SQL的存储过程：将常用的访问数据库的程序，定义一个过程，经编译后，存储在数据库中，供用户调用。格式：定义过程：execsqlcreateprocedure过程名(in输入参数，out输出参数)beginatomic//atomic表示执行保持原子性………end;execsql调用过程：call过程名(……);NoSQL数据库2019/12/2914七、数据库系统结构4种1.单机数据库系统2.C/S、B/S数据库系统3.逻辑上集中、物理上分布的数据库系统4.逻辑上分布、物理上分布的数据库系统2019/12/2915八、DBMS中的事务DBMS的一个执行单位ACID准则：A----原子性C----一致性I----隔离性（多个事务并发执行，应像各个事务独立执行一样D----持久性2019/12/2916九、数据目录是一组关于数据的数据，也叫元数据。数据目录中的数据分为两类：1.来自基表、视图和索引的定义，相对稳定；2.来自数据库状态的统计，例如：元组个数，不同属性值的个数。2019/12/2917十、数据库文件的组织1.顺序文件（堆文件）2.直接文件（Hash文件）3.索引文件静态索引---表组织，不插入/删除动态索引---B+树，插入、删除主索引、次索引倒排文件---所有属性都建立索引簇集索引---关键字相同的记录放在连续物理块稠密索引---每个键有一个索引项非稠密索引2019/12/2918•十一、存储系统的发展1.三级存储体系Cache----内存----外存2.RAID磁盘阵列3.存储器网络通过网络共享磁盘数据2019/12/2919第2章查询处理与优化一、基本概念1.查询是数据库中最基本、最常用、最复杂的操作2.查询一般以查询语言表示3.查询优化是查询处理中的重要环节。二、查询优化的方法1.规则优化2.代价估算优化2019/12/29201.规则优化（1）代数优化——对查询语句进行等效变换（2）物理优化——选择合理的存取策略2.代价估算优化先预估代价，再从中选优。三、代数优化(1)先做选择、投影，后做连接(2)先做小关系连接，再做大关系连接(3)提取查询中的公共表达式2019/12/2921•举例：设有关系S（供应商），P（零件），SP（供应关系），关系模式如下：S(SNUM,SNAME,CITY)P(PNUM,PNAME,WEIGHT,SIZE)SP(SNUM,PNUM,DEPT,QUAN)设有查询：SELECTSNAMEFROMS,P,SPWHERES.SNUM=SP.SNUMANDSP.PNUM=P.PNUMANDS.CITY=‘NANJING’ANDP.PNAME=‘BOLT’ANDSP.QUAN100002019/12/2922画查询树。处理过程：（1）select子句对应投影操作，from子句对应笛卡尔乘积，where子句对应选择操作，生成原始查询树。（2）应用变换规则，尽可能将选择条件移向树叶方向。（3）按照小关系先做的原则，重新安排连接（笛卡尔乘积）的次序。（4）如果笛卡尔乘积后还需按连接条件进行选择操作，则将两者组合成连接操作。（5）对每个叶结点加必要的投影操作，以消除对查询无用的属性。2019/12/2923四、物理优化依赖于存取路径的规则优化顺序存取，索引存取，散列存取1.选择操作的实现与优化（1）对于小关系，不必考虑其他存取路径，直接用顺序扫描。（2）如果无索引或散列可用，则用顺序扫描。（3）对于主键的等值查询，最多只有一个元组满足条件，应优先采用主键上的索引或散列。（4）对于非主键的等值查询，如果选中的元组数较多，则用簇集索引或顺序扫描，否则可用一般次索引（5）对于范围查询，若中选的元组数在关系中所占比例较大，且无簇集索引，则采用顺序扫描。（6）对于用and连接的合取选择条件，若有相应的多属性索引，则优先使用多属性索引。……(7)对于用or连接的析取选择条件，按其中各个条件分别选出，然后求这些元组集的并。2019/12/29242.连接操作的实现与优化有4种实现方法（1）嵌套循环法（2）利用索引或散列寻找匹配元组法内关系上建立索引或散列（3）排序归并法（4）散列连接法连接属性R.A和S.A具有相同的域，用A、B作为散列键，用相同的散列函数，把R、S散列到同一散列文件中。符合连接条件的R、S的元组必然位于同一桶中。2019/12/2925优化规则：（1）如果两个关系都已按连接属性排序，则优先用排序归并法。（2）如果两个关系中有一个关系在连接属性上有索引（特别是簇集索引）或散列，则可令另一关系为外关系，顺序扫描，利用内关系上的索引或散列寻找其匹配元组，以替代多遍扫描。（3）如果上述条件不具备，且两个关系都比较小，可以应用嵌套循环法。（4）如果上述都不适合，则用散列连接法。2019/12/29263.投影操作的实现投影操作一般与选择、连接操作同时进行，不需要附加的I/O开销。主要任务是：消除重复元组，比较费时。方法：（1）排序：将投影结果按属性排序，使重复元组连续存放，以便发现和消除。（2）散列：将投影结果按属性散列成一个文件，当一个元组散列到一个桶中时，可以检查是否与桶中已有元组重复。2019/12/29274.集合操作的实现R∪S,R∩S,R–S关键是发现R、S的共同元组。方法：（1）排序（2）散列2019/12/2928五、代价估算优化（适用于编译型DBMS）1.查询代价的组成I/O代价、CPU代价、通信代价I/O代价是主要的。I/O代价=I/O次数×D，I/O代价I/O次数2.选择操作的代价估算按照不同的存取策略估算。(1)顺序扫描•若最多选择一个元组：C=0.5b，b为关系的物理块•若选取多个元组：C=b2019/12/2929(2)利用主键上的索引或散列等值查询索引：C=L+1;L为索引级数散列：C=1(3)利用非主键的无序索引进行等值查询可能有多个元组满足条件。假设属性值均匀分布，满足条件的元组数s=n/N,n是元组总数，N是不同取值的个数代价估算：C=L+s2019/12/2930（4）利用簇集索引进行等值查询C=L+s/p（5）利用簇集索引进行范围查询假设有一半元组符合条件C=L+b/23.连接操作的代价估算4种实现方法（1）嵌套循环法：要考虑内存缓冲的大小（块数）（2）利用索引或散列寻找匹配元组法（3）排序归并法（4）散列连接法2019/12/2931第3章事务管理一、基本概念1.事务管理恢复----保证事务在故障时满足ACID准则并发控制----保证事务在并发执行时满足ACID准则2.故障的种类事务内部故障----程序本身造成系统故障----如：CPU故障、OS故障介质故障计算机病毒2019/12/29323.恢复技术(1)数据转储(2)运行记录+后备复本(3)多复本技术运行记录-----日志文件日志文件是用来记录事务对数据库更新操作的文件。内容包括：事务标识、操作类型、操作对象、更新前数据的旧值（前像）、更新后数据的新值（后像）2019/12/2933日志文件的登记原则：•按事务执行时间顺序•先写日志文件，后写数据库二、恢复操作与恢复策略1.操作：撤销事务（undo）----使用前像重做事务（redo）----使用后像2.恢复步骤：（1）事务故障恢复采用undo2019/12/2934•反向扫描日志文件，查找更新操作•对更新操作执行逆操作•重复执行，直到此事务开始标识（2）系统故障恢复根据事务状态采取恢复策略（undo/redo）恢复步骤：•正向扫描日志文件，查找已提交的事务和未提交的事务•对于已提交的事务redo•对于未提交的事务undo2019/12/2935（3）介质故障恢复数据和日志文件均被破坏------只有重装数据库，重做已完成的事务，用复本恢复。三、并发控制引论1.什么是并发？交叉并发----单CPU同时并发----多CPU2.并发执行引起的问题读写冲突、写写冲突数据不一致举例：2019/12/29363.并发控制的任务避免访问冲突引起数据不一致。4.并发控制的正确性原则若某个调度是可串行化的，则是正确的5.什么是调度？对n个事务的所有操作顺序的一个安排。例如：6.调度的等价性•目标等价：两个调度读出的数据一样，数据库的最终状态一样。•冲突等价：通过调换不冲突的操作，得到的新调度。)()()()()(13221xRyRxWxRxRS2019/12/2937冲突等价目标等价目标等价冲突等价7.可串行化调度若某个调度与一个串行调度等价，则称此调度可串行化。•目标可串行化•冲突可串行化例：S为冲突可串行化。)()()()(2132yWyRxWxRS不一定)()()()(3221xWyWxRyR2019/12/2938•目标可串行化不一定是冲突可串行化。例：目标等价于：它是目标可串行化，但不是冲突可串行化。8.可串行化调度判断算法前趋图法画前趋图，若无回路，则可串行化。举例：9.并发控制的基本方法加锁，基于时间标记的方法，乐观并发控制)()()()(3121xWxWxWxRS)()()()(3211xWxWxWxRS2019/12/2939四、用加锁方法实现并发控制1.X锁，排斥锁•在数据对象进行读写之前，要加锁。•获得X锁后，才能进行