Chap. 22 Advanced Applications

OLAP & Data Warehouse

∙OLAP (On-Line Analytical Processing)

- What kinds of queries to be processed?

⇒ Multidimensional aggregation/summary of large data.

Ex) Find 'the total sales' 'for all customers' 'last month'.

Who was 'our best customer' 'for this item' 'last year'?

cf.) Statistical analysis - statistical packages

⇒ mean/median, variance, distributions, correlation, regression, etc

Ex) crosstab table (3-dimensional data cube)

item location	TV		Computer		Both_Items
	sales	count	sales	count	sales	count
Asia Europe North America	15 12 28	300 250 450	120 150 200	1000 1200 1800	135 162 228	1300 1450 2250
All_Regions	45	1000	470	4000	525	5000

item

location

data

Ex) p.701 Fig. 21.1 and Fig. 21.2

p.702 Fig. 21.3

Ex) report writers

ꋻRollup - Transforming 'finer' granularity data into 'coarser' granularity one

⇒ Rollup can be performed on each of the 2n subsets of the n dimensions.

ꋻDrilldown - Transforming 'coarser' granularity data into 'finer' granularity one

item location	TV		Computer		Both_Items
	sales	count	sales	count	sales	count
Asia Korea Japan China Europe Germany Italy France North America USA Canada	15 … 12 … 28 …	300 … 250 … 450 …	120 … 150 … 200 …	1000 … 1200 … 1800 …	135 … 162 … 228 …	1300 … 1450 … 2250 …
All_Regions	45	1000	470	4000	525	5000

∙Characteristics

- OLAP: OLTP 보다 많은 데이터를 읽고, 처리해야 함.

⇒ 한 trans.이 수 GB ～ 수백 GB의 데이터를 읽어서, 합계, 평균값, 시계열 변화 등의 계산 작업을 수행

⇒ Batch processing

	OLTP	OLAP
목적	데이터 수집 (getting the data in)	데이터 분석 (getting the data out)
적용업무	업무처리 (daily operation)	의사결정 지원(DSS)
데이터내용	업무별 데이터 집합(transaction-driven) ⇒ 데이터의 구조가 복잡	주제별 데이터 집합 (subject-oriented) ⇒ 데이터의 구조가 단순
데이터 시간성	현재 데이터	과거 및 현재 데이터
데이터상세정도	상세	요약(aggregated)
데이터 갱신성	강함(dynamic, 자주 갱신)	read-only(static, snap shot 보관)
응답시간	performance-sensitive (2, 3초 내지 몇 분의 1초)	query 전용으로서 조건이 완화(수초내지는 몇 분까지 가능)
데이터 관리기간	과거 30일 내지 90일 정도에 걸친 데이터	과거 5년 내지 10년간에 걸친 시계열적인 데이터
query의 성격	예측이 가능하며 주기적 ⇒ predefined/well-defined queries	예측하기 어렵고 특수 ⇒ ad-hoc queries
데이터 모델	정규화, mission-critical	비정규화, read-only 및 index에 의존
가치	비즈니스 운영	비즈니스 선도
동시 user 수	많음	적음

- DB and DW

DB for OLTP		DW for OLAP
Complex data structures (3NF databases)		Multidimensional data structures
Few	Indexes	Many
Many	Joins	Some
Normalized Tables (to guarantee data consistency)	Duplicated Data	Denormalized Tables (to optimize query performance)
Rare	Derived Data and Aggregates	Common

∙DW Architecture

① Basic DW System

Integrator

Extractor

Info.

Source

Extractor

Info.

Source

Extractor

Metadata

Info.

Source

Data

Warehouse

Query

Processor

User

User

…

…

Analysis/

Reporting/

Mining

Summary/Raw

Data

② DW System with a Staging Area and Data Marts

Integrator

Data

Warehouse

Extractor

Info.

Source

Extractor

Info.

Source

Extractor

Metadata

Info.

Source

…

…

Query

Processor

User

User

Analysis/

Reporting/

Mining

Summary/Raw

Data

Staging

Area

Purchasing

Sales

Inventory

∙Data Structure: Multidimensional 'cube'

⇒ MOLAP & ROLAP

1. MOLAP(Multidimensional OLAP)

- DB가 물리적으로 여러 개의 차원을 갖고, 이 공간에 데이터를 저장.

- 사용자가 각각의 차원 축들에 대한 값들을 지정하여 필요한 데이터를 검색.

- Adv.: MOLAP에서는 비어 있는 cell들이 많이 생기게 되므로, 대용량의 시스템에 적합하지 않음.

- Disadv.: cell 단위의 데이터 비교가 가능.

Ex) p.701 Fig. 21.2

Ex) Express (Oracle)

2. ROLAP(Relational OLAP)

- MOLAP과는 달리 기존의 RDBMS를 기반으로 한 star schema 혹은 snowflake schema를 이용

- 사용자 측면에서는 schema에 의해 제공되는 다차원 시야로 인해서 사용 중인 DB가 마치 다차원 DB인 것처럼 보여짐.

- Adv.: ROLAP은 MOLAP에 비해 훨씬 적은 공간으로 유지가 가능하여 대용량의 데이터를 처리하는데 유리.

- Disadv.: 데이터는 RDBMS에 의해 레코드 단위로 관리가 되어 cell 단위의 비교가 불가능

Ex) Discoverer (Oracle),  MetaCube (Informix)

①Star schema: Data from 'all' levels in a dimension is stored in 'one' dimension table.

School - 'Fact' table

Seoul

Inchon

Daejun

…

location

'Dimension'

table

government

state/city

private

owner

'Dimension'

table

school_ID

location

owner

