Asignatura	Oferta de asignatura	Cuatrimestre ofertado (asignatura)

En este ejemplo, cuatrimestre ofertado solo existe si existe la asignatura. Cuatrimestre es una entidad dependiente y se representa por una caja con una raya encima. Las entidades dependientes siempre se asocian a otras por medio de una relación 1:N. Los atributos identificadores de una entidad dependiente son dos: El de la entidad fuerte (cod) y otro que permite diferenciar el conjunto de instancias de la entidad débil relacionadas con la entidad fuerte.

2.3 Generalización y especialización.

En ciertas ocasiones, varias entidades tienen las mismas características exceptuando algún atributo. En este caso, se puede construir una entidad general que englobe a las anteriores. Esta generalización evita la duplicación de atributos. En este modelo, las entidades del nivel inferior heredan las propiedades de las entidades del nivel superior.

En el ejemplo, un militar no puede ser a la ver recluta y mando. A este tipo de generalización se la denomina "generalización disjunta". No obstante, existen otros ejemplos en los que si se pueden dar ambos sucesos a la vez. A este nuevo tipo de generalización se le denomina "generalización con solapamiento". En este último tipo de generalización se suele añadir un campo de tipo que nos permita saber si un miembro de la entidad superior pertenece a una u otra entidad inferior (o a ambas).

Finalmente, existe un tercer tipo de asociación denominada "especialización" que consiste en agrupar dos entidades en principio disjuntas (salvo por algún que otro atributo como el atributo identificativo) para simplificar o aclarar el esquema de la base de datos. Este tipo de asociación se crea de abajo hacia arriba, al contrario que ocurre con las generalizaciones que se forman de arriba hacia abajo. Para distinguir una generalización de una especialización gráficamente estas últimas se representan mediante la letra E.

Tema 3.

Modelo relacional.

3.1 Estructura básica del modelo.

3.2 Clave y reglas de integridad.

3.3 Álgebra relacional.

3.4 Conversión de diagramas E/R a tablas.

3.5 Ejemplos de aplicación.

3.1 Estructura básica del modelo.

Los constructores del modelo son los atributos (también llamados dominio), las tuplas y las relaciones.

•       La información de un objeto se registra en términos de atributos. Los atributos tienen que tomar valores de algún tipo, el cual es un conjunto de valores consentido denominado dominio subyacente del atributo. Al definir el dominio aportamos una información substancial al atributo. El concepto de dominio es muy importante en el modelo relacional ya que define muchas propiedades (El problema de la mayoría de los programas gestores de bases de datos que actualmente se venden y que siguen este modelo es que no permiten moldear los dominios). Dentro del modelo relacional sólo se permiten modelos atómicos, es decir, valores que no puedan ser descompuestos en otros más pequeños. Así, por ejemplo, una fecha se considera un tipo de atributo atómico si no se va a operar dentro de la base de datos ni con los días, ni meses, ni años de la misma. En caso contrario, los tipos de atributo serían "tipo día", "tipo mes" y "tipo año". El carácter de atómico por tanto es subjetivo. Para referirnos a atributos simples como un DNI usaremos las letras A,B,C... y para referirnos a atributos compuestos como NOMBRE+APELLIDO1+APELLIDO2 usaremos las letras X,Y,Z...

•       Una tupla representa una instancia concreta de un objeto general. Puede ser una instancia entidad o una asociación. La tupla se presenta como un conjunto de valores ordenados para una serie de atributos: t=(a₁,a₂,a₃,...,a_n) con ai perteneciente a D_i=dominio de A_i. (Existen otro tipo de representaciones menos usadas tales como: t=(A₁:a₁,A₂:a₂,...,A_n:a_n) ).

El valor que una tupla tiene sobre un atributo concreto se representa con t[A_j]=a_j (proyección de la tupla t sobre el atributo j).

A	B	C	Cabecera de la relación (invariable en el tiempo)
a1	b1	c2
a1	b2	c2
a1	b3	c1
a2	b5	c2	Cuerpo de la relación (variable en el tiempo)
a3	b6	c3
a2	b2	c3

•       Una relación representa al conjunto de todos los atributos j de una instancia concreta. Una relación tiene dos partes: una cabecera que corresponde al esquema de la relación y un cuerpo que corresponde al conjunto de tuplas.

Una relación se representa por R(R ) donde R es un conjunto de atributos y la relación es un subconjunto del conjunto de todas las combinaciones posibles entre los valores de los dominios subyacentes de los atributos de R.

3.2 Claves y reglas de integridad.

En todos los modelos debe de existir una forma de identificar cada tupla de la relación. Para ello se usa un atributo o bien un conjunto de atributos. En muchos casos, varios atributos pueden identificar a una tupla: aparece el concepto de superclave.

•       Superclave. Sea R(R) una relación. Un atributo (o conjunto de atributos) X de R es superclave de R(R) si para cualquier elemento t de R, X permite identificar a t de manera unívoca. En el peor de los casos una superclave de una relación coincide con todos los atributos de la misma.

•       Clave. K es clave de una relación R(R) si es superclave y no existe un subconjunto de K menor que K que sea superclave. Todos los atributos que participan en una clave candidata se denominan atributos primos.

