Capitulo I - Introduccin a las Bases de Datos

Temas: 1.1 Sistemas de Archivos 1.2 Sistemas de Gestin de Bases de Datos 1.3 Inconvenientes de las Bases de Datos 1.4 Abstraccin de la informacin 1.5 Papeles en torno a una Base de Datos 1.6 Instancias y esquemas de una Base de Datos

1.1 Sistemas de Archivos Las bases de datos surgen a raz de necesidades no cubiertas por los Sistemas de Archivos tradicionales. Un sistema de archivos est formado por un conjunto de programas que dan servicio a los usuarios finales. Cada programa define y gestiona sus propios datos. Los registros son almacenados en varios archivos y se escriben diferentes programas de aplicacin para extraer registros y aadir registros a los archivos de datos. En los sistemas de archivos, la estructura fsica de los archivos de datos y de sus registros est definida dentro de los programas de aplicacin. Mantener informacin en un sistema de archivos, tiene los siguientes inconvenientes: Redundancia de datos: La informacin puede estar duplicada en los archivos de datos. Dificultad en el acceso a los datos: los sistemas de archivos son muy dependientes del

programador de aplicaciones: cualquier consulta o informe que se quiera realizar debe ser programado por l. En algunas organizaciones se conformaron con fijar el tipo de consultas e informes, siendo imposible realizar otro tipo de consultas que no se hubieran tenido en cuenta a la hora de escribir los programas de aplicacin

Dependencia de datos: ya que la estructura fsica de los datos (la definicin de los archivos y

de los registros) se encuentra codificada en los programas de aplicacin, cualquier cambio en dicha estructura es difcil de realizar. El programador debe identificar todos los programas afectados por este cambio, modificarlos y volverlos a probar, lo que cuesta mucho tiempo y est sujeto a que se produzcan errores. A este problema, tan caracterstico de los sistemas de archivos, se le denomina tambin falta de independencia de datos lgica-fsica.

Aislamiento de datos: debido a que los datos estn dispersos en varios archivos y los archivos

pueden estar en diferentes formatos, es difcil escribir nuevos programas de aplicacin para recuperar los datos apropiados.

Problemas de integridad: los valores de los datos almacenados en la base de datos, deben

satisfacer ciertos tipos de ligaduras de consistencia. Por ejemplo, el saldo de una caja de ahorro nunca puede ser negativo. Los desarrolladores hacen cumplir esas ligaduras en el sistema, aadiendo el cdigo apropiado en los diversos programas de aplicacin. Sin embargo cuando se aaden nuevas ligaduras, es difcil cambiar los programas para hacer que se cumplan. Tambin es probable que ocurran problemas de integridad referencial, es decir referencias a datos que fueron modificados o que ya no existen.

Problemas de atomicidad: en muchas aplicaciones, es crucial asegurar que una vez que un

fallo ha ocurrido y se ha detectado, los datos se restauran al estado de consistencia anterior al fallo. Por ejemplo si un programa transfiere un determinado monto de una cuenta A a una cuenta B, es posible que ante un fallo el monto haya sido debitado de la cuenta A pero no acreditado en la cuenta B. Las operaciones (en esta caso la transferencia de dinero), deben ocurrir por completo o no ocurrir (las operaciones deben ser atmicas).

Anomalas en el acceso concurrente: muchos sistemas deben permitir a mltiples usuarios

actualizar los datos en forma simultanea. En los sistemas de archivos, esta situacin debe controlarse dentro de los mismos programas de aplicacin.

Estas dificultades entre otras, han dado comienzo al desarrollo de los Sistemas de Gestin de Base de Datos (SGBD).

1.2 Sistemas de Gestin de Bases de Datos Una Base de Datos es un conjunto de datos almacenados entre los que existen relaciones lgicas y ha sido diseada para satisfacer los requerimientos de informacin de una empresa u organizacin. Las relaciones entre los conjuntos de datos viene dada por la aplicacin para la cual se disea la Base de Datos. Adems, la base de datos no slo contiene los datos de la organizacin, tambin almacena una descripcin de dichos datos. Esta descripcin es lo que se denomina meta datos, se almacena en el diccionario de datos o catlogo y es lo que permite que exista independencia de datos lgica - fsica. Los sistemas de bases de datos separan la definicin de la estructura de los datos, de los programas de aplicacin y almacenan esta definicin en la base de datos. Si se aaden nuevas estructuras de datos o se modifican las ya existentes, los programas de aplicacin no se ven afectados ya que no dependen directamente de aquello que se ha modificado. El Sistema de Gestin de Bases de Datos (SGBD) es una aplicacin (conjunto de programas) que permite a los usuarios definir, crear y mantener la base de datos, y proporciona acceso controlado a la misma. Adems un Sistema de Gestin de Bases de Datos debe de tener implementados mecanismos de seguridad que garanticen la integridad de la informacin, a pesar de cadas del sistema o intentos de accesos no autorizados. En general, un SGBD proporciona los siguientes servicios: Permite la definicin de la base de datos mediante el lenguaje de definicin de datos. Este

lenguaje permite especificar la estructura y el tipo de los datos, as como las restricciones sobre los datos. Todo esto se almacenar en la base de datos.

Permite la insercin, actualizacin, eliminacin y consulta de datos mediante el lenguaje de

manejo de datos. El hecho de disponer de un lenguaje para realizar consultas reduce el problema de los sistemas de archivos, en los que el usuario tiene que trabajar con un conjunto fijo de consultas, o bien, dispone de un gran nmero de programas de aplicacin costosos de gestionar.

Evita la redundancia de datos: la informacin no debe aparecer duplicada. Mantiene la integridad de los datos: por ejemplo si existen 2 archivos en la Base de Datos con

artculos y componentes de los artculos, que no queden componentes de un articulo cuando este se borra.

Mantiene la consistencia: segn las validaciones que se definan. Mantiene la atomicidad: las operaciones deben ocurrir por completo o no ocurrir. Mantiene la concurrencia: es decir que varios usuarios puedan acceder al mismo tiempo a la

Base de Datos. Permite definir polticas de seguridad

1.3 Inconvenientes de las Bases de Datos Complejidad. Los SGBD son conjuntos de programas muy complejos con una gran

funcionalidad. Es preciso comprender muy bien esta funcionalidad para poder sacar un buen partido de ellos.

Tamao. Los SGBD son programas complejos y muy extensos que requieren una gran

cantidad de espacio en disco y de memoria para trabajar de forma eficiente. Costo econmico del SGBD. El costo de un SGBD vara dependiendo del entorno y de la

funcionalidad que ofrece. Costo del equipamiento adicional. Tanto el SGBD, como la propia base de datos, pueden

hacer que sea necesario adquirir ms espacio de almacenamiento. Adems, para alcanzar las prestaciones deseadas, es posible que sea necesario adquirir una mquina ms grande o una mquina que se dedique solamente al SGBD. Todo esto har que la implantacin de un sistema de bases de datos sea ms cara.

Costo de la conversin. En algunas ocasiones, el costo del SGBD y el costo del equipo

informtico que sea necesario adquirir para su buen funcionamiento, es insignificante comparado al costo de convertir la aplicacin actual en un sistema de bases de datos.

Prestaciones. Un sistema de archivos est escrito para una aplicacin especfica, por lo que

sus prestaciones suelen ser muy buenas. Sin embargo, los SGBD estn escritos para ser ms generales y ser tiles en muchas aplicaciones, lo que puede hacer que algunas de ellas no sean tan rpidas como antes.

1.4 Abstraccin de la informacin A diferencia de los sistemas de archivos, el SGBD gestiona la estructura fsica de los datos y su almacenamiento. Sin embargo, se deben dar a los usuarios una visin abstracta de los datos es decir esconder ciertos detalles de cmo se almacenan y mantienen los datos. Existen 3 niveles de abstraccin: Nivel fsico: es la representacin del nivel ms bajo de abstraccin, en ste se describe en

detalle la forma en como de almacenan los datos en los dispositivos de almacenamiento. Nivel lgico o conceptual: describe que datos son almacenados realmente en la base de datos

y las relaciones que existen entre los mismos. El nivel conceptual de abstraccin lo usan los administradores de bases de datos, quienes deben decidir qu informacin se va a guardar en la base de datos.

Nivel de visin: nivel ms alto de abstraccin, es lo que el usuario final puede visualizar del

sistema terminado, describe slo una parte de la base de datos al usuario acreditado para verla. El sistema puede proporcionar muchas visiones para la misma base de datos. La interrelacin entre estos tres niveles de abstraccin se ilustra en la siguiente figura.

. . . 1.5 Papeles en torno a una Base de Datos Hay cuatro grupos de personas que intervienen en el entorno de una base de datos: el administrador de la base de datos, los diseadores de la base de datos, los programadores de aplicaciones y los usuarios. Los diseadores de la base de datos realizan el diseo lgico de la base de datos, debiendo identificar los datos, las relaciones entre datos y las restricciones sobre los datos y sus relaciones. El diseador de la base de datos debe tener un profundo conocimiento de los datos de la empresa y tambin debe conocer sus reglas de negocio. Las reglas de negocio describen las caractersticas principales de los datos tal y como las ve la empresa. Para obtener un buen resultado, el diseador de la base de datos debe implicar en el desarrollo del modelo de datos a todos los usuarios de la base de datos, tan pronto como sea posible. El diseo lgico de la base de datos es independiente del SGBD concreto que se vaya a utilizar, es independiente de los programas de aplicacin, de los lenguajes de programacin y de cualquier otra consideracin fsica. El administrador de la base de datos se encarga del diseo fsico de la base de datos y de su implementacin, realiza el control de la seguridad y de la concurrencia, mantiene el sistema para que siempre se encuentre operativo y se encarga de que los usuarios y las aplicaciones obtengan buenas prestaciones. Una vez se ha diseado e implementado la base de datos, los programadores de aplicaciones se encargan de implementar los programas de aplicacin que servirn a los usuarios finales. Estos programas de aplicacin son los que permiten consultar datos, insertarlos, actualizarlos y eliminarlos. Estos programas se escriben mediante lenguajes de tercera generacin o de cuarta generacin. Los usuarios finales son los clientes de la base de datos: la base de datos ha sido diseada e implementada, y est siendo mantenida, para satisfacer sus requisitos en la gestin de su informacin.

Vista 1 Vista 2 Vista n

Nivel Conceptual

Nivel Fisico

1.6 Instancias y esquemas de una Base de Datos Instancia : Es el estado que presenta una base de datos en un tiempo dado. Vemoslo como una fotografa que tomamos de la base de datos en un tiempo t, despus de que transcurre el tiempo t la base de datos ya no es la misma. Esquema : Es la descripcin lgica de la base de datos, proporciona los nombres de las entidades y sus atributos. El esquema no cambia los que varan son los datos y con esto tenemos una nueva instancia.

Capitulo 2 Indexacin y asociacin

