79 Kb

Transcrição

79 Kb

Refinamento de Esquemas e
Normalização
Database Management Systems, R. Ramakrishnan
(tradução, autorizada, de Anna & Mario Nascimento)
6-1
Os Maus da Redundância
❖
Redundância é a raiz de diversos problemas
associados com esquemas relacionais:
– armazenamento , anomalias de inserção, atualização e remoção
❖
❖
❖
Restrições de integridade, em particular dependências
funcionais, podem ser usadas para identificar
esquemas com tal problemas e sugerir refinamentos.
Principal técnica de refinamento: decomposição
(substituindo ABCD por AB e BCD, ou ACD e ABD).
Decomposição deve ser usada com cuidado:
– Há razão para decompor uma relação?
– Que problemas (se algum) a decomposição causa?
6-2
Dependências Funcionais (DFs)
❖
❖
❖
Uma dependência funcional X → Y se aplica a R se, para
todas instâncias r de R:
– t1 ∈ r, t2 ∈ r, π X (t1) = π X (t2) implica π Y (t1) = π Y (t2)
– i.e., dadas 2 tuplas em r, se o valor de X concorda, então o
valor Y também concordam . (X e Y são conjs. de atributos.)
Uma DF é um fato sobre todas relações possíveis.
– Tem que ser identificada c/ base na semântica da aplicação.
– Dados alguns exemplos possíveis r1 de R, podemos
verificar se estes violam algunas DF f, mas não podemos
falar se f é verdade sobre R!
K é uma chave candidata para R quer dizer que K→ R
– No entanto, K →R não requer que K seja mínima !
6-3
Exemplo: Restrições Num Conjunto de Entidades
❖
Considere relação obtida de Hourly_Emps:
– Hourly_Emps (ssn, name, lot, rating, hrly_wages, hrs_worked)
❖
Notação: Indicaremos este esquema de relação listando
os atributos: SNLRWH
– Este é realmente o conjunto de atributos {S,N,L,R,W,H}.
– Algumas vezes nos referiremos a todos atributos de uma
relação usando o nome da relação. (p.ex., Hourly_Emps
para SNLRWH)
❖
Algunas DFs em Hourly_Emps:
– ssn é a chave: S → SNLRWH
– rating determina hrly_wages: R → W
6-4
Exemplo (Cont.)
❖
Problemas devidos a R→ W :
S
N
L
– Anomalia de atualização : Podemos 123-22-3666 Attishoo 48
trocar W somente na 1a tupla de 231-31-5368 Smiley
22
SNLRWH?
131-24-3650 Smethurst 35
– Anomalia de inserção : E se nós
35
queremos inserir um empregado e 434-26-3751 Guldu
não sabemos o salário por hora
612-67-4134 Madayan 35
para sua avaliação?
S
N
– Anomalia de remoção : Se deletarmos
todos empregados com avaliação 5, 123-22-3666 Attishoo
perdemos a informação sobre
231-31-5368 Smiley
salário para avaliação 5!
Wages
R W H
8 10 40
8 10 30
5 7
30
5 7
32
8 10 40
L
R H
48 8 40
22 8 30
R W
131-24-3650 Smethurst 35 5 30
8 10
434-26-3751 Guldu
5 7
Hourly_Emps2 612-67-4134 Madayan
35 5 32
35 8 40
6-5
Refinando Um Diagrama ER
❖
1o diagrama traduzido:
Workers(S,N,L,D,S)
Departments(D,M,B)
Before:
since
name
– Lots associados a trabalhadores. ssn
❖
❖
❖
Supomos todos trabalhadores no
departamento são nomeados
Employees
mesmo lote: D→ L
Redundância; corrigida por:
Workers2(S,N,D,S)
After:
Dept_Lots(D,L)
Podemos refinar com:
name
Workers2(S,N,D,S)
ssn
Departments(D,M,B,L)
Employees
dname
lot
did
Works_In
budget
Departments
budget
since
dname
did
Works_In
lot
Departments
6-6
Analisando DFs
❖
❖
❖
❖
❖
Dadas alguns DFs, podemos geralmente inferir DFs adicionais:
– ssn → did, did → lot implica ssn → lot
Uma DF f é implícita por um conjunto de DFs F se f é verdade
quando todas DFs em F são verdade.
F + = closure de F é o conjunto de todas DFs que são
implicadas por F.
Axiomas de Armstrong’s (X, Y, Z são conjuntos de atributos):
– Reflexividade : If X ⊆ Y, then X→ Y
– Aumentação : If X→ Y, then XZ → YZ for any Z
– Transitividade : If X → Y and Y → Z, then X → Z
Estas regras de inferência de DFs são robustas e completas.
6-7
Analisando DFs (Cont.)
❖
Duplas de regras adicionais (que seguem de AA):
❖
Exemplo: Contracts(cid,sid,jid,did,pid,qty,value), e :
❖
❖
❖
– União: If X→ Y and X→ Z, then X→ YZ
– Decomposição: If X→ YZ, then X → Y and X → Z
– C é a chave : C → CSJDPQV
– Projete compras cada parte usando contrato simples: JP → C
– Compras departamento no máximo uma parte de um fornecedor:
SD→ P
JP → C, C → CSJDPQV implica JP → CSJDPQV
SD → P implica SDJ→ JP
SDJ→ JP, JP → CSJDPQV implica SDJ→ CSJDPQV
6-8
Analisando DFs (Contd.)
❖
❖
Calcular o “closure”” de um conjunto de DFs pode ser caro.
(Tamanho de “closure” é exponencial no número de atributos)
Tipicamente, só queremos verificar se uma dada DF X→ Y
está no “closure de um conjunto de DFs F . Uma verificação
eficiente:
+
X
– Compute “closure” de atributos de X (denotada
) wrt F:
◆
◆
Conjunto de todos atributos A tais que X→ A está em
Há um algorítimo de tempo linear para computar isto.
F+
+
X
– Verificar se Y está em
❖
F = {A → B, B → C, C D → E } implica A → E?
+
F
→
– i.e, is A
E in the closure
? Equivalently, is E in A+ ?
6-9
Formas Normais
❖
❖
❖
Retornando ao ponto do refinamento de esquema, a
1a questão a ser feita é: algum refinamento é preciso ?
Se uma relação está em uma certa forma normal
(BCNF, 3NF etc.), é sabido que certos tipos de
problemas são evitados/minimizados. Isto pode ser
usado para decidir se decompondo a relação irá
ajudar.
Papel de DFs em detectar redundância:
– Considere uma relação R com 3 atributos, ABC.
◆
◆
Sem DFs: Não há redundância aqui.
Dado A → B: Diversas tuplas poderiam ter o mesmo valor A, e se
é assim, todas terão o mesmo valor B
6-10
Forma Normal de Boyce-Codd (BCNF)
❖
R com DFs F is in BCNF se, p/ todo X → A in F +
– A ∈ X (Chamado uma DF trivial), ou
– X contem uma chave de R.
❖
I.e., R está em BCNF somente se as únicas DFs não
triviais que valem sobre R são restrições de chaves.
– Nenhuma depêndencia em R que pode ser predita usando
apenas DFs.
– Se mostrarmos duas tuplas que concordam X Y A
de um valor X, não podemos inferir o valor
x y1 a
A em uma tupla do valor A de outra
– Se a relação exemplo está em BCNF, as 2
x y2 ?
tuplas tem que ser idênticas (X é chave).
6-11
Terceira Forma Normal (3FN)
❖
❖
❖
❖
R c/ DFs F está em 3NF se, p/todo X → A in F +
– A ∈ X (Chamado um FD trivial),ou
– X contem uma chave para R, ou
– A é parte de algumas chaves para R.
Minimalidade de uma chave é crucial na terceira condição
acima!
Se R está em BCNF, óbviamente está em 3FN.
Se R está em 3FN, alguma redundância é possível. É um
compromisso, usado quando BCNF não alcançavel (p.ex.,
decomposição não é “boa”,ou considerações de performances).
– Decomposição de R preservando dependência e lossless join em
uma coleção de relações de 3NF é sempre possível.
6-12
O Que 3FN Conclui?
❖
Se 3FN é violada por X→ A, então:
– X é um sub conjunto de alguma chave K
◆
Há pares (X,A) armazenados redundantemente.
– X não é um subconjunto próprio de nenhuma chave.
◆
❖
Há uma cadeia de DFs K → X → A, que quer dizer que não
podemos associar um valor de X com um valor de K a menos que
nós também associemos um valor A com um valor X.
Mas: mesmo se R está em 3FN, estes problemas podem surgir.
– e.g., Reserva SBDC, S → C, C → S está em 3FN, mas para cada
reserva de marinheiro S, um mesmo par (S,C) é guardado.
❖
Assim, 3FN é na verdade um compromisso relativo para
BCNF.
6-13
Decomposição de um Esquema de Relação
❖
Supondo que relação R contem atributos A1 ... An. A
decomposição de R consiste em substituir R por duas
ou mais relações tais que:
– Cada novo esquema contem um subconjunto de atributos
de R (e não atributos que não aparecem em R), e
– Todo atributo de R aparece como um atributo de uma das
novas relações.
❖
❖
Intuitivamente, decompor R quer dizer que vamos
guardar instâncias de esquemas produzidas pela
decomposição, ao invés da instância de R.
P.ex., decompor SNLRWH em SNLRH e RW.
6-14
Exemplo de Decomposição
❖
Decomposições devem ser usadas somente quando
for preciso.
– SNLRWH tem FDs S → SNLRWH e R→ W
– Segunda DF causa violação de 3NF; valor W
repetidamente associado com valor R. Caminho mais fácil
para fixar isto é criar uma relação RW para guardar estas
associações, e para remover W do esquema principal:
◆
❖
i.e., Nós decompomos SNLRWH em SNLRH e RW
A informação a ser guardada consiste de tuplas
SNLRWH. Se somente guardarmos a projeção destas
tuplas em SNLRH e RW, há alguns problemas em
potencial p/ os quais deveríamos estar alertas?
6-15
Problemas com Decomposição
❖
Há três problemas em potencial para considerar:
❶ Algumas consultas ficam mais caras.
◆
p.ex., Quanto ganhava o marinheiro Joe? (salario= W x H)
❷ Dadas instâncias de relações decompostas, nós talvez não
possamos recontruir a instância correspondente da relação
original!
◆
◆
❖
Não é o caso no exemplo SNLRWH. Checar algumas
dependências talvez requeira junções de instâncias de relações
decompostas.
Novamente, não no exemplo SNLRWH
Custo/benefício: Deve considerar estes resultados vs.
redundância.
6-16
Decomposição Com Junção Sem Perda
❖
Decomposição de R em X e Y permite junção sem
perda c/ respeito a um um conjunto de FDs F se, para
cada instância r que satisfaz F:
– π X (r) π Y (r) = r
❖
É sempre verdade que
r ⊆ π X (r) π Y (r)
– Em geral, a outra direção não verifica! Se verificasse, a
decomposição é junção sem perda.
❖
❖
Definição extendida para decomposição em 3 ou mais
relações em um caminho simples e direto.
É essencial que todas decomposições usadas para lidar com
redundância sejam sem perda (lossless)! (Evita (2).)
6-17
Mais sobre Junção Sem Perda
❖
❖
A decomposição de R em X e
Y é junção sem perda com
relação a F se e somente se o
fechamento de F contem :
– X ∩ Y → X, or
– X ∩Y → Y
Em particular, a decomposição
de R em UV e R - V é junção
sem perda se U → V verifica
sobre R.
A
1
4
7
A
1
4
7
1
7
B
2
5
2
B
2
5
2
2
2
C
3
6
8
C
3
6
8
8
3
A
1
4
7
B
2
5
2
B
2
5
2
C
3
6
8
6-18
Decomposição que Preserva Dependência
❖
Considere CSJDPQV, C chave , JP → C e SD → P.
– BCNF decomposição: CSJDQV e SDP
– Problema: Checando JP → C requer uma junção !
❖
Decomposição que preserva dependência (Intuitivo):
– Se R é decomposto em X, Y e Z, e impomos as DFs que
verificam sobre X, sobre Y e sobre Z, então todas DFs que
foram dadas sobre no R devem também verficar. (Evita
Problema (3).)
❖
Projeção de conjunto de FDs F: Se R é decomposta em
X, ... projeção de F em X (denotado FX )é o conjunto
de DFs U → V in F+ (“closure” de F) tais que U, V
estão em X.
6-19
Decomposição que Preserva Dependência (Cont.)
❖
Decomposição de R em X e Y preserva dependência se
(FX union FY ) + = F +
– i.e., se considerarmos somente dependências no fechamento
F + que podem ser checadas em X sem considerar Y, e em Y
sem considerar X, isto implica todas dependências em F +.
❖
❖
❖
Importante considerar F +, não F, nesta definição:
– ABC, A → B, B → C, C→ A, decompostos em AB e BC. .
– Preserva dependência ? C → A é preservada ?
Preservar dependência não implica junção sem perda:
– ABC, A → B, decomposto em AS e BC.
E vice-versa! (Exemplo?)
6-20
Decomposição em BCNF
❖
❖
Considere relação R com DFs F.
Se X → Y viola
BCNF, decomponha R em R - Y e XY.
– Aplicação repetida desta idéia nos dará uma coleção de
relações que estão em BCNF; decomposição de junção sem
perda, e garante-se a terminação.
– e.g., CSJDPQV, chave C, JP→ C, SD → P, J → S
– Para lidar com SD→ P, decomponha em SDP, CSJDQV.
– Para lidar com J→ S, decomponha CSJDQV em JS e
CJDQV
Em geral diversar dependências podem causar violações de
BCNF. A ordem na qual nos “lidamos com” então poderia
levar a conjuntos de relações muitos diferentes !
6-21
BCNF e Preservação de Dependência
❖
Em geral, pode não haver uma decomposição em
BCNF que preserve dependência.
– e.g., CSZ, CS → Z, Z → C
– Não pode decompor dad a 1a DF; não em BCNF.
❖
Similarmente, decomposição de CSJDQV em SDP, JS
e CJDQV não preserva dependência (c/ relação as
DFs: JP→ C, SD → P and J → S).
– No entanto, é uma decomposição de junção sem perda.
– Neste caso, adicionando JPC para a coleção de relações
nos dá uma decomposição c/ preservação de dependência.
◆
tuplas JPC armazenadas apenas para checar DF! (Redundante!)
6-22
Decomposição em 3NF
❖
❖
Obviamente, o algorítimo para decomposição de
junção sem perda em BCNF pode ser usado para
obter um decomposição de junção sem perda em 3NF
(tipicamente, pode-se parar mais cedo).
Para assegurar preservação de dependência:
– Se X → Y não é preservado, adicione relação XY.
– O problema é que XY pode violar 3NF! P.ex., considere a
adição de CJP para `preservar’ JP→ C. E se tambem
tivermos J→ C ?
❖
Refinamento: Ao invés de dar conjunto de DFs F, use
uma mínima cobertura para F .
6-23
Cobertura Mínima para um Conjunto de DFs
❖
Cobertura Mínima G para um conjunto de FDs F:
– “closure” de F = “closure” de G.
– O lado direito de cada DF em G é um simples atributo.
– Se modificarmos G removendo uma DF ou removendo
atributos de uma DF em G, o “closure”muda.
❖
❖
Intuitivamente, toda DF em G é necessária, e é “a
menor possível” de modo a termos o mesmo “closure”
como F.
e.g., A → B, ABCD → E, EF → GH, ACDF → EG
Tem as seguintes coberturas mínimas
– A→ B, ACD → E, EF → G and EF → H
6-24
Resumo de Esquema de Refinamento
❖
❖
Se uma relação está em BCNF, está livre de redundâncias que
podem ser detectadas usando DFs. Assim, tentar assegurar
que todas relações estão em BCNF é uma boa heurística .
Se uma relação não está em BCNF, podemos tentar decompor
a mesma em uma coleção de relações de BCNF.
– Deve considerar se todas DFs são preservadas. Se uma
junção sem perda , decomposição com preservação de
dependência em BCNF não é possível (ou inadequado,
dadas consultas típicas), deve considerar decomposição em
3NF.
– Decomposição deve ser propagada e/ou re-examinada
enquanto se mantém necessidades de performance em mente.
6-25

79 Kb

Transcrição

Documentos relacionados

EnviroPure é uma solução simples para os problemas

Standard Systems Sistemas Estándar Sistemas padrão DFS

Resumo de Mercado

Prévias - Revista Literária em Tradução

Página 1 − Principal Cultura é a Grande "muralha" da China Autor

PCI410018 - Pós Graduação em Ciência da Informação

Cabo delgado Ajudant de escrv de direi

cat. geral protos08

VIA Consulting alarga parceria com Verdiem

Diário de Notícias − Principal Opinião − Uma nova ameaça global à

Jornal Estado de Minas 3

data blocks