45
Data Warehousing para Data Warehousing para Mineração de Dados Mineração de Dados Jacques Robin CIn-UFPE

Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Embed Size (px)

Citation preview

Page 1: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Data Warehousing para Data Warehousing para Mineração de DadosMineração de Dados

Jacques RobinCIn-UFPE

Page 2: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Funcionalidades do data warehouseFuncionalidades do data warehouse

Integração de dados:• integração de plataformas (1-3)• integração de modelos

de dados (1-3)• integração de esquemas (1)• integração de valores

(nomes, unidades, etc, 2,3) Transformação de dados:

• re-modelagem de dados (1)• discretização de dados (1-3)• normalização de escala e

distribuição (1-3)

Limpeza de dados (2,3) Seleção de dados

• seleção de atributos (1-3)• amostragem de registros (2,3)

Derivação de novos dados:• novos atributos (1-3)• novas relações (1-3)• hierarquias conceituais (1-3)

Consolidação de dados• construção de novos índices

(2-4)• materialização de visões (2-4)• agregação de valores (2-4)

Etapas:1. Criação do esquema do data warehouse 2. Carga inicial dos dados 3. Atualização periódica dos dados 4. Processamento de consultas

Tarefas:

Page 3: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integração de dadosIntegração de dados

Objetivo:• fornecer para usuário e software externo interface de consulta

e manipulação de dados homogêneo• escondendo heterogeneidade subjacente das fontes de dados

Dimensões de heterogeneidade:• Modelo de dados: relacional, O-R, OO, multi-dimensional,

semi-estruturado, dedutivo, temporal, ...• Esquema: relações, atributos, chaves, restrições de integridade• Codificação dos valores: unidades, nomes• Linguagem de consulta e manipulação • SGBD• Sistema operacional• Hardware

Page 4: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar vários BD OLTP relacionais no Integrar vários BD OLTP relacionais no data warehouse: integração de data warehouse: integração de

plataformaplataforma SGBD diferentes:

• Largamente resolvido pela adoção de padrões linguagem de consulta: SQL-92, SQL-99 API encapsulando todos os serviços de um SGBD relacional:

ODBC, OLE DB Sistemas operacionais diferentes:

• Largamente resolvido pela escassez de opções: Windows, Unix pelo fornecimento da parte do vendedores de SGBD de versões

para a maioria dos sistemas operacionais Hardware diferentes:

• Largamente abstraído pelo sistema operacional ou SGBD

Page 5: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar vários BD OLTP relacionais no Integrar vários BD OLTP relacionais no data warehouse: integração de data warehouse: integração de

esquemaesquema

Heterogeneidade semântica:• Homonímia:

relação ou atributo com mesmo nome em 2 bancos porém com semântica diferente, i.e., associados a conceitos do

mundo real diferente na cabeça dos 2 DBAs ex, atributo tipo em BD1 pode ser marca em BD2 e modelo em BD3

• Polisemia: relação ou atributo com mesma semântica porém com nomes diferente em cada esquema se não identificado pode gerar redundância e inconsistência

• Redundância: tabela ou atributo de BD1 pode ser derivada a partir das tabelas ou

atributo de BD2, via visões ou agregações

Page 6: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar vários BD OLTP relacionais no Integrar vários BD OLTP relacionais no data warehouse: integração de data warehouse: integração de

esquemaesquema Heterogeneidade esquemática:

• mesmos conceitos modelados como atributos em BD1 e como valores em BD2

Professor I nteligênciaArtificial

Mineraçãode Dados

Banco deDados

Carol no no yesGeber yes no noJ acques yes yes no

Prof Cursoacs BDglr I Aj r I Aj r Mineração de Dados

Heterogeneidade estrutural:• Relações e atributos com mesma semântica• porém estruturados diferentemente• ex, repartição diferente dos atributos entre as relações

Page 7: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar vários BD OLTP relacionais no Integrar vários BD OLTP relacionais no data warehouse: integração de data warehouse: integração de

esquemaesquema

Restrições de integridades:• tipos diferentes para mesmo atributo• ex, tipo do atributo mês:

tipo pré-definido mês, string, inteiro, {“Janeiro”, ..., “Dezembro”}, {“Jan”, ..., “Dez”}, {“January”, ..., “December”}, {1, .., 12}, {01, ... , 12}

• valores autorizadas diferentes para mesmo atributo• relevância de um atributo em função do valor de um outro

