BASES DE DATOS TEMA 1 INTRODUCCIÓN A LAS BASES DE DATOS • DE LOS SISTEMAS DE FICHEROS A LAS BASES DE DATOS • DEFINICIÓN DE BASE DE DATOS • ELEMENTOS DE UNA BASE DE DATOS • DATOS OPERATIVOS • VENTAJAS DE LAS BASES DE DATOS FRENTE A LOS FICHEROS CLÁSICOS • INDEPENDENCIA DE DATOS • TIPO DE BASES DE DATOS • DE LOS SISTEMAS DE FICHEROS A LAS BASES DE DATOS. Tenemos una serie de proveedores que suministran piezas de una cantidad, un proveedor puede suministras mas de una pieza y una pieza puede ser suministrada por mas de un proveedor. S# S1 S1 S2 S2 S3

NomS X X Y Y Z

Estado 10 10 20 20 30

Ciudad OU OU PO PO LU

P# P1 P3 P1 P4 P1

NomP Tuerca Tornillo Tuerca Perno Tuerca

Color A R A V A

Peso 10 20 10 30 10

Cantidad 100 100 200 50 100

Problemas • Redundancia • Inconsistencia : Cambio de datos • Integridad : Dos códigos de proveedor para diferentes registros. • No se permite compartir información. En los años 70 aparece el concepto de Base de Datos e intenta solucionar todos los problemas. Para solucionar estos problemas lo que haríamos seria dividirlo en tres ficheros uno guardando los proveedores, otro guardando las piezas y otro para hacer la relación entre los dos. • DEFINICIÓN DE BASE DE DATOS Sistema de captación y manutención de registros computerizados que permite añadir, modificar y borrar datos y que permiten añadir modificar y borrar información. Dato : Seria modificar los datos de una tabla, un campo. Información : Es la posibilidad de modificar, añadir o borrar un registro o la estructura de la Base de Datos. • ELEMENTOS DE UNA BASE DE DATOS Hay cuatro elementos en la Base da Datos: 1

• Los Datos • Hardware • Software • Usuarios Datos: Tienen q cumplir dos características: • Que estén integrados. • Que estén compartidos. Integrada: La unión de los ficheros deben recoger toda la información con redundancia mínima. Compartidos: Los elementos individuales de información en una Base de Datos puedan compartirse entre diversos usuarios. Hardware: Se componen de los dispositivos de almacenamiento, el procesador y la memoria principal. Dependiendo de la arquitectura hay dos tipos: Local: Todo concentrado en un único punto. Distribuido: Conectada mediante sistemas de red. Usuarios: Programador de Aplicaciones. Usuarios Finales. Administradores de la Base de Datos. Software: Sistema de gestión de la Base da Datos que permite la comunicación entre la Base de Datos física y los usuarios mediante paquetes Software que aportan facilidades de modificación, inserción borrado, etc. Usuarios: Programador de Aplicaciones: Encargado de escribir los programas que utilizan la Base de datos, para ello interactúa con el Sistema de Gestión de Base de Datos (SGBD). Usuario Final: Usuario que interactúa con el sistema o bien desde un terminal, una interfaz o un programa del programador de aplicaciones. Administrador de la Base de Datos: Encargado del diseño y mantenimiento de la Base de Datos. • DATO OPERATIVO. Es toda información que necesita una empresa para su funcionamiento, se componen de entidades y de las conexiones que existen entre los mismos. A todo el conjunto de entidades y conexiones se le denomina diseño lógico de la Base de Datos. Ejemplo: Datos por sistema: Datos que se almacenan en la Base de Datos y que no son de Entrada−Salida. Se pueden almacenar. Al no ser datos de Entrada−Salida no son datos operativos.

2

• VENTAJAS DE LAS BASES DE DATOS. • Que ventajas nos ofrecen las Bases de Datos frente al archivo en papel ♦ Compactación : Poder estar la información mas compacta. ♦ Rapidez de acceso a la información: Mucho más sencillo y rápido. ♦ Facilidad de Trabajo. ♦ Actualización. • La Base de Datos permite un control centralizado de la información. Administrador de Datos: Quien dirige o plantea la política de la empresa del uso de los datos que hay q manejar. El administrador (Crea, modifica y gestiona) de datos le dice al Administrador de la Base para saber cuales son sus necesidades. Como consecuencia del poder centralizado aparece lo siguiente: • Reducir redundancias. • Reducir inconsistencia. • Los datos pueden compartirse. • Se mantienen los estándares. • Mayor seguridad • Mayor facilidad de chequeo de errores. • Se equilibran requerimientos opuestos. • Permite el manejo de transacciones (Serie de operaciones que dan como resultado una información) • INDEPENDENCIA DE DATOS Inpugnidad de las aplicaciones existentes posibles cambios en la estructura de almacenamiento y en la forma de acceso de la Base de Datos. ¿Por qué es necesaria la independencia de datos? • Porque cada aplicación puede requerir una vista diferente de los mismos datos. • Que el administrador de la Bases de Datos debe tener libertad de modificar la estructura de almacenamiento o las técnicas de acceso para adaptarlas a cambios en los requerimientos sin tener que modificar las aplicaciones ya existentes. ¿Qué modificaciones son las más usuales que podría hacer el administrador de la Base de Datos y a las que las aplicaciones deberían ser inmunes? Campo Almacenado: Mínima cantidad de información q se almacena reconocible como un nombre. Los valores que toman cada campo se denominan ocurrencia. Registro almacenado: Un conjunto de campos almacenados, relacionados entre si y reconocibles por un nombre, y ocurrencia de registros almacenados serian los datos de ese registro almacenado. Fichero (o archivo) almacenado: Conjunto de ocurrencias de un determinado tipo de registros almacenados reconocidos por un nombre.

3

+ Representación de datos numéricos. + Representación de datos carácter. + Unidades para datos numéricos: Medidas de peso, medidas de longitud... + Codificación de datos. + Materialización de los datos: • Materialización directa: Cuando el campo lógico coincide con el campo almacenado. • Materialización virtual: Cuando el campo lógico coincide con mas de un campo almacenado. + Estructura de los registros almacenados. + Estructura de archivos almacenados. • TIPOS DE BASES DE DATOS. En los mundos de las Bases de datos existen dos tipos de enfoques. Enfoque relacional: Estructura de datos basca, la tabla. Enfoque segundo: Estructura de datos básica, el grafo. Si el grafo es abierto (árbol) tenemos los sistemas jerárquicos y si el grafo es cerrado tenemos la estructura en red. TEMA 2 ARQUITECTURA DE UN SISTEMA DE BASE DE DATOS. • NIVELES GENERALES DEL SISTEMA. • NIVEL EXTERNO • NIVEL CONCEPTUAL • NIVEL INTERNO • CORRESPONDENCIAS • EL ADMINISTRADOR DE LA BASE DE DATOS. 2.1 NIVELES GENERALES DEL SISTEMA El grupo ANSI/SPARC fue el que normalizo el uso de la Base de Datos haciendo estos niveles. NIVEL EXTERNO. Vistas individuales de cada uno de los usuarios NIVEL CONCEPTUAL Vista comunitaria de los usuarios (Vista de toda la Base de Datos) NIVEL INTERNO Formada por la vista de almacenamiento 4

EXTERNO CONCEPTUAL INTERNO 2.1.1 NIVEL EXTERNO. Nivel del usuario individual. El programador de aplicaciones tiene que tener un lenguaje de alto nivel (Cobol, Pascal...) y para el usuario final, el nivel externo, tiene q proporcionar un lenguaje de consultas (SQL) o bien un lenguaje de aplicaciones (Programas desarrollados mediante programador de aplicaciones, con menús, ventanas...) todos estos lenguajes de alto nivel deben incluir un sublenguaje de datos que están incluidos en el lenguaje anfitrión que se denomina DSL. Ejemplo: SQL " C (el lenguaje SQL esta contenido en C) Si el DSL es indistinguible el anfitrión se dice que están fuertemente acoplados pero si se pueden separar con nitidez son débilmente acoplados. El DSL se compone a su vez de 2 lenguajes de datos: DDL: Un lenguaje de definición de Datos. DHL: Un lenguaje de gestión o manejo de Datos. La vista individual de cada usuario se le denomina Vista Externa (el conjunto de ocurrencias será vista externa) esta vista está formada por el conjunto de ocurrencias de los distintos registros externos (registros lógicos). Toda vista externa se define mediante su Esquema externo donde el esquema externo son las definiciones de los tipos de registros externos en esa vista externa. El esquema externo se define mediante el DDL Externo. 2.1.2 NIVEL CONCEPTUAL. − Vista conceptual: Representación de toda la información (ocurrencia) contenida en la BD. Se compone, la vista, de todas las ocurrencias de los diferentes tipos de los registros conceptuales. La vista se define mediante el esquema conceptual que está formado por las definiciones de cada tipo de registro conceptual. El esquema conceptual se escribe mediante el DDL conceptual. ¿En el esquema conceptual hay q tener consideraciones sobre la estructura de almacenamiento? No, por la independencia de datos, por que si no tendríamos que cambiar los datos en el nivel externo y en el nivel conceptual. ¿Qué medidas de seguridad e integridad en que nivel? En el nivel conceptual por que es donde está toda la información de la Base de Datos. 2.1.3 NIVEL INTERNO. − Vista Interna: Representación de bajo nivel de toda la Base de Datos, se compone del conjunto de ocurrencias de los distintos tipos de registros internos. Se define mediante el esquema interno que 5