Temas: 2.1 Introduccin 2.2 Conceptos bsicos 2.3 ndices ordenados 2.3.1 ndices primarios 2.3.1.1 ndices densos y dispersos 2.3.1.2 ndices multinivel 2.3.2 ndices secundarios 2.4 Archivos de ndices de rbol B+ 2.4.1 Estructura de rbol B+ 2.4.1.2 Busqueda en un rbol B+ 2.4.1.2 Insercin en un rbol B+ 2.5 Archivos de ndices de rbol B 2.6 Asociacin esttica 2.6.1 Organizacin de archivos por asociacin 2.6.1.1 Funciones de asociacin 2.6.1.2 Gestin de desbordamiento de cajones 2.6.2 ndices asociativos 2.7 Asociacin dinmica

2.1 Introduccin Muchas consultas hacen referencia solo a una pequea parte de los registros de un archivo. Por ejemplo listar todos los clientes que viven en Mendoza hace referencia solamente a una fraccin de los registros del archivo de clientes. No seria eficiente (si este tipo de consulta es frecuente) tener que leer cada registro del archivo de clientes y comprobar si el campo provincia corresponde con el cdigo asignado a la provincia Mendoza. Lo mas adecuado, seria que el sistema fuese capaz de localizar directamente estos registros. Para facilitar estas formas de acceso, se disean estructuras adicionales que se asocian con archivos de datos. 2.2 Conceptos bsicos Un ndice para un archivo del sistema funciona de igual manera que un ndice alfabtico de un libro. Si se busca un tema que haga referencia a una palabra, se busca dicha palabra en el ndice alfabtico. Una vez encontrada dicha palabra, existirn una o mas referencias a nmeros de paginas donde se tratan temas relacionados a dicha palabra. De esta manera dada una palabra, no es necesario recorrer todo el libro para ver que temas tratan sobre dicha palabra. Hay que notar que el ndice alfabtico debe estar ordenado. Si se hara una revisin de un libro y se agregara algn tema, las palabras asociadas a dicho tema se deberan insertar en el ndice manteniendo el orden. Los ndices se clasifican en: ndices ordenados: los valores que estn en el ndice estn siempre ordenados. ndices asociativos o hash ndices: los valores del ndice se almacenan en una serie de

cajones o buckets segn el valor asignado por una funcin, llamada funcin de asociacin o hash function.

Hay a su vez varias tcnicas de indexacin y asociacin. Ninguna de ellas es la mejor, cada tcnica es mas o menos apropiada para una funcin especifica en la Base de Datos. Cada tcnica debe ser valorada segn los siguientes criterios: Tipos de accesos: se pueden buscar uno o varios registros con un valor concreto en un atributo

o buscar uno o varios registros cuyos atributos tengan valores dentro de un rango de valores. Tiempo de acceso: el tiempo que se tarda en buscar uno o varios elementos en la Base de

Datos. Tiempo de insercin: el tiempo empleado en insertar un nuevo elemento. Incluye el tiempo

empleado en determinar donde insertar dicho elemento as como el tiempo empleado en actualizar la estructura del ndice.

Tiempo de borrado: el tiempo empleado para borrar un elemento. Incluye el tiempo necesario

para buscar el elemento en cuestin as como el tiempo empleado en actualizar la estructura del ndice.

Espacio adicional requerido: el espacio adicional ocupado por la estructura del ndice. Como

normalmente la cantidad necesaria de espacio adicional suele ser moderada, es razonable sacrificar el espacio para alcanzar un mayor rendimiento.

A menudo se desea tener mas de un ndice por un archivo de datos. Los atributos o conjuntos de atributos usados para buscar en un archivo, se llaman claves de bsqueda. Las claves de bsqueda no tienen que ver con los conceptos de clave candidata o sper clave, es decir las claves de bsqueda pueden no determinar unvocamente a los registros del archivo. Por ejemplo en el archivo de clientes, lo mas probable es que necesitemos definir al menos 2 ndices: uno por cdigo o por cuit y otro por razn social (dado que las bsquedas mas frecuentes se harn sobre estos campos). Entonces si definimos un ndice por cdigo y otro por razn social, cdigo seria la clave de bsqueda para el primer ndice y razon_social seria la clave de bsqueda para el segundo ndice. Una clave de bsqueda podra estar formado por mas de un campo (por ejemplo por apellido y nombres) 2.3 ndices ordenados Para permitir un acceso rpido a los registros, se puede usar una estructura de ndice. Cada estructura de ndice esta asociada con una clave de bsqueda. Un ndice almacena de manera ordenada los valores de la clave de bsqueda y asocia a cada clave los registros que contienen dicha clave de bsqueda. Los registros en el archivo indexado, pueden estar a su vez almacenados siguiendo un orden. Un archivo puede tener varios ndices, segn diferentes claves de bsqueda. Si el archivo que contiene los registros esta ordenado secuencialmente, el ndice cuya clave de bsqueda especifica el orden secuencial del archivo es el ndice primario. Los ndices primarios tambin son llamados ndices con agrupacin (clustering ndices). Por lo general, la clave de bsqueda de un ndice primario es normalmente la clave primaria. Los ndices cuyas claves de bsqueda especifican un orden diferente del orden secuencial del archivo, se llaman ndices secundarios o ndices sin agrupacin (non clustering ndices). 2.3.1 ndices primarios Los archivos con ndice primario, se llaman archivos secuenciales indexados. Son los esquemas de ndices mas antiguos y mas usados por los sistemas de Base de Datos. Se emplean en aquellas aplicaciones que demandan un procesamiento secuencial del archivo completo, as como un acceso directo a sus registros. 2.3.1.1 ndices densos y dispersos Existen 2 clases de ndices ordenados: ndice denso: contiene un registro ndice (o entrada ndice) para cada valor de la clave de

bsqueda en el archivo. El registro ndice contiene el valor de la clave y un puntero al primer registro con ese valor de bsqueda. El ejemplo siguiente ilustra un ndice denso con clave de bsqueda Sucursal

Abasto Abasto C-217 150.000 Balvanera Balvanera C-101 100.000 Centro Balvanera C-110 120.000 Liniers Centro C-215 140.000 Parque Liniers C-102 80.000 San Telmo Liniers C-201 180.000 Liniers C-218 140.000 Parque C-222 140.000 San Telmo C-305 70.000 ndice disperso: se crea un registro ndice para algunos de los valores. Al igual que los ndices

densos, cada registro ndice contiene un valor de la clave de bsqueda y un puntero al primer registro con ese valor de la clave. Para localizar un registro, se busca la entrada del ndice con el valor mas grande que sea menor o igual que el valor que se esta buscando. Se empieza por el registro apuntado por esa entrada del ndice y se continua con los punteros del archivo hasta encontrar el registro deseado.

Abasto Abasto C-217 150.000 Centro Balvanera C-101 100.000 Parque Balvanera C-110 120.000 Centro C-215 140.000 Liniers C-102 80.000 Liniers C-201 180.000 Liniers C-218 140.000 Parque C-222 140.000 San Telmo C-305 70.000 Supongamos que en este ultimo caso se desea buscar los registros de la sucursal Liniers. Usando el ndice denso de la primer figura, se sigue el puntero que va directo al primer registro de la sucursal Liniers. Se procesa el registro y se sigue el puntero de ese registro hasta localizar el siguiente registro. Se continua procesando registros hasta encontrar uno cuyo nombre de sucursal fuese distinto de Liniers. Si se usa un ndice disperso (ultima figura), no existe una entrada en el ndice con ese valor de bsqueda. Se accede a la ultima entrada del ndice en orden alfabtico antes de Liniers, cuyo valor es Centro. Se sigue ese puntero y se lee el archivo en orden secuencial hasta encontrar el primer registro con clave Liniers. Se procesa el registro y se sigue el puntero de ese registro hasta localizar el siguiente registro. Se continua procesando registros hasta encontrar uno cuyo nombre de sucursal fuese distinto de Liniers. Como se ve, generalmente es mas rpido localizar un registro si se usa un ndice denso en lugar de un disperso. Sin embargo los ndices dispersos tienen algunas ventajas sobre los ndices densos, como el de utilizar un espacio mas reducido y un mantenimiento adicional menor para las inserciones y borrados. Por lo general, se utiliza un ndice disperso con una entrada del ndice por cada bloque. La razn reside en que el costo mayor de procesar una peticin en la base de datos es el tiempo empleado en traer un bloque de disco a la memoria. Una vez trado el bloque a memoria, el tiempo que se tarda en examinar el bloque completo es despreciable. Usando un ndice disperso con estas caractersticas se localiza el bloque que contiene el registro solicitado. De esta manera (a menos que el registro este en un bloque de desbordamiento) se minimizan los accesos a los bloques mientras se mantiene un tamao de ndice tan pequeo como sea posible.

2.3.1.2 ndices multinivel Aun utilizando ndices dispersos, el tamao del ndice podra ser demasiado grande para un procesamiento eficiente. Los archivos de ndices, se almacenan como archivos secuenciales en disco. Si un ndice es lo suficientemente pequeo como para guardarlo en la memoria principal, el tiempo de bsqueda para encontrar una entrada seria despreciable. Sin embargo si el ndice es tan grande que se debe guardar en disco, buscar una entrada implicar leer varios bloques de disco. Para localizar una entrada en el archivo ndice, se puede hacer una bsqueda binaria, pero aun as, la bsqueda tiene un costo elevado. Si el ndice ocupa b bloques, la bsqueda binaria tendr que leer a lo sumo log 2 (b) bloques. Para un ndice que ocupe 100 bloques, la bsqueda binaria necesita leer 7 bloques. En un disco donde leer un bloque tarda 30 milisegundos, la bsqueda empleara 210 milisegundos lo cual es bastante. Para resolver este problema, se trata al ndice como si fuese un archivo secuencial y se construye un ndice disperso sobre el ndice primario.

. . . . . . Bloques de

datos 0

ndice externo

. . .

Bloque de datos 1

ndice interno .

Para localizar un registro, se usa en primer lugar una bsqueda binaria sobre el ndice externo para buscar el registro con el mayor valor de la clave de bsqueda que sea menor o igual al buscado. El puntero apunta a un bloque en el ndice mas interno. Hay que examinar este bloque hasta encontrar el registro con el mayor valor de la clave que sea menor o igual al buscado. El puntero de este registro apunta al bloque del archivo que contiene el registro buscado. Se pueden utilizar tantos niveles de indexacin como sean necesarios. Los ndices con 2 o mas niveles se llaman ndices multinivel.