codificado em BD1 e não em BD2 ex, numero de parto quando sexo = masculino

Page 8: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar vários BD OLTP relacionais no Integrar vários BD OLTP relacionais no data warehouse: integração de data warehouse: integração de valoresvalores

Atributos categóricos:• conflitos de nomes• ex, “Internacional Business Machine” x “IBM” x “I.B.M.”

Atributos numéricos:• unidades implíticas• ex, 35o Celsius? Farenheit? Kelvin?

Page 9: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar vários BD OLTP relacionais no Integrar vários BD OLTP relacionais no data warehouse: técnicasdata warehouse: técnicas

GUI integrado para:• edição de esquemas• visualização e busca de dados• cálculo de estatísticas sobre dados• acesso a recursos lingüísticos de grande porte

dicionário de siglas, abreviações, nome próprios, sinônimos wordnets, terminologias especializadas

• acesso a ontologias gerais e especializadas Meta-dados:

• já existentes nas fonte • ou então criadas para a integração

Mineração de dados:• análise de correlação• indução de esquema com programação em lógica indutiva

Page 10: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar BD Integrar BD O-R e OOO-R e OO no data no data warehouse: integração de modelos de warehouse: integração de modelos de

dadosdados Modelos O-R e OO são semanticamente mais ricos do

que o modelo relacional Modelo integrado O-R ou OO:

• Como construir hierarquias conceituais para conversão E-R O-R ou OO ?

• Como gerar oids ?• Como gerar ligações entre oids a partir de chaves entre

tabelas ? Modelo integrado E-R:

• Como achatar hierarquias conceituais para conversão O-R ou OO E-R ?

• Como gerar chaves entre tabelas a partir de oids entre objetos ?• Porque perder informação ?

Page 11: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Divergência de modelo: relacional x O-Divergência de modelo: relacional x O-R/OOR/OO

I SBN Título Autor Editor Anointeiro string string string year1-556860 Data Mining: Concepts and Techniques J . Han NULL 20011-556860 Data Mining: Concepts and Techniques M. Kamber NULL 20011-988360 Benchmark Handbook for Databases NULL J im Gray NULL

Page 12: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar Integrar flatflat files no data warehouse: files no data warehouse: integração de modelos de dadosintegração de modelos de dados

Sistemas de arquivos não fornece serviços de BD:• linguagem de consulta declarativa (sério para DW)• acesso otimizado a memória segundaria (inconveniente

para DW)• transações (irrelevante para DW)

Abordagens:• criar um esquema de BD a partir dos atributos do flat e

povoar BD com os dados do flat• manter gerenciamento dos dados no arquivo chato via

re-implementação ad-hoc da alguns dos serviços de BD• ambos requer desenvolvimento de um parser do flat

Page 13: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar Integrar flatflat files no data warehouse: files no data warehouse: integração de modelos de dadosintegração de modelos de dados

Modelo flat semanticamente mais pobre do que o modelo relacional• representa única entidade em um formato desnormalizado

precisa quebrar tabela única em várias? como?• não representa restrições de integridade

como gerá-las automaticamente? como garantir seu respeito no sistema de arquivso sub-

jacente?

Page 14: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Integrar BD Integrar BD semi-estruturadosemi-estruturado no data no data warehouse: integração de modelos de warehouse: integração de modelos de

dadosdados Modelo semi-estruturado x modelo relacional

• tipágem fraco no lugar de forte• esquema pulverizado dentro dos dados (dados auto-descritivas)• atributos compartilhados no lugar de chaves

Modelo integrado semi-estruturado:• como pulverizar esquema sem perder informação ?• como representar tipágem forte e restrições de integridade ?

Modelo integrado relacional:• como construir esquema unificado, externo aos dados

a partir dos esquema pulverizado, embutido nos dados ?• como criar tipagem forte a partir de tipagem fraco ?• como criar atributos compartilhados a partir de chaves ?

Page 15: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

I SBN Título Autor Editor Anointeiro string string string year1-556860 Data Mining: Concepts and Techniques J . Han NULL 20011-556860 Data Mining: Concepts and Techniques M. Kamber NULL 20011-988360 Benchmark Handbook for Databases NULL J im Gray NULL

Divergência de modelo: Divergência de modelo: relacional x semi-estruturado relacional x semi-estruturado

{livro: &l1{isbn string: ”1-556860”, título string: “Data Mining: Concept and Techniques”, autor {string: “J. Han”, string: “M. Kamber”} ano integer: 2001}, livro: &l2{isbn integer: 1988360, título string: “Benchmark Handbook for Databases”, editor string: “Jim Gray”}}

