BD I - Capítulo 2. Modelo Relacional

La intención de este capítulo es introducir la notación que será utilizada en capítulos posteriores.

El modelo relacional es un modelo matemático abstracto que trabaja con relaciones, definiendo sus propiedades. El álgebra relacional es la que se encarga de definir las operaciones entre relaciones.

Para nosotros, existirá una equivalencia entre relación y tabla. Utilizaremos tablas para representar las relaciones y facilitar su estudio.

Sea la relación R = {A, B, C, D}

Donde R es el nombre de la relación y tanto A, B, C, D son los atributos que la componen.

Ya que dijimos que hablaremos de relaciones y tablas en forma equivalente, veamos cómo representar la estructura de la relación R en una tabla.

R

A	B	C	D
a1	b1	c1	d1
a2	b2	c2	d2
a3	b3	c3	d3
...	...	...	...
an	bn	cn	dn

Vayamos descomponiendo cada uno de los elementos que conforman a la relación R. En primera instancia vemos una cabecera

R

A	B	C	D

Esta cabecera está compuesta de metadatos, son los nombres que recibe cada atributo. En este caso tenemos los atributos A, B, C y D.

Los atributos poseen las siguientes propiedades:

• Identificador. Es decir, tienen un nombre único
• Atómico. Los atributos son indivisibles.
• Dominio. Define los valores legales y las operaciones que puede realizar cada atributo.

Cada fila de la relación R recibe el nombre de tupla. Cada tupla tiene los valores correspondientes a los atributos. Así, la primera tupla de la tabla es la siguiente:

a1

b1

c1

d1

Otros conceptos asociados a la estructura de una relación son los siguientes:

• Cuerpo. Es el conjunto de tuplas, el conjunto de todas las filas de la tabla (exceptuando la cabecera).
• Cardinalidad. Es la cantidad total de tuplas de la relación.
• Grado. Es la cantidad total de atributos.

 

De esta forma, la relación R tiene un grado igual a 4 y una cardinalidad igual a 'n'.

BD I - Capítulo 1. Introducción

Base de Datos I

Damos inicio al estudio de una nueva asignatura. No es la intención del curso focalizarse en conceptos teóricos, preferimos dejarle ese aspecto a autores como Date, Elmasri y Navathe.

Solamente a modo de introducción diremos que una Base de Datos es un conjunto de datos almacenados entre los que existen relaciones lógicas y que ha sido diseñada para satisfacer los requerimientos de información de una determinada empresa u organización.

Todos los contenidos que estudiaremos en los capítulos siguientes corresponderán al modelo de datos relacional. Cuando decimos modelo de datos nos referimos a que deben describirse:

• Estructuras de datos: Son los tipos de datos que existen en la base y la forma en que se relacionan.
• Restricciones de integridad: Condiciones que deben cumplir los datos para reflejar correctamente la realidad.
• Operaciones de manipulación de datos: Básicamente operaciones de inserción, eliminación, modificación y recuperación de datos.

En particular, las Bases de datos relacionales modelan la realidad utilizando relaciones. Estas relaciones pueden considerarse en forma lógica como conjuntos de datos. Pensamos cada relación como tablas compuestas por registros (las filas de la tabla) y campos (las columnas de la tabla).

Los temas que iremos abordando en los próximos capítulos son:

• Álgebra Relacional
• SQL
• Dependencias Funcionales
• Normalización de Base de Datos 

Capítulo 21. Algoritmos Greedy: Ejemplo de la mochila (Parte III)

Realizamos una ligera modificación al pseudocódigo del algoritmo de la mochila para poder almacenar los elementos que forman parte de la solución y devolverlos como resultado

Pseudocódigo

Análisis de Complejidad Temporal

El análisis es idéntico al realizado para el algoritmo del capítulo previo. La complejidad queda en el orden O(n*log(n)) si utilizamos MergeSort para ordenar la cadena por la razón Beneficio/Peso.

Capítulo 20. Algoritmos Greedy: Ejemplo de la mochila (Parte II)

Presentamos el pseudocódigo del ejemplo que resolvimos manualmente en el capítulo anterior.

Pseudocódigo

Análisis de Complejidad Temporal

Cabe señalar una importante diferencia respecto del análisis temporal para el ejemplo del cambio. Fijemos nuestra atención en el bloque 'mientras' y las condiciones:

i <= longitud(S) y capacidadParcial < P

En el peor de los casos, el bloque se ejecutará 'n' veces, siendo 'n' la cantidad de elementos en la secuencia S. Es decir, tiene mayor peso la condición i <= longitud(S) que la condición capacidadParcial < P.

Esto es así debido a que los objetos son finitos y no pueden repetirse en el armado de la solución final. Distinto era el caso en el ejemplo del cambio donde teníamos instancias infinitas de cada moneda y el objetivo era cubrir un importe P.

 

