1、11/20/2019 数据挖掘：概念与技术 1 数据挖掘：概念与技术数据挖掘：概念与技术 第三章：数据仓库与 OLAP技术概述 11/20/2019 数据挖掘：概念与技术 2 第三章：数据仓库与OLAP技术概述 ?什么是数据仓库? ?多维数据集模型 ?数据仓库体系结构 ?数据仓库实现 ?从数据仓库到数据挖掘 11/20/2019 数据挖掘：概念与技术 3 什么是数据仓库? ?多种定义方式，但不严格 ?从组织机构的操作数据库分离并独立维护的决策支持数据库 ?支持信息处理，为统一的历史数据分析提供坚实的平台 ?数据仓库是一个面向主题的、集成的、时变的和非易失的数据集合，支持管理部门的决策过程。W.
2、 H. Inmon ?建立数据仓库： ?构建和使用数据仓库的过程 11/20/2019 数据挖掘：概念与技术 4 数据仓库面向主题的 ?围绕主题组织数据, 如顾客、产品、销售等。 ?关注决策者的数据建模与分析，而不是组织机构的日常操作和事务处理。 ?提供特定主题的简明视图，排除对于决策支持过程无用的数据。 11/20/2019 数据挖掘：概念与技术 5 数据仓库集成的 ?由多个异构数据源集成构建 ?关系数据库,平面文件,联机事务记录 ?应用数据清理和数据集成技术 ?确保命名约定，编码结构，属性度量等一致性 ?将数据迁入数据仓库时需要进行数据转换 11/20/2019 数据挖掘：概念与技术 6
3、数据仓库时变的 ?数据仓库中数据的时间范围比业务操作系统中长得多 ?业务操作数据库：当前数据 ?数据仓库：提供历史数据信息 (如过去5-10年) ?数据仓库中的结构主键： ?都隐式或显示包含时间元素 ?但业务操作数据主键不一定包含时间元素 11/20/2019 数据挖掘：概念与技术 7 数据仓库非易失的 ?物理存储：与操作环境分离，虽然来自其中。 ?数据仓库环境中不发生数据更新操作 ?不需要事务处理，恢复和并发控制机制 ?只需要两种数据操作： ?i数据初始化装入 ?数据访问 11/20/2019 数据挖掘：概念与技术 8 数据仓库与异构数据库 ?传统异构数据库集成：查询驱动方法 ?在异构数据库
4、上建立包装程序和集成程序（中介程序） ?提交查询时，使用元数据字典将查询转换为异构站点上的查询。然后将查询映射和发送到局部查询处理器，由不同站点返回的结果集成为全局查询结果集。 ?复杂的信息过滤和集成处理，与局部数据源的处理竞争资源 ?数据仓库:更新驱动方法，高性能 ?将异构源的信息预先集成并存储在数据仓库中，供直接查询和分析 ?不包含最近的信息 ?支持复杂多维查询 11/20/2019 数据挖掘：概念与技术 9 数据仓库与业务操作数据库 ?OLTP (on-line transaction processing)，联机事务处理 ?传统关系数据库管理系统的主要任务 ?日常操作：购物，库存，制造
5、，银行，工资，注册，记账等。 ?OLAP (on-line analytical processing)，联机分析处理 ?数据仓库系统的主要任务 ?数据分析和决策制定 ?区别 (OLTP vs. OLAP): ?用户和系统的面向性：顾客事务和查询（办事员，打工仔）与市场数据分析（知识工人，老板） ?数据内容： 当前的，细节的 vs. 历史的, 汇总聚集的 ?数据库设计： E-R + 业务应用 vs. 星形、雪花型 + 主题 ?视图： 当前的,局部的 vs. 进化的,集成的 ?访问模式: 更新 vs. 只读 但查询复杂 11/20/2019 数据挖掘：概念与技术 10 OLTP vs. OLAP
6、 11/20/2019 数据挖掘：概念与技术 11 为什么需要分离数据仓库? ?提高两个系统的系能 ?DBMS tuned for OLTP: access methods, indexing, concurrency control, recovery ?Warehousetuned for OLAP: complex OLAP queries, multidimensional view, consolidation ?不同的功能和不同的数据: ?数据不全: Decision support requires historical data which operational DBs do
7、 not typically maintain ?数据聚合: DS requires consolidation (aggregation, summarization) of data from heterogeneous sources ?数据质量: different sources typically use inconsistent data representations, codes and formats which have to be reconciled ?Note: 越来越多的系统直接在DBMS上进行 11/20/2019 数据挖掘：概念与技术 12 Chapter 3
8、: Data Warehousing and OLAP Technology: An Overview ?What is a data warehouse? ?A multi-dimensional data model ?Data warehouse architecture ?Data warehouse implementation ?From data warehousing to data mining 11/20/2019 数据挖掘：概念与技术 13 由表和电子数据表到数据立方体 ?数据仓库和OLAP工具基于多维数据模型，以数据立方体的方式观察数据 ?数据立方体,如销售, 从多维角
9、度对数据建模和观察 ?维度表, 如 item (item_name, brand, type), or time(day, week, month, quarter, year) ?事实表 (如 dollars_sold) 包含度量值和关联维度表的码 ?名词： ?数据立方体成为方体(cuboid) ?存放最底层汇总的方体（ n-D ）成为基本方体(basic cuboid) ?存放最高层汇总的方体（ 0-D ）称为顶点方体(apex cuboid)，用all标记 ? 方体的格成为数据立方体(data cube) 11/20/2019 数据挖掘：概念与技术 14 3-D数据立方体 11/20/2
10、019 数据挖掘：概念与技术 15 4-D数据立方体 11/20/2019 数据挖掘：概念与技术 16 数据立方体:方体的格 time,item time,item,location time, item, location, supplier all time item location supplier time,location time,supplier item,location item,supplier location,supplier time,item,supplier time,location,supplier item,location,supplier 0-D(ap
11、ex) cuboid 1-D cuboids 2-D cuboids 3-D cuboids 4-D(base) cuboid 11/20/2019 数据挖掘：概念与技术 17 数据仓库的概念建模 ?数据仓库建模： dimensions & measures ?星形模型: A fact table in the middle connected to a set of dimension tables ?雪花模型: A refinement of star schema where some dimensional hierarchy is normalized into a set of s
12、maller dimension tables, forming a shape similar to snowflake ?事实星座型: Multiple fact tables share dimension tables, viewed as a collection of stars, therefore called galaxy schema or fact constellation 11/20/2019 数据挖掘：概念与技术 18 星形模型例子 time_key day day_of_the_week month quarter year time location_key s
13、treet city state_or_province country location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_type item branch_key branch_name branch_type branch 11/20/2019 数据挖掘：概念与技术 19 雪花模型例子 time_key day day_of_the_week
14、month quarter year time location_key street city_key location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_name brand type supplier_key item branch_key branch_name branch_type branch supplier_key supplier_type supplier city_key c
15、ity state_or_province country city 11/20/2019 数据挖掘：概念与技术 20 事实星座型例子 time_key day day_of_the_week month quarter year time location_key street city province_or_state country location Sales Fact Table time_key item_key branch_key location_key units_sold dollars_sold avg_sales Measures item_key item_nam
16、e brand type supplier_type item branch_key branch_name branch_type branch Shipping Fact Table time_key item_key shipper_key from_location to_location dollars_cost units_shipped shipper_key shipper_name location_key shipper_type shipper 11/20/2019 数据挖掘：概念与技术 21 DMQL 中的立方体定义语法 ?立方体定义 (Fact Table) defi
17、ne cube : ?维度定义 (Dimension Table) define dimension as () ?Special Case (Shared Dimension Tables) ?First time as “cube definition” ?define dimension as in cube 11/20/2019 数据挖掘：概念与技术 22 DMQL定义星形模型 define cube sales_star time, item, branch, location: dollars_sold = sum(sales_in_dollars), avg_sales = av
18、g(sales_in_dollars), units_sold = count(*) define dimension time as (time_key, day, day_of_week, month, quarter, year) define dimension item as (item_key, item_name, brand, type, supplier_type) define dimension branch as (branch_key, branch_name, branch_type) define dimension location as (location_k
19、ey, street, city, province_or_state, country) 11/20/2019 数据挖掘：概念与技术 23 DMQL定义雪花模型 define cube sales_snowflake time, item, branch, location: dollars_sold = sum(sales_in_dollars), avg_sales = avg(sales_in_dollars), units_sold = count(*) define dimension time as (time_key, day, day_of_week, month, quar
20、ter, year) define dimension item as (item_key, item_name, brand, type, supplier(supplier_key, supplier_type) define dimension branch as (branch_key, branch_name, branch_type) define dimension location as (location_key, street, city(city_key, province_or_state, country) 11/20/2019 数据挖掘：概念与技术 24 DMQL定
21、义事实星座型 define cube sales time, item, branch, location: dollars_sold = sum(sales_in_dollars), avg_sales = avg(sales_in_dollars), units_sold = count(*) define dimension time as (time_key, day, day_of_week, month, quarter, year) define dimension item as (item_key, item_name, brand, type, supplier_type)
22、 define dimension branch as (branch_key, branch_name, branch_type) define dimension location as (location_key, street, city, province_or_state, country) define cube shipping time, item, shipper, from_location, to_location: dollar_cost = sum(cost_in_dollars), unit_shipped = count(*) define dimension
23、time as time in cube sales define dimension item as item in cube sales define dimension shipper as (shipper_key, shipper_name, location as location in cube sales, shipper_type) define dimension from_location as location in cube sales define dimension to_location as location in cube sales 11/20/2019
24、数据挖掘：概念与技术 25 数据立方体的度量: 三类 ?分布式度量: 将函数用于n个聚合值得到的结果与将函数用于整个数据集（不划分）得到的结果一样 ?E.g., count(), sum(), min(), max() ?代数度量:能够用具有M个参数的代数函数计算，而每个参数都可以用一个分布式聚合函数求得 ?E.g., avg(), min_N(), standard_deviation() ?整体度量: 描述它的子聚集所需的存储没有常数界。 ?E.g., median(), mode(), rank() 11/20/2019 数据挖掘：概念与技术 26 概念分层: 维度 (location)
25、 all Europe North_America Mexico Canada Spain Germany Vancouver M. Wind L. Chan . . . . . . all region office country Toronto Frankfurt city 11/20/2019 数据挖掘：概念与技术 27 概念分层：数值型数据（price） 11/20/2019 数据挖掘：概念与技术 28 数据仓库和分层视图 Specification of hierarchies ?Schema hierarchy day month quarter; week year ?Set_
26、grouping hierarchy 1.10 = minsup ?动机 ?仅一小部分“浮于水面”的立方体单元存储在稀疏立方体中 ?仅计算感兴趣的单元数据超出某一阈值 ?避免立方体的爆炸性增长 11/20/2019 数据挖掘：概念与技术 54 索引OLAP数据：位图索引 ?某一具体列上的索引； ?列中的每一个值都有一个位向量：位操作速度快 ?如果给定属性上包含n个值，则位图索引中每项需要n个位。 ?位向量的长度：基本表的记录数 ?如果基表给定行上该属性值为 v，则位图索引对应行的该值位置1。 ?不适合集数很大的域，导致位向量很长 11/20/2019 数据挖掘：概念与技术 55 位图索引例子
27、11/20/2019 数据挖掘：概念与技术 56 索引OLAP数据: 连接索引 ?连接索引：JI(R-id, S-id) where R (R- id, ) ? S (S-id, ) ?传统的索引将给定列上的值映射到具有该值的行的列表上 ?在JI文件中物化关系连接，加快连接速度 ?在数据仓库中，连接索引维护维的属性值与事实表的对应行的联系 ?连接索引可以跨越多维，形成符合连接索引 11/20/2019 数据挖掘：概念与技术 57 连接索引例子 11/20/2019 数据挖掘：概念与技术 58 OLAP 查询的有效处理 ?确定哪些操作应该在可利用的方体上执行 ?将 drill, roll等操作转
28、化为SQL或OLAP操作 ? e.g., dice = selection + projection ?确定相关操作 应当使用哪些物化的方体 ?假设对 brand, province_or_state 处理查询，选择常量 “year = 2004”, 有4个物化方体可用： 1) year, item_name, city 2) year, brand, country 3) year, brand, province_or_state 4) item_name, province_or_state where year = 2004 应该选择哪一个来处理查询? 基于代价的估计。 ?采用稀疏矩阵
29、和数据压缩技术 11/20/2019 数据挖掘：概念与技术 59 Chapter 3: Data Warehousing and OLAP Technology: An Overview ?What is a data warehouse? ?A multi-dimensional data model ?Data warehouse architecture ?Data warehouse implementation ?From data warehousing to data mining 11/20/2019 数据挖掘：概念与技术 60 数据仓库的使用 ?三种数据仓库应用 ?信息处理
30、?支持查询、基本的统计分析、使用交叉表、表、图表进行报告 ?构造低代价的基于Web的访问工具。 ?分析处理 ?多维数据分析 ?支持OLAP操作： slice-dice, drilling, pivoting ?数据挖掘 ?从隐藏的模式中发现知识 ?支持关联分析，构造分析模型，进行分类和预测，使用可视化工具提供挖掘结果 11/20/2019 数据挖掘：概念与技术 61 数据仓库的渐进使用 ?商务管理人员使用数据仓库和数据集市进行数据分析和战略决策 ?数据仓库使用时间越长，进化的越好 ?开始，用于产生报告和回答预先定义的查询 ?渐渐地，用于分析汇总和详细的数据结果以报表和图表提供 ?稍后，用于战略
31、目的，进行多维分析和复杂的切片和切块操作。 ?最后，用于知识发现，并使用数据挖掘工具进行战略决策。 ?数据仓库工具：访问与检索工具，数据库报表工具，数据分析工具和数据挖掘工具 11/20/2019 数据挖掘：概念与技术 62 从联机分析处理(OLAP) 到联机分析挖掘 (OLAM) ?为什么需要联机分析挖掘？ ?数据仓库中数据的高质量 ?DW中包含集成，一致，干净的数据 ?环绕数据仓库的信息处理基础设施 ?ODBC, OLEDB, Web访问, 服务机制, reporting and OLAP tools ?基于OLAP的探测试数据分析 ?Mining with drilling, dicin
32、g, pivoting, etc. ?数据挖掘功能的联机选择 ?Integration and swapping of multiple mining functions, algorithms, and tasks 11/20/2019 数据挖掘：概念与技术 63 联机分析挖掘的体系结构 数据仓库 元数据 MDDB OLAM 引擎 OLAP 引擎 图形用户界面 API 立方体 API 数据库 API 数据清理 数据集成 第三层 OLAP/OLAM 第2层 多维数据库 第1层 数据存储 第4层 用户界面层 过滤&集成 过滤 数据库 挖掘查询 挖掘结果 11/20/2019 数据挖掘：概念与技术
33、 64 Chapter 3: Data Warehousing and OLAP Technology: An Overview ?What is a data warehouse? ?A multi-dimensional data model ?Data warehouse architecture ?Data warehouse implementation ?From data warehousing to data mining ?Summary 11/20/2019 数据挖掘：概念与技术 65 总结: 数据仓库和OLAP技术 ?为什么需要数据仓库? ?数据仓库的多维数据模型 ?St
34、ar schema, snowflake schema, fact constellations ?A data cube consists of dimensions & measures ?OLAP 操作: drilling, rolling, slicing, dicing and pivoting ?数据仓库结构体系 ?OLAP 服务器: ROLAP, MOLAP, HOLAP ?数据立方体的有效计算 ?Partial vs. full vs. no materialization ?Indexing OALP data: Bitmap index and join index ?OL
35、AP query processing ?从 OLAP 到 OLAM (联机分析挖掘) 11/20/2019 数据挖掘：概念与技术 66 References (I) ?S. Agarwal, R. Agrawal, P. M. Deshpande, A. Gupta, J. F. Naughton, R. Ramakrishnan, and S. Sarawagi. On the computation of multidimensional aggregates. VLDB96 ?D. Agrawal, A. E. Abbadi, A. Singh, and T. Yurek. Effic
36、ient view maintenance in data warehouses. SIGMOD97 ?R. Agrawal, A. Gupta, and S. Sarawagi. Modeling multidimensional databases. ICDE97 ?S. Chaudhuri and U. Dayal. An overview of data warehousing and OLAP technology. ACM SIGMOD Record, 26:65-74, 1997 ?E. F. Codd, S. B. Codd, and C. T. Salley. Beyond
37、decision support. Computer World, 27, July 1993. ?J. Gray, et al. Data cube: A relational aggregation operator generalizing group-by, cross-tab and sub-totals. Data Mining and Knowledge Discovery, 1:29-54, 1997. ?A. Gupta and I. S. Mumick. Materialized Views: Techniques, Implementations, and Applica
38、tions. MIT Press, 1999. ?J. Han. Towards on-line analytical mining in large databases. ACM SIGMOD Record, 27:97-107, 1998. ?V. Harinarayan, A. Rajaraman, and J. D. Ullman. Implementing data cubes efficiently. SIGMOD96 11/20/2019 数据挖掘：概念与技术 67 References (II) ?C. Imhoff, N. Galemmo, and J. G. Geiger.
39、 Mastering Data Warehouse Design: Relational and Dimensional Techniques. John Wiley, 2003 ?W. H. Inmon. Building the Data Warehouse. John Wiley, 1996 ?R. Kimball and M. Ross. The Data Warehouse Toolkit: The Complete Guide to Dimensional Modeling. 2ed. John Wiley, 2002 ?P. ONeil and D. Quass. Improve
40、d query performance with variant indexes. SIGMOD97 ?Microsoft. OLEDB for OLAP programmers reference version 1.0. In http:/ 1998 ?A. Shoshani. OLAP and statistical databases: Similarities and differences. PODS00. ?S. Sarawagi and M. Stonebraker. Efficient organization of large multidimensional arrays
41、. ICDE94 ?OLAP council. MDAPI specification version 2.0. In http:/www.olapcouncil.org/research/apily.htm, 1998 ?E. Thomsen. OLAP Solutions: Building Multidimensional Information Systems. John Wiley, 1997 ?P. Valduriez. Join indices. ACM Trans. Database Systems, 12:218-246, 1987. ?J. Widom. Research problems in data warehousing. CIKM95.
