Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
Clase 3: Normalización 2.019 BASE DE DATOS FAC.DE INGENIERIA – UNJu 2.018 3.- DEPENDENCIA FUNCIONAL “1 depend.funcional es 1restricción entre 2conj.de atributos de 1 BD.” Dado el esquema d 1 BD Relac. R={A1,A2,...,An}, 1depend.funcional X <== Y ( Y depende fcionalmente d X ) entre 2conj.de atributos X e Y q son subconj.de R, implica q existe 1depend.entre las posibles tuplas t1 y t2 q pueden pertenecer a la relación r(R). Esta dependencia conlleva a q p/ toda tupla t1 y t2 pertenecientes a la relación r, siempre que t1[X] = t2[X] se verifica que t1[Y] = t2[Y] Es decir, Y es funcionalm.depend. d X si y solo si, p/toda tupla d la relac.en la q X toma un valor, le corresponde un mismo valor p/Y (tal como se muestra) Relación (R) = BD de Alumnos 3.- DEPENDENCIA FUNCIONAL 1esquema relac.R(A,F) está constituido x1conj.d atrib. A={A1,A2,...An} y 1conj.de dependencias funcionales F existentes entre dichos atributos. X ej. en la relac.EMPLEADO_PROYECTO, se pueden establecer las sig.depend.fcionales: Numb_P ( (Nomb_P, Situ_P): esta dependencia indica q x el nro de un proyecto (Num_P) queda determinado su nombre (Nomb_P) y su situación (Situ_P). (CUIL, Num_P) (Horas) : conj.formadoXel nro.d la seguridad social d 1 empleado y el nro de un proy.q determinan funcionalm.las horas q un empleado trabaja en el. Depend.Fcionales de la relac.EMPLEADO_PROYECTO: CUIL (Nombre_E): esta depend.func.indica q el nro.de cuil (CUIL) de 1empleado determina el nombre del mismo (Nomb_E). Igualmente s puede decir q Nomb_E está funcionalm.determinado por NSS ya q dado 1valor de CUIL conocemos el valor de Nomb_E. REGLAS DE INFERENCIA LÓGICAS PARA DEPENDENCIAS FUNCIONALES Sea F 1conj.de depend.fcionales.especificadas en 1esquema Relac.R, y sea ƒ una depend.fcional.definida sobre el conj.de atrib.del esquema relac., se dice q F implica o infiere lógicamente a ƒ, (F = f), si c/relación r(R) q satisface las depend.fcionales en F también satisface ƒ. X ej., p/el sig.conj.de dependencias fcionales: F = { CUIL { Nomb_E, Fech_na, Dirección, Num_D }, Num_D { Nomb_D, CUIL_jefeD} } De F se pueden derivar las sig.depend.: CUIL { Nomb_E, CUIL_jefe } ƒ1 CUIL CUIL ƒ2 Num_D Nomb_D ƒ3 Las depend.fcionales.q se infieren de 1conj.de dependencias F están determinadas x las denominadas REGLAS DE INFERENCIA REGLAS DE INFERENCIA a) Reflexiva: 1 conj.de atrib.siempre se determina a si mismo y a 1subconj.propio. Si Y “está incluido en” X, X ⊆ Y entonces X Y Ej.: {CUIL, Nomb_E} Nomb_E {CUIL, Nomb_E} CUIL b) Aumentación: Si se suma 1conj.de atributos a ambos lados de 1dependencia fcional se obtiene otra dependencia fcional igualmente válida. Si X Y entonces XZ YZ Ej: {CUIL, Nomb_E} Dirección {CUIL, Nomb_E,Fech_na} {Dirección, Fech_na} c) Transitiva: Si Y depende funcionalmente de X, y Z depende funcionalm.de Y, entonces se verifica que Z depende funcionalm.d X. Si { X Y, Y Z } entonces X Z Ej. {CUIL} {Num_D} {Num_D} { Nomb_D} {CUIL} {Nomb_D} Estas 3 propiedades se conocen con el nombre de Axiomas de Armstrong y a partir d ellas se pueden deducir: REGLAS DE INFERENCIA d) Proyección: Si el conj.de atributos Y depende fcionalmente de X y s verifica q los valores del conj.de atributos Z están incluidos en los valores de Y, entonces se tiene q cumplir que Z depende funcionalm.d X. Si X Y ⊆ Z { X Y, X Z} Esta propiedad se puede demostrar a través de los axiomas de Armstrong: Aplicando la propiedad reflexiva: YZ Y YZ Z Mediante la propiedad transitiva: X Y X Z De esta prop.s desprende que se puede descomponer 1depend. fcional X { A1, A2,..., An } en 1conj.de depend.{ X A1, X A2, ... , X An} REGLAS DE INFERENCIA e) Unión: Si Y depende funcionalm.de X y se cumple q Z está fcionalm. determin.por X, entonces s verifica q Y y Z dependen funcionalm. d X. Si { X Y, X Z } X YZ Demostración: Por aumentación: X Y ==> X ⊆ X Y ⊆ X X YX X Z ==> YX YZ Con las nuevas dependencias por transitividad ==> X Y Esta prop.es la contraria a la proyección, permite combinar un conj. de depend.fcionales.{ XA1, XA2,..., XAn } en 1única depend. func. X { A1, A2,..., An } f) Pseudotransitiva: Si { X Y, WY Z } WX Z Demostración: Por aumentación X Y ==> WX WY Como WY Z, aplicando propiedad transitiva ==> WX Z X desaparece ya que está Incluida en sí misma REGLAS DE INFERENCIA CLAUSURA DE X BAJO F: Sea X 1conj.de atributos y F un conj.de depend. fcionales con X a la izq. La clausura de X bajo F, X* es el conj.de atrib.fcionalm. depend. d X bajo F más las depend.inferidas de F. Algorit.d la clausura de X bajo F, X* o X+: El valor inicial q toma X* está formado x todos los atributos de X, a continuación, a través de las reglas de inferencia transitiva, proyección y unión se van añadiendo nuevos atributos a X* apoyándose en las dependencias funcionales de F. X*:=X Repeat Antiguo X*:=X*; Por cada dependencia funcional Y Z do If Y ⊆ X*:then X*:=X* Z (ó X*:=X* U Z) Until ( antiguo X* = X*); X+ := X repetir viejoX+ := X+; para cada df Y -> Z en F hacer si Y ⊆ X+ entonces X+ := X+ U Z; hasta que (viejoX+ = X+); SUPERCLAVE 1conj.de atrib.de 1relación es superclave si y solo si ese conj.de atrib. determina a todos lo demás, es decir, si dicho conj. de atrib. determina unívocamente c/tupla de la relación. Una superclave de R = {A1, …, An} es un conj.de atributos S ⊆ R tal q no existen 2 tuplas t1 y t2 en ningún r tal que t1[S] = t2[S]. CLAVE O CLAVE CANDIDATA Dada 1relac.R = { A1, A2,..., An }, 1superclave de la relación es clave o clave candidata si es superclave mínima, es decir, si no existe ningún subconj.de atrib.d dicha superclave del cual dependan fcionalmente todos los demás atrib.d la relac. Cuando existen varias claves candidatas, se elige 1de ellas como clave primaria de la relac.denominándose al resto claves secundarias. ATRIBUTO PRIMARIO 1atrib.es primario si pertenece a alguna de las claves candidatas de la relac.tipo. Ej: AE determinan a todos los demás atributos de la relación, x lo tanto es superclave, además es superclave mínima ya q ni A ni E determinan a todos los atrib,, de ahí q tanto D como AE son claves candidatas. 1clave primaria es 1campo o grupo de campos q identifica de forma única a c/registro dentro de 1tabla. Una clave foránea en 1BD Relac.es 1clave q se usa en1tabla secundaria y q coincide con la clave primaria en 1tabla primaria relacionada. Las claves foráneas pueden tener valores duplicados (multiplicidad) en la tabla secundaria, mientras q p/las claves primarias eso no es posible. El uso apropiado de claves foráneas permite exigir la integridad referencial. Ej. CLAVE FORANEA NORMALIZACIÓN Es 1proceso reversible mediante el q se realiza 1descomposición progresiva d 1conj.de relac.dadas en sucesivos conj.caracterizados x presentar relac.c/vez +sencillas y regulares, alcanzando la estructura óptima p/su implement., gestión y explotación desde diferentes futuras aplicaciones. “El objetivo de la normalización es eliminar las anomalías detectadas en 1 esquema relac.de 1BD cuando éste presenta 1estructura no satisfactoria.” Los principales problemas q se pueden presentar en 1esquema relacional son: - Existencia de Réplicas: Cierta informac.puede aparecer duplicada innecesar., provocando desaprovechamiento del espacio de almacenam. - Anomalías de actualización: Como result.d la existencia de informac. redundante, 1operac.de actualizac.puede llevar a1estado inconsist.de la BD. - Anom.d Inserción: Puede resultar imposible añadir nueva informac.en la BD. - Anomalía de Borrado: Eliminar informac.puede desencadenar lapérdida no deseada de otro tipo de información. NORMALIZACIÓN El proceso de normaliz.parte de 1esquema relac.q contiene todos los atrib.(y anomalías ), y d forma interactiva se descompone en 2 o + relac. q se encuentran en una Forma Normal (FN) superior. “1 relac.está en una FN cuando satisface el conj. de restricc.impuestas p/dicha forma.” Las ventajas de la Normalización de datos: - Facilidad de uso: Los datos se encuentran agrupados en tablas que identifican claramente un objeto o una relación. - Facilidad de gestión: Los leng.manipulan la informac.d forma sencilla mediante operac.de álgebra y cálculo relacional aplicadas sobre las tablas. - Integridad: Las interrelaciones establecidas entre elementos de diferentes tablas permiten asegurar la integridad de la información almacenada. - Mínima redundancia: La informac.no aparece duplicada innecesariamente dentro de las diferentes estructuras constituyentes de la BD. - Máximo rendimiento de las aplicaciones: C/aplicación únicamente “ve” aquella parte d la información q le sirve de utilidad. NORMALIZACIÓN La descomposición de 1esquema relac.R(A,F), donde A es el conj.de atrib.q lo constituyen y F el conj.de depend.fcionales definidas sobre dichos atrib., es la sustitución de dicho esquema x 1colección p ={R1,R2 ,...,Rn } subconj.de R, de forma q se verifica: R= R1, R2, R3, ..., Rn. P/q1relación r(R) se pueda descomponer en 1conj. de p relaciones se deben cumplir: 1) Preservar el contenido de la relación Toda información q aparezca en R, debe aparecer en p. Esta prop.puede obtenerse imponiendo las sig. condiciones: - La unión de todos los atrib.de las p relac.da el conj.de atrib.de la relación R. R(A,F) ==> p= { R1 (A ,F ), R2 (A ,F ),...,R3 (A ,F ),} A = A1, A2, ... An - En c/relación Rn, p debe ser 1proyección de R de tal forma q R pueda crearse uniendo todos los Rn. NORMALIZACIÓN 2) Preservar el conjunto de dependencias Las depend.fcionales F son prop.inherentes al esquema relac. R(A,F). Imponer q éstas se mantengan, equivale a q todas las depend.fcionales q s verifican en R, se cumplan en p. “Estas restricciones se pueden englobar diciendo q, al hacer la descomposición no se debe perder ningún atributo ni ninguna dependencia.” 3) Carácter normal de las relaciones La 3ra.prop.q se desea cumplir es q cuando se construye un esquema relacional éste debe estar en FN. “Las FN son 1conj.de prop.deseables p/los esquemas relacionales. Al proceso de descompos.de 1relación tipo R en esquemas p={R} q estén en FN se denomina Normalización”. NORMALIZACIÓN En 1970 Codd definió la 1ra., 2da. y 3ra. FN (INF, IINF, IIINF respectivamente). Boyce y Codd en 1974 definieron 1versión mejorada de la IIINF, conocida como BCNF ( Boyce-Codd Normal Form), ésta fue depurada con la definición de la 4ta, IVNF, (Fagin 1977) y 5ta, VNF, (Fagin 1979). “El proceso de descomposición de 1relación en otras no estriba únicamente en 1 normalización, sino además se debe preservar en todo momento el contenido de la BD y sus dependencias fcionales.” En ocasiones la optimización del esquema conceptual p/determinar la forma de almacenamiento de los datos puede dar lugar a una des- normalización. PRIMERA FORMA NORMAL: INF 1 relac.está es INF si no contiene atrib.compuestos, ni multival., ni relac. anidadas. 1relac.está en INF si y solo sí los valores q componen c/u de los atrib. d 1tupla son atómicos. Si 1relac.no cumple estas restricc.se debe normalizar xq: - Falta 1espacio en el campo p/los valores q se desean almacenar (se pierde espacio cuando existen pocos valores). xq p/c/u d los atrib.no atómicos se reserva el espacio necesario p/almacenar el máximo nro.de valores q se estima q puede tomar 1atrib. - Dificultad de tratamiento p/operac.d inserción, actualización y borrado. a) ELIMINACIÓN DE ATRIB.MULTIVAL.: P/eliminar 1atributo multivaluado se puede: El atrib.multival.pasa a ser monovaluado y forma parte d la clave: esta postura no es aceptada ya q aunq se elimine el atrib.multivaluado, sigue existiendo redundancia. Se crea 1relac.auxiliar formada por la clave de la entidad y el atrib. multival.: esta es la postura acertada ya q se consigue eliminar informac.redundante. PRIMERA FORMA NORMAL: INF X ej.en la sig.relac.se encuentra diferentes tipos d material.existentes en 1 ferret, c/material tiene 1cód.q lo identifica, distintas dimens.y1descripc. Esta relac.no se encuentra en INF ya q el atrib.Dimensiones tiene varios valores en 1misma tupla. P/pasar a 1NF se deben realizar: 1º S localizan los atrib.q construyen la Clave primaria d la relac: Cod_Mat. 2º S descompone la relac.realizando1proyección: a) Se crea 1relac.con la clave y los atrib.monovaluados y simples. Dicha relac.permanece con el nombre q identifica a la relac.a normalizar. b) Se crea 1nueva relac.x c/u de los atrib.múltiples, estando formada x la clave d la relac.y dicho atrib. La clave d esta nueva relac.proyectada esta formada x ambos atrib. PRIMERA FORMA NORMAL: INF b) ELIMINACIÓN DE RELACIONES ANIDADAS: se crea 1relac.auxiliar formada x la clave de la entidad dueña y la relación anidada Si s define 1relac.p/la informac.anterior, varios d los dominios son no atómicos. • Autores: 1libro puede tener vs.autores. Si s desea hallar todos los docum.cuyo autor es Santos, hay int.en 1parte del elem.del dominio«conj.de autores» (Elem. indivis) • Palabras clave: si s guarda 1conj.d palabras clave d c/docum.s espera recuperar los docum.cuyas claves incluyan 1ó vs.de las palabras clave especificadas. El dominio d la lista de palabras clave no es atómico.(Elem.Multival., ya q incluye 1dom.tipo “conj”) • Editorial: no tiene 1dominio de tipo conj. Editorial consta de los subcampos nombre y sucursal, x lo q el dominio de editorial no sea atómico (Elem.Multival., incluye 1relac. anidada). Se crea 1relac.con la clave primaria (Cod) y los atrib.q son parte de la relac.anidada (nombre de la editorial y sucursal) X ej. Si p/c/libro de Biblioteca se almacena la siguiente informac: SEGUNDA FORMA NORMAL: IINF La IINF se encuentra basada en el concepto de depend.funcional total. Depend.func.total: 1depend.func. XY es 1depend.fcional total si al eliminar un subconj.de atrib.A de X, deja de cumplirse la depend. fcional: X Y: A X / X - {A} no determina Y Depend.func.parcial: 1depend.func. XY es 1depend.func.parcial si existe 1subconj.de X q determina a Y. X Y : A X / X – {A} Y 1 relac.está en 2NF si y solo sí está en INF y todo atrib.que no pertenece a la clave primaria tiene 1depend.func.total con respecto de la clave. “Esta FN únicamente se considera si la clave primaria está compuesta por 2ó+ atributos, Si la relac.está en INF y la clave primaria está formada por 1único atrib.se puede asegurar q la relac.se encuentra en IINF”. SEGUNDA FORMA NORMAL: IINF Algorit.de transformación de INFIINF P/pasar de 1NF a 2NF se deben eliminar todas las depend.fcionales. parciales con respecto de la clave. P/ello se efectúan las sig.proyecciones: 1º Se crea 1relac.formada x la clave primaria +todos los atrib.q dependen totalmente de ella. 2º Se crea 1nueva relac.auxiliar formada x los atrib.determinantes d la clave primaria + los atrib. q dependen fcionalmente de ellos. La clave d la relac.esta formada x el conj.de atrib.determin. Por ej.dada la relac.EMPL_PROY donde s tiene informac.sobre los empleados de1empr. C/u de las tuplas de la relac.contiene el nombre (Nomb_E) y nro de seguridad social (NSS) de 1empleado, número (Num_P) y nombre (Nomb_P) de 1proyecto en el q trabaja, así como el nro.de horas (Horas) que dicho empleado dedica c/semana al proyecto. SEGUNDA FORMA NORMAL: IINF Transformación de INF a IINF Como se observa, existe 1subconj.de la clave q determina funcionalmente a otros atrib.d la relac.: { NSS, Num_P } Horas Num_P { Nomb_P, Ciudad_P} NSS Nomb_E { Nomb_P,situ_P} y {Nomb_E} son conj.de atrib. q presentan 1depend.fcional parcial con respecto de la clave, p/q la relac.aparezca en 2NF, se deben eliminar estas depend.parciales creando, x c/depend.parcial, 1nueva relac.auxiliar formada x el atrib.determinante y el conj. de atrib.q dependen funcionalmente de él. TERCERA FORMA NORMAL: IIINF La IIINF está basada en el concepto de depend.transitiva. Depend.transitiva: Sea 1depend.fcional X Y en 1relación R= {A1,A2,…,An}, se dice q es 1 depend.transitiva si existe 1conj.de atributos Z de la relación R no pertenecientes a la clave de forma q se verifica : X Z, Z Y y además si Z no determina a X e Y no determina a X. “1 relación está en IIINF si y solo sí está en IINF y no existen atributos no primarios transitivamente dependientes de c/posible clave de la relación.” 1atrib.no primario únicamente debe conocerse a través de la clave primaria o d 1clave candidata de la relac., pero nunca x medio de otro atrib.no primario. Algoritmos de transformación de IINF IIINF 1º Sea una depend.func.X Y, definida en R(A,F), donde X e Y son disjuntos y no son clave ni forma parte de ninguna clave candidata de R. 2º Se obtienen las proyecciones: R1 = Proy ( X,Y ) R2 = Proy ( A – Y ) TERCERA FORMA NORMAL: IIINF Algorit.de transform.de IINF IIINF Siendo A el conj.de atrib.q constituyen la relac.R. P/normalizar 1relac. q está en IINF y en la q existen atrib.transitivamente dependientes de la clave: - Se crea 1nueva relac.R2 con la clave y los atrib.dependientes de la clave pero q no son transitiv.dependientes de ella ni de ninguna clave candidata. - Otra relación R1 con los atrib.transitivos y los atrib.q los determinan. Por ej. en la relac.EMPLEADOS se observa 1depend.transitiva, con respecto de la clave, del conj.de atributos formado por { Nom_D) NSS_Jef }. P/q la relac.pase a IIINF se debe normalizar, descomponiendo en 2relac., 1 formada x el atrib. determinante Num_D y aquello q dependen funcionalmente de él {Nomb_D, NSS_Jef}, y otra formada x la clave y aquellos atrib.q no dependen de forma transitiva de ella. FORMA NORMAL DE BOYCE-CODD: BCNF “1relac.está en BCNF si y sólo si está en IIINF y todo determinante es clave candidata” Es decir, todo conj.de atrib.no contenidos en la clave q determinan a algún atrib., debe determinar a todos los demás. La definición de BCNF engloba la IIINF ya q las dependencias transitivas existen a través de atributos secundarios q no son clave. BCNF se creó p/evitar los casos anómalos q no se resolvían con la IIINF y q aparecen cuando a partir de 1atrib.no primario se conoce parte de la clave primaria o de 1clave candidata. “Si las claves están formadas por un solo atributo y la relación se encuentra en IIINF se puede asegurar que también está en BCNF.” FORMA NORMAL DE BOYCE-CODD: BCNF Algoritmo de paso de IIINF a BCNF Si 1relac.está en IIINF y s detecta algún atrib.determinante (del cual depende fcionalmente otro atrib) q no es clave candidata, s debe normalizar la relac.descomponiendo: 1. 1 relac.formada x el atrib.determinante y los q dependen fcionalmente d él. 2. Otra formada x la clave y el resto de los atrib.incluidos los determinantes. El algorit.de descomposición q se aplica a 1relac.q no está en BCNF es el sig: 1- Sea la depend.func. X Y, definida en R(A,F), donde X e Y son disjuntos, X es 1atrib.no primario e Y forma parte d la clave primaria o de 1clave candidata. 2- Se realizan las siguientes proyecciones: R1= Proy ( X,Y ) R2= Proy ( A – Y ) X ej.se dispone de 1relac.con la informac. referente a un proveedor, del cual se conoce un código que lo identifica (Cod_Pro), tipo del material q suministra (Cod_Mate), nombre del almacén al q provee (Almacen) y Ciudad en la q se encuentra dicho almacén. FORMA NORMAL DE BOYCE-CODD: BCNF Algoritmo de paso de IIINF a BCNF PROVEEDOR Cod_Pro, Cod_Mate, Almacen, Ciudad En esta relac.se encuentra definidas las sig.depend.funcionales: { Ciudad, Cod_Mate } { Cod_Pro, Almacen } { Almacen } { Ciudad } { Cod_Pro } { Cod_Mate, Almacen } Calculando la clausura de c/u de los conj.de atrib.determinantes se observa q {Cod_Pro} y {Ciudad, Cod_Mate} son claves candidatas. Se puede asegurar q la relac.se encuentra en IIINF ya q en la relac. Almacen Ciudad, el atrib. (Almacen) forma parte de 1clave candidata(Cod_Pro). “Sin embargo, como Almacen (atrib.determinante de Ciudad ) no forma parte de ninguna clave la relac.no se encuentra en BCNF y es preciso normalizar.”
Compartir