además de las definiciones de los distintos tipos de registros internos también debe especificar lo siguiente: • Tipo de índices que hay. • Representación de los campos almacenados. • Secuencia física de los registros almacenados • Etc. 2.1.4 LAS CORRESPONDENCIAS Correspondencia conceptual interna: Define la correspondencia entre la vista conceptual y la Base de Datos almacenada y especifica como están representados los registros y campos conceptúales en el nivel interno, es decir, me permite enlazar los valores y tipos de con el nivel interno. El que modifica la estructura de almacenamiento el administrador de la Base de Datos será el encargado de modificar la correspondencia conceptual interna para que esos cambios no afecten al nivel conceptual y, por tanto, se puede conservar la independencia de datos. Correspondencia externa conceptual: Define la correspondencia entre la vista externa particular y la vista conceptual, Se encargará de enfocar campos con mas tipos de los campos, los nombres de los registros, los valores de los campos, que varios campos conceptuales pueden combinarse en un solo registro externo... 2.2 EL ADMINISTRADOR DE LA BASE DE DATOS −Funciones del Administrador de la Base de Datos. • Describir el contenido de la información en la Base de Datos, equivale a implementar el esquema conceptual. Para ello haremos el diseño lógico de la Base de Datos y luego mediante el DDL conceptual definimos los registros conceptuales. (Esto equivale a definir las tablas) • Decidir sobre la estructura de almacenamiento. Equivale a definir el esquema interno, mediante el DLL interno. También a esto se le denomina diseño físico de la Base de Datos. Y debe contener los siguientes aspectos: • Representación de campos. • Indexación. • Tipos de acceso • Seguridad Física. • Etc. • Conexión con los usuarios. Si el usuario final el Administrador de la Base de Datos debe captar la vista externa de cada uno y en función de ello escribe el esquema externo asociado, también debe definir del usuario final la correspondencia externa conceptual asociado a este esquema. Por ultimo debe crear al usuario final un entorno amigable. Al programador de Aplicaciones. El Administrador de la Base de Datos le debe dar: • Le tiene que dar ayuda para la implementación de la vista externa, es decir, el DLL externo. • Le tiene que permitir que el programador escriba sus aplicaciones (lenguaje anfitrión) • Definir la correspondencia externa y conceptual. • Le debe permitir explorar el entorno utilizando el DML externo.

6

• Debe definir la política de seguridad e integridad para ello utiliza el DLL conceptual. • Definir la estrategia de recuperación de fallos. • Ocuparse de problemas de rendimiento: Llamado AFINAMIENTO. TEMA 3 EL NIVEL INTERNO 3.1 INTRODUCCIÓN. 3.2 ETAPAS DE ACCESO A UNA BASE DE DATOS. 3.3 PAGINAS Y FICHEROS. 3.4 INDEXACIÓN. 3.5 HASHING. 3.6 CADENAS DE PUNTEROS. 3.7 TÉCNICAS DE COMPRENSIÓN. 3.1 INTRODUCCIÓN. Dos aspectos a tener en cuenta. • Minimizar al máximo los accesos a disco, ya que esta es más lenta que la memoria principal. • Tener diferentes estructuras de almacenamiento, q depende de los requisitos que necesitemos en cada momento. Independencia de datos al cambiar las estructuras de almacenamiento, las aplicaciones que corren sobre ella deben de seguir funcionando. 3.2 ETAPAS DE ACCESO A UNA BASE DE DATOS. Solicita registros almacenados Envía el registro correspondiente Ocurrencia de registros almacenados Envía una pagina Pagina: Cantidad de memoria que se puede leer o escribir en una sola operación de Entrada/Salida. Operación de Entrada/Salida (Física) Datos leídos de disco. • El Gestor de Ficheros y Gestor de Disco forman siempre parte del Sistema Operativo. − GESTOR DE DISCO 7

Es un componente del sistema operativo subyacente, se encarga de todas las operaciones de E/S, por tanto, necesita conocer todas las direcciones físicas del disco, en contraposición el Gestor de Ficheros percibe el disco como un conjunto de paginas, donde cada conjunto de paginas esta formado por grupos de paginas de tamaño fijo, donde cada conjunto de paginas y cada pagina de ese conjunto tienen un identificador único. El G.D. mantiene la correspondencia entre el identificados de pagina y la dirección física en disco de dicha pagina. Necesitamos saber el numero de paginas q hay libre para la introducción de nuevos datos. Se tiene un conjunto de paginas especiales llamado conjunto de paginas de espacio libre. OPERACIONES QUE PUEDE SOLICITAR EL G.F. AL G.D. • Leer la pagina p del conjunto de paginas c. • Reemplazar la pagina p por la pagina p´ en el conjunto de paginas c. • Añadir la pagina p al conjunto de paginas c. • Eliminar la pagina p del conjunto c. GESTOR DE FICHEROS El G.F. utiliza al G.D. para que el Sistema de Gestión de Bases de Datos perciba al disco como un conjunto de archivos almacenados. Cada conjunto de paginas puede contener a uno o más archivos almacenados. Cada archivo almacenado debe tener un identificados que lo diferencia de los demás dentro del conjunto de paginas. Habitualmente forma parte del Sistema Operativo. OPERACIONES QUE EL SGBD PUEDE SOLICITAR EL GF • Leer el registro almacenado r del fichero almacenado a. • Reemplazar el registro almacenado r del fichero almacenado a. • Añadir al fichero almacenado a un registro y devolver el nuevo identificador. • Eliminar el registro r del archivo almacenado a. • Crear un nuevo archivo almacenado a. • Eliminar un archivo almacenado a. • AGRUPAMIENTO El agrupamiento es una utilidad que permite que los registros que se utilizan tengan acceso de entrada y salidas más rápidos. Hay 2 tipos: Interarchivo Entrearchivo. INTERARCHIVO Los registros están o bien en la misma pagina o bien en paginas que físicamente son cercanas, es necesario buscar un criterio de secuencialidad (utiliza un campo clave que identifica el registro almacenado). ENTREFICHEROS Lo que se pretende es unir registros que se van a tratar juntos, aunque no sean del mismo fichero. Tenemos dos posibilidades. O bien mediante cadenas de punteros y la otra es intercalar registros de diferentes ficheros, 8

en el mismo conjunto de paginas. 3.3 PAGINAS Y FICHEROS Ejemplo: Tres tipos de ficheros Proveedores Piezas Envíos Administración de pagina: Logran que el Gestor de Ficheros perciba la entrada y salida física como entrada y salida de paginas. De esta transformación se encarga el Gestor de Disco. Ejemplo: Supongamos un único registro por paginas y q cada fichero almacenado le vamos a asignar un conjunto de paginas. Para hacer un agrupamiento de secuencialidad vamos a tener en cuenta el código. Conjunto paginas: 1 a 5: Proveedores 6 a 11: Piezas 12 al 23: Envíos 23... Conjunto de paginas libres Realizar las siguientes operaciones: Inserción del Proveedor S6 Borrar el Proveedor S2 Insertar S7 Borrar S4 − Ahora tenemos que cuando necesitamos buscar la P7 tenemos que recorrer todo el disco, por lo cual utilizamos punteros. La pagina Ø nos tiene que dar la siguiente información (y por eso la hemos representado vacía). 0 Dirección de las paginas Conjunto de Paginas 9

Vacías

4

Proveedores

1

Piezas

6

Envíos

12

De todo esto se encarga el Gestor de Disco MISIONES DEL GESTOR DE DISCO • Mantener el orden lógico de la pagina (punteros). • Mantener información general de la pagina (pagina Ø). • Optimizar las Entradas/Salidas a nivel de pagina. MISIÓN DEL GESTOR DE FICHEROS El gestor de Ficheros debe de intentar mantener la secuencia lógica de los registros en las paginas. ¿Qué sucede si tenemos mas de un registro por pagina? − El RID tiene que ser invariable Registro S1 S2 S3 S4 S5

RID 11 12 13 14 15

Sí borro el S2 no puedo cambiar el numero de RID. Para que el RID no varíe almacenamos la posición, tenemos 1 registro donde hay tantas posiciones como registros entren en esa pagina cambio la información de la pagina. RID: Tiene el numero de la pagina Posición en la pagina / en vez de este tengo un puntero donde esta la posición de la pagina. Desde el Gestor de Ficheros solicito un registro almacenado y necesito saber donde es rápidamente el RID. Para ello hay dos tipos de técnicas para localizar el RID. • Indexación. • Técnicas de acceso directo o Hashing. 3.4 INDEXACIÓN Técnica que permite encontrar paginas de la forma más rápida que se pueda y por tanto el numero de operaciones de E/S.

10

Una tabla índice es un archivo almacenado cuyos registros almacenados se componen de dos partes: 1º parte del registro esta formado por un valor semántico. 2º parte esta formada por el RID que posee ese valor semántico Ejemplo. Empresa que necesita proveedores de muchas ciudades. Tendremos una tabla índice que apunta a archivos almacenados de proveedores Prov RID LU LU OU OU PO PO Prov# Pieza Cant Provincia S6 X 20 LU S1 X 10 OU S2 X 20 LU S3 Z 10 OU S4 W 30 PO S5 X 30 PO • En la tabla índice tienen que estar los valores ordenados de forma secuencial ordeno las ciudades alfabéticamente luego pongo su RID. • Si tuviéramos que hacer barrido secuencial seria fácil, es una ventaja que aporta la tabla índice. • Desventaja: Ocupa mucho espacio. • Puedo tener tantas tablas índice como campos tenga. Aquí como mucho tendría cuatro, también es un problema, por que genera mucho espacio. Las tablas índice también tiene las siguientes ventajas: • Facilidad de acceso secuencial en los registros se minimiza el numero de operaciones de E/S, la tabla índice es más pequeña y caben mas registros en una tabla y puedo leer mas registros de un tirón. • La búsqueda directa es simple, no me obliga a leer todas las paginas. Inconvenientes: • Ocupa mas espacio, hay mas archivos almacenados, tantos como índices tengamos. • Tenemos muchas tablas. Posible solución: Tablas índice múltiples. • Tamaño de las tablas. (Un registro en la tabla índice por un registro de la tabla a la que apunta) Para minimizar el problema usamos índices no densos. Esta manera los índices se llaman tablas de índices densos TABLAS DE ÍNDICES MÚLTIPLES 11