Los ndices multinivel, estn estrechamente relacionados con la estructura de rbol, tales como los rboles binarios usados para la indexacin en memoria. 2.3.2 ndices secundarios Un ndice secundario es como un ndice denso primario, excepto en que los registros apuntados por los sucesivos valores del ndice no estn almacenados secuencialmente. Generalmente los ndices secundarios estn estructurados de manera distinta a como estn estructurados los ndices primarios. En los ndices secundarios no es suficiente apuntar solo al primer registro de cada valor de la clave de bsqueda. El resto de los registros con el mismo valor de la clave de bsqueda podran estar en cualquier otro sitio del archivo, ya que los registros estn ordenados segn la clave de bsqueda del ndice primario en lugar de la clave de bsqueda del ndice secundario. Por lo tanto, un ndice secundario debe contener punteros a todos los registros. Se puede usar un nivel adicional de direccionamiento para implementar los ndices secundarios sobre claves de bsqueda que no sean claves primarias. Los punteros en estos ndices secundarios no apuntan directamente al archivo. Por ejemplo:

70.000 Abasto C-217 150.000 80.000 Balvanera C-101 100.000

100.000 Balvanera C-110 120.000 120.000 Centro C-215 140.000 140.000 Liniers C-102 80.000 150.000 Liniers C-201 180.000 180.000 Liniers C-218 140.000

Parque C-222 140.000 San Telmo C-305 70.000

Representara a un ndice secundario teniendo como clave de bsqueda al campo Saldo. Los ndices secundarios mejoran el rendimiento de las consultas que emplean claves de bsqueda diferente de la clave de bsqueda del ndice primario. Sin embargo, requieren un tiempo adicional para el mantenimiento de cada uno de los ndices. 2.4 Archivos de ndices de rbol B+ El inconveniente principal de la organizacin de un archivo secuencial indexado reside en que el rendimiento, tanto para buscar en el ndice como para buscar secuencialmente a travs de los datos, se degrada a medida que crece el archivo de datos. Aunque esta degradacin se puede remediar reorganizando el archivo, el rendimiento de tales reorganizaciones no es deseable. La estructura de ndice de rbol B+ es la mas extendida de las estructuras de ndices que mantienen su eficiencia a pesar de la insercin y borrado de los datos.

Un ndice de rbol B+ toma la forma de un rbol equilibrado, donde los caminos de la raz a cada hoja son de la misma longitud. Cada nodo que no es nodo hoja, tiene entre x/2 y x hijos, donde x esta fijo para cada rbol en particular. Si bien la estructura de rbol B+ si bien implica una degradacin del rendimiento al insertar y al borrar, este tiempo adicional es aceptable incluso en archivos con altas frecuencias de modificacin, ya que se evita el costo de reorganizar el archivo. 2.4.1 Estructura de rbol B+ Un ndice de rbol B+ es un ndice multinivel, pero con una estructura que difiere del ndice multinivel de un archivo secuencial. En la figura siguiente se muestra un nodo tpico de rbol B+

P1 K1 P2 ... Px-1 Kx-1 Px Un nodo puede contener hasta x-1 claves de bsqueda (K1, K2, ..., Kx-1) y x punteros (P1, P2, ..., Px). Los valores de la clave de bsqueda de un nodo se mantienen ordenados. As si i < j => Ki < Kj. Consideremos primero la estructura de los nodos hojas: cada puntero Pi apunta a un registro del archivo con valor de la clave de bsqueda Pi o bien a un cajn de punteros, cada uno de los cuales apunta a un registro del archivo con valor de la clave de bsqueda Ki. La estructura cajn se utiliza solamente si la clave de bsqueda no forma una clave primaria y si el archivo no esta ordenado segn la clave de bsqueda. El puntero Px tiene un propsito especial que veremos mas adelante. En la figura siguiente se muestra un nodo hoja en el rbol B+ del archivo cuenta, donde x = 3 y la clave de bsqueda es sucursal. Obsrvese que como el archivo cuenta esta ordenado por sucursal, los punteros en el nodo hoja apuntan directamente al archivo. Abasto Balvanera

Abasto C-217 150.000 Balvanera C-101 100.000 Balvanera C-110 120.000 . . .

Cada nodo hoja puede guardar hasta x-1 claves de bsqueda. Esta permitido que los nodos hojas contengan al menos [ x / 2 ] valores. Los rangos de los valores en cada hoja no se solapan. As si Li y Lj son nodos hojas e i < j, entonces cada valor de la clave de bsqueda en Li es menor que cada valor de la clave de bsqueda en Lj. Dado que existe un orden lineal en las hojas basado en los valores de la clave de bsqueda que contienen, se usa Px para encadenar los nodos hojas en el orden de la clave de bsqueda. Esta ordenacin permite un procesamiento secuencial eficaz del archivo. Los nodos internos del rbol B+ forman un ndice multinivel (disperso) sobre los nodos hoja. La estructura de los nodos internos es la misma que la estructura de los nodos hojas, excepto que todos los punteros son punteros a nodos del rbol. Un nodo interno podra guardar hasta x punteros y debe guardar al menos [ x / 2] punteros. El numero de punteros de un nodo se llama grado de salida del nodo.

Consideremos que un nodo tiene m punteros. Para i=2, 3, ..., m-1, el puntero Pi apunta al subrbol que contiene los valores de la clave de bsqueda menores que Ki y mayores o iguales que Ki-1. El puntero Pm apunta a la parte del subrbol que contiene los valores de la clave mayores o iguales que Km-1 y el puntero P1 apunta a la parte del subrbol que contiene los valores de la clave menores que K1. El requisito de que cada nodo interno mantenga al menos [ x / 2 ] punteros se impone en todos los niveles del rbol excepto en la raz (que puede contener uno o mas valores de bsqueda). Por ejemplo, el ndice completo de rbol B+ para el archivo cuenta con clave de bsqueda Sucursal y x=3 seria:

Liniers

Centro San Telmo

Abasto Balvanera Centro Liniers Parque San

Telmo

Por simplicidad se omiten los punteros al propio archivo de datos. Notar que la cantidad de nodos que se corren en cada camino desde el nodo raz a cada nodo hoja es la misma. Esta propiedad es un requisito de los rboles B+, de hecho la letra B en rbol B+ proviene del ingles balanced (equilibrado). Esta propiedad de equilibrio de los rboles B+ es la que asegura un buen rendimiento para las bsquedas, inserciones y borrados. 2.4.1.1 Bsqueda en un rbol B+ Supongamos que se desea localizar el registro con clave de bsqueda K. Si K es menor que todas las claves de busqueda del nodo raiz, se accede al subarbol apuntado por el primer puntero. Si K es mayor que todas las claves de busqueda del nodo raiz, se accede al subarbol apuntado por el ultimo puntero. Si K es igual a alguna clave de busqueda del nodo raiz, se accede al subarbol apuntado por el puntero derecho que esta al lado de la clave de busqueda. En caso contrario, K esta entre 2 valores de clave de busqueda del nodo raiz donde Ki < K < Kj. En este caso se accede al subarbol apuntado por el puntero correspondiente a Ki. Se repite la bsqueda en el subrbol donde se accedio hasta llegar a los nodos hojas y determinar la existencia o no de la clave de busqueda K.

2.4.1.2 Insercin en un rbol B+ Usando la misma tcnica que en la bsqueda, se busca un nodo hoja donde tendra que aparecer el valor de la clave de bsqueda. Si el valor de la clave de bsqueda ya aparece en el nodo hoja, se inserta el registro en el archivo. Si el valor de la clave de bsqueda no aparece en el nodo hoja, se inserta de manera tal que las claves de bsqueda permanezcan ordenadas, se inserta el registro en el archivo y se actualizan los punteros del nodo hoja afectado. Si no hay lugar en el nodo hoja, el mismo debe ser partido en 2 nodos hojas y se toman n / 2 claves de bsqueda para cada nodo si n es par o [ n / 2 ] + 1 para el primer nodo y [ n / 2 ] para el segundo (manteniendo siempre el orden de las claves de bsqueda en los nodos hojas). Al partir un nodo hoja, se debe insertar una clave de bsqueda en el nodo del nivel inferior, el cual puede a su vez derivar en una particin de nodos en este nivel. Se repite el proceso hasta alcanzar (de ser necesario) una insercin y/o particin en el nodo raz. 2.5 Archivos de ndices de rbol B Los ndices de rbol B son similares a los ndices de rbol B+. La diferencia principal es que un rbol B elimina el almacenamiento redundante de los valores de la clave de bsqueda. En el rbol B+ de la figura anterior, las claves de bsqueda Centro, Liniers y San Telmo aparecen 2 veces. Cada valor de la clave de bsqueda aparece en algn nodo hoja y algunos se repiten en nodos internos. Un rbol B permite que los valores de la clave de bsqueda aparezcan solamente una vez. Ya que las claves de bsqueda no se repiten en los nodos del rbol, el ndice contendr menos nodos. Sin embargo puesto que las claves de bsqueda que aparecen en los nodos internos no aparecen en ninguna otra parte del rbol B, se incluye un campo adicional para tener un puntero por cada clave de bsqueda de un nodo interno. Estos punteros apuntan a registros del archivo o a los cajones de la clave de bsqueda asociada. Los nodos internos, tendrn ahora la siguiente estructura: P1 B1 K1 P2 B2 K2 ... Px-1 Bx-1 Kx-1 Px

Los punteros Pi son los punteros del rbol que se utilizan tambin para los rboles B+. Los punteros Bi son punteros a registros o cajones del archivo.

Centro

San Telmo

cajn o registro cajn o registro de Centro de San Telmo

Abasto Balvanera Liniers Parque

cajn o registro cajn o registro cajn o registro cajn o registro de Abasto de Balvanera de Liniers de Parque

2.6 Asociacin esttica Un inconveniente de la organizacin de archivos secuenciales es que hay que acceder a una estructura de ndices para localizar los datos. La organizacin de archivos basada en la tcnica de asociacin (hashing) permite evitar el acceso a la estructura de ndice. La asociacin tambin proporciona una forma de construir ndices. 2.6.1 Organizacin de archivos por asociacin En una organizacin de archivo por asociacin se obtiene la direccin del bloque de disco que contiene el registro deseado mediante el calculo directo de una funcin sobre el valor de la clave de bsqueda del registro. En nuestros trminos, utilizaremos cajn para referirnos a una unidad de almacenamiento que puede guardar uno o mas registros. Un cajn es normalmente un bloque de disco. Formalmente, sea K el conjunto de todos los valores posibles de clave de bsqueda y sea B el conjunto de todas las direcciones de cajones. Una funcin de asociacin h es una funcin de K a B. Para insertar un registro con clave de bsqueda Ki, calcularemos h(Ki) lo cual proporciona la direccin del cajn donde ser almacenado ese registro. Se supone (por ahora) que hay lugar en el cajn para almacenar el registro. Entonces el registro se almacena en dicho cajn. Para realizar una bsqueda con el valor de clave Ki, se calcula h(Ki) y luego se busca en el cajn con esa direccin al registro con clave de bsqueda Ki. 2.6.1.1 Funciones de asociacin La peor funcin de asociacin posible es la que asigna todos los valores de la clave de bsqueda al mismo cajn. Esta funcin no es deseable, ya que todos los registros deberan guardarse en el mismo cajn. Una bsqueda debera examinar cada registro hasta encontrar el deseado. En el otro extremo, otra funcin no deseable seria la que asigna a cada clave de bsqueda una direccin diferente, pues esto implicara que en cada cajn exista un nico registro (desperdicio de espacio). Una funcin ideal distribuye uniformemente las claves de bsqueda a travs de los cajones para que cada uno de ellos tenga el mismo numero de registros. Puesto que por lo general no se sabe en la etapa de diseo que valores de la clave de bsqueda se almacenaran en el archivo, se pretende elegir una funcin de asociacin que asigne los valores de las claves de bsqueda a los cajones de manera que se cumpla lo siguiente: Distribucin uniforme: cada cajn tiene asignado el mismo numero de valores de la clave de

