SEMANA 12 - TEORÍA DE NORMALIZACIÓN

TEORÍA DE NORMALIZACIÓN

Terminología relacional equivalente

Trabajo (Código, Nombre, Posición, Salario), donde Código es la Clave Primaria.

• Relación = tabla o archivo
• Registro = registro, fila , renglón o tupla
• Atributo = columna o campo
• Clave = llave o código de identificación
• Clave Candidata = superclave mínima
• Clave Primaria = clave candidata elegida
• Clave Ajena (o foránea) = clave externa o clave foránea
• Clave Alternativa = clave secundaria
• Dependencia Multivaluada = dependencia multivalor
• RDBMS = Del inglés Relational Data Base Manager System que significa, Sistema Gestor de Bases de Datos Relacionales.
• 1FN = Significa, Primera Forma Normal o 1NF del inglés First Normal Form.

Los términos Relación, Tupla y Atributo derivan del álgebra y cálculo relacional, que constituyen la fuente teórica del modelo de base de datos relacional.
Todo atributo en una tabla tiene un dominio, el cual representa el conjunto de valores que el mismo puede tomar. Una instancia de una tabla puede verse entonces como un subconjunto del producto cartesiano entre los dominios de los atributos. Sin embargo, suele haber algunas diferencias con la analogía matemática, ya que algunos RDBMS permiten filas duplicadas, entre otras cosas. Finalmente, una tupla puede razonarse matemáticamente como un elemento del producto cartesiano entre los dominio.

Dependencia

Una dependencia funcional es una conexión entre uno o más atributos. Por ejemplo si se conoce el valor de FechaDeNacimiento podemos conocer el valor de Edad.
Las dependencias funcionales del sistema se escriben utilizando una flecha, de la siguiente manera:
FechaDeNacimiento Edad
Aquí a FechaDeNacimiento se le conoce como un determinante. Se puede leer de dos formas FechaDeNacimiento determina a Edad o Edad es funcionalmente dependiente de FechaDeNacimiento. De la normalización (lógica) a la implementación (física o real) puede ser sugerible tener éstas dependencias funcionales para lograr la eficiencia en las tablas.

Propiedades de la Dependencia funcional

Existen 3 axiomas de Armstrong:

Dependencia funcional Reflexiva

Si "x" está incluido en "x" entonces x x A partir de cualquier atributo o conjunto de atributos siempre puede deducirse él mismo. Si la dirección o el nombre de una persona están incluidos en el DNI, entonces con el DNI podemos determinar la dirección o su nombre.

Dependencia funcional Aumentativa

entonces
DNI nombre
DNI,dirección nombre,dirección
Si con el DNI se determina el nombre de una persona, entonces con el DNI más la dirección también se determina el nombre y su dirección.

Dependencia funcional transitiva.

Sean X, Y, Z tres atributos (o grupos de atributos) de la misma entidad. Si Y depende funcionalmente de X y Z de Y, pero X no depende funcionalmente de Y, se dice entonces que Z depende transitivamente de X. Simbólicamente sería:
X Y Z entonces X Z
FechaDeNacimiento Edad
Edad Conducir
FechaDeNacimiento Edad Conducir
Entonces tenemos que FechaDeNacimiento determina a Edad y la Edad determina a Conducir, indirectamente podemos saber a través de FechaDeNacimiento a Conducir (En muchos países, una persona necesita ser mayor de cierta edad para poder conducir un automóvil, por eso se utiliza este ejemplo).

Propiedades deducidas

Unión

y entonces

Pseudo-transitiva

y entonces

Descomposición

y z está incluido en y entonces

Claves

