中级数据库工程师重要知识点.doc

重要知识点1. 数据库设计数据库是存储在外出上的有组织的、可共享的数据的集合。数据库设计分为需求分析、概念设计、逻辑设计、物理设计几个阶段需求分析：数据流图（DFD）、数据字典概念设计：E-R图、UML图，描述实体及其联系逻辑设计：设计关系模式及相关视图物理设计：设计数据的物理组织，如索引数据字典：数据收集和分析获得的主要成果，包括数据项、数据结构、数据流、数据存储、处理过程域：一组值的集合，例：D1姓名：A,B,C D2性别：男，女笛卡尔积：所有可能组合的集合，例： D1*D2=(A,男),(B,男),(C,男),(A,女),(B,女),(C,女)关系是一组域笛卡尔积的一个子集，一行对应一个元组，一列对应一个域主属性：任何一个候选码中的属性非主属性：不属于任何候选码的属性关系中没一个属性都是不可分解的，没有完全相同得行或列，行列顺序无关紧要复合属性：可细分的属性，如通信地址分为邮编、省、市、街道等多值属性：一个属性对应多个值派生属性：可以通过其他属性计算获得的属性，如年龄可以通过出生日期计算得到。生命周期：需求分析、概念结构设计、逻辑结构设计、物理结构设计、数据库实施、运行维护数据库性能的两个效率：存储效率、存取效率衡量数据库的性能指标：是否冗余、插入异常、删除异常、更新异常或潜在的不一致性数据依赖：X-Y：对于X，Y中存在唯一的值与之对应函数依赖的公理系统：设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则如下：Armstrong公理系统：自反律：YX,则XY增广律：XY，ZW，则XWYZ传递律：XY，YZ，则XZ三条引理：合并律：XY，XZ，则XYZ伪传递律：XY，WYZ，则WXZ分解律：XY，ZY，则XZ例题：给定关系模式R(U，F)，其中U为关系R属性集，F是U上的一组函数依赖，若XY，(42)是错误的，因为该函数依赖不蕴涵在F中。A.YZ成立，则XZBXZ成立，则XYZCZU成立，则XYZDWYZ成立，则XWZ答案：C解析：本题考查的是关系数据库理论方面的基础知识。Armstrong公理系统推导出下面三条推理规则：传递规则(选项A)：若AY，YZ成立，则XZ为F所蕴涵。 合并规则(选项B)：若XY，XZ成立，则XYZ为F所蕴涵。伪传递规则(选项D)：若XY，WYZ成立，则XWZ为F所蕴涵。例题：若关系模式RA，B，C，AB，BC)，则将R分解为R1(A，B)和R2(B，C)，则该分解(51)。A满足无损连接，但不保持函数依赖B不满足无损连接，但保持函数依赖C既不满足无损连接，又不保持函数依赖D既满足无损连接，又保持函数依赖参考答案D分析本题考查对模式分解的掌握。根据无损连接分解判定定理，有R1R2R2R1，即BC成立，故分解具有无损连接性；又R的函数依赖集F=AB，BC在R1，R2上的投影分别为F1=AB)，F2=BC，即有F1F2=F，从而(F1F2)+=F+，根据定义，分解保持函数依赖例题：设关系模式R，其中U=A, B, C, D, E，FABC，CD，BCE，EA，则分解=R1（ABCE），R2（CD）满足 （43） 。 A具有无损连接性、保持函数依赖 B不具有无损连接性、保持函数依赖 C具有无损连接性、不保持函数依赖 D不具有无损连接性、不保持函数依赖解析：无损链接判断：R1R2=C，R2-R1=D，C-D 蕴涵于F，故无损连接函数依赖判断：R1在F上投影F1：ABC，BCE， EA R2在F上投影F2：C-D F1并F2=F，故函数依赖答案：选A。对象关系模型与关系模型的区别：对象关系模型支持关系嵌套。标准建模语言UML五类图（共10种图）第一类是用例图，从用户角度描述系统功能，并指出各功能的操作者。第二类是静态图 (Static diagram)，包括类图、对象图和包图。类图描述系统中类的静态结构。类图描述的是一种静态关系，在系统的整个生命周期都是有效的。对象图是类图的实例，几乎使用与类图完全相同的标识。他们的不同点在于对象图显示类的多个对象实例，而不是实际的类。一个对象图是类图的一个实例。由于对象存在生命周期，因此对象图只能在系统某一时间段存在。包图由包或类组成，表示包与包之间的关系。包图用于描述系统的分层结构。第三类是行为图（Behavior diagram），包括：状态图、活动图、顺序图和协作图。描述系统的动态模型和组成对象间的交互关系。状态图描述类的对象所有可能的状态以及事件发生时状态的转移条件。通常，状态图是对类图的补充。在实用上并不需要为所有的类画状态图，仅为那些有多个状态其行为受外界环境的影响并且发生改变的类画状态图。活动图描述满足用例要求所要进行的活动以及活动间的约束关系，有利于识别并行活动。活动图是一种特殊的状态图，它对于系统的功能建模特别重要，强调对象间的控制流程。顺序图展现了一组对象和由这组对象收发的消息，用于按时间顺序对控制流建模。用顺序图说明系统的动态视图。协作图展现了一组对象，这组对象间的连接以及这组对象收发的消息。它强调收发消息的对象的结构组织，按组织结构对控制流建模。顺序图和协作图都是交互图，顺序图和协作图可以相互转换。第四类是交互图（Interactive diagram），描述对象间的交互关系。其中顺序图显示对象之间的动态合作关系，它强调对象之间消息发送的顺序，同时显示对象之间的交互；合作图描述对象间的协作关系，合作图跟顺序图相似，显示对象间的动态合作关系。除显示信息交换外，合作图还显示对象以及它们之间的关系。如果强调时间和顺序，则使用顺序图；如果强调上下级关系，则选择合作图。这两种图合称为交互图。第五类是实现图 ( Implementation diagram )。构件图描述代码部件的物理结构及各部件之间的依赖关系。一个部件可能是一个资源代码部件、一个二进制部件或一个可执行部件。它包含逻辑类或实现类的有关信息。部件图有助于分析和理解部件之间的相互影响程度。配置图定义系统中软硬件的物理体系结构。它可以显示实际的计算机和设备（用节点表示）以及它们之间的连接关系，也可显示连接的类型及部件之间的依赖性。在节点内部，放置可执行部件和对象以显示节点跟可执行软件单元的对应关系。从应用的角度看，当采用面向对象技术设计系统时，首先是描述需求；其次根据需求建立系统的静态模型，以构造系统的结构；第三步是描述系统的行为。其中在第一步与第二步中所建立的模型都是静态的，包括用例图、类图（包含包）、对象图、组件图和配置图等五个图形，是标准建模语言UML的静态建模机制。其中第三步中所建立的模型或者可以执行，或者表示执行时的时序状态或交互关系。它包括状态图、活动图、顺序图和合作图等四个图形，是标准建模语言UML的动态建模机制。因此，标准建模语言UML的主要内容也可以归纳为静态建模机制和动态建模机制两大类。关系代数：集合运算、关系运算、算术比较、逻辑运算集合运算：并() 、交、 差(-)、笛卡尔积()专门关系运算：投影()、选择()、连接、自然连接、除 （1）投影：对关系进行垂直分割，消去某些列，并重新安排列的顺序，再删去重复元组。（2）选择：从关系中选择满足条件的元组，条件可用命题公式F表示，F中的运算对象是常数（用引号括起来）或元组分量（属性名或列的序号）。运算符有算术比较运算符（，）和逻辑运算符（，）。为选择运算符，F(R)表示从R中挑选满足公式F的元组所构成的集合。（3）连接连接，从R、S的笛卡尔积中选取属性间满足一定条件的元组 计算过程：（1）计算R*S (2) 找出属性相等的元组等值连接，当为=时的连接自然连接，要求两个关系中进行比较的分量必须是相同得属性组，并将重复属性列去掉 R S 计算过程：（1）计算R*S (2) 找出公共属性相等的元组 （3）去掉S中公共属性列左外连接：取出左侧关系中，所有与右侧关系中任一元组都不匹配的元组，用NULL填充来自右侧关系的属性右外连接：取出右侧关系中，所有与左侧关系中任一元组都不匹配的元组，用NULL填充来自左侧关系的属性等值连接与自然连接的异同：自然连接一定是等值连接，反之不成立；等值连接要求相同得分量，但不一定是公共属性自然连接要求相等的分量必须是公共属性等值连接不做投影运算，自然连接要把重复的属性列删除。（4） 除：R如果能被S除，则一是R中属性必须包含S中属性；二是R中有些属性不在S中R/S结果：一个关系，属性由R中不在S中属性构成，元组则是S中所有元组在R中对应值相等的元组R/S含义：在R中找出包含所有S中属性的元组，且结果为R属性去掉S属性，并去掉重复元组。1.1 关系模型的数据约束实体完整性约束：关键属性不能为空参照完整性约束，F.NO是R的外关键字，则R中的NO在F中：1或取NULL；2或等于R.NO中某值。不能引用一个不存在的实体用户定义完整性：值的类型，宽度等例题：某论坛数据库中，有主题表保存用户发布的主题，有“回复主题表”保存对主题的回复贴子，关系如下： 主题（主题编号，主题标题，主题内容，发布时间） 回复主题表（回复主题编号，主题编号，回复主题标题.） 主题编号 外键 主题（主题编号）问：能够直接用delete 主题 where 主题编号=T1201删除主题中的某一元组吗？答：不能，会违反参照完整性约束，删除主题可能存在回复主题解决方法：（1）创建触发器，在删除主题时，删除其对应的回复主题 （2）在定义回复主题表时，指定级联删除。即在定义主题编号属性的外键约束后加上 on delete cascade1.2 三级模式/两级映像结构外模式（子模式）：用户与数据库的接口，用户能够看到和使用的局部数据的逻辑结构和特征描述，逻辑关系上看，是概念模式的子集。模式（概念模式）：既不涉及物理存储细节和硬件环境，也与具体的应用程序及程序语言无关，一个数据库只有一个概念模式；内模式（存储模式）：数据库中数据物理结构和存储方式的描述，一个数据只有一个内模式。三级结构通过映像来联系和转化数据独立性：逻辑独立性：模式变化，无需改变外模式或应用程序 物理独立性：不会因为内模式改变而导致模式改变1.3 范式：主属性：包含在任何一个候选码中的属性1NF：每个属性都是原子的，不可再分，而不能是集合，数组，记录等非原子数据项。2NF：每一个非主属性都完全依赖于码3NF：每一个非主属性，既不部分依赖于码，也不传递依赖于码BCNF：关系模式3NF，若每一个决定因素都含有码，则 所有非主属性对码都是完全函数依赖 所有主属性对每一个不包含它的码都是完全函数依赖 没有任何属性完全函数依赖于非码的任何一组属性3NF的不彻底性表现在可能存在主属性对码的部分依赖或传递依赖BCNF解决了插入异常、删除异常，但仍可能存在冗余4NF：解决多值依赖1.4 视图视图是从一个或多个表或视图中导出的表，其结构和数据建立在对表的查询基础上。视图不是真实存在的基础表，而是一个虚拟表。视图的创建：CREATE VIEW 视图名 （列名） AS SELECT 查询子句 WITH CHECK OPTION 执行UPDATE、INSERT、DELECT操作时保证操作行满足视图定义中的谓词条件1.5 数据库设计概念结构设计对现实事物抽象的三种方法：分类、聚集、概括 分类：按照固有的特征和行为，定义一种类型，如学生类、教师类 聚集：定义某一类型具有的属性 概括：由一种已知类型定义新的类型，如由学生类型定义研究生类型逻辑结构设计的主要任务： 确定数据模型、将E-R图转换为指定的数据模型、确定完整性约束、确定用户视图1.5.1 弱实体对另一些实体具有很强的依赖性关系，即一个实体的存在必须以另一个实体为前提如：职工与家属的联系，家属总是属于职工的，家属就是弱实体弱实体用双线矩形框表示1.5.2 超类-子类特殊化：一个实体集可以分为几个子实体，如学生实体集可以分为本科生、研究生、博士生等子集，这种由普遍到特殊的过程称特殊化；普遍化：将几个具有共同特性的实体集概括成一个更普遍实体集的过程在扩充E-R模型中，子类继承超类的所有属性和联系，但子类还有自己特殊的属性和联系。子类用双竖边矩形框表示超类、子类的关系一般用特殊化圆圈和连线的方式表示，超类到圆圈有一条连线，连线为双线则表示全特殊化，连线为单线表示部分特殊化。1.6 SQL语句结构化查询语言包含6个部分：一：数据查询语言（DQL）：其语句，也称为“数据检索语句”，用以从表中获得数据，确定数据怎样在应用程序给出。保留字SELECT是DQL（也是所有SQL）用得最多的动词，其他DQL常用的保留字有WHERE，ORDER BY，GROUP BY和HANG。这些DQL保留字常与其他类型的SQL语句一起使用。二：数据操作语言（DML）:其语句包括动词INSERT，UPDATE和DELETE。它们分别用于添加，修改和删除表中的行。也称为动作查询语言。三：事务处理语言（TPL）：它的语句能确保被DML语句影响的表的所有行及时得以更新。TPL语句包括BEGIN TRANSACTION，COMMIT和ROLLBACK。四：数据控制语言（DCL）：它的语句通过GRANT或REVOKE获得许可，确定单个用户和用户组对数据库对象的访问。某些RDBMS可用GRANT或REVOKE控制对表单个列的访问。五：数据定义语言（DDL）：其语句包括动词CREATE和DROP。在数据库中创建新表或删除表（CREAT TABLE 或 DROP TABLE）；为表加入索引等。DDL包括许多与人数据库目录中获得数据有关的保留字。它也是动作查询的一部分。六：指针控制语言（CCL）：它的语句，像DECLARE CURSOR，FETCH INTO和UPDATE WHERE CURRENT用于对一个或多个表单独行的操作。定义用关键词：PRIMARY KEY 主键必须包含唯一的值。主键列不能包含 NULL 值。每个表都应该有一个主键，并且每个表只能有一个主键。(1)Id_P int NOT NULL PRIMARY KEY,(2)Id_P int NOT NULL, PRIMARY KEY (Id_P) FOREIGN KEY 指向另一个表中的 PRIMARY KEY。(1) Id_P int FOREIGN KEY REFERENCES Persons(Id_P) 两种写法，注意(2)Id_P int, FOREIGN KEY (Id_P) REFERENCES Persons(Id_P)CHECK 限定约束 CHECK (Id_P0)Id_P int NOT NULL CHECK (Id_P0),INDEX 索引create index 索引名 on 表名（字段名 asc/desc）drop index 表名.索引名例：CREATE INDEX PersonIndex ON Person (LastName DESC) 降序索引 注意DESC 位置在括号里CREATE INDEX PersonIndex ON Person (LastName, FirstName) 多列索引 视图：Create view 视图名（属性列表） as select .授权Grant all privileges on table T_S to U with grant option触发器 triggercreate trigger orderinsert after insert on ordersas if (select status from goods,inserted where =inserted.goodsname)=1begin print the goods is being processed print the order cannot be committed rollback transaction -回滚避免加入endCreate trigger 触发器 After insert on 表名For each rowWhen 表明.id5Begin atomicUpdate 表名.级别=1;COMMIT WORK ;ENDALTER 添加列：添加列 ALTER TABLE ADD COLUMN 列名 类型 ALTER TABLE 账户 ADD 账户标识 INT DEFAULT 0 ALTER TABLE 账户 ADD(账户标识 INT DEFAULT 0, 账户名称 VARCHAR(8) 多个列删除列：ALTER TABLE table_name DROP COLUMN column_name 有COLUMN ALTER TABLE 账户 DROP COLUMN 账户标识 修改值：ALTER TABLE SET 账户标识=0 有 = 删除表：DROP TABLE 表名 CASCADE|RESTRICT CASCADE：将表及所涉对象一起删除，默认 RESTRICT：当有视图或约束条件涉及要删除的表，则禁止DBMS执行此命令设置默认值： ALTER TABLE 表名 ALTER COLUMN 列名 set default 默认; ALTER COLUMN 列名 drop default;查询用关键词：WHERE子句各种条件运算符：比较运算符（大小比较）：；、=、=、；、=、；、！；、！=10 AND age=302、列表运算符例：country IN (Germany,China)3、模式匹配符例：常用于模糊查找，%：可匹配任意类型和长度的字符，如果是中文，请使用两个百分号即%。_：匹配单个任意字符，它常用来限制表达式的字符长度。：指定一个字符、字符串或范围，要求所匹配对象为它们中的任一个。：其取值也 相同，但它要求所匹配对象为指定字符以外的任一个字符。ORDER BY 查询结果排序,ASC升序，为默认值，DESC为降序。DISTINCT 删除重复行TOP n PERCENT 限制返回的数据行数，TOP n说明返回n行，而TOP n PERCENT时，说明n是表示一百分数，指定返回的行数等于总行数的百分之几。TOP命令仅针对SQL Server系列数据库，并不支持Oracle数据库。GROUP BY 语句用于结合合计函数，根据一个或多个列对结果集进行分组。SELECT Customer,SUM(OrderPrice) FROM Orders GROUP BY CustomerHAVING 子句在 SQL 中增加 HAVING 子句原因是，WHERE 关键字无法与合计函数一起使用。SELECT Customer,SUM(OrderPrice) FROM OrdersGROUP BY CustomerHAVING SUM(OrderPrice) all(select 分数 from 成绩)（4） EXISTS 查询结果不返回数据，只产生逻辑真假 Where exists(select .)注意事项：（1）group by 列名 having 条件 ORDER BY 列名 （2）字符串两边用 单引号 （3）空值：列名 IS NULL 不能用列名=NULL（4）匹配：%匹配多个字符，_匹配一个字符 例：查找第二个字符为F的姓名 WHERE 姓名 LIKE _F%（5）COUNT (DISTINCT *) 用DISTINCT会在统计时删除重复性（6）ANY ALL WHERE 年龄ANY（SELECT 年龄 from 学生 where 院系计算机）（7） 不等于 ！= 大于等于 =（8） 外键 foreign key (id) references R(id) 有括号（9） SQL2不支持直接修改属性名、属性类型，因此必须先删除再添加（10） 可增加或减少列长度，但不能小于原有数据长度（11） NULL - NOT NULL时，要先处理该记录使非NULL（12） Select 学号，2004-年龄 as 出生年份 包含计算（13） 左右连接：from 学生 left join 选课 on . 会把没选课的学生信息列出来2. 并发调度事务：事务的4个特性：原了性(Atomicity)、一致性(Consistency)、隔离性(Isolation)和持久性(Durability)。原子性：事务的所有操作在数据库中要么全做要么全都不做。一致性： 一个事务独立执行的结果，将保持数据的一致性，即数据不会因为事务的执行而遭受破坏。 一致性可以由DBMS的完整性约束机制来自动完成，而复杂的事务则由应用程序来完成。隔离性：一个事务的执行不能被其他事务干扰。持久性：一个事务一旦提交，它对数据库的改变必须是永久的，即便系统出现故障时也是如此。事务执行状态：5种 (1)活动状态：事务的初始状态，事务执行时处于这个状态。 (2)部分提交状态：当操作序列的最后一条语句自动执行后，事务处于部分提交状态。这时，事务虽然已经完全执行，但由于实际输出可能还临时驻留在内存中，在事务成功完成前仍有可能出现硬件故障，事务仍有可能不得不中止。因此，部分提交状态并：不等于事务成功执行。 (3)失败状态：由于硬件或逻辑等错误，使得事务不能继续正常执行，事务就进入了失败状态，处于失败状态的事务必须回滚(ROLLBACK)。这样，事务就进入了中止状态。 (4)中止状态：事务回滚并且数据库恢复到事务开始执行前的状态。(5)提交状态：当事务成功完成后，称事务处于提交状态。只有事务处于提交状态后，才能事务已经提交。并发一致性问题：丢失的修改、不可重复读、读脏数据、幻影读（往往与不可重复读归为一类）。丢失的修改:两个事务T1和T2读入同一数据并修改，T2提交的结果破坏了T1提交的结果，导致T1的修改被丢失。不可重复读:是指事务T1读取数据后，事务T2执行更新操作，使T1无法再现前一次读取结果读脏数据:是指事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤消，这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致，则T2读到的数据就为脏数据，即不正确的数据。幻影读是指：事务1按一定条件从数据库中读取某些数据记录后，事务2插入了一些符合事务1检索条件的新记录，当事务1再次按相同条件读取数据时，发现多了一些记录。并发一致性问题的解决办法2.1 封锁（Locking）所谓封锁就是事务T在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。基本的封锁类型有两种：排它锁（Exclusive locks 简记为X锁）和共享锁（Share locks 简记为S锁）。 排它锁又称为写锁。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁。这就保证了其它事务在T释放A上的锁之前不能再读取和修改A。共享锁又称为读锁。若事务T对数据对象A加上S锁，则其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。这就保证了其它事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。注意：加X锁后，其它事务不能再加任何锁 加S锁后，其它事务可以加S锁，不能加X锁2.2 封锁协议对数据对象加锁时，需要约定一些规则，例如应何时申请X锁或S锁、持锁时间、何时释放等。三级封锁协议:不同程度上解决了丢失的修改、不可重复读和读脏数据等不一致性问题1级封锁协议 :事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括正常结束 （COMMIT）和非正常结束（ROLLBACK）。1级封锁协议可防止丢失修改，并保证事务T是可恢复的。如果仅仅是读数据不对其进行修改是不需要加锁的，所以它不能保证可重复读和不读脏数据。2级封锁协议 :1级封锁协议加上事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。2级封锁协议除防止了丢失修改，还可进一步防止读脏数据。3级封锁协议 :1级封锁协议加上事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放。3级封锁协议除防止了丢失修改和不读脏数据外，还进一步防止了不可重复读。两段锁协议：对任何数据读写之前必须对数据加锁，在释放一个锁之后，事务不再申请和获得任务其他锁。 缩短了持锁时间，提高了并发性，同时解决了数据的不一致性。前段申请，后段释放。注意：一级封锁协议可防止丢失修改，不能保证可重复读和不读脏数据二级封锁协议可防止丢失修改，防止读脏数据，不能保证可重复读三级封锁协议可防止丢失修改，防止读脏数据，保证可重复读两段锁协议保证事务可串行化，反之不成立。2.3 事务隔离级别尽管数据库理论对并发一致性问题提供了完善的解决机制，但让程序员自己去控制如何加锁以及加锁、解锁的时机显然是很困难的事情。索性绝大多数数据库以及开发工具都提供了事务隔离级别，让用户以一种更轻松的方式处理并发一致性问题。 常见的事务隔离级别包括：ReadUnCommitted、ReadCommitted、RepeatableRead和Serializable四种。 不同的隔离级别下对数据库的访问方式以及数据库的返回结果有可能是不同的。2.3.1 ReadUnCommitted与ReadCommittedReadUnCommitted是最低的隔离级别，这个级别的隔离允许读入别人尚未提交的脏数据，除此之外，在这种事务隔离级别下还存在不可重复读的问题。ReadCommitted是许多数据库的缺省级别，这个隔离级别上，不会出现读取未提交的数据问题，但仍然无法避免不可重复读（包括幻影读）的问题。当你的系统对并发控制的要求非常严格时，这种默认的隔离级别可能无法提供数据有效的保护，但对于决大多数应用来讲，这种隔离级别就够用了。RepeatableRead是指可重复读，它的隔离级别要比ReadCommitted级别高。它允许某事务执行重复读时数据保持不变，但是仍然无法解决幻影读的问题。Serializable隔离级别是最高的事务隔离级别，在此隔离级别下，不会出现读脏数据、不可重复读和幻影读的问题多个事务的并发调度的可串行化调度多个事务的并发执行是正确的，当且仅当并发调度的结果与某一次串行的执行这些事务的结果是相同得。不可串行化调度的原因：脏数据，一个事务的数据覆盖了另一事务的数据等。3. 面向对象OOA 面向对象分析，抽取和整理用户需求并建立问题域精确模型的过程OOD 面向对象设计，中间过渡环节，主要作用是对OOA分析的结果作进一步的规范化整理，以便能够被OOP直接接受。在OOD的设计过程中，主要工作：对象定义规格的求精过程、数据模型和数据库设计OOP 面向对象编程OOA三步：用例建模：例图use-case modeling use-case diagram 决定了如何由产品得到各项计算结果类建模： class modeling 决定了类及其属性，然后确定类之间的关系和交互动态建模：状态图 dynamic modeling state diagram 决定了类或每个子类的行为4. 程序设计语言4.1 低级语言与高级语言低级语言：机器语言（0,1）、汇编语言高级语言：各类面向应用的程序语言，不依赖于机器硬件。4.2 编译程序和解释程序语言处理程序：属系统软件，把高级语言或汇编语言编写的程序翻译成某种机器语言程序。分为汇编程序、编译程序和解释程序三种。汇编程序：将汇编语言编写的源程序翻译成机器语言；编译程序：将源程序翻译成目标程序（汇编语言程序或机器语言程序）解释程序：或者直接解释执行源程序，或者将源程序翻译成某种中间表示形式后再执行根本区别： 在编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不参与目标程序的执行过程； 在解释方式下，解释程序和源程序都要参与到程序的运行过程中，运行程序的控制权在解释程序； 解释器翻译源程序时不需要生成独立的目标程序；编译器则需将源程序翻译成独立的目标程序。4.3 编译程序工作过程可分6个阶段：可分为前端、后端两部分，前端从词法分析到中间代码生成；后端从中间代码优化到目标代码生成优化等。这样以中间代码为分水岭，把编译过程分为与机器无关部分，与机器相关部分。词法分析：识别“单词”符号，标识符、关键字、常数、运算符、分隔符语法分析：根据语言的语法规则，将单词符号序列分解成语言单位，如表达式、语句、程序等语义分析：检查源程序是否存在语义错误，并收集类型信息供后面代码生成阶段使用中间代码生成阶段：中间代码是简单且含义明确的记号系统，共同特征是与机器无关 常用中间代码是三地址码，用四元式实现，例：（*, id3,t1,t2）代码优化阶段：在中间代码生成阶段或目标代码生成阶段进行，一般建立在对程序控制流、数据流分析的基础上，与具体机器无关。目标代码生成阶段：把中间代码变换成特定机器上的绝对指令代码、可重定位指令代码或汇编指令代码。与具体机器密切相关出错处理： （1）静态错误 编译时发现的错误，分语法错误和语义错误 语法错误：单词拼写错误、标点错、表达式缺少操作数、括号不匹配等 语义错误：运算符与运算对象类型不匹配等。 （2）动态错误：发生在程序运行时的逻辑错误，如除0 编译时发现错误后，应采取适当策略跳过错误，使分析继续进行，以便在一次编译过程中找出更多错误。4.4 正规式、正规集 正规集就是正规式中字符串任意组合形成的字符串集合。Ab 符号串ab构成的集合A|b 符号串a、b构成的集合A* 由0个或多个a构成的集合（A|b）* 所有由字符a和b构成的串的集合，包括空串e4.5 解释程序与编译程序的主要区别：执行执行源程序或源程序的内部形式，因此不产生目标程序效率低：反复扫描源程序，类型检查、重新存储分配等灵活性：运行中修改可移植性：只需对解释器进行重新编译，就可解释器运行在不同环境中4.6 函数函数定义：包括函数首部和函数体函数首部说明了函数返回值的数据类型、函数名、所需参数及类型函数体描述函数实现的功能形参指明了所需参数的个数、类型和顺序函数调用的形式：函数名（实参表）4.7 形参、实参、传值调用、引用调用形参出现在函数定义中，在整个函数体内都可以使用，离开该函数则不能使用。实参出现在主调函数中，进入被调函数后，实参变量也不能使用。 形参和实参的功能是作数据传送。发生函数调用时，主调函数把实参的值传送给被调函数的形参从而实现主调函数向被调函数的数据传送。在传值方式下，实参将值传给形参（注意传递方向），实参可以是表达式、常量，也可是变量或数组，该方式下形参不向实参返回信息在传地址方式下，形参和实参间可以实现数据的双向传递，实参传递的是地址，故必须是变量、数组名或数组元数，不能为常量或表达式。当形参为引用类型时，函数中对形参的访问和修改实际上就是针对相应实参所作的访问和修改。4.8 哈希表根据设定的哈希函数和处理冲突的方法，将一组关键字映射到一个有限的地址集上.如果两个关键字的哈希值相同，则两个关键字冲突4.9 排序简单排序：直接插入排序法：在插入第i个记录时，前i-1个记录已排好序，将关键字与第i-1、i-2个记录进行比较，查找位置后直接插入冒泡排序法：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则交换； 再将第二个记录的关键字与第三个记录进行比较，若为逆序则交换，以此类推简单选择排序：首先第2个到第n个记录进行比较，找出最小的记录与第1个记录互换 然后，第3个到第n个记录进行比较，找出最小的记录与第2个记录互换 .希尔排序：先将整个序列分成若干子序列，然后分别进行直接插入排序，最终再进行一次总直接插入排序快速排序法：通过一趟排序将待排序记录分成两部分，一部分均比另一部分的关键字小，然后再分别对这两部进行快速排序。通常将第一个记录作为枢轴记录，然后从右向左与枢轴记录比较，比枢轴记录小，就与枢轴记录互换归并排序：将两个或多个有序文件合并成一个新的有序文件5. 软件工程5.1 进度管理进度安排的常用图形描述方法有Gantt图和PERT图Gantt图，以图示的方式通过活动列表和时间刻度形象地表示出任何特定项目的活动顺序与持续时间Gantt图：清晰描述任务何时开始、何时结束及任务间的并行性，但不能反映任务之间的依赖关系，难以确定项目的关键所在。PERT图是有向图，箭头表示任务，可以标上完成该任务所需时间。5.2 数据流图 Data Flow Diagram DFD从数据传递和加工角度，以图形方式来表达系统的逻辑功能、数据在系统内部的逻辑流向和逻辑变换过程，是结构化系统分析方法的主要表达工具及用于表示软件模型的一种图示方法。由于它只反映系统必须完成的逻辑功能，所以是一种功能模型。在结构化开发方法中，数据流图是需求分析阶段产生的结果。组成元素：数据流。数据流是数据在系统内传播的路径，因此由一组成分固定的数据组成。如订票单由旅客姓名、年龄、单位、身份证号、日期、目的地等数据项组成。由于数据流是流动中的数据，所以必须有流向，除了与数据存储之间的数据流不用命名外，数据流应该用名词或名词短语命名。：数据源（终点）。代表系统之外的实体，可以是人、物或其他软件系统。：加工（处理）。加工是对数据进行处理的单元，它接收一定的数据输入，对其进行处理，并产生输出。：数据存储。表示信息的静态存储，可以代表文件、文件的一部分、数据库的元素等。例：绘制数据流图时，需要注意加工的绘制，在绘制加工的输入、输出时可能出现的错误有哪些？答：1、有输入无输出-黑洞2、 有输出无输入-奇迹3、 输入数据流无法通过加工产生输出流-灰洞4、 输入流与输出流名称相同5.3软件测试白盒测试，测试数据应根据程序的内部逻辑和指定的覆盖标准黑盒测试：测试软件外部特性软件测试步骤：单元测试、组装测试、确认测试、系统测试6. 数据库设计6.1 数据库的备份与恢复（1）数据库故障分类：事务故障：事务程序内部错误引起，有些可预期如库存不足，有些不可预期如非法输入、运算溢出系统故障：造成系统停止运行的任何事件，使得系统需要重新启动。丢失数据缓冲区中的内容，可能引起数据库的不一致。介质故障：存储介质发生故障，直接破坏了数据库（2）数据库恢复：必须建立冗余，最常用的冗余数据时数据转储和建立日志文件。（3） 恢复策略撤销事务：反向扫描未完成的事务日志，查找事务的更新操作；对更新操作执行逆操作，直至事务开始标记处；重做事务：对已经提交的事务重新执行，正向扫描日志，重做所有操作，直至事务结束标志处（4） 故障对应的恢复策略事务故障的恢复：事务在运行至正常终止点（submit rollback）前中止，事务日志只有开始标识没有结束标识，可通过撤销事务，使数据库恢复到执行事务前正确状态；系统故障的恢复：系统故障造成数据库不一致的原因有二：一是未完成的事务对数据库的更新可能已写入数据库；二是已提交的事务对数据库的更新可能还在缓冲区中未写入数据库。故：撤销故障发生时未完成事务；重做已提交的事务。系统故障的恢复在重启后自动执行。介质故障的恢复：重装数据库，利用最近一次的备份和故障前的日志文件副本，由系统撤销或重做事务。6.2 事务事务是一系列的数据库操作，是数据库应用程序的基本逻辑单位，这些操作要么全做要么全不做。四个特性：原子性、一致性、隔离性、持久性7. 数据结构7.1 二叉树（1）第i层最多2的i-1次方个结点（2）深度为k的二叉树至多2k-1个结点（3）具有n个结点的完全二叉树的深度为log2n+1（4）对任何一棵二叉树，其叶子节点数为n0，度为2的节点数为n2，则n0=n2+1遍历：根据根结点访问位置的不同，有前序、后序、中序三种遍历算法先序：访问根节点，先序遍历左子树，先序遍历右子树中序：中序遍历左子树，访问根节点，中序遍历右子树后序：后序遍历左子树，后序遍历右子树，访问根节点二叉排序树或者是一棵空树，或者是具有如下性质的二叉树： 若它的左子树非空，则其左子树上所有节点的关键字均小于根节点的关键字：若它的右子树非空，则其右子树上所有节点的关键字均大于根节点的关键字；左、右子树本身就是两棵二叉排序树。由上述定义可知，二叉排序树是一个有序表，对二叉排序树进行中序遍历，可得到一个关键字递增排序的序列。 对于给定的关键字序列，可从空树开始，逐个将关键字插入树中，来构造一棵二叉排序树。其过程为：每读入一个关键字值，就建立一个新节点。若二叉排序树非空，则将新节点的关键字与根节点的关键字相比较，如果小于根节点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空树，则新节点作为二叉排序树的根节点。 显然，若关键字初始序列已经有序，则构造出的二叉排序树一定是单枝树(每个节点只有一个孩子)。为了使在二叉排序树上进行的查找操作性能最优，构造二叉排序树时需进行平衡化处理，使每个节点左、右子树的高度差的绝对值不超过18. 多媒体标准8.1音频信号PC机处理的音频信号为人耳能听得到的音频信号，频率范围：20HZ - 20KHZ人的说话声频率范围：300HZ - 3400HZ声音信号数字化：取样-量化法（1） 采样：为不产生失真，采样频率不低于声音信号最高频率的2倍，因此语音信号采样频率8kHZ，音乐信号采样频率在40kHZ以上（2） 量化（3） 编码波形声音：数据传输率=采样频率*量化位数*声道数声音信号数据量=数据传输率*持续时间/8例1：语音信号的带宽通常为3003400Hz，经过数字化之后每秒钟产生的数据量大约是：A.64KB B.32KB C.128KB D.8KB解析：最高频率按4KHz算，由奈奎斯