Monografias | Normalización de base de datos

Índice

1. Descomposición y Normalización

2. Dependencia

3. Normalización

4.Primera Forma Normal

5.Segunda Forma Normal

6.Tercera Forma Normal

7.Cuarta Forma Normal

1. Descomposición y Normalización

Siempre que un analista de sistemas de base de datos arma unabase de datos, queda a su cargo descomponer dicha base en grupos y segmentos deregistros. Este proceso es la descomposición; el mismo es necesarioindependientemente de la arquitectura de la base de datos - relacional, red ojerárquica-. Sin embargo, para la base de datos relacional, la accióncorrespondiente puede dividirse y expresarse en términos formales y se denominanormalización a la misma.

La normalización convierte una relación en variassub-relaciones, cada una de las cuales obedece a reglas. Estas reglas sedescriben en términos de dependencia. Una vez que hayamos examinado lasdistintas formas de dependencia, encontraremos procedimientos a aplicar a lasrelaciones de modo tal que las mismas puedan descomponerse de acuerdo a ladependencia que prevalece. Esto no llevará indefectiblemente a formar variassubrelaciones a partir de la única relación preexistente.

2. Dependencia

Significado :

Antes de entrar en el tópico principal de dependencia, vamosa rever algunos conceptos acerca de los individuos y acerca de las tuplas quelos describen en la base de datos relacional (BDR). Restringiremos la discusióna la BDR, si bien la misma se aplica igualmente a las otras arquitecturas.

Los individuos tienen muchos atributos que pueden ser deinterés a diferentes personas en diferentes momentos. Nuestro problema actuales con una sola aplicación o conjunto de aplicaciones: solemne son de interésalgunos de los atributos.

Los símbolos aplicables a la relación han sido introducidospreviamente.

• R es una tupla general o vector que describe a unindividuo;

• R es una relación, una matriz o un conjunto de vectores que pertenecen la población de interés.

• U es el universo consistente en todas las posibles descripciones individuales, obtenido mediante una combinación exhaustiva de los valores a atributos.

La tupla general toma la siguiente forma

R = (a, b, c, ...., n) La pertenencia con respecto arelaciones, tuplas y universos se indica mediante. Con respecto a los atributos:

• A es el símbolo del nombre de un atributo

• a es el símbolo de un valor del atributo.

Dominio (A) es el dominio para el atributo cuyo nombre es A.

Campo de aplicación

Estamos interesados en relaciones dependientes entreatributos de los individuos en una o varias poblaciones. Consideramos a losatributos D, E, y F. La dependencia es una relación funcional tal que losvalores de una (o más de una) de las variables determina y fija el valor de lasotras variables en la relación dependiente. Consideramos el caso en el que E yF dependen de D. Esto se describe más brevemente en forma simbólica:

e = e (d) f = f(d)

Existen tres tipos distintos de dependencia.

o     Total uno-uno-sinónimo

o     Completa - subtupla

o     Transitiva - múltiple.

La dependencia es una relación funcional que penetra en eluniverso de posibilidades. La dependencia no puede deducirse solamente de losdatos de nuestra, ya que éstos son necesariamente incompletos, sino que debeser inherente al comportamiento del sistema. Por ejemplo, si los datos revelanque cada uno de nuestros proveedores tiene exactamente una planta y que todasestas plantas están en diferentes ciudades, podemos asumir una dependenciatotal entre proveedor, planta y ciudad. Es decir, dada una ciudad, la misma estáasociada con un proveedor; y dado este proveedor estará asociado con unaciudad. En la práctica, solamente cuando un nuevo proveedor se incorpore conuna planta en la misma ciudad que uno de nuestro antiguos proveedores, resultaráclaro que no existe dicha dependencia total, Esto no podría ser deducido apartir de los datos previos.

Dependencia Total

Consideremos los atributos x e y. Cada valor de x tiene uno ysolo un valor de y asociados a el; e inversamente, dado un valor de y existesolamente un valor de x asociado a éste. Se trata de una función unitaria deuna variable tanto en sentido directo como inverso y por o tanto se denominadependencia total. Otra forma de expresar lo mismo es decir que x e y son sinónimos;ambas expresiones son equivalentes.

Ejemplo con clave

Si una de las variables es al mismo tiempo la clave, comoconsecuencia todo valor de ambas variables es único en cualquier tupla de larelación. Por ejemplo, consideremos un archivo de personal donde cada uno delos empleados es identificado de tres maneras.

• Su nombre

• Su número de seguridad social

• Su número de empleado

Los tres pueden representar una dependencia total. Tanto el númerode seguridad social como el número de empleado identifican al individuo enforma única. El número de seguridad social atañe a la población completa detrabajadores de los Estados Unidos. El número de empleado se aplica solamenteal personal de una empresa en particular. El nombre puede no ser totalmente únicoy la dependencia total existe solamente cuando cada empleado tiene un nombre único.

Si el número de empleado es al clave de la relación, el númerode seguridad social es sinónimo de aquel. Podemos en consecuencia decir que elnúmero de seguridad social, el campo no clave, es totalmente dependiente de laclave, y es una clave candidata.