bsqueda dentro del conjunto de todos los valores posibles de la clave de bsqueda. Distribucin aleatoria: en el caso medio, cada cajn tendr casi el mismo numero de valores

asignados a el. Como una ilustracin a estos principios, vamos a escoger una funcin de asociacin para el archivo cuenta, utilizando la clave de bsqueda sucursal. La funcin de asociacin que se elija, debe tener las propiedades deseadas no solo en el ejemplo del archivo cuenta dado, sino tambin en el archivo cuenta real para un gran banco con muchas sucursales.

Supngase que se decide tener 26 cajones y se define una funcin de asociacin que asigna a los nombres que empiezan con la letra i-esima del alfabeto al i-esimo cajn. Esta funcin de asociacin tiene la virtud de la simplicidad, pero no logra proporcionar una distribucin uniforme, ya que se espera tener mas nombres de sucursales que comiencen con letras como B o R que con Q o X. Ahora, supongamos que se quiere una funcin de asociacin en la clave de bsqueda saldo. Supongamos que el saldo mnimo es 1 y el mximo es 20.000.000. Definimos una funcin de asociacin que divide los valores posibles en 10 rangos (se utilizaran 10 cajones): 1-2.000.000, 2.000.001-4.000.000 y as sucesivamente. La distribucin de la clave de bsqueda es uniforme (ya que cada cajn tiene el mismo numero de valores de saldo diferentes) pero no es aleatorio. Los registros con saldos entre 1 y 2.000.000 son mas comunes que los registros con saldos entre 18.000.001 y 20.000.000. Las funciones de asociacin tpicas, realizan clculos sobre la representacin binaria interna de la maquina para los caracteres de la clave de bsqueda. Las funciones de asociacin requieren de un diseo cuidadoso. Una mala funcin de asociacin podra provocar que una bsqueda tome un tiempo proporcional al numero de claves de bsqueda en el archivo. Una funcin bien diseada en un caso medio de bsqueda toma un tiempo constante (pequeo), independientemente del numero de claves del archivo. 2.6.1.2 Gestin de desbordamiento de cajones Hasta ahora se ha asumido que cuando se inserta un registro, el cajn al que se asigna tiene espacio para almacenar el registro. Si el cajn no tiene espacio, sucede lo que se denomina como desbordamiento de cajones. Los desbordamientos de cajones pueden ocurrir por varias razones: Cajones insuficientes. Atasco: algunos cajones tienen asignados mas registros que otros, por lo que un cajn se

podra desbordar incluso cuando los otros tienen espacio disponible. El atasco puede ocurrir por 2 razones:

1. Varios registros tienen la misma clave de bsqueda.

2. La funcin de asociacin elegida podra producir una distribucin irregular de las claves

de bsqueda. La problemtica descripta se soluciona colocando cajones de desbordamiento. Si un registro se tiene que insertar en un cajn c y c esta lleno, se proporciona un cajn de desbordamiento para c y el registro se inserta en el cajn de desbordamiento. Si el cajn de desbordamiento tambin esta lleno, se proporciona otro cajn de desbordamiento y as sucesivamente. Todos los cajones de desbordamiento de un cajn estn encadenados juntos en una lista enlazada denominada cadena de desbordamiento.

cajn 0

cajn 1

Cajones de desbordamiento

cajn 2

para el cajn 1

. . .

cajn n

2.6.2 ndices asociativos La asociatividad se puede utilizar no solo para la organizacin de archivos, sino tambin para la creacin de estructuras de ndice. Un ndice asociativo (hash index) organiza las claves de bsqueda, con sus punteros asociados, dentro de una estructura de archivo asociativo. Un ndice asociativo se construye de la siguiente manera: se aplica una funcin de asociacin sobre la clave de bsqueda para identificar un cajn dentro del ndice, luego se almacenan las claves y los punteros asociados en el cajn del ndice (o en los cajones de desbordamiento). A continuacin se muestra un ndice asociativo secundario en el archivo cuenta para la clave cdigo de cuenta. La funcin de asociacin utilizada calcula la suma de los dgitos del numero de cuenta modulo 7. El ndice asociativo tiene 7 cajones, cada uno de tamao 2 (los ndices realistas tendran, por supuesto, tamaos de los cajones mas grandes).

cajn 0 cajn 1 C-215 C-305 cajn 2 Abasto C-217 150.000 C-101 Balvanera C-101 100.000 C-110 Balvanera C-110 120.000 Centro C-215 140.000 cajn 3 Liniers C-102 80.000 C-217 C-201 Liniers C-201 180.000 C-102 Liniers C-218 140.000 Parque C-222 140.000 cajn 4 San Telmo C-305 70.000 C-218 cajn 5 cajn 6 C-222 Uno de los cajones tiene 3 claves asignadas a el, por lo que tiene un cajn de desbordamiento. En este ejemplo, cdigo de cuenta es una clave primaria para cuenta, por lo que cada clave de bsqueda tiene solamente un puntero asociado. En general se pueden asociar mltiples punteros con cada clave. 2.7 Asociacin dinmica Como se ha visto, la necesidad de fijar el conjunto C de direcciones de cajn, presenta un problema serio con la tcnica de asociacin esttica vista. La mayora de las bases de datos crece con el tiempo. Si se va a utilizar la asociacin esttica para estas bases de datos, tenemos 3 clases de opciones: 1. Elegir una funcin de asociacin basada en el tamao actual del archivo. Esta opcin producir

una degradacin del rendimiento a medida que la base de datos crezca. 2. Elegir una funcin de asociacin basada en el tamao previsto del archivo con relacin a un

punto determinado del futuro. Aunque se evite la degradacin del rendimiento, inicialmente puede que se pierda una cantidad de espacio significante.

3. Reorganizar peridicamente la estructura asociativa en respuesta al crecimiento del archivo.

Esta reorganizacin implica elegir una nueva funcin de asociacin, volviendo a calcular la funcin de asociacin de cada registro en el archivo y generando nuevas asignaciones de los

cajones. Esta reorganizacin es una operacin masiva que requiere mucho tiempo. Adems, es necesario prohibir el acceso al archivo durante la reorganizacin.

Algunas tcnicas de asociacin dinmica permiten modificar la funcin de asociacin dinmicamente para acomodarse al aumento o disminucin de la base de datos. Describiremos una forma de asociacin dinmica, llamada asociacin extensible. La asociacin extensible hace frente a los cambios del tamao de la base de datos, separando y uniendo cajones a medida que la base de datos aumenta o disminuye. Como resultado, se conserva eficazmente el espacio. Por otra parte, puesto que la organizacin se realiza sobre un cajn cada vez, la degradacin del rendimiento resultante es aceptable. Con la asociacin extendible se elige una funcin de asociacin h con las propiedades deseadas de uniformidad y aleatoriedad. Sin embargo, esta funcin de asociacin genera valores dentro de un rango relativamente amplio (llamado enteros binarios de b-bits). Un valor normal de b es 32. No se crea un cajn para cada valor de la funcin de asociacin. De hecho 232 esta por encima de 4 billones y no seria razonable crear tanto cajones. Por el contrario, se crean cajones bajo demanda, esto es, tantos como registros haya insertados en el archivo. Inicialmente no se utiliza el total de b bits del valor de la funcin de asociacin. En cualquier caso, empleamos i bits, donde 0

hace considerando un bit adicional en el valor de la funcin de asociacin. Luego se incrementa el valor de i en uno, duplicando el tamao de la tabla de direcciones de cajones. Cada entrada se sustituye por dos entradas, cada una de las cuales con el mismo puntero que la entrada original. Ahora 2 entradas en la tabla de direcciones apuntan al cajn j. as pues se asigna un nuevo cajn (cajn z) y hacemos que la segunda entrada apunte al nuevo cajn. A continuacin se vuelve a calcular la funcin de asociacin para cada registro del cajn j y dependiendo de los primeros i bits se mantiene en el cajn j o se coloca en el cajn z.

Si i > i j , entonces mas de una entrada en la tabla de direcciones de cajones apunta al cajn j.

as se puede dividir el cajn j sin incrementar el tamao de la tabla de direcciones. Se asigna un nuevo cajn (cajn z) y se pone i j e i z al valor que resulta de aadir uno al valor i j original. A continuacin se ajustan las entradas en la tabla de direcciones de cajones que anteriormente apuntaban al cajn j. La primera mitad de todas las entradas se dejan como estaban (apuntando al cajn j) y el resto de las entradas se ponen apuntando al cajn recientemente creado (cajn z). Por ultimo al igual que el caso anterior, se vuelve a calcular la funcin de asociacin para cada registro en el cajn j y se colocan o bien en el cajn j o en el cajn z.

Para borrar un registro con valor de clave de bsqueda K, se sigue el mismo procedimiento de bsqueda anterior, finalizando en algn cajn j. Se suprimen ambos el registro del archivo y la clave de bsqueda en el cajn. El cajn tambin se elimina si queda vaci. Si esto sucede, se reduce el tamao de la tabla de direcciones de cajones a la mitad. A continuacin mostraremos un ejemplo de insercin en el archivo cuentas. Supongamos que elegimos una funcin de asociacin que produce los siguientes valores: Sucursal h(sucursal) Abasto 0010 1101 1111 1011 0010 1100 0011 0000 Balvanera 1010 0011 1010 0000 1100 0110 1001 1111 Centro 1100 0111 1110 1101 1011 1111 0011 1010 Liniers 1111 0001 0010 0100 1001 0011 0110 1101 Parque 0011 0101 1010 0110 1100 1001 1110 1011 San Telmo 1101 1000 0011 1111 1001 1100 0000 0001 Vamos a suponer que un cajn solo puede almacenar 2 registros y que inicialmente el archivo esta vaco: Prefijo asociativo 0 0 cajn 1 Vamos a insertar el registro (Abasto, C-217, 150.000). La tabla de direcciones de cajones contiene un puntero al nico cajn donde se inserta el registro (hay lugar en el cajn). Prefijo asociativo 0 0 Abasto C-217 150.000

