FICHEROS Y BASES DE DATOS

TEMA 1 ASPECTOS BÁSICOS DE LOS FICHEROS

1.1 Jerarquía de memoria

Memoria Primaria

- La primera idea es almacenar la información en el medio más rápido posible, para asegurar

una rápida gestión.

- El coste de acceso a memoria primaria, o memoria RAM, es fijo y reducido.

- Pero la utilización de este tipo de memoria presenta diferentes problemas:

- Suele ser un medio bastante caro, por lo que se suele limitar su capacidad.

- La información se pierde al producirse un fallo de corriente eléctrica.

Memoria Secundaria

- Estas limitaciones aconsejan, la utilización de la memoria secundaria.

- Sus propiedades son las siguientes:

- Presenta un coste por byte mucho menor que la memoria RAM.

- Preserva su contenido al producirse un fallo de corriente eléctrica.

- Es bastante más lenta que la RAM y además el coste de acceso no es fijo.

Definición de Ficheros

- La información en memoria secundaria se almacena en ficheros, que se define como una

Colección de Información Relacionada.

- Debido al alto coste temporal del acceso a la memoria secundaria, se desea:

- Maximizar la información recuperada.

- Minimizar el número de accesos.

Manejo de Buffers

- Un buffer se define como un conjunto de bytes, que son leídos o escritos desde un

dispositivo de almacenamiento, en la memoria primaria.

- La utilización de esta técnica permite reducir el número de accesos a memoria secundaria.

1.2 Ficheros lógicos y ficheros físicos

- Desde un punto de vista físico, un fichero se define como un conjunto de bytes que se

almacenan en memoria secundaria.

- Desde el punto de vista de una aplicación, un fichero es su conexión con el mundo exterior,

posibilitándole el envío y la recepción de información.

-De este modo se definen el Fichero Físico y el Fichero Lógico.

- La conexión entre ambos es realizada por el sistema operativo.

1.3 Acceso a los datos situados en ficheros

Administrador de Ficheros

- El administrador de ficheros es la parte del sistema operativo que se encarga de la gestión de

los ficheros.

- Su primera tarea es comprobar que existe una conexión entre el fichero lógico y un fichero

físico determinado.

- Seguidamente se define en que parte del fichero se desea realizar la operación, y si esta se

encuentra en un buffer de memoria.

Procesador de Entrada/Salida

- El procesador de entrada/salida se encarga de controlar el tráfico de información desde y

hacia la memoria primaria.

Número de Buffers y Velocidad de Acceso

- El manejo de buffers por parte del administrador de ficheros permite reducir el número de

accesos a memoria secundaria.

- Pero una cuestión fundamental es el número de buffers a utilizar.

- En realidad se utilizan varios buffers que se manejan de modo indistinto para lecturas y

escrituras.

- Si todos los buffers están ocupados, se debe vaciar uno de ellos para posibilitar una lectura.

- Normalmente se utiliza el algoritmo LRU, es decir, se vacía el buffer menos recientemente

utilizado.

1.4 Coste de acceso a dispositivos de almacenamiento

Tipos de Dispositivos

- Según el modo en el que se accede a un dato dentro del medio de almacenamiento:

- Los Dispositivos de Acceso en Serie, como las cintas magnéticas.

- Los Dispositivos de Acceso Directo, como los discos magnéticos.

- Los primeros se utilizan para almacenar información que deba ser leída o escrita de modo

global.

- Mientras que los segundos se utilizan en el manejo de ficheros cuyo criterio de acceso es

más aleatorio.

1.4.1 Coste de acceso a discos

Organización de un Disco

- Un disco se presenta como un conjunto de Platos, cada uno de los cuales presenta al menos

una Superficie Magnética sobre la que se almacena información.

- Cada superficie se divide en Pistas, y éstas a su vez en Sectores.

- Las operaciones sobre la superficie se realiza a través del Cabezal de Lectura/Escritura.

- El movimiento del cabezal para alcanzar una pista concreta se denomina Desplazamiento.

- Cuando un disco presenta varios platos se denomina Paquete de Discos.

- La capacidad de los sectores suele ser constante en todo el disco, por lo que las pistas

interiores presentan mayor densidad de grabación.

- El acceso a un dato en disco, lee o escribe la información de un sector sobre un buffer.

Organización por Sectores

- Un usuario asume que los ficheros aparecen en sectores continuos dentro del disco.

- Pero no es así, ya que no es posible leer sectores contiguos, porque se requiere un cierto

tiempo para procesar la información inicialmente leída.

- Por tanto, si se almacenaran de este modo, sólo se podría leer un sector en cada giro.

- Para evitar este problema, se suelen intercalar los sectores lógicamente contiguos entre otros

sectores.

- Otra alternativa es el acceso consecutivo de un conjunto de sectores, denominado Cúmulo.

- La secuencia lógica de los cúmulos en el fichero aparece en la FAT.

- Para reducir el coste de acceso, es necesario minimizar el coste de los desplazamientos.

- Un registro puede aparecer en un único sector, lo que puede producir Fragmentación interna.

Organización por Bloques

- Las pistas de los discos también pueden estar organizados por bloques.

- Su tamaño puede ser definido por el usuario, y su valor puede ser fijo o variable.

- Un bloque puede descomponerse en una serie de subbloques:

- Subbloque Contador, que incluye el número de bytes del bloque asociado.

- Subbloque Clave, que incluye la clave del último registro del bloque.

- Subbloque de Datos, en el que aparece la información.

Overhead de las Organizaciones

- Tanto los sectores como los bloques produce cierto overhead de almacenamiento, que

reduce la capacidad del disco.

- Parte de este overhead se produce cuando se formatea el disco.

- En las organizaciones por sectores, debe de incluir en cada sector la siguiente información:

- Dirección del Sector y de la Pista.

- Estado del Sector, útil o dañado.

- Espacios y Marcas de Sincronización.

- El usuario no tiene la posibilidad de manejar esta información. En las organizaciones por

bloques, parte de esta información sí puede ser definida por el programador.

Cálculo del Coste de Acceso a un Disco

- El coste del acceso a un disco se calcula a partir de la suma de tres valores:

- Tiempo de Desplazamiento, para situar el cabezal sobre el cilindro adecuado.

Se obtiene como suma del Tiempo Inicial de Arranque del Cabezal, s, y el producto

del coste de atravesar un cilindro, m, y el número de cilindros a atravesar, n.

f(n) = s + m*n

- Retraso por Rotación, que incluye el tiempo necesario para situar el cabezal en la

pista. Depende de la velocidad de giro del disco y de la posición del cabezal.

- Tiempo de Transferencia, en el que se realiza de modo efectivo la operación.

Depende del número de bytes a transmitir y de la velocidad de giro.

Tiempo Transferencia = (n� bytes a transmitir / n� bytes en la pista) * Tiempo Rotación

1.4.2 Coste de Acceso a Cintas

Organización de las Cintas

- Una cinta suele estar compuesta por una serie de pistas paralelas.

- Los datos se agrupan en bloques cuyo tamaño es variable.

- Una cinta se caracteriza por los parámetros:

- Densidad de la Cinta, medido en número de bits por pulgada.

- Velocidad de la Cinta, medido en pulgadas por segundo.

- Tamaño del Hueco entre Bloques.

Cálculo del Tamaño de una Cinta

- Para calcular el tamaño necesario de la cinta para almacenar una información se considera:

- La longitud Física de un Bloque de Datos.

b = (Tamaño del Bloque) / (Densidad de la Cinta)

- La longitud de un hueco entre bloques, g.

- El número de Bloque, n.

s = n * (b+g)

Cálculo del Acceso a una Cinta

- El Coste Nominal de Transmisión de Datos se define como:

Densidad de Cinta (bpi) * Velocidad de Cinta (ips)

- Pero no se tiene en cuenta el espacio ocupado por los huecos entre bloques, para ello es

necesario definir la densidad de grabado efectivo,

Número de Bytes por Bloque / Número pulgadas necesarias para almacenar bloque

TEMA 2 ESTRUCTURA DE UN FICHERO

2.1 Introducción

- Los bytes que constituyen el fichero aparecen agrupados para formar unidades de inform.

- En un fichero aparecen un conjunto de entidades caracterizadas por una serie de atributos.

- Las entidades se asocian a Registros, y los atributos a Campos.

- La cuestión se centra en como se puede localizar un determinado atributo de una entidad

dentro del fichero.

- Una alternativa es conocer de antemano la posición de inicio de cada una de las informac.

