1、LOGO高级数据库系统及其应用高级数据库系统及其应用2022-12-242第第12章章 数据仓库与决策支持系统数据仓库与决策支持系统数据仓库技术概述数据仓库技术概述12.1OLAP12.2OLAP的实现技术的实现技术12.3视图与决策支持系统视图与决策支持系统12.4快速返回部分结果快速返回部分结果12.52022-12-24312.1 数据仓库技术概述数据仓库技术概述12.1.1 决策支持查询的新特征 12.1.2 支持决策支持查询的系统类型 12.1.3 数据仓库2022-12-24412.1.1 决策支持查询的新特征决策支持查询的新特征v 查询表达的查询表达的WHERE子句通常是包含很多
2、子句通常是包含很多AND和和OR的的复杂条件。复杂条件。传统RDBMS针对OR的处理能力很弱。v 数据分析应用需要广泛使用各种统计函数。数据分析应用需要广泛使用各种统计函数。SQL-92只内置支持的了min/max/avg/sum/count五个统计函数,不支持象标准差等一些其它基本统计函数。完成高级统计需要由嵌入SQL的应用代码来完成。v 许多查询包括与时间有关的条件,通常需要基于各种典许多查询包括与时间有关的条件,通常需要基于各种典型时间周期进行分析和汇总。型时间周期进行分析和汇总。SQL-92缺乏处理时间序列数据方面的功能支持。v 在数据分析应用中,用户可能需要反复提出同一组类似在数据分
3、析应用中,用户可能需要反复提出同一组类似查询。查询。这不仅枯燥乏味,也使得DBMS无法从中识别或发掘查询优化机会。2022-12-24512.1.2 决策支持查询的系统类型决策支持查询的系统类型1)增强或扩展了)增强或扩展了OLAP特性的特性的DBMS OLAP:OnLine Analytic Processing 这类系统可高性能支持包含GROUP-BY和汇总操作符型式查询,且能对复杂布尔条件、统计函数和时间序列分析提供良好支持。2)专用)专用OLAP系统系统 在已有DBMSs的基础上,面向决策支持进行优化,以增强支持高效OLAP查询的一类专用系统。随时间推移,专用OLAP系统和增强了OLA
4、P特性的RDBMS系统之间区别可能会越来越小。3)数据挖掘)数据挖掘(Data Mining,DM)。希望从大数据集中探索发现有趣、意外趋势,探索特别数据模式。2022-12-24612.1.3 数据仓库系统数据仓库系统2022-12-24712.2 OLAP12.2.1 多维数据模型 12.2.2 OLAP查询12.2.3 与SQL操作比较12.2.4 统计数据库 12.2.5 OLAP设计2022-12-24812.2.1 多维数据模型多维数据模型 v 在多维数据模型中,核心数在多维数据模型中,核心数据项是一组事实度量,每个据项是一组事实度量,每个度量依赖于一组维度。度量依赖于一组维度。v
5、 例如,在一个关于销售数据例如,在一个关于销售数据管理的应用中,管理的应用中,sales(销售数量)是度量属性。维度则包括Product(产品)、Location(地区)和Time(时间)。给定一个产品、一个地区和一个时间点,我们最多只有一个销售值。图图12.2 一个多维数据集的图形化表示 每个小立方体格点(每个小立方体格点(cell)内)内存储表示一个销售值。存储表示一个销售值。2022-12-24912.2.1 多维数据模型多维数据模型v MOLAP 直接用多维数组来存储多维数据集的OLAP专用系统。MOLAP:multidimensional OLAPv ROLAP 直接关系来存储多维数
6、据集的OLAP专用系统。例如对前述销售管理,可被表示为以下一组关系:Sales(pid、timeid、locid,sales)Locations(locid:integer,city:string,state:string,country:string);Products(pid:integer,pname:string,category:string);Times(timeid:integer,date:string,week:integer,month:integer,quarter:integer,year:integer,holiday_flag:boolean);2022-12-24
7、1012.2.2 OLAP查询查询v OLAP系统的目标是给最终用户提供一个直观且强有力的系统的目标是给最终用户提供一个直观且强有力的查询接口,满足一般的面向商务分析任务。查询接口,满足一般的面向商务分析任务。v 常见的常见的OLAP操作是基于多维数据集,在一个或多个维度操作是基于多维数据集,在一个或多个维度上的度量值汇总。上的度量值汇总。一些典型的OLAP操作 上卷上卷(roll up)下钻下钻(drill-down)绕轴旋转绕轴旋转(pivoting)以下几个查询非常具有典型性,查销售总额;查询每个城市的销售总额;查询每个州的销售总额;查询销售总额排行前五名的产品类(该查询无法用标准SQL
8、语法来表达)。2022-12-241112.2.3 与与SQL操作比较操作比较v 虽然有些虽然有些OLAP查询很难用查询很难用SQL表达,或根本不能用表达,或根本不能用SQL表达(如表达(如TOP n查询)。但大多数的查询)。但大多数的OLAP查询都查询都可用可用SQL表达。典型地,它们是一些包含分组和聚合操表达。典型地,它们是一些包含分组和聚合操作的作的SQL语句。语句。v 单个单个OLAP操作可能导致几个密切相关的操作可能导致几个密切相关的SQL查询。例查询。例如,对图如,对图12.5的交叉表,是通过绕轴的交叉表,是通过绕轴(Time,Locatin)旋转获得。我们也可用下面查询来获得同样
9、的结果:旋转获得。我们也可用下面查询来获得同样的结果:SELECT SUM(S.sales)FROM Sales S,Time T,Locations L WHERE S.timeid=T.timeid AND S.locid=L.locid GROUP BY T.year,L.state 这个查询产生图12.5中灰色背景部分的单元。而该图中最下汇总行和最右汇总列则可分别通过下面两个SQL语句获得:SELECT SUM(S.sales)FROM Sales S,Locations LWHERE S.locid=L.locidGROUP BY L.stateSELECT SUM(S.sales)
10、FROM Sales S,Time TWHERE S.timeid=T.timeidGROUP BY T.year2022-12-241212.2.3 与与SQL操作比较操作比较v 这个交叉表也可被认为是在这个交叉表也可被认为是在Location维、时间维、以及维、时间维、以及同时在同时在Location维和时间维上的上卷。每个上卷对应一维和时间维上的上卷。每个上卷对应一个带个带GROUP BY的的SQL查询。查询。v 一般来说,给定一个带有一般来说,给定一个带有k个相关维的度量,我们能在任个相关维的度量,我们能在任何这何这k个维的子集维上上卷,故我们有总数大约个维的子集维上上卷,故我们有总数
11、大约2k个这个这样的样的SQL查询。查询。v 一个高层次的操作(象一个高层次的操作(象pivoting操作),一次可能产生操作),一次可能产生这这2k个个SQL查询。分析这些查询的共性,有助于我们更查询。分析这些查询的共性,有助于我们更有效地协调计算这组查询集。有效地协调计算这组查询集。v 一种关于一种关于SQL的建议扩展称为的建议扩展称为CUBE,它等价于一组,它等价于一组GROUP BY语句,每个语句,每个GROUP BY语句中包含的相关语句中包含的相关属性,对应属性,对应k维属性集的一个属性子集。维属性集的一个属性子集。2022-12-241312.2.3 与与SQL操作比较操作比较v
12、CUBE使用示例使用示例 观察下面这个特殊的扩展查询:CUBE pid,locid,timeid BY SUM Sales 它将在其所有的八个子集(包括全集pid,locid,timeid和空集)上上卷。它等价于八个以下形式的操作:SELECT SUM(S.sales)FROM Sales S GROUP BY grouping-list 这些查询只是在grouping-list上稍有不同,每个grouping-list对应pid,locid,timeid的一个子集。我们可将这八个查询想象为被分别对应图12.6中的一个栅格节点。每个节点上的结构元组可被进一步聚合来计算它的任何子节点结果。在一个
13、CUBE内,这些查询间的关系可被发掘利用来改善赋值性能。图图12.6 2022-12-241412.2.4 统计数据库统计数据库v 许多许多OLAP概念已在早期的统计数据库概念已在早期的统计数据库(statistical databases,SDBs)中得到了体现。中得到了体现。多维数据模型中关于“度量关联维度”的概念、“维值的分类层次结构”都早已被用在SDBs,上卷和下钻,在SDBs中也都有对应的操作。可能是由于应用领域和使用术语不同,两者的联系并未引起人们足够的注意。v 但但OLAP和和SDB之间还是有相当程度的区别。例如,之间还是有相当程度的区别。例如,SDBs主要用在社会经济学领域,对
14、属性概念分类层次和便于针对一些个性问题进行处理非常重要。SDBs中分类层次通常比OLAP应用中的分类层次更复杂,且受关注的程度更高。OLAP则主要面向包含大量数据集的商务应用,比SDB更关注高效处理非常大数据集的能力。2022-12-241512.2.5 OLAP设计设计vOLAP设计一般建议采用以事实表为中心(本例设计一般建议采用以事实表为中心(本例中,事实表为中,事实表为Sales),并以事实表主键的各分),并以事实表主键的各分量属性关联各维表的星型模式。量属性关联各维表的星型模式。v数据的主体主要存储在事实表中,要求采用无冗数据的主体主要存储在事实表中,要求采用无冗余设计,一般要求满足余
15、设计,一般要求满足BCNF规范。规范。v维表设计不要求满足很高规范(只要求满足维表设计不要求满足很高规范(只要求满足2NF规范即可)。规范即可)。降低维表规范虽然可带来一定的冗余,但可显著减少连接操作,有助于提高查询处理的性能。由于维表中数据量很少,而且变化不大,适度的冗余带来的空间浪费基本上可忽略。2022-12-2416一个典型的星型模式设计示例(图一个典型的星型模式设计示例(图12.7)2022-12-241712.3 OLAP的实现技术的实现技术12.3.1 位图索引 12.3.2 连接索引12.3.3 文件组织12.3.4 其它OLAP实现问题 2022-12-241812.3.1
16、位图索引位图索引v我们已在我们已在5.5部分,介绍了位图索引及其相关技部分,介绍了位图索引及其相关技术,包括位图压缩技术。术,包括位图压缩技术。v与传统的散列和与传统的散列和B+树索引相比,位图索引至少树索引相比,位图索引至少有两个重要优势:有两个重要优势:1)允许使用高效的位操作(用位向量的AND、OR操作)来回答查询;2)位图结构比B+树结构更紧凑,而且压缩、解压缩操作简单容易。v位图的这些特点和优势,使得它很适合于位图的这些特点和优势,使得它很适合于OLAP环境应用,特别是针对那些表结构相对简单、数环境应用,特别是针对那些表结构相对简单、数据量却非常大的事实表建立索引。据量却非常大的事实
17、表建立索引。2022-12-241912.3.2 连接索引连接索引v 当关系的数据量很大时,希望用很小的时间计算连接是当关系的数据量很大时,希望用很小的时间计算连接是很难的。处理这个问题的一个方法是,分别为需加快的很难的。处理这个问题的一个方法是,分别为需加快的特定、常用连接查询创建专门索引。特定、常用连接查询创建专门索引。v 考虑连接查询将事实表考虑连接查询将事实表F与两个维表与两个维表D1、D2连接,且表连接,且表D1的的C1列、表列、表D2的的C2列被包含在选择条件中。列被包含在选择条件中。可在连接索引中存储一组形如元组。这里,r1是表D1中在C1列取值c1所对应的那个元组rid,r2是
18、表D2中在C2列取值c2所对应的那个元组rid,而r是事实表F中一个元组的rid。r1,r2和r这三个元组被连接在一起。v 这种连接索引的主要缺陷是:这种连接索引的主要缺陷是:索引的大小可能因每个维表有几个列被包含在选择中,而高速增长。冗余存储代价可能很大。2022-12-242012.3.3 文件组织文件组织v由于许多由于许多OLAP查询通常只包含一个大数据集关查询通常只包含一个大数据集关系的几个列,垂直分区因此变得很有吸引力。系的几个列,垂直分区因此变得很有吸引力。然而,分开存储一个关系列值可能降低那些可能包含多个列的查询。如果在存储整个大关系的同时,也单独存储该大关系的每个列,但这显然会
19、增加存储空间且会带来一致性维护的额外问题。v一种更彻底的文件组织,是将事实表视为一个很一种更彻底的文件组织,是将事实表视为一个很大的多维数组,并直接按多维数组进行存储和建大的多维数组,并直接按多维数组进行存储和建立索引。立索引。这个方法已被用在MOLAP系统中。传统B+树索引可用来支持块中元组的快速检索。2022-12-242112.3.4 其它其它OLAP实现问题实现问题1.使用压缩已成为面向使用压缩已成为面向OLAP系统的一个广泛性问题。系统的一个广泛性问题。2.决定哪些视图需要进行预计算和存储,使得一些特色查决定哪些视图需要进行预计算和存储,使得一些特色查询能得到更快的响应处理也是一个极
20、富有挑战性问题。询能得到更快的响应处理也是一个极富有挑战性问题。汇总查询和操作符丰富的CUBE结构,为智能选择视图预计算和存储提供了更多的机会。自动或智能化选择预计算视图的相关探索,仍是当前的一项热点研究课题。3.许多许多OLAP系统都以新颖的方式,增强了查询表达和优系统都以新颖的方式,增强了查询表达和优化特性。化特性。4.一些传统一些传统SQL系统已逐渐演变为能有效支持系统已逐渐演变为能有效支持OLAP风格风格的查询,更强调对复杂查询的赋值处理,并逐渐移植了的查询,更强调对复杂查询的赋值处理,并逐渐移植了OLAP系统需要的那些特别技术。系统需要的那些特别技术。2022-12-242212.4
21、 视图与决策支持系统视图与决策支持系统12.4.1 视图、OLAP与DW 12.4.2 改写基于视图的查询12.4.3 视图物化12.4.4 视图物化相关问题 2022-12-242312.4.1 视图、视图、OLAP与与DWv视图与视图与OLAP的关系的关系 OLAP查询,典型地,是一些汇总查询。分析者通常希望这些查询能获得快速的响应,即便是面对非常大的数据集。我们很自然会想到利用预计算视图。CUBE操作非常有利于发现更有效的预计算赋值策略。v视图与视图与DW的关系的关系 本质上,DW只不过是一组异步复制表和一组需周期性维护的物化视图。DW维护的基本内容是:异步维护复制表和异步维护物化视图。
22、2022-12-242412.4.2 改写基于视图的查询改写基于视图的查询v 考虑如下的区域销售视图定义:考虑如下的区域销售视图定义:CREATE VIEW RegionalSales(category,state,sales)AS SELECT P.category,L.state,S.sales FROM Products P,Sales S,Locations L WHERE P.pid=S.pid AND S.locid=L.locidv 可基于视图可基于视图RegionalSales,计算每类产品在各州的销,计算每类产品在各州的销售汇总:售汇总:SELECT R.category,R
23、.state,SUM(R.sales)FROM RegionalSales R GROUP BY R.category,R.state 对于基于视图的查询赋值。通常做法是将查询表达中的视图名用视图定义替换,将查询改写为不含视图的一般查询。这种方法的思想虽然简单、清晰,但改写后表达含复杂的嵌入子查询,赋值性能一般很低。2022-12-242512.4.3 视图物化视图物化v视图物化视图物化 指事先赋值视图定义并存储赋值结果,然后直接在预计算结果上执行基于视图的查询。优缺点:优点:该方法通常比简单查询改写方法快得多,因为执行查询时不必再去赋值复杂的视图。缺点:需要维持预物化视图与基表的一致性。一旦
24、基表中数据有更新,须及时重新计算视图。v如何选择物化视图如何选择物化视图 系统预期的查询工作负荷,对如何选择要进行物化的视图和如何创建索引有重要影响。2022-12-242612.4.4 视图物化相关问题视图物化相关问题v对于视图物化,至少有三个需要考虑的重要问题:对于视图物化,至少有三个需要考虑的重要问题:哪些视图需要物化?在视图上需要建哪些索引?给定一个基于视图的查询和一组物化视图,我们能利用物化视图来回答查询吗?为保持物化视图与基表的一致性,我们应何时和如何刷新物化视图?几种延迟视图维护方案:懒惰(lazy)法。周期法(periodic)。强制法(forced)。2022-12-2427
25、12.5 快速返回部分查询结果快速返回部分查询结果12.5.1 TOP N查询 12.5.2 在线汇总2022-12-242812.5.1 TOP N查询(查询(1)v 用户可能希望从大量产品中了解销售最好的几种产品。用户可能希望从大量产品中了解销售最好的几种产品。常规实现方法:执行SQL查询,并按销售额排序结果。但如果有上亿个产品,而用户感兴趣的只是前几项产品,那么这种直接的赋值方法显然很浪费,且还需用户自己从列表中截留前几个结果。v 实际上,这种特殊的查询需求为实际上,这种特殊的查询需求为DBMS提供了优化机会。提供了优化机会。观察下面这个有点特别的查询表达:观察下面这个有点特别的查询表达
26、:SELECT P.pid,P.name,S.sales FROM Sales S,Products P WHERE S.pid=P.pid AND S.locid=1 AND S.timeid=3 ORDER BY S.sales DESC OPTIMIZE FOR 10 ROWS2022-12-242912.5.1 TOP N查询(查询(2)vDBMS应如何利用应如何利用OPTIMIZE FOR提示来更提示来更高效回答查询?关键点在于如何限制只计算销售高效回答查询?关键点在于如何限制只计算销售值可能落在前十的那些产品所对应元组。值可能落在前十的那些产品所对应元组。v我们可以采用如下查询来获
27、得:我们可以采用如下查询来获得:SELECT P.pid,P.name,S.sales FROM Sales S,Products P WHERE S.pid=P.pid AND S.locid=1 AND S.timeid=3 AND S.salesc ORDER BY S.sales DESC 由于附加了选择限制条件S.salesc,执行起来肯定比全关系选择和排序要快得多。2022-12-243012.5.1 TOP N查询(查询(3)v该方法有几个关键问题需要解决:该方法有几个关键问题需要解决:如何确定截断值c?直方图和其它系统统计都可用来帮助确定c值。但只能近似的估计值。如果返回结果元
28、组超过10该如何处理?这个问题较容易处理。SQL-92标准已能支持从结果集中返回前N个的功能,只要在SELECT关键字之后加上可选关键字Top N即可。如果返回结果元组少于10该如何处理?v显然,该方法的有效性依赖于我们能否很好估计显然,该方法的有效性依赖于我们能否很好估计截断值截断值c,特别地,应尽可能减少,特别地,应尽可能减少“出现返回结出现返回结果元组数比需要结果数少果元组数比需要结果数少”情况的次数。情况的次数。2022-12-243112.5.2 在线汇总在线汇总v 当目标关系当目标关系数据量很大时,查询的代价可能很大。当查数据量很大时,查询的代价可能很大。当查询提交时,若用传统方法
29、进行完全计算,将很难快速返询提交时,若用传统方法进行完全计算,将很难快速返回结果。回结果。一种解决方法是,采用预计算法。一种解决方法是,采用预计算法。另一种是另一种是在线汇总方法在线汇总方法:在查询时计算查询回答,但:在查询时计算查询回答,但先尽快给用户返回一个近似结果,而后再不断给出精先尽快给用户返回一个近似结果,而后再不断给出精化结果。化结果。v 如何实现在线汇总如何实现在线汇总 DBMS必须移植一些统计技术,以便为近似结果提供可信度区间,并使用相关操作符的非全关系算法。嵌入循环连接(nested loops join)和散列连接(hash join)比排序-连接更为合适用来进行在线连接汇总计算。v一个典型的在线汇总应用示例一个典型的在线汇总应用示例