Una clave primaria es aquella columna (o conjunto de columnas) que identifica únicamente a una fila. La clave primaria es un identificador que va a ser siempre único para cada fila. Se acostumbra a poner la clave primaria como la primera columna de la tabla pero es más una conveniencia que una obligación. Muchas veces la clave primaria es numérica auto-incrementada, es decir, generada mediante una secuencia numérica incrementada automáticamente cada vez que se inserta una fila.
En una tabla puede que tengamos más de una columna que puede ser clave primaria por sí misma. En ese caso se puede escoger una para ser la clave primaria y las demás claves serán claves candidatas.
Una clave ajena (foreign key o clave foránea) es aquella columna que existiendo como dependiente en una tabla, es a su vez clave primaria en otra tabla.
Una clave alternativa es aquella clave candidata que no ha sido seleccionada como clave primaria, pero que también puede identificar de forma única a una fila dentro de una tabla. Ejemplo: Si en una tabla clientes definimos el número de documento (id_cliente) como clave primaria, el número de seguro social de ese cliente podría ser una clave alternativa. En este caso no se usó como clave primaria porque es posible que no se conozca ese dato en todos los clientes.
Una clave compuesta es una clave que está compuesta por más de una columna.
La visualización de todas las posibles claves candidatas en una tabla ayudan a su optimización. Por ejemplo, en una tabla PERSONA podemos identificar como claves su DNI, o el conjunto de su nombre, apellidos, fecha de nacimiento y dirección. Podemos usar cualquiera de las dos opciones o incluso todas a la vez como clave primaria, pero es mejor en la mayoría de sistemas la elección del menor número de columnas como clave primaria.

·         Diccionario de Datos

. 1FN, 2FN,3FN

La Primera Forma Normal Esta primera Forma Normal, nos lleva a no repetir datos en nuestras tablas. Los famosos maestro – detalle, deben aplicarse a la estructura de la tabla.Si nuestra tabla de ventas repite una y otra vez (por cada venta) , el nombre, el domicilio y otros datos del Cliente, es que no hemos aplicado esta Normalizaciòn.Si tenemos una tabla clientes, en la tabla ventas, solo deberia figurar el codigo del cliente, para que el resto de los datos se puedan referenciar automaticamente sin problemas y sin duplicar información.Lo mismo ocurriria en una tabla de detalle de ventas, si por cada item vendido colocamos el detalle del producto, con su descripción , medidas, etc…Tendriamos un desaprovechamiento de espacio y recursos muy grande. Para ello, tendremos nuestra tabla maestra de Productos y con solo grabar el código de dicho producto en nuestra tabla de ventas, será suficiente.

La Segunda Forma Normal (Si o si debe estar previamente aplicada la Primera Forma Normal) La Segunda Forma Normal nos habla de que cada columna de la tabla debe depender de la clave.Esto significa que todo un registro debe depender únicamente de la clave principal, si tuvieramos alguna columna que se repite a lo largo de todos los registros, dichos datos deberian atomizarse en una nueva tabla.Veamos un ejemplo

La Tercera Forma Normal En realidad si nos guiamos en el ejemplo de esta nota, ya no quedaria normalización por aplicar y podriamos decir que nuestro ejemplo cumple con las 3 formas normales, ya que la 3ra Forma Normal nos habla de que :

1. Ninguna Columna puede depender de una columna que no tenga una clave
2. No puede haber datos derivados

En el 2do ejemplo hemos descubierto campos que dependian de la clave principal (VentaID) y que podrian incluirse en una tabla maestra.Pero supongamos un ejemplo donde ciertas columnas no dependen de la clave principal y si dependen de una columna de nuestra tabla.

ConclusiónFinalmente si tomamos en cuenta que una tabla de detalle de venta (item x item) puede contener un volumen de millones de registros, al haberle aplicado las 3 formas normales nos estaremos ahorrando varios Gigabytes de tamaño en dicha tabla y por supuesto mejorado notablemente la performance.

Formas Normales

Las formas normales son aplicadas a las tablas de una base de datos. Decir que una base de datos está en la forma normal N es decir que todas sus tablas están en la forma normal N.

Diagrama de inclusión de todas las formas normales.

En general, las primeras tres formas normales son suficientes para cubrir las necesidades de la mayoría de las bases de datos. El creador de estas 3 primeras formas normales (o reglas) fue Edgar F. Codd.^[1]

 Primera Forma Normal (1FN)

Artículo principal: Primera forma normal

Una tabla está en Primera Forma Normal si:

• Todos los atributos son atómicos. Un atributo es atómico si los elementos del dominio son indivisibles, mínimos.
• La tabla contiene una llave primaria única.
• La llave primaria no contiene atributos nulos.
• No debe existir variación en el número de columnas.
• Los Campos no llave deben identificarse por la llave (Dependencia Funcional)
• Debe Existir una independencia del orden tanto de las filas como de las columnas, es decir, si los datos cambian de orden no deben cambiar sus significados

Una tabla no puede tener múltiples valores en cada columna. Los datos son atómicos. (Si a cada valor de X le pertenece un valor de Y y viceversa)
Esta forma normal elimina los valores repetidos dentro de una BD

 Segunda Forma Normal (2FN)

Artículo principal: Segunda forma normal

Dependencia Funcional. Una relación está en 2FN si está en 1FN y si los atributos que no forman parte de ninguna clave dependen de forma completa de la clave principal. Es decir que no existen dependencias parciales. (Todos los atributos que no son clave principal deben depender únicamente de la clave principal).
En otras palabras podríamos decir que la segunda forma normal está basada en el concepto de dependencia completamente funcional. Una dependencia funcional es completamente funcional si al eliminar los atributos A de X significa que la dependencia no es mantenida, esto es que . Una dependencia funcional es una dependencia parcial si hay algunos atributos que pueden ser eliminados de X y la dependencia todavía se mantiene, esto es .
Por ejemplo {DNI, ID_PROYECTO} HORAS_TRABAJO (con el DNI de un empleado y el ID de un proyecto sabemos cuántas horas de trabajo por semana trabaja un empleado en dicho proyecto) es completamente dependiente dado que ni DNI HORAS_TRABAJO ni ID_PROYECTO HORAS_TRABAJO mantienen la dependencia. Sin embargo {DNI, ID_PROYECTO} NOMBRE_EMPLEADO es parcialmente dependiente dado que DNI NOMBRE_EMPLEADO mantiene la dependencia.

 Tercera Forma Normal (3FN)

Artículo principal: Tercera forma normal

La tabla se encuentra en 3FN si es 2FN y si no existe ninguna dependencia funcional transitiva entre los atributos que no son clave.
Un ejemplo de este concepto sería que, una dependencia funcional X->Y en un esquema de relación R es una dependencia transitiva si hay un conjunto de atributos Z que no es un subconjunto de alguna clave de R, donde se mantiene X->Z y Z->Y.
Por ejemplo, la dependencia SSN->DMGRSSN es una dependencia transitiva en EMP_DEPT de la siguiente figura. Decimos que la dependencia de DMGRSSN el atributo clave SSN es transitiva vía DNUMBER porque las dependencias SSN→DNUMBER y DNUMBER→DMGRSSN son mantenidas, y DNUMBER no es un subconjunto de la clave de EMP_DEPT. Intuitivamente, podemos ver que la dependencia de DMGRSSN sobre DNUMBER es indeseable en EMP_DEPT dado que DNUMBER no es una clave de EMP_DEPT.
Formalmente, un esquema de relacion R está en 3 Forma Normal Elmasri-Navathe,^[2] si para toda dependencia funcional , se cumple al menos una de las siguientes condiciones:

1. X es superllave o clave.
2. A es atributo primo de R; esto es, si es miembro de alguna clave en R.

Además el esquema debe cumplir necesariamente, con las condiciones de segunda forma normal.



SEMANA 11- MODELO DE DATOS

MODELO DE DATOS

Un diagrama o modelo entidad-relación (a veces denominado por sus siglas, E-R "Entity relationship", o, "DER" Diagrama de Entidad Relación) es una herramienta para el modelado de datos de un sistema de información. Estos modelos expresan entidades relevantes para un sistema de información así como sus interrelaciones y propiedades.

Modelado Entidad-Relación

El Modelo Entidad-Relación.

1. Se elabora el diagrama (o diagramas) entidad-relación.
2. Se completa el modelo con listas de atributos y una descripción de otras restricciones que no se pueden reflejar en el diagrama.