- Otra posibilidad es marcar de algún modo el principio y el fin de cada información.

2.2 Organización: Campos y Registros

Definición y Tipos de Campos

- Campo: menor unidad de información con significado lógico en un fichero.

- Alternativas para localizar los campos en un fichero:

1�) Campos de Tamaño Fijo.

- Cada campo ocupa en disco el mismo número de bytes. Para datos con longitud muy

variable, puede producir un derroche, bastante importante, de la capacidad del disco.

2�) Comenzar un Campo con un indicador de longitud.

Este indicador incluye el número de bytes del dato incluido en el campo.

3�) Colocar un delimitador al final del campo.

Se elige un carácter especial que se escribe a continuación de los bytes del campo.

Definición y Tipos de Registros

- Registro: conjunto de campos que permanecen juntos cuando se observa el fichero con un

mayor nivel de abstracción.

- Para poder agrupar los campos de un registro, resulta necesario determinar los límites de un

registro, apareciendo diferentes opciones:

1�) Registros de tamaño fijo, a nivel de bytes.

Los campos de longitud fija se suelen reunir para formar registros de tamaño fijo.

2�) Registros de tamaño fijo, a nivel de campos.

3�) Comenzar cada registro con un indicador de longitud.

4�) Definir un fichero índice.

Se utiliza un fichero índice cuyos registros indican el byte de inicio de los registros del

fichero original.

5�) Colocar un delimitador al final de los registros.

Elección de la Estructura

- Existen diferentes aspectos que influyen en la elección de la estructura de un fichero: el

lenguaje de programación, el tipo de operaciones que se implemente sobre el fichero.

2.3 Acceso a la Información

Modos de Acceso

- La recuperación de la información puede ser de dos tipos:

- Global, que recupera toda la información.

- Selectiva, en donde se desea recuperar una parte de la información del fichero.

- Mediante la utilización de la primera opción, el coste de los dos tipos de recuperación es

equivalente, O(n).

- La segunda opción debe conocer la posición de un registro en el fichero.

- La recuperación selectiva con esta opción requiere el manejo de registros de tamaño fijo,

obteniendo un coste O(1).

Definición de Agrupamientos

- El agrupamiento pretende almacenar lo más próximamente posible los registros que, de

modo habitual, se acceden conjuntamente.

- El agrupamiento se puede realizar dentro de un fichero o entre ficheros

2.4 Actualización de la Información

- Cuando se realizan diferentes operaciones de eliminación e inserción de información, puede

aparecer espacio no utilizado en el fichero.

Compactado de la Información

- Esta opción es la más sencilla, siendo útil tanto para registros de tamaño fijo como variable.

- Puede no ser una solución eficiente para fichero con un alto grado de actualización.

Lista de Registros Disponibles

- El borrado de registros debe de asegurar que el registro quede perfectamente marcado

(elegir un carácter que se escriba al principio del registro) y que se puedan reutilizar estos

registros, lo que se puede realizar de diferentes formas:

- Acceso Secuencial al fichero (coste alto, no se suele utilizar).

- Enlazar los registros borrados mediante una Lista.

Lista en Registros de Longitud Fija

- El carácter que marca el registro como borrado, aparece al principio del registro.

- En este tipo de registros, la lista se forma a partir del número relativo de registro, grabado a

continuación del carácter de borrado.

Lista en Registros de Longitud Variable

- La lista debe de contener el tamaño de cada uno de los registros que la componen.

- El carácter de borrado aparece como primer carácter del primer campo del registro, es decir,

a continuación del tamaño del registro.

- El enlace entre los registros de la lista se realiza mediante la utilización de la posición física

de los registros.

- Dicha información aparece a continuación del carácter de borrado.

Fragmentación Interna y Externa

- La Fragmentación se define como el espacio asignado a un fichero en memoria secundaria

que no puede ser utilizado para almacenar información.

- La fragmentación puede ser de dos tipos:

Interna, si el espacio aparece asignado a un registro.

Externa, si el espacio aparece entre el asignado a dos registros.

- El primer tipo aparece cuando se utilizan registros de longitud fija para almacenar datos de

tamaño variable.

Reducción de la Fragmentación Externa

- La solución más sencilla es la Compactación de los ficheros, aunque es una solución muy

costosa.

- La solución más interesante es la utilización de Estrategias de Colocación que seleccionen el

Hueco más adecuado en la lista.

Estrategias de Colocación

- La estrategia más sencilla es la del Primer Ajuste, que toma el primer espacio en el que

quepa el nuevo registro, aunque no resuelve la problemática de la fragmentación externa.

- Una solución es ordenar los espacios en orden de tamaño ascendente, de modo que en la

búsqueda se obtenga el espacio de tamaño más similar.

- Esta estrategia del Mejor Ajuste, puede tener un coste de inserción y borrado de la lista muy

alto, y además los espacios libres pueden ser demasiado pequeños para su reutilización.

- La ordenación descendiente reduce el coste del borrado, y además el tamaño del espacio

�libre resultante puede ser reutilizado.

- Esta opción da lugar a la estrategia del Peor Ajuste.

Conclusiones

- Si la frecuencia de las operaciones de actualización es baja, la estrategia del primer ajuste es

suficiente.

- Cuando el problema se relaciona con la fragmentación interna, no debe ser utilizada la

estrategia del peor ajuste.

- Si aparece un problema de fragmentación externa, no debe utilizarse la estrategia del mejor

ajuste.

TEMA 3 ESTRUCTURAS DE ALMACENAMIENTO BÁSICAS

3.1 Búsqueda de Información

Definición de Clave

- Normalmente se desea acceder a los registros que contienen cierta información en un campo

- Este método de búsqueda de información se denomina Acceso por Clave.

- Los valores en este campo deben de cumplir una serie de normas de almacenamiento que

aseguren su localización, tales como:

- Las cadenas de caracteres deben estar en mayúsculas, y sólo debe aparecer un

� espacio en blanco entre palabras.

- No deben aparecer espacios en blanco ni en los campos numéricos ni en los de fecha.

- En estos casos se dice que la clave aparece en Forma Canónica.

Búsqueda Secuencial y Búsqueda Binaria

- El método de acceso más sencillo es la búsqueda secuencial, pero su coste es O(n).

- Un método alternativo es la Búsqueda Binaria, cuyo coste es O(log n).

- Este método requiere que los registros sean de tamaño fijo y que estén ordenados por el

valor del campo clave asociado al proceso de búsqueda.

Ordenación de un Fichero

- La idea principal va a ser leer completa, o parcialmente, todos los registros, y

posteriormente realizar la ordenación en memoria RAM.

Ordenación en Memoria

- La primera idea es leer todos los registros en un vector de cadena de caracteres que se puede

ordenar en memoria.

- Pero el orden de este vector de cadenas puede ser diferente al definido por la clave.

- Para evitar este problema, se crea un segundo vector de caracteres, el índice, en el que

aparece la clave de los registros y un puntero a la posición del registro en el anterior vector.

- Es posible reducir el coste si se define un tercer vector que contiene únicamente los

punteros antes mencionados.

Conclusiones

- La ordenación en memoria sólo es útil cuando el fichero es lo suficientemente pequeño

como para poder almacenarse en memoria.

- Todos estos hechos aconsejan definir una técnica que:

- Reduzca el coste de acceso, a uno o dos accesos a disco, para cualquier clave.

- La búsqueda de información no requiera ordenar los registros del fichero.

- Las operaciones de actualización se realicen de modo eficiente.

3.2 Definición y Manejo de índices

Concepto de Fichero índice

- Los Ficheros índices se definen como un fichero cuyos registros son de tamaño fijo, en el

que se almacena la clave del registro y un puntero a este registro.

- Su utilización presenta una serie de ventajas:

- Permite el uso de la búsqueda binaria tanto para ficheros de registros de tamaño fijo

como para los de tamaño variable.

- El proceso de ordenación se restringe al fichero índice.

- Es posible definir diferentes ficheros índice, cada uno de los cuales se asocia a una

clave de búsqueda.

- Pero también presenta inconvenientes:

- Las operaciones de actualización requieren la actualización de más de un fichero.

- El orden establecido en los ficheros índices debe de mantenerse.

- Si el fichero índice es demasiado grande para almacenarse en memoria, estas

operaciones pueden ser muy costosas.

Tipos de índices

- Una primera clasificación es la siguiente:

- índice Denso, si contiene una referencia a todos los registros del fichero.