Al insertar el siguiente registro (Balvanera, C-101,100.000) que se inserta en el nico cajn existente dado que el cajn aun tiene lugar. Prefijo asociativo 0 0 Abasto C-217 150.000 Balvanera C-101 100.000 Cuando se intenta insertar el registro (Balvanera,C-110,120.000) nos encontramos con que el cajn esta lleno. Ya que i = i 0, es necesario incrementar el numero de bits que se toman del valor de la funcin de asociacin. Ahora se utiliza un bit, permitiendo 21 = 2 cajones. Este incremento en el numero de bits necesario, duplica el tamao de la tabla de direcciones de cajones a 2 entradas. Se continua con la divisin del cajn, colocando en el nuevo cajn aquellos registros cuya clave de bsqueda tiene un valor de la funcin de asociacin que comienza por 1 y dejando el resto de los registros (los que comienzan con 0) en el cajn original. 1 1 0 Abasto C-217 150.000 1 1 Balvanera C-101 100.000 Balvanera C-110 120.000 A continuacin insertamos (Centro, C-215, 140.000). Ya que el primer bit de h(Centro) es 1, se tiene que insertar este registro en el cajn apuntado por la entrada 1 en la tabla de direcciones de cajones. Nuevamente el cajn apuntado esta lleno. Se incrementa el numero de bits que se usan del valor de la funcin de asociacin a 2, lo cual duplica el tamao de la tabla de direcciones de cajones a 22 = 4 entradas. Como el cajn con el prefijo 0 de la tabla de direcciones no se dividi, las 2 entradas de la tabla de direcciones 00 y 01 apuntan al mismo cajn. Para cada registro en el cajn con prefijo 1 del valor de la funcin de asociacin, se examinan los 2 primeros bits del valor de la funcin de asociacin para determinar que cajn de la nueva estructura le corresponde. 2 1 00 Abasto C-217 150.000 01 10 11 2 Balvanera C-101 100.000 Balvanera C-110 120.000 2 Centro C-215 140.000

Proseguimos insertando el registro (Liniers, C-102, 80.000) el cual se aloja en el mismo cajn que Centro. La siguiente insercin (Liniers, C-201, 180.000) provoca un desbordamiento en un cajn, produciendo el incremento del numero de bits y la duplicacin de la tabla de direcciones de cajones. La insercin del siguiente registro (Liniers, C-218, 140.000) produce otro desbordamiento. Sin embargo este desbordamiento no se puede resolver incrementando el numero de bits, ya que los 3 registros tienen exactamente el mismo valor de la funcin de asociacin. Por lo tanto, se utiliza un cajn de desbordamiento como se muestra en la siguiente figura: 3 1 000 Abasto C-217 150.000 001 010 011 2 100 Balvanera C-101 100.000 101 Balvanera C-110 120.000 110 111 3 Centro C-215 140.000 3 Liniers C-102 80.000 Liniers C-218 140.000 Liniers C-201 180.000 Se continua de esta manera hasta que se insertan todos los registros del archivo cuenta. La estructura resultante seria: 3 1 000 Abasto C-217 150.000 001 Parque C-222 140.000 010 011 2 100 Balvanera C-101 100.000 101 Balvanera C-110 120.000 110 111 3 Centro C-215 140.000 San Telmo C-305 70.000 3 Liniers C-102 80.000 Liniers C-218 140.000 Liniers C-201 180.000

Capitulo 3 Modelos de datos Temas: 3.1 Diseo Conceptual de Bases de Datos 3.2 Metodologa de diseo de Bases de Datos 3.3 Modelos de Datos 3.4 Tipos de modelos 3.5 Modelo Entidad - Relacin 3.6 Modelo Entidad Relacin Extendido 3.7 Modelo Relacional 3.8 Transformacin del modelo E-R al modelo Relacional

3.1 Diseo Conceptual de Bases de Datos El diseo de bases de datos es el proceso por el que se determina la organizacin de una base de datos, incluidos su estructura, contenido y las aplicaciones que se han de desarrollar. El diseo de bases de datos desempea un papel central en el empleo de los recursos de informacin en la mayora de las organizaciones. El diseo de bases de datos ha pasado a constituir parte de la formacin general de los informticos.' Las bases de datos son componentes esenciales de los sistemas de informacin, usadas rutinariamente en todos los computadores. El diseo de bases de datos se ha convertido en una actividad popular, desarrollada no slo por profesionales sino tambin por no especialistas. A finales de la dcada de 1960, cuando las bases de datos entraron por primera vez en el mercado del software, los diseadores de bases de datos actuaban como artesanos, con herramientas muy primitivas: diagramas de bloques y estructuras de registros eran los formatos comunes para las especificaciones, y el diseo de bases de datos se confunda frecuentemente con la implementacin de las bases de datos. Esta situacin ahora ha cambiado: los mtodos y modelos de diseo de bases de datos han evolucionado paralelamente con el progreso de la tecnologa en los sistemas de bases de datos. Se ha entrado en la era de los sistemas relacionales de bases de datos, que ofrecen poderosos lenguajes de consulta, herramientas para el desarrollo de aplicaciones e interfaces amables con los usuarios. La tecnologa de bases de datos cuenta ya con un marco terico, que incluye la teora relacional de datos, procesamiento y optimizacin de consultas, control de concurrencia, gestin de transacciones y recuperacin, etc. Segn ha avanzado la tecnologa de bases de datos, as se han desarrollado las metodologa y tcnicas de diseo. Se ha alcanzado un consenso, por ejemplo, sobre la descomposicin del proceso de diseo en fases, sobre los principales objetivos de cada fase y sobre las tcnicas para conseguir estos objetivos.'' Desafortunadamente, las metodologas de diseo de bases de datos no son muy populares; la mayora de las organizaciones y de los diseadores individuales confa muy poco en las metodologas para llevar a cabo el diseo y esto se considera, con frecuencia, una de las principales causas de fracaso en el desarrollo de los sistemas de informacin. Debido a la falta de enfoques estructurados para el diseo de bases de datos, a menudo se subestiman el tiempo o los recursos necesarios para un proyecto de bases de datos, las bases de datos son inadecuadas o ineficientes en relacin a las demandas de la aplicacin, la documentacin es limitada y el mantenimiento es difcil. Muchos de estos problemas se deben a la falta de una claridad que permita entender la naturaleza exacta de los datos, a un nivel conceptual y abstracto. En muchos casos, los datos se describen desde el comienzo del proyecto en trminos de las estructuras finales de almacenamiento; no se da peso a un entendimiento de las propiedades estructurales de los datos que sea independiente de los detalles de la realizacin.'' 3.2 Metodologa de diseo de Bases de Datos El diseo de una base de datos es un proceso complejo que abarca decisiones a muy distintos niveles. La complejidad se controla mejor si se descompone el problema en subproblemas y se resuelve cada uno de estos subproblemas independientemente, utilizando tcnicas especficas. As, el diseo de una base de datos se descompone en diseo conceptual, diseo lgico y diseo fsico. El diseo conceptual parte de las especificaciones de requisitos de usuario y su resultado es el esquema conceptual de la base de datos. Un esquema conceptual es una descripcin de alto nivel de la estructura de la base de datos, independientemente del SGBD que se vaya a utilizar para manipularla.

Un modelo conceptual es un lenguaje que se utiliza para describir esquemas conceptuales. El objetivo del diseo conceptual es describir el contenido de informacin de la base de datos y no las estructuras de almacenamiento que se necesitarn para manejar esta informacin. El diseo lgico parte del esquema conceptual y da como resultado un esquema lgico. Un esquema lgico es una descripcin de la estructura de la base de datos en trminos de las estructuras de datos que puede procesar un tipo de SGBD. Un modelo lgico es un lenguaje usado para especificar esquemas lgicos (modelo relacional, modelo de red, etc.). El diseo lgico depende del tipo de SGBD que se vaya a utilizar, no depende del producto concreto. El diseo fsico parte del esquema lgico y da como resultado un esquema fsico. Un esquema fsico es una descripcin de la implementacin de una base de datos en memoria secundaria: las estructuras de almacenamiento y los mtodos utilizados para tener un acceso eficiente a los datos. Por ello, el diseo fsico depende del SGBD concreto y el esquema fsico se expresa mediante su lenguaje de definicin de datos. 3.3 Modelos de Datos Un modelo de datos es una serie de conceptos que puede utilizarse para describir un conjunto de datos y las operaciones para manipularlos. Un modelo es una representacin de algo. Un modelo de datos es una representacin que describe los datos y las relaciones entre ellos. Hay dos tipos de modelos de datos: los modelos conceptuales y los modelos lgicos. Los modelos conceptuales se utilizan para representar la realidad a un alto nivel de abstraccin. Mediante los modelos conceptuales se puede construir una descripcin de la realidad fcil de entender. En los modelos lgicos, las descripciones de los datos tienen una correspondencia sencilla con la estructura fsica de la base de datos. En el diseo de bases de datos se usan primero los modelos conceptuales para lograr una descripcin de alto nivel de la realidad, y luego se transforma el esquema conceptual en un esquema lgico. 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 lingsticas o grficas que describen la estructura de los datos de inters. 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 fciles de entender. Minimalidad: cada concepto debe tener un significado distinto. Formalidad: todos los conceptos deben tener una interpretacin 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 aadir aserciones que complementen el esquema. 3.4 Tipos de modelos Los modelos de datos se clasifican en tres grupos principales:

1. Modelos lgicos basados en objetos: Se usan para describir datos en los niveles conceptual y de visin. Ejemplos de este tipo de modelos son:

Modelo entidad relacin.

Modelo binario

Modelo semntico de los datos

Modelo infolgico

2. Modelos lgicos basados en registros: Se utilizan para describir datos en los niveles conceptual y fsico. Estos modelos utilizan registros e instancias para representar la realidad. Se usan para especificar la estructura lgica de la Base de Datos y para proporcionar una descripcin mas alta de la implementacin. Ejemplos de estos tipos de modelos son:

Modelo relacional: Los datos y las relaciones se representan mediante tablas, cada una con diferentes columnas y nombres nicos.

Modelo de red: Los datos se representan mediante nombres de registros y las relaciones mediante conjunto de ligas.

Modelo jerrquico: Es semejante al modelo de red, pero con una estructura arbolada.

3. Modelos fsicos de datos: describen los datos en el nivel ms bajo y permiten identificar algunos detalles de implementacin para el manejo del hardware de almacenamiento. Ejemplos de este tipo de modelos son:

Modelo unificador

Modelo memoria de cuadros 3.5 Modelo Entidad - Relacin Fue propuesto por Peter Chen en el ao 1976 como medio de representacin conceptual de los problemas y para representar la visin de un sistema de forma global. El modelo Entidad-Relacin es en esencia una herramienta del diseo utilizada para representar el mundo real por medio de simbologas y expresiones determinadas. No tiene implementacin fsica. Representa la realidad a travs de entidades y relaciones. Una entidad es un objeto que existe y que puede ser distinguido de otro por medio de sus propiedades o atributos. Por ejemplo: el empleado de una fabrica, un automvil, un alumno , una cuenta bancaria. Se clasifican en tangibles o concretos (objetos que se pueden ver, tocar o sentir) e intangibles o abstractos (no pueden verse aun sabiendo que existen).