Si los nombres de todos nuestros empleados son únicos, tambiénpueden, ser claves candidatas. Sin embargo puede existir alguna duplicación,dos personas llamadas John Smith, por ejemplo. Dado que esta es una posibilidad,no puede establecerse una dependencia total con respecto total con respecto alnombre. Puede incorporarse a la firma un nuevo empleado y este puede tener elmismo nombre que uno de nuestros empleados actuales.

Ejemplo con estado Consideremos una relación que contieneinformación sobre estado en dos formas :

• Una identificación de estado con dos letras, tal como CA para California.

• Una designación con un número de dos dígitos tal como 12 para

California.

Estas dos formas de información sobre estado ilustran unadependencia total. Debe notarse sin embargo que muchas tuplas pueden contener lamisma identificación de Estado, dado que muchos de nuestros clientes puedenprovenir de California. En consecuencia resulta claro que la dependencia totalno significa unicidad.

Dependencia Completa

El concepto de dependencia completa se aplica solamentecuando:

• Tenemos más de dos variables, y

• Una variable dependiente depende de dos o más variables

independientes.

Consideramos una relación que abarca las variables P, Q y R.Supongamos que P es la variable dependiente. Si el valor de P está determinadopor una función de Q y R combinados, se trata de una dependencia completa. Estoes, el valor de P no depende únicamente ni de Q ni de R.

Vamos a repetir esto simbólicamente. El valor de P escompletamente dependiente de los valores de q y r.

p = p (q,r)

Ejemplo con orden de compra

Como un ejemplo de dependencia completa, consideremos el casode una orden de compra. Supongamos que esta orden de compra describe mediantetres variables que son de interés para nosotros:

• El número de orden de compra (PON) designa la ordencompleta;

• El número de parte de pieza designa una de las partes ordenadas por el pedido;

• La cantidad de piezas es el número de unidades de dicha pieza requerida para satisfacer el pedido.

Los pedidos describen en consecuencia una orden por medio devarias partes diferentes, y para cada una distinta asociada. El sistema contableve varios pedidos diferentes. La misma parte puede aparecer en distintos pedidosy, cuando ello sucede, puede estar asociadas distintas cantidades con la mismaparte.

Un tupla de la base de datos relacional contendrá un PON unnúmero de parte y una cantidad. La cantidad es completamente dependiente delPON y del número de parte. Resulta claro que el número de pedido no essuficiente para determinar la cantidad todas las partes de un determinado pedidono tiene la misma cantidad). Análogamente, un número de parte no es suficientepara determinar la cantidad ordenada, dado que diferentes pedidos puedenrequerir distintas cantidades de dicha parte. Por lo tanto, es nuestro ejemplo,la cantidad no es dependiente solamente del PON o del número de parte; escompletamente dependiente de ambos.

Puede imaginarse, aunque no es muy probable el caso de quecada vez ordenados una parte la ordenamos solamente por una cantidad como unadocena, o tres gruesas o cualquier otro valor fijo. Si esto ocurre para todaslas partes y para todos los pedidos de nuestro sistema, en consecuencia noexistirá dependencia completa. En efecto podemos decir que hay dependenciatotal entre cantidad y número de partes - condición improbable-.

Hemos examinado anteriormente un ejemplo académico y lasvariables profesor, clase y sección. Tenemos en esta caso una dependenciacompleta de profesor respecto de clase y sección. Si en nuestra facultad estáestablecido existirá dependencia completa. Esto existiría que un profesor enseñesiempre a todas las secciones de una clase particular - una condición no muyfactible con un curso de 20 secciones-.

Dependencia transitiva

La dependencia transitiva se aplica o tres o más variables.Consideremos el caso de solo tres variables y llamémoslas S, T y V.

Diremos que S es la variable independiente si los valores deS determinan tanto a T como a V, y se simbolizará así:

S ----> T; S ----> V

Sin embargo, sería deseable encontrar una relación másrestrictiva o definida.

Tenemos dependencia transitiva cuando S determina a T y V,pero los valores de V pueden considerarse siempre como dependiendo de losvalores de T. Esto puede escribirse como

S ----> T; T ---->

o alternativamente como

v = v(t); t = t(s) v = v(t(s))

Reducción

Si podemos manejar las dependencias transitivas, podremosreducir el espacio total requerido para almacenar los datos. Varios valores de Spueden generar un único valor de T. De modo similar, pueden existir variosvalores de T asociados solamente con un valor de V. La separación de estasrelaciones permite conservar espacios. Esto puede observarse mejor con respectoal ejemplo que se describe más abajo.

Ejemplo

Consideramos un ejemplo que asocia cursos con departamento ycon escuela. En consecuencia, canto será dictado por el departamento de músicaen la escuela de Artes y Ciencias; hidráulica será dictada por ingenieríacivil en la Escuela de Ingeniería; impuestos será dictado por el departamentocontable en la Escuela de Administración.

Llamemos

• S al curso

• T al departamento