Suponemos Que hay que indexar por mas de un campo, la ciudad y el estado, por ejemplo. Se hace la búsqueda por un solo campo: o ciudad o estado. Ciud/Est RID LU/20 LU/20 OU/10 OU/10 PO/30 PO/30 TABLAS DE ÍNDICES NO DENSOS • Se utilizan para reducir el tamaño de las tablas índice y para ellos se utiliza el mayor valor que se almacena en una pagina. Ejemplo: • El tamaño de pagina permite almacenar tres registros por pagina entonces el RID seria (mostrado en la tabla) • Como funciona: Necesito el proveedor S7 miro en la tabla de índices densos y si no es mayor es cuando lo encuentro entonces voy a la pagina y solo leo esa. S# RID2 S1 11 S2 12 S3 13 S4 21 S5 22 S6 23 S7 31 S8 32 Prov# RID1 S3 S6 S8 ÁRBOLES B Son la clase de índices no densos más importantes, ya que la mayoría de los sistemas relacionables incluyen árboles B como principal estructura de almacenamientos (y en muchísimos casos la única) • Los árboles B son árboles equilibrados cuyos nodos son las paginas de sucesivas tablas índice siendo los nodos terminales del árbol las propias paginas de la tabla índice. Hago tablas mas pequeñas y las voy encadenando. (índices no densos) • Se denomina conjunto secuencia de un árbol B a los nodos terminales y conjunto índice a los nodos no terminales a si mismo la profundidad del árbol viene marcada por el numero de niveles. • El orden del árbol es el numero mínimo de anotaciones que hay en cada pagina.

12

3.5 DIRECCIONAMIENTO DIRECTO HASHING. • Permite obtener acceso directo rápido a un registro almacenado especifico en base a un valor dado por un cierto campo (clave). En el modelo relacional coincide con claves. • Tres etapas de acceso o tres pasos para asignar el RID: 1.− Cada registro almacenado se coloca en la Base de Datos en un lugar cuya dirección (RID) se calcula mediante una función, que se denomina algoritmo de direccionamiento (No permite la secuencialidad). 2.− El SGBD calcula la dirección (mediante ese algoritmo de direccionamiento) y le ordena al GF que lo grabe (el RID) en esa dirección calculada. 3.− Para localizar el registro a partir de la dirección el SGBD realiza el mismo calculo y le ordena al GF que lea el registro en la posición calculada. Si tengo una función que me genera el mismo RID, se dice que son sinónimos. Tienen tres problemas que vienen dados por el algoritmo de direccionamiento: • Encontrar una función de distribución eficiente. • Sinónimos. • Huecos. Hashing tiene problemas que vienen dados por el algoritmo de las direcciones si este no hace una distribución uniforme de las direcciones se producen colisiones, y a esto se le denomina sinónimos. La función devuelve el mismo RID para funciones distintas y se producen colisiones y a su vez se producen huecos, hay direcciones que nunca se ocupan. Para evitar los huecos y colisiones es necesario encontrar un buen algoritmo de almacenamiento. Los algoritmos de almacenamiento mas usados son: • Técnicas de direccionamiento aleatorio intentando minimizar el numero de colisiones. • Transformación de plegamiento: utilizada en claves que se almacenan en binario. Ejemplo: Utilizo 8 bits, se suman: 4+4=8 ! RID • Cuadros centrales: Se eleva al cuadrado la clave y se utilizan los dígitos centrales como dirección. Ejemplo: F = (3600)²= 129(600)00 600 es la dirección. • Métodos de convergencia. La Clave la multiplico por algo, le sumo algo y hago modulo de un numero primo y el resultado es la dirección 13

(ak + b)mod m • Desplazamiento 256381 lo voy sumando hasta dejarlos en el margen que yo quiera 256 + 381 = 637 63 + 7 = 70 (70) será el RID De todas formas siempre va a haber colisiones, por tanto hay que tener lo que se denomina zonas de desbordamiento o overflow, de manera que cuando se produce colisión el registro se almacena en esta zona de desbordamiento, pero a la hora de buscarlos si no está en la posición que le correspondería hay que hacer una búsqueda secuencial en la zona de desbordamiento y en el peor de los casos es hacer una búsqueda en toda la zona de desbordamiento. Otra posible solución es dejar huecos vacíos en las paginas de manera que cuando se produce una colisión lo almacena en esta página y así solo tendré una operación de E/S para buscar un registro (ya que está todo en la pagina). Pero si se llena la pagina pues haremos como antes en la zona de overflow. La desventaja es que se desperdicia mucho espacio. 3.6 CADENAS DE PUNTEROS Se utilizan cuando se trabaja con campos que no son claves para que sean eficientes estos campos deben contener pocos valores y repetirse mucho en los registros. Aparece como solución a las tablas con índices densos. En estas tablas hay que recolocar toda la información y con las cadenas de punteros lo que hacemos es: Archivo Ciudades Archivo Proveedores Problemas: Para leer un proveedor que esta en la posición n hay que leer antes los proveedores n−1, todos los que están antes. Además también hay otro problema. Por ejemplo, obtener la ciudad del proveedor S4, habrá que leer ciudad por ciudad, solución repetir el campo ciudad en el archivo proveedores. Para solucionar el problema de leer n−1 antes lo solucionamos con apuntadores simples a los padres. Ventajas: − Facilidad de inserción y borrado − Se pueden tener tantos índices como se quiera 3.7 TÉCNICAS DE COMPRENSIÓN • Permiten el ahorro de memoria masiva. • Hay tres técnicas: • Diferencial 14

• Jerárquica • Código Huffman Se basen las tres en el siguiente principio: Los valores de los datos casi nunca son completamente aleatorios si no que existe un grado de parecido que permite que exista secuencia entre ellos. • DIFERENCIAL Esta técnica consiste en remplazar cada valor del dado individual por alguna representación de la diferencia que existe entre el y el valor que lo precede. Tienen que estar ordenados de forma secuencial y alfabéticamente • DIFERENCIAL (Es igual al agrupamiento) Esta define de la forma que los registros se agrupan según una clave que contiene duplicados entonces se realiza una compresión dentro del archivo determinando registros de longitud variable que contienen 1 parte fija y otra variable. • CÓDIGO HUFFMAN Se base en la codificación interna de los datos, se trata de cambiar esa codificación de los registros. Los datos que mas se repiten tienen una codificación mas beneficiosa. Posibilidad REG E A D C B

Codificación de aparición 35% 30% 20% 10% 5%

1 01 001 0001 00001

−Le añado dígitos a aquellos que tengan menos probabilidad de aparición y así será mas rápido la operación de lectura.

TEMA 4 ESTRUCTURAS DE DATOS: DISTINTOS ENFOQUES 4.1 INTRODUCCIÓN 4.2 EL ENFOQUE RELACIONAL 4.3 EL ENFOQUE JERÁRQUICO 4.4 EL ENFOQUE EN RED 4.1 INTRODUCCIÓN 15