Un conjunto de entidades es un grupo de entidades del mismo tipo. Una entidad puede pertenecer a mas de un conjunto de entidades a la vez. Por ejemplo, la persona Juan Gonzales puede ser parte de los conjuntos de entidades alumnos y clientes. Una entidad se distingue de otra porque posee ciertas caractersticas que la hacen nica. A estas caractersticas se les conoce como atributo. Por ejemplo el apellido, el nombre, la direccin, el numero de documento, el sexo y la fecha de nacimiento son atributos de la entidad alumno. El rango de valores validos para un atributo determinado ser conocido como dominio del atributo. En el modelo Entidad-Relacin, los conjuntos de entidades se representan por rectngulos y los atributos por elipses. Ejemplos: Una relacin es una asociacin entre 2 o mas entidades. Un conjunto de relaciones es un grupo de relaciones del mismo tipo. Por ejemplo: Clientes Relacin Dueo de Cuentas Bancarias Numero Apellido Nro. Cuenta Saldo

1010 Lopez 325/2 500.00

1030 Gomez 484/5 350.20

1040 Perez 3200/12 2800.25

400/21 305.10 Una relacin puede estar definida con una sola entidad. Una relacin puede tener atributos descriptivos. La cantidad de conjunto de entidades que participan de una relacin, se llama grado de la relacin. Las mas comunes son relaciones de grado 2, tambin llamadas relaciones binarias.

Automovil

Patente Modelo

Color

Alumno

Dni Apellido

Nombres

Direccion

Telefono

Sexo

Fecha Nacimiento

Cardinalidad de una relacin Especifica la cantidad de entidades que pueden asociarse mediante la relacin. Se dividen en:

1. UNA A UNA: Una entidad de A puede asociarse nicamente con a lo sumo una entidad de B.

2. UNA A MUCHAS: Una entidad de a puede asociarse con cualquier cantidad de entidades de B.

3. MUCHAS A UNA: Cualquier cantidad de entidades de A puede asociarse con una entidad de B.

4. MUCHAS A MUCHAS: Cualquier cantidad de entidades de a puede asociarse con cualquier cantidad de entidades en B.

Ejemplo: UNA A UNA UNA A MUCHAS MUCHAS A UNA MUCHAS A MUCHAS Alumnos Tesis A B

Carreras Alumnos A B

Alumnos Carreras A B

Alumnos Materias A B

En el modelo Entidad-Relacin, los conjuntos de relaciones se representan con rombos y la cardinalidades se expresan por lneas con flechas hacia el lado de la cardinalidad 1.

Ejemplos: Claves primarias Entendemos como una clave al medio que nos permite identificar en forma unvoca (nica e inequvoca) a una entidad dentro de un conjunto de entidades.

Existen diversas categoras que permiten clasificar los tipos de claves a utilizar:

a) SUPER -CLAVE .- Es un conjunto de atributos mediante los cuales es posible reconocer a una entidad. Este tipo de claves contiene comnmente atributos ajenos; es decir; atributos que no son indispensables para llevar a cabo el reconocimiento de la entidad.

Provincias

Codigo Nombre

Ciudades

Codigo Nombre

Capital de

Clientes

Cuit Razon Social

Direccion

Telefono

Pedidos

Numero Fecha

Fecha Entrega

Realiza

Personas

Dni

Nombres Sexo

Viviendas Tipo

Ambientes

Vive en

Fecha

Dni

Apellido Calle

Numero

b) CLAVE CANDIDATO.- Son aquellas sper claves que no contienen atributos ajenos; es decir, aquellos conjuntos de atributos que no tienen un subconjunto menor que pueda considerarse como sper clave. c) CLAVE PRIMARIA.- Es aquella clave que el diseador de la base de datos selecciona entra las claves candidatos encontradas. Los atributos que son claves primarias en los conjuntos de entidades, se los subraya en el diagrama Entidad Relacin. Ejemplo 3.6 Modelo Entidad Relacin Extendido El Modelo Entidad-Relacin Extendido incluye todos los conceptos del Entidad-Relacin e incorpora los conceptos de Subclase y Superclase con los conceptos asociados de Especializacin y Generalizacin. Asociado a estos conceptos est el importante mecanismo de Herencia de atributos. Habr que tener en cuenta que no existe una terminologa estandarizada para estos conceptos, por lo que usaremos la mas difundida. Subclases, Superclases y Especializacin En el modelo Entidad-Relacin, un conjunto de entidades agrupa un conjunto de ocurrencias de entidades del mismo tipo. En muchos casos, estas ocurrencias se pueden agrupar a su vez en otros subconjuntos que tienen un significado propio para los propsitos de la Base de Datos y, por tanto, deberan representarse de forma explcita. Por ejemplo, la entidad EMPLEADO puede a su vez subdividirse en SECRETARIA, INGENIERO, TCNICO, ASALARIADO, SUBCONTRATADO, etc. El conjunto de ocurrencias de entidades en cada uno de estos subconjuntos de entidades ser un subconjunto de las ocurrencias de entidad de EMPLEADO, ya que por ejemplo, un ingeniero tambin es un empleado. Llamaremos a cada uno de estos subconjuntos Subclases de la entidad EMPLEADO y a EMPLEADO una Superclase de cada uno de estos subconjuntos. Llamaremos a la relacin existente entre las Superclases y las Subclases como relacin Clase/Subclase, tambin conocida en algunas bibliografas como relacin ISA (is a) o ES UN en castellano. En el ejemplo anterior, EMPLEADO/SECRETARIA y EMPLEADO/TCNICO son dos relaciones Clase/Subclase.

Cuentas

Numero Saldo

Clientes

Cuit Razon Social

Dni

Direccin

Pertenece a

Hay que tener en cuenta que una ocurrencia de una Subclase representa el mismo objeto real que alguna correspondiente a su Superclase, por ejemplo la SECRETARIA "Hernandez Julia" ser tambin la EMPLEADA " Hernandez Julia ". Por tanto, la ocurrencia de Subclase es la misma que en la Superclase pero con un rol especfico. Una ocurrencia de Subclase no tienen sentido si no es a su vez ocurrencia de Superclase. Por otro lado, una ocurrencia de superclase puede ser a su vez ocurrencia de varias subclases o de ninguna. Por ejemplo, "Mora Jorge" como ocurrencia de EMPLEADO puede a su vez pertenecer a subclases INGENIERO y ASALARIADO. Las relaciones ES UN se representan en el modelo Entidad-Relacin Extendido con un rectngulo. Herencia de atributos en la relacin ES UN Debido a que una subclase es a su vez parte de una superclase, la subclase tendr sus atributos especficos as como los atributos correspondientes a la superclase a la que pertenece. Esto quiere decir que la ocurrencia de entidad de una subclase hereda los atributos correspondientes a la superclase a la que pertenece. Especializacin El proceso por el que se definen las diferentes subclases de una superclase se conoce como especializacin.

Empleado

Cuil Apellido Nombre

Fecha_nacimiento

Fecha_ingreso

ES UN

Secretaria Ingeniero Tecnico Asalariado Subcontratado

Velocidad_escritura

Tipo Nivel Sueldo Valor_hora

El conjunto de subclases se define basndonos en caractersticas diferenciadoras de las ocurrencias de entidad de la superclase. Por ejemplo, el conjunto de subclases {SECRETARIA, INGENIERO, TECNICO} es una especializacin de la superclase EMPLEADO mediante la distincin del tipo de trabajo en cada ocurrencia de entidad. Podemos tener varias especializaciones de una misma entidad basndonos en distintos criterios. Por ejemplo, otra especializacin de EMPLEADO podra dar lugar a las subclases ASALARIADO y SUBCONTRATADO, dependiendo del tipo de contrato. Generalizacin El proceso de especializacin expuesto en el punto anterior nos permite lo siguiente:

Definir un conjunto de subclases a partir de una entidad. Asociar atributos especficos a cada subclase. Establecer relaciones especficas entre cada subclase con otras entidades o

subclases. Podemos pensar en un proceso inverso de abstraccin en el cual suprimimos las diferencias entre las distintas entidades, identificando sus caractersticas comunes, y generalizando dichas entidades en una sola superclase de la cual las entidades iniciales seran subclases especiales. Usamos el trmino generalizacin para referirnos al proceso de definicin de una entidad generalizada a partir de unas entidades dadas. 3.7 Modelo Relacional Fue propuesto por Codd en el ao 1970 y esta basado en la teora de conjuntos. Todos los datos se estructuran lgicamente en forma de tablas (relaciones). La tabla o relacin es la estructura nica del modelo. Una tabla es un conjunto de filas o tuplas. Cada fila representa una entidad (la tabla representa al Conjunto de Entidades). Las columnas representan a los atributos. El grado de una relacin es la cantidad de atributos que posee. Ejemplo: ALUMNOS(dni, apellido, nombre, direccion, telefono, sexo, fecha_nacimiento) Es una tabla o relacin de grado 7. Si llamamos D1 al conjunto de valores del atributo 1 (dominio), D2 al conjunto de valores del atributo 2, Dn al conjunto de valores del atributo n, luego una fila o tupla cualquiera de la tabla

formada por los valores (v1, v2, ... , vn) D1 X D2 X .... X Dn donde X representa al producto cartesiano. Luego: n

TABLA X Di i=1

Una relacin es un subconjunto del producto cartesiano de una lista de dominios. Cada tabla debe tener un nombre nico. No se pueden repetir los nombres de los atributos dentro de una tabla. No pueden existir en una tabla 2 filas o tuplas idnticas. Los atributos claves se subrayan.

Ejemplos: ALUMNOS(dni, apellido, nombre, direccion, telefono, sexo, fecha_nacimiento) CLIENTE(cuit, razon, direccion, telefono) PEDIDOS(numero, fecha, fecha_entrega) Los ejemplos anteriores representas esquemas de una Base de Datos. Un ejemplo de una instancia seria: PEDIDOS NUMERO FECHA FECHA_ENTREGA

345 12/03/2001 21/03/2001 346 12/03/2001 26/03/2001 348 15/03/2001 31/03/2001 349 15/03/2001 15/04/2001

3.8 Transformacin del modelo E-R al modelo relacional 1) Toda conjunto de entidades del DER se transforma en una tabla. Los identificadores son

tambin identificadores en el modelo relacional. Ejemplo: MODELO DER MODELO RELACIONAL

A(A1, A2, ... , An) : 2) Toda relacin M:N se transforma en una tabla, cuyo atributos son los identificadores de las

entidades que une mas los atributos propios de la relacin. Se toman como identificadores de la tabla a los atributos que eran identificadores en las entidades que relacionaba.

Ejemplo:

A

A1

A2

An

MODELO DER MODELO RELACIONAL A( A1, A2, ..., An)