Dado lo rudimentario de esta técnica se necesita cierto entrenamiento y experiencia para lograr buenos modelos de datos.

El modelado de datos no acaba con el uso de esta técnica. Son necesarias otras técnicas para lograr un modelo directamente implementable en una base de datos. Brevemente:

• Transformación de relaciones múltiples en binarias.
• Normalización de una base de datos de relaciones (algunas relaciones pueden transformarse en atributos y viceversa).

Conversión en tablas (en caso de utilizar una base de datos relacional).



Definicion de modelo de datos

``Un modelo de datos es un sistema formal y abstracto que permite describir los datos de acuerdo con reglas y convenios predefinidos. Es formal pues los objetos del sistema se manipulan siguiendo reglas perfectamente definidas y utilizando exclusivamente los operadores definidos en el sistema, independientemente de lo que estos objetos y operadores puedan significar. ‘‘  
``Un modelo de datos es una combinación de tres componentes:

1. una colección de estructuras de datos (los bloques constructores de cualquier base de datos que conforman el modelo);
2. una colección de operadores o reglas de inferencia, los cuales pueden ser aplicados a cualquier instancia de los tipos de datos listados en (1) , para consultar o derivar datos de cualquier parte de estas estructuras en cualquier combinación deseada;
3. una colección de reglas generales de integridad, las cuales explícita o implícitamente definen un conjunto de estados consistentes --estas reglas algunas veces son expresadas como reglas de insertar-actualizar-borrar. ‘‘

Un modelo de datos puede ser usado de las siguientes maneras:

• i) como una herramienta para especificar los tipos de datos y la organización de los mismos que son permisibles en una base de datos específica;
• ii) como una base para el desarrollo de una metodología general de diseño para las bases de datos;
• iii) como una base para el desarrollo de familias de lenguajes de alto nivel para manipulación de consultas ( querys ) y datos;
• iv) como el elemento clave en el diseño de la arquitectura de un manejador de bases de datos.

El primer modelo de datos desarrollado con toda la formalidad que esto implica fue el modelo relacional , en 1969, mucho antes incluso que los modelos jerárquicos y de red. A pesar de que los sistemas jerárquicos y de red como software para manejar bases de datos son previos al modelo relacional, no fue sino hasta 1973 que los modelos de tales sistemas fueron definidos, apenas unos cuantos años antes de que estos sistemas empezaran a caer en desuso.
“El modelo de datos es el proceso que implica crear una representación que tienen los usuarios de los datos Si el modelo de datos representa en forma incorrecta la visión que poseen los usuarios de los datos, encontrarán las aplicaciones difíciles de usar, incompletas y por supuesto en el desarrollo de las bases de datos y sus aplicaciones..”
“Un modelo de datos es una serie de conceptos que puede utilizarse para describir un conjunto de datos y las operaciones para manipularlos.
Hay dos tipos de modelos de datos: los modelos conceptuales y los modelos lógicos.

• Los modelos conceptuales se utilizan para representar la realidad a un alto nivel de abstracción. Mediante los modelos conceptuales se puede construir una descripción de la realidad fácil de entender.
• En los modelos lógicos , las descripciones de los datos tienen una correspondencia sencilla con la estructura física de la base de datos.

En el diseño de bases de datos se usan primero los modelos conceptuales para lograr una descripción de alto nivel de la realidad, y luego se transforma el esquema conceptual en un esquema lógico. El motivo de realizar estas dos etapas es la dificultad de abstraer la estructura de una base de datos que presente cierta complejidad.
Un esquema es un conjunto de representaciones lingüísticas o gráficas que describen la estructura de los datos de interés.
Los modelos conceptuales deben ser buenas herramientas para representar la realidad, por lo que deben poseer las siguientes cualidades:

• Expresividad : deben tener suficientes conceptos para expresar perfectamente la realidad.
• Simplicidad : deben ser simples para que los esquemas sean fáciles de entender.
• Minimalidad : cada concepto debe tener un significado distinto.
• Formalidad : todos los conceptos deben tener una interpretación única, precisa y bien definida.