…

no_of_student

size

…

'star query' ⇒

owner location	government		city/state		private
	students	size	students	size	students	size
Seoul Inchon Daejun …	300 250 450 …	15 12 28 …	1000 1200 1800 …	120 150 200 …	1300 1450 2250 …	135 162 228 …
Total	…	…	…	…	…	…

ꋻStructure

① One or more very large 'fact' tables: Contain the 'primary' info. (데이타)

② A no. of much smaller 'dimension' table: Contains info. about entries for a particular attr. in the fact table. (차원값)

⇒ The analogy of a data 'cube': A space where facts are stored at the intersection of n dimensions.

owner(G, C/S, P)

location(S, I, D, …)

data(St, Si)

ꋻAdv.:

Provide a 'direct and intuitive' mapping between the business entities being analyzed by end users and the schema design.

Provide highly optimized performance for typical DW queries.

ꋻStar query: Join between a fact table and a no. of dimension tables.

⇒ The 'cost-based' optimizer recognized star queries and generates efficient execution plans.

⇒ Not recognized by the 'rule-based' optimizer.

②Snowflake schema: Data from 'different' levels in a dimension is stored in 'different' tables.

productNo

name

categoryNo

unitPrice

profit

…

product

salepersonID

name

storeID

quota

salesperson

store

storeID

locationNo

floorSize

noEmployees

location

locationNo

street

city

state

category

categoryNo

name

desc

Item_sold

orderNo

salespersonID

customerID

date

storeID

productNo

…

quantity

unitPrice

totalPrice

…

ꋻThe dimension data has been 'grouped' into multiple tables instead of one large table.

⇒ Normalize dimensions to eliminate 'redundancy'.

ꋻAdv.:

Saves space by removing redundancy.

Disadv.:

Increases the no. of dimension tables

⇒	Requires more foreign key joins.

⇒ More complex queries.

⇒ Reduces	query performance.

∙DW Design

- Identify which info. belongs to a central 'fact' table and

which info. belongs to its associated 'dimensional' tables.

- Schema 설계 단계

①처리 요구사항을 정의하고, 처리의 중심대상을 fact 테이블로 정의.

⇒ Subject-oriented info. 정의

②fact 테이블에 저장할 중요 attribute들을 결정.

③fact 테이블의 데이터를 분석할 주요 분석요인(factor)을 차원으로 결정.

④fact 테이블에 대한 집계(aggregation) 사실의 수준을 결정.

⑤차원의 설명을 포함하여 dimension 테이블의 attribute들을 정의.

⑥집계사실의 저장방법을 결정: Star/snowflake schema

⇒ A star schema optimizes performance by keeping queries 'simple' and providing 'fast' response time.

⇒ The Oracle Co. recommends that you choose a star schema unless you have a 'clear' reason not to. (Oracle9i DW Guide, p.2-4)

Ex) 교원 star schema

Case 1: 모든 키(년도키, 설립키, 지역키, 남녀키, 교사키, 자격증키)를 차원테이블로 설정.

차원테이블

연도별       설립별          지역별        남녀별

년도키

설립키

설립명

지역키

지역명

남녀키

남녀명

교사별       자격증별

교사키

교사명

자격증키

자격증명

사실테이블

교원수

년도키	설립키	지역키	남녀키	교사키	자격증키	교원수

Case 2: 표준 키(년도키, 설립키, 지역키, 남녀키) 및 자격증키를 차원테이블로 설정.

차원테이블

연도별      설립별     지역별      남녀별    자격증별

년도키

설립키

설립명

지역키

지역명

남녀키

남녀명

자격증키

자격증명

사실테이블

교사별 교원수

년도키	설립키	지역키	남녀키	자격증키

총계	교장	교감	주임교사	교사	양호교사	임시교사

Case 3: 표준 키(년도키, 설립키, 지역키, 남녀키) 및 교사키를 차원테이블로 설정.

Case 4: 표준 키(년도키, 설립키, 지역키, 남녀키)만 차원테이블로 설정.

∙Implementation/Performance

- Transforms logical design into physical design

⇒ Uses the 'DW functions' of the RDBMS

Ex) DB design

Entities

Relationships

Attributes

Unique

Identifiers

Tables

Logical Design

Integrity Constrains

- Primary Key

- Foreign Key

- Not Null

Columns

Indexes

Materialized

Views

Dimensions

Physical Design

Ex) DW design

Start schema ⇒ Physical design

- Star query: SQL aggregation (SUM, COUNT, AVG, etc.) with GROUP BY

ꋻCUBE extension to GROUP BY

ꋻROLLUP extension to GROUP BY

ꋻGROUPING functions

ꋻGROUPING SETS extension to GROUP BY

ꋻetc.

Ex)  Generate a multidimensional table, Fig. 21.2

SELECT color, size, SUM(number)

FROM sales

GROUP BY color, size WITH CUBE

Key

Aggregated data

Color	Size	Number
…	…	…

① CUBE Extension

ꋻCalculate 'all possible' combinations of aggregations such as SUM, COUNT and AVG.

⇒ Calculates all the subtotals from multiple and independent dimensions.

⇒ Generates the info. needed in cross-tabulation reports.

Ex)	CUBE(time, region, department)

Ex) Oracle9i

prod_id

cust_id

time_id

channel_id

amount_sold

quantity_sold

prod_id

prod_desc

cust_id

country_id

time_id

year_desc

month_desc

date_desc

channel_id

channel_desc

products

customers

sales

times

channels

SELECT	channel_desc, month_desc, country_id,

TO_CHAR(SUM(amount_sold), '9,999,999,999') SALES$

FROM	sales, customers, times, channels

