高级数据库原理

高 级 数 据 库 原 理SJ0821 200820212043张东圆一、简答题1、简述数据挖掘的概念以及数据挖掘的分类。答：数据挖掘(Data Mining，简称DM)，简单地讲就是从大量数据中挖掘或抽取出知识。数据挖掘，又称为数据库中知识发现(Knowledge Discovery from Database，简称KDD)，它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。整个知识挖掘(KDD)过程是由若干挖掘步骤组成，而数据挖掘仅是其中的一个主要步骤。数据挖掘涉及的学科领域和方法很多，有多种分类方法。从数据分析角度出发，数据挖掘可以分为两种类型:描述型数据挖掘和预测型数据挖掘。根据挖掘任务可以分为:分类或预测模型发现、数据总结与聚类发现、关联规则发现、序列模式发现、相似模式发现、混沌模式发现、依赖关系或依赖模型发现、异常和趋势发现等。根据挖掘对象可以分为:关系数据库、面向对象数据库(Object一oriented Database)、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、遗产数据库以及web等对象的挖掘。根据挖掘方法可以分为:机器学习方法、统计方法、聚类分析方法、探索性分析、神经网络(Neural Network)方法、遗传算法(Genetic Algorithm)、数据库方法、近似推理和不确定性推理方法、基于证据理论和元模式的方法、现代数学分析方法、粗糙集(Rough Set)方法、集成方法等。根据数据挖掘所能发现的知识可以分为:广义型知识挖掘、差异型知识挖掘、关联型知识挖掘、预测型知识挖掘、偏离型异常知识挖掘、不确定性知识等。当然这些分类方法都从不同角度刻画了数据挖掘研究的策略和范畴，他们是互相交叉而又相互补充的。2、什么是N个事务的一个调度？答: 事务是一个操作序列，这些操作“要么不做，要么都做”，是数据库环境中不可分割的逻辑工作单位。事务的执行次序称为调度。当有N个事务要执行时，它的调度有两种方式，一种是串行调度，一种是并行调度。前者是指N个事务依次执行，可有n！种有效调度，其执行结果总是正确的；后者是指系统用分时的方法同时处理N个事务，如果一个并发调度的结果与某一个串行调度执行的结果等价，则称该并行调度是可串行化调度。N个事务的一个调度就是为N个事务指定一种执行方式，让它们按照指定的方式能有效的执行。3、简述Apriori算法的思想，谈谈算法的应用领域并举例。答：Apriori算法：使用候选项集找频繁项集。它是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。该算法的应用领域比较广泛，最典型的应用是在超市购物、银行客户等。在超市购物中比较典型的就是“啤酒和尿布”的例子，通过Apriori算法了解到购买尿布的人士一起购买啤酒的概率很大，因此将啤酒和尿布摆在一起有利于买卖。4、在数据库的并发控制中，什么是“封锁的粒度”？封锁的粒度与系统的并发度之间有什么联系？答: 封锁的粒度(Granularity)是指封锁对象的大小。封锁对象可以是逻辑单元，也可以是物理单元。封锁粒度与系统的并发度和并发控制的开销密切相关。封锁的粒度越小，并发度越高，系统开销也越大；封锁的粒度越大，并发度越低，系统开销也越小。5、企业面对海量数据，应如何具体实施数据挖掘，使之转换成可行的结果/模型？答：企业对海量数据的数据挖掘应依据不同的问题进行不同的挖掘过程，但总的挖掘过程如下：1、问题定义。首先要明确实际工作对数据挖掘的具体要求，其次是通过对各种算法的对比来确定可用的算法。后续数据准备在此基础上进行。2、数据收集和数据预处理。这个过程可以分为三个子步骤:数据选取、数据预处理和数据变换。数据选取确定数据挖掘任务的操作对象，即目标数据，是用户根据需求从原始数据库中抽取的一组数据；数据预处理一般包括消除数据噪声、补全缺失数据项、确保数据一致性和完成数据类型转换等；数据变换主要目的是消减数据维数，从初始特征中找出真正有用的特征，以减少数据挖掘中需要考虑的变量个数。3、数据挖掘。基于需要执行的数据挖掘任务，这一步骤就是对变换后的数据应用具体算法来产生期望的挖掘结果。如分类、聚类、关联规则发现或序列模式发现等。4、结果解释和评估。数据挖掘发现的模式经过评估，可能存在冗余或者无关的模式，需要将其剔除；另外，挖掘结果如何呈现给用户也是一个非常重要的问题，挖掘结果的有用性主要取决于这一步，通常使用各种可视化工具和图形用户界面。依据上述步骤，将有利于数据挖掘的进行。二、现为某住宅小区的物业管理公司的数据库设计一个ER模型，涉及到的信息有：房屋、业主（包括工作单位）、收费（多个种类）、维修、违章处理、宠物登记、老人登记、幼儿登记、业主特长等。试画出ER图，ER图中应说明属性、联系类型（1:1、1:N、M:N）及实体标识符。说明：每个实体的属性不要多，只要能说明问题即可；画出完整的ER图即可，不必再作其他说明。1:11:N维修违章处理房屋老人房屋业主宠物收费特长姓名年龄年龄种类价格年限期限种类费用1:11:1幼儿登记1:N性别三、在应用项目的实施中发现，许多程序员在利用一些前端数据库开发工具（如PowerBuilder、Delphi等）开发数据库应用程序时，只注重用户界面的华丽，并不重视查询语句的效率问题，导致所开发出来的应用系统效率低下，资源浪费严重。因此，如何设计高效合理的查询语句就显得非常重要。以应用实例为基础，结合数据库理论，介绍查询优化技术在现实系统中的运用。解析：下面我们举一个制造公司的例子来说明查询优化的应用。制造公司数据库中包括3个表，模式如下所示：1part表零件号零件描述其他列（part_num）（part_desc）（othercolumn）102，032Seageat30Gdisk500，049Novel10Mnetworkcard2vendor表厂商号厂商名其他列（vendor_num）（vendor_name）（othercolumn）910，257SeageatCorp523，045IBMCorp3parven表零件号厂商号零件数量（part_num）（vendor_num）（part_amount）102，032910，2573,450,000234，423321，0014，000，000下面的查询将在这些表上定期运行，并产生关于所有零件数量的报表：SELECT part_desc，vendor_name，part_amountFROM part，vendor，parvenWHERE part.part_num=parven.part_numAND parven.vendor_num=vendor.vendor_numORDERBY part.part_num如果不建立索引，上述查询代码的开销将十分巨大。为此，我们在零件号和厂商号上建立索引。索引的建立避免了在嵌套中反复扫描。关于表与索引的统计信息如下：表行尺寸行数量每页行数量数据页数量（table）(rowsize)（Rowcount）（Rows/Pages）（DataPages）part15010，00025400Vendor1501，0002540Parven1315，00030050索引键尺寸每页键数量页面数量（Indexes）(KeySize)（Keys/Page)(LeafPages）part450020Vendor45002Parven825060看起来是个相对简单的3表连接，但是其查询开销是很大的。通过查看系统表可以看到，在part_num上和vendor_num上有簇索引，因此索引是按照物理顺序存放的。parven表没有特定的存放次序。这些表的大小说明从缓冲页中非顺序存取的成功率很小。此语句的优化查询规划是：首先从part中顺序读取400页，然后再对parven表非顺序存取1万次，每次2页（一个索引页、一个数据页），总计2万个磁盘页，最后对vendor表非顺序存取1.5万次，合3万个磁盘页。可以看出在这个索引好的连接上花费的磁盘存取为5.04万次。实际上，我们可以通过使用临时表分3个步骤来提高查询效率：1从parven表中按vendor_num的次序读数据：SELECT part_num，vendor_num，priceFROM parvenORDER BY vendor_numINTO temppv_by_vn这个语句顺序读parven（50页），写一个临时表（50页），并排序。假定排序的开销为200页，总共是300页。2把临时表和vendor表连接，把结果输出到一个临时表，并按part_num排序：SELECT pv_by_vn.*, vendor.vendor_numFROM pv_by_vn, vendorWHERE pv_by_vn.vendor_num=vendor.vendor_numORDER BY pv_by_vn.part_numINTOTMP pvvn_by_pnDROPTABL Epv_by_vn这个查询读取pv_by_vn(50页)，它通过索引存取vendor表1.5万次，但由于按vendor_num次序排列，实际上只是通过索引顺序地读vendor表（402=42页），输出的表每页约95行，共160页。写并存取这些页引发5160=800次的读写，索引共读写892页。3把输出和part连接得到最后的结果：SELECT pvvn_by_pn.*，part.part_descFROM pvvn_by_pn，partWHERE pvvn_by_pn.part_num=part.part_numDROPTABLE pvvn_by_pn这样，查询顺序地读pvvn_by_pn(160页)，通过索引读part表1.5万次，由于建有索引，所以实际上进行1772次磁盘读写，优化比例为301。笔者在InformixDynamicSever上做同样的实验，发现在时间耗费上的优化比例为51(如果增加数据量，比例可能会更大)。四、针对多维数据库，谈谈你的理解，以及多维数据分析的实现和应用答：多维数据库（Multidimensional Database, MDD）可以简单地理解为：将数据存放在一个n维数组中，而不是像关系数据库那样以记录的形式存放。因此它存在大量稀疏矩阵，人们可以通过多维视图来观察数据。多维数据库增加了一个时间维，与关系数据库相比，它的优势在于可以提高数据处理速度，加快反应时间，提高查询效率。目前有两种MDD的OLAP产品：基于多维数据库的MOLAP和基于关系数据库的ROLAP。ROLAP建立了一种新的体系，即星型结构。MDD并没有公认的多维模型，也没有像关系模型那样标准地取得数据的方法(如SQL、API等)。基于MDD的OLAP产品，依据决策支持的内容使用范围也有很大的不同。在低端，用户使用基于单用户或小型LAN的工具来观察多维数据。这些工具的功能性和实用性可能相当不错，但由于受到规模的限制，它们不具备OLAP的所有特性。这些工具使用超立方结构，将模型限制在n维形态。当模型足够大且稀疏数据没有控制好时，这种模型将会不堪一击。这些工具使用数据库的大小是以MB来计量的，而不是以GB计量的，因此只能进行只读操作，且具备有限的复杂计算。在高端，OLAP工具用4GL提供了完善的开发环境、统计分析、时间序列分析、财政报告、用户接口、多层体系结构、图表等许多其他功能。尽管不同的OLAP工具都使用了它们自己的多维数据库，但它们在不同程度上也利用了关系数据库作为存储媒体。因为关系数据库和OLAP工具同时在高端服务器上处理，所以速度和效率仍然很快。纯多维数据库引擎也被开发出来。尽管这些工具缺乏4GL及充分的开发环境，但却有比高端MDD工具所使用的数据库更为复杂的数据库。这些工具也具有统计分析、财务分析和时间序列分析等功能，并有自己的API，允许其对前端的开发环境开放。MDD能提供优良的查询性能。存储在MDD中的信息比在关系数据库中的信息具有更详细的索引，可以常驻内存。MDD的信息是以数组形式存放的，所以它可以在不影响索引的情况下更新数据。因此MDD非常适合于读写应用。多维数据分析维是数据分类方法的关键成分或特征,例如时间,指标,单位,其中每一项都可以认为是数据的一维,这些维数的交点产生一个单元,它是通过在一个多维数据组中选择每一维的一个值来定义的.多维数据是一个数据集合,通常是从枚举字典的枚举项构造,并组织和汇总成一个多维结构,多维数据分析是对数据库中的数据进行快速访问的技术,它是一种方便,快捷的查询方式.OALP的多维数据分析1. 切片和切块在多维数据结构中,按二维进行切片,按三维进行切块,可得到所需要的数据。如在 城市、产品、时间三维立方体中进行切块和切片,可得到各城市、各产品的销售情况2. 钻取钻取包含向下钻取和向上钻取操作， 钻取的深度与维所划分的层次相对应。3.旋转通过旋转可以得到不同视角的数据。五、试选择下面第一组关键字或第二组关键字，撰写一篇有关这些技术的500800字的短文，试论述数据库技术的发展：第一组关键字：中间件，ODBC技术，数据库与WWW，网络数据库第二组关键字:概念建模，ER图，对象联系模型，UML类图数据库概念模型是数据库的全局逻辑数据视图，是数据库管理元所看到的实体、实体属性和实体间的联系。ER图及实体-联系图(Entity-Relation Diagram)用来建立数据模型，在数据库系统概论中属于概念设计阶段，形成一个独立于机器，独立于DBMS的ER图模型。ER图提供了表示实体（即数据对象）、属性和联系的方法，用来描述现实世界的概念模型。UML（Unified Modeling Language的缩写）统一建模语言,是用来对软件密集系统进行可视化建模的一种语言。UML为面向对象开发系统的产品进行说明、可视化、和编制文档的一种标准语言。移动数据库和微小型数据库是未来数据库的发展的两个子方向，研究移动计算环境中的数据管理技术，即移动数据库技术。与基于固定网络的传统分布计算环境相比，移动计算环境具有以下特点：移动性、频繁断接性、带宽多样性、网络通信的非对称性、移动计算机的电源能力、可靠性要求较低和可伸缩性等。这就对概念模型，ER图，对象联系模型，UML类图提出了更高的设计要求。微小型数据库系统(a small-footprint DBMS)可以定义为：一个只需很小的内存来支持的数据库系统内核。微小型数据库系统针对便携式设备其占用的内存空间大约为2MB，而对于掌上设备和其他手持设备，它占用的内存空间只有 50KB 左右。这些数据库的基础，依然会是在传统的设计方法中加以适当的改进。六、R-10000个元组，占1000个磁盘块；S-5000个元组，占500个磁盘块。1）如果R和S各分得一个主缓冲区，分别用循环嵌套，排序合并，HASH计算