Elementos de Bases de Datos

Vista previa del material en texto

1
Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación
Elementos de Bases de Datos – 2do. Cuatrimestre de 2004
Elementos de 
Bases de Datos
Dpto.Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Lic. María Mercedes Vitturini
[mvitturi@cs.uns.edu.ar]
Clase 13 1er. Cuatrimestre de 2004
Elementos de Bases de Datos 
Clase 13 2
Ingeniería de Software
Es un área de las ciencias de la 
computación.Trata sobre la construcción de 
sistemas de software tan grandes y 
complejos que requieren de un grupo de 
ingenieros.
Características:
Es esencialmente una actividad en equipo: un 
ingeniero de software desarrollará un componente 
de software que se combinará con otros 
componentes desarrollados por otros ingenieros.
Existen versiones del producto.
Requiere de un trabajo disciplinado.
Elementos de Bases de Datos 
Clase 13 3
Es una propiedad que debe satisfacer un 
producto o un proceso.
Calidad ...
Se busca desarrollar productos de 
ingeniería de software de alta calidad.
Existen diferentes enfoque de calidad 
para un producto de ingeniería.
Elementos de Bases de Datos 
Clase 13 4
Principios, Metodología y 
Herramientas de Ing.SW
Principio
Métodos y técnicas
Metodología
Herramientas
Elementos de Bases de Datos 
Clase 13 5
Principios
Rigurosidad y formalismo.
Separación de intereses.
Modularización.
Manejo de abstracciones.
Anticipo al cambio.
Generalidad.
Incrementalidad.
Elementos de Bases de Datos 
Clase 2
Sistemas Automatizados
Sistemas automatizados: son sistemas 
construidos por el hombre que interactúan o son 
controlados por una o más computadoras. 
Principios generales de los sistemas:
Cuanto más especializado es un sistema, menos 
capacidades tendrá de adaptarse a diferentes 
circunstancias.
Cuanto más grande es un sistema, más recursos 
necesita.
Los sistemas son parte de un sistema mayor y 
generalmente pueden dividirse en subsistemas.
Los sistemas tienden a crecer.
2
Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación
Elementos de Bases de Datos – 2do. Cuatrimestre de 2004
Elementos de Bases de Datos 
Clase 13 7
Ciclo de Vida
Definición: Se define como ciclo de vida al 
proceso que implica la construcción de un 
producto, desde su inicio hasta que deja de 
usarse.
En la construcción de cualquier producto se 
sigue una secuencia de pasos para lograr 
cada tarea
El proceso de desarrollo del software se 
denomina ciclo de vida del software.
Elementos de Bases de Datos 
Clase 13 8
Comparación de los Modelos
Modelo Conducido por Observaciones 
Cascada Documentación Rígido. 
Puede haber problemas de 
integración 
Evolutivos Incremento funcional Los problemas se descubren 
antes. 
Utiliza técnicas de prototipeo 
Transformacional Especificación Sólo se aplica a problemas 
formales 
Espiral Riesgo Es un metamodelo 
 
 
Elementos de Bases de Datos 
Clase 13 9
Estructura general de un sistema
Interfaces de
Aplicación
Programas de
Aplicación Consultas
Esquema de 
Base de Datos
Usuarios
Ingenuos
Programadores
de Aplicación
Usuarios
Sofisticados
Administrador
de la BD
Usuarios
Código Objeto de
Prog.de Aplicación
Precompilador
Embebido de LMD 
Compilador
de LMD
Intérprete
de LDD
Motor de
Evaluación de Consultas
Gestor de
Transacciones
Gestor de
Buffers
Gestor de Archivos
Archivos de Datos Indices Datos Estadísticos Diccionario de Datos
G
es
to
rd
e
C
on
su
lta
s
G
es
to
rd
e
Al
m
ac
en
am
ie
nt
o
SMBD
Almacenam.
Elementos de Bases de Datos 
Clase 13 10
Entidades y Conjuntos de Entidades
Entidad: es un objeto que existe y es distinguible de 
otros objetos.
Miguel Montero, con número de CUIL 20-22134567-1 es
una entidad ya que identifica únicamente a una persona en 
el universo.
Conjunto de Entidades: es un conjunto de entidades
del mismo tipo.
El conjunto de todas las personas que tienen cuenta en un 
banco define al conjunto de entidades Cliente.
El conjunto de todas las cuentas de un banco define al 
conjunto de entidades Cuenta.
Elementos de Bases de Datos 
Clase 13 11
Modelo Entidad-Relación
Relación: es una asociación entre varias entidades.
Conjunto de relaciones: son varias relaciones de un 
mismo tipo.
Formalmente, si E1, E2, …, En (n > 1) son conjuntos de 
entidades entonces el conjunto de relaciones R es un 
subconjunto de:
{(e1,e2,…,en): e1 ∈ E1, e2 ∈ E2,…, en ∈ En}
Ejemplos:
Trabaja para: es una relación que vincula los conjuntos de 
entidades empleado y empleador.
Tiene: es una relación que vincula los conjuntos de entidades
cliente y cuenta.
Elementos de Bases de Datos 
Clase 13 12
Cardinalidad de las Relaciones
La cardinalidad de asignación adecuada para un 
conjunto de relaciones depende del mundo real que
se esté modelando.
Las relaciones pueden ser de cardinalidad uno a uno, 
uno a muchos, muchos a uno y muchos a muchos.
EJEMPLO: Si modelamos una relación entre los conjuntos de 
entidades Cliente y Cuenta, un mismo cliente podría tener
muchas cuentas (una a muchas). Si una cuenta puede
pertenecer a varios clientes, entonces cada cliente puede
tener muchas cuentas y viceversa (muchas a muchas).
3
Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación
Elementos de Bases de Datos – 2do. Cuatrimestre de 2004
Elementos de Bases de Datos 
Clase 13 13
Limitaciones del Modelo E-R
¿Entidad o Atributo? Muchas veces cuesta distinguir
si un objeto es una entidad en si misma o es
atributo de otra entidad.
¿Entidad o Relación? Otras veces, cuesta distinguir
si un objeto será una entidad o una relación que
vincule entidades.
¿Binarias, ternarias, …? muchas veces, la dificultad
de determinar correctamente la aridad de la 
relación, nos lleva a diagramas que no representan
la información tal cual es en el mundo real.
Elementos de Bases de Datos 
Clase 13 14
Modelo Relacional
Está basado en el uso de relaciones.
Las relaciones nos permiten representar conjuntos de 
entidades y conjuntos de relaciones del modelo E-R.
Cada relación es una tabla compuesta por filas o 
tuplas. 
Cada tupla está compuesta por una serie de atributos
y representa una entidad.
A1 A2 … An
Relación
Elementos de Bases de Datos 
Clase 13 15
Modelo E-R a Modelo Relacional
Sean los conjuntos de entidades E1=(A1,…,Am) y 
E2=(B1,…,Bn) con llaves (A1,…,Ai) y (B1,…,Bj) 
respectivamente.
Sea R una relación que la vincula E1 y E2 con 
cardinalidad muchos a uno:
Solución Costosa (general):
E1=(A1,…, Ai,…,,Am).
E2=(B1,…, Bj,…,Bn).
R= (A1,…,Ai,B1,…,Bj).
Solución Económica:
E1=(A1,…, Ai,…,,Am, B1,…, Bj).
E2=(B1,…, Bj,…,Bn).
Elementos de Bases de Datos 
Clase 13 16
Modelo E-R a Modelo Relacional
Sean los conjuntos de entidades E1,E2,…,En, con llaves
k1,…,kn respectivamente.
Sea R una relación n-aria que vincula E1,E2, … y En:
Solución General:
E1=(A1,…, Ai1,…,Am1), k1 = {A1,…, Ai1}.
E2=(B1,…, Bi2,…,Bm2), k2 = {B1,…, Bi2}.
...
En=(N1,…, Njn,…,Nmn), kn = {N1,…, Njn}.
R= (A1,…,Ai1,B1,…,Bi2,…,N1,…, Njn).
Si una relación tiene atributos se pueden agregar
atributos a la relación o a una de las entidades que la 
involucra.
Elementos de Bases de Datos 
Clase 13 17
Poder Expresivo de los Lenguajes
Lenguajes de Consulta Formales
Algebra Relacional.
Cálculo Relacional de Tuplas
Restringido a expresiones seguras (en términos
generales, expresiones sin negación).
Lenguajes de Consulta Comerciales
SQL
Elementos de Bases de Datos 
Clase 13 18
Dependencias Funcionales (DF's)
Sea R=(A1,…,An) un esquema de relación, X e Y 
subconjuntos de {A1,…,An}. 
Decimos que "X determina funcionalmente a Y" o 
"Y depende funcionalmente de X" si para
cualquier relación r sobre el esquema de relación
R, no es posible que r contenga dos tuplas que
coincidan en todos los componentes de X pero no 
coinciden en uno o más componentes de Y.
Esta relación se representa como X → Y.
4
Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación
Elementos de Bases de Datos – 2do. Cuatrimestre de2004
Elementos de Bases de Datos 
Clase 13 19
Cubrimientos mínimos
Definición: Un conjunto de df’s F es no redundante si
no existe ningún subconjunto propio F’ de F equivalente
a F, esto es, no existe F’ tal que F’ ⊂ F y F ≡ F’.
Definición: Un conjunto de df’s F es mínimo si no existe
un conjunto de df’s G equivalente a F con menos df’s, 
esto es, no existe G tal que || G || < || F || y G ≡ F.
Definición: Un conjunto de df’s F es óptimo si es
mínimo y no existe un conjunto de df’s G equivalente a 
F de un tamaño menor (el tamaño es la suma de los
atributos que aparecen a izquierda y derecha de cada
df).
Elementos de Bases de Datos 
Clase 13 20
Algoritmo MínimoReducido
Algoritmo MínimoReducido (Informalmente)
Datos de Entrada: un conjunto de df's F.
Datos de Salida: un cubrimiento mínimo reducido de F.
Comienzo del Algoritmo
1. Obtener las df’s cerradas en atributos (X→X+).
2. Eliminar df’s redundantes.
3. Reducir a izquierda las df’s.
4. Reducir a derecha las df’s.
Fin del Algoritmo
Elementos de Bases de Datos 
Clase 13 21
¿Cómo determinar las llaves de R?
Dado un esquema de relación R=(A1,…,An), y un 
conjunto F de df's no redundante y sin atributos
extraños, entonces para cada atributo Ai:
Siempre es parte de una llave si no aparece ni a 
izquierda ni a derecha en ninguna dependencia de F, o
aparece solamente a izquierda en df's de F.
Nunca es parte de una llave si aparece solamente a 
derecha en las df's de F.
Tal vez es parte de una llave si aparece a izquierda y 
derecha en dos o más df’s de F. 
Un conjunto X es llave de R si X+=R.
Elementos de Bases de Datos 
Clase 13 22
Descomposición de Relaciones
Definición: una descomposición de un esquema
de relación R = (A1,A2,…,An) es una colección de 
subconjuntos de R de la forma ρ = (R1,R2,…,Rk) 
tal que R = R1 ∪ R2 ∪ … ∪ Rk.
En una descomposición, no existe el 
requerimiento de que los Ri's sean disjuntos.
El objetivo de descomponer relaciones es evitar
redundancias, eliminar inconsistencias y 
anomalías de inserción y de borrado.
Elementos de Bases de Datos 
Clase 13 23
Descomposición de Relaciones
Si bien un esquema de relación R puede no 
satisfacer cierta forma normal, es posible obtener
una descomposición ρ=(R1,…,Rk) tal que cada
esquema Ri la satisface.
Definición: Una descomposición ρ=(R1,…,Rk) 
satisface una forma normal determinada si cada
Ri satisface esa forma normal.
Sería deseable que la descomposición preserve 
dependencias y sea join sin pérdida.
Elementos de Bases de Datos 
Clase 13 24
Join sin Pérdida (JSP)
Definición: un esquema de relación R=(A1,A2,…,An) 
descompuesto en el esquema ρ = (R1,R2,…,Rk) es una
descomposición join sin pérdida con respecto a un 
conjunto de df's D si cada relación r de R satisfaciendo D 
es tal que:
r = πR1(r) |><| πR2(r) |><| … |><| πRk(r)
Esto es, cada relación r es igual al join natural de sus
proyecciones en los Ri's.
Si r ⊂ πR1(r) |><| πR2(r) |><| … |><| πRk(r) entonces hay 
más información en la descomposición que en la relación
original.
5
Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación
Elementos de Bases de Datos – 2do. Cuatrimestre de 2004
Elementos de Bases de Datos 
Clase 13 25
Preservación de Dependencias (PD)
Definición: Sea ρ = (R1,R2,…,Rk) la descomposición
de un esquema de relación R y F el conjunto de df’s
para R. La proyección de F en el conjunto de 
atributos Z, denotado por ΠZ(F), es el conjunto de 
df’s X→Y en F+ (no en F) tales que XY ⊆ Z.
Definición: Sea ρ = (R1,R2,…,Rk) la descomposición
de un esquema de relación R y F el conjunto de df’s
para R. Se dice que ρ preserva dependencias si:
∪ki=1 ΠRi(F) = ΠR1(F) ∪ ΠR2(F) ∪ … ∪ ΠRk(F) |= F
Preservación de dependencias es una restricción de 
integridad para R independiente de la propiedad jsp. Elementos de Bases de Datos 
Clase 13 26
Primera Forma Normal
Definición: Un esquema de relación R está en 
primera forma normal (1FN) si los valores en 
dom(A) son atómicos para cada atributo A en R.
Esto es, los valores de los dominios no son 
valores compuestos (conjuntos, listas, etc).
Ventajas de la 1FN:
Representación Tabular.
Lenguajes de Consulta más simples.
Definición de Restricciones de Integridad más simples.
Elementos de Bases de Datos 
Clase 13 27
Segunda Forma Normal
Definición: Un esquema de relación R está en 
segunda forma normal (2FN) con respecto a un 
conjunto de df's F si está en 1FN y cada atributo
no primo es totalmente dependiente de cada
llave en R.
Definición: Un esquema de relación R está en 
segunda forma normal (2FN) con respecto a un 
conjunto de df's F si para cada df X → A (A ∉ X) 
en F se verifica que:
X no es un subconjunto propio de una llave, o bien:
A es primo.
Elementos de Bases de Datos 
Clase 13 28
Tercera Forma Normal
Definición: Un esquema de relación R está en 
tercera forma normal (3FN) con respecto a un 
conjunto de df's F si está en 1FN y cada atributo
no primo no es transitivamente dependiente de 
una superllave de R.
Definición: Un esquema de relación R está en 
tercera forma normal (3FN) si para cada
dependencia funcional X → A (A ∉ X) en F se 
verifica que:
X es superllave, o bien:
A es primo.
Elementos de Bases de Datos 
Clase 13 29
Forma Normal de Boyce-Codd
Definición: Un esquema de relación R está en forma 
normal de Boyce-Codd (FNBC) con respecto a un 
conjunto de df's F si para cada dependencia funcional
X→A (A∉X) en F vale se verifica que X es superllave.
Definición: Un esquema de relación R está en forma 
normal de Boyce-Codd (FNBC) con respecto a un 
conjunto de df's F si para cada subconjunto Y de R y 
cada atributo A en R\Y, si Y→A entonces Y→R en F. 
Esto es, si Y determina no trivialmente cualquier
atributo de R entonces Y es superllave de R.
Elementos de Bases de Datos 
Clase 13 30
¿Por qué buscamos FNBC?
La 3FN es apropiada en muchos casos pero no 
en aquellos casos en los que:
Existen dos o más llaves candidatas, o bien:
Las llaves candidatas son compuestas, o bien:
Las llaves candidatas son solapadas (esto es, tienen al 
menos un atributo en común).
En aquellos casos en los que no sucede esto, la 
3FN y la FNBC son equivalentes.
El problema es que FNBC puede no preservar
dependencias.
6
Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación
Elementos de Bases de Datos – 2do. Cuatrimestre de 2004
Elementos de Bases de Datos 
Clase 13 31
¿Cómo obtener 3FN o FNBC?
Obtener un cubrimiento mínimo reducido.
Abrir a derecha las df’s.
Para 3FN, tomar un esquema por cada df (puede que más 
de una df caiga en un esquema).
Para asegurar jsp debe asegurarse que un esquema contenga 
una llave.
Este algoritmo preserva dependencias y es jsp.
Optimización: se pueden fusionar esquemas con al menos una 
llave en común.
Para obtener FNBC tenemos dos posibilidades:
Utilizar el algoritmo de descomposición (llamado informalmente 
“Algoritmo de las Burbujas”), y optimizar o bien:
Obtener 3FN y descomponer solamente aquellos esquemas que 
violan la FNBC. Elementos de Bases de Datos 
Clase 13 32
Algoritmos para 3FN y FNBC
Partimos de un cubrimiento mínimo reducido y abrimos 
a derecha las df’s.
Para 3FN:
• Algoritmo3FNpd.
• Algoritmo3FNpdjsp.
• Algoritmo3FNpdjsp optimizado.
Para FNBC:
• AlgoritmoFNBCjsp (Burbuja).
• AlgoritmoFNBCjsp (Burbuja) optimizado.
• AlgoritmoFNBC a partir de Algoritmo de 3FNpdsjp:
+ Suele perder menos dependencias que el algortimo de 
burbuja.
− Las descomposiciones pueden tener más subesquemas.
Elementos de Bases de Datos 
Clase 13 33
Resumen de Formas Normales
1FN: Exige que los atributos sean atómicos.
2FN: Elimina dependencias funcionales parciales
(salvo para los atributos primos).
3FN: Elimina dependencias funcionales
transitivas (salvo para los atributos primos).
FNBC: Permite solamente dependencias
funcionales donde su lado izquierdo contiene una
llave.
Elementos de Bases de Datos 
Clase 13 34
Formas Normales
1FN
2FN
3FN
FNBC
4FN Fuera del alcancede este curso
Elementos de Bases de Datos 
Clase 13 35
Metodología de DiseñoHacer un relevamiento exhaustivo de información.
Construir el Modelo Entidad-Relación.
Obtener el Modelo Relacional a partir del Modelo
Entidad-Relación.
Considerar un esquema universal con los atributos.
Plantear las dependencias funcionales y multivaluadas.
Buscar cubrimientos mínimos reducidos o buenos
cubrimientos (según corresponda).
Buscar la forma normal más alta posible, 
descomponiendo el esquema universal mientras sea 
necesario.
Elementos de Bases de Datos 
Clase 13 36
Temas de la clase de hoy
Revisión de todos los temas vistos y 
que comprenden el primer parcial.