WHERE	sales.time_id = times.time_id	AND

sales.cust_id = customers.cust_id	AND

sales.channel_id = channels.channel_id	AND

channles.channel_desc	IN ('Direct Sales', 'Internet')	AND

times.month_desc	IN ('2002-03', '2002-04')	AND

customers.country_id	IN ('KR', 'JP')

GROUP BY CUBE(channel_desc, month_desc, country_id)

CHANNEL_DESC	MONTH_D	CO SALES$

----------------------	--------- -- ---------

Direct Sales	2002-03	KR	1,000

Direct Sales	2002-03	JP	1,000

Direct Sales	2002-03	2,000

Direct Sales	2002-04	KR	1,500

Direct Sales	2002-04	JP	1,500

Direct Sales	2002-04	3,000

Direct Sales	KR	2,500

Direct Sales	JP	2,500

Direct Sales	5,000

Internet	2002-03	KR	1,000

Internet	2002-03	JP	1,000

Internet	2002-03	2,000

Internet	2002-04	KR	1,500

Internet	2002-04	JP	1,500

Internet	2002-04	3,000

Internet	KR	2,500

Internet	JP	2,500

Internet	5,000

2002-03	KR	2,000

2002-03	JP	2,000

2002-03	4,000

2002-04	KR	3,000

2002-04	JP	3,000

2002-04	6,000

KR	5,000

JP	5,000

10,000

② ROLLUP Extension

ꋻCalculates aggregations at 'increasing' levels of a 'single' dimension.

⇒ From the most detailed up to a grand total.

ꋻCreates progressively higher-level subtotals, moving 'from right to left' thru the list of grouping columns.

Ex)	ROLLUP(year, month, day)

ROLLUP(country, state, city)

Ex)	SELECT	channel_desc, month_desc, country_id,

TO_CHAR(SUM(amount_sold), '9,999,999,999') SALES$

FROM	sales, customers, times, channels

WHERE	sales.time_id = times.time_id	AND

sales.cust_id = customers.cust_id	AND

sales.channel_id = channels.channel_id	AND

channles.channel_desc	IN ('Direct Sales', 'Internet')	AND

times.month_desc	IN ('2002-03', '2002-04')	AND

customers.country_id	IN ('KR', 'JP')

GROUP BY ROLLUP(channel_desc, month_desc, country_id)

CHANNEL_DESC	MONTH_D	CO SALES$

----------------------	--------- -- ---------

Direct Sales	2002-03	KR	1,000

Direct Sales	2002-03	JP	1,000

Direct Sales	2002-03	2,000

Direct Sales	2002-04	KR	1,500

Direct Sales	2002-04	JP	1,500

Direct Sales	2002-04	3,000

Direct Sales	5,000

Internet	2002-03	KR	1,000

Internet	2002-03	JP	1,000

Internet	2002-03	2,000

Internet	2002-04	KR	1,500

Internet	2002-04	JP	1,500

Internet	2002-04	3,000

Internet	5,000

10,000

subtotaling: moving 'from right to left'

① first-level subtotal

② second-level subtotal

③ third-level subtotal

③ GROUPING Functions

ꋻEnables to 'programmatically' determine 'subtotal' rows and its exact 'level' of aggregation.

⇒ Returns 1 when it encounters a NULL value created by a ROLLUP/CUBE.

Ex)	SELECT	channel_desc, month_desc, country_id,

TO_CHAR(SUM(amount_sold), '9,999,999,999') SALES$,

GROUPING(channel_desc)	AS	CH,

GROUPING(month_desc)	AS	MO,

GROUPING(country_id)	AS	CO

FROM	sales, customers, times, channels

WHERE	sales.time_id = times.time_id	AND

sales.cust_id = customers.cust_id	AND

sales.channel_id = channels.channel_id	AND

channles.channel_desc	IN ('Direct Sales', 'Internet')	AND

times.month_desc	IN ('2002-03', '2002-04')	AND

customers.country_id	IN ('KR', 'JP')

GROUP BY ROLLUP(channel_desc, month_desc, country_id)

CHANNEL_DESC	MONTH_D	CO SALES$	CH   MO  CO

----------------------	--------- -- ----------- ---- ---- ----

Direct Sales	2002-03	KR	1,000	0	0	0

Direct Sales	2002-03	JP	1,000	0	0	0

Direct Sales	2002-03	2,000	0	0	1

Direct Sales	2002-04	KR	1,500	0	0	0

Direct Sales	2002-04	JP	1,500	0	0	0

Direct Sales	2002-04	3,000	0	0	1

Direct Sales	5,000	0	1	1

Internet	2002-03	KR	1,000	0	0	0

Internet	2002-03	JP	1,000	0	0	0

Internet	2002-03	2,000	0	0	1

Internet	2002-04	KR	1,500	0	0	0

Internet	2002-04	JP	1,500	0	0	0

Internet	2002-04	3,000	0	0	1

Internet	5,000	0	1	1

10,000	1	1	1

⇒ A program can easily identify

① The detail rows: A mask of "0 0 0" on the CH, MO and CO columns.

② The first level subtotal rows: A mask of "0 0 1".

④ GROUPING SETS Extension

ꋻComputing a full cube creates a heavy processing load.

⇒ Replacing CUBE with GROUPING SETS can significantly increase performance.

ꋻ'Selectively' specify the set of groups that you want to create without computing the 'whole' cube.

Ex)	SELECT	channel_desc, month_desc, country_id,

TO_CHAR(SUM(amount_sold), '9,999,999,999') SALES$

FROM	sales, customers, times, channels

WHERE	sales.time_id = times.time_id	AND

