Download Aseveraciones Ejemplo de aseveración Disparadores Ejemplo de

Aseveraciones
Tema 4: Otros conceptos de diseño de bases
de datos relacionales
„ Aseveraciones
„ Una aseveración es un predicado que expresa una condición
que queremos que se cumpla siempre en la base de datos.
„ Disparadores (triggers)
„ Cuando se hace una aseveración, el sistema comprueba su
„ Seguridad
validez, y la comprueba de nuevo en cada actualización que
puede violar la aseveración
„ Autorización
„ NORMALIZACIÓN
+
+
+
+
+
+
+
+
+ Esta comprobación puede introducir una sobrecarga importante; por
Primera forma normal
tanto las aseveraciones se deben utilizar con mucho cuidado.
Problemas en el diseño lógico relacional
„ Aseverar
Dependencias funcionales
para todo X, P(X)
se consigue de manera indirecta con
no existe X tal que no P(X)
Descomposición
Forma normal de Boyce-Codd
Tercera forma normal
Otras formas normales y dependencias multivaluadas
Proceso global de diseño de bases de datos
Bases de datos
1
Bases de datos
Ejemplo de aseveración
Disparadores
„ La suma de todos los préstamos de cada sucursal debe ser
„ Un disparador es una sentencia que se ejecuta
menor que la suma de todos los saldos de cuentas de esa
sucursal.
automáticamente por el sistema como efecto lateral de una
modificación de la base de datos.
create assertion restriccion-suma check
(not exists (select * from sucursal
where (select sum(cantidad) from prestamo
where prestamo.-nombre-sucursal =
sucursal.nombre-sucursal)
>= (select sum(saldo) from cuenta
where cuenta.nombre-sucursal =
sucursal. nombre-sucursal)))
Bases de datos
„ Para especificar un disparador debemos:
+ Especificar las condiciones par a su ejecución.
+ Especificar las acciones a realizar cuando se ejecuta.
„ Los disparadores se introdujeron en el estándar SQL en
SQL:1999, pero eran soportados antes por la mayoría de los
gestores de bases de datos mediante sintaxis no estándar.
3
Ejemplo de disparador
Bases de datos
4
Ejemplo de disparador en SQL:1999
„ Supongamos que en vez de permitir saldos de cuenta negativos,
el banco trata los descubiertos de la siguiente manera:
+ poniendo el saldo de la cuenta a cero
+ creando un préstamo por la cantidad del descubierto
+ dando a ese préstamo un número de préstamo idéntico al número
de cuenta de la cuenta al descubierto
„ La condición para ejecutar el disparador será una actualización
de la relación cuenta que dé lugar a un valor de saldo negativo.
Bases de datos
2
5
create trigger descubierto after update on cuenta
referencing new row as nrow
for each row
when nrow.saldo < 0
begin atomic
insert into prestatario
(select nombre-cliente, numero-cuenta
from depositante
where nrow.numero-cuenta =
depositante.numero-cuenta);
insert into prestamo values
(n.row.numero-cuenta, nrow.nombre-sucursal,
– nrow.saldo);
update cuenta set saldo = 0
where cuenta.numero-cuenta = nrow.numero-cuenta
end
Bases de datos
6
Eventos y acciones de disparadores en SQL
„ Los eventos de disparo pueden ser: insertar, eliminar o actualizar
Disparadores a nivel de sentencia
„ En vez de ejecutar una acción separada para cada fila afectada,
se puede ejecutar una sola acción para todas las filas afectadas
por una transacción
„ Los disparadores sobre actualizaciones se pueden restringir a
determinados atributos
+ Utilizar for each statement en vez de for each row
+ P.e. create trigger descubierto after update of saldo on cuenta
„ Se pueden referenciar los valores anteriores y posteriores a una
actualización
„ Los disparadores se pueden activar antes de un evento, con lo que
pueden servir como restricciones adicionales.
+ Utilizar referencing old table o referencing new table para
referirse a tablas temporales (llamadas tablas de transición) que
contengan las filas afectadas
+ Puede ser más eficiente cuando tratamos sentencias SQL que
afectan a muchas filas
P.e. convertir blancos a nulos:
create trigger ponernulos before update on r
referencing new row as nrow
for each row
when nrow.numero-telefono= ‘ ‘
set nrow.numero-telefono= null
Bases de datos
7
Bases de datos
8
Seguridad
Seguridad (Cont.)
+ Nivel físico
„ Seguridad – protección frenet a intentos maliciosos de robar o
modificar datos.
El acceso físico a los servidores permite que los intrusos
destruyan datos; se necesita seguridad física tradicional
+ Nivel de sistema de bases de datos
Las máquinas deben protegerse también contra líquidos, fuego,
Mecanismos de autentificación y autorización permiten a
etc.
determinados usuarios acceder sólo a los datos requeridos
+ Nivel humano
+ Nivel de sistema operativo
Nos debemos asegurar de que los usuarios no den acceso a
¡Los superusuarios del sistema operativo pueden hacer cualquier
cosa en las bases de datos! Se necesita una buena seguridad a nivel
de sistema operativo.
intrusos
Uso adecuado de password
+ Nivel de red: debemos utilizar cifrado para prevenir
“Escuchas” (lecturas no autorizadas de mensajes)
Suplantaciones (pretender ser un usuario autorizado o enviar
mensajes supuestamente de usuarios autorizados)
Bases de datos
9
Bases de datos
Autorización
Autorización (Cont.)
Formas de autorización sobre partes de la base de datos:
„ Autorización de lectura – se permite leer, pero no modificar los
datos.
„ Autorización de inserción – se permite introducir nuevos datos,
pero no modificar los existentes.
Formas de autorización para modificar el esquema de la base de
datos:
„ Autorización de índexado – se permite crear y eliminar índices.
„ Autorización de recursos – se permite crear nuevas relaciones.
„ Autorización de alteración – se permite añadir o eliminar atributos
„ Autorización de actualización – se permite modificar, pero no
de una relación.
borrar datos.
„ Autorización de borrado – se permite borrar relaciones.
„ Autorización de eliminación – se permite eliminar datos.
Bases de datos
10
11
Bases de datos
12
Autorización y vistas
Ejemplo de vista
„ Los usuarios pueden obtener autorizaciones sobre vistas, sin
„ Supongamos que un cajero necesita conocer los nombres de los
tener ninguna autorización sobre las relaciones utilizadas en la
definición de la vista
clientes de cada sucursal, pero no está autorizado para ver
información específica sobre los créditos.
+ Aproximación: Denegar el acceso directo a la relación prestamo,
„ La característica de las vistas de ocultar datos sirve tanto para
pero permitir el acceso a la vista cliente-prestamo, que está
formada solamente por los nombres de los clientes y las sucursales
en las que tienen un préstamo.
simplificar el uso del sistema como para aumentar la seguridad
permitiendo a los usuarios que sólo accedan a los datos que
necesitan para su trabajo
+ La vista cliente-prestamo en SQL se define así:
„ Se puede utilizar una combinación de seguridad a nivel
relacional y seguridad a nivel de vista para limitar los accesos de
los usuarios a los datos que necesitan.
Bases de datos
13
create view cliente-prestamo as
select nombre-sucursal, nombre-cliente
from prestatario, prestamo
where prestatario.numero.prestamo = prestamo.numeroprestamo
Bases de datos
Ejemplo de vista (Cont.)
14
Autorización sobre vistas
„ El cajero estará autorizado a ver el resultado de la consulta:
„ La creación de vistas no requiere autorización de recursos dado
select *
from cliente-prestamo
que no se está creando ninguna relación real
„ El creador de la vista obtiene solo aquellos privilegios que
„ Cuando el procesador de consultas transforme el resultado en
una consulta de las relaciones de la base de datos, obtendremos
una consulta sobre prestatario y prestamo.
„ Las autorizaciones se deben comprobar sobre la consulta del
„ P.e. si el creador de la vista cliente-prestamo sólo tenía
cajero antes de que el procesador de consultas reemplace una
vista por la definición de la vista.
Bases de datos
suponen que no exista autorización adicional sobre la que ya
tenía.
autorización de lectura sobre prestatario y prestamo, sólo
obtiene autorización de lectura sobre cliente-prestamo
15
Concesión de privilegios
Bases de datos
16
Grafo de concesión de privilegios
„ El paso de autorización de un usuario a otro se puede
representar mediante un grafo de autorización.
„ Requisito: Todas las flechas de un grafo de autorización deben partir de
un camino que tenga su origen en el administrador de bases de datos
„ Los nodos del grafo representan usuarios.
„ Si el DBA revoca el privilegio para U1:
„ La raíz del grafo es el administrador de la base de datos.
+ Se debe revocar la concesión de U4 dado que U1 ya no tiene autorización
„ Consideremos el grafo para autorizaciones de actualización
+ No se debe revocar la autorización de U5 dado que U5 tiene otro camino de
sobre prestamo.
autorización desde DBA a través de U2
„ Una flecha Ui →Uj indica que el usuario Ui ha concedido
„ Se deben prevenir ciclos de concesiones sin camino desde la raíz:
autorización de actualización sobre prestamo a Uj.
U1
+ DBA concede autorización a U7
+ U7 concede autorización a U8
U4
+ U8 concede autorización a U7
+ DBA revoca la autorización a U7
DBA
Bases de datos
U2
U3
+ Se debe revocar la concesión de U7 a U8 y de U8 a U7 dado que no queda
ningún camino desde DBA a U7 o a U8.
U5
17
Bases de datos
18
Roles
„ Los roles permiten especificar sólo una vez privilegios comunes a
varios usuarios.
„ Los privilegios se conceden o revocan a los roles igual que para
usuarios individuales
„ Los roles se pueden asignar a usuarios o a otros roles
„ SQL:1999 soporta roles
NORMALIZACIÓN
create role cajero
create role gestor
grant select on sucursal to cajero
grant update (saldo) on cuentas to cajero
grant all privileges on cuentas to gestor
grant cajero to gestor
grant cajero to alicia, juan
grant gestorr to ana
Bases de datos
19
Primera forma normal
Bases de datos
Manuel Ramos Cabrer
20
Problemas en el diseño lógico relacional
„ Un dominio es atómico si sus elementos se pueden considerar
unidades indivisibles
„ El diseño de bases de datos relacionales requiere
encontrar un “buen” conjunto de esquemas de relación.
Un mal diseño puede dar lugar a:
+ Ejemplos de dominios no atómicos:
Nombres, atributos compuestos
+ Repetición de información (redundancia)
Números de identificación como 305010789 que se pueden
+ Imposibilidad de representar cierta información.
dividir en partes
„ Objetivos de diseño:
„ Un esquema relacional R esté en primera forma normal si los
dominios de todos los atributos de R son atómicos
+ Evitar la redundancia
„ Los valores no atómicos complican el almacenamiento y dan
+ Asegurar que se representan las asociaciones entre
lugar a redundancia
atributos
+ Facilitar la comprobación de las violaciones de
+ P.e. Conjunto de cuentas almacenado con cada cliente, y conjunto
restricciones de integridad en las actualizaciones de las
bases de datos.
de propietarios almacenado con cada cuenta
+ Vamos a asumir que todas las relaciones están en primera forma
normal
Bases de datos
21
Bases de datos
Ejemplo
22
Descomposición
„ Consideremos el siguiente esquema de relación:
Esquema-prestamo = (nombre-sucursal, ciudad-sucursal, activos,
nombre-cliente, numero-prestamo, cantidad)
nombresucursal
ciudadsucursal
Vigo
Vigo
Santiago
Santiago
Madrid-1
Vigo
activos
nombrecliente
numeroprestamo
9000000
Sánchez
L-17
1000
2100000
Gómez
L-23
2000
Madrid
1700000
López
L-15
1500
Vigo
9000000
Veiga
L-14
1500
„ Descompongamos el esquema de relación Esquema-prestamo
en:
Esquema-sucursal = (nombre-sucursal, ciudad-sucursal, activos)
cantidad
Esquema-info-prestamo = (nombre-cliente, numero-cliente,
nombre-sucursal, cantidad)
„ Todos los atributos del esquema original (R) deben aparecer en
la descomposición (R1, R2):
„ Redundancia:
+ Los datos de nombre-sucursal, ciudad-sucursal, activos se repiten para cada
préstamo que hace una sucursal
+ Gasto de espacio
+ Se complica la actualización, introduciendo la posibilidad de inconsistencias
R = R1 ∪ R2
„ Descomposición reversible por join
Para todas las posibles relaciones r en el esquema R
r = ∏R1 (r)
„ Valores nulos:
∏R2 (r)
+ No se puede almacenar información sobre una sucursal si no existen
préstamos
+ Se pueden utilizar valores nulos, pero son difíciles de gestionar.
Bases de datos
23
Bases de datos
24
Ejemplo de descomposición no reversible por join
Objetivo — Una teoría para:
„ Decidir cuando una determinada relación R está en un “estado
adecuado”.
„ Descomposición de R = (A, B)
R1 = (A)
R2 = (B)
„ En el caso de que la relación R no sea “buena”, descomponerla
en un conjunto de relaciones {R1, R2, ..., Rn} tales que
A
B
α
α
β
α
β
1
2
„ Nuestra teoría está basada en:
∏A(r)
∏B(r)
+ Dependencias funcionales
1
2
1
r
∏A (r)
+ Cada relación esté en “estado adecuado”
A B
∏B (r)
A
B
α
α
β
β
1
2
1
2
Bases de datos
+ La descomposición sea reversible por join
+ Dependencias multivaluadas
25
Dependencias funcionales
Bases de datos
26
Dependencias funcionales (Cont.)
„ Dado un esquema de relación R
„ Restricciones sobre el conjunto de relaciones permitidas en un
α⊆R y β⊆R
conjunto relación.
„ La dependencia funcional
„ Introducen como restricción que el valor de un conjunto
determinado de atributos determina de manera única el valor de
otro conjunto de atributos.
„ El concepto de dependencia funcional es una generalización del
concepto de clave.
α→β
se da en R si y solo si para cualquier relación legal r(R), cuando
dos tuplas cualquiera t1 y t2 de r coinciden en los valores de los
atributos α, entonces también coinciden en lso valores de los
atributos β. Es decir,
t1[α] = t2 [α] ⇒ t1[β ] = t2 [β ]
„ Ejemplo: Consideremos r(A,B) con la siguiente instancia de r.
1
1
3
4
5
7
„ En esta instancia, A → B NO se da, pero B → A si.
Bases de datos
27
Dependencias funcionales (Cont.)
Bases de datos
28
Uso de Dependencias Funcionales
„ K es una superclave del esquema de relación R si y solo si K → R
„ K es una clave candidata de R si y solo si
„ Utilizamos dependencias funcionales para::
+ Comprobar las relaciones para ver si son legales bajo un conjunto
dado de dependencias funcionales.
+ K → R, y
+ Para ningún α ⊂ K, α → R
Si una relación r es legal bajo un conjunto F de dependencias
„ Las dependencias funcionales nos permiten expresar restricciones
que no se pueden expresar mediante superclaves. Consideremos el
esquema:
Esquema-info-prestamo = (nombre-cliente, numero-prestamo,
nombre-sucursal, cantidad).
Debemos esperar que se cumplan las siguientes dependencias
funcionales:
numero-prestamo → cantidad
numero-prestamo → nombre-sucursal
pero debemos esperar que no se cumpla:
funcionales, decimos que r satisface F.
+ Especificar restricciones sobre un conjunto de relaciones legales
Decimos que F se da en R si todas las relaciones legales sobre R
satisfacen el conjunto de dependencias funcionales F.
„ Nota: Una instancia específica de un esquema de relación puede
satisfacer una dependencia funcional aun cuando la dependencia
funcional no se dé en todas las instancias legales.
+ Por ejemplo, una instancia específica de Esquema-prestamo puede,
por tanto, satisfacer
numero-prestamo → nombre-cliente.
numero-prestamo → nombre-cliente
Bases de datos
29
Bases de datos
30
Cierre de un conjunto de dependencias
funcionales
Dependencias funcionales (Cont.)
„ Una dependencia funcional es trivial si se satisface para todas
„ Dado un conjunto F de dependencias funcionales, hay otras
las instancias de una relación
dependencias funcionales que se pueden inferir de F.
+ P.e. Si A → B y B → C, entonces podemos inferir que A → C
+ P.e.
nombre-cliente, numero-prestamo → nombre-cliente
„ El conjunto de todas las dependencias funcionales que se pueden
inferir de F forman el cierre de F.
nombre-cliente → nombre-cliente
+ En general, α → β es trivial si β ⊆ α
„ Denotaremos el cierre de F por F+.
„ Podemos calcular F+ aplicando los Axiomas de Armstrong:
+ si β ⊆ α, entonces α → β
(reflexividad)
+ si α → β, entonces γ α → γ β
(aumentación)
+ si α → β, y β → γ, entonces α → γ
(transitividad)
„ Estas reglas son
+ consistentes (generan solo dependencias funcionales que se dan) y
+ completas (generan todas las dependencias funcionales que se dan)
Bases de datos
31
Bases de datos
32
Procedimiento de cálculo de F+
Ejemplo
„ R = (A, B, C, G, H, I)
„ Para calcular el cierre de un conjunto de dependencias
F={ A→B
A→C
CG → H
CG → I
B → H}
funcionales F:
F+ = F
repetir
para cada dependencia funcional f en F+
aplicar las reglas de reflexividad y aumentación a f
añadir las dependencias funcionales resultantes a F+
para cada par de dependencias funcionales f1y f2 en F+
si f1 y f2 se pueden combinar por transitividad
entonces añadir la dependencia funcional
resultante a F+
+
hasta que F no cambie
„ Algunos miembros de F+
+ A→H
Por transitividad de A → B y B → H
+ AG → I
por aumentación de A → C con G, que da AG → CG
y después por transitividad con CG → I
+ CG → HI
de CG → H y CG → I : la “regla de la unión” se puede inferir de
– La definición de dependencia funcional, o
– Por aumentación de CG → I para inferir CG → CGI, aumentación de
CG → H para inferir CGI → HI, y entonces transitividad
Bases de datos
33
Cierre de dependencias funcionales
(Cont.)
Bases de datos
34
Cierre de un conjunto de atributos
„ Dado un conjunto de atributos α, definimos el cierre de α bajo F
(denotado por α+) como el conjunto de atributos funcionalmente
determinados por α bajo F:
α → β está en F+ ➳ β ⊆ α+
„ Podemos simplificar el cálculo manual de F+ utilizando las
siguientes reglas adicionales.
+ Si α → β se da y α → γ se da, entonces α → β γ se da (unión)
+ Si α → β γ se da, entonces α → β se da y α → γ se da
„ Algoritmo para calcular α+, el cierre de α bajo F
resultado := α;
mientras (cambie resultado) hacer
para cada β → γ en F hacer
begin
si β ⊆ resultado entonces resultado := resultado ∪ γ
end
(decomposición)
+ Si α → β se da y γ β → δ se da, entonces α γ → δ se da
(pseudotransitividad)
Estas reglas (y otras) se pueden inferir de los axiomas de
Armstrong.
Bases de datos
35
Bases de datos
36
Ejemplo de cierre de un conjunto de atributos
„ R = (A, B, C, G, H, I)
Utilidad del cierre de atributos
Hay varias utilidades del algoritmo de cierre de atributos
„ F = {A → B
A→C
CG → H
CG → I
B → H}
„ (AG)+
„ Comprobar una superclave:
+ Para comprobar si α es una superclave, calculamos α+, y
comprobamos si α+ contiene todos los atributos de R.
„ Comprobar dependencias funcionales
1. resultado = AG
+ Para comprobar si una dependencia funcional α → β se da (o, en
2. resultado = ABCG
(A → C y A → B)
3. resultado = ABCGH
(CG → H y CG ⊆ AGBC)
4. resultado = ABCGHI
(CG → I y CG ⊆ AGBCH)
otras palabras, está en F+), se comprueba si β ⊆ α+.
+ Es decir, calculamos α+ utilizando el cierre de atributos, y entonces
comprobamos si contiene β.
„ ¿AG es una clave candidata?
+ Es una comprobación simple y poco costosa, y muy útil
1. ¿AG es una superclave?
„ Cálculo del cierre de F
1. ¿AG → R? == (AG)+ ⊇ R
+ Para cada γ ⊆ R, buscamos el cierre γ+, y para cada S ⊆ γ+,
2. ¿Algún subconjunto de AG es una superclave?
generamos la dependencia funcional γ → S.
1. ¿A → R? == (A)+ ⊇ R
2. ¿G → R? == (G)+ ⊇ R
Bases de datos
37
Bases de datos
38
Descomposición
Objetivos de la normalización
„
„ Decidir cuando una determinada relación R está en un “estado
Descompongamos el esquema de relación Esquema-prestamo en:
Esquema-sucursal = (nombre-sucursal, ciudad-sucursal, activos)
adecuado”.
„ En el caso de que la relación R no sea “buena”, descomponerla
en un conjunto de relaciones {R1, R2, ..., Rn} tales que
Esquema-info-prestamo = (nombre-cliente, numero-cliente,
nombre-sucursal, cantidad)
„
Todos los atributos del esquema original (R) deben aparecer en la
descomposición (R1, R2):
„
Descomposición reversible por join
Para todas las posibles relaciones r en el esquema R
„
Una descomposición de R en R1 y R2 es reversible por join si y sólo si al
menos una de las siguientes dependencias funcionales está en F+:
+ Cada relación esté en “estado adecuado”
+ La descomposición sea reversible por join
R = R1 ∪ R2
„ Nuestra teoría está basada en:
+ Dependencias funcionales
+ Dependencias multivaluadas
r = ∏R1 (r)
∏R2 (r)
+ R1 ∩ R2 → R1
+ R1 ∩ R2 → R2
Bases de datos
44
Ejemplo de descomposición no reversible por
join
„
„
Bases de datos
45
Normalización utilizando dependencias funcionales
„ Cuando descomponemos un esquema de relación R
Las descomposiciones no reversibles por join dan lugar a
alteraciones de la información.
Ejemplo: Descomposición de R = (A, B)
R2 = (B)
R1 = (A)
con un conjunto de dependencias funcionales F en R1,
R2,.., Rn queremos:
+ Descomposición reversible por join: Si no la descomposición puede
A B
A
B
α
α
β
α
β
1
2
∏A(r)
∏B(r)
1
2
1
r
∏A (r)
Bases de datos
∏B (r)
A
B
α
α
β
β
1
2
1
2
suponer alteraciones de la información.
+ Sin redundancia.
+ Preservación de dependencias: Dado Fi como el conjunto de
dependencias F+ que incluya sólo atributos de Ri.
La descomposición debería preservar las dependencias, es decir,
(F1 ∪ F2 ∪ … ∪ Fn)+ = F+
Si no perdemos dependencias, que son restricciones introducudas
en la fase de diseño para modelar adecuadamente la aplicación. No
es deseable.
46
Bases de datos
47
Comprobación de preservación de
dependencias
Ejemplo
„ Para comprobar si una dependencia α→β se preserva en una
„ R = (A, B, C)
descomposición de R en R1, R2, …, Rn aplicamos la siguiente
comprobación simplificada (con el cierre de atributos realizado
respecto a F)
F = {A → B, B → C)
+ Se puede descomponer de dos maneras diferentes
„ R1 = (A, B), R2 = (B, C)
+ resultado = α
while (cambie resultado) do
for each Ri en la descomposición
t = (resultado ∩ Ri)+ ∩ Ri
resultado = resultado ∪ t
+ Descomposición reversible por join:
R1 ∩ R2 = {B} y B → BC
+ Preserva las dependencias
+ Si resultado contiene todos los atributos de β, entonces se preserva la
„ R1 = (A, B), R2 = (A, C)
dependencia funcional α → β.
+ Descomposición reversible por join:
„ Debemos aplicar el test a todas las dependencias de F para
R1 ∩ R2 = {A} y A → AB
comprobar si la descomposición preserva las dependencias
+ No preserva las dependencias
„ Este procedimiento tiene una complejidad temporal polinomial,
(se pierde B → C)
Bases de datos
frente a la complejidad exponencial de calcular F+ y (F1 ∪ F2 ∪ …
∪ Fn)+
48
Bases de datos
Forma Normal de Boyce-Codd
49
Ejemplo
Un esquema de relación está en FNBC con respecto a un conjunto
de dependencias funcionales F si para todas las dependencias
funcionales de F+, α → β, donde α ⊆ R y β ⊆ R, se cumple al menos
una de las siguientes condiciones:
„ R = (A, B, C)
F = {A → B
B → C}
Clave = {A}
„ R no está en FNBC
„ α
„ α
→ β es trivial (es decir, β ⊆ α)
„ Descomposición R1 = (A, B), R2 = (B, C)
es una superclave de R
+ R1 y R2 en FNBC
+ Reversible por join
+ Preserva las dependencias
Bases de datos
50
Comprobación de la FNBC
Bases de datos
51
Algoritmo de descomposición en FNBC
„ Para comprobar si una dependencia no trivial α →β cumple la FNBC
1. calcular α+ (el cierre de atributos de α), y
2. verificar que incluye todos los atributos de R, es decir, es una superclave de
R.
„ Comprobación simplificada: Para comprobar si un esquema de relación R
está en FNBC, es suficiente comprobar las dependencias del conjunto F,
en vez de comprobar todas las dependencias de F+.
+ Si ninguna de las dependencias de F viola la FNBC, entonces ninguna de las
dependencias de F+ violará la FNBC.
„ Pero, es incorrecto utilizar sólo F cuando se comprueba una relación de
una descomposición de R
+ P.e. Consideremos R (A, B, C, D), con F = { A →B, B →C}
resultado := {R};
hecho := false;
calcular F+;
while (not hecho) do
if (hay un esquema Ri en resultado que no está en FNBC)
then begin
dada una dependencia funcional no trivial α → β
que se da en Ri
tal que α → Ri no está en F+,
y α ∩ β = ∅;
resultado := (resultado – Ri ) ∪ (Ri – β) ∪ (α, β );
end
else hecho := true;
Nota: cada Ri está en FNBC, y la descomposición es sin pérdidas.
Descomponemos R en R1(A,B) y R2(A,C,D)
Ninguna de las dependencias de F contiene sólo atributos de
(A,C,D) por eso podríamos cometer el error de pensar que R2 está en
FNBC.
De hecho, la dependencia A → C de F+ indica que R2 no está en FNBC.
Bases de datos
52
Bases de datos
53
Ejemplo de descomposición en FNBC
„ R = (nombre-sucursal, ciudad-sucursal, activos,
Comprobación de descomposición en FNBC
„ Para comprobar si una relación Ri de una descomposición de R está en
nombre-cliente, numero-prestamo, cantidad)
FNBC,
F = {nombre-sucursal → activos ciudad-sucursal
+ o bien comprobar si Ri está en FNBC con respecto a la restricción de F a Ri
(es decir, todas las DFs de F+ que contienen sólo atributos de Ri)
numero-prestamo → cantidad nombre-sucursal}
+ o utilizar el conjunto original de dependencias F que se dan en R, pero con la
Clave = {numero-prestamo, nombre-cliente}
siguiente comprobación:
„ Decomposición
– para cada conjunto de atributos α ⊆ Ri, comprobar que α+ (el cierre de
atributos de α) o bien no incluye ningún atributo de Ri- α, o incluye
todos los atributos de Ri.
+ R1 = (nombre-sucursal, ciudad-sucursal, activos)
+ R2 = (nombre-sucursal, nombre-cliente, numero-prestamo,
Si la condición se viola por algún α →
cantidad)
α → (α+ - α ) ∩ Ri
se da en Ri, y Ri viola la FNBC.
+ R3 = (nombre-sucursal, numero-prestamo, cantidad)
β de F, la dependencia
Utilizaremos la dependencia anterior para descomponer Ri
+ R4 = (nombre-cliente, numero-prestamo)
„ Descomposición final
R1, R3, R4
Bases de datos
54
FNBC y preservación de dependencias
Bases de datos
55
Tercera Forma Normal: Motivación
„ Hay algunas situaciones en las que
No siempre es posible llegar a una descomposición en FNBC
que preserve las dependencias
+ La FNBC no preserva las dependencias
„ Solución: definir una forma normal más débil, denominada Tercera
„ R = (J, K, L)
Forma Normal.
F = {JK → L
L → K}
Dos claves candidatas = JK y JL
+ Permite cierta redundancia (con los problemas consabidos)
+ Pero siempre existe una descomposición a 3FN que es reversible por
join y que preserva las dependencias:
„ R no está en FNBC
„ Cualquier descomposición de R no preserva
JK → L
Bases de datos
56
Bases de datos
57
Tercera Forma Normal
3FN (Cont.)
„ Un esquema de relación R está en tercera forma normal (3FN) si
para todas las:
„ Ejemplo
+ R = (J, K, L)
α → β de
se cumple am menos una de las siguientes condiciones:
F+
F = {JK → L, L → K}
+ Dos claves candidatas: JK y JL
+ α → β es trivial (es decir, β ⊆ α)
+ R está en 3FN
+ α es una superclave de R
JK → L
L→K
+ Cada atributo A de β – α está contenido en una clave candidata de
R.
„ La descomposición en FNBC da (JL) y (LK)
(NOTA: cada atributo puede estar en una clave candidata diferente)
„ Se pierde JK → L
„ Si una relación está en FNBC entonces también está en 3FN
(dado que en FNBC se debe dar una de las dos primeras
condiciones).
„ La tercera condición es una relajación mínima de la FNBC que
asegura la preservación de dependencias funcionales.
Bases de datos
JK es una superclave
K está contenida en una clave candidata
„ Hay cierta redundancia en este esquema
58
Bases de datos
59
Comprobación de la 3FN
Algoritmo de descomposición a 3FN
Dado el conjunto de dependencias funcionales F;
i := 0;
for each dependencia funcional α → β de F do
if ninguno de los esquemas Rj, 1 ≤ j ≤ i contiene α β
then begin
i := i + 1;
Ri := α β
end
if ninguno de los esquemas Rj, 1 ≤ j ≤ i contiene una clave
candidata de R
then begin
i := i + 1;
Ri := cualquier clave candidata de R;
end
return (R1, R2, ..., Ri)
„ Optimización: Sólo es necesario comprobar las dependencias
funcionales de F, no todas las de
F+.
„ Utilizar el cierre de atributos para comprobar en cada
dependencia α → β, si α es una superclave.
„ Si α no es superclave, tenemos que verificar si cada atributo de
β está contenido en una clave candidata de R
+ Esta comprobación es bastante más costosa, dado que supone
encontrar las claves candidatas
+ Se ha demostrado que comprobar la 3FN es NP-hard
+ Por suerte, descomponer a 3FN se puede hacer con una
complejidad polinomial
Bases de datos
60
Bases de datos
61
Ejemplo
Algoritmo de descomposición a 3FN (Cont.)
„ El algoritmo anterior asegura:
„ Esquema de relación:
+ que cada esquema de relación Ri está en 3FN
Esquema-info-banquero = (nombre-sucursal, nombre-cliente,
nombre-banquero, numero-despacho)
+ La descomposición es reversible por join y preserva las dependencias
„ Las dependencias funcionales para este esquema de relación
son:
nombre-banquero → nombre-sucursal numero-despacho
nombre-cliente nombre-oficina → nombre-banquero
„ La clave es:
{nombre-cliente, nombre-sucursal}
Bases de datos
62
Bases de datos
Aplicando 3FN a Esquema-info-banquero
63
Comparación de FNBC y 3FN
„ Siempre es posible descomponer una relación en relaciones en
„ El bucle for del algoritmo hace que incluyamos los
3FN y
siguientes esquemas en nuestra descomposición:
Esquema-despacho-banquero = (nombre-banquero,
nombre-oficina, numero-despacho)
Esquema-banquero = (nombre-cliente,
nombre-sucursal, nombre-banquero)
+ La descomposición es reversible por join
+ Se preservan las dependencias
„ Siempre es posible descomponer una relación en relaciones en
FNBC y
+ La descomposición es reversible por join
+ Puede que no se preserven las dependencias
„ Dado que Esquema-banquero contiene una clave
candidata para Esquema-info-banquero, hemos terminado
el proceso de descomposición.
Bases de datos
64
Bases de datos
65
Comparación de FNBC y 3FN (Cont.)
Objetivos de diseño
„ El objetivo de un diseño de base de datos relacional es:
„ Ejemplo de problemas debidos a la redundancia en la 3FN
+ FNBC.
+ R = (J, K, L)
F = {JK → L, L → K}
+ Descomposición reversible por join.
J
L
K
j1
l1
k1
j2
l1
k1
j3
l1
k1
null
l2
k2
+ Preservación de dependencias.
„ Si no se puede conseguir, podemos aceptar
+ o bien perder la preservación de dependencias,
+ o bien la existencia de redundancia debida al uso de la 3FN (suele ser la
opción preferible)
„ Sorprendentemente, SQL no proporciona un mecanismo directo de
especificar dependencias funcionales distintas de las superclaves.
Se pueden especificar DFs como aseveraciones, pero son costosas de
comprobar
Un esquema que está en 3FN pero no en FNBC tiene problemas
de
„ Aunque tengamos una descomposición que preserve las dependencias,
„ Repetición de información (p.e., la asociación l1, k1)
utilizando SQL no podremos comprobar de manera eficiente una
dependencia funcional cuya parte izquierda no sea una clave.
„ Necesidad de utilizar valores nulos (p.e., para representar la
asociación l2, k2 que no tiene valor para J).
Bases de datos
66
Bases de datos
Otras formas normales
67
Dependencias multivaluadas
„ Existen otras formas normales que es deseable que
„ Dado un esquema de relación R y dados α ⊆ R y β ⊆ R.
La dependencia multivaluada
se den en una relación: Cuarta Forma Normal (4FN),
Quinta Forma Normal (5FN), …
α →→ β
se da en R si en cualquier relación posible r(R), para
todos los pares de tuplas t1 y t2 de r tales que t1[α] = t2 [α],
existen en r las tuplas t3 y t4 tales que:
„ La 3FN es la forma ideal en lo referente a
dependencias funcionales. ¿Por qué existen
entonces otras formas normales?
t1[α] = t2 [α] = t3 [α] = t4 [α]
t3[β]
= t1 [β]
t3[R – β] = t2[R – β]
t4 [β]
= t2[β]
t4[R – β] = t1[R – β]
+ Pues porque pueden existir otras dependencias en una base
de datos además de las dependencias funcionales, aunque
estas últimas son las más habituales.
+ Las dependencias no funcionales más habituales son las
dependencias multivaluadas.
Bases de datos
68
Bases de datos
Dependencias multivaluadas (Cont.)
„ Representación gráfica de α →→ β
69
Dependencias multivaluadas
„ Definición alternativa:
t1
α
a1 … ai
β
ai+1 … aj
R- α- β
aj+1 … an
t2
t3
a1 … ai
a1 … ai
bi+1 … bj
ai+1 … aj
bj+1 … bn
bj+1 … bn
t4
a1 … ai
bi+1 … bj
aj+1 … an
+ Dado un esquema de relación R con un conjunto
de atributos particionado en tres subconjuntos no
vacíos
Y, Z, W
+ Decimos que Y →→ Z (Y multidefine a Z)
si y sólo si para todas las relaciones posibles r(R)
si
< y1, z1, w1 > ∈ r y < y2, z2, w2 > ∈ r
entonces
< y1, z1, w2 > ∈ r y < y2, z2, w1 > ∈ r
Bases de datos
70
Bases de datos
71
Proceso global de diseño de bases de datos
El modelo E-A y la normalización
„ Cuando un diagrama E-A se diseña adecuadamente, identificando
„ Hemos asumido que un esquema R viene dado por
+ R puede haber sido generado por el paso de un diagrama E-A a un
conjunto de relaciones.
+ R puede ser una única relación que contiene todos los atributos de
interés (se denomina relación universal).
+ La normalización divide R en relaciones más pequeñas.
+ R puede ser el resultado de algún otro proceso de diseño de
relaciones, el cual comprobamos/convertimos a forma normal.
todas las entidades correctamente, las relaciones generadas a partir
del diagrama E-A no deberían necesitar normalización adicional.
„ No obstante, en un diseño real (imperfecto) puede haber
dependencias funcionales desde atributos que no sean clave de una
entidad hacia otros atributos de la entidad.
„ P.e. La entidad empleado con atributos numero-despacho y
localizacion-despacho, y una dependencia funcional
numero-despacho → localización-despacho
+ En un buen diseño se debería haber creado una entidad despacho
„ Es posible encontrar dependencias funcionales desde atributos de un
conjunto asociación que no sean clave, pero no es frecuente --- la
mayoría de los conjuntos asociación son binarios
Bases de datos
72
Bases de datos
73
Otros aspectos de diseño
„ La normalización no se ocupa de algunos aspectos del diseño de bases
de datos.
„ Ejemplos de malos diseños de bases de datos que se deben evitar:
En vez de beneficios(id-empresa, año, cantidad), utilizar
+ beneficios-2000, beneficios-2001, beneficios-2002, etc., todos con el
esquema (id-empresa, beneficios).
Fin del tema 4
Las relaciones anteriores están en FNBC, pero hacer consultas que
afecten a varios años es difícil y además se necesita una tabla nueva
para cada año.
+ empresa-año(id-empresa, beneficios-2000, beneficios-2001,
beneficios-2002)
También está en FNBC, pero también es difícil hacer consultas que
afecten a varios años y necesita un atributo nuevo cada año.
Es un ejemplo de una tabla cruzada, en la que los valores de un
atributo se utilizan como nombres de columnas.
Se utiliza sobre todo en hojas de cálculo, y en herramientas de análisis
de datos.
Bases de datos
74
Bases de datos
Manuel Ramos Cabrer
75