chap05 SQL实践 - 数据库设计与实践

课程：0A102 数据库设计与实践（田浩然上传资料）章节：第5章 SQL实践

概述

本章是SQL高级实践内容，涵盖五大主题：

递归查询 — 处理层次结构数据（零件组装、员工上下级）
物化视图 — 预计算结果加速查询，OLAP常用技术
数据分区 — 大规模数据（GB→TB→PB）的物理存储优化
数据分析 — 直方图、中位数、Skyline、分析函数、窗口函数、OLAP多维分析
数据挖掘 — 关联分析、分类分析、聚类分析、KDD过程

一、递归查询

1.1 问题引入

示例：组成trike的零件有哪些？

Assemble关系存储零件组装关系（part → subpart），需要找到组成trike的所有子零件（包括间接子零件）。

关系代数方法（非递归）：

第一层：πR.part, S.subpart(σR.subpart=S.part(ρR(Assemble) × ρS(Assemble)))
第二层：需要三重笛卡尔积
问题：不知道递归深度，无法写固定层数的查询

1.2 DB2递归查询语法

select * from Components C2
where C2.part = 'trike'

（注：课件中此页为DB2递归查询示例入口，具体WITH递归语法详见SQL Server部分）

1.3 SQL Server递归查询

使用 CTE（公用表表达式）+ WITH RECURSIVE 实现递归。

典型结构：

WITH RECURSIVE cte_name AS (
    -- 锚点成员（递归起点）
    SELECT ... FROM ... WHERE ...
    UNION ALL
    -- 递归成员（引用CTE自身）
    SELECT ... FROM ... JOIN cte_name ON ...
)
SELECT * FROM cte_name;

应用场景：

员工-领导层级关系（employees(empid, mgrid)，返回一个员工的所有领导）
零件BOM（物料清单）展开
树形结构遍历（组织机构、分类树）

1.4 Prolog程序

Prolog是说明性语言而非过程性语言，基于逻辑谓词：

事实：对象间的一种关系，或对象的属性
规则：从一事实推出另一事实

示例：

% 事实
likes(bill, cindy).
likes(cindy, bill).
likes(bill, dog).
 
% 规则
likes(cindy, Something) :- likes(bill, Something).
 
% 查询
likes(bill, What).   % What = dog; What = cindy
likes(cindy, What).  % What = bill; What = dog; What = cindy

1.5 Datalog基本结构

Datalog由一组规则构成，用来定义视图，使用位置来识别关系的属性名。

语法规则：

:- 表示”如果”
, 表示”并且”
支持否定（not）
视图可由多条规则定义，结果取并集

示例1：退休老师的姓名和年龄