En general, un modelo no es capaz de expresar todas las propiedades de una realidad determinada, por lo que hay que añadir aserciones que complementen el esquema.”
 

Resumen:

Un modelo de datos es una serie de conceptos que puede utilizarse para describir un conjunto de datos y las operaciones para manipularlos.
Más explícitamente:
Un modelo de datos es la combinación de una colección de estructuras de datos, operadores o reglas de inferencia y de reglas de integridad, las cuales definen un conjunto de estados consistentes. El cual puede ser usado como una herramienta para especificar los tipos de datos y la organización de los mismos. Además para la manipulación de consultas y datos, así mismo es el elemento clave en el diseño de la arquitectura de un manejador de BD.
El primer modelo de datos fue el relacional en 1969, mucho antes incluso que los modelos jerárquicos y de red.

. Técnica de Aplicaciones

   El problema de las bases de datos es cómo buscar en ellas; no porque sea especialmente dificultoso sino porque – a pesar de los intentos efectuados – no hay un único lenguaje o modelo de interrogación.

Por eso, es importante tomarse un tiempo cada vez que nos enfrentemos a una base de datos, y consultar la ayuda que casi todas incorporan.

 No obstante, hay una serie de rasgos que suelen ser comunes (aunque su utilización pueda ser diferente):

—     Toda consulta se traduce en una especie de ecuación, que es la que interroga al sistema. Muchas veces oiremos hablar de ella como ecuación de búsqueda.

—     Puede buscarse por un único campo (sólo en un tipo de datos del registro: materias, títulos,...), por varios a la vez o por todos (o al menos, por los más significativos).

Normalmente, los términos están normalizados (se establece que un nombre de autor o una materia, por ej., aparezca siempre de la misma forma).

—     Se utiliza la lógica booleana para buscar por varios términos a la vez. Cuando veamos el término búsqueda avanzada, generalmente hace referencia a la utilización de tal lógica.

Los elementos básicos de la misma (llamados operadores booleanos) son los siguientes:

Y :  representa una intersección (en Matemáticas “Ç”) y reduce los resultados

Significa que los términos buscados deben encontrase todos a la vez en los registros que recuperemos. Acota, por tanto, los resultados: sirve para reducir su número.

Algunas otras formas en que aparece son: AND, + , .AND., ...

Ej.: "economics and spain " recupera sólo los registros donde aparezcan a la vez los dos términos

O :  representa una unión (en Matemáticas “È”). Amplía los resultados.

Su uso provoca que en los resultados aparezca uno cualquiera de los términos buscados en solitario, cualquier combinación de ellos (si son más de dos) y todos ellos a la vez.

Generalmente, obtenemos demasiados resultados, produciéndose ruido documental (información que no responde a lo que nos interesa en una búsqueda).

Otras formas de representación: OR, / , .OR., ...

Ej.: "economics or social" recupera los registros que contengan alguno de los términos o los dos a la vez.

NOT :  representa la negación: excluye (en Matemáticas “Ë”)

Todo término que siga al operador será considerado como no pertinente y eliminará del resultado los registros que lo contengan

Se representa también como: NOT, — , .NOT., ...

Existen otros operadores booleanos, que son combinación de los anteriores. Pondremos como ejemplo el “O exclusivo” (NOR): funciona exactamente como el O; pero invalida los registros en que aparezcan todos los términos implicados a la vez: sólo serán válidos los que contengan un único término (uno, u otro, u...)

Ej.: "Economics not spain" recupera sólo los registros que incluyan economics pero no spain.

—     Truncamientos: Consiste en indicar una serie de caracteres que queremos que aparezcan en nuestra consulta; pero sin que escribamos la palabra completa.

Se utilizan una serie de símbolos, llamados comodín, que pueden suplir a cualquier número de caracteres o a uno sólo: los más utilizados son * y s

Los truncamientos pueden situarse a la izquierda, a la derecha o en ambos lados. Los más frecuentes son los de la derecha.

Sirven para recuperar palabras que pertenecen a la misma familia. En rigor, sería como buscar varios términos utilizando el O booleano.

Ej. Econom*