sales.cust_id = customers.cust_id	AND

sales.channel_id = channels.channel_id	AND

channles.channel_desc	IN ('Direct Sales', 'Internet')	AND

times.month_desc	IN ('2002-03', '2002-04')	AND

customers.country_id	IN ('KR', 'JP')

GROUP BY GROUPING SETS( (channel_desc, month_desc, country_id),

(channel_desc, country_id),

(month_desc, country_id) )

⇒ Aggregates over only 3 groupings, NOT all the 8(2*2*2) groupings.

- Other 'enhanced' SQL capabilities for analytical processing (Oracle9i)

ꋻRanking Functions

ꋻWindowing Aggregate Functions

ꋻReporting Aggregate Functions

ꋻLAG/LEAD Functions

ꋻFIRST/LAST Functions

ꋻLinear Regression Functions

ꋻInverse Percentile Functions

ꋻHypothetical Rank and Distribution Functions

ꋻWIDTH_BUCKET Function

ꋻUser-Defined Aggregate Functions

ꋻCASE Expressions

- Materialized View: Pre-computed aggregation/summary tables in advance

ꋻ일반적인 view는 물리적으로 존재하지 않지만, materialized view는 실제 데이터를 갖고 있음.

ꋻ미리 연산되어 있는 데이터를 사용할 수 있고, 자동으로 변경사항들이 갱신됨.

Ex) Materialized view 생성 - rollup

회원

회원ID	회원명	지역	메일주소
tykim mypark hwkim hslee	김태영 박미영 김현우 이현수	서울 전주 서울 수원	…

회원년수입

회원ID	1999	2000	2001
tykim mypark hwkim hslee	10,000K 25,000K 23,000K 33,000K	…	…

CREATE MATERIALIZE VIEW 지역별회원수익_MV

REFRESH FAST ON COMMIT

AS SELECT A.지역, SUM(B.1999), SUM(B.2000), SUM(B.2001)

FROM 회원정보 A, 회원년수입 B

WHERE A.회원ID = B.회원ID

GROUP BY A.지역

BUILD IMMEDIATE;

지역별회원수익_MV

지역	1999	2000	2001
서울 전주 수원 …	…	…	…

- Table partition

ꋻ하나의 table을 나누어서 (partitioning) 서로 다른 tablespace에 각각 할당함.

ꋻUtilize 'parallel' processing

Ex) Executes 'joins' in parallel.

Ex) Create a new tablespaces.

SQLWKS> create tablespace users02

2>   datafile '/oradb/u02/oradata/COMORA2/users02.dbf'

3>   size 10M

Statement processed.

SQLWKS> select * from SYSFILES

TSNAME            FNAME	BLOCKS

--------------------------------------------------- ----------	SYSTEM	/oradb/u01/oradata/COMORA2/system01.dbf	40960

RBS	/oradb/u01/oradata/COMORA2/rbs01.dbf	7680

TEMP	/oradb/u01/oradata/COMORA2/temp01.dbf	512

TOOLS	/oradb/u01/oradata/COMORA2/tools01.dbf	12800

USERS	/oradb/u01/oradata/COMORA2/users01.dbf	512

USERS02	/oradb/u02/oradata/COMORA2/users02.dbf	5120

6 rows selected.

① Range Partitioning

ꋻThe most common type of partitioning that is often used with dates.

ꋻSkew problem

Ex) Range partitioning a table.

SQLWKS> CREATE TABLE dept_range (deptno	number(2) primary key,

2>	dname	char(14),

3>	location	char(13) )

4>  PARTITION BY RANGE(deptno)

5>  (PARTITION dept1 VALUES LESS THAN (500) TABLESPACE USERS,

6>   PARTITION dept2 VALUES LESS THAN (MAXVALUE) TABLESPACE	USERS02)

7>

CREATE TABLE dept	(deptno	number(2) primary key,

*

ORA-00439: feature not enabled: Partitioning

② Hash Partitioning

ꋻThe ideal method for distributing 'evenly' across devices.

ꋻGood and easy-to-use alternative to range partitioning

ꋻUses a linear hashing algorithm

ꋻShould define the no. of partitions by a power of 2 (e.g., 2, 4, 8).

Ex) Hash partitioning a table.

CREATE TABLE dept_hash (deptno	number(2) primary key,

dname	char(14),

location	char(13) )

PARTITION BY  HASH(deptno)

PARTITIONS     2

STORE IN	(USERS, USERS02)

③ List Partitioning

ꋻSpecifies a list of discrete values for the partitioning column.

ꋻCan group unordered and unrelated sets of data.

Ex) List partitioning a table.

CREATE TABLE dept_list (deptno	number(2) primary key,

dname	char(14),

location	char(13) )

PARTITION BY  LIST(location)

(PARTITION dept_west VALUES IN ('California', 'Arizona')

TABLESPACE USERS,

PARTITION dept_east VALUES IN ('Virginia', 'New York')

TABLESPACE USERS02)

④ Composite Partitioning

ꋻCombines range and hash partitioning.

ꋻFirst, distribute data into partitions according to boundaries established by the partitioning ranges.

ꋻThen, uses a hashing algorithm to further divide the data into 'subpartitions' within each range partition.

Ex) Composite partitioning a table.

CREATE TABLE dept (deptno	number(2) primary key,

dname	char(14),

location	char(13) )

PARTITION BY RANGE(deptno)

SUBPARTITION BY HASH(dname) SUBPARTITIONS 4

(PARTITION dept1 VALUES LESS THAN (500),

PARTITION dept2 VALUES LESS THAN (MAXVALUE))

⇒ The total no. of subpartitions is 8 (= 2×4).

- RAID: Disk Striping