Page 16: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

ArquiteturaArquiteturas de data s de data

warehousewarehouse

Q ue ry/re p o rt Ana lysis Da ta m ining

O LAP se rve r O LAP se rve r

To p tie r: fro nt-e nd to o ls

M id d le tie r: O LAP se rve r

Bo tto m tie r: d a ta wa re ho use se rve r

Da ta

O utp ut

Extra c t C le a n

Tra nsfo rm Lo a d

Re fre sh

Da ta wa re ho use Da ta m a rtsM o nito ring

M e ta d a ta re p o sito ry

O p e ra tio na l d a ta b a se s Exte rna l so urc e s

Ad m inistra tio n

Page 17: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Metodologias de desenvolvimento Metodologias de desenvolvimento de data warehousede data warehouse

Ente rp rise d a ta

wa re ho use

M ulti-tie r d a ta

wa re ho use

Distrib ute d d a ta m a rts

Da ta m a rt

De fine a hig h-le ve l c o rp o ra te d a ta m o d e l

Da ta m a rt

M o d e l re fine m e nt M o d e l re fine m e nt

Page 18: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Projeto lógico de data warehouse: Projeto lógico de data warehouse: especificação do esquema analíticoespecificação do esquema analítico

Selecionar as tabelas operacionais relevantes das fontes subjacentes para o modelo analítico

Selecionar os atributos relevantes dessas tabelas Possivelmente definir atributos e relações (tabelas) derivados de

granularidade suficiente para descoberta de insights por OLAP ou mineração

Escolher um modelo de dados analítico• estrala, floco de neve, constelação

Particionar os atributos relevantes e derivados em:• atributos da(s) tabela(s) de fatos do modelo analítico• atributos das tabelas de dimensões do modelo analítico• atributos não dimensionais (i.e., ao longo dos quais não há agregação)• chaves ligando as tabelas

Definir as funções de agregação para cada par (medida,dimensão) Definir as hierarquias conceituais de cada dimensão

Page 19: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Projeto Projeto lógico lógico de data de data

warehouse: warehouse: exemploexemplo

c usto m e r cust_ID

C 1 . . . . . .

nam e Sm ith , Sa ndy

. . .

. . .

address 546 3 E H as tings, B urnaby,

BC V5 A 4S9 , C anada . . .

age 21 . . . . . .

inc om e $27 000

. . .

. . .

cred it_in fo 1

. . .

. . .

. . .

. . .

. . .

. . .

e m p lo ye e em pl_ID

E55 . . .

nam e Jones, J ane

. . .

category hom e en tertainm ent

. . .

g roup m a nager

. . .

salary $18 ,00 0

. . .

com m iss ion 2% . . .

b ra nc h branc h_ID

B 1 . . .

nam e C ity S quare

. . .

addre ss 369 C am bie St., Vancouve r, B C V5L 3A2 , C anada

. . .p u rc ha se s

trans_ID T100

. . .

cust_ID C 1 . . .

em pl_ID E55 . . .

date 09/21/98

. . .

tim e 15:45

. . .

m e thod_paid Vis a . . .

am ount $13 57.00

. . .ite m s_ so ld

trans_ID T100 T100 . . .

item _ID I3 I8

. . .

q ty 1 2

. . .wo rks_a t em pl_ID

E55 . . .

b ra nch_ID B 1 . . .

ite m item _ID

13 18 . . .

nam e h igh -res-TV m ultid isc-

C D play

bra nd Tos hiba Sanyo

. . .

category h igh resolution

m ultid isc . . .

type TV

C D p la yer . . .

price $98 8.00 $36 9.00

. . .

p la ce_m ade Japan Japan

. . .

supplier N ik oX

M usicFront . . .

cost $60 0.00 $12 0.00

. . .

time dimension tabletime_key day day_of_week month quarter year

sales fact table

time_key item_key branch_key location_key dollars_sold units_sold

item dimension tableitem_key item_name brand type supplier_key

branch dimension table

branch_key branch_name branch_type

location dimension table

location_key street city_key

supplier dimension tablesupplier_key supplier_type

city dimension table

city_key city province_or_state country

Page 20: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

ROLAP:• Armazena dados em tabelas

relacionais• Lento porém versátil• Acesso a células de cuboidenvolve muitas junções, varrimento