Si * equivale a cualquier nº de caracteres, obtendremos Economía, econometría, económico (si no se tienen en cuenta las tildes), economicos, econometrices, economia ,...

Sería como haber utilizado en la búsqueda todos esos términos conectados con O.

 Todos estos son elementos que encontraremos en cualquier base de datos (en cierto modo, están también en la base de cualquier catálogo).

SEMANA 9- ATRIBUTOS Y DOMINIOS

ATRIBUTOS Y DOMINIOS

Dominios

Un dominio describe un conjunto de posibles valores para cierto atributo. Como un dominio restringe los valores del atributo, puede ser considerado como una restricción. Matemáticamente, atribuir un dominio a un atributo significa "todos los valores de este atributo deben de ser elementos del conjunto especificado".
Distintos tipos de dominios son: enteros, cadenas de texto, fecha, no procedurales etc.

Dominio

Dominio: Rango o conjunto de posibles valores de un atributo.

El concepto de dominio es el mismo en el modelo E-R y en el modelo relacional. Pero en este modelo tiene mayor importancia, ya que será un dato importante a la hora de dimensionar la relación.
De nuevo estamos ante un concepto muy flexible. Por ejemplo, si definimos un atributo del tipo entero, el dominio más amplio sería, lógicamente, el de los números enteros. Pero este dominio es infinito, y sabemos que los ordenadores no pueden manejar infinitos números enteros. Al definir un atributo de una relación dispondremos de distintas opciones para guardar datos enteros. Si en nuestro caso usamos la variante de "entero pequeño", el dominio estará entre -128 y 127. Pero además, el atributo corresponderá a una característica concreta de una entidad; si se tratase, por ejemplo, de una calificación sobre 100, el dominio estaría restringido a los valores entre 0 y 100.


  Dominio y atributo

·         Dominio: conjunto finito de valores homogéneos y atómicos, caracterizados por un nombre y un tipo de datos; además de ciertas restricciones en algunos casos.

Los dominios se pueden definir por extensión (= España, Costa Rica, Etc.) o por intensión (Edad > 10 < 15).

·         Atributo: un atributo A, es el papel que juega un dominio D en una relación; se dice que D es el dominio de A y se denota Dom(A); así el atributo Nacionalidad de la tabla Autor, definidos sobre el dominio Nacionalidades, nos indica que dicho dominio tiene el papel de nacionalidad del autor en la tabla Autor.

SEMANA 8 - RECURCIVIDAD

RECURSIVIDAD

Definición.Hablamos de recursividad, tanto en el ámbito informático como en el ámbito matemático, cuando definimos algo (un tipo de objetos, una propiedad o una operación) en función de sí mismo. La recursividad en programación es una herramienta sencilla, muy útil y potente.

Tipos.
Podemos distinguir dos tipos de recursividad:
Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente.
Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros.

Características.
Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y una condición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación.
Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.

Ventajas e inconvenientes.La principal ventaja es la simplicidad de comprensión y su gran potencia, favoreciendo la resolución de problemas de manera natural, sencilla y elegante; y facilidad para comprobar y convencerse de que la solución del problema es correcta.
El principal inconveniente es la ineficiencia tanto en tiempo como en memoria, dado que para permitir su uso es necesario transformar el programa recursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables.

Estructura Representación
Una tabla es una estructura homogénea en la que todos los elementos que la componen son del mismo tipo. Son estáticas, no crecen ni decrecen en tiempo de ejecución y tienen un límite preestablecido antes de la compilación.
Para acceder a los elementos de una tabla se utilizan los "índices" y estos pueden ser de cualquier tipo escalar de PASCAL (enumerados, INTEGER, CHAR, subrogo, BOOLEAN).Por ello las tablas son estructuras de acceso directo o acceso por índice. 

Búsqueda secuencial.
Búsqueda secuencial con centinela.Almacenamiento externo
Usamos espacios fuera de las de la tabla para colocar las colisiones. Dentro del almacenamiento externo hay varios tipos.
Encadenamiento directo y zona de overflow.
Encadenamiento directo.
Esta realización considera la tabla como un vector en el que cada posición contiene un elemento y un campo adicional con el comienzo de la lista de elementos con los que existe colisión. Es decir, las posibles colisiones se resuelven construyendo una lista de elementos cuya imagen hash coincida.