- índice no Denso, si sólo contiene referencia a un subconjunto de registros.

- Otra posible clasificación es la siguiente:

- índice Primario, si contiene la clave primaria del fichero.

- índice Secundario, si contiene otra clave.

Control contra Fallos del Sistema

- Si no se produjera la actualización del índice por una fallo del sistema, este no reflejaría el

estado real del fichero y por tanto debería de reestablecerse.

- Para detectar esta posibilidad, en el registro de cabecera del fichero índice se introduce una

bandera que indique esta situación:

- La lectura del fichero, debería marcar el fichero como leído y no escrito.

- Por su parte, la escritura debería modificar el valor de esta bandera.

- La lectura debería controlar el estado de esta bandera, reconstruyendo el fichero índice si

ésta indicara que ha sido leído y no reescrito.

3.3 índices Multinivel. Arboles B y B+

índices Multinivel

- Cuando un fichero índice es demasiado grande para almacenarse en memoria RAM, su

gestión puede resultar muy costosa.

- Estos problemas también surgen si no es posible almacenar en memoria todos los ficheros

índice de un fichero.

- La solución a estos problemas es la definición de un índice no denso sobre el fichero índice

en cuestión.

- De este modo se define un índice multinivel, compuesto por un conjunto de índices no

densos que actúan sobre un índice que puede ser denso o no denso.

Propiedades de los Arboles B

- Se define el orden de un árbol B como el número máximo de hijos de una página.

- Por su parte la hoja de un árbol B como el nivel más bajo de la estructura.

- Así un árbol B de orden m cumple que:

- Una página puede referenciar m páginas hijo como máximo.

- Toda página, excepto la raíz y las hojas tienen al menos m/2 hijos.

- La raíz tiene por lo menos dos páginas hijo.

- Todas las hojas aparecen en el mismo nivel.

- Una página, que no es una hoja y que tiene k hijos, contiene k-1 claves.

- Una página hoja contiene al menos (m/2)-1 claves y no más de m-1 claves.

Operaciones sobre Arboles B

- Inserción: siempre se intenta insertar en una página hoja.

- Si esta se encuentra completa, se elige una clave que divida el nuevo conjunto de claves en dos subconjuntos equilibrados.

- Los dos subconjuntos se almacenan en dos páginas, mientras que la clave elegida se inserta en el nivel superior, en donde se puede repetir el proceso.

- Borrado:

- Siempre se deben eliminar claves situadas en una página hoja.

- Si se desea eliminar una clave que no esté en una página hoja, se intercambia con la

clave siguiente, que está en una hoja y luego se elimina.

- Cuando una página hoja queda con un número de claves menor que el mínimo, hay que examinar sus páginas hermanas. Si una página hermana tiene más del número mínimo de claves, se deben redistribuir sus claves con la página actual.

En caso contrario, se concatena la página actual, una página hermana y la clave que las separa, repitiéndose el proceso.

Tipos de Arboles B

- Un árbol B* intenta mejorar el llenado de las páginas del árbol.

- La redistribución se incluye en la inserción, tal que si es posible se distribuyen las claves entre páginas hermanas y si no se divide.

- Así, la división involucra dos páginas llenas dando lugar a tres nuevas páginas. Una página tiene al menos (2m-1)/3 hijos. Una página hoja tiene al menos [(2m-1)/3]

claves.

- Por su parte el árbol B+ pretende el manejo de los datos de modo secuencial y directo. Los

datos aparecen en bloques enlazados, denominados Conjunto Secuencia.

Arbol B � desperdicio máximo por página = m/2

Arbol B* � desperdicio máximo por página = m/3

TEMA 4 TÉCNICAS DE DISPERSIóN

4.1 Introducción

Concepto de Dispersión

- La Dispersión permite definir la posición que ocupará un registro en el fichero, mediante la

aplicación de una función de dispersión sobre la clave de acceso.

- Esta posición se utiliza en las operaciones de inserción y borrado, por lo que el número de

accesos se reduce a uno.

- Un registro puede almacenarse en cualquier posición dentro del fichero, según la función de

dispersión que se utilice. Por esta razón, esta opción sólo se puede utilizar en ficheros con

registros de tamaño fijo.

Colisiones

- El problema se presenta cuando más de un registro se asocia a la misma posición.

- Las claves que se asocian a la misma posición se les denomina Sinónimos.

- La aparición de colisiones puede aumentar el número de accesos requerido para acceder a

un registro determinado.

- Para reducir el problema se puede:

- Utilizar una función de dispersión perfecta, que reduzca al máximo su número.

- Definir variantes que reduzcan el número de colisiones que pueden aparecer.

- La primera opción es demasiado costosa, por lo tanto utilizaremos diferentes variantes de

esta técnica, las más comunes son:

- Definir una función de dispersión que realice una distribución adecuada de los regs.

- Aumentar el tamaño del fichero para reducir la posibilidad de aparición de colisiones

- Almacenar más de un registro en la misma posición, que referenciará a una página.

4.2 Funciones de Dispersión

Clasificación y Análisis

- Las funciones de dispersión se pueden clasificar a partir de la probabilidad de asignación de

un registro en una dirección como,

- Uniforme, en la que los registros aparecen uniformemente distribuidos en el fichero.

- Aleatoria, si un determinado registro puede ser asignado a cualquier dirección.

- La primera clase no suele ser viable, mientras que no existe ningún tipo de control sobre la

segunda. Es por esto, que se estudian alternativas para mejorar su comportamiento:

- Buscar un patrón en la clave.

- Particionar la clave que luego se suman.

- Dividir la clave por un número.

4.3 Saturación Progresiva

Definición

- Una de las opciones más simples para resolver la aparición de una colisión en una dirección,

es elegir el primer hueco no ocupado que se encuentre a continuación de aquel.

- Si se alcanza el final del fichero en este proceso, se debe continuar con la primera dirección

del fichero. Esta técnica se denomina Verificación Lineal o Saturación Progresiva.

Búsqueda de información

- Se inicia en la dirección asociada a la clave, si el registro buscado aparece en el fichero, está

operación finaliza cuando se encuentra el registro con la clave seleccionada. En caso

contrario, el proceso finaliza cuando se produce una de las siguientes situaciones:

- Aparece un hueco no ocupado.

- Se alcanza la dirección inicial.

Eliminación de Registros

- En la eliminación de un registro de la estructura se debe de considerar que,

- El registro pueda ser reutilizado.

- El borrado no impida la localización de un registro.

- La primera condición se consigue marcando el hueco asociado como vacío.

- Para la segunda condición se debe de marcar de marcar de un modo especial. Esta marca

indicará al proceso de búsqueda de un registro que el hueco correspondiente estuvo

ocupado.

4.4 Empaquetado de Registros

Frecuencia de Colisiones

- La Densidad de Registros en un fichero se define como el cociente entre el número de

registros almacenados y el número de registros que caven en un fichero.

- La probabilidad de aparición de x registros asociados a una dirección en un fichero con una

capacidad de N huecos y con r registros, se define por la función de Poisson,

- Siendo n la capacidad en registros del fichero, el número de colisiones se calcula como:

num_colis =

- Siendo b el número de registros en un hueco, la relación entre el número de huecos y el

número de registros almacenados se define: n = bN

- Para un mismo valor de densidad, el número de colisiones disminuye cuando crece b,

4.5 Otras Técnicas de Dispersión de Colisiones

- En la Doble Dispersión , si aparece una colisión se aplica una segunda función de

dispersión. En este sistema los sinónimos pueden estar muy separados, aumentando su coste

de acceso.

- La Saturación Progresiva Enlazada forma una lista con los sinónimos, reduciendo el coste de

acceso a éstos, pero con inconvenientes:

- Cada registro debe de poseer un campo en el que se almacene una dirección.

- Toda dirección debe contener un registro con esa dirección.

- Para resolver los problemas se puede enlazar con un Área de Saturación Separada.

- Por su parte las Tablas de Dispersión se aplican sobre índices, lo que permite manejar

registros de tamaño variable.

4.6 Dispersión Extensible

Planteamiento

- Cuando no se conoce el tamaño del fichero y se desea eliminar la influencia de las

colisiones es necesario modificar estas técnicas.

- Como en el caso de los índices, la solución se basa en la utilización de un árbol binario.

- Las hojas del árbol aparecen en un vector, el Directorio, y referencian a una página.

- El directorio se puede almacenar en memoria, reduciendo a uno el número de accesos.