MOLAP:• Armazena dados em arrays de

dimensões N• Sem acesso a granularidade

mínima (i.e., única transações)• Acesso a células de cuboid direto

(complexidade constante?)

HOLAP (OLAP Híbrido):• Duplica dados• Tabelas para dados atômicos• Arrays para agregados• Flexível e rápido de execução• Custoso em memória e

desenvolvimento Questões:

• até que nível de granularidade duplicar dados no array ?

• que agregados calcular com antecedência ?

Projeto físico de data warehouse:Projeto físico de data warehouse:tabelas x arraystabelas x arrays

Page 21: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

RID ite m c ityR1 R2 R3 R4 R5 R6 R7 R8

H C P S H C P S

V V V V T T T T

RID H CR1 R2 R3 R4 R5 R6 R7 R8

1 0 0 0 1 0 0 0

0 1 0 0 0 1 0 0

P S0 0 1 0 0 0 1 0

0 0 0 1 0 0 0 1

RID V TR1 R2 R3 R4 R5 R6 R7 R8

1 1 1 1 0 0 0 0

0 0 0 0 1 1 1 1

Ba se ta b le Ite m b itm a p ind e x ta b le C ity b itm a p ind e x ta b le

No te : H fo r Ò ho m e e nte rta inm e nt,Ó C fo r Ò c o m p ute r,Ó P fo r Ò p ho ne ,Ó S fo r Ò se c urity,Ó V fo r Ò Va nc o uve r,Ó T fo r Ò To ro nto .Ó

Projeto físico de data warehouse:Projeto físico de data warehouse:índicesíndices bitmapbitmap para OLAP para OLAP

Adequado para atributos com poucas valores possíveis• Conciso: 1 bit para cada valor• Rápido: comparação, junção e agregação por aritmética binária

Para atributos com muitos valores:• compressão no pré-processamento permite usar índices bitmap

Page 22: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Projeto físico de data warehouse:Projeto físico de data warehouse:índices de índices de junçãojunção para OLAP para OLAP

Permite acesso direto ao valor de uma medida a partir de coordenadas multi-dimensionais

“Simula” array multi-dimensional com tabelas Economize custosos varrimentos e junções

J o in ind e x ta b le fo r lo c a tio n/sa le s

lo c a tio n sa le s_ ke y. . . M a in Stre e t M a in Stre e t M a in Stre e t . . .

. . . T57 T238 T884 . . .

J o in ind e x ta b le fo r ite m /sa le s

ite m sa le s_ ke y. . . So ny-TV So ny-TV . . .

. . . T57 T459 . . .

J o in ind e x ta b le linking two d im e nsio ns lo c a tio n/ite m /sa le s

ite mlo c a tio n sa les_ ke y. . . M a in Stre e t . . .

. . . So ny-TV . . .

. . . T57 . . .

Page 23: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Projeto físico de data warehouse:Projeto físico de data warehouse:criação de índicescriação de índices para mineração de para mineração de

dadosdados

índices invertidos:• armazenar juntas na memória colunas no lugar de linhas

• a,d,g,b,e,h,c,f,i no lugar de a,b,c,d,e,f,g• junto com índices bitmap chega a acelerar 100 vezes

índices aleatórios (random)• coluna suplementar na criação/atualização do warehouse• permite rápida extração de amostras aleatória durante

processamento striding index

• para extraír amostras representativa da distribuição de valores no banco

a b cd e fg h i

Page 24: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Projeto físico de data warehouse:Projeto físico de data warehouse:visões virtuais x materializadasvisões virtuais x materializadas

Materializar:• junções freqüentes em tabelas redundantes• agregações em tabelas redundantes• i.e., desnormalizar

Problema: • compromisso tempo x espaço

definir quais junções e agregações materializar

Page 25: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Projeto físico de data warehouse:Projeto físico de data warehouse:armazenamento de valores agregadosarmazenamento de valores agregados

Page 26: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Carga inicial e atualização periódicaCarga inicial e atualização periódicade dados: problemática e abordagensde dados: problemática e abordagens

Como não atrapalhar o rendimento das fontes OLTP?• Continuamente mantém no background uma cópia histórica

de curto prazo• Essa cópia é usada para a carga e a atualização

Atualização incremental ? Manutenção da consistência e validade dos dados

derivados:• atributos derivados• relações derivadas (visões materializadas) • agregações derivadas

Page 27: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Processamento eficiente de consultas Processamento eficiente de consultas OLAP: problemática e abordagensOLAP: problemática e abordagens