B( B1, B2, ... , Bm) R(A1, B1, B2, R1) . . 3) Toda relacin 1:N es absorbida por la tabla que corresponda a la cardinalidad muchos por el

concepto de clave fornea siempre y cuando no tenga atributos propios dicha relacin. Ejemplo: MODELO DER MODELO RELACIONAL . . A( A1, A2, ..., An)

B(B1, B2, ... , Bm, A1) . .

A

A1

B

B1

R

A

A1 A2 An

B

B1 B2 Bm

R

A2 An

B2 Bm

R1

Si hay atributos propios en la relacin, conviene considerar una tabla por la relacin, dado que de incorporar dichos atributos propios en la tabla correspondiente a la cardinalidad muchos, obligara a asignar valores nulos si no hay instancias de la relacin. Ejemplo: MODELO DER MODELO RELACIONAL VENDEDOR(Codigo, Apellido, Nombre)

CLIENTES(Cuit, Razon, Direccion) ATIENDE(Codigo, Cuit, Comision) Se podra agregar el campo Codigo como clave fornea de la tabla Clientes junto con el campo Comision, pero esto obligara a definir valores nulos de comisin y cdigo de vendedor para aquellos clientes que no tienen vendedor asociado. En el caso de generar una tabla por la relacin, se toma como identificadores a los identificadores de la entidad Muchos. 4) Toda relacin 1:1 es absorbida por una de las tablas correspondientes a una entidad (como

clave fornea) si no hay atributos propios o bien se genera una tabla por la relacin con las claves de las entidades mas los atributos propios seleccionando como atributos claves en forma indistinta a los que correspondan a atributos claves en una entidad.

VENDEDOR

Codigo Apellido Nombre

CLIENTES

Cuit Razon Direccion

ATIENDE

Comision

Ejemplo: MODELO DER MODELO RELACIONAL . . .. A(A1, A2, ... , An) B(B1, B2, ..., Bm, A1)

o bien A(A1, A2, ... , An, B1, B2) B(B1, B2, ... , Bm) . . MODELO DER MODELO RELACIONAL . . A(A1, A2, ... , An) B(B1, B2, ..., Bm) R(A1, B1, B2, R1, R2)

o bien A(A1, A2, ... , An) B(B1, B2, ..., Bm) R(A1, B1, B2, R1, R2) . .

A

A1

B

R

B

B1 B2 Bm

R

R1

R2

A

A1 A2 An

A2 An

B2 Bm B1

5) Todo conjunto de entidades subclase de otro conjunto de entidades se transforma en una tabla

que hereda los atributos claves del conjunto de entidades clase. Estos atributos heredados tambin son claves en la subclase.

En el ejemplo dado en el apartado 2.6, las tablas quedaran: EMPLEADO(Cuil, Apellido, Nombre, Fecha_nacimiento, Fecha_ingreso) SECRETARIA(Cuil, velocidad_escritura) INGENIERO(Cuil, tipo) TECNICO(Cuil, nivel) ASALARIADO(Cuil, sueldo) SUBCONTRATADO(Cuil, valor_hora)

Capitulo 4 Algebra Relacional

Temas: 4.1 Algebra Relacional 4.2 Operadores fundamentales 4.3 Seleccin 4.4 Proyeccin 4.5 Unin 4.6 Diferencia 4.7 Producto cartesiano 4.8 Renombramiento 4.9 Operadores no fundamentales 4.10 Interseccin 4.11 Junta natural 4.12 Divisin 4.13 Asignacin

4.1 lgebra relacional Es un lenguaje de consulta (el usuario solicita informacin de la Base de Datos) terico (no tiene implementacin fsica directa) y es procedural (el usuario especifica las operaciones para calcular el resultado, a diferencia de los lenguajes no procedurales en los que el usuario describe la informacin que necesita sin dar el o los procedimientos para obtenerla). El Algebra relacional esta formada por un conjunto de operaciones que toman como entrada una o mas relaciones (del modelo relacional) y producen como resultado otra relacin. Las operaciones fundamentales son: Seleccin, Proyeccin, Unin, Diferencia, Producto cartesiano y Renombramiento. Cualquier consulta puede ser expresada combinando estas operaciones. Hay otras operaciones como Interseccin, Junta Natural, Divisin y Asignacin que se definen en trminos de las operaciones fundamentales. 4.2 Operaciones fundamentales Se dividen en operaciones unarias (aquellas que operan sobre 1 sola tabla) y operaciones binarias (aquellas que operan sobre 2 tablas). Las operaciones unarias son: Seleccin Proyeccin Renombramiento Las operaciones binarias son: Unin Diferencia Producto Cartesiano 4.3 Seleccin

Selecciona tuplas o filas que satisfacen un predicado. Se la denota con la letra y el predicado aparece como subndice. El predicado es una expresin lgica. Se utilizan operadores de comparacin y conectores lgicos. Ejemplos: CUENTA(codigo_cta, sucursal, saldo) Cod_cta Sucursal Saldo

230/2 Avellaneda 520.10 511/8 Balvanera 1380.25 345/1 Avellaneda 345.40 226/3 Balvanera 860.22

(CUENTA) saldo > 500 Cod_cta Sucursal Saldo

230/2 Avellaneda 520.10 511/8 Balvanera 1380.25 226/3 Balvanera 860.22

(CUENTA) saldo > 500 ^ sucursal=Avellaneda Cod_cta Sucursal Saldo

230/2 Avellaneda 520.10 4.4 Proyeccin Produce como resultado una nueva relacin con los atributos que se indican. Se eliminan las filas duplicadas (en una relacin no pueden existir uplas duplicadas, as como en un conjunto no pueden existir elementos repetidos). Se denota con la letra . Ejemplos: (CUENTA) sucursal

Sucursal Avellaneda Balvanera

( (CUENTA) ) cod_cta, saldo saldo > 500 Cod_cta Saldo

230/2 520.10 511/8 1380.25 226/3 860.22

4.5 Unin Produce como resultado una nueva relacin uniendo las tuplas de 2 relaciones y eliminando las duplicadas. Se denota como r U s. Se deben cumplir 2 condiciones:

1) r y s deben tener el mismo numero de atributos.

2) Los dominios deben ser iguales para cada atributo. Ejemplo: CLIE_LOC_1 Cuit Apellido 20-11111111-2 Perez 20-22222222-3 Lopez 20-33333333-6 Martinez 20-44444444-7 Garcia CLIE_LOC_2 Cuit Apellido 20-11111111-2 Perez 20-33333333-6 Martinez 20-55555555-8 Ramirez CLIE_LOC_1 U CLIE_LOC_2 Cuit Apellido 20-11111111-2 Perez 20-22222222-3 Lopez 20-33333333-6 Martinez 20-44444444-7 Garcia 20-55555555-8 Ramirez 4.6 Diferencia Dadas 2 relaciones, devuelve las uplas que estan en la primer relacion y no estan en la segunda relacion. Se denota como r - s Ejemplo: CLIE_LOC_1 - CLIE_LOC_2

Cuit Apellido 20-22222222-3 Lopez 20-44444444-7 Garcia 4.7 Producto cartesiano Dadas 2 relaciones r y s produce como resultado una nueva relacion con cantidad de atributos igual a la suma de los atributos de cada relacion y con filas que se obtienen de tomar cada fila de la relacion r y juntarla con cada fila de la relacion s. Se exige que las relaciones tengan nombres diferentes. Se denota como r X s Ejemplo: R1 R2 A B C D a1 b1 c1 d1 a1 b2 c2 d1 a2 b1 a2 b2 R1 X R2 A B C D a1 b1 c1 d1 a1 b1 c2 d1 a1 b2 c1 d1 a1 b2 c2 d1 a2 b1 c1 d1 a2 b1 c2 d1 a2 b2 c1 d1 a2 b2 c2 d1 4.8 Renombramiento Tiene 2 formas: 1. Renombrar relacion: (E) X devuelve como resultado la relacin E con el nombre X

2. Renombrar relacion y atributos: (E) X(A1,A2,...An) devuelve como resultado la relacin E con el nombre X y los atributos A1, A2,..,An Con este operador, se podria realizar el producto cartesiano de una relacion consigo misma (recordar que el producto cartesiano exige que las relaciones tengan nombres diferentes. Ejemplo: Dada la relacin Cuenta, seleccionar la o las cuentas de mayor saldo ( CUENTA ) X ( ( CUENTA ) ) cod_cta, saldo d cod_cta, saldo Cod_cta Saldo d.Cod_cta d.Saldo

230/2 520.10 230/2 520.10 230/2 520.10 511/8 1380.25 230/2 520.10 345/1 345.40 230/2 520.10 226/3 860.22 511/8 1380.25 230/2 520.10 511/8 1380.25 511/8 1380.25 511/8 1380.25 345/1 345.40 511/8 1380.25 226/3 860.22 345/1 345.40 230/2 520.10 345/1 345.40 511/8 1380.25 345/1 345.40 345/1 345.40 345/1 345.40 226/3 860.22 226/3 860.22 230/2 520.10 226/3 860.22 511/8 1380.25 226/3 860.22 345/1 345.40 226/3 860.22 226/3 860.22

Ejemplo: seleccionar de la tabla cuenta, el codigo de o de las cuentas de mayor saldo a) Seleccionamos primero las cuentas tales que existe una cuenta con saldo mayor