• V a la escuela

Por lo tanto

S ----> T ----> V

la descomposición consiste en la asociación de un curso conun departamento en una relación. Otras relación identifica a cada departamentocon una escuela. Esta segunda relación es necesariamente menor tanto en gradocomo en cardinalidad y aquí reside el ahorro de espacio.

3. Normalizacion

¿Qué es normalización?

Normalización es un proceso que clasifica relaciones,objetos, formas de relación y demás elementos en grupos, en base a lascaracterísticas que cada uno posee. Si se identifican ciertas reglas, se aplicaun categoría; si se definen otras reglas, se aplicará otra categoría.

Estamos interesados en particular en la clasificación de lasrelaciones BDR. La forma de efectuar esto es a través de los tipos dedependencias que podemos determinar dentro de la relación. Cuando las reglas declasificación sean más y más restrictivas, diremos que la relación está enuna forma normal más elevada. La relación que está en la forma normal máselevada posible es que mejor se adapta a nuestras necesidades debido a queoptimiza las condiciones que son de importancia para nosotros:

• La cantidad de espacio requerido para almacenar los datos es la menor posible;

• La facilidad para actualizar la relación es la mayor posible;

• La explicación de la base de datos es la más sencillaposible.

4. Primera forma normal

Para que una relación esté en primera forma normal (1 FN),debe ser solamente una relación propia, una matríz m por n, donde:

• Ninguna celda de la matriz está vacía;

• El valor n cualquier columna está definido por el dominio para dicho atributo.

• Cada tupla tiene una clave que la identifica en forma unívoca, pero dicha clave no significa orden.

La aplicación determina la relación

Para que una relación sea normalizada en pasos adicionales,debe encontrarse en la primera forma normal. Colocar los datos en la primeraforma normal está a cargo del diseñador de la aplicación. Estos datos seencuentran disponibles de alguna manera inicialmente. Si la aplicación existeen forma manual, o ha sido anteriormente computarizada pero no todavía comorelación, el diseñador reorganiza los datos de modo de conformar una matríz1FN.

La segunda inicial más importante es la dimensión de larelación ¿cuántos componentes existen en la tupla o cuántas columnas en latabla? ¿De qué manera se compara esto con el número de campos en el documentofuente?.

En la figura se puede observar un documento como muestra, unafactura típica. Parte de la información es fija y otra variable. La figura nosmuestra un formulario impreso dentro de l cual se ha agregado información. Laimpresión puede dividirse en dos categorías.

• Información descriptiva para el usuario

• Nombres de atributos.

La información impresa es necesariamente fija. Podemosobservar el nombre de la compañía en la figura, así como otrasparticularidades (tales como el número de teléfono que no figura aquí). Otrosnombres impresos corresponden a los atributos cuyos valores se escriben en elmomento en que el formulario es llenado. Estos nombres de atributos son tambiénlos nombres de campos para almacenar los datos en el sistema. Los que se escribeson los valores de atributos.

La información convertida queda formada en tuplas. La próximapregunta es cuantas tuplas representarán a la formación en esta forma. Debenotarse que el número de partes ordenadas varía de una factura o pedido aotro.

Wetco factura no. 91529

23 river road fecha factura 3/19/77

saltsea texas

orden fecha

de cliente vendedor de la orden via orden wetco

M0007 2-14 3/12/17 ups 1922447

Cliente no. 31-0285-fl

Venta a flores associates expedido a

108 8 avenue el mismo

brooklyn, n.y. 11215

cantidad precio parte descripcion monto

Pen-

Orde-despa-dien-

Nada chada te

2 2 3.50 018719 camisa 7.00

2 2 .35 020428 guia .70

1 1 .70 020808 rodillo motor .70

1 0 .25 020811 rodillo libre 0.00

1 1 6.00 020819 humidrum 8.00

Transporte Y Seguro .96

17.38

Dado que una tupla debe tener un número fijo de componentes,necesitamos una tupla en primera forma normal para cada parte de cada pedido.Sin embargo, la información que se encuentra en la parte superior delformulario, y que se llena a máquina, es la misma para todas las partesordenadas más abajo. Por lo tanto cada tupla consiste en una parte de datos queson variables y datos del pedido que se duplican para cada parte ordenada.

Grafo de Dependencia

Una vez que los datos han sido puestos en primera formanormal, resulta conveniente descomponer la relación en un número de relacionesmás pequeñas, cada una en forma normal superior, de modo de optimizar elalmacenamiento y usar su funciones. Para esto resulta necesario reconocer lasdependencias existentes. Un grafo exhibe los distintos tipos de dependencias queexisten, y enfatizan que hemos investigado completamente cada dependencia.

El grafo simple no está diseñado para mostrar dependencias.Para hacer utilizable a este grafo, se agregan colores pueden expresarse enblanco y negro mediante distintos tipos de líneas. Discutiremos estos tipos delíneas en términos de la dependencia que cada uno representa. En las figurasque siguen las formas gráficas aparecen a la izquierda y se utilizan paraconstituir un grafo completo. A la derecha se puede observar una forma simbólicapara describir dependencias únicas.