ꋻTo avoid I/O bottlenecks, all tablespaces accessed by 'parallel' operations should be 'striped'.

ꋻStriping divides the data of a 'large' table into small portions and stores them on 'separate' datafiles on 'separate' disks.

⇒ 하나의 tablespace를 나누어서 (partitioning) 서로 다른 disk에 각각 할당함.

Ex) Striping tablespaces & OPS (Oracle Parallel Server)

⇒ 4 CPUs, 2 controllers and 5 tablespaces

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

tablespace 1

tablespace 2

tablespace 3

tablespace 4

tablespace 5

controller 1

controller 2

- Hash cluster: Speedup in reading a large table (대량 데이터 조회)

⇒ Disk I/O를 최소화

ꋻCluster: 관련있는 두 개 이상의 table들을 물리적인 위치에 같이 저장.

⇒ Search key 값을 interleaving함.

Ex) 물리적인 cluster를 생성.

CREATE CLUSTER 회원_cluster (회원번호 char(10))

SIZE 512	; the expected avg. row size (bytes)

STORAGE (initial 100K next 50k)

Ex) Cluster에 두 개 이상의 table들을 함께 저장.

CREATE TABLE 회원 (회원번호 char(10),

…	…    )

CLUSTER 회원_cluster(회원번호);

CREATE TABLE 회원년수입 (회원번호 char(10),

…	…    )

CLUSTER 회원_cluster(회원번호);

ꋻSearch key값에 index를 만들거나 'hash' cluster를 사용하여 access 속도 향상.

⇒ Oracle에서는 내부적으로 hash function을 제공함.

⇒ cluster의 생성시 hash key 값을 정의하면 바로 원하는 tuple의 access가 가능함.

Ex)	CREATE CLUSTER 회원_cluster (회원번호 char(10))

SIZE 512

HASHKEYS 1009	; the next highest prime no. to

the no. of search keys (=1000)

STORAGE (initial 100K next 50k)

ꋻData의 update와 insert가 빈번한 경우에는 cluster를 유지하기 위해서 많은 작업이 필요함.

- Bitmap Index

ꋻ일반 index의 leaf node는 ROW_ID를 가리키고 있으나, bitmap index는 bit 값을 가지고 있음.

ꋻ이 bit 값이 미리 정의된 function을 통하여 ROW_ID로 변환.

ꋻbit 값을 사용하기 때문에 disk 사용을 최소화.

ꋻDW와 같은 대용량 DB에서는 index의 크기가 커지므로 사용하면 효과적.

Ex) CREATE BITMAP INDEX idx_회원 ON 회원(회원명);

30

10

40

30

40

30

40

50

30

40

bit value

30	1 0 0 1 0

key value

row_id

key value

key value

40	0 0 1 1 0

mapping function

Ex)  customers

cust_id	cust_gender	cust_marital_status
70 80 90 100 110 120 130 140	F F M F F M M M	married single married single married

bitmap index on cust_gender & cust_marrital_status

	gender='M'	gender='F'	m_status='married'	m_status='single'	m_status=NULL
cust_id 70 cust_id 80 cust_id 90 cust_id 100 cust_id 110 cust_id 120 cust_id 130 cust_id 140	0 0 1 0 0 1 1 1	1 1 0 1 1 0 0 0	0 1 0 0 1 0 0 1	0 0 1 0 0 1 0 0	1 0 0 1 0 0 1 0

Query: "How many of our married customers are female?

SELECT COUNT(*)

FROM customers

WHERE cust_marrital_status = 'married' AND cust_gender ='F'

⇒ Count the no. of 1s after the AND operation.

	gender='F'	m_status='married'	AND
cust_id 70 cust_id 80 cust_id 90 cust_id 100 cust_id 110 cust_id 120 cust_id 130 cust_id 140	1 1 0 1 1 0 0 0	0 1 0 0 1 0 0 1	0 1 0 0 1 0 0 0

⇒ To identify additional attributes that satisfy the criteria, use the resulting bitmap to access the customer table after a 'bitmap-to-rowid' conversion.

ꋻPrimarily intended for DW applications.

⇒ Users 'query' the data rather than 'update' it.

⇒ Not suitable for OLTP with large no.'s of concurrent transactions modifying the data.

ꋻThe adv. is greatest for 'low cardinality' col.'s in which the no. of distinct values is small.

Ex) customer_gender: Only two distinct values

A table with 1,000,000 rows and a col. with 1,000 distinct values.

ꋻMost effective for queries that contain 'multiple conditions' in the WHERE clause.

⇒ Rows that satisfy 'some', but not all, conditions are 'filtered out' before the table itself is accessed.

⇒ This improves response time, often 'dramatically'.

⇒ The majority of indexes of DW should be bitmap indexes.

ꋻBitmap join index: A bitmap index for the 'join' of two or more tables.

⇒ Much more efficient in 'storage' than materialized join views.

Ex)  sales

time_id	cust_id	amount
01-JAN-2002 01-JAN-2002 01-JAN-2002 01-JAN-2002 01-JAN-2002 01-JAN-2002	70 80 90 100 110 120	2291 114 553 0 195 280

CREATE BITMAP INDEX sales_customers_gender_bjix

ON sales(customers.cust_gender)

FROM customers, sales

WHERE sales.cust_id = customers.cust_id

⇒ For each value in a col. of a table, a bitmap index stores the 'rowids' of corresponding rows

bitmap join index: sales_customers_gender_bjix

	cust_gender='M'	cust_gender='F'
sales row 1 sales row 2 sales row 3 sales row 4 sales row 5 sales row 6	0 0 1 0 0 1	1 1 0 1 1 0