( ( CUENTA ) X ( ( CUENTA ) ) cuenta.saldo < d.saldo cod_cta, saldo d cod_cta, saldo Cod_cta Saldo d.Cod_cta d.Saldo

230/2 520.10 511/8 1380.25 230/2 520.10 226/3 860.22 345/1 345.40 230/2 520.10 345/1 345.40 511/8 1380.25 345/1 345.40 226/3 860.22 226/3 860.22 511/8 1380.25

( ( ( CUENTA ) X ( ( CUENTA ) ) ) cuenta.cod_cta cuenta.saldo < d.saldo cod_cta, saldo d cod_cta, saldo Cod_cta

230/2 345/1 226/3

Estas seran las cuentas que no pueden tener el mayor saldo, pues existe otra cuenta que tiene saldo mayor al saldo de la misma. Luego la o las cuentas de mayor saldo seran todas menos estas.

( CUENTA ) - cod_cta

( ( ( CUENTA ) X ( ( CUENTA ) ) ) cuenta.cod_cta cuenta.saldo < d.saldo cod_cta, saldo d cod_cta, saldo Cod_cta

511/8 4.9 Operadores no fundamentales Se utilizan para simplificar las consultas complejas, pero pueden expresarse como combinaciones de las operaciones fundamentales. 4.10 Interseccion

r s Produce como resultado una relacion con las tuplas que estan en r y no en s. Ejemplo:

CLIE_LOC_1 CLIE_LOC_2 Cuit Apellido 20-11111111-2 Perez 20-33333333-6 Martinez

Verificar que: r s = r - ( r - s )

4.11 Junta natural o reunion natural Combina un producto cartesiano con una seleccin en una sola operacin. Se denota como: r X s Realiza el producto cartesiano entre r y s, selecciona las filas que coinciden en los atributos comunes y elimina luego una ocurrencia de los atributos comunes. R1 R2 A B B C a1 b1 b1 c1 a2 b2 b3 c3 a3 b3 R1 X R2 A B C a1 b1 c1 a3 b3 c3 4.12 Division Se denota como: r s Como restriccion, se debe cumplir que los atributos de s deben estar incluidos en los atributos de r. Como resultado produce una relacion con los atributos que estan en r pero no en s y con las uplas de r que aparecen con todas las ocurrencias de s. Ejemplo: R1 R2 A B C B C a1 b1 c1 b1 c1 a1 b2 c2 b2 c2 a3 b1 c1 a4 b1 c1 a4 b2 c2 R1 R2 A a1 a4

Se puede escribir como: r s = ( r ) - ( ( ( r ) X s ) - r ) R-S R-S R-S Donde R-S denota a los atributos de r que no estn en s. 4.13 Asignacin Se permite asignar a una variable de relacion una expresion del Algebra Relacional para simplificar las consultas. Ejemplo: temp1 ( r ) R-S temp2 ( ( temp1 X s ) r ) R-S r s = temp1 - temp2

Capitulo 5 SQL DML Temas: 5.1 Historia de SQL 5.2 Componentes 5.3 Estructura bsica de una consulta 5.4 Clusula Select 5.5 Clusula Where 5.6 Clusula From 5.7 Renombramiento 5.8 Operaciones sobre cadenas 5.9 Clusula Order By 5.10 Operador Union 5.11 Funciones agregadas 5.12 Clusula Group By 5.13 Clusula Having 5.14 Valores nulos 5.15 Pertenencia a conjuntos 5.16 Comparacin de un valor en un conjunto de valores 5.17 Comprobacin de relaciones vacas 5.18 Operador Join

5.18.1 Inner Join 5.18.2 Outer Join 5.18.2.1 Left Outer Join 5.18.2.2 Right Outer Join 5.18.2.3 Full Outer Join 5.19 Modificacin de la Base de datos 5.19.1 Borrado 5.19.2 Insercin 5.19.3 Modificacin

5.1 Historia de SQL SQL es el lenguaje de consulta de mayor influencia, el mas implementado. Esta basado en el lgebra Relacional y el Calculo Relacional de Uplas. Fue definido inicialmente por D.D. Chamberlin en los aos 70 y se denomino SEQUEL (Struct English Query Languaje). Fue desarrollado con el prototipo de base de datos relacional de IBM, el System R. Desde entonces ha evolucionado y su nombre paso a ser SQL (Struct Query Languaje). En 1986, 2 organismos internacionales de normalizacin, ANSI (American National Standars Institute) e ISO (International Standards Organization) publicaron una norma de SQL que se denomino SQL-86. En 1987 IBM publica su propia norma que se denomino SAA-SQL. En 1989 se publico una norma extendida denominada SQL-89 y en 1992 se defini el ultimo estndar de SQL denominado SQL-92 o ANSI SQL-92 que actualmente contienen la mayora de los sistemas de los gestores de Base de Datos que trabajan con SQL. En este curso vamos a trabajar con Microsoft SQL 2000 que esta basado en dicha norma. Aunque se considera un lenguaje de consultas, tiene adems otras capacidades como la de definir la estructura de los datos y la actualizacin de los mismos. 5.2 Componentes El lenguaje esta compuesto por comandos, clusulas, operadores y funciones de agregado. Estos elementos se combinan en las instrucciones para crear, actualizar y manipular la Base de Datos. Existen 2 tipos de comandos: 1. Comandos del Lenguaje de Definicin de Datos o DDL (Data Defination Languaje): permiten

crear bases de datos, definir esquemas de relacin, crear ndices y definir vistas, seguridad, accesos, integridad y manejo de transacciones.

2. Comandos del Lenguaje de Manipulacin de Datos o DML (Data Manipulation Languaje):

permiten realizar consultas a la Base de Datos como as tambin actualizar los datos (insertar, borrar y modificar).

5.3 Estructura bsica de una consulta La estructura bsica de una consulta en SQL consiste en 3 clusulas: SELECT, FROM y WHERE. SELECT: corresponde a la operacin Proyeccin del lgebra Relacional. Se utiliza para dar la lista de los atributos que se quieren obtener en la consulta. tambin pueden ser utilizadas expresiones. FROM: indica la o las relaciones que intervienen en la consulta. Si hay mas de una relacin, se realiza el Producto Cartesiano entre las relaciones que intervengan. WHERE: corresponde al operador Seleccin del lgebra Relacional, es decir es un predicado que se aplica a las uplas de la relacin indicada en la clusula FROM o a las uplas del producto cartesiano si interviene mas de una relacin en la consulta. Una consulta tpica en SQL tiene la forma:

SELECT A1, A2, ... , An FROM R1, R2, ... , Rm WHERE p Donde A1, A2, ..., An son atributos, R1, R2, ..., Rm son relaciones y p es un predicado. La expresin anterior es equivalente a la siguiente expresin del lgebra Relacional:

( ( R1 X R2 X ... X Rm) ) A1, A2, ..., An p Se puede omitir la clusula WHERE, si se omite se asume Verdadero al predicado p. El resultado de una consulta en SQL es una nueva relacin, sin embargo, a diferencia del lgebra Relacional el resultado puede contener uplas repetidas. Utilizaremos el siguiente esquema del modelo Relacional para realizar consultas sobre el mismo: EMPLEADO(legajo, cuil, apellido, nombres, fecha_nac, fecha_ing, fecha_baja, tarea_id) TAREA(tarea_id, tarea_desc) SECRETARIA(legajo, velocidad_escritura) INGENIERO(legajo, tipo_ing) TECNICO(legajo, nivel) ASALARIADO(legajo, sueldo_mensual) CONTRATADO(legajo, valor_hora) 5.4 Clusula Select Como nombramos anteriormente, el resultado de una consulta en SQL es una nueva relacin. Por ejemplo: SELECT apellido FROM empleado Obtiene todos los legajos de la relacin empleado. En el resultado estaran los apellidos de cada una de las uplas de la relacin empleado. Si queremos eliminar los duplicados, se inserta la palabra clave Distinct despus de SELECT. Si no se utiliza la palabra clave Distinct se asume que no se eliminaran los duplicados (tambin puede ser indicado implcitamente con la palabra clave ALL). SELECT DISTINCT apellido FROM empleado Dara como resultado una relacin donde cada apellido aparecera una sola vez. SELECT ALL apellido FROM empleado Listara los nombres de empleados por cada upla que haya en la relacin empleado (equivalente al primer caso, es decir es el Default).

Se puede utilizar el * para indicar todos los campos de las relaciones que intervienen o bien el nombre de una relacin.* para indicar todos los campos pero solo de esa relacin. SELECT * FROM empleado Listara todos los atributos de la relacin empleado. SELECT empleado.*, tarea_desc FROM empleado, tarea WHERE empleado.tarea_id = tarea.tarea_id Produce como resultado una relacin con todos los campos de la relacin Empleado mas la descripcin de la tarea que cada empleado realiza. Si se quiere restringir la consulta a las primeras n uplas de la relacin resultante, se utiliza TOP n para indicar que se listen solo las primeras n uplas de la relacin resultante. SELECT TOP 10 * FROM empleado Listara las primeras 10 uplas de la relacin empleado. Se pueden utilizar expresiones aritmticas, alfanumricas o funciones aplicadas a los atributos de una relacin. SELECT legajo, sueldo_mensual, sueldo_mensual * 2 FROM asalariado tambin se pueden utilizar valores constantes, funciones o variables del sistema y si no se coloca la clusula FROM se obtiene una relacin con un solo atributo y 1 sola upla. SELECT 5*4 SELECT getdate() SELECT @@VERSION 5.5 Clusula WHERE En la misma se especifican predicados. Se utilizan conectores lgicos (and, or, not) y operadores de comparacin ( =, , = ). Ejemplo: SELECT legajo, apellido, nombres FROM empleado WHERE year(fecha_ing) = 2003 AND month(fecha_ing) = 2 Se puede utilizar el operador BETWEEN que devuelve verdadero cuando un valor se encuentra en un rango de valores.

Ejemplo: SELECT legajo FROM asalariado WHERE sueldo_mensual BETWEEN 1000 AND 2000 5.6 Clusula From Realiza un producto de las relaciones que intervienen. Para realizar una junta natural, es necesario igualar en el predicado los atributos comunes. Ejemplo: SELECT empleado.*, tarea_desc FROM empleado, tarea WHERE empleado.tarea_id = tarea.tarea_id Como en el lgebra Relacional se realiza el producto cartesiano y luego la seleccin de las uplas que cumplen con la condicin de junta, pero a diferencia del lgebra Relacin si se utiliza el * en el SELECT, no se eliminan instancias de los atributos comunes. Se pueden incluir otros operadores de comparacin que no sea el igual. 5.7 Renombramiento Se pueden renombrar tanto relaciones como atributos. Para renombrar atributos hay 3 expresiones equivalentes: 1. SELECT atributo as alias 2. SELECT atributo alias 3. SELECT alias=atributo Las 3 expresiones cambian en la relacin resultante el nombre del atributo por el alias. Ejemplo: SELECT legajo, Ingreso=fecha_ing, Baja=fecha_baja FROM empleado O bien SELECT legajo, fecha_ing as Ingreso, fecha_baja as Baja FROM empleado O bien SELECT legajo, fecha_ing Ingreso, fecha_baja Baja FROM empleado

Cabe aclarar que el renombramiento en los atributos es la ultima operacin que se realiza sobre los datos que se consultan, por ende no pueden utilizarse los alias dados a los atributos en las clusulas del comando SELECT. Por no seria valido: SELECT empleado.legajo as ap, sueldo_mensual FROM empleado, asalariado WHERE empleado.legajo = asalariado.legajo AND ap=Perez Para renombrar las relaciones que intervienen en una consulta, se utiliza el alias luego del nombre de la relacin o entre ambos se coloca la palabra reservada AS. SELECT E.legajo, apellido, nombres, sueldo_mensual FROM empleado AS E, asalariado AS Asa WHERE E.legajo=Asa.legajo El renombramiento de las relaciones que intervienen en la clusula FROM es especialmente til para comparar 2 filas de la misma relacin. Ejemplo: obtener los legajos de las asalariados que ganan mas que algn otro asalariado. SELECT DISTINCT A1.legajo FROM asalariado A1, asalariado A2 WHERE A1.sueldo_mensual > A2.sueldo_mensual 5.8 Operaciones sobre cadenas Para comparacin de cadenas de caracteres, se utiliza el operador LIKE con caracteres especiales para definir patrones. Dichos caracteres son: % : especifica cualquier subcadena sin limites en la cantidad de caracteres. _ : especifica cualquier carcter en dicha posicin (