TEMA 5 SISTEMAS DE BASES DE DATOS FRENTE A SISTEMAS DE

FICHEROS

5.2 Problemas de los Sistemas de Ficheros

- La información redundante ocupa espacio en disco, que podría eliminarse centralizando la

información.

- Pueden aparecer problemas de integridad de los Datos:

• A nivel físico. Valor en diferentes ficheros son diferentes.

• A nivel lógico. No existe algún dato que se referencia desde otro fichero.

- La Consistencia de los Datos, es decir que los datos se almacenan siempre en el mismo

formato, puede no estar asegurada.

- Debido al procesamiento por lotes, los datos consultados pueden no ser reales.

- El procesamiento por bloques también puede requerir la reorganización física de los

ficheros.

5.3 Sistemas de Bases de Datos

Características básicas de los SBD

- Surgen para resolver los problemas de los SF.

- Desde el punto de vista lógico (programas y usuarios), los datos y la definición de sus

relaciones se almacenan en un único lugar, que es común.

- Físicamente, los datos se almacenan en uno o varios ficheros.

- El acceso de los datos se realiza, a través del sistema de gestión de bases de datos (SGBD),

mediante sentencias específicas que pueden incluirse dentro de lenguajes de alto nivel.

Visiones de la Base de Datos

- Física. Muestra el modo real en el que los datos se almacenan en ficheros. útil para

programadores de sistemas y creadores del SGBD.

- Subesquema o Vista. Visión lógica de los datos relacionados con una aplicación. útil para

programadores de aplicaciones y usuarios finales.

- Esquema. Indica la visión lógica global de la BD. útil para el diseñado del sistema y el

administrador del sistema.

Funciones del SGBD

- Aceptar definiciones de esquemas y vistas.

- Manipular los datos siguiendo las órdenes de los usuarios.

- Cuidar que se respete la seguridad e integridad de los datos.

- Controlar la concurrencia y las operaciones asociadas a la recuperación de los fallos.

- Proporcionar un diccionario de datos que contenga los esquemas. Información de los

usuarios, ...

5.4 Ventajas de los Sistemas de Bases de Datos

Datos Compartidos

- Aparecen menos datos redundantes:

. Se ocupa menos espacio en disco.

. La integridad física de los datos se reduce.

5.5 Inconvenientes de los Sistemas de Bases de Datos

Comparación con SF

- Son más caros a nivel de hardware y software.

- Su diseño requiere una fase de planificación, realizada por especialistas, que resulta muy

costosa.

- La vulnerabilidad de los SBD es mayor, ya que el fallo en cualquier fichero produce el fallo

en todo el sistema.

TEMA 6 EL DISEÑO DE LAS BASES DE DATOS

6.1 Fases del Diseño de Bases de Datos

Elementos del Ciclo de Vida

- Estudio de la Viabilidad.

Determina la rentabilidad de las diferentes alternativas y las prioridades de los elementos

del sistema.

- Recogida y Análisis de Requerimientos

Permite comprender la misión del sistema, mediante la interacción con los usuarios, dando

lugar a los Requerimientos del Sistema.

- Diseño

Se especifica la estructura del sistema, diferenciando el Diseño de la Base de Datos y el

Diseño de las Aplicaciones.

- Creación de Prototipos

Mediante la utilización de herramientas, se define una Realización Simplificada del Sistema.

Permite verificar si el diseño se ha realizado correctamente, así como la opinión del usuario

sobre éste.

- Implantación

Se implementa la versión final del sistema, analizando la mejor alternativa que asegure un

rendimiento óptimo.

- Validación y Prueba

Garantiza que las fases del desarrollo se han realizado correctamente, verificando que la

aplicación cumple los requerimientos.

- Operación

Se inicia con la carga inicial de los datos y acaba cuando el sistema se convierte en obsoleto.

6.2 Diseño Conceptual

Objetivos

- Describir el Contenido de la Información de la Base de Datos.

- Esta descripción debe ser independiente del modo en el que se almacene la información.

Características

- A partir de los Requerimientos obtiene el denominado Esquema Conceptual (EC).

- El EC es una descripción de alto nivel de la estructura de la Base de Datos.

- El Modelo Conceptual (MC) es un lenguaje utilizado en la descripción de los EC.

6.3 Diseño Lógico

Objetivos

- Describir el Contenido de la Información de la Base de Datos.

- Esta descripción puede ser procesada por el software del tipo de SGBD a utilizar.

Características

- A partir del Esquema Conceptual obtiene el denominado Esquema Lógico (EL).

- El Modelo Lógico (ML) es un lenguaje utilizado para especificar Esquemas Lógicos.

6.4 Diseño Físico

Objetivos

- Describir el Contenido de la Información de la Base de Datos.

- Esta descripción sólo puede ser procesada por un SGBD específico.

Características

- A partir del Esquema Lógico obtiene el denominado Esquema Físico (EF).

- El EF describe las estructuras a utilizar para almacenar los datos y los métodos usados para

acceder a ellos.

- Las decisiones tomadas es esta fase, que permiten mejorar el rendimiento de la BD, puede

modificar el esquema lógico.

- Es decir, existe una retroalimentación entre el diseño lógico y el diseño físico.

Análisis Funcional

- Genera el Esquema Funcional mediante el llamado Modelo de Funciones.

- Descripción de alto nivel de las tareas a realizar , así como del flujo de información

asociado.

6.5 Interacción entre el Diseño de Bases de Datos y el Análisis Funcional

Características

- Una metodología conjunta debe de considerar que:

- Los datos necesarios para las funciones aparezcan en el esquema conceptual.

- Las funciones requeridas por los datos se definan en el esquema funcional.

TEMA 7 MODELOS DE BASES DE DATOS

7.1 Introducción

Modelos de Datos y Esquemas

- Los Modelos de Datos (MD) son herramientas que permiten describir la realidad.

- Los programadores los utilizan para construir Esquemas, que son representaciones de la

realidad.

Clases de Modelos de Datos

- Existen dos tipos de MD:

- Modelo Conceptual que representa la realidad en un alto nivel de abstracción.

- Modelo Lógico, o Modelo de Base de Datos, que describen las relaciones lógicas

entre los datos y la base de datos.

- El primero genera el Esquema Conceptual y el segundo el Esquema Lógico.

Sistemas Prerrelacionales

- Modelo Jerárquico.

Los datos se relacionan de modo jerárquico, y se representa mediante una estructura en

árbol.

- Modelo de Red.

Se entiende como una generalización del modelo jerárquico, en donde los nodos hijo pueden

tener varios nodos padre.

Sistemas Relacionales

- Modelo Relacional.

Se utilizan conceptos matemáticos, como las relaciones, para representar los datos y las

operaciones sobre estos.

Sistemas Postrrelacionales

- Modelo Orientado a Objetos.

Los datos se representan mediante objetos, que contienen variables y métodos, y su

manipulación se realiza mediante mensajes.

- Modelo Semántico.

Tienen como objetivo describir de un modo más preciso la información contenida en la base

de datos.

- Modelo Deductivo.

Son capaces de deducir hechos a partir de las relaciones base y una serie de axiomas

deductivas o reglas de inferencia.

7.2 Modelo Jerárquico

Estructura Jerárquica

- Una Base de Datos Jerárquica se compone de un Conjunto Ordenado de Árboles.

- El orden global de la base de datos se obtiene mediante el recorrido en Preorden del bosque.

Diagramas de Ocurrencias (DO)

- Cada uno de los rectángulos representa la instancia de un tipo de registro.

- Los arcos definen la relación existente entre las instancias de dos niveles contiguos del

árbol.

- No se suelen especificar los campos de los registros.

- Cuando la información almacenada en la base de datos es muy grande, se convierte en

inmanejable.

Diagrama de Bachman (DA)

- Describe gráficamente el esquema lógico de una base de datos jerárquica.

- Los rectángulos representan los tipos de registro.

- Los arcos representan la relación existente entre los tipos de registro.

- Los arcos se etiquetan porque puede existir más de una relación entre dos tipos de registro

(no en el modelo jerárquico).

- La flecha simple-doble indica que existe un único padre para cada hijo, pero pueden existir

cero o más hijos de un padre.

Problemas de las BD Jerárquicas

- únicamente pueden representar relaciones de 1-a-Muchos.

- Las relaciones Muchos-a-Muchos requieren la redundancia de información.

- Si un registro tipo aparece como "hijo" en más de dos relaciones, se debe de replicar.