Dependencia única

En la figura vemos un arco que conecta dos vértices A y B. Aes la cola y B es la cabeza de la "flecha". Esto significa que Bdepende de A. Es decir dado un valor de A podemos predecir de A. Es decir, dadoun valor de A podemos predecir cuál será el valor de B.

Dependencia total

La dependencia total se define como una dependencia bilateralo simétrica. Es decir, si C depende de D, en consecuencia D será dependienteen forma similar de C. Esto se expresa en la figura mediante una arista (sin unaflecha) que une C y D. Para enfatizar la dependencia total, se usa una líneadoble o una línea más gruesa. Esto representa una medida de seguridad paraverificar que el usuario no dibuje un arco e inadvertidamente omita la flecha.Simbólicamente se utiliza una doble flecha.

Dependencia completa

La variable G depende en forma completa de otras dosvariables E y F, lo cual puede ilustrarse como se ve a la izquierda de lafigura. Pero así no es representada adecuadamente la dependencia completa, yaque el valor de G no depende de E o F, independiente, sino que depende de ambosvalores. Por lo tanto en el centro de la figura A, vemos una forma mejor; laarista que une E y F no intenta demostrar una dependencia entre E y F, por lotanto se dibuja en líneas de trazos; a partir del centro de esta línea detrazos, se dibuja un arco dirigido hacia G para indica que G depende de ambasvariables E y F.

Dependencia transitiva

Supongamos que dos variables, K y L, dependen de J. Si puedeverificarse que L depende en forma primaria de K, existiría una dependenciatransitiva. Mostramos a la izquierda de la figura B que L. depende de J o de K.Más apropiado s el grafo del centro de la figura B, donde podemos ver que L estádefinida por K la cual, a su vez, está determinada por los valores de J.

Simbólicamente indicamos una dependencia transitiva de Lrespecto de J mediante una flecha de trazos desde J a L, como puede verse a laderecha de la figura B.

Ejemplo

En la figura B se presenta un grafo de dependencia hipotético.En el mismo se dibujan las relaciones de dependencia entre atributos para unaaplicación de remuneración. EMPNO y DEPTNO están subrayadas en la figura paraexpresar que ambas son partes de una clave compuesta para la relación. Una líneagruesa conecta EMPNO a EMPNOM para indicar que si nombre de empleado y existeuna dependencia total.

Varios atributos dependen directamente del número deempleados:

• TITL es el título de la tarea del empleado

• PAYLVL es un carácter que indica el nivel de sueldo del empleado.

• HORAS representa el número de horas que el empleado ha trabajado la presente semana.

• PAYRT está apuntado a PAYLVL indicando que el régimen de pago es transitivamente dependiente del nivel de pago.

La línea de trazos que une PAYRT y HORAS indica que ambasparticipan en una dependencia completa por la cual el receptor es PAYAMT, elvalor pagado para esta semana.

A la derecha de la figura, encontramos los atributos quedependen del número de departamento. Obsérvense la dependencia total entre númeroy nombre del jefe del mismo (MGRO y MGRNM).

Hay solamente un atributo que es completamente dependiente deambas partes de la clave compuesta, es decir, el número deproyecto, PROJNO.

5. Segunda Forma Normal

Una relación está en segunda forma normal (2FN)solamente si todos los atributos son dependientes en forma completa de la clave.

Descripcion De La Segunda Forma Normal (2 Fn)

Su nombre ya nos indica el hecho de que la segunda formanormal es por lo general el próximo paso de normalización y descomposición.Para ser accesible a la normalización, y poder ser puesta en segunda formanormal, la relación debe poseer las siguientes propiedades:

• Debe estar en primera forma normal

• Debe tener una clave compuesta.

La consecuencia inmediata de los requerimientos expresados másarriba es que cualquier relación en primera forma normal que tiene una clavesimple, está automáticamente en segunda forma normal. Comencemos con unejemplo en forma de tabla de una relación consistente en 17 atributos, que sepresenta en la figura. La misma se encuentra en primera forma normal y tiene unaclave compuesta que consiste en dos atributos P y Q. Estos están subrayados enla figura para mostrar que sirven como clave. La tupla de relación puede tambiénescribirse linealmente en forma simbólicamente:

R = (A,B,C,D,E,F,G,H,I,L,M,N,O,P,Q)

El próximo paso es crear un grafo de dependencia,presentando aquí como figura. Debe notarse que este grafo se crea examinado conconocimientos y atributos para determinar como participan y relacionan entreellos.

No resulta suficiente analizar la matríz de relación, lacual puede hacernos creer que existe una dependencia debido a que la muestra dela cual se ha extraído dicha relación es pequeña. Si somos inducidos a errorpor los datos existentes y construimos una dependencia donde esta no existe, seplanteará un problema. Cuando lleguen nuevos datos que contradigan ladependencia, deberá dejarse de lado el esquema completo.