Ventajas: eficientes y rápidos.
Inconvenientes: Para cada elemento de la lista se debe reservar un espacio para punteros lo que significa un desaprovechamiento de memoria en el "manejo de lista".

Zona de Overflow.
Se reserva espacio en cierta zona de externa a la propia tabla, de aproximadamente el 10% de su tamaño, para introducir las colisiones. Cada sinónimo se almacena en la primera celda disponible de la zona de overflow.
Inconveniente: Desaprovechamiento de memoria (poco).Es poco eficiente cuando se han producido colisiones, ya que la búsqueda en la zona de overflow es secuencial.
Ventajas: Ocupa menos memoria que el anterior. El algoritmo de búsqueda y de inserción es mas sencillo.

Almacenamiento interno
Cuando el espacio usado para almacenar las colisiones esta dentro de los límites de la tabla. Dentro del almacenamiento interno están: Encadenamiento directo y encadenamiento vacío.

Encadenamiento directo.
Se usa dentro de la tabla un campo de tipo puntero para que apunte al siguiente colisionado, que estará dentro de la tabla. En ese campo se guarda la dirección del siguiente colisionado.
En el encadenamiento directo con zona de overflow podemos sobredimensionar la tabla para almacenar las colisiones, en esta zona las casillas estarán encadenadas con una variable que apunte al primer espacio libre de la zona de overflow. Consiste en enlazar todos los elementos cuyas claves generan igual índice primario por medio de enlaces dentro de la tabla a las nuevas posiciones ocupadas por estos elementos.
Inconvenientes: Espacio reservado en cada elemento para el enlace.
Ventajas: Más rápido que el externo con zona de overflow ya que evita la búsqueda secuencial.
Ocupación de memoria: Depende del método usado. El primer caso ocupa menos memoria, y el segundo es más rápido.

Como todo buen diseñador de base de datos sabe, es bastante común encontrarse con entidades recursivas en el diseño de nuestra BD, 2 ejemplos típicos son el jefe y el subordinado, en el diseño ambas personas se encuentran registradas como duplas dentro de la entidad Persona o Funcionario (según el diseño que hemos tomado, incluso estaría mejor diseñado si se lo hace en base al cargo), al no existir 2 entidades que tengan cardinalidad 1:M, por que así obtendríamos duplicación de datos, debemos determinar un modo que ambos estén en la misma entidad y a su vez tener la capacidad de controlar quién es jefe de quién, esto se lograría agregando una columna más que sea del mismo dominio que su propia PK, es decir, la columna nueva sería FK de la PK que le determina, logrando así una cardinalidad 1:M recursiva.

Otro ejemplo típico es el caso de los contratos, estos suelen tener la característica que vencen en una fecha determinada, por cuestiones de ventas/marketing al cliente se le facilita normalmente este proceso con una renovación de contrato (en algunos casos automáticas), entonces el nuevo contrato debe poder determinarse lo siguiente: la renovación de que contrato está siendo, o si es el primer contrato, para realizarlo se aplica el mismo ejemplo anterior, una columna FK que sea del mismo dominio de la PK que le determina.

ENTIDADES ASOCIATIVAS

En este subapartado veremos un mecanismo que nos permite considerar una interrelación entre entidades como si fuese una entidad.
La entidad que resulta de considerar una interrelación entre entidades como si fuese una entidad es una entidad asociativa, y tendrá el mismo nombre que la interrelación sobre la que se define.
La utilidad de una entidad asociativa consiste en que se puede interrelacionar con otras entidades y, de forma indirecta, nos permite tener interrelaciones en las que intervienen interrelaciones. Una entidad asociativa se denota recuadrando el rombo de la interrelación de la que proviene.

Ejemplo de entidad asociativa

La figura siguiente muestra un ejemplo de entidad asociativa:
           