- Esto puede producir problemas de Integridad y Consistencia de los Datos.

- Los lenguajes de manipulación asociados son fuertemente navegacionales.

- Hace falta un Lenguaje de Programación Anfitrión en el que se inserten los operadores.

7.3 Modelo de Red

Estructura de Red

- El Modelo de Red se puede entender como una extensión del modelo jerárquico.

- También se presenta mediante un árbol, pero en este caso, cada hijo puede tener varios

padres.

- De este modo se reducen, o eliminan, las redundancias.

- Pero desaparece la herencia de los campos.

Tipos de Redes

- Se dice que la Red es Simple si los padres de un hijo son instancias de registros tipo

diferentes.

- Se dice que la Red es Compleja si los padres pueden ser instancias del mismo registros tipo.

Conversión Compleja-Simple

- Permite reducir el problema de la pérdida de información asociado a las redes complejas.

- La idea es convertir una relación muchos-a-muchos en dos relaciones uno-a-muchos,

mediante la inserción de un nuevo tipo de registro.

- Este registro se denomina Registro Intersección si contiene algún tipo de información, que

se denomina Datos de la Intersección.

- En otro caso, se denomina Registro de Enlace.

Ciclos y Lazos

- Existen dos tipos de relaciones específicas, los Ciclos y los Lazos.

- En un ciclo, diferentes tipos de registros se relacionan de modo circular.

- Los lazos representan la relación de un tipo de registro consigo mismo.

- Los lazos sólo pueden manejarse en redes complejas.

Problemas Asociados

- Los lenguajes de manipulación asociados son fuertemente navegacionales.

- Hace falta un lenguaje de programación Anfitrión en el que se inserten los operadores.

- Especialmente complicada en redes complejas.

7.4 Modelo Relacional

Estructura Relacional

- La estructura de datos básicos es la Relación, denominada normalmente como Tabla.

- Una base de datos relacional se compone de una colección de relaciones.

- Cuando una tabla contiene datos se dice que es una instancia de la relación.

- Cada relación se asocia a una entidad, y se compone de una serie de atributos.

- Las filas de la tabla definen las instancias de la entidad, y son las Tuplas de la Relación.

- No se permiten tuplas duplicadas en una tabla, aunque los SGBD no suelen controlarlo.

- Las columnas de la tabla son las ocurrencias de los atributos de la entidad.

- Con cada atributo se asocia un Dominio que define el posible rango de valores.

7.5 Otros Modelos

Modelos Clásicos

- Los modelos clásicos presentan una serie de características comunes:

- Uniformidad. Un gran cantidad de datos se estructuran de modo similar.

- Orientación en Registros. Los datos básicos se almacenan en registros de longitud fija.

- Datos Pequeños. Los registros son cortos, normalmente de pocos cientos de bytes.

- Campos Atómicos. Los campos de los registros son cortos, de longitud fija y no poseen

ningún tipo de estructura interna.

- Transacciones Cortas. En las transacciones no tienen interacción con el usuario y además su

duración es de alguna fracción de segundo.

- Esquema Casi Estático. No suelen realizarse cambios en los esquemas, y si aparecen son de

poca importancia.

TEMA 8 ESTRUCTURA DE DATOS RELACIONAL

8.1 Ejemplo Introductorio

Definiciones

- Relación (Tabla). Elemento básico del modelo relacional, que se asocia a una entidad.

- Tupla (Fila o Registro). Cada una de las instancias de una entidad.

- Cardinalidad (Número de Filas). Número de instancias de una entidad en una relación.

- Atributo (Campo o Columna). Cada una de las propiedades que caracterizan una entidad.

- Grado (Número de Columnas). Número de atributos asociados a una entidad.

- Clave Primaria (Identificador único). Conjunto de uno o más atributos que identifican de

modo completo una instancia de una entidad.

- Dominio (Conjunto de Valores Legales). Define la colección de valores de donde uno o más

atributos obtienen sus valores reales.

8.2 Dominios

Definiciones

- Un escalar es la menor unidad semántica de información, es decir, es un dato atómico.

- Se define un Dominio, o Dominio Simple, como un conjunto de escalares.

Terminología

- Es aconsejable que el nombre de los dominios y de los atributos coincidan, siempre y

cuando no exista ambigüedad.

Dominios Compuestos

- Un dominio compuesto es una combinación de dominios simples.

Interpretación de los Dominios

- Desde un punto de vista intuitivo, un dominio es equivalente a un tipo de datos.

- De este modo, se define atributos (variables) que pertenezcan a un dominio (tipo de datos).

8.3 Relaciones

Definiciones

- Una Relación sobre un conjunto de dominios se compone de dos partes, la Cabecera y el

Cuerpo.

- La Cabecera, o Esquema de la Relación, se compone de un conjunto fijo de pares atributo

dominio.

- El Cuerpo, o Extensión de la Relación, está formado por un conjunto Tuplas.

Interpretación de las Tablas

- Existe un dominio subyacente asociado a cada columna de la tabla.

- Las dos partes de la tabla corresponden a las dos partes de la relación.

- Las filas se forman de pares atributo-valor.

Propiedades

- No existen tuplas repetidas.

En una relación aparece un conjunto de tuplas, y por lo anterior, no pueden haber dos tuplas

iguales.

En una tabla si pueden haber filas repetidas.

- Las tuplas no están ordenadas.

- Los atributos no están ordenados.

- Los valores de los atributos son atómicos.

Una relación que cumple esta cuarta propiedad se dice que está normalizada.

TEMA 9 REGLAS DE INTEGRIDAD

9.2 Claves Primarias

Definición

- Una Superclave es un conjunto de atributos que identifican de modo único las tuplas de una

relación.

- Una Clave Candidata es el menor subconjunto de atributos de una superclave que sigue

siendo un identificador único.

- En una relación pueden existir diferentes claves candidatas que se compongan de un número

diferente de atributos.

- De todas las claves candidatas se elige una que será la Clave Primaria.

- El resto de claves candidatas se definen como Claves Alternativas.

Propiedades

- Por lo anterior, existen dos propiedades básicas asociadas a una clave candidata:

- Unicidad: no existen dos tuplas que posean el mismo valor de la clave candidata.

- Minimalidad: no se puede eliminar ningún atributo de la clave candidata sin destruir la

unicidad de la clave candidata.

9.3 Regla de Integridad de Entidades

Definición

- Ningún Componente de la Clave Primaria de una Relación Base puede aceptar Nulos.

- En el modelo relacional Nulo se refiere a ausencia de valor.

- En SQL dicha definición varía ligeramente.

Justificación

- Las entidades se identifican de modo único en la realidad, y también deben de poderse

identificar en el modelo relacional.

- Dicha identificación es realizada por las claves primarias.

- Si una clave primaria contiene un nulo quiere decir que no se puede aplicar la definición de

clave primaria sobre la entidad asociada.

- Por lo tanto, esta entidad no se puede identificar, lo que entre en contradicción con la

definición de entidad.

- Así pues, la regla también se puede formular:

- En una base de datos relacional, no se puede almacenar información sobre algo que no se

pueda identificar.

- Las claves primarias compuestas debe de ser no nulas en su totalidad, es decir, ninguno de

sus atributos puede ser nulo.

9.4 Claves ajenas

Definición

- Una Clave Ajena es un conjunto de atributos de una relación R2 cuyos valores o son

completamente nulos o coinciden que los de la clave primaria de una relación R1.

- De un modo gráfico se representa mediante una flecha entre las dos relaciones que se

etiqueta por el conjunto de atributos que la definen,

R₂ R₁

- La relación donde se encuentra la clave ajena se denomina Relación Referencial.

- La Relación Referida u Objetivo indica la relación donde se encuentra la clave primaria.

Comentarios

- Una relación referida puede ser también una relación referencial respecto de otro conjunto

de atributos.

- De este modo se puede definir una Ruta Referencial entre diferentes relaciones de la base de

datos.

- Si alguna de las relaciones aparece más de una vez en la ruta referencial se dice que

aparecen Ciclos Referenciales.

- La Relación Autorreferencial es un caso particular del anterior, donde coinciden la relación

referida y la relación referencial.

- Las claves ajenas pueden admitir nulos, a diferencia de las claves primarias.

9.5 Regla de Integridad Referencial

- La Base de Datos no debe contener valores de clave ajena sin concordancia.

- Es decir, para cualquier valor no nulo de la clave ajena existe un valor asociado en la clave

primaria de la relación objetivo.