Muchas veces se da la situación de que una relación tiene un conjunto de posibles claves (claves candidatas). Entonces, de entre todas estas hay que seleccionar una de ellas como clave de esa relación. A esta clave se la denominará clave primaria. Todos loa atributos que participan en una clave candidata se denominan atributos primos.

•       Sea R(R) y S(S ). Suponemos que $K_síR. Si K_s es clave primaria de la relación S, se le denomina clave externa de la relación R para la relación S. Ejemplo:

EMP(NSS#, Nombre, Ciudad, Departamento#)

DEP(Departamento#, NombreDep, Otros)

Departamento# es clave externa de la relación EMP para la relación DEP. Dicho valor sirve para referenciar una tupla de DEP dentro de la relación EMP.

Las claves externas suponen la herramienta fundamental de conexión entre las relaciones. Nos van a permitir representar las asociaciones que existen entre entidades. Las relaciones R y S no necesariamente tienen que ser disjuntas: EMP(NSS#, Nombre, Ciudad, Dpto#, NSS#_Responsable).

Reglas de integridad.

1.   Un valor de clave primaria no puede ser nulo. Ni siquiera uno de los atributos de la clave primaria en particular puede serlo. A esta regla la denominamos regla de integridad de la entidad.

2.   Si K_síR dadas R(R) y S(S) en una clave externa, entonces "t�R, t[K_s]={null|v�$t'�S/v=t'(K_s)}. Es decir, si sobre una clave externa aparece un valor distinto de nulo, esta regla nos dice que necesariamente tiene que existir una tupla en la relación que de referencia con ese valor de clave primaria (todas las referencias tienen que ser integras y válidas). A esta regla se la denomina regla de integridad referencial.

La mayoría de las implementaciones obligan a cumplir la 1� regla, pero la 2� no es tan fácil de cumplir por lo que a veces no es obligatoria.

3.3 Álgebra relacional.

Es un conjunto de operadores a disposición del usuario para manipular los objetos de la base de datos. Este conjunto es reducido y cerrado (toma como entrada una o dos relaciones y como salida obtiene una nueva relación). Dentro de los operadores del álgebra relacional tenemos:

•       Operadores puramente algebraicos. Son los operadores típicos de conjuntos. É (unión), � (intersección) y - (diferencia) sólo pueden ser aplicados cuando los esquemas de las relaciones operando sean iguales. x (producto cartesiano) obtiene una relación cuyos atributos son resultado de la concatenación de los atributos de los operandos ( R(A,B,C) x S(B,D,E) = RxS(A,B,C,B,D,E) ).

•       Operadores relacionales. Los principales son selección (s), proyección (P), concatenación o "join" (∞) y división (�).

•       Selección. Dada la relación R se define la relación s_p como el conjunto de tuplas de R que satisfacen el predicado p: s_p(R)={t�R / P(t)}. El esquema de la relación resultante sería R, es decir, el mismo que el de la relación R (Obtenemos un subconjunto horizontal). Ejemplo: Militar(DNI#, Nombre, Rango, Edad). s_Rango="Cabo"(Militar)={Cabos de la base}

•       Proyección. Si xíR se define P_x(R) como el conjunto de las proyecciones de las tuplas de R sobre el atributo x: xíR, P_x(R)={t[x] / t�R}. El esquema obtenido en la relación resultante sería x (Obtenemos un subconjunto vertical de la base de datos). En el caso de obtenerse duplicaciones en el resultado, estas son eliminadas automáticamente.

Ejemplo: Militar(DNI#, Nombre, Rango, Edad). P_Rango (Militar)={Rangos distintos}

Ejemplo: Militar(DNI#, Nombre, Rango, Edad). P_Rango,DNI# (Militar)={Rangos y DNI's}

•       Concatenación. Existen dos tipos de concatenación: Join natural y q_join.

�Join natural: Consideremos R(R) y S(S) tales que R�S �� (tienen algún atributo en común). Se define (R∞S) como una relación cuyo esquema es la concatenación de los dos esquemas eliminando en uno de ellos los atributos repetidos y cuyos datos son el conjunto resultante de la unión de los datos de las relaciones anteriores.

Ejemplo:

R	(A,	B)		S	(B,	C)		R∞S	(A,	B,	C)
	a1	b1			b1	c1			a1	b1	c1
	a2	b1			b2	c2			a2	b1	c1
	a1	b2			b2	c1			a1	b2	c1
									a1	b2	c2

Se pueden realizar join's sobre un atributo únicamente. En este caso se escribe dicho atributo sobre el símbolo ∞. Generalmente, el join natural se usa para conectar relaciones a través de las claves externas.

A=D

R

(A,

B)

S

(B,

C,

D)

R∞S

(A,

R.B,

S.B,

C,

D)

a1

b1

b1

c1

d1

a1

b1

b1

c1

d1

a2

b1

b2

c1

d1

a1

b1

b2

c1

d1

a1

b2

b2

c1

d2

a2

b1

b2

c1

d2

a1

b2

b1

c1

d1

a1

b2

b2

c1

d1

�q_join: Es semejante al join natural en su funcionamiento. La diferencia radica en que mientras que el join natural basaba sus relaciones en un atributo común, el join natural la basa en una relación previamente establecida en la que intervienen operadores relacionales {=,<,>,>=,>=,<>}.

•       División. Sea R(A₁,A₂,A₃,...,A_n,B₁,B₂,...,B_m) y S(B₁,B₂,...,B_m).El resultado de la división es una nueva relación (R�S)(A₁,A₂,A₃,...,A_n) en la que las tuplas pertenecientes a la misma verifican que "t'=<y>�S tiene que existir una tupla t''=<xy>�R donde <y>=(B₁,...,B_m) y <x>=(A₁,...,A_n).

Ejemplo: Piloto(DNI#,Avión), Aviones(Avión), Piloto�Aviones(DNI#)={Pilotos que pilotan todos los tipos de aviones de Aviones}

•       Operadores adicionales. Dentro de este tipo de operadores nos encontramos con dos principales: el operador adición (�) y el operador agrupamiento (S).

•       Adición. Sirve para añadir a una relación un determinado atributo en donde el valor que tiene una tupla sobre ese nuevo atributo es el resultado de la expresión que aparece en este formato de la expresión: �_Expresión Nuevo_atributo (Relación).

Ejemplo: Productos(Nombre, Precio, Color), � _Precio*1,15 Precio_IVA(Productos)

Podemos eliminar el nuevo atributo proyectando la nueva relación sobre el resto de los atributos.

•       Agrupamiento. Sirve para reordenar las tuplas de una relación formando grupos. El formato que tiene es el siguiente: S_Atributo [�_{Función_agregada}Nuevo_Atributo...](R) que produce un ordenamiento de la relación R por el atributo especificado (La parte entre corchetes es opcional). El esquema de la relación resultante es el atributo sobre el que se aplica la misma y los nuevos atributos añadidos si es que los hay.

Ejemplo: S_DNI# (Alumno) crea una lista de DNI's de alumnos ordenados.

Ejemplo: S_Nombre�_{Media(Precio)}PrecioMedio�_{Cuenta(Ciudad)}NumeroCiudades(Producto) con la relación Producto(Nombre, Ciudad, Precio) crea una nueva relación cuyo esquema resultante es (Nombre, PrecioMedio, NumeroCiudades) ordenada por nombres que contiene los precios medios de los productos especificados por el nombre y el número de ciudades que venden dicho producto.

Las funciones agregadas para este tipo de operación son cuenta, suma, media, máximo y mínimo entre otras.

3.4 Conversión de diagramas E/R a tablas.

La regla básica consiste en convertir cada una de las entidades del diagrama en una relación, cuya clave primaria será el identificador de la entidad (En el caso de darnos cuenta de que esto no sucede así es seguramente porque el diagrama del que partimos está mal diseñado). Tenemos los siguientes casos:

•       Relación 1:1 de A(A#,otros) con B(B#,otros). En una de las dos relaciones se introduce como clave externa el atributo identificativo de la otra: A(A#,otros,B#) y B(B#,otros) con B# clave externa de A para la relación B. En el caso de opcionalidad a uno de los lados, la clave externa se presentará en la relación correspondiente a la entidad obligatoria.

•       Relación 1:N de A(A#,otros) con B(B#,otros) donde A es el lado 1 y B el lado muchos. Se introduce en la relación B el atributo identificativo de la clave A como clave externa quedando A(A#,otros) y B(B#,otros,A#).

•       Relación N:M de A(A#,otros) con B(B#,otros). En este caso se crea una nueva relación con el nombre de la asociación que contiene los atributos identificadores de A y B además de los suyos propios en el caso de existir. En el caso de que la clave primaria no coincida con la concatenación de las claves primarias de A y B seguramente es porque hemos realizado un diseño erróneo de la base de datos. Las relaciones resultantes por tanto quedarían: (A#,otros), B(B#,otros), Asociación(A#, B#, otros).

•       Asociaciones unarias. El funcionamiento es similar al de las relaciones binarias.

•       Asociación ternaria 1:1:1. Además de las relaciones ya existentes se crea una nueva con los atributos de la misma y con las claves externas de dos de las relaciones que participan en la asociación.

•       Asociación ternaria 1:1:N. Al igual que en las de tipo 1:1:1 se crea una nueva relación con las claves externas de dos de las relaciones que participan en la asociación, teniendo en cuenta que una de las dos ha de ser la clave primaria de la relación del lado N de la asociación.

•       Asociación ternaria 1:N:M. Se crea una nueva asociación cuya clave primaria es resultado de la concatenación de las claves externas para las relaciones del lado N y M.

•       Asociación ternaria N:M:Ñ. Se crea una nueva asociación cuya clave primaria corresponde con la concatenación de las tres claves primarias de las relaciones integrantes.

•       En las especializaciones y generalizaciones se emplean asociaciones diferentes para supertipos y subtipos siempre y cuando cada uno aparezca en una asociación diferente. En el caso de no aparecer en asociaciones no merece la pera la representación de estas.

CONVERSIóN DIAGRAMA E/R

La regla básica consiste en convertir cada una de las entidades del diagrama en una relación, siendo la clave primaria el atributo identificador de la entidad.

Conversiones:

�

A(A#,O_A,B#)

B# es clave externa para la relación B

B (B#,O_B)

La clave externa debe aparecer en la relación correspondiente a la entidad obligatoria.

�A(A#,O_A)

�B(B#,O_B,A#)

A# clave externa para A

La relación que se representa en la entidad del lado "muchos" es la que incluye como clave externa el identificador de la entidad del lado "uno" y todos los atributos conectados sobre la asociación.

A(A#,O_A)

B(B#,O_B,A#,atr)

A(A#,O_A)

�B(B#,O_B,A#)

Las relaciones muchos a muchos generan una nueva relación con el nombre de la asociación, la clave primaria de A, la clave primaria de B y los atributos de la asociación.

A(A#,O_A)

B(B#,O_B)

ASOC(A#,B#, atr) A#B# clave primaria, A# clav. ext. B# clav. ext.

Si A#B# no forman clave primaria de ASOC debemos pensar que ASOC está mal diseñado y que esa asociación se debe modelar con asociaciones dependientes pues puede estar expresando una variación en el tiempo aunque no siempre ese es el motivo.

A(A#,O_A,Ref_A#)

No podemos poner A(A#,O_A,A#) pues habría dos atributos con el mismo nombre. Renombramos el último a Ref_A#.

Todas las asociaciones ternarias se convierten en una asociación (Excepción: algunas relaciones 1:1:1 no interesan convertirlas en relación y conviene llevar las claves externas a una de las tres relaciones junto con los atributos de la asociación).

ASOC (A#,B#,C#)

Las claves, serán:

-relación 1:1:1 => A#B# ó B#C# ó A#C# ó B#C# (cualquier par entre A#,B#,C#)

-relación N:1:1 => A#B# ó A#C# (la clave del muchos siempre participa)

-relación N:M:1 => A#B# (las dos del muchos)

-relación N:M:L => A#B#C# (las tres)

Generalizaciones y especializaciones:Se crea una relación para el supertipo si éste aparece en alguna relación y si no, no merece la pena representar el supertipo.

Borrado de tuplas

Cuando se borra una tupla, el borrado puede ser:

- Borrado en cascada (on delete cascade)

Cuando se borra una tupla referenciada, todas las otras tuplas que la referencian son borradas.

- Borrado a nulo (on delete null)

Cuando se elimina una tupla referenciada, aquellos valores que referencian esa tupla, se ponen a nulo.

- Borrado por defecto (on delete default)

Cuando se elimina una tupla referenciada, aquellos valores que referencian esa tupla, se ponen a un valor por defecto para ese atributo.

TEMA 4 - TEORíA DE LA NORMALIZACIóN

INTRODUCCIóN

La teoría de la normalización es una teoría sobre el diseño de relaciones que nos proporciona una herramienta que permite definir el nivel de diseño que tiene una relación y herramientas para descomponer una relación y obtener relaciones que estén en el nivel de diseño adecuado.

Existen dos tipos fundamentales de defectos a la hora de diseñar una relación: redundancia de datos y anomalías de inserción/borrado.

Supongamos que tenemos la siguiente relación:

ESTUDIANTE_INFO (Nombre,Cod_Curso,Tfno,Asigantura,Profesor,Nota)

En este ejemplo hay redundacia de datos, pues un alumno puede estar matriculado en varios cursos. También el nombre de la asignatura o del profesor se repite en todas las tuplas de los alumnos, etc. Estas redundancias pueden producir inconsitencias y poca flexibilidad (p.ej. si un profesor se da de baja hay que cambiar todas las tuplas de los alumnos).

Las anamolías de inserción se refieren a que no se puede almacenar una información determinada. Por ejemplo, si se crease una nueva asignatura en la que aún no se ha matriculado ningún alumno, cómo representaríamos esa asignatura. No podemos poner (null,null,null,asignutura,profesor,null) pues tendríamos claves primarias con valor null.

Las anamolías de borrado se refiere a perder información relevante al intentar borrar una información no relevante. Por ejemplo si sólo hay una alumno matriculado en una asignatura y borramos el alumno, tal y como está construida la relación borraríamos también la asignatura.

La teoría de normalización propone la posibilidad de definir el nivel de diseño y propone herramientas para obtener, a partir de una relación otras relaciones tales que todas esas nuevas relaciones se encuentran en un nivel de diseño mayor que la relación original.

La descomposición de una relación debe verificar que:

•                     sea reversible por concatenación: el join de las relaciones resultantes de la descomposión debe dar como resultado la relación original.

•                     toda la información semántica de la relación original debe permanecer en las relaciones resultado, esto es, deben mantenerse las dependencias funcionales.

DEPENDENCIAS FUNCIONALES

Son herramientas sencillas que nos permiten formalizar parte de la semántica de la relación.

Sea R una relación con el esquema R(X,Y,Z), se dice que R satisface la dependencia funcional X->Y (X determina funcionalmente a Y, ó Y depende funcionalmente de X) si cualquiera que sea x valor del dominio de X, la relación P_y (s_X=x(R)) contiene a la sumo UNA tupla (en otras palabras, asociado a un único valor de x hay un único valor de y). A X se le conoce como antecedente y a Y como consecuente.

Ejemplo: R( A B C D)

a1 b2 c1 d1 B->D cierto, todas las tuplas con un valor de B tienen

a1 b3 c1 d2 asociado un único valor de D (b2->d1,b3->d2)

a2 b2 c2 d1 A->D falso, pues a1->d1 y a1->d2

a1 b2 c2 d1 CD->B cierto: c1d1->b2 c1d2->b3 c2d1->b2

La dependencia funcional es algo virtual, pues si añadimos una nueva tupla las dependencias se pueden romper. Por eso nos fijaremos en las dependencias funcionales asociadas al esquema de la relación, a la parte invariable, para así imponer que cualquier extensión válida de la relación satisfaga esa relación válida.

P.ej. el código postal, la calle y la ciudad: la calle y la ciudad determinan el mismo código postal. De no ser así, esa tupla será errónea. El sistema de BD debe imponer esa restricción.

Sea � un esquema de relación y sean X,Y í �, decimos que X->Y está asociado a � si "R(�), R satisface necesariamente la dependencia funcional X->Y.

A partir de ahora, a cada relación le asociaremos un conjunto F de dependencias funcionales.

AXIOMAS DE AMSTRONG

Son axiomas que aplicaremos para desarrollar las reglas funcionales. Consideraremos que tenemos una relación � y un conjunto de atributos X,Y,Z,W � � que pueden ser simples o compuestos.

Axioma 1- Reflexividad: Cualquier relación R(�) satisface que X->X.

Axioma 2- Aumentación: Si R satisface X->Y entonces R satisface XZ->Y

Demostración:

t₁,t₂ � R / t₁(XZ)=t₂(XZ) ===(en particular)==> t₁(X)=t₂(X)

como por hipótesis R satisface X->Y ==> t₁(Y)=t₂(Y)

Axioma 3- Aditividad: Si R satisface X->Y y X->Z entonces R satisface X->YZ.

Demostración:

t₁,t₂ � R / t₁(X)=t₂(X),

por hipótesis X->Y ==> t₁(Y)=t₂(Y) |

X->Z ==> t₁(Z)=t₂(Z) | ==> t₁(YZ)=t₂(YZ)

Axioma 4- Proyectividad: Si R satisface X->YZ ==> R satisface X->Y

Demostración:

t₁,t₂ � R / t₁(X)=t₂(X)

por hipótesis X->YZ => t₁(YZ)=t₂(YZ) => t₁(Y)=t₂(Y) y t₁(Z)=t₂(Z)

Axioma 5- Transitividad: Si R satisface X->Y y Y->Z entonces R satisface que X->Z.

Demostración:

t₁,t₂ � R / t₁(X)=t₂(X) y como X->Y => t₁(Y)=t₂(Y)

Como R por hipótesis Y->Z t₁(Y)=t₂(Y) => t₁(Z)=t₂(Z) => X->Z

Axioma 6- Pseudotransitividad: Si R satisface X->Y y YW->Z => XW->Z.

Demostración:

t₁,t₂ � R / t₁(XW)=t₂(XW) => t₁(X)=t₂(X) ₍₁₎ y t₁(W)=t₂(W) ₍₂₎

por hipótesis X->Y ==(1)==> t₁(Y)=t₂(Y) ==(2)==> t₁(YW)=t₂(YW) =>

=> YW->Z

Con estas reglas de Armstrong podemos obtener nuevas dependencias funcionales. Un conjunto de dependencias funcionales F infiere una dependencia funcional X->Y (y se representa: F ╞ X->Y) si la dependencia funcional X->Y se puede obtener a partir de F por aplicación de los axiomas de Armstrong. Por definición, F infiere a todas las dependencias funcionales de F, esto es, X->Y ╞ X->Y.

CLAUSURAS

Al conjunto de dependencias funcionales que se infieren a partir de F se lo denomina clausura de F y se denota con F⁺.

F⁺ = {X->Y / F╞ X->Y}

F⁺ es un conjunto tal que incluye a F y tal que si aplicamos los axiomas de Armstrong a sus dependencias funcionales no se obtenienen nuevas dependencias funcionales, pues ya incluye a todas las posibles. Por ello (F⁺)⁺=(F⁺).

Ejemplo: R=(A,B,C) F={A->B,B->C}

F⁺= {A->B,B->C,A->A,B->B,C->C,AB->A,ABC->A,AB->C,BC->C....}

Como F⁺ es un conjunto muy grande, necesitaremos buscar una herramienta que nos permita saber si una dependencia funcional pertenece a F⁺ sin tener que calcular F⁺.

Definición: Sea � un esquema de relación y X un atributo del esquema � (X��), y sea F un conjunto de dependencias funcionales sobre �, se llama clausura de X respecto de F, y se denota con X_F⁺ al atributo más grande de � tal que X-> X_F⁺ �F⁺.

Ejemplo: R(A,B,C) F={A->B,B->C}

A->A y A->B => A->AB |

B->C y A->C => A->AC | => A->ABC A_F⁺=ABC

Proposición

Sea � un esquema de relación, y X,Y� �, F conjunto DFs sobre �, entonces X->Y � F⁺ si y solo si Y�X_F⁺

Demostración:

=>) supongamos que X->Y �F⁺, como X->X_F⁺ � F⁺ y X_F⁺ es el más grande, entonces Y� X_F⁺ pues de no ser así X_F⁺ no sería el más grande al faltarle Y.

<=) X-> X_F⁺ � F⁺ como por hipótesis Y� X_F⁺ entonces por el axioma de proyectividad X->Y �F⁺

ALGORITMO PARA CALCULAR X_F⁺

Sea R(�) y F conjunto de DFs sobre �, X� �

Inicialmente X_F⁺ = X

Cambio = TRUE

while (cambio)

cambio=false

for (cada DF W->Z � F)

if w� X_F⁺ then X_F⁺= X_F⁺ É Z; cambio=true;

endfor

endwhile

END.

Ejemplo: F={A->G,CD->E,E->C,D->AH,AB->D,DH->BC}

inicio cd->e d->ah

(BCD)_F⁺=BCD E AH = BCDEAH (primera pasada)

a->g

(BCD)_F⁺ = BCDEAH G Resultado = BCDEAHG

Supongamos que tenemos R(�) F={A->B,B->C,A->C} y G={A->B,B->C}. Si observamos G y F notamos que ambos proporcionan la misma información: la dependencia A->C, la podemos conocer con G y los axiomas de Armstrong. G y F recogen en esencia la misma información, y nos interesa más G por ser más manejable.

Definición: Dos conjuntos de dependencias funcionales F y G se dicen equivalentes y se deonota con F�G cuando sus clausuras son iguales: F⁺=G⁺. Interesa eliminar las dependencias redundantes (aquellas que pueden obtenerse con el resto de las dependencias) y reducir en lo que podamos el conjunto de Dfs.

Definición: Sea R(�) y F un conjunto de Dfs sobre �, F se dice redundante si existe un F� � F tal que F� � F.

Ejemplo: F = {A->B,B->A,B->C,A->C} ¿es redundante?. Observemos cada una de las dependencias:

¿F-{A->B} ╞ A->B? A⁺_F-{A->B}=AC (no está B => esta dependencia no es redundante)

¿F-{B->A} ╞ B->A? B⁺_F-{B->A}=BC (no está A => esta dependencia no es redundante)

¿F-{B->C} ╞ B->C? B⁺_F-{B->C}=BAC (está C => esta dependencia es redundante:

elimina y trabajamos con el resto:)

F� = {A->B, B->A, A->C}

¿F�-{A->C} ╞ A->C? A⁺_F-{A->B}=AB

Supongamos ahora que F = {A->B, B->C, A->CD}, la dependencia funcional A->CD no es redundante, pero A->CD╞ A->D que no es redundante y A->CD╞ A->C que sí e redundante. Se dice entonces que C es un atributo extraño a la derecha.

Una dependencia funcional X->Y se dice simple si Y es atributo simple. Todas aquellas dependencias funcionales que no sean simples se pueden descomponer en dependencias simples (por axioma de proyectividad). Así, por ejemplo, si tenemos X->A₁A₂A₃ lo descompondremos en X->A₁, X->A₂ y X->A₃.

Observemos ahora F = {A->C, BC->D, B->C} , en donde F no redundante pero aquí sus atributos son simples y ocurre que B->C y BC->D ╞ B->D (axioma pseudo-transitividad) y B->D ╞ BC->D (pero no BC->D╞ B->D). La dependencia B->D aporta más información que BC->D. Se dice que C es un atributo extraño a la izquierda. Nos interesa más trabajar con F� = {A->C, B->D, B->C}

Sea R(�) y F conjunto de DFs sobre �. Sea X->Y � F con A�C (X es atributo compuesto). Se dice que A es extraño a la dependencia funcional X->Y respecto de F si F-{X->Y}É{X - A->Y} � F.

Consideremos BC->D. Queremos ver si C es extraño en BC->D. Esto sucedería si F�{A->C,B->D,B->C}� F. Siempre se cumple que F�� F por el axioma de aumentación, pero lo que puede que no sea cierto es que F╞ F�. Eso último sucederá cuando F╞ B->D, pero eso es equivalente a que D�B⁺_F. Por consiguiente, C será extraño en BC->D respecto de F si D�B⁺_F.

COBERTURA CANóNICA

Sea R(�) y F conjunto de DFs sobre �. Se llama cobertura canónica de F a un conjunto F_c tal que F_c es no redundante, todas sus dependencias funcionales son simples y no incluye atributos extraños a la izquierda. La cobertura canónica contiene la esencia de la información que maneja F.

Método para conseguir una F_c:

1- desdoblamiento de las dependencias funcionales: si encontramos un dependencia funcional cuyo consecuente sea un atributo doble se transforma en Dfs con consecuentes simples.

2- eliminación de atributos extraños a la izquierda.

3- eliminación de redundancias.

4- agrupacmiento de dependencias funcionales

Ejemplo:

Sea R(A,B,C,D,E,F,G,H,I,J) y

F ={A->B, A->C, B->CD, D->B, ABE->F, E->J, EG->H, H->G}

Consegir F_c:

1- Desdoblamiento. Resulta A->B, A->C, B->C, B->D, D->B, ABE->F, E->J, EG->H, H->G}

2- Eliminación atributos extraños a la izquierda.

ABE->F

¿A extraño? (BE)⁺_F = BECD Como A no pertenece => A no es extraño

¿B extraño? (AE)⁺_F = AEBCD... B pertenece => B es extraño

Quitamos ABE->F y ponemos AE->F

AE->F

¿A extraño? (A)⁺_F = ABCD Como F no pertenece => A no es extraño

¿E extraño? (E)⁺_F = EI F no pertenece => E no es extraño

EG->H

¿E extraño? (E)⁺_F = EJ Como H no pertenece => E no es extraño

¿G extraño? (G)⁺_F = G H no pertenece => G no es extraño

3- eliminación redundancias

¿A->B? A⁺_F-{A->B}=AC -> no es red.

¿B->C? B⁺_F-{B->C}=BD -> no es red.

¿D->B? D⁺_F-{D->B}=D -> no es red.

E->J y H->G no son redundantes

¿A->C? A⁺_F-{A->C}=ABCD -> es redundante. Eliminamos A->C

¿B->D? B⁺_F-{B->D}=BC -> no es red.

¿AE->F? B⁺_F-{B->D}=BC -> no es red.

¿EG->H? no es redundante (no hay ningún consecuente H)

Resulta F={ A->B, B->C, B->D, D->B, AE->F, E->J, EG->H, H->G}

4- Agrupamientos de Dfs:

F_c={ A->B, B->CD, D->B, AE->F, E->J, EG->H, H->G}

RELACION ENTRE DEPENDENCIAS FUNCIONALES Y CLAVES

Sea R(�) y F un conjunto de Dfs asociado a �, y x � �. Si encontramos un atributo tal que F╞ X->� (X⁺_F = �) entonces X es una superclave.

Las dependencias funcionales permiten automatizar el proceso de búsqueda de superclaves.

Una clave candidata es aquel atributo X � � tal que no existe X'� X tal que (X')⁺_F = �, o sea que X->� no contenga atributos extraños a la izquierda.

Sea R(�) y F_c, veremos un método que nos permita obtener las claves candidatas de R:

1- obtener K� � que contenga aquellos atributos de � que no aparecen como consecuente en F_c. Toda clace candidata es un superconjunto de K.

2- Si K⁺_Fc = � => K es la única clave candidata

3- Si K⁺_Fc � � => las claces candidatas de R serán de la forma KW, donde W es un atributo simple o compuesto de � que no está en �-K⁺_Fc (con W � �-K⁺_Fc).

Ejemplo:

Sea R=(ABCDEGH) y F={AC_>DE, B->G, BDE->C, G->H} ya canonizado.

1- No parecen como consecuente: A B

2 - (AB)⁺_F=ABGH no es clave candidata. La clave candidata tiene la forma ABX con X�{ C,D,E}

3- Veamos todas las posibles combinaciones:

(ABC)⁺_F=ABCGHDE = � => (ABC) es una clave candidata

(ABD)⁺_F=ABDGH � � => (ABD) no es una clave candidata

(ABE)⁺_F=ABEGH � � => (ABE) no es una clave candidata

(ABDE)⁺_F=ABCDEGH � � => (ABDE) es una clave candidata

Tenemos dos claves candidatas (ABC) y (ABDE)

NORMALIZACIóN POR MEDIO DE LAS DFS.

Existen varios niveles de diseño:

1FN = 1� forma normal. Es un nivel de diseño que debe existir en toda base de datos relacional. Una entidad está en 1FN cuando todos sus atributos son atómicos, es decir, en sus tuplas no existen grupos repetitivos.

2FN = Segunda forma normal. Una relación está en 2FN si cada atributo de la relación depende complentamente de una clave candidata. Si una relación ha alcanzado la 2FN, también ha alcanzado la 1FN.

3FN = Tercera forma normal. Sea R(�), F_c, decimos que R está en tercera forma normal si cada dependencia funcional X->Y satisface algunas de estas condiciones:

1- X es superclave

2- Y es primo (=participa en una clave candidata -puede no ser simple-)

Todas las relaciones 3FN son también 2FN.

FNBC = Forma Normal de Boyce-Codd. Sea R(�), F_c, decimos que R está en FNBC si para todo X->Y � F, X es una superclave (todas las Dfs deben provenir de claves). Todas las relaciones FNBC son también 3FN.

Ejemplo:

R(ABCD) con F_R={AB->C,D->C} y S(ABC) F_S={AB->C,C->AB}

¿Está R en FNBC?

Primero veremos las claves de R: la única clave que hay es ABD. Todas las Dfs de R no satisfacen la condición de FNBC, por lo tanto no está en FNBC.

¿Está S en FNBC?

Las claves de S son AB y C. Cumple la condición y sí está en FNBC

Nuestro objetivo es que todas las relaciones estén en FNBC.

Sea R(�) una relación con F conjunto de dependencias funcionales y R_i=P_X��(R), se llama proyección de F a �_i al conjunto F_i=P F ={X->Y � F /X,Y � �_i}

Si tenemos una relación R(�) con F conjunto de dependencias funcionales, si R no se encuentra en FNBC realizaremos un proceso de descomposición r_R = {R₁..R_n} donde R_i es la proyección de R sobre determinados atributos (R_i=P_X�� R)

Esa descomposición r_R debe satisfacer dos propiedades:

1- r_R deber ser "sin pérdida" o reversible por concatenación.

Es decir, R=R₁�R₂....�R_n

2- r_R debe "preservar" las dependencias funcionales, es decir É F_i�F.

Ejemplo:

Sea R(ABC) F={A->B,B->C,C->A}, r_R={R₁(AB),R₂(BC)} ¿preserva r_R las Dfs?

Primero calcularemos las depedendecias sobre cada descomposición

F₁=P_AB F = {A->B, B->A} F₂=P_BC F = {B->C, C->B}

F₁ É F₂ �F (B->A no apaerece en F pues allí es redundante, pero en F₁ no es redundante)

ALGORITMO DE DESCOMPOSICIóN EN FNBC

Este algoritmo tiene como entrada R(�), F_c y R que no está en FNBC, y obtiene como salida r_r / "R_i � r_R están en FNBC y r_R es sin pérdida:

1- Tomamos una dependencia funcional X->Y � F tal que X no es superclave.

2- Construimos dos relaciones R₁=P_X,Y(R)=R₁(X,Y) y R₂=P_�-Y(R)=R₂(�-Y). Todos los atributos de R₁ menos el consecuente.

3- Si alguna de las dos relaciones no está en FNBC se vuelve a aplicar el algoritmo.

El algoritmo garantiza que la descomposición es reversible pero no garantiza que preserve las dependencias funcionales. La salida del algoritmo no es única, y algunas de ellas no preservan las dependencias funcionales.

Ejemplo:

R(ABCDE) F={A->B,AC->D,BD->E} que está canonizado.

Busquemos las claves: sólo hay una AC (AC)⁺=ABCDE

1- Tomamos A->B

2- R₁(AB) R₂(ACDE)

3- F₁={A->B} clave A => está en FNBC

F₂={AC->D,AD->E} A->B y BD->E => AD->E Clave AC => no está en FNBC

Aplicamos el algoritmo sobre R₂ y F₂:

1- Tomamos AD->E

2- R₃(ADE) y R₄(ACD)

3 F₃={AD->E} clave (AD) -> FNBC F₄={AC->D} clave (AC) -> FNBC

Fin del algoritmo: r_r={R₁(AB),R₃(ADE),R₄(ACD)}

Veamos ahora si preserva las dependencias funcionales:

Tenemos que ver si F₁ É F₃ É F₄ � F_c

Como AC->D � F_c y A->B � F_c solo hay que ver si F₁ É F₃ É F₄ ╞ BD->E

(BD)⁺ _{F1 É F3 É F4 = BD , E no pertenece => no preserva las Dfs}

_Como r_R no es única y depende del antecedenete tomado, obtendremos otro r_R.

BD->E

R₁(BDE) F₁={BD->E} (BD) FNBC

R'(ABCD) F�={A->B,AC->D} (AC) no FNBC

A->B

R₂(AB) F₂={A->B} (A) FNBC

R₃(ACD) F₃={AC->D} (AC) no FNBC

Ahora hay que ver si F₁ É F₂ É F₃ � F_c lo cual se ve a simple vista. Mantiene las dependencias funcionales.

ALGORITMO DE DESCOMPOSICIóN EN 3FN

Entrada del algoritmo: R, F_c

Salida del algoritmo: r_R sin pérdida, manteniendo Dfs y con relaciones al menos en 3FN.

Algoritmo:

Paso1: Obtener todos los atributos de � que no aparezcan en F_c (lo llamaremos R₁). Construir R₁(�₁) y ponerlo en la salida.

Paso2: Hacer �=�-�₁

Paso3: Si $ X->Y �F_c tal que �=XY => construir R₂(XY) y ponerlo en la salida

si no, para cada Df X->Y � F_c, construir R_i(XY) y ponerlo en la salida.

Ejemplo:

R(ABCDE) F_c={A->B, AC->D, BD->E} (AC)

No está en 3FN pues A->B no cumple ninguna de las dos condiciones de 3FN

1 y 2- no hay

3- R₁(AB) F₁={A->B} (A) => está en FNBC

R₂(ACD) F₂={AC->D} (AC) => está en FNBC

R₃(BDE) F₃={BD->E} (BD) => está en FNBC

Dada una relación R con r_R={R₁,R₂} (descomposición en DOS relaciones), con �₁É�₂=�, r_R es reversible por JOIN si �₁��₂->�₁-�₂ � F⁺ ó �₁��₂->�₂-�₁ � F⁺