Supongamos en consecuencia que el grafo que se puede observaren la figura ha sido derivado en forma funcional y que expresa correctamente lasdependencias. Resulta claro a partir de este grafo que los atributos que partende P son dependientes solamente de este. De un modo similar los que parten de Qdependen solamente de este último. Solamente aquellos que parten de la líneade trazos que conecta a P y Q tienen dependencia completa de ambos. Esta es laguía para la descomposición.

Descomposición

La figura contiene 3 sub-árboles, la base de nuestradescomposición. Definimos una subtupla general en base a cada sub-árbol y enconsecuencia:

P' = (P,A,B,C,E,H,K)

Q' = (Q,F,G,J,N)

PQ = (P,Q,D,I,L,M,O)

Aquí la raíz de los sub-árboles de la izquierda y laderecha. P y Q, se convierte en la clave de sus respectivas subtuplas; ambos. Py Q forman la clave compuesta para la subtupla PQ.

Proyección

El próximo paso es proyectar la relación R sobre cada unade estas subtuplas para formar tres nuevas relaciones, y en consecuencia.

P' = proyectar R(P')

Q' = proyectar R(Q')

PQ = proyectar R(PQ)

Las relaciones así formadas nos dan tres nuevassub-relaciones. Una subrelación es la relación que deriva de una relaciónmayor. Las subrelaciones ilustradas en la figura están correlacionadas pormedio de los componentes de sus claves. La clave compuesta P y Q de la relaciónoriginal R. es también la clave de la sub-relación PQ. P y Q tienen a P y Qrespectivamente como claves. La línea de trazos en la figura indica que Q estácorrelacionada con PQ por medio de la componente Q y P está correlacionada conPQ por medio de P.

Para restablecer la relación original R debemos juntar estastres subrelaciones en algún orden, indicado simbólicamente como:

R = juntar P [juntar PQ, (Q)] (P) = juntar Q[juntar PQ P(P)](Q).

Grafos

La nueva sub-relación que se ve en la figura se presenta enforma de grafo en la figura siguiente. Existe una considerable analogía entresestas figuras y la figura anterior. Lo importante es la diferencia. En PQ existeuna línea de trazos que conecta los componentes de la clave compuesta P y Q enel centro de la figura. Los arcos parten del centro de esta línea de trazoshacia todos los componentes de P y Q, los cuales son dependientes en formacompleta de ambos, es decir de P y Q. Una línea de puntos conecta P en larelación PQ a P de la relación P. Esto representa la correspondencia entreambas veces P. Una línea de puntos conecta de un modo similar Q en PQ a Q en Qpara indicar una correspondencia similar.

Efectos

El efecto de esta descomposición puede no resultarinmediatamente claro. Debemos insistir en que ninguna relación correcta debecontener tuplas duplicadas. La relación original R contiene muchas subtuplasduplicadas P' y Q'. Las mismas han sido eliminadas durante la descomposición.Esto facilita en forma extraordinaria la actualización y otras importantesoperaciones que afectan a estas relaciones, las cuales serán aclaradas en losejemplos que siguen.

Ejemplo de inventario

Vamos a utilizar ahora un ejemplo práctico para demostrar lanormalización. En la figura se observa una parte de la matríz de relación PW.

Pueden verse los nombres de los atributos simbólicos y sussignificados, pero no sus valores. Las columnas no aparecen en ningún orden enparticular. Debe observarse la clave compuesta que distingue cada tupla, queabarca el número de pieza y el número de depósito PNO y WNO.

Arbol de Dependencia

El medio para descomponer la relación es el árbol dedependencia que se ve en la figura. Este árbol ha sido construido solamenteteniendo en cuenta la dependencia completa, y no muestra las dependencias totalo transitiva, que se describe más adelante, si es que las mismas existen.

Como podíamos esperar, aparecen tres sub-árboles. El sub-árbolde la izquierda, con raíz PNO, contiene los atributos que se aplican solamentea la pieza o parte. El sub-árbol de la derecha con raíz WNO describe cada depósito.EDl sub-árbol del centro corresponde a las partes y al depósito, y describe lacantidad de partes disponibles en el depósito, QOH, y el número de cajón oestante, BIN (o algún otro parámetro de ubicación), donde dichas partespueden ser halladas.

El próximo paso es definir tres tuplas generales para cadasub-árbol,

P = (PNO, DESC, PR, UNIT)

W = (WNO, WAD, FUE)

P/W = (PNO, WNO, BIN, QOH)

La descomposición consiste en proyectar la relación PWsobre cada una de estas tuplas para obtener tres nuevas sub-relaciones:

P = proyectar PW(P)

W = proyectar PW(W)

P/W = proyectar PW(P/W)

La descomposición en la figura muestra las tres relacionescomo matrices; la línea de trazos indica como se vinculan las relaciones.

Efecto

Discutiremos ahora algunas de las ventajas obtenidas mediantela descomposición. Si estas relaciones se utilizan para el control deinventario. nuestra preocupación será cuantas piezas de cada tipo estándisponibles en un depósito en particular. Cuando se retiran piezas o se recibennuevos envíos la cantidad disponible, QOH será la variable de cambio. Laactualización consiste en poner al día sub-relación P/W la cual ahoracontiene solamente malos componentes en lugar de los nuevos P/W.