9.6 Reglas para las Claves Ajenas

Borrado de Claves Primarias

- La decisión depende de los requerimientos, existiendo tres posibilidades:

- Restringida (Restricted). No se puede borrar un tupla si está referenciada.

- Se Propaga (Cascades). Se borra la tupla junto con las tuplas que la referencian.

- Anula (Nillifies). Se borra la tupla y se pone a nulo la clave ajena de las tuplas que la

referencian, siempre y cuando los acepte.

Modificación de Claves Primarias

- La decisión depende de los requerimientos, existiendo tres posibilidades:

- Restringida (Restricted). Una tupla no se puede modificar si está referenciada.

- Se Propaga (Cascades). Se modifica la tupla junto con las tuplas que la referencian.

- Anula (Nullifies). Se modifica la tupla y se pone a nulo la clave ajena de las tuplas que la

referencian, siempre y cuando los acepte.

TEMA 10 ÁLGEBRA RELACIONAL

10.1 Introducción

- Mediante el Álgebra Relacional se suministran los operadores que permiten construir una

relación que contiene la información buscada.

- El Cálculo Relacional define la notación que permite describir las propiedades que deben

cumplir las tuplas de la relación resultante.

10.2 Una Sintaxis para el Álgebra Relacional

Cabecera de las Relaciones Resultado

- Si el operador trabaja sobre una relación, la cabecera de la relación resultado es un

subconjunto de los atributos de la relación operando.

- Si el operador trabaja sobre dos relaciones, la cabecera de la relación resultado es un

subconjunto de la unión de los atributos de las relaciones operando.

- Renombrar (Rename), operador unario que permite modificar el nombre de los atributos de

una relación.

Herencia de Claves Primarias

- La relación resultado está compuesta de una cabecera y un cuerpo, pero también debe de

elegirse una clave primaria.

- Por lo tanto, se deben de definir unas Reglas de Herencia de Clave Primaria, que permitan

definir la clave primaria de la relación resultado de cualquier operador.

10.4 Operaciones Tradicionales sobre Conjuntos

- Todas las tuplas que aparecen en la relación resultado deben ser Homogéneas, para lo cual

las relaciones operando deben de ser Compatibles:

- El grado de la relaciones operando tiene que coincidir.

- El dominio de sus atributos con el mismo nombre también debe de coincidir.

Producto Cartesiano Ampliado

- El Producto es el Conjunto de todos los Pares Ordenados de Tuplas, de modo que la primera

Tupla pertenece a la Primera Relación y la Segunda pertenece a la Segunda. (TIMES)

Propiedades

- La unión, la intersección y el producto son Conmutativas, aunque no la diferencia.

- Lo mismo ocurre con la Asociatividad.

10.5 Operaciones Relacionales Especiales

Restricción

- La Restricción da como resultado una relación que contiene un subconjunto de las tuplas de

la relación operando.

- Siendo A una relación, X e Y un literal o un atributo de la relación A, y theta un operador de

comparación escalar simple, la expresión

A WHERE X theta Y theta � {<, <=, =, <>, >=, >}

da como resultado una relación que contiene las tuplas de A que cumplen que la condición

(X theta Y) es verdadera.

Proyección

- La Proyección genera una relación en la que aparece un subconjunto de los atributos de la

relación operando.

- Siendo A una relación y X, Y, ..., Z atributos de A, la expresión,

A [X, Y, ... , Z]

genera una relación donde, la cabecera son los atributos X, Y, ..., Z.

- Se define la Proyección Identidad como la proyección en la que no se especifica la lista de

atributos.

- Cuando se especifica la lista de atributos pero no se especifica ningún atributo en ella, se

obtiene la Proyección Nula.

Reunión Natural

- La Reunión Natural permite unir tuplas de dos relaciones, que cumplen que parte de sus

atributos coinciden.

- Siendo A y B dos relaciones donde,

- La cabecera de A es (X₁, ..., X_m, Y₁, ..., Y_n).

- La cabecera de B es (Y₁, ..., Y_n, Z₁, ..., Z_p).

entonces se cumple que la expresión, A JOIN B

genera una relación cuya cabecera es, (X₁, ..., X_m, Y₁, ..., Y_n, Z₁, ..., Z_p) � (X, Y, Z)

(((A RENAME Y AS YA) TIME B) WHERE YA = Y) [X, Y, Z]

- El análisis de la anterior expresión demuestra que la reunión natural cumple las propiedades

de conmutatividad y asociatividad.

- Además, si el conjunto de atributos Y es vacío, la reunión natural es equivalente al producto.

Reunión Theta

- La Reunión Theta es una versión generalizada de la reunión natural, en donde las tuplas de

las relaciones deben cumplir cierta condición para que su unión aparezca en el resultado.

- Siendo A y B dos relaciones, X un atributo de A, y un atributo de B, y theta un operador de

comparación escalar simple, la expresión

(A TIMES B) WHERE X theta Y, theta � {<, <=, =, <>, >=, >}

genera una relación cuya cabecera coincide con la del producto de A y B, y el cuerpo es el

subconjunto de tuplas de este producto que cumplen la condición (X theta Y).

- Cuando el comparador es el signo igual se obtiene una Equirreunión.

- Una reunión natural se puede observar como una equirreunión de la que se ha proyectado un

subconjunto determinado de atributos.

División

- La División permite seleccionar un subconjunto de los valores de las tuplas que cumplen

que los atributos asociados se relacionan en la relación con un subconjunto de valores del

resto de los atributos.

- Siendo A y B dos relaciones donde,

- La cabecera de A es (X₁, ..., X_m, Y₁, ..., Y_n).

- La cabecera de B es (Y₁, ..., Y_n).

entonces se cumple que la expresión, A DIVIDEBY B

genera una relación donde, la cabecera es (X₁, ..., X_m).

- Como el resultado es una relación, se eliminan las tuplas duplicadas que pudieran aparecer.

- Este operador suele ser útil para consultas que incluyan en su enunciado la palabra "todos".

- Se puede definir mediante una combinación de operadores como sigue,

A [X] MINUS ((A [X] TIMES B) MINUS A) [X]

10.6 ¿Para qué sirve el Álgebra?

- La intersección mediante la utilización de la diferencia.

A INTERSECT B � A MINUS (A MINUS B)

- Así, un lenguaje es Relacionalmente Completo si puede expresar cualquier relación definida

mediante una expresión del álgebra.

10.7 Operaciones Adicionales

Ampliación

- Ampliación (Extent). Operador unario que genera una relación con un atributo más que la

relación operando en la que se incluye el resultado de una operación entre escalares y/o los

valores de los atributos de cada tupla.

- La sintaxis de este operador es la siguiente,

EXTENT término ADD cálculo AS atributo

donde cálculo es cualquier operación entre escalares y/o valores de atributos de término, y

atributo no coincide con ningún atributo de término.

- Un ejemplo podría ser el siguiente,

EXTENT P ADD (PESO * 454) AS PESOGRS.

- Para evitar el anidamiento de operadores, cuando se desea realizar varias ampliaciones sobre

la misma relación, se podría modificar la sintaxis anterior como sigue,

EXTENT termino ADD calc1 AS atrib1, calc2 AS atrib2

Resumen

- Resumen (Summarize). Operador unario que genera una relación en la que aparecen los

atributos por los que se agrupa y un atributo adicional en el que aparece el resultado de

aplicar la operación seleccionada sobre los valores de un atributo en cada grupo.

- La sintaxis de este operador es la siguiente,

SUMMARIZE término GROUPBY (lista_con_comas_de_atributos)

ADD cálculo_de_agregados AS atributo

donde cálculo_de_agregados es una función definida sobre un conjunto de valores, y que se

aplica a uno de los atributos de término.

- La lista_con_comas_de_atributos puede ser una lista vacía en cuyo caso la función se aplica

sobre todas las tuplas de término.

- El operador SUMMARIZE aplicado sobre una relación vacía genera una relación vacía.

- Para poder aplicar diversas funciones sobre un mismo agrupamiento se debe modificar la

sintaxis como sigue.

SUMMARIZE término GROUPBY (lista_con_comas_de_atributos)

ADD cálculo_de_agreg1 AS atrib1,

ADD cálculo_de_agreg2 AS atrib2.

División Generalizada

- La División Generalizada (Generalized Divide) es una extensión del operador división

clásico que se puede aplicar sobre cualquier pareja de relaciones.

- Siendo A y B dos relaciones donde,