Ejemplo de diagrama de entidad−relación para proveedores−piezas. Diseño Lógico de la Base de Datos 4.2 ENFOQUE RELACIONAL Vamos a ver en como se trata cada uno de estos enfoques. Una base de datos relacional equivale a una tabla. La estructura básica de este enfoque es la tabla. (relación " tabla). Las tablas están formadas por filas y columnas, donde las filas son las ocurrencias de los distintos tipos de registros y las columnas son los atributos. Los atributos se definen sobre dominios. Dominio: Se define como deposito de valores del cual se obtienen los que aparecen en una columna especifica. Ejemplo: Dominio de color son azul, amarillo... Las tablas para nuestro diseño se representan: Cada entidad genera una tabla: S# NumS

Estado

P# NumP

Color Peso

S# P#

Ciudad

Cantidad

• Las conexiones generan tablas dependiendo de su cardinalidad, más concretamente cuando sus conexiones de cardinalidad de muchos a muchos. VENTAJAS: • Simplicidad de la representación, y por tanto simplicidad en su manejo. • Sus algoritmos son simétricos (es decir iguales son los algoritmos para las distintas entidades). Son iguales para una misma operación independientemente con la entidad que se trabaja. INCONVENIENTES: • Inserción: Habrá siempre problemas, ya que no se puede insertar un envío de una pieza o un proveedor que no existe • Borrado: Un envío se borra sin ningún problema, se borra la fila y ya esta. Para borrar un proveedor o una pieza hay que actualizar la información de envío eliminando las apariciones de proveedor o pieza. IMPORTANTE Relación " tabla " archivo secuencial. (en relación a las filas se le llama tupla)

16

Tupla " fila " registro Atributo " columna " campo 4.3 EL ENFOQUE JERÁRQUICO La estructura básica de este enfoque es el árbol. En nuestro caso con cardinalidad de mucho a muchos, en principio no podemos saber la cardinalidad del padre o la del hijo. Entonces la elección es aleatoria, podremos por ejemplo la pieza como padre. La implementación de este enfoque se puede hacer basándose en dos estructuras de datos: • Registros de longitud variable. • Cadena de punteros (es la que se implementa). Ponemos piezas como padre y proveedores como hijo. Ventaja: no crear nuevas entidades con los distintos proveedores se hace una cadena de punteros. Inconveniente: Los algoritmos son asimétricos, no es lo mismo insertar en el padre que un hijo. Algoritmos distintos para padre e hijo. Insertar: Cualquier padre, pero solo puedo insertar nuevos hijos si tienen padre. No puedo insertar ningún proveedor si no hay piezas. Borrado: Si borro una pieza, desaparece todo. Cuando se borra un padre se pierde información de los hijos que no aparece en otros padres, es un gran inconveniente. Modificación: Leo todas y cada una de las piezas para ver el proveedor, tengo que leer árbol a árbol para ver si el proveedor esta en cada una de las piezas. Si la relación es de 1 a 1: El problema de modificación desaparece pero el de borrado e inserción aun existen, pero es mucho menor, o de 1 a muchos es lo mismo. 4.4 ENFOQUE EN RED La estructura básica es el grafo. Aquí los datos, la información se representa mediante registros . Permite trabajar con cualquier tipo de cardinalidad. Para implementar las conexiones se utilizan un tipo de registros denominados conector. Desventaja: La complejidad Los algoritmos son simétricos, son listas conectando grafos. Inserción: Sencillas, sin problemas. Permite insertan cualquier tipo de registros sin que nadie lo suministre

17

Borrado: Fácil, lo borro, y sus hijos y ya esta. Modificación: También muy sencilla Modelo en red: Es bastante bueno, pero tiene un problema, que exige una gran cantidad de memoria. TEMA 5 EL MODELO RELACIONAL 5.1 ELEMENTOS DEL MODELO 5.2 ESQUEMA DE RELACIÓN 5.3 DEPENDENCIAS FUNCIONALES 5.4 DEPENDENCIAS TRANSITIVAS, DEPENDENCIAS PARCIALES, CLAVES. 5.5 CIERRE DE UN DESCRIPTOS RESPECTO DE UN CONJUNTO DE DEPENDENCIAS FUNCIONALES 5.6 RECUBRIMIENTO NO REDUNDANTE 5.7 PARTICIÓN FUNCIONAL 5.8 ALGORITMO DE SIMPLIFICACIÓN−REDUCCIÓN 5.9 ALGORITMO DE SÍNTESIS 5.1 ELEMENTOS DEL MODELO Todos los modelos de datos constan de tres partes. 1ª Parte: Modelo estructurado: Estructura de datos que va a soportar el modelo. 2ª Parte: Parte semántica, formado por el conjunto de restricciones que debe cumplir el modelo. 3ª Parte: Manipulativa, formada por el conjunto de operadores asociados al modelo. PARTE ESTRUCTURADA La estructura de datos para el modelo relacional es la relación. Ejem: A1 A2 A3 ... An a11 a21 a31 an1 a21 a22 a32 an2 a1m a2m a3m

anm

¿Como defino todos los valores de tabla?

18

Dominio (A1), que operación hago para que todos los dominios se relacionen, es mediante el producto cartesiano: R " Dom(A1) x Dom(A2) x x Dom(An) Relación: Es un subconjunto del producto cartesiano del dominio, donde el atributo A definido como cada caso particular de una dominio en una relación está restringido a tomar sus valores en un dominio. Los dominios de dos o mas atributos diferentes para una relación pueden ser iguales aunque no los nombres asociados a esos atributos. (No dos atributos iguales en una relación). Ejemplo: Nombre DNI Apellidos Nombre Apellidos y nombre si que tiene igual dominio. No puede haber dos atributos con el mismo nombre, no pueden existir dos Nombre. Grado: El grado de una relación es el valor `n', es decir el numero de atributos, mientras que la cardinalidad seria el numero de tuplas. El orden de las tuplas es irrelevante y por eso las tablas las vemos como si fueran conjuntos. • PARTE MANIPULATIVA Viene definida como el álgebra relacional. • PARTE SEMÁNTICA Clave: Se define como un conjunto mínimo de atributos cuyo valor determina el de todos los demás de las relación. Es equivalente a la clave candidata " clave. SuperClave: Es equivalente a la clave primaria. Clave elegida entre mis claves candidatas. El dominio sobre el que se definen los atributos de una clave primaria se denominan dominio primario. Para solventar problemas de inserción y borrado se definen dos reglas de integridad: 1ª Regla de integridad de entidad: Ningún valor de la clave primaria de la relación puede ser nulo o tener componentes nulos (desconocido, vacío). 2ª Integridad Referencial Intenta controlas las conexiones que existen entre las entidades. S# ... S1 A 19

P# ... P1 T

S# P# ... S1 P1 S# Es clave externa respecto al código del proveedor. P# Es clave externa respecto al código de la pieza.

Para poder haber en la 3 entidad una tupla S1 P1, S1 necesariamente tiene que existir en la 1 entidad y P1 tiene que existir en la 2 entidad. Supongamos que un atributo A es una clave primaria en una relación R y está definida en un dominio primario, entonces para cada valor A de A en R tiene que existir una relación S con clave primaria simple B tal que A ocurre como un valor de B en S. Al atributo A se le denomina clave externa de R respecto a S. 5.2 ESQUEMA DE RELACIÓN Dos ocurrencias R y R que pertenecen a un conjunto de atributos denominados T. R y R " T = { A1, A2, ... An,} verifican el mismo conjunto de reglas de integridad que vamos a denominas L y que está formado por las regla de integridad−entidad y regla de integridad referencial mas todas las restricciones que permiten definir la semántica del problema. (RE, RL, restricciones que definen la semántica del problema) Al par formado por el conjunto de atributos T y L se le denomina esquema relacional R(T, ). A cualquier subconjunto de T se le denomina descriptos Ejemplo S# S1 S2 S3 S4

NomS X Y X Z

Estado 10 20 20 10

Ciudad OU PO LU OU

x, y " T (Conjunto de atributos) x!y Si conozco x puedo saber de forma segura y. Esto significa dependencia funcional.

20

Ciudad ! Estado? No es cierto Estado ! Ciudad? No lo se por que no se si se puede repetir o no con toda seguridad S# ! NomS Si es cierto, por que teniendo el código del proveedor se con toda seguridad su nombre. NomS ! Ciudad? No, por que puede ser de Ou, Lu, etc y seguir siendo el mismo proveedor. S# ! Estado? S# ! Ciudad? Estas dos ultimas si son ciertas Ejemplo: Para las piezas que dependencias funcionales habría? P#! NumP, Color, Peso " P# ! NumP P# ! Color P# ! Peso Para el envío que dependencias funcionales hay? S# ! P# S#,P# ! Cantidad. S# ! Cantidad Ojo, no equivale a S# ! Cantidad, S# ! Cantidad Dependencia Funcional : Se representa x ! y donde x e y son descriptores que pertenecen a L (Conjunto de descriptores. Si para toda ocurrencia r de R el valor x determina unívocamente al valor y. (r : esquema de relaciones). x ! y (Conocido el valor de x conozco el de y) Dado un conjunto de dependencias funcionales L, este conjunto permite deducir nuevas dependencias funcionales, este nuevo conjunto se denomina cierre y se representa L+. Para deducir las dependencias funcionales tenemos lo que se denomina Axiomas de Amstrong. Estos axiomas son 5: • Reflexividad: "x, x ! y • Aumentatividad: Si x !y, x' ! y "x' " x Ejemplo: S# ! NomS S#, Ciudad ! NomS • Proyectividad: Si x ! y, x ! y' "y' " y 21

Ejemplo: S# ! NomS, Estado, Ciudad S# ! NomS S# ! Estado S# ! Ciudad • Adictividad: Si x !y, u !w ! xvu ! yuw • Transitividad: Si x ! y, y ! z ! x ! z • DEPENDENCIAS TRANSITIVAS, DEPENDENCIAS FUNCIONALES, CLAVES. Las dependencias transitivas crean anomalías en las tablas, por esto son muy importantes, se representan x− ! y, y se da entre dos descriptores x e y si solo si se cumple las siguientes condiciones. • Los descriptores son disjuntos x " y = Ø • z es disjunto respecto a x e y. "z: x"z = Ø; y"z = Ø • x ! z, z ! x; z ! y Ejemplo: S# − ! Ciudad E = estado S# ! Estado; Estado − ! S#; Estado ! Ciudad La dependencia x ! y es parcial si solo si existe un x' tal que x ! y es parcial si y solo si " x'/ x' " x ! x' ! y En caso contrario se dice que la dependencia es total y se representa así: x ! y. Clave: Un descriptor K " T es clave de R(T,) cuando se cumple lo siguiente: K ! T (Cuando no hay un subconjunto mas pequeño de K y todos los atributos dependen de la clave) Los atributos que dependen de las claves se denominan atributos principales y aquellos que no pertenecen a la clave se denominan no principales. • CIERRE DE UN DESCRIPTOS RESPECTO DE UN CONJUNTO DE DEPENDENCIAS FUNCIONALES Si un descriptor `x' y `L' un conjunto de dependencias funcionales, el cierre de `x' respecto a L (se pone X+) es un descriptor que verifica lo siguiente: (x ! x+) " L+ Con el cierre, así obtengo todos loa atributos que puedo obtener a partir de un descriptor. Además, el cierre tienen que ser máximo: x+ es máximo. −Algoritmo de cierre de un descriptor: Determina descriptores de la forma X(i) con la propiedad x ! x(i) " L+ de forma que x(i) = x(i−1) incrementando en los atributos Ak de la forma: 22

X(i) = X(i−1) " Ak / (u ! v) " L u " X(i−1) y Ak " v, partiendo de x(0) = x Si x(i−1) = x(i) ! x(i) = x+ El proceso es finito por que T es finito, el conjunto de atributos es finito (T). EJERCICIO: L: AB ! C D ! EG C ! A BE ! C BC ! D CG ! BD ABC ! B CE ! AG T: {A,B,C,D,E,G} • Calcular el cierre de BD: (BD)+. x(0) = BD x(1) = BDEG Aquí añado de los de arriba los que están contenidos x(2) = BDEGC en BD en la parte izquierda es así, por que conocida x(3) = BDEGCA la parte izquierda conozco la parte derecha x(4) = ABCDEG BD+ = BD Puedo decir que BD es clave, por que a partir de el obtengo todos los atributos. • Calcular el cierre de CE: (CE)+ x(0) = CE x(1) = CEAG x(2) = CEAG x(3) = ABCDEG Entonces CE también es clave. • Calcular el cierre de CD: (CD)+

23

x(0) = CD x(0) = CDB x(0) = CDB CD no seria clave, ya que con ella no obtengo T, el conjunto de todos los atributos. • RECUBRIMIENTO NO REDUNDANTE. Ejemplo: BC ! D A!D AC ! D Dependencia redundante Dos conjuntos de dependencias funcionales L y M son equivalentes si y solo si sus cierres son iguales. L y M son equivalentes sii L+ = M+. También se dice que L recubre a M y que M recubre a L. Esto sucederá cuando : " x ! y " L+ ! x ! y " M+ " u ! v " M+ ! u ! v " L+ Esta forma es muy complicada por que hay que calcular todos los cierres y hay una forma mejor. (X)+ respecto a M+ ! y " (X)+ ! x ! y " M+ (Calculo el cierre de x respecto a la dependencia M+) Se dice que un conjunto de dependencias funcionales M no es redundante si solo si ocurre: • Todas sus dependencias tienen que ser de la forma x ! Ai, es decir, los segundos miembros tienen que ser simples. • No pueden existir dependencias reduntandes. (x ! Ai) " M+ es redundante sii (M − (x ! Ai))+ = M+ Una dependencia es redundante cuando su eliminación no altera el cierre. • No pueden existir atributos extraños. Una atributo Bi es extraño en la dependencia x ! Ai si y solo si llamamos Z al descriptor z= x − {Bi} el cierre de M no se altera al sustituir x ! Ai por z ! Ai, es decir: (M − {x ! Ai} " {z ! Ai})+ = M+ (El cierre no varia) Ejemplo: 24