Query: SELECT sales.time_id, customers.cust_gender, sales_amount

FROM sales, customers

WHERE sales.cust_id = customers.cust_id

Result:

time_id	cust_gender	amount
01-JAN-2002 01-JAN-2002 01-JAN-2002 01-JAN-2002 01-JAN-2002 01-JAN-2002	F F M F F M	2291 114 553 0 195 280

- 대량 데이터 load: SQL*Loader

Ex) emp_data.ctl script file 작성

LOAD DATA

NFILE *

INTO TABLE dept

FIELDS TERMINATED BY ',' OPTIONALLY ENCLOSED BY '"'

(deptno, dname, location)

BEGINDATA

12,"RESEARCH","SARATOGA"

10,"ACCOUNTING","CLEVELAND"

11,"ART","SALEM"

13,"FINANCE","BOSTON"

21,"SALES","PHILA"

22,"SALES","ROCHESTER"

42,"INT'L","SAN FRAN"

$sqlldr scott/tiger emp_data

- Tablespace 복사: Speedup in copying a large table

Data Mining

∙Overview

-	Why DM? Data Explosion

ꋻData doubles every 20 months

ꋻIncrease in the number and size of DBs

Ex)	NASA - Earth observation satellites, 1 picture/sec

Human genome - several billion genetic bases

US census data - lifestyle and subculture of the US

- How to analyze these DBs (raw data)

ꋻThere is a gap between data generation and data understanding

⇒ ‘Intelligent’ data analysis will be useful and valuable

Ex)	- AA uses frequent flyer DB to find its ‘better’ customers for specific market promotions.

- Bank uses customers loan and credit information to derive 'better' loan approval and bankrupt protection.

- Package-goods manufacturers use the scanned supermarket data to measure the effect of their promotions and to look for shopping 'patterns'.

- School data? students (achievements/behaviors/etc.), teachers, facilities, etc.

- DM: Finding 'patterns' from large amount of data.

⇒ What is a pattern?

ꋻInformation/knowledge or 'better description' of large data

ꋻUsed for decision/prediction.

Ex) Young men with annual incomes greater than ￦40,000K are most likely to buy a SUV.

- Related Topics

ꋻStatistics: Numeric data - mean, variance, distributions, correlation, etc.

ꋻData Warehousing: Text/Numeric data - OLAP/Multidimensional analysis

ꋻMachine Learning: Text/Semantic data - knowledge/pattern discovery

Machine Learning

Data Warehousing

Statistics

- Structure

① Input

ꋻRaw data from DB

ꋻInformation from data dictionary - definition, scope

ꋻAdditional domain knowledge

ꋻUser defined biases that provide high level focus

② Output - knowledge/pattern

ꋻNew Domain Knowledge

ꋻFeedback of the discovered knowledge to generate new knowledge

③ DB issues

ꋻDynamic data (time sensitive; e.g. weight & height, pulse rate)

ꋻIrrelevant fields (zip codes, pulse rate, sex)

ꋻMissing data

ꋻNoise and uncertainty

ꋻMissing field

- Topics

ꋻData structure: pattern description

Ex) rules, decision trees, frames, etc

(Polygon (name: rectangle)

(no. of angles: 4)

(no. of sides: 4) )

Humidity

Outlook

Windy

Sunny

Cloudy

Rain

High

Normal

True

False

'Go to

picnic'

'Go to

picnic'

'Not go to

picnic'

'Not go to

picnic'

'Go to

picnic'

ꋻProcessing algorithm: characterization/classification, association, sequence,   approximation, etc.

⇒ performance: information credibility (NOT 100% accurate)

Ex)	characterization/classification - classifying rows

association - finding a relationship between attributes.

approximation - fuzzy question

ꋻIntelligent query answering/optimization

⇒ Deductive DBs

ꋻImplementation: language, visualization

Ex) Data Mining Query Language (DMQL)

Source	Processing (Algorithm)	Knowledge Base (DS)	Query Processing	Implementation (language/ system)	Application
a large amount of (distributed) numeric/ text data ⇒ training data set	join(OLAP) statistical summarization characterization association approximation	multidimensional cube table, graph rule frame decision tree		statistical package, knowledge processing language, reporting tool etc.

- Techniques used

ꋻStatistics

ꋻMachine Learning

ꋻInformation Theory

ꋻFuzzy Set

[그림 ] DM 프로세스

∙The Objective of Education

Let students acquire

① How to Extract

② How to Represent	Knowledge/Wisdom

③ How to Apply

⇒ We call these abilities 'Intelligence'.

Education in Korea: ③

What about other countries?

∙Background

- Pattern Def.

ꋻExtraction of implicit, previously unknown and potentially useful ‘information’ from ‘data’

ꋻGiven a set of facts (Data) F, a language L, measure of certainty C, pattern: a statement S in L that describes the ‘relationship’ among a subset Fs of F with certainty C, such that Fs is a ‘simpler’ representation than the enumeration of all facts in Fs.

Ex) association rules, a decision tree for characterization

ꋻDiscovered Knowledge: The ‘output’ of a program that monitors the set of facts in a DB and produce patterns.

- Four Main Characteristics in Knowledge Discovery from DB

① Representation: High-Level Language

⇒ Expressed by high level language

⇒ Understood and used directly by 'human' users

ꋻDiscovery must be represented in a form appropriate for the intended user.

ꋻRules:	A → B forms casual ‘chains’ or ‘network’

Ex) Association rule

∀transactions T, buys(T, 'bread') → buys(T, 'milk')

- Natural Language

- Formal Logic

- Mathematics

- Diagram

- Common representation

of domain knowledge