- La cabecera de A es (X₁, ..., X_m, Y₁, ..., Y_n).

- La cabecera de B es (Y₁, ..., Y_n, Z₁, ..., Z_p).

entonces se cumple que la expresión, A DIVIDEBY B

genera una relación donde,

- La cabecera de es (X₁, ..., X_m, Z₁, ..., Z_p).

- En función de la cardinalidad de los conjuntos de atributos de X, Y y Z se obtiene,

- Si Z es vacío se obtiene la división clásica entre A y B.

- Si X es vacío se obtiene la división clásica entre B y A.

- Si Y es vacío se obtiene el producto de A y B.

Reunión Externa

- La Reunión Externa es una generalización de la reunión clásica, que genera al menos una

tupla en la relación resultado para toda tupla de las relaciones operando.

TEMA 11 CALCULO RELACIONAL

11.1 Introducción

El Álgebra Relacional y el Cálculo Relacional

- Se puede decir que el cálculo es descriptivo y que el álgebra es prescriptivo.

- También se puede decir que el cálculo plantea el problema y el álgebra lo resuelve.

Panorama General del Cálculo

- El cálculo relacional se fundamenta en una rama de la lógica matemática denominada

Cálculo de Predicados.

- Una característica fundamental del cálculo relacional es la denominada Variable de Tuplas

o Variable de Recorrido.

- Una variable de Tuplas se asocia a una relación y sus únicos valores permitidos son las

tuplas de dicha relación.

7.2 Cálculo Relacional Orientado a Tuplas

Variables de Tuplas

- Una Variable de Tupla se define mediante una proposición de la forma siguiente,

RANGE O T IS X1, X2, ..., Xn

donde

- T es la variable de tuplas definida.

- X1, X2, ..., Xn son nombres de relación, o bien una expresión del cálculo de tuplas entre

paréntesis.

- Normalmente, una variable de tupla se asocia a un única relación, aunque la definición sea

más general.

Concepto de Variables Libres y Acotadas

- Cada Ocurrencia o Aparición de una Variable de Tupla en un fórmula bien formada puede

ser Libre o Acotada.

- Será Acotada si la variable se asocia a un cuantificador y la fórmula donde se encuentra la

ocurrencia forma parte de la fórmula bien formada del cuantificador.

EXISTS x (x > 3)

- Será Libre si no es Acotada.

(x > 3)

- En una expresión, una misma variable de tupla puede aparecer como libre y como acotada

en diferentes fórmulas bien formadas.

EXISTS x (x > 3) AND (x > 0)

Sintaxis de Variables Libres y Acotadas

- El cuantificador EXISTS se lee como "existe", mientras que el cuantificador FORALL se

lee como "para todos".

- El FORALL se puede expresar mediante EXISTS,

FORALL x(g) � NOT EXISTS x (NOT g)

- También existe la expresión IF - THEN que no es primitiva, y cuya funcionalidad es la

siguiente,

IF f THEN g � (NOT f) OR g

Listas Objetivo

- Una Lista Objetivo es una lista de Elementos Objetivo separados mediante comas, en la que

cada elemento es una variable de tupla, o bien una expresión como la siguiente,

[X =] T.A.

donde

- T es una variable de tupla y A es uno de sus atributos asociados.

- X es un nombre de atributo para el atributo correspondiente en el resultado de evaluar la

lista objetivo.

- Algunos ejemplos de listas objetivo aparecen a continuación,

SX.S#

SNUM = S.S#

SX

SX.S#, SX.CIUDAD, SPX.P#

7.3 Cálculo Relacional y Álgebra Relacional: Algoritmo de Reducción de Codd

Equivalencia del Cálculo y del Álgebra

- El álgebra relacional y el cálculo de tuplas son dos formalismos equivalentes.

- Codd demostró esta equivalencia con su Algoritmo de Reducción, que genera una expresión

del álgebra semánticamente equivalente a la expresión del cálculo de la que se parte.

TEMA 12 DISEÑO CONCEPTUAL

12.2 Abstracciones en el Diseño Conceptual

Presentación

- La abstracción es un proceso mental que se aplica al seleccionar algunas características y

propiedades de un conjunto de objetos y excluir otras no pertinentes.

- En el diseño conceptual de bases de datos se realizan tres tipos de abstracciones:

- Abstracción de Clasificación.

- Abstracción de Agregación.

- Abstracción de Generalización.

- Estas abstracciones ayudan al programador en la tarea de entender, clasificar y modelar la

realidad.

Abstracción de Clasificación

- Su objetivo es clasificar los objetos de la realidad caracterizados por propiedades comunes.

MES: Enero, Febrero, ..., Diciembre

- Estas abstracciones se representan mediante un árbol, cuya raíz es la clase y las hojas son los

miembros de la clase.

Abstracción de Agregación

- Se definen nuevas clases a partir del conjunto de clases asociadas a las partes que la

componen. SE_IMPARTE

CURSO DIA AULA

- Las clases hoja son parte de la clase-raíz.

- Se puede decir que mediante la clasificación se identifican tipos de atributos y con la

agregación se identifican tipos de entidades.

Abstracción de Generalización

- Permite definir una relación de subconjunto entre dos o más clases.

PERSONA

HOMBRE MUJER

- En una generalización, todas las abstracciones definidas por la clase raíz son heredadas por

las clases subconjunto.

Propiedades de la Agregación Binaria

- El número de clases-hoja que se asocian a una clase-raíz permite diferenciar dos tipos de

agregaciones binarias y n-arias.

La Cardinalidad en una Agregación Binaria

- Dada una agregación A y una de sus clases asociadas C_i, se pueden definir dos tipos de

cardinalidades:

- Cardinalidad Mínima. Menor número de correspondencias en las que los elementos

de C_i pueden tomar parte. Los valores habituales son 0 y 1.

- Si card-min (C_i,A) = 0 la participación de los elementos de C_i en A es opcional.

- Si card-min (C_i,A) > 0 la participación de los elementos de C_i en A es obligatoria.

- Cardinalidad Máxima. Mayor número de correspondencias en las que los elementos

de C_i pueden tomar parte. Los valores habituales son 1 y n.

- Si card-max (C_i,A) = n, la participación de un elemento de C_i en A es ilimitado.

- En otro caso, el valor de card-max (C_i,A) marca el límite de la participación de un

elemento de C_i en A.

Propiedades de la Generalización

- Las clases-hoja pueden definir de un modo completo o incompleto la clase genérica.

- Total. Los valores de la clase genérica pertenecen a alguna de las clases-hoja.

- Parcial. Algún valor de la clase genérica no pertenece a ninguna clase-hoja.

- Las clases-hoja pueden compartir aspectos de la definición de la clase genérica.

- Exclusiva. Los valores de la clase genérica pertenecen a una sola clase-hoja.

- Superpuesta. Los valores de la clase genérica pertenecen a varias clases-hoja.

12.3 Modelo Entidad/Relación

- Fue introducido por Peter Chen en 1976, en 1988 el ANSI lo seleccionó como modelo

estándar para los sistemas de diccionarios de recursos de información.

- Inicialmente se constituía de los siguientes conceptos: entidades, interrelaciones y atributos.

- Posteriormente se incluyeron otros conceptos en el modelo: jerarquías de generalización,

subconjunto, atributos compuestos e identificadores.

Entidades

- Una entidad representa un clase de objetos de la realidad.

- Se representa mediante un rectángulo que incluye el nombre de la clase.

Interrelaciones

- Una interrelación define una agregación entre las clases del modelo.

- Se representa mediante un rombo que incluye el nombre de la agregación, y al cual se

conectan las entidades asociadas a las clases que forman la agregación.

- El Anillo es un tipo de interrelación que conecta una entidad consigo misma.

- Las conexiones se etiquetan con la cardinalidad asociada a cada entidad.

(1,1) (0,n)

PERSONA vive_en CIUDAD

Atributos

- Los atributos permiten caracterizar tanto las entidades como las interrelaciones.

- El concepto de cardinalidad también se asocia a los atributos.

- Por lo que respecta a la cardinalidad mínima,

- Si fuera igual a cero, el atributo en cuestión admite nulos.

- En caso contrario, se debería especificar un número mínimo de valores del atributo

para todos los casos.

- La cardinalidad máxima,

- Si es igual a uno se dice que el atributo es Monovalente, es decir, en un caso el

atributo solo puede tener un valor asociado.

- Cuando es mayor que 1, es atributo es Polivalente, y por tanto pueden aparecer casos