Existe una tupla P en la sub-relación de pieza o parte, P,para cada parte y una tupla. W, en la sub relación W, para cada depósito yestos últimos probablemente no serán muchos. Consideremos la facilidad deefectuar cambios en un depósito en particular. Si un atributo de uno de los depósitosvaría entraremos en W para efectuar el cambio solamente en una tupla. En laprimera forma normal para PW teníamos que encontrar todas las tuplas en lascuales el valor de WNO esta el particularmente deseado, y efectuar el mismocambio en cada una de ellas. Si dicho depósito almacenaba 100 partes, comoconsecuencia debía variar 100 tuplas de PW. El procedimiento de actualizaciónse aplica también a las descripciones de partes. Si el precio de alguna parte opieza cambia, este cambio es independiente del depósito en el cual se almacenadicha parte. Solamente se efectúa un cambio en P a diferencia de los muchos quehubieran sido requeridos para PW.

6. Tercera forma normal

Una relación se encuentra en tercera forma normal (EFN)si no existen transitividades entre sus atributos y si ya se encuentra en 2 FN.

Descripción

Una relación R a poner en tercera forma normal debe estar enla segunda forma normal. Es muy común que R sea una sub-relación; la relaciónoriginal estaba en primera forma normal (para ponerla en segunda forma normalfue descompuesta en varias sub-relaciones). Estas son ahora candidatas a unadescomposición adicional.

Recordamos que las propiedades de la segunda forma normal(2Fn) son:

• Tenemos una matríz m x n con un valor determinado para cada componente de cada tupla.

• Cada valor es obtenido a partir de un dominio propiamente definimos

• Cada valor contiene una clave, ya sea simple o compuesta

• Cada componente no clave es dependiente en forma completa de su clave.

En consecuencia es evidente que tenemos, o bien una clavesimple, o una clave compuesta de la cual todos los componentes no clave sondependientes en forma completa.

El objeto de esta fase es determinar todas las dependenciastransitivas; la descomposición producirá a continuación sub-relaciones paralas cuales no existirán dependencias transitivas -la definición de la terceraforma normal (EFN)-.

Una dependencia transitiva abarca como mínimo trescomponentes. Si los componentes fueran más, la dependencia múltiple puedederivarse en varias dependencias atransitivas de tres componentes solamente dadauna. Por lo tanto dirigiremos nuestra atención a una dependencia transitivasimple de tres componentes. Tal dependencia puede expresarse como:

Q ---> A ----> B

En la cual se dice que B depende de A y que A depende de Q.La transitividad existe debido a que el valor de B depende en la últimainstancia del valor de Q.

La dependencia transitiva es degenerada si cualquiera de lasdependencias anteriores es total. Esto es, podemos prever que la relación de Qa A es muchos-unos, donde varios valor único de A. Dado un valor tal Q el valorde A queda determinado. La inversa no se aplica y en consecuencia no existe unadependencia total: dado un valor de A el valor correspondiente de Q no quedadeterminado a menos de que se trate de una dependencia total.

El ahorro que surge de colocar la relación en tercera formanormal aparece a raíz de la granularidad del dominio involucrado. Se puedeprever que:

num dominio (Q)> num dominio (A) > num dominio (B)

Determinación de al dependencia transitiva

Si el grafo utilizado para llevar la relación a la segundaforma normal es completo en termino de las transitividades existentes, noresulta necesario un grafo adicional. El grafo para convertir a la segunda formanormal requiere solamente que todas las dependencias completas y parciales seanconocidas. Supongamos que no hemos establecido todas las dependenciastransitivas. Se presenta una situación simple en la figura anterior donde A, By C son dependientes de Q. SI suponemos que existe una dependencia entre A, B yC son dependientes de Q. Si suponemos que existe una dependencia entre a y Bdebemos confirmarlo en forma funcional.

Una dependencia total entre A y B en el grafo de la figurapuede representarse como se ve en la figura el arco desde A a B no muestra unadependencia de B respecto de A inversamente el arco a partir de B hacia Amuestra una dependencia de A respecto de B; los arcos a partir de Q a A y a Bnos muestra la dependencia de cada una de éstas respecto de Q. Esto puedeobservarse nuevamente en la figura, donde una doble arista entre A y B indica labi-direccionalidad de esta dependencia. El hecho de que Q apunte a esta aristanos muestra que cada una de las variables A y B es claramente dependiente deaquella.

Como ejemplo sea Q el número PO, A el número de parte opieza y B el nombre de parte, A y B son totalmente dependientes y cada unodependen de Q.

Transitividad simple

Para la dependencia transitiva unilateral, la variableindependiente apunta a la variable dependiente, tal cual se presenta en elfigura donde B depende de A. El arco entre B y Q ha sido eliminando; ladependencia implícita de B respecto de Q resulta obvia.

Si se presenta la dependencia inversa, debe gratificarse comose ve en la figura.

Descomposición