Tradução ingênua das consultas OLAP em SQL ineficiente

Ordem das junções• em último junção com tabela de fato

já ela ocupa a maioria esmagadora do espaço no banco• junções de N tabelas simultaneamente como operação sub-

jacente (no lugar do que aninhamento de junções binárias) Ordem de cálculo dos sub-cuboids no reticulado de

cuboids

Page 28: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Reticulado de CuboidesReticulado de Cuboides

sup p lie r

all

tim e, ite m , lo c a tio n, sup p lie r

ite m , lo c a tio ntim e, lo c a tio nite m , sup p lie rtim e, sup p lie r

tim e, lo c a tio n, sup p lie rite m , lo c a tio n, sup p lie r

lo c a tio n, sup p lie r

tim e, ite m , sup p lie r

tim e ite m lo c a tio n

tim e, ite m

tim e, ite m , lo c a tio n

0-D (a p e x) c ub o id

1-D c ub o id s

2-D c ub o id s

3-D c ub o id s

4-D (b a se ) c ub o id

Page 29: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Sistema de Informação Federados Sistema de Informação Federados (SIF)(SIF)

ArquivosEstruturados

Interfaces emformulários

BDRelacional

BD orientadoa objetos

Internet

Programa de interface

Programa de interface

Programa de interface

Programa de interface

Máquina de Execução

Page 30: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Visões do mundo

Descrições das fontes:- conteúdo- capacidades

Máquina de execuçãoselect, project, join, ...

Geradorde

Planos

Interface com oUsuário

Raciocínio relevante

Planejamento lógico

Planejam. de execução

Plano de execução

Consulta

Respostas

Sistema de Informação Federados Sistema de Informação Federados (SIF)(SIF)

Page 31: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Sistema de Informação Federado (SIF) Sistema de Informação Federado (SIF) com arquitetura data warehousecom arquitetura data warehouse

cliente cliente cliente

servidordados

servidordados

servidordados

consultaresposta

atualizaçãodados

warehouse

dados

Page 32: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Sistema de Informação Federado (SIF) Sistema de Informação Federado (SIF) com arquitetura de mediadorescom arquitetura de mediadores

cliente cliente cliente

servidordados

servidordados

servidordados

consultaresposta

mediador

consultaresposta

Page 33: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

SISI Federad Federado: arquitetura o: arquitetura fortamente acoupladafortamente acouplada

Esquema Exportado 1

Esquema Exportado 2

Esquema Exportado n

Esquema Componente 1

Esquema Componente n

Esquema Global

Esquema Externo 1

Esquema Externo 2

Esquema Externo n

Esquema Local 1 Esquema Local n

DBS Componente 1 DBS Componente n

Page 34: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

SISI Federad Federado: arquitetura o: arquitetura fracamentefracamente acouplada acouplada

Mediador 1 Mediador 2

Tradutor 1 Tradutor 2 Tradutor 3

BD1 BD2 BD3

Consultas através de mediadores:

1. As consultas são submetidas ao sistema, via mediador, e este as transforma em subconsultas a serem enviadas às bases de dados.

2. As subconsultas geradas pelo mediador devem ser traduzidas para linguagens de consultas de cada SGBD componente.

3. Os resultados das consultas são traduzidos e a resposta é devolvida ao usuário

Page 35: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Tipologia dos meta-dados do data Tipologia dos meta-dados do data warehousewarehouse

Page 36: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Dimensões descritivas dos data Dimensões descritivas dos data warehouseswarehouses

Page 37: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

BD federados: definição e aplicaçõesBD federados: definição e aplicações

Page 38: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

BD federados: abordagensBD federados: abordagens

Page 39: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Data warehouse x BD federado:Data warehouse x BD federado:problemática comumproblemática comum

Page 40: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Data warehouse x BD federado:Data warehouse x BD federado:diferenças chavesdiferenças chaves

Page 41: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

BD temporais: definição e aplicaçõesBD temporais: definição e aplicações

Page 42: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

BD temporais: abordagensBD temporais: abordagens

Page 43: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

BD temporais: exemploBD temporais: exemplo

Page 44: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Data warehouse x BD temporal: Data warehouse x BD temporal: problemática comumproblemática comum

Page 45: Data Warehousing para Mineração de Dados Jacques Robin CIn-UFPE

Data warehouse x BD temporal: Data warehouse x BD temporal: diferenças chavesdiferenças chaves