Las sentencias contenidas en el bloque 'mientras' tienen una complejidad constante dando un costo de O(n) para todo el bloque por lo explicado anteriormente.

Se observa entonces que la complejidad temporal del algoritmo dependerá del método de ordenamiento elegido para "ordenarPorBeneficioPeso". Si utilizamos MergeSort la complejidad temporal de MOCHILA_GREEDY nos queda en O(n*log(n)).

No debe sorprendernos que la complejidad en algoritmos Greedy venga dada por el método de ordenamiento utilizado ya que es la forma más eficiente que encontramos para implementar la estrategia de selección.

En el próximo capítulo haremos una ligera modificación al pseudocódigo de forma que nos permita guardar los elementos que serán almacenados en la mochila.

Fuentes:

Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda

Capítulo 19. Algoritmos Greedy: Ejemplo de la mochila (Parte I)

Continuando con los Algoritmos Greedy, centraremos nuestra atención en el ejemplo de la mochila. La descripción del problema es la siguiente:

Se tienen n objetos y una mochila con capacidad P. Cada uno de los n objetos tiene dos propiedades: peso y beneficio. Para i = 1, 2, ..., n, el objeto i tiene un peso p_i y un beneficio b_i. Tanto el peso como el beneficio son siempre positivos.

Además, los objetos pueden ser fraccionados, esto quiere decir que puedo llevar 1/2, 1/3 o cualquier otra fracción de un objeto.

Matemáticamente si una fracción x_i (0<x_i<1) del objeto i es colocada en la mochila, esta fracción contribuye en un peso x_i*p_i y en un beneficio x_i*b_i.

Para dejar en claro esto último, si tengo un objeto i cuyo peso es 12 y beneficio es 9, si decido llevar 1/3 del objeto, la contribución de este objeto al problema sería:

Peso = x_i*p_i = 1/3*12 = 4. 
Benefición = x_i*b_i = 1/3*9 = 3. 

Aclarado todo esto, el objetivo del problema es llenar la mochila de forma tal que se maximice el beneficio de los objetos transportados sin exceder la capacidad P (peso total) de la mochila.

Vamos a resolver un ejemplo de este problema en forma manual y en el siguiente capítulo lo haremos a través del pseudocódigo. Supongamos entonces que tenemos la siguiente instancia del problema:

La capacidad P de la mochila es 12 y poseemos el conjunto de elementos:

Elementos = { (p = 5; b = 4) , (p = 7; b = 5), (p = 2; b = 3), (p = 6; b = 3), (p = 4; b = 5) }

Con el fin de abreviar la nomenclatura representaremos a cada elemento e_i con el par (p_i, b_i). De esta forma, el conjunto anterior es simplemente:

Elementos = { (5,4), (7,5), (2,3), (6,3), (4,5) }

Recordemos que en los algoritmos Greedy podía identificarse una función selección, muchas veces asociada a la forma de ordenar el conjunto de elementos candidatos. En forma intuitiva, ya que el objetivo es maximizar el beneficio y los objetos pueden fraccionarse, convendría ordenar los elementos por su relación beneficio/peso en forma decreciente. Así, el conjunto de elementos ordenado por b/p nos queda:

Elementos = { (2,3), (4,5), (5,4), (7/5), (6, 3) }

Ahora, deberíamos ir tomando cada uno de estos elementos y verificar que no nos excedamos de la capacidad P de la mochila. Llamaremos W al peso parcial y B al beneficio parcial tras la elección de cada elemento (actúan como contadores).

Empecemos entonces tomando el primer elemento del conjunto ordenado, el (2,3). Nuestros contadores quedan:

W = 2
B = 3

Ya que no nos excedimos de la capacidad P, procedemos a elegir el siguiente elemento (4, 5):

W = 2 + 4 = 6
B = 3 + 5 = 8

Siendo que 6 es menor a P = 12 elegimos un tercer elemento, el (5,4):

W = 6 + 5 = 11
B = 8 + 4 = 12

El peso parcial acumulado aún no excede la capacidad de nuestra mochila, es por ello que podemos elegir un nuevo elemento: el (7,5).

W = 11 + 7 = 18 
B = 12 + 5 = 17

¿Qué ha pasado? Hemos superado la capacidad total P de la mochila. Siendo que el peso acumulado W del paso anterior era igual a 11, sólo necesitábamos contribuir en 1 para alcanzar la capacidad total. Aquí es cuando debemos fraccionar el elemento.

Es fácil ver que con la fracción 1/7 cumpliremos nuestro cometido y los acumuladores quedarán:

W = 11 + 1/7*7 = 12
B = 12 + 1/7*5 = 89/7

Todo esto realizado en forma intuitiva deriva en la solución óptima. Vale aclarar que debería demostrarse matemáticamente, cosa que excede el alcance de nuestro curso.

Esto mismo que hemos hecho manualmente, se verá plasmado en pseudocódigo en el siguiente capítulo.