Dada una sub-relación con una o más dependenciastransitivas, la descomposición consiste en partir la relación en una o más deuna sub-relación, donde la variable intermedia aparezca como variabledependiente en una y como variable independiente en la otra.

Caso simple Tenemos:

Q ---> A ----> B

Q ---> C

Dado que ambas, A y C dependen directamente de Q debenconservarse en una sub-relación Q, con clave Q.:

Q ---> A; Q ---> C

Debe separarse la relación directa remanente, y colocarla ensu propia sub-relación A' con la A:

A ---> B

Los grados de Q' y A'. Aquí la componente A relaciona Q' conA, a es la clave simple de A'. Si bien A no es la clave de Q' es le medio derelacionar un valor de Q en Q' con un valor de B en A' y se llama por lo tantola clave externa de Q' . Para crear Q' y A' debemos utilizar las subtuplasgenerales Q' y A' denifidas en consecuencia:

Q' = (Q,A,C)

A' = (A,B) donde el subrayado indica una clave.

Este deben proyectarse sobre Q para obtener lassub-relaciones:

Q'= proyectar Q(Q')

A'= proyectar Q(A')

Caso Compuesto

Las dependientes transitivas múltiples han sido investigadasy exhibidas. Tenemos en consecuencia.

Q --> C

Q --> A --> B1

Q --> A --> B2

Q --> A --> B3

La descomposición separa nuevamente todas estas variablesdirectamente dependiente de la clase original en una subtupla. Q'' = (Q, A, C)

Las variables restantes son todas dependientes directa ototalmente de A o C y se reorganizan de un modo similar. A'' = (A, B1, B2, B3);C'' = (C, D)

Deben construirse tres sub-relaciones por proyección:

Q'' = proyectar Q(Q'')

A'' = proyectar Q(A'')

C'' = proyectar Q(C'')

Aquí Q'', A'' y C'' aparecen como sub-árboles. Las mismasse relacionan por medio de la clave externa de Q'' es decir A y C; esto semuestra mediante la línea de puntos entre A y A y entre C y C. Nos podemosmover directamente entre las dos figuras sin la intervención de pasos simbólicos,utilizando solamente manipulaciones gráficas.

Descomposición Gráfica

Hemos discutido el enfoque simbólico. Dado un grafo 2FN.Debemos seleccionar en primer término los nodos apuntados por la raíz que nosean hojas. Los mismos se convierten en raíces de sus propios sub-árboles, A''y C''. Estos sub-árboles son eliminados de Q dejando en Q'' solamente los nodosA y C, que son las raíces de A;; y C''.

Ejemplo de orden de compra

Examinaremos solamente una pequeña porción de la relaciónorden de compra que ha sido convertida en un grafo de dependencia. Para estaporción de la relación compra PP, tenemos:

• Las partes se compran utilizando el número de parte,PNO;

• Un vendedor, VNDR está asociado a cada parte;

• Cada vendedor tiene una clasificación de forma de pago,PAYCLS.

Por lo tanto PAYCLS representa si el vendedor debe cobrardentro de los 10 días, 30 días, 60 días, etc. La acción para convertir larelación.

Tenemos aquí una relación transitiva que puede serrepresentada en consecuencia:

PNO ---> PAYCLS

Sabemos que la variable intermedia, el vendedor VNDR, es elque determina el tipo de pago de modo tal que

PNO ---> VNDR --> PAYCLS

para poner esta relación en la tercera forma normal, lamisma se descompone en dos sub-relaciones. Las dos sub-relaciones PV y VP, seforman por proyección a partir de la relación original PP de modo tal que:

PV = proyectar PP (PNO, VNDR); PV = proyectar PP (VNDR,PAYCLS).

La relación PV relaciona partes con vendedores.

La identificación del vendedor, VNDR es la clave externa parPV. La misma se utiliza para entrar en la relación VP, en la cual es la claveprimaria.

Debe notarse que, para el mantenimiento, si cambia la clasede pago solamente cambiara una entrada o tupla en VP y ninguna en PV. Para elcaso de PP hubiera cambiado muchas tuplas.

Ejemplo de inventario

Presentamos ahora una porción de un ejemplo de inventario,al cual corresponde el grafo parcial. Tenemos en este caso:

• PNO es un número de parte

• PNM es el nombre de parte y tiene dependencia total con el número de parte

• PREC es el costo de UNITS multiplicado por el número departes

• PCL es la clase de parte, la cual da el tipo de parte en términos de su peso y de su forma.

• WHN es el número de depósito donde está almacenada laparte.

• WHLOC Es la ubicación del deposito

• FUE es la categoría de seguro de incendio del depósivto.

Resulta claro a partir del grafo que el número de partedetermina la clasificación de la parte, la cual a su vez determina parcialmenteel deposito donde está almacenada dicha parte. Usaremos esta dependenciatransitiva, que está circundada con línea de trazos gruesos, para descomponerla relación en su tercera forma normal: PNO ---> WHN; PNO ---> PCL---> WHN