Recorrido es una interrelación de conectividad M:N que registra las ciudades por donde han pasado los diferentes viajes organizados por una empresa de reparto de paquetes. Consideramos recorrido una entidad asociativa con el fin de interrelacionarla con la entidad cliente; de este modo nos será posible reflejar por orden de qué clientes se han hecho repartos en una ciudad del recorrido de un viaje, así como el número de paquetes cargados y descargados siguiendo sus indicaciones.
El mecanismo de las entidades asociativas subsume el de las entidades débiles
y resulta todavía más potente. Es decir, siempre que utilicemos una entidad débil podremos sustituirla por una entidad asociativa, pero no al revés.

Ejemplo de sustitución de una entidad débil por una asociativa

A continuación se muestra la entidad débil despacho, que tiene la interrelación asignación con la entidad empleado.
                                              
Podríamos modelizar este caso haciendo que despacho fuese una entidad asociativa si consideramos una nueva entidad número-despacho que contiene simplemente números de despachos. Entonces, la entidad asociativa despacho se obtiene de la interrelación entre edificio y número-despacho.
Aunque las entidades débiles se puedan sustituir por el mecanismo de las entidades asociativas, es adecuado mantenerlas en el modelo ER porque resultan menos complejas y son suficientes para modelizar muchas de las situaciones que se producen en el mundo real.

Dependencias funcionales

El concepto de dependencia funcional Hay veces en que los atributos están relacionados entre si de manera más especifica que la de Pertenecer a una misma relación. Hay veces en que es posible determinar que un atributo depende  de otro funcionalmente, como si existiera una función f en el “mundo”, tal que t [A] = f (t [B]). La funci´on se anotaría como f: A! B, pero como f es desconocida (o sino B seria un atributo derivado), sólo nos quedamos con A! B, la dependencia funcional, que se lee “A determina B”. Formalmente, X! Y en R se

Cumple si y sólo si 8s, t 2 R, s [X] = t[X] ) s[Y

Dependencias Funcionales (1/3)

I Es un conceptos muy importante en el diseño de base de

Datos relaciones Una dependencia funcional es una restricción entre dos

Conjuntos de atributos de la base de datos.

Sea el esquema de relación R definido sobre el conjunto de atributos A y sean X e Y subconjuntos de A llamados descriptores. Se dice que Y depende funcionalmente de X o que X determina o implica a Y, que se representa por X! Y, si y solo si, cada valor de X tiene asociado en todo momento un ´único valor de Y.

Dependencias Funcionales (2/3)

Sea el esquema de relación R definido sobre el conjunto de atributos A y sean X e Y subconjuntos de A llamados descriptores. Se dice que Y depende funcionalmente de X o que X determina o

implica a Y , que se representa por X ! Y, si y solo si, cada valor de X tiene asociado en todo momento un ´único valor de Y .X! Y para dos duplas cualesquiera t1 y t2 de un estado relación r de R, si t1 [X] = t2 [X], entonces t1 [Y] = t2[Y ]. Si una restricción de R dice que no puede haber más de una dupla con un valor X dado en cualquier instancia de relación r (R), X es una clave candidata de R y X! Y para cualquier subconjunto de atributos de Y de R. Si X! Y, no nos dice que Y! X o no.

Dependencias Funcionales (3/3)

 ej.: cód. Libro! titulo, el código del libro determina el titulo. El es el implicante y titulo es el implicado. Siempre el implicado es un hecho (una información) acerca del implicante.

OBS1: la afirmación cód. libro determina titulo NO significa que a partir de cód. libro podamos conocer el titulo. Es decir, para un esquema R, si tenemos la dependencia funcional X ! Y, dado un valor de X no podemos en general conocer el valor de Y. Solo nos limitaremos a afirmar que para dos duplas de cualquier extensión de R que tengan el mismo valor de X, el valor de Y también será igual en ambas. I OBS2: Las dependencias son predicados o restricciones sobre cualquier extensión válida del esquema de relación, por lo que observar una determinada extensión (datos) no puede llevarnos a afirmar la existencia de una dependencia funcional.