- programming  language

- declarative formalism

e.g., SQL

Human

Discovery

System

Computer

⇒ 'Forms' for pattern

Ex) Rule: If condition/antecedent then conclusion/consequent

IF age < 25 and Driver-Education-Course = No

THEN At-Fault-Accident = Yes

WITH likelihood = 0.3

ꋻInter-field patterns: related values of field in the same record

⇒ 'association' rule

Ex) procedure = surgery implies days in hospital > 5

ꋻInter-record patterns: aggregated over group of records or identify useful clusters/classes

⇒ 'classification/clustering/categorization' rule

Ex)	'profit making' companies

'money losing' companies

⇒ Able to input to another program (e.g. expert system)

② Accuracy

⇒ Patterns are often probabilistic rather than deterministic

ꋻMissing and erroneous data

ꋻInherent indeterminism of the underlying real world causes

Ex) 50% chance of rain tomorrow

ꋻsampling

⇒ Expressed by 'measure' of uncertainty

ꋻProof of success

ꋻStandard deviation

ꋻBelief measures

ꋻLinguistic uncertainty - fuzzy sets

Ex) near

ꋻVisual presentation by density, size, and shading

ꋻSampling technique for large DB: Accuracy of results depends on sample size

③ Interesting Results

⇒ Patterns are novel and potentially 'useful'.

⇒ Patterns that are completely unrelated to ‘current goals’ are NOT considered as knowledge.

Ex) Patterns that are relating at-fault-accident to a driver‘s age	is not useful to auto sales figures.

⇒ Pattern + ‘interesting’ results = knowledge

Ex) Age > 16 is not an interesting pattern for driver since all drivers require age > 16.

④ Efficiency

⇒ Running 'times' for large-sized DB are predictable and acceptable

⇒ The discovery process should be efficiently implemented on a computer.

⇒ An algorithm is considered efficient if the run time and space used are a ‘polynomial’ function of low degree of input length n.

Ex)	Efficient algorithms for restricted concept 'classes'

⇒ classification/clustering

- Disjunctive concepts, (A∧B∧C)

A B C

- Disjunction of classes of conjunctions of no more than k literals

(A∨B)∧(C∨D)∧(E∨F), k=2.

A∨B C∨D E∨F

- Discovery Algorithm

ꋻA learning algorithm takes the data set and its accompanying information as input and returns a statement (e.g., a concept) representing the results of the learning as output.

⇒ Data sets can be a file of records in DB

ꋻProblems in learning DB

⇒ DB are

Dynamic

Incomplete

Noisy

Much larger than typical machine learning data sets

⇒ Much of work in learning DB focuses on overcoming these complications!

ꋻThree Problems

① Classification: Finding rules that 'partition' the given data into disjoint groups.

Ex) Customer classification in a Bank

∀customers C,

C.occupation='doctor' AND C.income≥￦50,000K

→ C.credit=excellent

C.occupation='professor' AND C.income≥￦40,000K

→ C.credit=good

②Association: Finding 'relationships' among items/attributes.

Ex) Association rule

∀transactions T, buys(T, 'bread') → buys(T, 'milk')

③Sequence: Find 'time-series' pattern

Ex) stock prices on a sequence of days.

"Whenever bond rates go up for a day, the stock prices go down within 2 days.

association -

'inter-field' pattern

classification -

'inter-record' pattern

sequence -

'time-series' pattern

A	B		A'	B'

- Two methods of DM

①Supervised: The user is involved 'directly' in the knowledge discovery process.

ꋻThe user has 'primary' responsibility for discovering rules.

⇒ The DB plays a 'supporting' role.

ꋻMethod

①The user makes up a 'hypothesis' and runs tests on the DB.

②There may be several iterations involving successive 'refinement' of the hypothesis.

ꋻData 'visualization' helps users to examine large volumes of data and to detect patterns visually.

②Unsupervised: The knowledge discovery system is responsible for 'automatically' discovering knowledge from the DB by detecting 'patterns' and 'correlations' in the DB.

ꋻStrongly influenced by work in machine learning (AI).

ꋻDM 'algorithms' are used for pattern discovery.

DM Algorithms

Classification

Association

Sequence

DB -

training set

KB

Domain Knowledge

Query Processing

User

Induction

New Case

Answer

'guide the mining process'

Deduction

∙Applications

- Discovery of Knowledge in DB

ꋻMedicine

ꋻFinance

ꋻAgriculture

ꋻSocial and Education

ꋻMarketing and Sales

ꋻInsurance

ꋻEngineering and Science

ꋻMilitary

ꋻLaw Enforcement

ꋻPublishing

ꋻetc.

∙Future Directions

- Domain knowledge: How to effectively use domain knowledge to discover knowledge.

- Efficient Algorithms

ꋻRestrict rule type

ꋻHeuristic and approximate algorithms

ꋻSampling

ꋻParallel computing

ꋻOODB

ꋻDeductive DB

- Incremental methods

ꋻEfficiently keep pace with changes in Data

ꋻIncremental discovery system, reuse their discoveries and make more complex discoveries.

- Interactive Systems

ꋻKnowledge analyst included in the discovery loop

ꋻUse human judgement, machine computation power

ꋻNeed information to be presented on a human-oriented form (text, sound, visuals)

- Integration/Implementation

Ex) Data mining server

DB 1

DB n

DB Servers

Browser

…

Data Collector

User 1

Clients

DM Server

User m

Wrapper 1

…

Wrapper n

Query processor/

Reporter

Wired/Wireless Network

processing

bean m

Knowledge

Mediator

processing

bean 1

Application

Client

Training

Data

KB

1. Classification (Clustering/Categorization)