La variable intermedia, clase de parte, PCL, es el medio deque disponemos para descomponer el grafo. Se deja como ejercicio hallar lasproyecciones y la relaciones resultantes.

Ejemplo bancario

Consideremos parte de un ejemplo de banco donde cadadepositante tiene un número de cuenta que lo identifica. El depositante recibeuna línea de crédito. Puede extraer dinero hasta dicho valor. La parte noutilizada de crédito puede ser retirada cuando lo desee. Vemos que la línea decrédito LNCR es funcionalmente dependiente del número de cuenta CUET; el valorya extraído DEBIT es también dependiente del número de cuenta. El valor de créditodisponible en este momento, DISP, es dependiente en forma completa de ambos,LNCR y DEBIT.

Parecería que lo lógico es descomponer el grafo y volver apresentarlo. En base a esto, P tiene como clave el número de cuenta CUENT.Debemos entrar en P para obtener LNCR y DEBIT. Estas son claves externas para P;las mismas forman la clave compuesta para entrar en Q y hallar el valor de lavariable completamente dependiente DISP.

Esto funcionaría, pero hay una forma más simple de resolverel problema. El valor de crédito disponible en la actualidad es simplemente ladiferencia entre la línea de crédito y el debido corriente. Todo lo quetenemos que hacer es ejecutar una sustracción. La relación original nonecesita contener DISP. dado que éste se calcula simplemente durante elprocesamiento. Por lo tanto podemos sencillamente omitir Q.

Transitivas múltiples.

Establecemos de entrada la condición simple de que Z seadependiente en forma transitiva de Q. Si existe más de una variable intermediade dependencia, la transitiva no será completa hasta que se especifiquen todasdichas variables. Es decir, si bien empezamos con la condición detransitividad, Q ---> Z,

la condición completa podría ser, Q ---> X ---> Y---> Z

Ninguna condición intermedia Q ---> X ---> Z --->;Q ---> Y ----> Z

sería suficiente para descomponer la original de la figura.

7. Cuarta forma normal

Dependencias multivaluadas

La tercera forma normal toma en cuenta la dependenciatransitiva y provee una reducción óptima universal, excepto para los casosinfrecuentes de dependencia multivaluadas. Ha quedado claro en épocas recientesque es posible una reducción adicional en este caso, y esto es lo que se llevaa cabo mediante la cuarta forma normal.

Existe una dependencia multivaluada cuando un valor de unavariable está siempre asociado con varios valores de otra u otras variablesdependientes que son siempre las mismas y están siempre presentes. Esto seilustra mejor con el ejemplo presentado en la figura. La relación FAB describetejidos. La variable independiente (con respecto a las dependencias(multivaluadas) es el número de tejido FABNO. Con el se encuentra asociados unmodelo (o patrón) y un color. En la figura, el tejido 345 vienen en dos modelosy entres combinaciones de modelo y color. En este caso se aplica el grafo dedependencia. Para hacer mas clara que esta es una dependencia multivariable, unacabeza doble de flecha apunta desde FABNO o PATRN y también desde FABNO aCOLOR.

La ineficiencia en el registro de información y se resultaclara al examinar las dos nuevas relaciones. La primera de éstas, FABPAT listael número de tejido contra el modelo; en el segundo caso, FABCOL, lista el númerode tejido contra las combinaciones de color. Dado que la regla es que todas lascombinaciones de las variables dependientes multivaluadas deben prevalecer,resulta simple reconstruir la relación FAB a partir de las dos sub-relacionesque resultaron.

Descomposición Para poner una relación o sub-relación enla cuarta forma normal debe poder aplicarse lo siguiente:

• Debe estar en la tercera forma normal.

• Deben existir una o mas multidependencias.

Después de construir el grafo de dependencia, el próximopaso es ejecutar proyecciones utilizando la variable independiente y una de lasvariables multidependientes.

FABPAT = proyectar FAB (FABNO, PATRN)

FABCOL = proyectar FAB (FABNO, COLOR)

El resultado son nuevas sub-relaciones que han sidoutilizadas para ahorra espacio y permitir una más fácil actualización.

Ejemplo de profesor y texto

Consideremos otro ejemplo. Los cursos dictados en una escuelacorresponden a un número de curso. Asociada a cada número de curso seencuentra la descripción del mismo. Para cada curso existe una selección detextos y una selección de profesores. Puede darse cualquier combinación detexto y profesor.

El grafo de dependencia. El mismo nos muestra una dependenciatotal entre el número de curso y la descripción del curso. Existe unamultidependencia entre texto y número de curso, y también entre profesor y númerode curso.

Para descomponer la sub-relación en sus relaciones máspequeñas, se efectúan tres proyecciones. Las sub-relaciones resultantes.

Trabajo enviado por:
Prof. Manuel Torres Remon
mtr-unlimited@correoweb.com
manuelt23@mixmail.com
Docente de la Carrera Profesional de Computación e Informática
Instituto Superior Tecnológico Publico Manuel Arevalo Caceres
Av. Alisos Cdra. 9 Los Olivos -
Telf. 5214525

Compartir