Semana 8
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.
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.
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.
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.
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.
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.
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".
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.
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.
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.
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
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.