∙Problem Def.

- Partition the given data into disjoint groups.

Ex)	Find efficient algorithms for restricted concept 'classes'

- Disjunctive concepts,

(A∧B∧C)

A B C

- Disjunction of classes of conjunctions of no more than k literals

(A∨B)∧(C∨D)∧(E∨F), k=2.

A∨B C∨D E∨F

Ex) Store categorization

Successful/Average/Unsuccessful stores

Given a 'profile' of each category of stores (domain knowledge)

⇒ How to decide each profile?

Ex) Best N problem

A company may be interested in finding the best N candidates to whom a ski package should be mailed.

Ex) Customer classification in Bank

IF	…	Then Loan ≥ 30,000K

IF	…	Then Loan ≥ 20,000K

IF	…	Then Loan ≥ 10,000K

IF	…	Then Loan ≥  5,000K

Not-Loanable

⇒ Find a set of rules from credit history data (age, income, address, etc...)

∙Basic Algorithm

Ex) Customer classification in a Bank

- Training set: The credit of each tuple is already known.

Customers

custID	custName	degree	income	…	credit
…	…	D(doctorate) M(master) B(bachelor) N(none)	A(over 75,000K) B(50,000K to 74,999K) C(25,000K to 49,999K) D(under 24,999K)	…	4(excellent) 3(good) 2(fair) 1(poor)

- Algorithm

① Starts with antecedents consisting of only a single attribute, e.g. degree.

② The data are divided into groups based on this attribute.

IF all or most of the tuples in each group have the 'same' credit value,

THEN output a set of rules based on the attribute(s) AND stop.

③ The partitioning at the 'next' level is made on one of the other attribute, e.g. income.

IF all the attributes are considered, THEN stop.

④ Repeat ② & ③.

Ex) Step ②

degree

1

1

1

1

1

2

2

2

3

3

3

4

4

2

4

N

B

M

D

credit

∀customers C, C.degree='D' → C.credit=4

C.degree='M' → C.credit=3

C.degree='B' → C.credit=2

C.degree='N' → C.credit=1

Ex) Step ③

p.707, Fig.21-4

∀customers C, C.degree='M' AND C.income='A' → C.credit=4

C.degree='M' AND C.income='B' → C.credit=3

…

∙Improvements

- The no. of rules can be 'reduced' by merging rules that generate the same category together.

- The I/O cost can be reduced by techniques that grow multiple branches of a tree with a 'single' scan of the tuples.

- etc.

2. Association

∙Problem Def.

- Finding 'relationships' among items/attributes.

Ex) Shelf planning problem

- 90% of transactions that purchase bread and butter also purchase milk.

∀transactions T, buys(T,'bread') AND buys(T,'butter') → buys(T,'milk')

- Association rule X→Y with

① Support: Usefulness/Interestingness

⇒ The fraction of transactions that contains X∪Y

⇒ The ratio Cardinality(X∪Y)/Cardinality(all trans.)

② Confidence: Likelihood

⇒ The ratio Support(X∪Y)/Support(X)

Ex) Transactions

Trans. ID	Items bought
1000 1001 1002 1003	A, B, C A, C A, D B, E, F

Let min. support 50% and min. confidence 50%, we have

rule A→C with	S(A→C) = 2/4 = 50%

S(A) = 3/4 = 75%

C(A→C) = 50/75 = 66.7%

rule C→A with	S(C→A) = 2/4 = 50%

S(C) = 2/4 = 50%

C(C→A) = 50/50 = 100%

Ex) buys(x, 'diapers') → buys(x, 'beers') [support=10%, confidence=40%]

Customer

buys beer

Customer

buys both

Customer

buys diaper

All Customers

support = 10%

confidence=40%

∙Basic Algorithm

- Training set

Transactions

Trans. ID	Items bought
1000 1001 1002 1003 …	A, B, C A, C A, D B, E, F …

① From the item set, I = {A, B, C, … , Z}, │I│=n, we must consider 'all subsets' of the set I.

⇒ The no. of subsets considered = 2n - (n + 1)

② For each subset, we must check whether there is a 'sufficient' no. of transactions in which all the items in the subset are purchased.

⇒ Check 'support'

③ Choose only those rules that have 'strong' support.

Ex) Check support by using a 'bitmap'

	{A,B}, {A,C}, {A,D} … {Y,Z} {A,B,C} … {A,B,… Z}
T0 T1 T2 … Tk	1 1 1 1
support

∙Improvement

- Consider only some sets.

⇒ If a subset occurs in 'too small' a fraction of the transactions, it is eliminated and none of its 'supersets' needs to be considered.

3. Sequence

∙Problem Def.

- Find patterns of 'ordering' data

c.f) association: No ordering

Ex) 'Temporal' data related to item sold

dress followed by matching shoes

Stock market data

'When AT&T stock goes up on 'two consecutive' days AND

DEC stock does not fall during this period

Then IBM stock goes up the 'next' day 75% of the time.

Video rental

Customers typically rent 'Star Wars', then 'Empire Strikes Back', and then 'Return of the Jedi'.

∙Basic Algorithm

- Training set

Transactions

TransID	ItemsBought	custID	time
1000 1001 1002 1003 …	1, 2, 3 1, 3 2, 4 2, 5, 6 …	A B B A …	09:02 09:03 09:05 09:15 …

Customer (temporal ordering) sequence

A's sequence = {(1,2,3) (2,5,6)}

B's sequence = {(1,3) (2,4)}

Sequential pattern

{(1,3) (2)} with support=100%

{(1,3) (4)} with support=50%

…

⇒ Find the maximal sequences among all sequences that have a certain user-specified minimum support.