que tengan varios valores del atributo.

- Cada atributo se asocia a un dominio que define el conjunto de valores válidos del atributo.

Jerarquía de Generalización

- Se representa mediante flechas que parten de las entidades E_i y llegan a la entidad E.

- Las generalizaciones se caracterizan por las propiedades anteriormente comentadas,

- Pueden ser Totales o Parciales.

- Pueden ser Exclusivas o Superpuestas.

- Las propiedades de la entidad genérica son heredadas por las entidades subconjunto.

Subconjuntos

- Es un caso particular de generalización donde sólo aparece una entidad subconjunto.

- Por su definición, un subconjunto se asocia a una generalización parcial y exclusiva.

Atributos Compuestos

- Están definidos por grupos de atributos afines.

- Se representan mediante un óvalo conectado a la entidad o interrelación asociada, y al que

se conectan los atributos que lo componen.

Identificadores

- Un identificador es un conjunto de atributos y entidades que permiten determinar de modo

único los casos de una entidad. (Clave o Clave candidata).

- El identificador siempre existe por lo que la cardinalidad mínima de sus componentes es 1.

- Un identificador debe cumplir que,

- No puede aparecer dos casos en E que tengan el mismo valor del identificador.

- Si se omite algún atributo o entidad, la condición anterior no se cumple.

- Los identificadores se pueden clasificar a partir de diferentes criterios,

�- Simple: si la suma de n y m es igual a 1; si es mayor que 1 se denomina Compuesto.

- Cuando m=0 el identificador es Interno, mientras que si n=0 se denomina Externo.

n = número de atributos de la entidad; m = número de entidades vinculadas.

- Si n y m son mayores que cero, entonces se dice que el identificador es Mixto.

TEMA 13 DISEÑO LóGICO

El objetivo del diseño lógico es convertir un esquema conceptual en un esquema lógico que se ajuste al sistema de gestión de base de datos a utilizar.

Se pretende que el esquema lógico cumpla ciertas características:

- Las relaciones deben de estar en tercera forma normal.

- Se deben definir las claves primarias y ajenas de todas las relaciones.

- Es necesario incluir en el esquema las reglas de integridad necesarias.

13.2 Diseño Lógico en el Modelo Relacional

- El modelo relacional no puede representar jerarquías de generalización. Existen tres

posibles alternativas:

Integración de las Entidades Subconjunto

- Los atributos de las entidades subconjunto se añaden a los de la entidad genérica con

cardinalidad mínima cero.

- Se añade un atributo discriminativo en la entidad genérica, que indica el caso al que

pertenece la entidad considerada, con

- Cardinalidad Mínima cero si la jerarquía es parcial, o uno si fuera total.

- Cardinalidad Máxima uno si la jerarquía es exclusiva, o n si fuera superpuesta.

- Puede generar la aparición de muchos nulos.

Eliminación de la Entidad Genérica

- Los atributos de la entidad genérica son heredados por todas las entidades subconjunto.

- Sólo es útil para jerarquías totales y exclusivas.

- Las operaciones sobre la entidad genérica deben aplicarse sobre todas las entidades subconj.

No Eliminar Ninguna de las Entidades

- La inclusión de las entidades subconjunto sobre la entidad genérica se modeliza mediante la

interrelación ES_UN.

- La cardinalidad de la entidad genérica sobre la relación es (0,1), mientras que en las

entidades subconjunto es (1,1).

Transformación de Identificadores Externos

- En el modelo relacional no se pueden utilizar identificadores externos, por lo que hay que

transformarlos en internos.

- Una posibilidad es importar a la entidad los atributos asociados al identificador de las

entidades que forman parte del identificador externo.

- Las interrelaciones asociadas al identificador externo pueden eliminarse.

Transformación de Atributos Compuestos

- El modelo relacional no permite representar atributos compuestos, por lo que se busca una

alternativa. Transformar los atributos compuestos, como:

- Considerar el atributo compuesto como un atributo simple.

- Eliminar el atributo compuesto y considerar cada uno de sus atributos como atributo

simple de la entidad.

Transformación de Atributos Polivalentes

- Cada atributo polivalente de una entidad requiere la inclusión de una nueva entidad donde

se cumple que,

- El atributo polivalente se convierte en un atributo monovalente.

- La entidad hereda los atributos asociados al identificador de la entidad original.

- El identificador de esta nueva entidad está compuesto por todos sus atributos.

- Si el atributo polivalente se asocia a una interrelación, también es necesario crear una nueva

entidad.

Transformación de Entidades

- Las entidades del esquema conceptual se transforman en relaciones base dentro del esquema

lógico.

- Los atributos de las entidades se convierten en atributos de la relación base asociada.

EMPLEADO (NSS, empleado, apellido, salario)

Transformación de Interrelaciones Uno a Uno

- Cuando la cardinalidad mínima de ambas entidades es igual a uno, las dos entidades se

pueden integrar en una relación.

- La relación resultante presenta los atributos que no son clave primaria de la relaciones

asociadas a las entidades.

- Por lo que respecta a la clave primaria:

- Si coincide en ambas relaciones se incluye una única vez.

- En caso contrario, se incluyen las dos claves primarias y se elige una como clave

primaria.

- Si alguna de las entidades tiene cardinalidad mínima igual a cero, la interrelación se

transforma en una relación.

- Hereda como atributos las claves primarias de las relaciones anteriores, y una de

ellas será la clave primaria.

- Aparecen como atributos, los atributos de la interrelación.

Transformación de Interrelaciones Uno a Muchos

- Estas interrelaciones se pueden transformar de dos modos diferentes:

- Añadiendo la clave primaria de la relación asociada a la entidad de la parte uno y los

atributos de la interrelación en la relación asociada a la entidad de la parte muchos.

- Generando una nueva relación que incluye los atributos de la interrelación y las

claves primarias de las dos entidades. Clave primaria de la parte muchos.

- Cuando la cardinalidad mínima de la entidad uno es igual a uno, se suele utilizar la primera

opción. En cambio si la cardinalidad mínima fuera cero, se suele utilizar la segunda opción.

Transformación de Interrelaciones Muchos a Muchos

- Se genera una nueva relación que incluye los atributos de la interrelación y las claves primarias de las dos entidades, que forman la clave primaria de la nueva relación.

13.3 Normalización de Relaciones

Comentarios Iniciales

- La teoría de la normalización, desarrollada por Codd en 1972 permite mejorar el diseño

lógico de un sistema de información.

- Se fundamenta en la Formas Normales, que son un conjunto de restricciones que deben de

cumplir la relaciones,

- Una relación está en primera forma normal, si satisface que sus dominios simples sólo tienen valores atómicos.

- Ventajas de la normalización:

- Evita dependencia de datos en inserciones, borrados y modificaciones.

- Mejora la independencia de los datos.

- No establece restricciones artificiales en la estructura de los datos.

Dependencia Funcional

- Dada una relación R, el atributo Y de R depende funcionalmente del atributo X de R,

R.X - - - - -> R.Y

si y sólo si un valor Y en R está asociado a cada valor X en R

- Si el atributo X es una clave candidata de R, entonces todos los atributos Y de la relación

dependen funcionalmente de X.

- Si el atributo Y es por completo dependiente funcionalmente de X, entonces no depende

funcionalmente de ningún subconjunto propio de X.

Tercer Forma Normal

- El objetivo del diseño lógico es obtener relaciones en tercera forma normal.

- Una relación está en tercera forma normal si y sólo si sus atributos no clave son,

- Mutuamente independientes, no existe un atributo que dependa funcionalmente de

alguna combinación del resto de atributos.

- Por completo dependientes funcionalmente de la clave primaria.

Primera y Segunda Forma Normal

- Una relación se encuentra en primera forma normal si todos sus atributos son atómicos.

- Una relación se encuentra en segunda forma normal si está en primera forma normal y todos

los atributos no clave dependen de la clave primaria.

Segunda y Tercera Forma Normal

- Una relación está en tercera forma normal, si está en segunda forma normal y además cada

atributo no clave no depende de modo transitivo de la clave primaria.

Buenas y Malas Descomposiciones

- Un buena descomposición es aquella que genera relaciones independientes.

- Dos proyecciones R1 y R2 de la relación R son independientes si y sólo si cumplen que,

- Toda dependencia funcional en R se puede deducir de las dependencias funcionales

definidas en R1 y R2.

- Los atributos comunes de R1 y R2 son una clave candidata de al menos una de las

dos proyecciones.