PROF(P#, PNAME, SAL, AGE, D#)
v1(A, B) :- PROF(O, A, P, B, Q), B > 60.

语义：for all A, B — if (O,A,P,B,Q) ∈ PROF and B > 60, then (A,B) ∈ v1

示例2：税率计算（多条规则）

tax-rate(A, 0) :- PROF(A, B, C, D, E), C < 800.
tax-rate(A, 5) :- PROF(A, B, C, D, E), C >= 800.

示例3：否定的使用（没有选课的学生）

v2(A) :- S(A, B, C, D, E), not v3(A).
v3(A) :- SC(A, M, N).

示例4：视图递归定义（退休老师税额）

retiree-tax(A, T) :- retiree(A, B), tax-rate(A, C), T=B * C / 100.
retiree(A, B) :- PROF(O, A, B, P, Q), P > 60.
tax-rate(A, 0) :- PROF(A, B, C, D, E), C < 800.
tax-rate(A, 5) :- PROF(A, B, C, D, E), C >= 800.

1.6 Datalog中的递归

不动点：f(v) = v
相互递归定义：多个视图互相依赖
递归查询的实现基于不动点计算

二、物化视图

2.1 概念

物化视图（Materialized View）是将视图的计算结果物理存储起来的数据库对象，区别于普通视图（仅存储定义，查询时实时计算）。

核心价值：

预计算常用的聚合/连接结果，大幅加速查询
特别适用于OLAP场景（数据仓库、BI报表）
查询重写（Query Rewrite）：优化器自动将查询改写为访问物化视图

2.2 SQL Server中的物化视图

SQL Server中称为索引视图（Indexed View）：

在视图上创建唯一聚集索引
视图结果物理化存储
查询优化器可自动匹配使用

2.3 Oracle中的物化视图

Oracle提供完整的物化视图机制：

CREATE MATERIALIZED VIEW 语句创建
支持多种刷新方式：快速刷新（增量）、完全刷新、强制刷新
支持查询重写（QUERY REWRITE）

查询重写示例：

原始查询（连接三个大表+聚合）：

SELECT CUSTOMER.CUST_NAME, TIME.MONTH,
       SUM(SALES.SALES_AMOUNT)
FROM SALES, CUSTOMER, TIME
WHERE SALES.CUST_ID = CUST.CUST_ID
  AND SALES.TIME_ID = TIME.TIME_ID
GROUP BY CUSTOMER.CUST_NAME, TIME.MONTH

重写后（直接访问物化视图）：

SELECT CUSTOMER.CUST_NAME, SALES_SUMMARY.MONTH, SALES_SUMMARY.AMT
FROM CUSTOMER, SALES_SUMMARY
WHERE CUSTOMER.CUST_ID = SALES_SUMMARY.CUST_ID

三、数据分区

3.1 背景与动机

数据规模从GB到TB到PB级增长：

电信公司的通话记录
连锁超市的销售记录

分区定义：将数据分散到各自的物理单元中去，以便能分别独立处理，灵活地访问数据，提高效率。

实际需要：分析往往对某种相关性的数据集合进行

某一时段的数据
某一地区的数据
某特定业务领域的数据
日期往往是自然而均匀的分割

二维分区示例（保险业务 × 年份）：

年份	健康保险	人寿保险	意外伤亡保险
1988	分片1	分片2	分片3
1989	分片4	分片5	分片6
1990	分片7	分片8	分片9

3.2 分区的优点

增强可用性：如果表的某个分区出现故障，表在其他分区的数据仍然可用
维护方便：如果表的某个分区出现故障，需要修复数据，只修复该分区即可
均衡I/O：可以把不同的分区映射到磁盘以平衡I/O，改善整个系统性能
改善查询性能：对分区对象的查询可以仅搜索自己关心的分区，提高检索速度（分区裁剪）

3.3 Oracle分区方法

Oracle提供三种分区方法：

（1）范围分区（Range Partitioning）

根据某个属性值的范围，决定将该数据存储在哪个分区上。

CREATE TABLE sales (
    invoice_no NUMBER,
    ...
    sale_date DATE NOT NULL
)
PARTITION BY RANGE (sale_date) (
    PARTITION sales2006_q1
        VALUES LESS THAN (TO_DATE('2006-04-01','YYYY-MM-DD'))
        TABLESPACE ts_sale2006q1,
    ……
    PARTITION sales2006_q4
        VALUES LESS THAN (TO_DATE('2007-01-01','YYYY-MM-DD'))
        TABLESPACE ts_sale2006q4
);

（2）散列分区（Hash Partitioning）

通过分区编号将数据均匀散列到I/O设备上，使得这些分区大小一致。

（3）复合分区（Composite Partitioning）

先使用范围分区，然后在每个分区内再使用散列分区。

列表分区（List Partitioning）示例：

CREATE TABLE emp (
    empno number(4),
    ename varchar2(30),
    location varchar2(30)
)
PARTITION BY LIST (location) (
    PARTITION p1 VALUES ('北京'),
    PARTITION p2 VALUES ('上海','天津','重庆'),
    PARTITION p3 VALUES ('广东','福建'),
    PARTITION p0 VALUES (DEFAULT)
);

3.4 SQL Server分区

分区表

三步创建分区表：

-- 1. 创建分区函数
CREATE PARTITION FUNCTION customer_partfunc(int)
    AS RANGE RIGHT
    FOR VALUES (250000, 500000, 750000);
 
-- 2. 创建分区架构
CREATE PARTITION SCHEME customer_partscheme
    AS PARTITION customer_partfunc
    TO (fg1, fg2, fg3, fg4);
 
-- 3. 对表进行分区
CREATE TABLE customers (
    FirstName nvarchar(40),
    LastName nvarchar(40),
    CustomerNumber int
)
ON customer_partscheme (CustomerNumber);

分区视图（Partitioned View）

将大型表根据某列的数据值范围进行分区，拆分成较小的成员表。每个成员表的数据范围在CHECK约束中定义，使用UNION ALL定义视图。

CREATE VIEW Year1998Sales
AS
SELECT * FROM Jan1998Sales
UNION ALL
SELECT * FROM Feb1998Sales
UNION ALL
……
UNION ALL
SELECT * FROM Nov1998Sales
UNION ALL
SELECT * FROM Dec1998Sales;

查询优化器使用CHECK约束确定哪个成员表包含查询所需行（分区消除）。

四、数据分析

4.1 数据分析流程

关系系统负责计算数据立方体，可视化系统负责显示数据立方体。

常见分析需求：

直方图展示
不同粒度上的聚集函数（roll up & drill down）
交叉表（透视表）

4.2 Red Brick的SQL扩展

Red Brick是早期专注于数据仓库的数据库，提供分析扩展：

N-tile

将所有元组按值大小分为n个连续区间，每个区间的元组个数相同，返回每个区间的平均值。

SELECT percentile, avg(salary)
FROM EMP
GROUP BY N_tile(salary, 10) AS percentile;

Ratio_To_Total

计算每个分组的和在总和中的比例。

Rank

返回值在所有列值中的序号（排名）。

4.3 直方图

四种直方图类型：

类型	定义
等宽直方图	每个桶的宽度区间是一致的
等频(等深)直方图	每个桶的频率粗略地为常数（每个桶包含大致相同个数的邻近样本）
V最优直方图	给定桶的个数，具有最小方差的直方图。方差是每个桶代表的原来值的加权和，权等于桶中值的个数
MaxDiff直方图	考虑每对相邻值之间的差，桶的边界是具有β-1个最大差的对

4.4 中位数

中位数是将排序后的数据集中间位置的值。

计算规则：

元素数目为奇数：就是正中间的那个数
元素数目为偶数：正中间两个数的平均值

示例：

{3, 5, 7, 8, 37} → 中位数是7，平均值是12
{50.2, 25.7, 32.0, 17.2, 18.4, 19.6, 44.3, 22.5, 1000.7} → 中位数25.7
{50.2, 25.7, 32.0, 17.2, 18.4, 19.6, 44.3, 1000.7} → 中位数(25.7+32.0)/2=28.85

SQL Server游标实现：

DECLARE @temp INT, @median INT
SET @temp = (SELECT COUNT(*) FROM sc) / 2
DECLARE my_curs CURSOR FOR
    SELECT GRADE FROM SC ORDER BY GRADE
OPEN my_curs
WHILE(@temp > 0)
    BEGIN
        FETCH my_curs
        @temp = @temp - 1
    END
FETCH my_curs INTO @median

窗口函数实现（更优雅）：

WITH
dt1 AS (SELECT grade, ROW_NUMBER() OVER (ORDER BY grade) AS num FROM SC),
dt2 AS (SELECT COUNT(grade) + 1 AS count FROM dt1),
dt3 AS (SELECT grade FROM dt1, dt2
        WHERE num = FLOOR(count/2e0)
           OR num = CEILING(count/2e0))
SELECT DECIMAL(AVG(grade),10,2) AS median FROM dt3

4.5 Skyline查询

问题引入

找一个便宜并且离海滩近的旅馆。系统无法决定哪些是”最好的”，但会提供所有备选（interesting）旅馆——它们不会在两个维上都比其他任何旅馆差。称为Skyline。

统治（Dominate）定义

称点x统治点y，如果x在所有维上都不比y差，并且至少在一个维上好过y。

例：(price=50, distance=0.8) 统治 (price=100, distance=1.0)

Skyline性质

对任意单调计分函数R，如果p∈M使得R最大，那么p一定在M的Skyline中
对Skyline中的任意一点p，总存在一个单调计分函数，使得p使得它最大（Skyline不会包含无用的点）
统治满足传递性：p统治q，q统治r → p统治r

SQL扩展语法

SELECT…FROM…WHERE
GROUP BY…HAVING…
SKYLINE OF [ DISTINCT ]
    d1 [ MIN | MAX | DIFF ], …,
    dn [ MIN | MAX | DIFF ]
TOP …
ORDER BY…

含义：SKYLINE OF d1 MIN, d2 MAX, d3 DIFF — p(p1,p2,p3)统治q(q1,q2,q3)，如果 p1≤q1, p2≥q2, p3=q3

4.6 分析函数（Analytic Functions）

DB2、Oracle等数据库支持分析函数，语法格式：

FUNCTION_NAME(<argument>, <argument>, …)
OVER (
    <Partition by子句>
    <Order by子句>
    <Windowing子句>
)

组成部分：

Partition by：对表进行分区，类似GROUP BY
Order by：排序
Windowing：窗口定义

窗口子句示例：

PARTITION BY deptno：按照部门分区
ORDER BY salary：按照salary排序进行累计
RANGE BETWEEN 50 PRECEDING AND 150 FOLLOWING：每行对应的数据窗口包含比当前行值大50以及小于150的行（值范围窗口）
ROWS BETWEEN 50 PRECEDING AND 150 FOLLOWING：每行对应的数据窗口是之前50行，之后150行（行窗口）
ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING：从第一行到最后一行

示例1：同部门平均工资

SELECT manager_id, last_name, hire_date, salary,
       AVG(salary) OVER (PARTITION BY manager_id) AS c_mavg
FROM employees;

示例2：滑动窗口平均（前一行+当前行+后一行）

SELECT manager_id, last_name, hire_date, salary,
       AVG(salary) OVER (ORDER BY hire_date
           ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING) AS c_mavg
FROM employees;

示例3：统计与本人工资差距在100内的员工个数

SELECT ename, sal, greater_num + lower_num
FROM (
    SELECT ename, sal,
        COUNT(ename) OVER (ORDER BY sal DESC RANGE 100 PRECEDING) AS greater_num,
        COUNT(ename) OVER (ORDER BY sal ASC RANGE 100 PRECEDING) AS lower_num
    FROM emp
) a;

4.7 窗口聚集

累积聚集（Cumulative Aggregate）

计算从起始到当前月的累计汇总：

SELECT O1.empid,
    CONVERT(VARCHAR(7), O1.ordmonth, 121) AS ordmonth,
    O1.qty AS qtythismonth,
    SUM(O2.qty) AS totalqty,
    CAST(AVG(1.*O2.qty) AS DECIMAL(12, 2)) AS avgqty
FROM dbo.EmpOrders AS O1
  JOIN dbo.EmpOrders AS O2
    ON O2.empid = O1.empid
     AND O2.ordmonth <= O1.ordmonth
GROUP BY O1.empid, O1.ordmonth, O1.qty
ORDER BY O1.empid, O1.ordmonth;

滑动聚集（Sliding Aggregate）

计算最近3个月的滑动窗口：

SELECT O1.empid,
    CONVERT(VARCHAR(7), O1.ordmonth, 121) AS tomonth,
    O1.qty AS qtythismonth,
    SUM(O2.qty) AS totalqty,
    CAST(AVG(1.*O2.qty) AS DECIMAL(12, 2)) AS avgqty
FROM dbo.EmpOrders AS O1
  JOIN dbo.EmpOrders AS O2
    ON O2.empid = O1.empid
    AND (O2.ordmonth > DATEADD(month, -3, O1.ordmonth)
         AND O2.ordmonth <= O1.ordmonth)
GROUP BY O1.empid, O1.ordmonth, O1.qty
ORDER BY O1.empid, O1.ordmonth;

4.8 统计函数

数据库内置的统计分析函数：

函数	含义
VARIANCE	方差
STDDEV	标准差
COVARIANCE	协方差
CORRELATION	相关系数
REGR_SLOPE/REGR_INTERCEPT/REGR_R2	线性回归

方差示例：

SELECT AVG(salary), VARIANCE(salary)
FROM employee
WHERE workdept = 'D11';
-- 平均工资：24677.78，方差：1.885506172839506E7

协方差示例：

SELECT COVARIANCE(salary, bonus)
FROM employee
WHERE workdept = 'D11';
-- 结果：23650.86（正相关：工资越高，奖金越高）
-- COV(X,Y) = E(XY) - E(X)E(Y)

相关系数示例：

SELECT CORRELATION(salary, bonus)
FROM employee
WHERE workdept = 'D11';
-- 结果：0.739（强线性关系）
-- ρXY = COV(X,Y) / √D(X)√D(Y)

线性回归示例（Y = aX + b）：

SELECT REGR_SLOPE(bonus, salary) AS slope,
       REGR_ICPT(bonus, salary) AS intercept
FROM employee
WHERE workdept = 'D11';
-- slope = 0.0125, intercept = 179.313
-- R2 = 0.54624（拟合程度一般）

函数	含义
REGR_SLOPE	返回斜率
REGR_INTERCEPT / REGR_ICPT	返回截距
REGR_R2	返回R²相关系数，衡量拟合程度

4.9 联机分析处理（OLAP）

概念

存在大量分析型应用——要求对大量数据从各个角度进行综合分析（多维分析）。

典型分析应用：

销售金额（指标）从时间、地区、商品类型（维）等角度分析
时间维层次：日、周、月、季、年
地理维层次：城市、地区、省、国家、大区
今年销售量下降的因素分析（时间、地区、商品、销售部门）

多维数据模型

基本组成：维 + 度量

概念	含义	示例
变量（指标）	数据的实际意义，一般是数值度量	销售量、销售额
维	观察数据的特定角度	时间、地区
维的层次	特定角度的不同细节程度	时间维：日→周→月→季→年

多维分析的基本操作

操作	定义
切片（Slice）	从多维数组选定一个二维子集，切出一个”平面”
切块（Dice）	从多维数组选定一个三维子集，切出一个”立方体”
旋转（Pivot）	改变一个报告显示的维方向
上卷（Roll-up）	从细粒度到粗粒度的聚集
下钻（Drill-down）	从粗粒度到细粒度的明细

CUBE与ROLLUP

所有可能的分析需求（3个维的情况）：

每种车型：GROUP BY model
每个年份：GROUP BY year
每种颜色：GROUP BY color
每个年份、每种车型：GROUP BY model, year
每个年份、每种颜色：GROUP BY color, year
每种颜色、每种车型：GROUP BY model, color
全部维度：GROUP BY model, year, color

总行数 = (model个数+1) × (year个数+1) × (color个数+1)

GROUPING函数：产生一个附加列，当用CUBE或ROLLUP添加行时输出1，否则输出0。

WITH CUBE示例：

CREATE VIEW auto_cube(units, model, theyear, color) AS
SELECT SUM(units_sold),
    CASE WHEN (GROUPING(model)=1) THEN 'ALL'
         ELSE ISNULL(model, '????') END,
    CASE WHEN (GROUPING(theyear)=1) THEN 'ALL'
         ELSE ISNULL(theyear, '????') END,
    CASE WHEN (GROUPING(color)=1) THEN 'ALL'
         ELSE ISNULL(color, '????') END
FROM my_cube
GROUP BY model, theyear, color WITH CUBE;

WITH ROLLUP：按层次聚合（CUBE的子集，从最细粒度逐步上卷）。

五、数据挖掘

5.1 经典故事：尿布与啤酒

美国加州某个超市连锁店通过数据挖掘发现：在下班后前来购买婴儿尿布的顾客多数是男性，他们往往也同时购买啤酒。于是经理重新布置货架，把啤酒放在尿布附近，销量成倍增长。

5.2 KDD与数据挖掘的定义

KDD（Knowledge Discovery in Database，数据库中的知识发现）：识别数据中有效的（Valid）、新颖的（Novel）、潜在有用的（Potentially Useful）和最终可被理解（Ultimately Understandable）的模式（Pattern）的非平凡过程。

数据挖掘（Data Mining）：是KDD过程的一个步骤，它是在现实可接受的计算效率限制下，应用数据分析和知识发现算法，在数据的基础上，对模式（Pattern）的特定枚举。

5.3 数据挖掘的任务与方法

任务类别	含义	相关技术
数据划分（Segmentation）	将数据分成不同类别	聚类分析、Bayesian分类、决策树、人工神经网络
依赖性分析（Dependency Analysis）	找出各属性之间的依赖关系	Bayesian网络、关联分析
偏差和奇异点分析	找出与一般数据行为不一致的数据项	聚类分析、奇异点检测
趋势检测（Trend Detection）	时间序列上的综合分析	回归分析、序列模式分析

注：

聚类分析：在预先没有确定类别的情况下，根据数据不同属性将数据分成不同类别（无监督学习）
分类分析：将数据映射到预先定义的数据类别中（有监督学习）

5.4 关联分析（Associations）

目的与含义

发现数据库中数据间的相互关联。给定一组事务集合，推导出数据项间的相关性。

典型例子：98%的顾客在购买电动剃须刀的同时会购买一些电池。

核心概念

概念	定义
项集（itemset）	项的集合，包含k个项的称为k-项集
事务（Transaction）	每个事务T是项的集合，T ⊆ I
项集出现频率	D中包含该项集的事务数
频繁项集	出现频率 ≥ 最小支持度 × 事务总数；频繁k-项集记作Lk
关联规则 A⇒B	A⊂I, B⊂I, A∩B=∅
强规则	同时满足最小支持度和最小置信度的规则

支持度（Support）

满足规则的记录数与总记录数的比，表明规则模式在数据库中出现的频度。

Support(X ⇒ Y) = P(X ∪ Y) = 同时购买X和Y的交易数 / 总交易数

置信度（Confidence）

满足规则的记录数与出现被分析数据项的记录数之比。

Confidence(X ⇒ Y) = P(Y|X) = 同时购买X和Y的交易数 / 购买X的交易数

示例：

规则 A ⇒ C：support = 50%, confidence = 66.6%
规则 C ⇒ A：support = 50%, confidence = 100%

关联分析的基本步骤

两步法：

发现频繁项集：找出所有出现频率 ≥ 最小支持度的项集
生成强关联规则：从频繁项集产生满足最小置信度的规则

Apriori算法

Apriori性质（先验法则）：一个频繁项集的任何非空子集肯定也是一个频繁项集。

反单调：一个集合如果不能通过测试，则它的任何超集也不能通过测试

算法核心：从Lk-1产生Lk

连接步（Self-Join）：

INSERT INTO Ck
SELECT p.item1, p.item2, …, p.itemk-1, q.itemk-1
FROM Lk-1 p, Lk-1 q
WHERE p.item1=q.item1, …, p.itemk-2=q.itemk-2,
      p.itemk-1 < q.itemk-1

剪枝步（Pruning）：

for all item sets c in Ck do
    for all (k-1)-subsets s of c do
        if (s is not in Lk-1) then delete c from Ck

示例：

L3 = {abc, abd, acd, ace, bcd}
连接步：abc+abd → abcd；acd+ace → acde → C4候选
剪枝步：acde中ade不在L3中，删除 → C4 = {abcd}

从频繁项集生成关联规则

步骤：

对于每个频繁项集l，产生l的所有非空子集
对每个非空子集s，如果 support(l) / support(s) ≥ min_conf，则输出规则 s ⇒ (l-s)

由于规则由频繁项集产生，每个规则自动满足最小支持度。

示例（l = {I1, I2, I5}，min_conf = 70%）：

规则	置信度	输出?
I1 ⇒ I2 ∧ I5	2/6 = 33%	✗
I2 ⇒ I1 ∧ I5	2/7 = 29%	✗
I5 ⇒ I1 ∧ I2	2/2 = 100%	✓
I1 ∧ I2 ⇒ I5	2/4 = 50%	✗
I1 ∧ I5 ⇒ I2	2/2 = 100%	✓
I2 ∧ I5 ⇒ I1	2/2 = 100%	✓

5.5 分类分析（Classifiers）

含义

有一个记录集合和一组标记（类别），先为每个记录赋予标记，再对同类记录的特征进行描述。

描述方式：

显式描述：一组规则定义
隐式描述：一个数学模型或公式

广泛应用：医疗诊断、性能预测、选择购物、信誉证实等。

两个步骤

步骤1：构建模型（训练）

训练集（Training Set）：已知类标号的元组集合
有指导的学习（Supervised Learning）
输出模型：决策树、分类规则、数学公式等

步骤2：模型应用（预测）

对未知数据对象进行分类

示例：信用卡信誉分类

记录集合：持卡人记录
标记：良好、普通、较差
特征描述：信誉良好持卡人的特征（收入25000以上、年龄45-55、居住XYZ地区）
用途：对新持卡人自动分类

示例：顾客购物分类

属性：姓名、年龄、收入、职业、信誉度
标记：是否购买计算机
应用：定向营销

5.6 决策树分类（ID3算法）

决策树结构

内部节点：表示一个与属性值相关的判断（测试属性）
边：表示判断的结果
叶节点：类别标识

信息增益（Information Gain）

设S是s个样本的集合，类标号有m个不同值，定义m个不同类Ci：

I(s1,…,sm) = -Σ pi·log2(pi)，其中 pi = si/s（期望信息 / 熵）

根据属性A划分的熵：

E(A) = Σ (|sj|/|S|) · I(s1j,…,smj)

信息增益：

Gain(A) = I(s1,…,sm) - E(A)

选择信息增益最大的属性作为分裂属性。

ID3算法

算法：Generate_decision_tree
输入：训练样本samples；候选属性集合attribute_list
输出：决策树

步骤：
  ⑴ 创建节点N
  ⑵ if samples都在同一个类C then
        返回N作为叶节点，以类C标记
  ⑶ if attribute_list为空 then
        返回N作为叶节点，标记为samples中最普通的类
  ⑷ 选择attribute_list中具有最高信息增益的属性test_attribute
  ⑸ 标记节点N为test_attribute
  ⑹ for each test_attribute中的已知值ai
        由节点N长出一个条件为test_attribute=ai的分枝
  ⑺ 设si是samples中test_attribute=ai的样本的集合
  ⑻ if si为空 then
        加上一个树叶，标记为samples中最普通的类
      else
        加上一个由Generate_decision_tree(si, attribute_list-test_attribute)返回的节点

示例：购买计算机分类

训练数据的类标号属性buys_computer有两个值{yes, no}，yes有9个样本，no有5个样本。

各属性信息增益：

属性	信息增益
age	0.246
income	0.029
student	0.151
credit_rating	0.048

→ 选择age作为根节点分裂属性。

最终规则：

IF age = "<=30" AND student = "no"  THEN buys_computer = "no"
IF age = "<=30" AND student = "yes" THEN buys_computer = "yes"
IF age = "31…40"                     THEN buys_computer = "yes"
IF age = ">40" AND credit_rating = "excellent" THEN buys_computer = "no"
IF age = ">40" AND credit_rating = "fair"      THEN buys_computer = "yes"

5.7 聚类分析（Clustering）

含义

聚类是把一组对象按照相似性归成若干类别，即”物以类聚”。

同一类别内个体距离尽可能小
不同类别间个体距离尽可能大

与分类的区别：聚类是无监督学习，预先不知道类别。

应用：市场或客户分割、模式识别、基因分类、Web文档分类等。

K-Means算法

算法：k-平均（K-Means）
输入：簇的数目k，包含n个对象的数据库
输出：k个簇，使平方误差最小

步骤：
  1. 任意选择k个对象作为初始的簇中心
  2. Repeat
       根据簇中对象的平均值，将每个对象赋给最类似的簇
       更新簇的平均值，即计算每个簇中对象的平均值
     Until 平方误差小于某个阈值或不再发生变化

特点：对噪音数据敏感（异常值会拉偏簇中心）。

六、本章知识图谱

SQL高级实践
├── 递归查询
│   ├── CTE + WITH RECURSIVE (DB2, SQL Server)
│   ├── 应用：BOM展开、层级遍历
│   └── 理论基础：Prolog、Datalog、不动点计算
├── 物化视图
│   ├── 索引视图 (SQL Server)
│   ├── Materialized View (Oracle)
│   └── 查询重写 (Query Rewrite)
├── 数据分区
│   ├── 范围分区 / 散列分区 / 列表分区 / 复合分区 (Oracle)
│   ├── 分区函数 + 分区架构 + 分区表 (SQL Server)
│   └── 分区视图 (Partitioned View)
├── 数据分析
│   ├── 直方图（等宽/等频/V最优/MaxDiff）
│   ├── 中位数（窗口函数实现）
│   ├── Skyline查询（统治关系）
│   ├── 分析函数（窗口函数：ROWS/RANGE）
│   ├── 统计函数（方差/标准差/协方差/相关系数/线性回归）
│   └── OLAP多维分析（CUBE/ROLLUP/GROUPING）
└── 数据挖掘
    ├── KDD过程
    ├── 关联分析（Apriori算法、支持度、置信度）
    ├── 分类分析（决策树ID3、信息增益）
    └── 聚类分析（K-Means）

关联笔记

来源：田浩然上传的资料/0A102 数据库设计与实践/chap05 SQL实践.ppt 提取方式：PowerPoint二进制TextCharsAtom记录提取（图片型PPT，文本量较完整）

知识库

探索

chap05 SQL实践 - 数据库设计与实践

chap05 SQL实践 - 数据库设计与实践

概述

一、递归查询

1.1 问题引入

1.2 DB2递归查询语法

1.3 SQL Server递归查询

1.4 Prolog程序

1.5 Datalog基本结构

1.6 Datalog中的递归

二、物化视图

2.1 概念

2.2 SQL Server中的物化视图

2.3 Oracle中的物化视图

三、数据分区

3.1 背景与动机

3.2 分区的优点

3.3 Oracle分区方法

（1）范围分区（Range Partitioning）

（2）散列分区（Hash Partitioning）

（3）复合分区（Composite Partitioning）

列表分区（List Partitioning）示例：

3.4 SQL Server分区

分区表

分区视图（Partitioned View）

四、数据分析

4.1 数据分析流程

4.2 Red Brick的SQL扩展

N-tile

Ratio_To_Total

Rank

4.3 直方图

4.4 中位数

4.5 Skyline查询

问题引入

统治（Dominate）定义

Skyline性质

SQL扩展语法

4.6 分析函数（Analytic Functions）

4.7 窗口聚集

累积聚集（Cumulative Aggregate）

滑动聚集（Sliding Aggregate）

4.8 统计函数

4.9 联机分析处理（OLAP）

概念

多维数据模型

多维分析的基本操作

CUBE与ROLLUP

五、数据挖掘

5.1 经典故事：尿布与啤酒

5.2 KDD与数据挖掘的定义

5.3 数据挖掘的任务与方法

5.4 关联分析（Associations）

目的与含义

核心概念

支持度（Support）

置信度（Confidence）

关联分析的基本步骤

Apriori算法

从频繁项集生成关联规则

5.5 分类分析（Classifiers）

含义

两个步骤

5.6 决策树分类（ID3算法）

决策树结构

信息增益（Information Gain）

ID3算法

示例：购买计算机分类

5.7 聚类分析（Clustering）

含义

K-Means算法

六、本章知识图谱

关联笔记

关系图谱

目录

反向链接