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ónUna 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
externoUsamos 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
internoCuando 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 ASOCIATIVASEn
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ébilesy
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 asociativaA
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.
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ónUna 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
externoUsamos 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
internoCuando 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 ASOCIATIVASEn
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ébilesy
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 asociativaA
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.
No hay comentarios:
Publicar un comentario