D!E D ! EG D!G BE ! C CG ! B CG ! BD CG ! D Si tengo ACD ! B y CD ! B Tengo que A es un atributo extraño, por que si ya puedo obtener B sabiendo solamente CD, A no me hace falta, y lo puedo eliminar. ALGORITMO QUE CALCULA EL RECUBRIMIENTO NO REDUNDANTE PARA UN CONJUNTO DE DEPENDENCIAS FUNCIONALES. Siempre existe recubrimiento no redundante en un conjunto de dependencias funcionales. El algoritmo consta de tres pasos: • Paso Para toda dependencia x ! y de L x!y"L"x!y"L Sustituimos x ! y por x ! A1, x ! A2,..., x ! Ar Donde A1, A2,..., Ar son atributos de y • Paso Para toda dependencia x ! Ai " L Calculamos x+ (cierre de x) respecto a (L(1) − { x ! Ai }) − Si Ai " x+ entonces x ! Ai es redundante y se elimina − Obtenemos un conjunto L(2) que es el resultante. • Paso " x ! Ai " L(2) Si Bi " x tal que z = x − {Bi} calculamos z+ (cierre de z) respecto a L2

25

Si Ai " z+, entonces sustituimos x ! Ai por z ! Ai . El resultado de esta sustitución daría como resultado L3 = M (recubrimiento no redundante). EJERCICIOS EN LOS FOLIOS ADJUNTOS DE EJERCICIOS (PAG. 1, 2) • ALGORITMO DE DETERMINACIÓN DE LAS CLAVES DE UN ESQUEMA Sea M un recubrimiento no redundante definimos atributos esenciales como aquellos que solo aparecen en el lado izquierdo de alguna dependencia funcional o bien o bien en ninguno. Atributos posibles, son aquellos atributos que aparecen a los dos lados de la dependencia funcional. Atributos no esenciales: Son aquellos que solo aparecen en el lado derecho de las dependencias y nunca aparecen en la clave. De estas definiciones obtenemos las propiedades. Atributo esencial: Pertenece a todas las claves. Atributo no esencial: No pertenece a ninguna de la claves. Atributo posible: No se sabe si pertenece o no a alguno clave excepto si esta incluido en el cierre de los esenciales, en cuyo caso no pertenecerá a ninguna clave. • ALGORITMO DE SIMPLIFICACIÓN−REDUCCIÓN Sea R el esquema relacional R = Donde: M = [xi ! Ai ] I = 1n (es el recubrimiento mínimo) Sigue en las fotocopias...< ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. EJEMPLO Y EJERCICIOS EN HOJAS DE EJERCICIOS (PAG 2 POR ATRÁS Y SIGUIENTES) • ALGORITMO DE SÍNTESIS EJEMPLO Y EJERCICIOS DEL ALGORITMO DE SÍNTESIS EN HOJAS DE EJERCICIOS (PAG 5 POR ATRÁS Y SIGUIENTES) • PARTICIÓN FUNCIONAL Basándose en el concepto de relaciones de equivalencia, son clases de equivalencia en una relación de equivalencia: Si tengo un conjunto de dependencias funcionales M lo descompongo en: 26

M: M1! K1 M1! K1 " Ki = K M1! K1 i=n ..................... M1! K1 En subconjuntos de dependencias funcionales Sea Fi una dependencia funcional de la forma si! xi y sea fi otra dependencia de la forma fj = sj! xj definimos la matriz de adyacencia y se representa ~ de la siguiente manera: fi ~ fi sii (si " xi)" (sj " xj) " 0 si tienen atributos comunes son adyacentes En caso contrario fi " fi sii (si " xi)" (sj " xj) " 0 si no tienen atributos comunes no son adyacentes Adyacentes . Esta relación es reflexiva y simétrica pero no transitiva para hacerla transitiva definimos la relación de transición y se representa ", de la forma: fi " fi sii fi ~ fi o bien "fki"ri=1 " tal que fi ~ fk1~ fk2~ ...~ fkr~ fj Al ser reflexiva, simétrica y transitiva es una relación de equivalencia, en la cual permite dividir a L en clases de equivalencia, de manera que partiendo de un esquema Ri(Ti, Li) "ri=1 Ki = K, de la forma que el calculo de la clave se resume en calcular el calculo de las claves de los subesquemas Ki, donde la unión de los Ki me da la clave del esquema R. La relación de adyacencia y la relación de conexión se representan mediante matrices donde las filas y las columnas están etiquetadas por las dependencias funcionales, de manera que un elemento vale un si: Adyacencia f1 f2 fr f1 f1 . fij = 1 sii fi " fi . fij = 1 sii no fi " fi . fr Ojo: para las conexiones es el mismo cuadro

Las combinaciones de unos y ceros de la matriz de conexión indican las clases de equivalencia, es decir: 001100 1 1 0 1 1 1 Si las 2 filas son iguales se trata de la misma clase 27

0 0 1 1 0 0 de equivalencia Me interesa que salgan muchas clases de equivalencia para reducir el numero de clases que tenemos que calcular. EJEMPLO EN HOJAS DE EJERCICIOS (PAG 8 POR ATRÁS) TEMA 6 EL ÁLGEBRA RELACIONAL • DEFINICIÓN INTUITIVA E INTRODUCCIÓN. • SÍNTESIS PARA EL MANEJO DE EXPRESIONES RELACIÓNALES. • LOS OPERADORES TRADICIONALES. • LAS OPERACIONES RELACIÓNALES TÍPICAS. 6.1 DEFINICIÓN INTUITIVA E INTRODUCCIÓN. Se basa en lenguajes imperativos de la forma K1" K2 − (R3) = RT. Los conjuntos de operadores son: • Unión (Union). • Intersección (Intersect). Se definen como conjuntos binarios • Diferencia (Minus). Conjuntistas o tradicionales • Producto cartesiano (Times). Y por otro lado tenemos: • Selección (Select) • Proyección Denominados operadores propios o • Reunión (Join) relacionales • División (Divide by) La unión de dos tablas es una nueva tabla que contiene las tuplas de unión de ambas tablas: R1 Union R2 La intersección da como resultado una tabla que contiene las tuplas que estas en R1 y en R2. La diferencia entre R1 y R2 son aquellas tuplas que están contenidas en R1 y no en R2. R1 Minus R2 El producto cartesiano crea una combinación de tuplas de manera que: A a b c

B x y z

times

28

C 1 2 Genera una nueva tabla de la forma: A a a b b c c

B x x y y z z

C 1 2 1 2 1 2

Selección: Consiste en la creación de filas de una selección de 1 relación, obtiene tuplas de una relación. Proyección : Obtiene columnas de una relación. Reunión: (Join) Consiste en reunir tablas, aquellas que tienen atributos en común. A B x 1 y 1 z 2 B1 B2 x a y b JOIN

C1 C2 C3 x a 1 y b 1 Reúne las tablas por valores de igualdad, no queda la columna duplicada. El atributo en común será la clave externa. División: (Divide by) A1 x x x y

B1 1 2 3 1 29

y z

2 3

Divide by C 1 2 3

.

D x

Solo vale x por que es el que tienen los valores 1,2,3 Da como resultado aquellos valores de atributos que tengan todos los atributos valores de la tabla divisor. 6.3 OPERADORES RELACIÓNALES TÍPICOS • Selección: R Where P Relación: Tabla donde se verifica un predicado P. Me devuelve aquellas filas donde se verifica esto. Ejemplo: Que proveedores hay en la ciudad de Ourense, devolver código de proveedor: S Where Ciudad = `Ou' Devuelve: S1 x 10 OU S2 y 20 OU Pero me falta sacar la columna, por eso necesito una proyección. (S Where Ciudad = `Ou') [S#] Entonces después de hacer esto nos devolvería solamente aquello que esta encuadrado: S1 x 10 OU S2 y 20 OU • Reunión: Ejemplo: Me piden proveedores que suministran piezas de color azul.

30

(S#, color = `Azul') P SP P# P1 P2 P3 S# S1 S1 S2

NombreP ColorPeso Tornillo Azul 10 Tuerca Rojo 20 Perno Azul 30 P# Cantidad P1 50 P3 60 P2 10

SP Join P (Where color = `Azul') Así obtengo una tabla donde luego hago la proyección tender S#, P#, Cantidad, Color, Peso, NombreP, la tabla resultante será: S# P# NombreP Color Peso Cantidad S1 P1 Tornillo Azul 10 50 S1 P3 Perno Azul 30 10 Pero aunque ya tengo los proveedores que suministran piezas de color azul, aun me falta proyectar: (SP Join P(Where color = `Azul'))[S#] • División: M + N (grado del dividendo: Numero de atributos) Ejemplo: Encontrar proveedores que suministren todas las piezas: S Divide By P = Divide el código del proveedor entre las piezas. No esta correcto, la operación por que no hay atributos con mismo dominio y además no tiene mayor grado sino igual grado. SP Divide By P = No por que el código del proveedor y cantidad no están en P y el dividendo no tiene mayor grado que el divisor. SP Divide By P [P#], [S#] = Correcto, tiene grado mayor, el divisor esta contenido en el dividendo. Me queda código del proveedor y cantidad entonces hay que proyectar por código de proveedor Hay otra forma de hacerlo: SP([S#, P#] Divide By P[P#]). Esta es equivalente a la de arriba. • Producto Cartesiano (Times). SP times S[S#] equivalente a tener una nueva tabla S# P# Cantidad S# 31

Tenemos dos atributos con distintos valores e igual nombre, la solución es etiquetar los productos con el nombre de su relación. SP.S# SP.P# SP.Cantidad S.S# Pero que ocurre si hacemos: SP times SP, lo que se hace es definir un apodo de la forma: define alias SP for envi de forma que la tabla resultante será: SP.S# SP.P# SP.Cantidad Envi.S# Envi.P# Envi.Cantidad Ejemplo: Encontrar parejas de proveedores que suministran la misma pieza: Define alias SP for ENVI (SP times ENVI Where (SP.P# = ENVI.P#)) [SP.S#, ENVI.S#] SP.S# S1 S1 S1 S1 S1 S1 S2 S2 S2

SP.P# P1 P1 P1 P3 P3 P3 P2 P2 P2

SP.cantidad 50 50 50 60 60 60 10 10 10

ENVI.S# S1 S1 S2 S1 S1 S2 S1 S1 S2

ENVI.P# P1 P3 P2 P1 P3 P2 P1 P3 P2

ENVI.cantidad 50 60 10 50 60 10 50 60 10

Y obtengo: S1 S1 S1 S1 S2 S2 S1 con S1 no es una pareja entonces no estaría bien

(SP Times ENVI Where (SP.P# = ENVI.P#)) [SP.S#, ENVI.S#] and (SP.S# == ENVI.S#) Así aun no estaría bien por que al ser así me daría aun las parejas S1 S2 S2 S1 Entonces tendré que poner:

32

(SP Times ENVI Where (SP.P# = ENVI.P#)) [SP.S#, ENVI.S#] and (SP.S# < ENVI.S#) Seria lo mismo < que >. TEMA 7 CÁLCULO RELACIONAL 7.1 INTRODUCCIÓN. 7.2 EL CÁLCULO DE PREDICADOS EN BASES DE DATOS RELACIONALES. 7.3 EL CÁLCULO RELACIONAL ORIENTADO A TUPLAS. SINTAXIS DE MANEJO. • INTRODUCCIÓN El cálculo relacional es una alternativa al álgebra relacional, pero el cálculo relacional se basa en lenguajes descriptivos, es decir nos indica aquello que queremos obtener. El cálculo relacional se divide en dos tipos: a) Calculo relacional orientado a tuplas: Se generan una serie de variables que se evalúan sobre las tuplas de una relación. Este calculo fue enunciado por Codd (1973) y dio un lenguaje denominado Alpha y en un Sistema de Base de Datos denominado Ingres. En 1977 Lacrorx y Piolte definen un nuevo tipo de calculo relacional. b) Calculo relativo orientado al dominio: Donde las variables se evalúan no sobre las tuplas si no sobre los valores de los atributos. • CALCULO DE PREDICADOS EN CASES DE DATOS RELACIONALES − El calculo de predicados son técnicas matemáticas que sirven para la representación del conocimiento. − Elementos del calculo de predicados: • Dominio del discurso: es un conjunto de objetos de nuestro mundo con una entidad propia. Ejemplo: personas, colores, coches... • Los objetos: Son las constantes de un dominio del discurso. Ejemplo: Colores: Azul, rojo, amarillo... • Las variables : son la representación en un momento dado de un objeto del dominio • Las funciones: permiten enlazar dominios Ejemplo: Padre: persona ! persona • El predicado: Son funciones cuya evaluación devuelve verdadero o falso Ejemplo: Padre (Juan, José) 33

Se puede representar mediante sentencias sencillas que se denominan formulas atómicas. Ejemplo: Escribió (Lorca, Yerma) = Verdadero Nació (Lorca, Sevilla) = Falso La fórmula atómica se combina mediante juntores: " (AND) " (OR) ~ (NOT) ! (IMPLICACIÓN) ~" Formando lo que se denominan formulas bien formadas (WFF) fa1 ! fa2 " ~ fa1" fa2. Ejemplo : Formula bien formada (WFF): Si suspendo BD o me meto un tiro o se lo meto al profesor. Suspende (yo, BD) ! (Pego (yo, yo) " Pego (yo, profesor)) Esto se puede sustituir por cualquier valor x!y O también se puede sustituir por variables que pueden estar o no cuantificadas, si la variable esta cuantificada se dice que es una variable ligada en caso contrario es una variable libre. Tenemos dos tipos de cuantificadores que me indican en que medida es cierta una formula que contiene variables, tenemos dos tipos: Cuantificador Universal: "x: Divide By "x: Join Ejemplo : Si hay un día cualquiera con lluvia entonces yo llevo paraguas (Hay (x, lluvia) ! Llevo (Yo, paraguas)) "x (Hay (x, lluvia) ! Llevo (Yo, paraguas)) que al menos uno de los días llevo paraguas o todos los días. Existe al menos un día o todos. "x (Hay (x, lluvia) ! Llevo (Yo, paraguas)): Todos los días que llueve llevo paraguas. • CALCULO RELACIONAL ORIENTADO A TUPLAS Las expresiones del cálculo de tuplas se construyen a partir de los elementos siguientes: 34

• Variables de tuplas T, U, V... Cada variable de tupla se restringe a variar sobre alguna relación con nombre. Si la variable de tupla T representa a la tupla t, entonces la expresión T.A representa al componente A de t, donde A es un atributo de la relación sobre la cual varía T. • Condiciones de la forma x*y donde * es cualquiera de los símbolos =, <>, <, <=, >, >=, y al menos una entre la otra es una expresión semejante o una constante. • Formulas bien formadas. Variables libre y acotadas Cada ocurrencia de una variable de tupla dentro de una FBF es libre o acotada. • Dentro de una condición, todas las ocurrencias de las variables de tupla son libres. • Las ocurrencias de las variables de tupla en las FBFs (f), ~(f) son libres / acotadas según sean libres / acotadas en f. Las ocurrencias de las variables de tupla en las FBFs (f " g), (f " g) son libres / acotadas según sean libres/ acotadas en f o en g (cualquiera de las dos en donde aparezcan). • Las ocurrencias de T que sean libres en f son acotadas en las FBFs "T(f), "T(f). Una expresión del cálculo de tuplas es de la forma T.A, U.B, , V.C [WHERE f] Donde T, U, ... , V son variables de tupas; A, B, ... , C son atributos de las relaciones asociadas, y f es un FBF que contiene exactamente T, U, ... , V como variables libres. El valor de esta expresión es una proyección del subconjunto del producto cartesiano T. x U x ... x V para la cual f se evalúa como verdadera. SINTAXIS BNF PARA CALCULO RELACIONAL ORIENTADO A TUPLAS • rel−definicion ::= DEFINE RELACION nom−rela [nom−atributos] • var−definicion ::= RANGE OF nom−var IS expr • expr ::= objetivo | objetivo WHERE wff • objetivo ::= nom_variable . nom_atributo • wff::= predicados | (wff) | ~(wff) | wff " wff | wff " wff | wff ! wff | " nom−variable(wff) | " nom−variable (wff) • Predicado::= objetivo compa objetivo | objetivo compa consonante • Compa::= = | > | < | <> | >= | <= TEMA 8 TEORÍA DE DISEÑO DE BASES DE DATOS RELACIONALES (I) • DESCOMPOSICIÓN DE ESQUEMAS. • DESCOMPOSICIÓN CON LA PROPIEDAD DE UNIÓN SIN PERDIDA DE INFORMACIÓN (LJ). • TEST DE LA PROPIEDAD LJ. • DESCOMPOSICIÓN CON PRESERVACIÓN DE DEPENDENCIAS. • ALGORITMO DE TEST DE PRESERVACIÓN DE DEPENDENCIAS. • FORMAS NORMALES BASADAS EN DEPENDENCIAS FUNCIONALES. • FORMAS NORMALES DE CODD. • PRIMERA FORMA NORMAL (1FN). • SEGUNDA FORMA NORMAL (2FN). • TERCERA FORMA NORMAL (3FN). • FORMA NORMAL DE BOYCE−CODD (FNBC) • ALGORITMO DE DESCOMPOSICIÓN EN FNBC CON LA PROPIEDAD LJ. • DESCOMPOSICIÓN EN 3FN DE CODD CON PRESERVACIÓN DE DEPENDENCIAS. 35

• DESCOMPOSICIÓN EN 3FN DE CODD SON PRESERVACIÓN DE DEPENDENCIAS Y VERIFICACIÓN DE LA PROPIEDAD LJ. 8.1 DESCOMPOSICIÓN DE ESQUEMAS R(T,L) L = { S# ! NOMS, ESTADO, CIUDAD ESTADO ! CIUDAD P# ! NOMP, COLOR, PESO S#, P# ! CANTIDAD} L = { R1, R2,, Rk} Sea R(T,L) un esquema que presenta anomalías de inserción, borrado y modificación podemos descomponerlo en un conjunto de proyecciones para evitar las anomalías anteriores. Anomalía de inserción: Se define como la perdida de información producida por la imposibilidad de insertar una tupla en una relación al no conocerse el valor de algún atributo primario. Anomalía de borrado: Pérdida de información como consecuencia del borrado de una tupla. Anomalía de modificación: Necesidad de propagar modificaciones debido a un diseño redundante. Al proceso de descomposición de R en sus proyecciones (sin anomalías) se le denomina NORMALIZACIÓN, es la base para el diseño de la base de datos. Puede suceder esto: "r "R ! r " R1[T1] JOIN R2[T2] JOIN JOIN Rk[Tk] "r "R ! r " R1[T1] JOIN R2[T2] JOIN JOIN Rk[Tk] No se puede perder (o ganar) tuplas que están en el esquema original. 8.2 DESCOMPOSICIÓN CON LA PROPIEDAD DE UNIÓN SIN PÉRDIDA DE INFORMACIÓN (LJ: Lossless Join) Sea el esquema R(T,L), L = { R1, R2,..., Rk} descomposición de R(T,L), Ri(Ti,, Li) especificación del esquema i−ésimo, decimos que f es una descomposición que cumple la propiedad de unión sin pérdida de información (LJ) respecto de L si y solo si para toda ocurrencia r " R se cumple que: r = R1[T1] JOIN R2[T2] JOIN JOIN Ri[Ti] JOIN JOIN Rk[Tk] Reunión de los atributos de los subesquemas 8.3 TEST DE LA PROPIEDAD LJ

36

Sea el esquema R(T,L), T = { A1, A2, ... ,An}, L = {x ! y " L / x " y " T}, l = { R1, R2, ... , Rk} descomposición de R(T,L), el algoritmo LJ es: Para verificar el cumplimiento de l de la propiedad LJ se construye una tabla donde las columnas son etiquetadas con los atributos de T y las filas etiquetadas con los atributos pertenecientes a cada uno de los subesquemas. En la intersección de ambas se sitúan el símbolo aj si el atributo Aj " Ti y el símbolo bij en caso contrario aj si Aj " Ti bij si Aj " Ti (i fila, j columna) Consideramos a continuación cada una de las dependencias x ! y de L, cada vez que consideramos una dependencia procedemos de la siguiente manera, si encontramos dos o mas filas que coincidan en las entradas correspondientes a x igualamos las correspondientes a y de la forma siguiente: Si un símbolo es aj hacemos su homologo = aj Si ambos son de tipo b igualamos el subíndice de uno de ellos a los del otro, se repite hasta que la tabla no varie. Si finalmente se encuentra una fila de la forma : (a1, a2, ... , an) la descomposición verifica la propiedad LJ y no la verifica en caso contrario. ALGORITMO Y EJEMPLO EN HOJAS DE EJERCICIOS (PAG. 9) 8.4 DESCOMPOSICIÓN CON PRESERVACIÓN DE DEPENDENCIAS. Sea el esquema R(T,L) donde L = {x ! y / x " y " T}, l = { R1, R2, ... , Rk}, Ri (Ti, Li) esquema i−ésimo. Li = {xi ! yi / xi " yi " Ti} k Existe presenvacion de dependencias sii ( " Li)+= Li+ i=1 8.5 ALGORITMO DE TEST DE PRESENVACIÓN DE DEPENDENCIAS Veremos un algoritmo de preservación de dependencias de orden polinomial. Este algoritmo k calcula el diere de un descriptor x respecto a " Li sin necesidad de calcular L+, para ello hace uso de T− i=1 operación de la siguiente manera: 37

Sea Z un descriptor repecto del conjunto de dependencias funcionales L, defiimos T−operación como la sustitución de z por z " ((z^t)+ ^ T) donde el cierre se calcula respecto L. El proceso se repetirá tantas veces como subesquemas haya. Si al calcular la primera iteración z no cambia el resultado seria el k cierre de z respecto a (" Li). i=1 En casa etapa se modifica el valor del descriptor al aplicar las K−Ti−operaciones para i=1 hasta k, k si al calcular una etapa no hubiese cambio el resultado es el cierre de z respecto a (" Li), de manera que si i=1 k y <= z final ! la dependencia x!y " (" Li), se preserva. i=1 "x!y " L, y " z final, entonces se preservan las dependencias y no lo harán en caso contrario. 8.6 FORMAS NORMALES BASADAS EN DEPENDENCIAS FUNCIONALES 8.6.1 FORMAS NORMALES DE CODD 5FN 4FN FNBC 3FN 2FN 1FN 8.6.1 PRIMERA FORMA NORMAL (1FN) Un esquema R(T,L) está en 1FN cuando todas sus entradas son simples " grupos repetitivos. Los valores de un atributo tienes que ser unicos. 8.6.2 SEGUNDA FORMA NORMAL (2FN) Un esquema R(T,L) que está en 1FN está en 2FN cuando todos los atributos que no pertenecen a la clave primaria tienen una dependencia funcional total respecto de cada una de las claves.

38

No se permiten dependencias funcionales parciales respecto de la clave primaria. 8.6.3 TERCERA FORMA NORMAL (3FN) No puede existir dependencias funcionales transitivas respecto de la clave primaria. De esta forma se normalizan la mayoría de las Bases de Datos pero hay tres casos especiales. • 3FN • Mas una clave • Atributos solapados. 1FN: Un esquema R(T,L) está en 1FN cuando todas las entradas son simples, no aparecen grupos repetidos. 2FN: Un esquema R(T,L) que está en 1FN lo está en 2FN cuando todos sus atributos no principales tienen dependencia funcional total respecto a cada una de las claves. 3FN: Un esquema en 2FN está en 3FN cuando ningún atributo no principal depende transitivamente de ninguna clave. Cuando no existe ninguna dependencia funcional transitiva respecto de la clave primaria. FNBC: Un esquema en 1FN está en FNBC cuando para toda dependencia funcional no trivial x ! y, x es clave. y"x x ! y Trivial si y solo si y=0 SEGUNDA FORMA NORMAL Diagrama funcional: Hay anomalías de inserción, borrado y modificación debido a una dependencia transitiva entre proveedor y estado y ciudad. Para eliminas esta dependencia transitiva se descompone en: Un esquema R(T,L) esta en 3FN si está en 2FN y si no existen dependencias funcionales transitivas respecto a la clave primaria. Con estas tres formar normales se normalizan todos los problemas. Hay tres casos especiales que estas tres formas normales no dan resultados idóneos: 1º Caso: Tenemos mas de una clave candidata, estas son compuestas (mas de un atributo) y además se solapan 2º Caso: Existen redundancias y la tabla está en 3FN, además hay tres atributos principales donde dos de ellos son independientes entre si y a su vez dependen del tercero. 3º Caso: Un esquema que no se puede descompones en dos subesquemas pero si es mas de dos. Dado un estudiante y una materia solo " un profesor: Dado un estudiante y un profesor solo existe una materia:

39

Están en 1FN, en 2FN y en 3FN. Para este caso aparece la FN de BOYCE−CODD (FNBC), dice: Un esquema R(T,M) en 1FN está en FNBC si para toda dependencia no trivial ("x ! y " L no trivial), x es clave. 1FN 2FN 3FN FNBC Toda FNBC está en 1FN, en 2FN y en 3FN. 2FN: Un esquema R(T,L) que está en 1FN lo esta en 2FN cuando todos sus atributos no principales tienen dependencia funcional total respecto a cada una de las claves. 3FN: Un esquema en 2FN está en 3FN cuando ningún atributo no principal depende transitivamente de ninguna clave. Cuando no existe ninguna dependencia funcional transitiva respecto de la clave primaria. FNBC: Un esquema en 1FN está en FNBC cuando para toda dependencia funcional no trivial x ! y, x es clave. y"x x ! y TRIVIAL si y solo si y=0 EJERCICIO PROPUESTO: Toda relación binaria esta en FNBC. Explicación de la afirmación anteriormente citada. Relación trivial: y"x x ! y TRIVIAL si y solo si y=0 Ejemplo: AB ! B AB ! A AB ! AB AB ! Ø

40

8.7 ALGORITMOS DE DESCOMPOSICIÓN EN FNBC CON LA PROPIEDAD LJ No preservan dependencias. Sea R(T,m) donde `m' es un recubrimiento no redundante, si existe una dependencia X ! A que pertenece a m donde X no es clave primaria, proyectamos R en R1 y R2 donde T1 = X " {A} (atributos de la dependencia) y T2 = T − {A} (atributos de la dependencia excepto la parte derecha que hemos escogido) y cumpliendo (T1 " T2) ! (T1 − T2). El ejercicio acabará siempre: Si " k ! A ; Si " k ! A EJERCICIO: Sea R(T,m) donde: T = curso, profesor, hora, aula, estudiante y grado. Restricciones semánticas: • Cada curso es impartido por un solo profesor. • A una hora y en un aula se imparte un solo curso. • A una hora un profesor está en una sola aula. • Cada estudiante tiene un grado por cada curso que sigue. • A una hora cada estudiante está en una sola aula. Obtener la descomposición en FNBC. Pasos a seguir: • obtener las dependencias. • Obtener recubrimiento no redundante. • Obtener clave. Resuelto en hojas de ejercicios pagina 11 por detrás y siguientes.

PUNTOS 8.8 Y 8.9 NO SE DONDE ESTÁN, PQ AQUÍ DESDE LUEGO QUE NO ESTÁN .................................................................. ............................................................................................................................................................................................... TEMA 9 TEORÍA DEL DISEÑO DE BASES DE DATOS RELACIONALES (II) • DEPENDENCIAS MULTIVALORADAS. • CUARTA FORMA NORMAL(4FN). • DESCOMPOSICIÓN EN 4 FN CON VERIFICACIÓN DE LA PROPIEDAD LJ. • DEPENDENCIAS MULTIVALORADAS EMBEBIDAS. • DEPENDENCIAS DE UNIÓN (DU). • QUINTA FORMA NORMAL (5FN). 9.1 DEPENDENCIAS MULTIVALORADAS.

41

Se desea diseñar una Base de Datos formada por profesores, materias y libros con las siguientes restricciones: • Un profesor puede impartir mas de una materia • Para una materia habrá mas de un libro y este puede ser compartido por varias materias. LIBRO AUTOR −−−−−−−−−−−−− * PROFESOR AP −−−−−−−−−−− *

MATERIA

MATERIA−−−−−−−−−− * IMPARTE AP AUTOR MATERIA * * *

MATERIA

PROFESOR LIBRO DATO J.F.

PRIETO

V.W

FDEZ

V.W.

PRIETO

BD I. GRAFICA

RDGUEZ Lo primero que tengo que hacer es pasarlo a primera forma normal (1FN) MATERIA PROFESOR LIBRO BD JF PRIETO BD

JF

DATA

BD

JF

FDEZ

BD

VW

PRIETO

BD

VW

DATA

BD

VW

FDEZ

IG

VW

PRIETO

IG

VW

RDGUEZ

42

No existe ninguna dependencia funcional, pero hay muchísima redundancia, así que descomponemos la tabla: MATERIA BD

PROFESOR JF

BD

VW

IG MATERIA

VW LIBRO PRIETO

BD BD BD IG IG

DATA FDEZ PRIETO RDGUEZ

Y así eliminamos la redundancia. Esto se llama dependencia multivalorada (siempre entre tres atributos donde dos de ellos son independientes entre sí, pero a su vez dependen del tercero). En este caso son independientes Profesor y Libro pero dependen los dos de Materia. Toda Dependencia funcional es una dependencia multivalorada, pero no al revés, solo en el caso de que sean dos atributos. DV DMV DF Las dependencias MULTIVALORADAS son una generalización de las dependencias funcionales en el sentido en que toda dependencia funcional es una dependencia multivalorada aunque no toda dependencia multivalorada es una dependencia funcional. Las dependencias MULTIVALORADAS se dan entre tres atributos y se representan de la siguiente manera: A!B|C MATERIA ! PROFESOR | LIBRO Y se leen de la forma: se dice que el atributo B o el atributo C es multidependendiente del atributo A, o bien que A multidetermina al atributo B o al atributo C. Dependencia multivalorada de un esquema R(T,L) donde T = {A, B, C} de la siguiente manera. A ! B se cumple en el esquema R si y solo si el conjunto de valores de B correspondiente al par valor de A, valor de C en R depende solo del valor de A y es independiente del valor de C, donde A, B y C pueden ser atributos compuestos. 43

9.2 CUARTA FORMA NORMAL (4FN) Un esquema R(T,L) con atributos A, B y C se puede descompones en dos proyecciones que verifican la propiedad LJ del tipo: R1(A, B) y R2(A,C) si y solo sí en R se cumple las dependencias multivaloradas A ! B | C Un esquema R(T,L) esta en 4FN si y solo si siempre que exista una dependencia multivalorada en R tipo A ! B todos loa atributos de R dependen también funcionalmente de A, es decir, las únicas dependencias funcionales o multivaloradas en R son de la forma k! x, o sea, una Dependencia Funcional con respecto a una clave candidata k de algún otro atributo x. O lo que es equivalente: el esquema R esta en 4FN si esta en FNBC y todas las dependencias multivaloradas en R son de hecho dependencias funcionales. 9.3 DESCOMPOSICIÓN EN 4 FN CON VERIFICACIÓN DE LA PROPIEDAD LJ. El algoritmo es el mismo que el de FNBC. Sea el esquema R(T,L), si R no es un esquema en 4FN tendrá al menos una dependencia multivalorada de la forma x ! y que no es trivial y con x no clave primaria. Descomponemos el esquema R en dos subesquemas: R1 y R2 donde T1 = {x " y} y T2 = T − {y} de esta manera verifica la propiedad LJ. EJEMPLO EN LAS HOJAS DE EJERCICIOS PAG. 14 POR DETRÁS. 9.4 DEPENDENCIAS MULTIVALORADAS EMBEBIDAS. Se entiende por aquellas que aparecen en el proceso de descomposición de une esquema en subesquemas. EJEMPLO EN LAS HOJAS DE EJERCICIOS PAG. 15. 9.5 DEPENDENCIAS DE UNIÓN. PROV PIEZAS PROYECTO SANCHEZ TORNILLO PROY X SANCHEZ PERNO

PROY Y

PEREZ

TORNILLO PROY Y

GARCIA

PERNO

PROY Z

PEREZ

TUERCA

PROY X

PEREZ

TORNILLO PROY X

SANCHEZ TORNILLO PROY Y PROV PIEZA SANCHEZ TORNILLO SANCHEZ PERNO 44

PEREZ

TORNILLO

PEREZ

TUERCA

GARCIA PERNO PIEZA PROYECTO PROY X TORNILLO TORNILLO

PROY Y

PERNO

PROY Y

PERNO

PROY Z

TUERCA

PROY X

J O I N PROV PIEZA PROYECTO SANCHEZ TORNILLO PROY X SANCHEZ TORNILLO PROY Y SANCHEZ PERNO

PROY Y

SANCHEZ PERNO

PROY Z

PEREZ

TORNILLO PROY X

PEREZ

TORNILLO PROY Y

PEREZ

TUERCA

PROY X

GARCIA

PERNO

PROY Y

GARCIA

PERNO

PROY Z

Este es el resultado al realizar el JOIN de las dos tablas de arriba, pero esto no es correcto, por que aparecen tuplas espureas. Y estas no deberían aparecer, por lo cual tenemos que encontrar otra solución. Tuplas espureas.

La solución es añadir a las dos tablas anteriores (Proveedor−Pieza, Pieza−Proyecto) una tercera con 45

Proveedor−Proyecto, y así arreglaríamos el problema. PROV PROYECTO SANCHEZ PROY X SANCHEZ PROY Y PEREZ

PROY Y

PEREZ

PROY X

GARCIA

PROY Z

Y así al realizar el JOIN entre las tres tablas nos daría el resultado buscado. PROV PIEZA PROYECTO SANCHEZ TORNILLO PROY X SANCHEZ TORNILLO PROY Y SANCHEZ PERNO

PROY Y

PEREZ

TORNILLO PROY X

PEREZ

TUERCA

PEREZ

TORNILLO PROY Y

GARCIA

PERNO

PROY X

PROY Z

¿Pueden existir dependencias funcionales embebidas? No nunca, las Dependencias Funcionales dependen de la naturaleza de los datos y las Dependencias Multivaloradas dependen del contexto. Las Dependencias de Unión aparecen para dar respuesta a aquellos esquemas que tienen redundancias, pero no contienen ni Dependencias Funcionales ni Dependencias Multivaloradas, estos esquemas no se pueden descomponer en dos subesquemas, si no en mas de dos, para manejas estos casos anómalos tenemos las dependencias de reunión o unión y la Quinta Forma Normal (5FN). Una Dependencia de Union (DU) definida mediante la sentencia: DU (R1, R2, ... , Rn) Donde las Ri son esquemas de relación de R que especifican un conjunto de tuplas r " R donde este conjunto de tuplas original de R1, R2, ... , Rn, de la siguiente manera, el conjunto de tuplas original R se forma a través de la proyección R1[T1] JOIN R2[T2] JOIN ... JOIN Rn[Tn]. Las Dependencias Multivaloradas es un caso especial de la Dependencia de Unión para cuando n=2. Una Dependencia de Unión es trivial si alguno de los esquemas de relación Ri es igual a R. 46

• QUINTA FORMA NORMAL (5FN). También llamada Forma Normal de Proyección−Unión, se define de la siguiente manera: Un esquema R(T,L) esta en 5FN con respecto al conjunto L de Dependencias Funcionales, Dependencias Multivaloradas, y Dependencias de Unión si para toda Dependencia de Unión NO TRIVIAL, DU (R1, R2, ... , Rn) en L+ cada Ri es una clave primaria de R. TEMA 10 SEGURIDAD E INTEGRIDAD • INTRODUCCIÓN. • SEGURIDAD: CONSIDERACIONES GENERALES. • INTEGRIDAD: CONSIDERACIONES GENERALES. • CONSIDERACIONES FINALES. 10.1 INTRODUCCIÓN. Seguridad: Es la protección de los datos contra una alteración, destrucción o revelación no autorizada. Integridad: Exactitud o validez de los datos. Implicaciones de la Seguridad e Integridad. La seguridad que los usuarios estén autorizados para realizar lo que pretenden hacer. La integridad implica asegurar que los que tratas de hacer es correcto. Similitudes entre Seguridad e Integridad. • En ambos casos el sistema necesita saber las restricciones que los usuarios no deben violar. • El Sistema de Gestión de Base de Datos será el encargado de que la interacción con los usuarios cumpla las restricciones. 10.2 SEGURIDAD. CONSIDERACIONES GENERALES • Aspectos sociales, legales y éticos. • Controles físicos. Quien tiene acceso al espacio donde esta la Base de Datos. Se refiere al espacio físico, donde esta el `ordenador' que contiene la Base de Datos. • Cuestión de Política interna. Que usuarios pueden acceder a que datos y como accede. • Problemas de operación. Tratamiento de contraseñas. • Controles de equipos. Dependiendo de las características de CPU pudiéramos considerar el área de almacenamiento para cada usuario. • Seguridad del Sistema Operativo. Poder borrar el contenido de las áreas de almacenamiento cuando ya no se necesita. • Materias de relevancia especificas para el Sistema de Gestión de Base de Dato. Propiedad de los datos. La unidad de información para seguridad puede ir desde un conjunto de tablas hasta un valor determinado. Así un usuario tendrá diferentes autorizaciones, según con los objetos de información que trate, a esto se le denomina propiedad de los datos. Hay que tener en cuenta que diferentes usuarios pueden tener diferentes derechos sobre un mismo objeto de información. Las decisiones de que derechos se le pueden conceder a cada usuario dependen de la política interna de la empresa. Para llevar a cabo que las decisiones de la política interna de la empresa se lleve a cabo por el Sistema de Gestión de Bases de Datos, este debe saber estas decisiones y debe ser capaz de recordarlas, y además, debe existir alguna forma de verificar una 47

solicitud de acceso dada contra las restricciones de seguridad aplicables. Para saber que restricciones se le aplican a una solicitud, no basta con saber que solicitud es, si no también quien lo hace. 10.3 INTEGRIDAD. CONSIDERACIONES GENERALES 10.4 CONSIDERACIONES FINALES. Seguridad: Protección de la Base de Datos contra usuarios no autorizados. Integridad: Protección de la Base de Datos de usuarios autorizados. Tanto la seguridad con la integridad implican: • La definicion de restricciones • Especificar las medidas a tomar si se violan las restricciones. • Suspensión por parte del sistema de las operaciones de los usuarios para detectar tales violaciones. Pagina 16 Proveedores Partes Vbo de casi Lugares Departamentos Empleados Proyectos U1 BD1 U4 U3 U2 SGBD GESTOR DE FICHEROS (G.F.) GESTOR DE FICHEROS (G.F.) B.D. Almacenamiento Físico Solicita 1 pagina 48

ATENAS PARIS LONDRES SALAZAR S1 20 S1 ACTIVA 30 S1 S1 CORONA JAIMES 100 40 S# Cantidad NumP NumS Ciudad Peso Estado Color P# Proveedores Envío

49

Proveedores Tuerca P1 1 10 S1 S2 S5 −−−−−−−−−− −−−−−−−−−−− −−−−−−−−−−− 100 100 100 R Tornillo P3 10 S1 −−−−−−−−−−− 100 S4 −−−−−−−−−−− 100 P2 Perno

50

R 20 CANTIDAD S# P# NOMS CIUDAD LOCALIZ NOMP COLOR PESO LOCALIZ CIUDAD NOMS S# PESO COLOR NOMP P# CANTIDAD S# P# S# NOMS CIUDAD CIUDAD

51

LOCALIDAD 1FN 2FN 3FN FNBC S# NOMS ESTADO CIUDAD ESTADO NOMS S# S# CIUDAD E M P M P E K, A K!A K: K K Ø K: K

52

MATERIA PROFESOR LIBRO AP MATE AUTOR IMPARTE PROV PIEZA PROYECTO

53