Resumen - Base de Datos

Base de Datos (75.15 - 95.
05)
Resumen
Esta obra est bajo una Licencia Creative Commons

Atribucin-NoComercial-CompartirIgual 4.0 Internacional.
ltima actualizacin: 08/03/2015
fiuba-apuntes.github.io
LICENCIA
Este es un resumen (y no un sustituto) de la licencia. Este resumen destaca slo algunas de las
caractersticas clave y los trminos de la licencia real. No es una licencia y no tiene valor legal. Usted
debe revisar cuidadosamente todos los trminos y condiciones de la licencia actual antes de usar el
material licenciado.
Usted es libre para:

Compartir copiar y redistribuir el material en cualquier medio o formato
Adaptar remezclar, transformar y crear a partir del material
El licenciante no puede revocar estas libertades en tanto usted siga los trminos de la licencia
Bajo los siguientes trminos:

Atribucin Debe reconocer adecuadamente la autora, proporcionar un enlace a la licencia
e indicar si se han realizado cambios. Puede hacerlo de cualquier manera razonable, pero no de
una manera que sugiera que tiene el apoyo del licenciador o lo recibe por el uso que hace.
NoComercial Usted no puede hacer uso del material con fines comerciales.
CompartirIgual Si usted mezcla, transforma o crea nuevo material a partir de esta obra,
usted podr distribuir su contribucin siempre que utilice la misma licencia que la obra original.
No hay restricciones adicionales Usted no puede aplicar trminos legales ni medidas tecnolgicas que
restrinjan legalmente a otros hacer cualquier uso permitido por la licencia.
Aviso:
Usted no tiene que cumplir con la licencia para los materiales en el dominio pblico o cuando su uso est
permitido por una excepcin o limitacin aplicable.
No se entregan garantas. La licencia podra no entregarle todos los permisos que necesita para el uso que
tenga previsto. Por ejemplo, otros derechos como relativos a publicidad, privacidad, o derechos morales pueden
limitar la forma en que utilice el material.
NDICE
ndice
Acerca del proyecto
Introduccin a las Bases de Datos
1. Modelo de datos
2. BDs y SGBDs
2.1. Base de datos . . . . . . . . . . . . . . . . .
2.2. Por qu una base de datos y no un sistema
2.3. Diseo de una base de datos . . . . . . . . .
2.4. Modelos de datos . . . . . . . . . . . . . . .
2.4.1. Operaciones en una base de datos .
2.4.2. Restricciones . . . . . . . . . . . . .
2.5. Modelos de bases de datos . . . . . . . . . .
. . . . . . .
de archivo?
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
7
7
8
8
9
9
9
3. Modelo Entidad-Interrelacin (E-R)

3.1. Entidades . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Interrelaciones . . . . . . . . . . . . . . . . . . . . . . .
3.2.1. Tipos de interrelaciones . . . . . . . . . . . . . .
3.3. Restricciones . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1. Restricciones de participacin . . . . . . . . . . .
3.3.2. Restricciones de cardinalidad de correspondencia
3.3.3. Restricciones de dependencia existencial . . . . .
3.3.4. Restricciones de identificacin . . . . . . . . . . .
3.4. Diagramas E-R . . . . . . . . . . . . . . . . . . . . . . .
3.5. Cuestiones de diseo . . . . . . . . . . . . . . . . . . . .
3.6. Reduccin de un esquema E-R a un modelo relacional .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
10
10
12
13
13
13
15
15
16
16
17
4. Modelo Relacional
4.1. Estructura del modelo relacional . . . . .
4.2. Restricciones del modelo relacional . . . .
4.3. Operaciones del modelo relacional: lgebra
4.3.1. Operadores bsicos . . . . . . . . .
4.3.2. Operadores secundarios . . . . . .
4.4. Operadores extendidos . . . . . . . . . . .
4.5. Actualizaciones a bases de datos . . . . .
4.5.1. Delete . . . . . . . . . . . . . . . .
4.5.2. Insert . . . . . . . . . . . . . . . .
4.5.3. Update . . . . . . . . . . . . . . .
4.6. Vistas (views) . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
18
18
19
19
20
22
23
23
23
23
23
. . . . . .
. . . . . .
relacional
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5. Clculo relacional
24
6. Lenguajes de consulta
24
7. Integridad y seguridad
7.1. Restricciones de dominio . . . . . . . .
7.2. Restricciones de integridad referencial
7.2.1. Acciones referenciales . . . . .
7.3. Seguridad y autorizaciones . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
24
24
24
25
25
8. Triggers
25
II
26
Diseo de bases de datos
Pgina 1 de 74
Base de Datos (75.15 - 95.05) - Resumen
NDICE
9. Dependencias funcionales
26
9.1. Axiomas de Armstrong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
9.2. Clausura y superclaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
9.3. Cubrimiento minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
10.Primera forma normal (1FN)
29
11.Descomposicin de una relacin

30
11.1. Descomposicin SPI en 2 relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
11.2. Descomposicin SPI en ms de 2 relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
12.Segunda forma normal (2FN)
33
13.Forma normal Boyce-Codd (FNBC)
33
14.Tercera forma normal (3FN)
34
15.Dependencias multivaluadas
15.1. Propiedades de las DMVs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.2. Preservacin de dependencias multivaluadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15.3. Base minimal de Dependencias e Implicacin de DMVs . . . . . . . . . . . . . . . . . . . . . . . .
35
36
37
37
16.Cuarta forma normal (4FN)

38
16.1. Descomposicin SPI en 2 relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
16.2. Descomposicin SPI en ms de 2 relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
17.Dependencias de junta
40
17.1. Dependencias de junta embebidas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
18.Quinta forma normal (5FN)
41
18.1. Implicacin de dependencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
III
SQL
43
19.DDL
19.1. Tipos de dominios
19.2. Create table . . . .
19.3. Drop table . . . . .
19.4. Alter table . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
43
43
44
44
20.DML
20.1. Consultas anidadas
20.2. Delete . . . . . . .
20.3. Insert . . . . . . .
20.4. Update . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
44
45
47
47
47
IV
Procesamiento de Consultas
48
21.ndices
49
21.1. Estructuras de ndices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
22.Formas de realizar consultas
50
22.1. Operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
23.Algoritmos
51
23.1. Seleccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
23.2. Junta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Pgina 2 de 74
NDICE
24.Evaluacin de expresiones
53
25.Optimizacin de consultas
53
25.1. Reglas de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
25.2. Heursticas de optimizacin de consultas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
26.Estimacin de tamao de consultas
54
26.1. Clculo de juntas con histogramas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Control de Concurrencia
57
27.Transacciones
57
28.Problemas de concurrencia
58
28.1. Atributos de una transaccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
29.Schedules de transacciones
60
30.Protocolos de Control de Concurrencia: Protocolo de Locking

30.1. Lock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30.1.1. Tipos de locks . . . . . . . . . . . . . . . . . . . . . . . . .
30.1.2. Problemas con el uso de locks . . . . . . . . . . . . . . . . .
30.2. Lock de update . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30.3. Matriz de compatibilidad de locks . . . . . . . . . . . . . . . . . .
30.4. Lock table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30.5. Protocolo de dos fases (two-phase locking) . . . . . . . . . . . . . .
30.6. Protocolo de rbol . . . . . . . . . . . . . . . . . . . . . . . . . . .
VI
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Tcnicas de Recuperacin
61
62
62
62
63
63
64
64
65
66
31.Necesidad de Recuperacin
66
32.Archivo de Log
66
32.1. Checkpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
32.1.1. Checkpoints bloqueantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
32.1.2. Checkpoints no bloqueantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
33.Protocolos de Recuperacin
33.1. Deferred update . . . . . . .
33.2. Immediate update . . . . . .
33.2.1. UNDO/REDO . . .
33.2.2. UNDO . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
68
68
69
69
70
Colaboradores
73
Historial de cambios
74
Pgina 3 de 74
ACERCA DEL PROYECTO
Acerca del proyecto

FIUBA Apuntes naci con el objetivo de ofrecer en formato digital los apuntes de las materias que andan
rondando por los pasillos de FIUBA y que los mismos sean fcilmente corregidos y actualizados.
Cualquier persona es libre de usarlos, corregirlos y mejorarlos.
Encontrars ms informacin acerca del proyecto o ms apuntes en fiuba-apuntes.github.io.
Por qu usamos LaTeX?

LaTeX es un sistema de composicin de textos que genera documentos con alta calidad tipogrfica, posibilidad de representacin de ecuaciones y frmulas matemticas. Su enfoque es centrarse exclusivamente en el
contenido sin tener que preocuparse demasiado en el formato.
LaTeX es libre, por lo que existen multitud de utilidades y herramientas para su uso, se dispone de mucha
documentacin que ayuda al enriquecimiento del estilo final del documento sin demasiado esfuerzo.
Esta herramienta es muy utilizado en el mbito cientfico, para la publicacin de papers, tesis u otros documentos. Incluso, en FIUBA, es utilizado para crear los enunciados de exmenes y apuntes oficiales de algunos
cursos.
Por qu usamos Git?

Git es un software de control de versiones de archivos de cdigo fuente desde el cual cualquiera puede obtener
una copia de un repositorio, poder realizar aportes tanto realizando commits o como realizando forks para ser
unidos al repositorio principal.
Su uso es relativamente sencillo y su filosofa colaborativa permite que se sumen colaboradores a un proyecto
fcilmente.
GitHub es una plataforma que, adems de ofrecer los repositorios git, ofrece funcionalidades adicionales muy
interesantes como gestor de reporte de errores.
Pgina 4 de 74
Parte I
Introduccin a las Bases de Datos

1.
Modelo de datos
Un fenmeno o idea usualmente refiere a un objeto y a algn aspecto del objeto, el cual captura un determinado valor en un cierto momento.
Dato tupla <nombre de objeto, propiedad de objeto, valor de la propiedad del objeto, instante>.
Dato elemental terna <nombre de objeto, propiedad de objeto, valor de la propiedad del objeto>.
Modelo de datos herramienta intelectual que provee una interpretacin del mundo real. Es un dispositivo de
abstraccin.
Figura 1: Datos, informacin y conocimiento

Ejemplos de modelos de representacin simblica de la informacin: lenguaje natural, frmulas matemticas,
mapas, partituras.
La pieza ms elemental de informacin es el dato. Un dato solo es de utilidad si est vinculado a otros
datos. La estructura y el contexto le dan significado a los datos.
2.
BDs y SGBDs
Sistema de Base de Datos est formado por cuatro componentes:

1. Hardware
2. Software
3. Datos
4. Personas
a) Administradores: definen el esquema de la base de datos, definen permisos de acceso, ejecutan
mantenimientos de rutina (backups, ampliando la capacidad de los discos, monitoreando la performance)
b) Usuarios
Pgina 5 de 74
2 BDs y SGBDs
Tipo de usuario
Ingenuos
Descripcin
Consultan la base de datos
Sofisticados
Consultan la base de datos

mediante un lenguaje, sin
programar aplicaciones
Programador de
aplicaciones
Especializados
Crean programas para acceder a

la base de datos
Programan aplicaciones
especiales (knowledge bases,
sistemas expertos, etc.)
Interfaz que utiliza

Rellenando formularios de
consulta, o leyendo reportes
generados de la base de datos.
Usan aplicaciones
Herramientas OLAP (Online Analytical Processing)
Herramientas de data mining
Herramientas RAD (Rapid
Application Development)
Sistema de Gestin de Base de Datos (SGBD) Ejemplos: Oracle, MySQL, SQL Sever, DB2, Access, PosgreSQL. Sistema formado por datos y los programas que acceden a los datos. Su objetivo es almacenar y
permitir consultas en formas convenientes y eficientes.
Est formado por tres capas, las abstracciones:
1. Nivel exterior : vistas que ven los usuarios. Solo ven una parte de la base de datos, la que les interesa
2. Nivel lgico: cmo se agrupan lgicamente los datos, las entidades y sus relaciones. Ejemplo: tablas,
grafos.
3. Nivel fsico: como se organizan fsicamente los datos. Ejemplos: bitmaps, rboles.
Gestin de Base de Datos est formada por las siguientes herramientas:
1. Compiladores: proveen el lenguaje de consulta.
2. Catlogo: provee informacin de la base de datos; por ejemplo, para sacar estadsticas de consultas.
3. Optimizador de consultas
4. Manejador de transacciones: asegura que una transaccin se ejecute completamente o permita una
vuelta atrs.
5. Manejador de concurrencia: asegura la integridad de la base de datos ante usuarios concurrentes.
6. Manejador de seguridad :
a) Contra hechos no intencionales. Ejemplo: fallas de energa.
b) Contra hechos intencionales. Ejemplo: ataques de terceros para robar informacin.
(a) Los datos se almacenan en una base de datos, que

es administrada por un sistema de gestin de bases
de datos
(b) Estructura general de un sistema de base de datos
Figura 2: SGBD
Pgina 6 de 74
2.1
Base de datos
2.1.
Base de datos
Base de Datos (BD) conjunto de datos interrelacionados.

Instancia de la base de datos coleccin de informacin en la base de datos en un momento particular.
Esquema de la base de datos descripcin de la base de datos. La base de datos fsica vara con el tiempo
(porque se producen altas, bajas y modificaciones), pero el esquema es fijo (o se cambia en raras ocasiones).
Modelo conceptual: representacin de alto nivel, que concentra los requerimientos del cliente. Utiliza
el modelo Entidad-Relacin.
Modelo lgico: representacin de bajo nivel. Utiliza el modelo relacional.
Modelo fsico: utiliza SQL.
Figura 3: Base de datos
2.2.
Por qu una base de datos y no un sistema de archivo?
Desventajas de usar un sistema de archivo:

Inconsistencia y redundancia, porque se usan muchos archivos, y tal vez tienen distintos formatos
Dificultad para acceder a los datos, porque se necesitan programas para acceder a los archivos
Problemas de integridad, porque es difcil cambiar todos los programas para que adopten restricciones de
consistencia
Dificultad para asegurar la atomicidad de las transacciones
Problemas para garantizar el acceso concurrente
Problemas de seguridad
Pgina 7 de 74
2.3
2.3.
Diseo de una base de datos
Diseo de una base de datos
Figura 4: Metodologa de diseo de una base de datos
2.4.
Modelos de datos
Modelo de datos gua para organizar los datos de una base de datos. Formado por tres componentes:
1. la estructura de los datos (tablas, rboles, redes, etc.),
2. las operaciones sobre las estructuras, y
3. las restricciones sobre las estructuras o sobre las operaciones (para que los datos mantengan su
integridad semntica).
La potencia semntica de un modelo de datos est determinada por su capacidad de representar, adems
de la estructura de los datos, el significado de los mismos y sus interrelaciones.
Pgina 8 de 74
2.5
Modelos de bases de datos
2.4.1.
Operaciones en una base de datos
Estado de una BD valor de todos los atributos de todos los objetos de la base de datos.
Operadores los hay de dos tipos:
1. De consulta (no modifican el estado de la base de datos)
2. De actualizacin (modifican el estado de la base de datos)
Transaccin conjunto de operaciones elementales. Ejemplo: la transferencia a una cuenta.
leer ( cuenta_a )
cuenta_a <- cuenta_a + 100
escribir ( cuenta_a )
leer ( cuenta_b )
cuenta_b <- cuenta_b - 100
escribir ( cuenta_b )
2.4.2.
Restricciones
Tipos de restricciones sobre una base de datos:

Inherentes: determinado por la estructura de la base de datos
Explcitas: provienen del mundo real
Implcitas: se derivan de las explcitas
De estado: restringen los posibles valores de los atributos. Ejemplo: la edad de una persona no puede ser
negativa.
De actualizacin: restringen las posibles operaciones sobre los atributos. Ejemplo: no se puede disminuir
la edad de una persona.
De entidad: Ejemplo: no puede haber dos objetos iguales en la misma base de datos.
De integridad referencial: Ejemplo: no se puede referenciar a un objeto que no existe en la base de
datos.
2.5.
Modelos de bases de datos
1. Entidad-Interrelacin: para el diseo conceptual

2. Relacional: para el modelo lgico. La relaciones se representan a travs de claves forneas
3. Jerrquico (rbol): el acceso a niveles inferiores slo es posible a travs de sus padres
4. De red: las relaciones entre los datos se representan con referencias fsicas
5. De objetos: existe una persistencia de los objetos ms all de la existencia en memoria
Pgina 9 de 74
3 Modelo Entidad-Interrelacin (E-R)
3.
Modelo Entidad-Interrelacin (E-R)

Nota importante: no podemos tener nombres de entidades o interrelaciones repetidos.
3.1.
Entidades
El modelo entidad-interrelacin se basa en la idea de que el mundo real est compuesto por objetos (las
entidades) y las interrelaciones que hay entre las entidades.
Entidad algo que existe, concreto o abstracto. Ejemplo: una persona Juan, la cuenta bancaria n4500011.
Conjunto de entidades / tipo de entidad conjunto de entidades del mismo tipo. Ejemplo: el conjunto de
entidades cliente abarca todas las personas que tienen cuenta en un banco.
Un conjunto de entidades E tiene un predicado asociado p para probar si una entidad e pertenece al conjunto.
E = {e/p(e)}
Los conjuntos de entidades no necesitan ser disjuntos. Ejemplo: animales y mamferos no son disjuntos.
Un tipo de entidad queda definido por:
1. Nombre: en singular o frase simple en singular. Ejemplos: cliente, cuenta corriente
2. Significado: texto preciso, conciso y claro. Debe indicar, si existieran, dependencias con otros tipos de
entidades
3. Atributos: caractersticas de todas las entidades de ese tipo. Ejemplo: para el conjunto de entidades
cliente, posibles atributos son nombre, DNI, calle, ciudad, etc. Cada atributo tiene un conjunto
de valores permitidos, denominado el dominio del atributo. Ejemplo: el DNI debe ser un nmero positivo.
Los atributos deben ser atmicos (es decir, que no se pueden descomponer), y no pueden estar repetidos.
Formalmente, un atributo es una funcin que hace corresponder un conjunto de entidades a un dominio o
producto cartesiano de dominios. Ejemplo: una entidad empleado est descrita por el conjunto {(nombre,
Juan), (apellido, Cancela), (DNI, 5.678.901)}.
Un atributo puede tener el valor nulo, por varias razones:
a) No aplica
b) Faltante
c) Desconocido
Tipos de atributos:
a) Simple vs compuesto. Ejemplo: nombre puede descomponerse en primer nombre, segundo nombre, y
apellido.
b) Un valor vs Multivaluado: se repite varias veces en la entidad. Ejemplo: nmero de telfono.
c) Derivable: su valor puede calcularse a partir de otros atributos. Debe evitarse. Ejemplo: si tengo el
atributo fecha de nacimiento, edad es un atributo derivable.
4. Identificador: atributo o conjunto de atributos que permiten distinguir a cada entidad dentro del conjunto
de entidades del mismo tipo.
3.2.
Interrelaciones
Interrelacin asociacin entre dos o ms conjuntos de entidades.

Conjunto de interrelaciones / tipo de interrelacin conjunto de interrelaciones del mismo tipo. Si E1 , E2 , . . . , En
son conjuntos de entidades, entonces el conjunto de interrelaciones R es un subconjunto del producto cartesiano
{(e1 , e2 , . . . , en ) /e1 E1 , e2 E2 , . . . , en En }
donde la tupla (e1 , e2 , . . . , en ) es una interrelacin.
Pgina 10 de 74
3.2
Interrelaciones
Figura 5: Tenencia es una interrelacin entre dos entidades
Un tipo de interrelacin puede tener atributos descriptivos. Ejemplo: la interrelacin tenencia puede
tener un atributo fecha ltimo movimiento.
Caractersticas:
Grado de una interrelacin cantidad de tipos de entidades que participan en la relacin.
Figura 6: Grado de una interrelacin

Cardinalidad de una interrelacin cantidad de tipos de entidades con las que puede estar relacionado.
Rol funcin que desempea una entidad en una interrelacin. Normalmente no se especifica porque est implcito. Ejemplos: un cliente tiene una cuenta, un empleado es jefe de n empleados.
Instancia de una interrelacin asociacin entre dos o ms entidades. Debe ser unvocamente identificable
sin usar los atributos descriptivos de la interrelacin.
Un tipo de interrelacin puede identificarse por:
1. Un atributo propio, o
2. Una clave primaria, formada por los atributos de las claves primarias de los tipos de entidad que asocian.
Ejemplo: DNI es la clave primaria de cliente, y nro cuenta es la clave primaria de cuenta. La clave
primaria del tipo de interrelacin tenencia es (DNI, nro cuenta)
La estructura de la clave primaria de una interrelacin R depende de las restricciones de cardinalidad del
conjunto de interrelaciones.
Pgina 11 de 74
3.2
3.2.1.
Interrelaciones
Tipos de interrelaciones
Especializacin un conjunto de entidades se divide en grupos de entidades que son distintivas. Ejemplo: en
el contexto de un banco, una persona puede ser especializada en un empleado o un cliente, o ambas, o
ninguna
Generalizacin la inversa de especializacin. Existe una superclase y una o ms subclases.
Puede haber restricciones de pertenencia:
1. Qu tipos de entidades pueden ser miembros de una subclase?
a) Definido por condicin: existe una condicin o predicado explcito que decide la pertenencia o
no pertenencia.
b) Definido por el usuario: el usuario de la BD asigna entidades a una subclase.
2. Las entidades pueden pertenecer a ms de una subclase dentro de una superclase?
a) S = Generalizaciones superpuestas
b) No = Generalizaciones disjuntas
3. Una entidad en la superclase debe pertenecer a al menos una entidad en la subclase?
a) S = Generalizacin total
b) No = Generalizacin parcial
En la especializacin y en la generalizacin, las subclases heredan atributos de la superclase.
Agregacin abstraccin mediante la cual un conjunto de interrelacin es tratado como una superclase.
Pgina 12 de 74
3.3
Restricciones
3.3.
Restricciones
3.3.1.
Restricciones de participacin
Se dice que la participacin de un conjunto de entidades E en un conjunto de interrelaciones R es total

cuando cada entidad en E participa en al menos una interrelacin en R. Si solo algunas entidades participan,
la participacin es parcial.
3.3.2.
Restricciones de cardinalidad de correspondencia
Cardinalidad de correspondencia cantidad mnima y mxima de entidades a las cuales puede asociarse una
entidad a travs de un tipo de interrelacin.
Para una interrelacin binaria R entre dos tipos de entidades A y B, la cardinalidad puede ser:
1. Uno a uno (1 : 1): Una entidad en A est asociada como mximo a una entidad en B, y una entidad en
B est asociada como mximo a una entidad en A.
Figura 7: Cardinalidad 1 : 1
2. Uno a muchos (1 : M ): Una entidad en A est asociada como mximo con cualquier cantidad de entidades
en B, y una entidad en B est asociada como mximo a una entidad en A.
Tambin existe la restriccin muchos a uno (M : 1).
Figura 8: Cardinalidad 1 : M
3. Muchos a muchos (M : M ): Una entidad en A est asociada como mximo con cualquier cantidad de
entidades en B, y una entidad en B est asociada como mximo con cualquier cantidad de entidades en
A.
Figura 9: Cardinalidad M : M
Para una interrelacin ternaria R entre tres tipos de entidades A, B y C, la cardinalidad puede ser:
Pgina 13 de 74
3.3
Restricciones
N:N:N
Figura 10: Las fbricas le compran insumos a proveedores.

Claves candidatas de Compra: {idf abrica , idinsumo , idproveedor }
N:N:1
Figura 11: Las fbricas le compran insumos a proveedores. Una fbrica no puede comprar el mismo insumo a
ms de un proveedor.
Claves candidatas de Compra: {idf abrica , idinsumo }
N:1:1
ms de un proveedor. Un proveedor no puede venderle el mismo insumo a ms de una fabrica.
Claves candidatas de Compra: {idf abrica , idinsumo } ; {idproveedor , idinsumo }
1:1:1
ms de un proveedor. Un proveedor no puede venderle el mismo insumo a ms de una fabrica. Una
fbrica no puede comprarle ms de un insumo a cada proveedor.
Pgina 14 de 74
3.3
Restricciones
Claves candidatas de Compra: {idf abrica , idinsumo } ; {idproveedor , idinsumo } ; {idf abrica , idproveedor }
Teorema: en las relaciones ternarias, las restricciones de cardinalidad no imponen restricciones en las
relaciones binarias. En el ejemplo anterior, una fbrica puede comprar N insumos. Una fbrica puede comprarle
a N proveedores. Un proveedor puede proveer N insumos.
3.3.3.
Restricciones de dependencia existencial
Si la existencia de la entidad S depende de la existencia de la entidad D, entonces se dice que S tiene

dependencia existencial de D. Operacionalmente, esto significa que si D es borrado, tambin S es borrado.
La entidad D es la entidad dominante y S es la entidad subordinada.
3.3.4.
Restricciones de identificacin
Superclave conjunto de uno o ms atributos que, tomados en conjunto, permiten identificar unvocamente
una entidad o una interrelacin en el conjunto de entidades o interrelaciones del mismo tipo.
Si K es una superclave, cualquier superconjunto de K tambin es una superclave.
Clave candidata superclaves minimales; aquellas para las cuales ningn subconjunto propio es una superclave.
Sea R un esquema de relacin con atributos A1 , . . . , An . El conjunto de atributos K = (A1 , . . . , Ak ) es
una clave candidata de R s y slo s satisface:
1. Unicidad : en todo momento, no existen dos tuplas distintas de R que tengan el mismo valor para
Ai , donde i [1, k].
2. Minimalidad : ningn atributo de K puede ser eliminado sin que se pierda la propiedad de unicidad.
Clave primaria aquella clave candidata que es elegida por el diseador del modelo de datos para identificar
entidades dentro del conjunto de entidades. Esta clave no debera cambiar en el tiempo. Ejemplo: la
direccin de un cliente no es una buena clave primaria, porque se puede mudar
Clave fornea atributo o conjunto de atributos que es clave primaria en otra relacin. Ejemplo: en una relacin
autos, puede haber una clave fornea DNI que es la clave primaria en otra relacin personas, y que
indica el dueo de ese auto
Entidad dbil entidad que tiene dependencia de identificacin, porque no es identificable por sus propios
atributos. Est subordinada a otro tipo de entidad, la entidad fuerte.
Entidad fuerte entidad que tiene una clave primaria propia.
El concepto de entidades fuertes y dbiles est relacionado con el concepto de dependencia de existencia.
Una entidad dbil es, por definicin, una entidad subordinada a la entidad dominante de la cual depende
su identidad. Toda dependencia de identidad es una dependencia de existencia, pero una dependencia de
existencia no implica necesariamente una dependencia de identidad.
Discriminador atributo o conjunto de atributos de una entidad dbil que lo distingue de otras entidades
dbiles que dependen de la misma entidad fuerte.
Para una entidad dbil, su clave primaria est formada por su identificador ms la clave primaria de la
entidad fuerte de la cual depende.
Pgina 15 de 74
3.4
3.4.
Diagramas E-R
Diagramas E-R
Figura 14: Simbologa en los diagramas E-R
Figura 15: Simbologa en los diagramas E-R para entidades fuertes (cuenta) y dbiles (transaccin). La clave
primaria de la entidad fuerte se identifica con el atributo subrayado (nro. cuenta). La dependencia a
la entidad fuerte se identifica con arcos dobles. El discriminador de la entidad dbil se identifica con
el atributo subrayado a medias (nro. transaccin). El identificador de la entidad dbil es la suma
de su discriminador y de la clave primaria de la entidad fuerte (nro. cuenta + nro. transaccin)
3.5.
Cuestiones de diseo
1. Conjuntos de entidades vs. Atributos?

a) Algunos atributos no pueden transformarse en entidades. Ejemplo: el nombre de una persona
b) Algunos atributos estn mejor representados como entidades, para permitir atributos. Ejemplo: telfonos de una persona
2. Conjuntos de entidades vs. Conjuntos de interrelaciones?
Las interrelaciones modelan acciones que ocurren entre entidades.
3. Conjuntos de interrelaciones binarias vs. n-arias?
Teorema: es posible reemplazar cualquier conjunto de interrelaciones naria (con n > 2) con un nmero
de interrelaciones binarias.
4. Localizacin de atributos de interrelaciones
a) Relaciones 1 : 1 = en cualquiera de las dos entidades participantes
b) Relaciones 1 : N = en la segunda entidad
c) Relaciones N : N = en la interrelacin
Pgina 16 de 74
3.6
3.6.
Reduccin de un esquema E-R a un modelo relacional
Reduccin de un esquema E-R a un modelo relacional
Para cada entidad y para cada interrelacin, se construye una nica tabla. Cada tabla contiene mltiples
columnas.
Representacin de conjuntos de entidades fuertes
Sea E un conjunto de entidad fuerte con atributos a1 , . . . , an . Se representa a la misma con una tabla
llamada E con n columnas. Cada fila de la tabla es una entidad. El conjunto de todas las posibles filas de
la tabla es el producto cartesiano entre los dominios de cada atributo:
D1 . . . Dn
Representacin de conjuntos de entidades dbiles
Sea A un conjunto de entidad dbil con atributos a1 , . . . , am . Sea B el conjunto de entidad fuerte del cual
depende A. La clave primaria de B est formada por los atributos b1 , . . . , bn . Se representa a A con una
tabla con m + n columnas a1 , . . . , am , b1 , . . . , bn .
Representacin de conjuntos de interrelaciones
Sea R un conjunto de interrelaciones entre las entidades E1 , . . . , En con atributos r1 , . . . , rm . Sean a1 , . . . , an
el conjunto de atributos formado por la unin de las claves primarias de cada entidad participante. Se
representa a R con una tabla con columnas a1 , . . . , an , r1 , . . . , rm .
Si la interrelacin relaciona un conjunto de entidades dbil y otro fuerte, la tabla de R no es necesaria,
es redundante.
Representacin de interrelaciones 1 : N entre entidades A y B
Si la participacin de A en R es total (i.e. cada entidad en A debe participar en la relacin R), se pueden
unir las tablas de A y R.
Representacin de atributos compuestos
Sea el atributo compuesto x formado por x1 , . . . , xn . Se debe generar una columna para cada x1 , . . . , xn ,
pero no para x.
Representacin de atributos multivaluados
Sea el atributo multivaluado x. Se debe crear una tabla T con una columna C que corresponde a x y
el resto de las columnas son la clave primaria del conjunto de entidades o interrelacin del cual x es un
atributo.
Representacin de generalizacin
Hay dos mtodos:
1. Una tabla para la superclase + una tabla para cada subclase, que incluya una columna con la clave
primaria de la superclase
2. Si la generalizacin es disjunta y completa, no se crea una tabla para la superclase. Se crea una tabla
para cada subclase, que incluya todos los atributos de la superclase.
Representacin de agregacin
La tabla de la interrelacin R entre la agregacin A y el conjunto de entidades B incluye una columna
por cada clave primaria de B y A.
Pgina 17 de 74
4 Modelo Relacional
4.
4.1.
Modelo Relacional
Estructura del modelo relacional
El modelo relacional es un ejemplo de modelo basado en registros. Usa un grupo de tablas para representar
los datos y las relaciones entre los datos. Cada tabla tiene mltiples columnas. Cada tabla contiene registros de
un tipo en particular. Cada registro tiene atributos (las columnas).
Figura 16: Tablas

Dominio valores posibles de un conjunto. Ejemplo: Dpadron = {1, 2, . . . 100000}
Existe un valor que es posible en cualquier dominio: el valor nulo. Este valor significa atributo desconocido o atributo inexistente. Se puede prohibir, para un atributo, que este tenga el valor nulo, ya que
puede causar problemas al realizar consultas.
Esquema de relacin descripcin de una relacin. Es el nombre de la relacin seguido de la lista de los
atributos con sus dominios. Ejemplo: Estudiante (Padrn, nombre, direccin, fechaIngreso)
Relacin instancia de un esquema. Subconjunto del producto cartesiano de una lista de dominios. Sea el
esquema de relacin R, denotamos a la instancia r mediante r(R).
Tabla representacin de una relacin. Se pueden relacionar entre s al compartir atributos. Una tabla de n
atributos es un subconjunto de D1 D2 Dn . Notar que al ser un conjunto, el orden no interesa.
Atributo nombre de cada columna de una tabla.
Esquema de BD relacional conjunto de esquemas de relacin.
Tupla miembro de una relacin. Son las filas de una tabla.
4.2.
Restricciones del modelo relacional

Regla de integridad de entidad
Ningn atributo de la clave primaria de un esquema de relacin puede tomar valor nulo.
Regla de integridad referencial
Si la relacin r incluye una clave fornea F que es la clave primaria P de una relacin s, entonces todo
valor de F en r debe ser totalmente nulo o ser igual al valor de P en alguna tupla de s.
Pgina 18 de 74
4.3
Operaciones del modelo relacional: lgebra relacional
4.3.
Es un lenguaje formal y procedural que permite realizar consultas sobre un conjunto de relaciones, y
produce relaciones como resultado.
4.3.1.
Operadores bsicos
Los siguientes operadores son linealmente independientes. Se utilizan para filtrar, cortar y combinar relaciones.
Operaciones unarias
Proyeccin
Proyeccin: a1 ,...,an (r)
Dados los atributos a1 , . . . , an que pertenecen a r, devuelve una relacin de esquema {a1 , . . . , an }.
Se eliminan las tuplas repetidas.
Seleccin
Seleccin: p (r)
Devuelve una relacin r0 con el mismo esquema que r, en la que las tuplas son aquellas pertenecientes
a r que satisfacen la condicin o el predicado p. La condicin puede ser de dos estilos:
1. Atmica: expresin lgica simple del tipo que utiliza un operador de comparacin , tal que
{=, 6=, <, >, , }. Se permiten dos tipos de expresiones:
a) Atributo atributo
b) Atributo constante
2. Compuesta: utiliza conectores and, or, not.
Renombre
Renombre: R(A1 ,A2 ,...,An ) (E)
Cambia el nombre de la relacin E a R, y tambin cambia el nombre de sus atributos a A1 , A2 , . . . , An .
Pgina 19 de 74
4.3
Operaciones binarias
Unin
Unin: r
Sean r y s instancias homogneas a de las relaciones R y S respectivamente. r contiene m tuplas y s

contiene n tuplas. La unin se define como:
[
r s = {x : x r x s}
Las tuplas repetidas se eliminan.
a Las
relaciones homogneas tienen: (a) la misma cantidad de atributos, y (b) para todo i, el dominio del atributo
i de r es el mismo que el dominio del atributo i de s
Diferencia
Diferencia: r s
Sean r y s instancias homogneas de las relaciones R y S respectivamente. La diferencia se define
como:
r s = {x : x r x 6 s}
Producto cartesiano
Producto cartesiano: r s
Sean r y s instancias de las relaciones R y S respectivamente. El producto cartesiano es el conjunto
de tuplas que resulta de concatenar cada tupla de r con cada tupla de s.
r s = {(r1 , s1 ) ; . . . ; (r1 , sm ) ; . . . ; (rn , s1 ) . . . , (rn , sm )}
Si r tiene n tuplas y s tiene m tuplas, r s tendr n m tuplas. El grado de r s es la suma de los
grados de r y s.
4.3.2.
Operadores secundarios
No proporcionan nuevas funcionalidades, solo simplifican las consultas.

T
1. Interseccin (r s)
Dadas las relaciones r1 y r2 con el mismo esquema, devuelve una relacin r con igual esquema, tal que
r = {x : x r1 x r2 }
\
r s r (r s)
2. Junta (join) (r ./ s)
La junta de dos relaciones r y s segn un predicado P es una relacin de esquema igual al producto
cartesiano r s, cuyas tuplas son el conjunto de tuplas de r s que satisfacen el predicado P .
r ./p s p (r s)
a) Equi-join: dadas las relaciones r y s, es el join segn el predicado r.Ai = s.Aj
b) Auto-join: dada la relacin r, es el join de r consigo mismo segn el predicado 1.Ai 2.Ai donde 1
y 2 son aliases de r.
Pgina 20 de 74
4.3
c) Natural
T join (r s). Requiere que haya atributos compartidos entre las relaciones r y s, y adems
que R S 6= .
r s RS (r.c1 =s.c1 r.c2 =s.c2 r.ch =s.ch (r s))
El join natural es una operacin asociativa, por lo tanto, (r s) t = r (s t).
Figura 17: Junta natural

3. Divisin (r/s).
Sean las relaciones r R con n atributos y s S con m atributos, tal que m < n y S R. La divisin
son todas las tuplas t tales que, multiplicadas por todas las filas u de s, me dan filas que estn en r. El
esquema de la divisin es R S.
r/s 1,...,nm (r) 1,...,nm ((1,...,nm (r) s) r)
Figura 18: Divisin

4. Asignacin (r s)
r no cambia al ejecutar operaciones de actualizacin sobre s.
Pgina 21 de 74
4.4
4.4.
Operadores extendidos
Operadores extendidos
1. Proyeccin generalizada: permite operadores aritmticos como parte de una proyeccin.

F1 ,F2 ,...,Fn (E)
donde E es una expresin de lgebra relacional, y Fi es una expresin aritmtica que involucra constantes
y atributos del esquema E.
2. Funciones agregadas: son funciones que toman como parmetro un multiconjunto 1 .
sum
count
min
max
avg
La forma general es:

G1 ,...Gn GF1 (A1 ),...,Fm (Am ) (E)
donde E una expresin de lgebra relacional; Gi es un atributo para formar grupos, Fi es una funcin
agregada, y Ai es un atributo. Las tuplas de la relacin resultado de E se particionan en grupos de tal
forma que
a) Todas las tuplas en un grupo tienen el mismo valor para Gi i [1, n]
b) Tuplas en distintos grupos tienen distinto valor para Gi i [1, n]
Para cada grupo, la relacin tendr una tupla (g1 , . . . , gn , a1 , . . . , am ) donde para cada i, ai es el resultado
de aplicar la funcin Fi en el multiconjunto, para el atributo Ai del grupo.
Ejemplo: dada la relacin EmpleadosPartTime(nombre,sucursal,salario), la siguiente expresin devuelve
una relacin con un solo atributo (sin nombre) y una sola fila, que contiene el valor de la suma de todos
los salarios:
Gsum(salario) EmpleadosP artT ime
Se puede usar el operador distinct para eliminar mltiples ocurrencias de un valor.
Ejemplo: con la misma relacin anterior, la siguiente expresin devuelve una relacin con un solo atributo
(sin nombre) y una sola fila, que contiene la cantidad de sucursales:
Gcountdistinct(sucursal) EmpleadosP artT ime
Se puede usar el operador de grupos para particionar una relacin y computar una funcin agregada a
cada grupo.
Ejemplo: con la misma relacin anterior, la siguiente expresin devuelve una relacin con dos atributos
(sin nombres), que contiene la suma de salarios de cada sucursal:
sucursal Gsum(salario) EmpleadosP artT ime
3. Join externo (outer join): es una extensin de la operacin de join que lidia con informacin faltante
(null s).
a) Left outer join (r1 ./ r2 ): hace un join natural, y toma todas las tuplas de r1 que no matchearon con
ninguna tupla de r2 , les agrega valores null a los atributos de r2 , y los agrega al resultado.
b) Right outer join (r1 ./ r2 ): hace un join natural, y toma todas las tuplas de r2 que no matchearon
con ninguna tupla de r1 , les agrega valores null a los atributos de r1 , y los agrega al resultado.
1 Un
multiconjunto es un conjunto en el que un valor puede aparecer muchas veces.
Pgina 22 de 74
4.5
Actualizaciones a bases de datos
c) Full outer join (r1 ./ r2 ): combina las dos operaciones anteriores.
Figura 19: Ejemplo de full outer join
4.5.
Actualizaciones a bases de datos
4.5.1.
Delete
En lgebra relacional se expresa como r r E, donde r es una relacin y E es una expresin de consulta.
Solo se pueden borrar tuplas completas, no valores de atributos.
4.5.2.
Insert
En lgebra relacional se expresa como r r E, donde r es una relacin y E es una expresin de consulta,
o una relacin constante con una sola tupla.
4.5.3.
Update
En lgebra relacional se expresa como r F1 ,...,Fn (r), donde r es una relacin y cada Fi es, o el atributo
i-simo de r, o una expresin que involucra solo constantes y el nuevo valor de r, que da el nuevo valor del
atributo i-simo.
4.6.
Vistas (views)
Vista relacin que no es parte del modelo lgico de la base de datos, pero que es visible para el usuario como
una relacin virtual.
1
CREATE VIEW v AS < expresion de consulta >
Limitaciones:
No se pueden ejecutar operaciones de update sobre una vista, salvo que la vista sobre la relacin R cumpla
lo siguiente:
Deben usar SELECT, y no SELECT DISTINCT
La clusula WHERE no debe incluir a R en una consulta anidada
La clusula WHERE no debe incluir a otra relacin
Los atributos del SELECT deben ser NOT NULL
El update solo se ejecutar sobre los atributos del SELECT.
A las operaciones de delete sobre una vista se les pasa la clusula WHERE de la vista (para borrar solo las
tuplas que se pueden ver en la vista).
Si las relaciones subyacentes son modificadas, la vista queda desactualizada. Por eso, en los motores, en
una expresin que involucra una vista, la relacin de la vista se recalcula al evaluar la expresin.
Vista materializada vista que se evala y se almacena fsicamente. Los cambios a estas vistas se realizan de
forma incremental (no se reconstruye toda la vista desde cero)
Pgina 23 de 74
5 Clculo relacional
5.
Clculo relacional
COMPLETAR
6.
Lenguajes de consulta
Query expresin que solicita una porcin de informacin.

Hay dos tipos de lenguajes de consulta (query languages):
1. Procedurales: el usuario indica una serie de operaciones a ejecutar sobre una base de datos para producir
el resultado deseado. Ejemplos: SQL.
2. No procedurales: el usuario indica la informacin deseada, sin especificar el procedimiento para obtenerla. Ejemplos: Datalog (similar a Prolog).
7.
Integridad y seguridad
En SQL, tenemos las siguientes restricciones:
NOT NULL: indica que un atributo no puede tener el valor null
UNIQUE: asegura que para todas las tuplas, el valor del atributo es nico
PRIMARY KEY: asegura que una o varias columnas tengan una identidad nica, no nula
FOREIGN KEY: asegura la integridad referencial de una tabla
CHECK: asegura que el valor de un atributo satisface una condicin especificada
DEFAULT: especifica un valor por defecto cuando no se especifique ninguo
7.1.
1
2
3
Restricciones de dominio
CREATE DOMAIN color AS VARCHAR (10)
DEFAULT SinColor
CHECK ( value IN ( SinColor , Azul , Rojo ) ) ;
4
5
CAST relacion . Atributo AS < dominio >;
6
7
DROP DOMAIN < dominio >;
8
9
7.2.
ALTER DOMAIN < dominio >;
Restricciones de integridad referencial
Ejemplo:
1
2
3
CREATE TABLE hospital (

IdHosp SMALLINT ,
PRIMARY KEY ( IdHosp ) ) ;
4
5
6
7
8
9
CREATE TABLE medico (

IdHosp SMALLINT ,
IdMedico SMALLINT ,
Nombre VARCHAR (40)
PRIMARY KEY ( IdMedico ) ) ;
10
11
12
13
14
ALTER TABLE medico

ADD CONSTRAINT FK_medico
FOREIGN KEY IdHosp
REFERENCES hospital ( IdHosp ) ;
Pgina 24 de 74
7.3
Seguridad y autorizaciones
7.2.1.
Acciones referenciales
Son llamadas SQL que se ejecutan de forma automtica ante la eliminacin o actualizacin de una restriccin
de integridad referencial, para mantener la misma.
1
2
3
4
5
ALTER TABLE medico

ADD CONSTRAINT FK_medico
FOREIGN KEY IdHosp
REFERENCES hospital ( IdHosp )
ON [ DELETE | UPDATE ] [ SET DEFAULT | SET NULL | CASCADE | NO ACTION ];
De esta forma, cuando se elimine o actualice una fila en la tabla Hospital, el sistema de base de datos
ejecutar la accin especificada en la tabla Medico:
SET DEFAULT / SET NULL: se fija el valor predeterminado o nulo en la fila referenciante.
CASCADE: al eliminar una tupla referenciada, las tuplas referenciantes son eliminadas. Al modificar la clave
en la tabla referenciada, el correspondiente valor de la clave fornea es actualizado.
7.3.
Seguridad y autorizaciones
Para brindar autorizaciones, se brindan privilegios. Los privilegios son tipos de autorizaciones para leer,
insertar, actualizar o borrar datos. Tambin existe el privilegio references, que permite declarar claves forneas
al crear relaciones nuevas.
Con la opcin WITH GRANT OPTION se permite que el usuario que recibe el permiso se lo conceda a alguien
ms. El pase de autorizaciones de un usuario a otro se representa con un grafo de autorizacin, donde cada
nodo es un usuario (la raz es el DBA), y las aristas representan autorizaciones concedidas.
Un usuario tiene autorizacin s y solo s existe un camino desde la raz del grafo hacia el nodo usuario.
1
2
3
4
GRANT < privilegios >

ON <[ relacion | vista ] >
TO <[ usuario | rol ] >
[ WITH GRANT OPTION ];
Para eliminar autorizaciones se usa el comando REVOKE. Por defecto, este comando tiene el efecto de revocar
los privilegios que el usuario le brind a otros. Para evitar este efecto cascada, se usa la opcin RESTRICT.
1
2
3
4
REVOKE < privilegios >

ON <[ relacion | vista ] >
FROM <[ usuario | rol ] >
[ RESTRICT ];
Para crear roles:

1
8.
CREATE ROLE instructor ;
Triggers
Trigger: comando que el sistema ejecuta automticamente si un evento satisface cierta condicin. Son un
conjunto de acciones; por ejemplo, enviar un e-mail, ejecutar el rollback de una transaccin, o crear una copia
de la base de datos.
1
2
3
4
5
6
CREATE TRIGGER chequear_horario

[ BEFORE | AFTER ] [ UPDATE | INSERT | DELETE ] [ OF atributo ] ON curso
WHEN condicion
BEGIN
acciones
END
Pgina 25 de 74
Parte II
Diseo de bases de datos

Objetivos de diseo de base de datos
Reducir la redundancia de la informacin (porque ocupa espacio y es ms difcil de actualizar):
repeticin de informacin en varias tuplas
Eliminar las anomalas:
De actualizacin: podra darse el caso de que actualizamos una tupla y no actualizamos
otra tupla con el mismo dato
De insercin: no es posible insertar ciertos datos sin insertar otros (posiblemente no relacionados)
De eliminacin: podra darse el caso de que eliminamos una tupla y, sin querer, borramos
un dato importante
Devolver informacin rpidamente
Notacin
Nombre de esquemas: R, S, R1 , . . . , Rn , S1 , . . . , Sn
Instancias de esquemas: r, s, r1 , . . . rn , s1 , . . . , sn
Conjuntos de atributos: , ,
Atributos: A, B, C
Tuplas: t1 , t2
9.
Dependencias funcionales
Dependencia funcional sea el esquema R, y sean R y R. La dependencia funcional se cumple

si para cada par de tuplas t1 , t2 tal que t1 [] = t2 [], tambin se cumple que t1 [] = t2 [].
Una dependencia funcional es trivial si . En particular, es trivial.
Un conjunto K es superclave de R si K R.
Un conjunto J es clave candidata de R si J R y adems 6 J/ R.
Una dependencia funcional, a diferencia de una diferencia multivaluada o de junta, prohbe que ciertas
tuplas existan.
Dependencias funcionales implicadas sea el esquema R. Una dependencia funcional f est lgicamente
implicada por un conjunto de dependencias F , si para cada instancia de relacin r(R) que cumple F ,
tambin cumple f .
9.1.
Axiomas de Armstrong
Se utilizan para hallar las dependencias funcionales implicadas, es decir, F + de un conjunto F .

Pgina 26 de 74
9.2
Clausura y superclaves
Axiomas de Armstrong
1. Regla de reflexividad
Si es un conjunto de atributos y , entonces ( ) F +
2. Regla de augmentacin
Si es una dependencia funcional y es un conjunto de atributos, entonces ( )
F+
3. Regla de transitividad
Si es una dependencia funcional y es otra dependencia funcional, entonces
( ) F +
Propiedades deducidas de los axiomas de Armstrong

1. Regla de unin
Si se cumplen y , entonces tambin se cumple
2. Regla de descomposicin
Si se cumple , entonces tambin se cumplen y
3. Regla de pseudotransitividad
Si se cumplen y , entonces tambin se cumple
Teorema: R satisface la dependencia funcional X Y s y slo s R descompone sin prdida sobre los
esquemas XY y X(R XY ), es decir, si R satisface la dependencia de junta (XY, X(R XY ))
9.2.
Clausura y superclaves
Clausura de F sea F un conjunto de dependencias funcionales sobre el esquema R. F + es el conjunto de

dependencias funcionales implicadas por F .
F + = { /F }
Algoritmo 1 Computar F +
Entrada: relacin R, conjunto de dependencias funcionales F
Salida: F +
1. F + = F
2. Repetir hasta que F + no vare:
a) Para cada dependencia funcional f en F + :
Aplicar reglas de reflexividad y aumentacin a f
Agregar las dependencias funcionales restantes a F +
b) Para cada par de dependencias funcionales f1 , f2 en F + :
Si f1 , f2 pueden combinarse usando el axioma de transitividad:
Agregar la dependencia funcional resultante a F +
3. Devolver F +
Para un esquema R con n atributos, hay 2n+1 posibles dependencias funcionales.
Pgina 27 de 74
9.3
Cubrimiento minimal
Clausura de bajo F es el conjunto de atributos de R que dependen funcionalmente de .

+
F
= {/ R F }
Algoritmo 2 Computar +
Entrada: relacin R, conjunto de dependencias funcionales F , atributo
+
Salida: F
1. a+ = a
2. Repetir hasta que a+ no vare:
a) Para cada dependencia funcional B Y F :
Si B a+ : a+ = a+ Y
3. Devolver a+
Usos del algoritmo de clculo de la clausura de a+
1. Para determinar si es una superclave de R: debe cumplirse que + = R.
2. Para determinar si la dependencia funcional F + : debe cumplirse que + .
3. Es una forma alternativa de calcular F +
Algoritmo 3 Clculo de claves candidatas mediante un grafo
Entrada: relacin R, conjunto de dependencias funcionales F
Salida: claves candidatas de R
1. Dibujar el grafo de dependencias funcionales (si X Y F , dibujar una arista entre X e Y )
2. Vni = atributos sin aristas entrantes
3. Voi = atributos que solo tienen aristas entrantes
4. K = {}
5. Repetir hasta que no se pueda agregar nada a K:
a) CC = todos los atributos de Vni
b) Agregar a CC un atributo de R que no est en Voi ni Vni
c) K = K CC
6. Devolver K
9.3.
Cubrimiento minimal
Atributo extrneo atributo de una dependencia funcional que se puede quitar de la misma sin cambiar la
clausura del conjunto de dependencias funcionales.
Sea el conjunto de dependencias funcionales F y la dependencia funcional en F .
El atributo A es extrneo en si, cuando lo sacamos de , la dependencia funcional se sigue cumpliendo (B ( A)+
F ). Formalmente:
A , y
F implica lgicamente a (F { B}) {( A) }
El atributo B es extrneo en si, cuando lo sacamos de , la dependencia funcional se sigue cumpliendo ( ( B)) Formalmente:
Pgina 28 de 74
10 Primera forma normal (1FN)
B , y
El conjunto (F { }) { ( B)} implica lgicamente a F
Cubrimiento minimal: El cubrimiento minimal Fmin para F es un conjunto de dependencias funcionales
tales que F implica todas las dependencias en Fmin , y Fmin implica todas las dependencias en F .
Fmin debe tener las propiedades siguientes:
Ninguna dependencia funcional en Fmin contiene un atributo extrneo
No existen dos dependencias funcionales 1 y 2 en Fmin tales que 1 = 2 . Es decir, los
lados izquierdos deben ser nicos
Algoritmo 4 Clculo de cubrimiento minimal
Entrada: conjunto de dependencias funcionales F
Salida: cubrimiento minimal Fmin
1. Usar el axioma de la descomposicin para dejar un solo atributo en el lado derecho de cada dependencia
funcional.
2. Eliminar los atributos extrneos de los lados izquierdos.
Sea Y B una dependencia funcional en F , con al menos dos atributos en Y . Sea Z igual a Y pero con
algn atributo de menos. Si F implica a Z B, entonces reemplazar Y B con Z B.
3. Eliminar las dependencias funcionales redundantes (es decir, que se deducen de los axiomas de Armstrong).
Ejemplo: sea el conjunto de dependencias F = {A BD, B CD, AC E}. Calcular el cubrimiento

minimal.
1. Dejar todos los lados derechos con un nico atributo.
Fmin = {A B, A D, B C, B D, AC E}
2. Eliminar todos los atributos redundantes del lado izquierdo.
a) Hay que analizar solamente la dependencia que tiene lado izquierdo compuesto: AC E.
+
b) C es redundante en AC E? Hay que verificar si E est en A+
F . Como AF = ABCDE, entonces
C es redundante en AC E y podemos reemplazar esta dependencia funcional por A E.
Fmin = {A B, A D, B C, B D, A E}
3. Eliminar las dependencias redundantes.
Hay que revisar una por una todas las dependencias de Fmin . En caso de que una sea redundante, se
la elimina de Fmin y se sigue analizando el resto tomando como referencia el nuevo Fmin .
A D es redundante en Fc ? Hay que verificar si D est en A+
Fc {AD}
Fmin {A D} = {A B, B C, B D, A E}
A+
Fmin {AD} = ABCDE
Como D Fmin {A D}, A D es redundante
Fmin = {A B, B C, B D, A E}
Puede comprobarse que el resto de las dependencias funcionales no es redundante.
10.
Primera forma normal (1FN)
Dominio atmico los elementos del dominio se consideran unidades indivisibles.

Pgina 29 de 74
11 Descomposicin de una relacin
Primera forma normal (1FN)

Una relacin con esquema R est en 1FN si los dominios de sus atributos son atmicos, y si no hay
atributos similares repetidos.
Ejemplo: la siguiente relacin no est en 1FN.

Ttulo Libro
Database System Concepts
Applied Cryptography
Autor 1
Avi Silberschatz
Bruce Schneier
Autor 2
Henry Korth
NULL
Autor 3
S. Sudarshan
NULL
Para normalizarla, hay que dividirla en dos relaciones.

ID libro
1
2
11.
ID libro
1
1
1
2
Ttulo Libro
Database System Concepts
Applied Cryptography
Autor
Avi Silberschatz
Henry Korth
S. Sudarshan
Bruce Schneier
Descomposicin de una relacin

Descomposicin de una relacin
Sea el esquema relacional R. El conjunto de esquemas {R1 , R2 , . . . , Rn } es una descomposicin de R
si
R = R1 R2 Rn
Sea la relacin r(R). Sean ri = Ri (r) para i = 1, 2, . . . , n. Es decir, {r1 , r2 , . . . , rn } es la base de
datos que resulta de descomponer R en {R1 , R2 , . . . , Rn }. Siempre se verifica que
r r1 ./ r2 ./ . . . ./ rn
Es decir, r es un subconjunto de la junta de la descomposicin (la junta podra tener tuplas que no
estn en r).
Propiedades deseadas de la descomposicin

1. Sin prdida de informacin
Verifica que r = R1 (r) ./ R2 (r) ./ . . . ./ Rn (r).
2. Preservacin de dependencias
Una descomposicin que verifica que F 0+ = F + preserva dependencias, donde F 0 = F1 F2
Fn son las dependencias proyectadas.
Esta propiedad es deseable porque significa que podemos chequear si se cumple la dependencia
con solo verificarla en una relacin individual, y no necesitamos hacer un join de las relaciones
de la descomposicin.
3. Poca o nula redundancia de informacin
Pgina 30 de 74
11.1
Descomposicin SPI en 2 relaciones
Algoritmo 5 Clculo de la proyeccin de dependencias Fi

Entrada: relacin R, relacin Ri , conjunto de dependencias funcionales F
Salida: conjunto de dependencias funcionales que se verifican en Ri (Fi )
1. Fi = {}
2. Para cada conjunto de atributos X que es un subconjunto de atributos de Ri :
a) Calcular XF+
b) Fi = Fi {X A}, tal que A XF+ y A Ri
3. Devolver Fi
Algoritmo 6 Clculo para saber si una descomposicin preserva una dependencia

Entrada: dependencia funcional A B, conjunto de dependencias funcionales F , descomposicin {R1 , . . . , Rn }
Salida: verdadero si la descomposicin preserva A B
1. Z = A
2. Repetir hasta que Z no vare o hasta que Z incluya a B:
h
i
+
Para cada Ri : Z = Z (Z Ri ) Ri
3. Si B Z: devolver verdadero
4. Si no: devolver falso.
11.1.
Sea el esquema relacional R, y sea F el conjunto de dependencias funcionales sobre R. Sean R1 y R2 una
descomposicin de R. Esta descomposicin es sin prdida de informacin (SPI) si al menos una de las siguientes
dependencias funcionales est en F + :
R1 R2 R1 R2
R1 R2 R2 R1
Ejemplo: La descomposicin de R(A, B, C, D, E, F ) en R1 = (A, D, E, F ) y R2 = (B, C, D) es SPI respecto
de F = {A BD, B CD, AC E}?
R1 R2 = D
R1 R2 = AEF
R2 R1 = BC
Como DF+ = {D}, vemos que no se cumplen ni R1 R2 R1 R2 ni R1 R2 R2 R1 . Por lo tanto,
esta descomposicin no es SPI.
11.2.
Descomposicin SPI en ms de 2 relaciones
El algoritmo Chase Tableau se utiliza para verificar si una descomposicin de R en R1 , . . . , Rk (k > 2)

es SPI. Es decir, si la proyeccin de un esquema restringido por dependencias en una descomposicin, puede
recuperarse haciendo el join de las proyecciones.
Pgina 31 de 74
11.2
Algoritmo 7 Algoritmo Chase Tableau

Entrada: esquema de relacin R, conjunto de dependencias funcionales F , descomposicin {R1 , . . . , Rk }
Salida: verdadero si {R1 , . . . , Rn } descompone SPI.
1. Armar una matriz T (0) con las relaciones Ri en las filas (i = 1, . . . , k) y los atributos Aj en las columnas.
Cada elemento de la matriz tendr valor:
(
aj
si Aj Ri (variable distinguida)
mij =
bij si Aj 6 Ri (variable ligada)
2. i = 1
3. Obtener T (i) :
Para cada dependencia funcional X Y F :
Si tuplas t1 , t2 tal que t1 [X] = t2 [x], realizar un cambio de variable en t1 [Y ] y en t2 [Y ]
Variables ligadas por distinguidas
Si hay dos ligadas, poner la de menor subndice
4. Si hay una fila slo con variables distinguidas, devolver verdadero.
5. Si T (i) = T (i1) y adems no hay una fila slo con variables distinguidas, devolver falso.
6. Si no, i i + 1 y volver a 3.
Ejemplo: sea el esquema de relacin R(A, B, C, D) con F = {A B, B C, CD A}. Sea la descomposicin R1 = (A, D), R2 = (A, C), R3 = (B, C, D). La descomposicin es SPI?
R1 (A, D)
R2 (A, C)
R3 (B, C, D)
A
a1
a1
b31
B
b12
b22
a2
C
b13
a3
a3
D
a4
b24
a4
Aplicamos A B. Como a1 es igual en las primeras dos filas, pero b12 y b22 no, cambiamos b22 por b12 en
la segunda fila.
R1 (A, D)
R2 (A, C)
R3 (B, C, D)
A
a1
a1
b31
B
b12
b12
a2
C
b13
a3
a3
D
a4
b24
a4
Aplicamos B C. Las filas 1 y 2 coinciden en b12 pero no en c. Entonces, cambiamos b13 por a3 en la fila 1.
R1 (A, D)
R2 (A, C)
R3 (B, C, D)
A
a1
a1
b31
B
b12
b12
a2
C
a3
a3
a3
D
a4
b24
a4
Aplicamos CD A. Las filas 1 y 3 tienen mismo valor para c y d, pero distinto valor para a. Por lo tanto,
cambiamos b31 por a1 en la tercera fila.
R1 (A, D)
R2 (A, C)
R3 (B, C, D)
A
a1
a1
a1
B
b12
b12
a2
C
a3
a3
a3
D
a4
b24
a4
En este punto notamos que la fila 3 tiene valores de la forma aj . Como son todas variables distinguidas, la
descomposicin es sin prdida de informacin.
Pgina 32 de 74
12 Segunda forma normal (2FN)
12.
Segunda forma normal (2FN)
Atributo primo atributo de R que pertenece a una clave candidata.

Segunda forma normal (2FN)
Sea R una relacin y F el conjunto de sus dependencias funcionales. R estar en 2FN si para
toda dependencia funcional X Y que est en en F + , se cumple al menos una de las siguientes
condiciones:
1. X Y es trivial
2. Y es un atributo primo,
3. X no es un subconjunto de una clave candidata
Ejemplo: la siguiente relacin no est en 2FN porque Direccin de local depende slo de ID de local, que
no es una clave.
ID de cliente
1
1
2
ID de local
1
3
1
Direccin de local
Los Angeles
San Francisco
Los Angeles
F = {Id cliente, Id local Direccion local; Id local Direccion local}.

La segunda dependencia funcional no es trivial, el lado derecho no pertenece a una clave candidata, y el lado
izquierdo es un subconjunto de la clave candidata.
ID de cliente
1
1
2
13.
ID de local
1
3
1
ID de local
1
3
Direccin de local
Los Angeles
San Francisco
Forma normal Boyce-Codd (FNBC)

Forma normal Boyce-Codd (FNBC)
Un esquema de relacin R est en FNBC con respecto a un conjunto de dependencias funcionales
F si, para todas las dependencias funcionales en F + de la forma , donde R y R, se
cumple alguna de las siguientes:
es trivial (es decir, )
es una superclave para R
Propiedades de la forma normal Boyce-Codd (FNBC)

Cualquier relacin de dos atributos est en FNBC
Brinda eliminacin de anomalas
Brinda una descomposicin SPI
No garantiza que se preserven las dependencias funcionales
Pgina 33 de 74
14 Tercera forma normal (3FN)
Para verificar si una dependencia funcional viola FNBC, alcanza con computar + y ver si es R.
Para verificar si una relacin R est en FNBC, alcanza con ver si las dependencias de F no violan FNBC.
Para verificar si una descomposicin Ri est en FNBC, para cada subconjunto de atributos de Ri , verificar
+
que F
o no incluya atributos de Ri , o incluya todos los atributos de Ri .
Algoritmo 8 Descomposicin FNBC
Entrada: una relacin R, un conjunto de dependencias funcionales F
Salida: una descomposicin = {R1 , . . . , Rn } tal que Ri est en FNBC con respecto a Fi
1. = R
2. Repetir hasta que no haya esquemas en que violen FNBC
a) Elegir una dependencia funcional X Y que viole FNBC sobre i
b) Descomponer i en dos relaciones:
R1 (XY )
R2 (X(R XY ))
c) En , reemplazar i por R1 y R2
3. Devolver
14.
Tercera forma normal (3FN)

A statement of Codds definition of 3NF, paralleling the traditional pledge to give true evidence in a
court of law, was given by Bill Kent: [Every] non-key [attribute] must provide a fact about the key,
the whole key, and nothing but the key. A common variation supplements this definition with the
oath: so help me Codd.
Requiring existence of the key ensures that the table is in 1NF; requiring that non-key attributes be
dependent on the whole key ensures 2NF; further requiring that non-key attributes be dependent on
nothing but the key ensures 3NF.
Tercera forma normal (3FN)

Un esquema de relacin R est en 3FN con respecto a un conjunto de dependencias funcionales F
si, para todas las dependencias funcionales en F + de la forma , donde R y R, se
cumple alguna de las siguientes:
es trivial (es decir, )
es un atributo primo
Dicho de otra forma, R no debe tener dependencias funcionales transitivas: todos los atributos que
no son clave deben depender funcionalmente de la clave primaria.
Pgina 34 de 74
15 Dependencias multivaluadas
Propiedades de la tercera forma normal (3FN)

No tiene prdida de informacin
No hay prdida de dependencias
No garantiza la eliminacin de anomalas (es decir, tiene redundancia)
Es menos estricta que FNBC (FNBC = 3FN)
Algoritmo 9 Descomposicin 3FN

Entrada: una relacin R, un cubrimiento minimal Fmin
Salida: una descomposicin = {R1 , . . . , Rn } tal que Ri est en 3FN con respecto a Fi
1. = {}
2. Para cada dependencia funcional X Y Fmin :
= Ri (XY )
3. Si existen Ri , Rj tal que Ri Rj :
= Ri
4. Si ninguna relacin es una superclave de R, y K es una clave para R
=K
5. Devolver
Ejemplo: la siguiente relacin no est en 3FN porque Fecha de nacimiento del ganador depende slo de
Ganador, que depende de la clave candidata {Torneo, Ao}.
Torneo
Indiana Invitational
Cleveland Open
Des Moines Masters
Ao
1998
1999
1999
1999
Ganador
Al Fredrickson
Bob Albertson
Al Fredrickson
Chip Masterson
Fecha de nacimiento de ganador

21 Julio 1975
28 Septiembre 1968
21 Julio 1975
14 Marzo 1977
F = {T orneo, A
no Ganador, Ganador F echa nacimiento ganador}. La segunda dependencia funcional no es trivial, el lado derecho no pertenece a una clave candidata (no es atributo primo), y el lado izquierdo
no es una superclave.
Torneo
Cleveland Open
Des Moines Masters
15.
Ao
1998
1999
1999
1999
Ganador
Al Fredrickson
Bob Albertson
Al Fredrickson
Chip Masterson
Ganador
Chip Masterson
Al Fredrickson
Bob Albertson
Fecha de nacimiento
14 Marzo 1977
21 Julio 1975
28 Septiembre 1968
Dependencias multivaluadas
Una dependencia multivaluada expresa que dos conjuntos de atributos en un esquema son mutuamente
independientes.
Sean los conjuntos de atributos disjuntos A y B de la relacin R(A, B, U A B). Sean las tuplas t1 y t2 .
La dependencia multivaluada A B indica que si t1 [A] = t2 [A], entonces podemos encontrar tuplas t3 y t4
tales que:
t1 [A] = t2 [A] = t3 [A] = t4 [A]
Pgina 35 de 74
15.1
Propiedades de las DMVs
t3 [B] = t1 [B]
t3 [U A B] = t2 [U A B]
t4 [B] = t2 [B]
t4 [U A B] = t1 [U A B]
Figura 20: Dependencia multivaluada

Ejemplo: sea R(curso, libro, prof esor) una relacin que indica una lista de cursos universitarios, los libros
que se usan en el curso, y los profesores que la dictan.
Curso
lgebra II
lgebra II
lgebra II
Algebra II
Libro
David Lay - Algebra Lineal
Strang - Algebra Lineal
David Lay - Algebra Lineal
Strang - Algebra Lineal
Profesor
Acero
Acero
Piortrowsky
Piortrowsky
Dado que los profesores de un curso y los libros de un curso son independientes entre s, esta relacin tiene una DMV. Si tuvisemos que agregar un nuevo libro al curso lgebra II, deberamos agregar una tupla
para cada profesor del curso. Es decir, formalmente, hay dos DMV en esta relacin: {curso} {libro} y
{curso} {prof esor}. Esta relacin exhibe redundancia.
Dependencia multivaluada: no existen en el esquema original pero son satisfechas por la descomposicin
del mismo.
15.1.
Propiedades de las DMVs
es trivial si si R = .
Una dependencia multivaluada garantiza que ciertas tuplas existan.
Regla de transitividad multivaluada: Si y c, entonces c
Regla de replicacin: si , entonces . La inversa no es cierta.
(
(
Z
Regla de interaccin 2 : si
y existe un tal que
, entonces Z
Z
=
Regla de aumentacin: si entonces w .
Regla del complemento: si , entonces R
Regla de unin: si , y c, entonces c
c
Regla de descomposicin: si , y c, entonces c
c
2 Esta
regla puede agregar dependencias funcionales a M
Pgina 36 de 74
15.2
Preservacin de dependencias multivaluadas
Regla de pseudotransitividad: si y c , entonces c c

Si R = {A1 , . . . , An , B1 , . . . , Bm }, entonces {A1 , . . . , An } {B1 , . . . , Bm }
Teorema: las nicas DMVs implicadas por un conjunto de DFs son de la forma X Y , donde Y X + o
R XY X + .
Teorema: las nicas DFs implicadas por un conjunto de DMVs son las triviales.
Teorema: un conjunto de DFs de tipo xi yi slo implica DMVs de tipo xi yi .
Teorema: sea r una instancia del esquema de relacin R, X, Y subconjuntos de R, y Z = R XY . La
relacin r satisface la DMV X Y s y solo s R1 = XY y R2 = X Z descomponen sin prdida de informacin
a r.
Algoritmo 10 Verificar si r satisface la dependencia multivaluada X Y
Entrada: relacin r(R)
Salida: verdadero si la dependencia multivaluada X Y se satisface
1. Proyectar r en R1 (XY ) y R2 (X, R XY )
2. Calcular R1 ./ R2
3. Si r = R1 ./ R2 devolver verdadero
Algoritmo 11 Proyeccin de dependencias funcionales y multivaluadas

Entrada: conjunto de dependencias funcionales y multivaluadas D+ , descomposicin {R1 , . . . , Rn }
Salida: conjunto de dependencia funcionales y multivaluadas Di que se satisfacen en Ri
1. Z = {}
2. Agregar a Z las dependencias funcionales de D+ que solo incluyan atributos de Ri
3. Agregar a Z las dependencias multivaluadas de la forma A B Ri , donde A B est en D+ y A Ri
4. Devolver Z
15.2.
Preservacin de dependencias multivaluadas
Una descomposicin de R en los esquemas R1 , . . . , Rn es una descomposicin que preserva las dependencias con respecto a un conjunto D de dependencias funcionales y multivaluadas si, para cada relacin
r1 (R1 ), . . . , rn (Rn ) tal que para cada i, ri satisface Di , entonces existe una relacin r(R) que satisface D y para
el cual ri = Ri (r) para todo i.
15.3.
Base minimal de Dependencias e Implicacin de DMVs
Base minimal sea la coleccin de conjuntos S = {S1 , . . . , Sp } donde U = S1 . . . Sp . La base minimal de S

es Base(S) y es una particin de U {T1 , . . . , Tq } tal que:
1. Cada Si es la unin de algunos de los Tj .
2. No existe una particin de U con menos elementos que cumpla la primera propiedad.
Ejemplo: sea S = {ABCD, CDE, AE} y U = ABCDE. Entonces la base de S es Base(S) = {A, B, CD, E}.
Base de dependencias sea M un conjunto de dependencias multivaluadas sobre R, y sea X R. Sea G =
{Y /M |= X Y }. La base de dependencias de X con respecto a M es:
Bdep(X) = Base (G)
Pgina 37 de 74
16 Cuarta forma normal (4FN)
Ejemplo: sea M = {A BC, DE C} un conjunto de dependencias multivaluadas sobre R(ABCDE).

Entonces G = {A, BC, DE, C, BDE, B, BCDE, CDE}y la base de A es
Base(A) = {A, B, C, DE}
Algoritmo 12 Clculo de la base de dependencias de X
Entrada: conjunto de dependencias multivaluadas M , conjunto de atributos X
Salida: Bdep(X)
1. T = R X
2. Mientras T vare:
Si V T y Y Z M tal que (V Y = ) y (V Z 6= )
Reemplazar V por {V Z} y {V Z}
3. Bdep(X) = T {A/A X}
Implicacin de dependencias dado un conjunto M de dependencias multivaluadas, una dependencia multivaluada X Y pertenece a M + s y solo s Y se puede expresar como la unin de algunos componentes
de Bdep(X).
Ejemplo: sea R(A, B, C, D, E, I), M = {A EI, C AB}. Se cumple AC BI?
La base de dependencias de AC es:
1. T (0) = BDEI
a) V = BDEI. Entonces A EI, Y = A, Z = EI
b) V Z = EI
c) V Z = BD
2. T (1) = {EI, BD}
a) Si V = EI, Y = A, Z = EI, V Z = EI, V Z = {} y no nos aporta nada.
b) V = BD. Entonces C AB, Y = C, Z = AB
c) V Z = B
d) V Z = D
3. T (2) = {EI, B, D}
Bdep(AC) = {EI, B, D, A, C} y entonces AC BI no se cumple porque BI no se puede expresar como la
unin de componentes de Bdep(AC).
16.
Cuarta forma normal (4FN)

Cuarta forma normal (4FN)
Un esquema de relacin R est en 4FN con respecto a un conjunto de dependencias funcionales y
multivaluadas M si, para todas las dependencias multivaluadas en M + de la forma , donde
R y R, se cumple alguna de las siguientes:
es trivial
Pgina 38 de 74
16.1
Propiedades de la cuarta forma normal (4FN)

No tiene prdida de informacin
Una descomposicin 4FN no garantiza la preservacin de dependencias
Ejemplo: la siguiente relacin no est en 4FN. La clave es {N V uelo, Dia de la semana, T ipo de avi
on}.
N Vuelo
106
106
106
106
Dia de la semana
Lunes
Martes
Lunes
Martes
Tipo de avin
B737
B737
A380
A380
F = {N V uelo Dia de la semana, N V uelo T ipo de avi

on}. La primera dependencia multivaluada no
es trivial, y el lado izquierdo no es una superclave de R.
NVuelo
106
106
16.1.
Dia de la semana
Lunes
Martes
N Vuelo
106
106
Tipo de avin
B737
A380
Sea el esquema relacional R, y sea M el conjunto de dependencias funcionales y multivaluadas sobre R. Sean
R1 y R2 una descomposicin de R. Esta descomposicin es sin prdida de informacin (SPI) si al menos una
de las siguientes dependencias multivaluadas est en M + :
1. R1 R2 R1 R2
2. R1 R2 R2 R1
16.2.
El algoritmo es idntico al de descomposicin en BCFN, excepto que se usan dependencias multivaluadas y

se restringe Ri al conjunto M + .
Entrada: una relacin R, un conjunto de dependencias multivaluadas M +
Salida: una descomposicin = {R1 , . . . , Rn } tal que Ri est en 4FN con respecto a Mi
1. = R
2. Repetir hasta que no haya esquemas en que violen 4FN
a) Elegir una dependencia multivaluada X Y que viole 4FN sobre i
b) Descomponer i en 2 relaciones:
R1 (XY )
R2 (X(R XY ))
c) En , reemplazar i por R1 , R2
3. Devolver
Pgina 39 de 74
17 Dependencias de junta
17.
Dependencias de junta
Sea un esquema de relacin R y sea la descomposicin R1 , . . . , Rn . La dependencia de junta (R1 , . . . , Rn )

restringe el conjunto de relaciones posibles a aquellas para las cuales R1 , . . . Rn es una descomposicin sin
prdida de informacin.
Formalmente, si R = R1 Rn , una relacin r(R) satisface la dependencia de junta (R1 , . . . , Rn ) si
r = R1 (r) ./ ./ Rn (r)
La dependencia de junta (R1 , . . . , Rk ) se satisface para R si restringe los valores de toda instancia r(R) tal
que, si existen k tuplas t1 , . . . , tk que satisfacen ti [Ri Rj ] = tj [Ri Rj ], luego tambin existe en r otra tupla
tk+1 definida por tk+1 [Ri ] = ti [Ri ] para 1 i k.
Propiedades:
Si una de las Ri es R, la dependencia de junta es trivial.
Toda dependencia de junta (R1 , R2 ) es equivalente a la dependencia multivaluada R1 R2 R2 .
No existen un conjunto de reglas para inferir dependencias de juntas.
Teorema: R satisface la dependencia multivaluada X Y s y slo s R descompone sin prdida sobre los
esquemas X Y y X(R XY ), es decir, si R satisface la dependencia de junta (XY, X(R XY ))
Teorema: si una relacin R puede descomponerse SPI en 3 esquemas, pero no puede hacerlo sobre 2, esa
relacin solo satisface DMVs triviales.
Ejemplo: sea la relacin R(A, B, C) y la dependencia de junta |{z}

AB , |{z}
BC , |{z}
AC . Qu tupla debe tener
R1
r para satisfacer la misma?

r
t1
t2
t3
A
1
4
4
1
B
2
5
2
8
R2
R3
C
3
6
7
7
Dado que se cumplen:

t1 [R1 R2 ] = t2 [R1 R2 ] = 2
t1 [R1 R3 ] = t3 [R1 R3 ] = 1
t2 [R2 R3 ] = t3 [R2 R3 ] = 7
Entonces para que se satisfaga la dependencia de junta deber existir una tupla t4 tal que:
t4 [R1 ] = t1 [R1 ] = {1, 2}
t4 [R2 ] = t2 [R2 ] = {2, 7}
t4 [R3 ] = t3 [R3 ] = {1, 7}
Es decir, deber existir la tupla (1, 2, 7).
17.1.
Dependencias de junta embebidas
Un esquema de relacin r(R) satisface la dependencia de junta embebida DJE (R1 , . . . , Rp ) si S (r)
satisface la dependencia de junta (R1 , . . . , Rp ), donde S = R1 R2 . . . Rp .
Notar que r puede no satisfacer la DJE.
Pgina 40 de 74
18 Quinta forma normal (5FN)
18.
Quinta forma normal (5FN)

Quinta forma normal (5FN)
Una relacin R est en 5FN con respecto a un conjunto de dependencias funcionales, multivaluadas
y de junta D, si para todas las dependencias de junta en D+ de la forma (R1 , . . . , Rn ) donde cada
Ri R y R = R1 Rn , al menos una de las siguientes condiciones se cumple:
La dependencia de junta (R1 , . . . , Rn ) es trivial
Cada Ri es una superclave de R
Propiedades de la quinta forma normal (5FN)

Toda relacin que est en 5FN est en 4FN, y est en BCNF.
Una descomposicin 5FN no garantiza la preservacin de dependencias.

Entrada: una relacin R, un conjunto de dependencias D+
Salida: una descomposicin = {R1 , . . . , Rn } tal que Ri est en 5FN con respecto a Di
1. = R
2. Repetir hasta que no haya esquemas en Z que violen 5FN
a) Elegir una dependencia de junta (DJ1 , . . . DJk )que viole 5FN sobre i
b) Descomponer i en k relaciones:
R1 (DJ1 )
Rk (DJk )
c) En , reemplazar por R1 , . . . , Rk
3. Devolver
(ABCD, CDE, BDI)
(AB, BCD, AD)

Ejemplo: sea D =
sobre el esquema de relacin R = ABCDEI.
A BCDE
BC AI
Las clave candidata de R son, por las dependencias funcionales, {A, BC}.
R no est en 5FN porque la dependencia de junta (ABCD, CDE, BDI) no es trivial, y CDE, BDI no
son superclaves de R.
R1 = ABCD
La descomposicin R = R2 = CDE s est en 5FN porque:
R3 = BDI
Para R1 aplica la dependencia de junta (AB, BCD, AD), y todos los miembros son superclaves de R,
por lo tanto est en 5FN.
Para R2 solo aplican dependencias de junta triviales.
Para R3 solo aplican dependencias de junta triviales.
Pgina 41 de 74
18.1
18.1.
Implicacin de dependencias
Implicacin de dependencias
Utilizar el algoritmo Chase Tableau.
Pgina 42 de 74
Parte III
SQL
Componentes:
1. DDL (Data Definition Language)
2. DML (Data Manipulation Language)
3. CL (Control Language)
Para identificar unvocamente a una relacin, se utiliza el formato <catalogo>.<esquema>.<relacin>
19.
DDL
DDL: Lenguaje de definicin de datos para especificar el esquema de la base de datos, eliminar relaciones,
modificar esquemas, crear vistas, crear restricciones de integridad, especificar derechos de acceso, etc.
19.1.
Tipos de dominios
char(n): texto de longitud n

varchar(n): texto de longitud variable, con un mximo de n caracteres
nvarchar(n): texto de longitud variable, con un mximo de n caracteres, utilizando el formato Unicode
int
smallint
numeric(p,d): p dgitos con signo, y d de los p dgitos estn a la derecha del punto decimal.
real, double precision
float(n)
date
time
timestamp
clob(n): character large object de n bytes
blob(n): binary large object de n bytes
19.2.
1
2
3
4
Create table
CREATE TABLE r ( A1 D1 , A2 D2 , ... , An Dn ,

< restriccion - integridad1 > ,
... ,
< restriccion - integridadK >) ;
La instruccin anterior crea una tabla llamada r con atributos Ai , y Di es el dominio del atributo Ai .
Las restricciones de integridad pueden ser:
primary key (Aj1 , Aj2 , . . . , Ajm ): los atributos Aji , con i [1, m] forman la clave primaria de cada tupla.
No pueden ser null, y deben ser nicos.
check (P ): todas las tuplas de r deben satisfacer el predicado P .
foreign key:
Pgina 43 de 74
19.3
1
2
Drop table
FOREIGN KEY ( atr ) REFERENCES rel

ON [ UPDATE | DELETE ] [ CASCADE | SET NULL | SET DEFAULT ];
Se establece que el atributo atr es una clave primaria en la relacin rel. Se puede especificar lo que sucede
si se produce una actualizacin o un borrado de dicho valor en la relacin rel:
Cascade: se actualiza/elimina la tupla en esta relacin
Set null: la clave fornea se establece en null
Set default: la clave fornea se establece en su valor por default
assert: define una restriccin aplicable a varias tablas.
1
2
19.3.
CREATE ASSERTION nombre_asercion

CHECK P
Drop table
La instruccin DROP TABLE r elimina todas las tuplas de la tabla r y el esquema de relacin r.
19.4.
Alter table
La instruccin puede utilizarse para agregar atributos nuevos (con valor null ) o para eliminarlos.
1
2
3
4
ALTER TABLE r
ADD < Atributo > < Dominio >;
ALTER TABLE r
DROP < Atributo >;
Diccionario de datos: contiene metadatos (informacin sobre los datos), en particular, sobre el esquema
de la misma.
20.
DML
DML: lenguaje de manipulacin de datos para expresar las consultas a la base de datos.
Operaciones CRUD (Create, Read, Update, Delete)
lgebra relacional
attr (r)
cond (r)
rs
SQL
SELECT attr FROM r
SELECT * FROM r WHERE cond
SELECT * FROM r,s
La expresin
1
2
3
SELECT a1 , a2 , ... , an
FROM r1 , r2 , ... , rm
WHERE p ;
es equivalente a la expresin a1 ,a2 ,...,an (p (r1 r2 rm )).

El resultado de una expresin SQL puede contener tuplas duplicadas. Para eliminar los duplicados, se
utiliza la clusula SELECT DISTINCT.
Las funciones agregadas no se pueden componer. Por ejemplo, max(count(*)) no es vlido.
Una clusula de tipo SELECT * indica que se seleccionan todos los atributos de las relaciones en la clusula
FROM.
El operador de renombre as: SELECT viejo-nombre AS nuevo-nombre
El operador like se puede usar dentro de una clusula where para buscar valores que cumplan un patrn,
especificado con los siguientes caracteres especiales:
Pgina 44 de 74
20.1
Consultas anidadas
%: matchea cualquier sub string

_: matchea un caracter cualquiera
El operador order by <atributo(s)>[asc|desc] ordena el resultado de una consulta por uno o varios
de los atributos, de forma ascendente o descendente (ascendente por default).
Operadores sobre conjuntos:
Union
Intersect
Except
El operador group by permite agrupar tuplas en base a uno o ms atributos (las tuplas con el mismo valor
para los atributos en esta clusula se ponen en un mismo grupo). Los atributos en la clusula select, por
fuera de las funciones agregadas, deben estar en el operador group by. La sintaxis es:
1
2
3
4
SELECT expr1 , ... , exprN , funcionAgregada ( expr )

FROM tablas
WHERE condiciones
GROUP BY expr1 , ... , exprN ;
Ejemplo: encontrar el promedio del saldo de las cuentas en cada sucursal de un banco.
1
2
3
SELECT sucursal - nombre , AVG ( saldo )

FROM cuentas
GROUP BY sucursal - nombre ;
El operador having permite seleccionar a grupos formados con group by que cumplan una condicin.
Cualquier atributo que est presente en la clusula having sin agregar, debe aparecer en el operador group
by.
1
2
3
4
5
SELECT columna , funcion_agregada ( columna )

FROM tabla
WHERE columna operator value
GROUP BY columna
HAVING funcion_agregada ( columna ) operator value ;
Ejemplo: encontrar los nombres de las sucursales del banco que tengan un promedio general de saldo mayor
a $1200.
1
2
3
4
SELECT sucursal - nombre

FROM cuentas
GROUP BY sucursal - nombre
HAVING AVG ( saldo ) > 1200
Nota: si se utilizan el operador where y el operador having, primero se aplica el where y luego se filtra por
having.
20.1.
Consultas anidadas
En una consulta anidada, el select interno puede tener variables de tuplas definidas dentro del select, o
en cualquier consulta que incluya a sta.
El conector in permite verificar la pertenencia de un valor a un conjunto que es resultado de una clusula
select. De forma equivalente, existe el conector not in.
Ejemplo: encontrar los nombres de los clientes que tienen un prstamo y una cuenta en el banco.
1
2
3
4
SELECT DISTINCT cliente - nombre

FROM pidio - prestamo
WHERE cliente - nombre IN ( SELECT cliente - nombre
FROM tiene - cuenta ) ;
Pgina 45 de 74
20.1
Consultas anidadas
El operador de comparacin some en una clusula where de un select externo devuelve verdadero si el
valor del atributo en cuestin es mayor o menor que al menos un valor de la clusula select interna.
Ejemplo: encontrar los nombres de las sucursales del banco que tienen activos mayores que los de al menos
una sucursal en Brooklyn.
1
2
3
4
5

FROM sucursales
WHERE activos > SOME ( SELECT activos
FROM sucursales
WHERE sucursal - nombre = Brooklyn ) ;
El operador de comparacin all en una clusula where de un select externo devuelve verdadero si el
valor del atributo en cuestin es mayor a todos los valores de la clusula select interna.
Ejemplo: encontrar los nombres de las sucursales del banco que tienen activos mayores que los todas las
sucursales en Brooklyn.
1
2
3
4
5

FROM sucursales
WHERE activos > ALL ( SELECT activos
FROM sucursales
WHERE sucursal - nombre = Brooklyn ) ;
El operador any devuelve verdadero si existe al menos un valor para

Ejemplo: encontrar los clientes que pidieron un prstamo de monto mayor a al menos los activos de una
sucursal.
1
2
3
4
SELECT cliente - nombre

WHERE cantidad > ANY ( SELECT activos
FROM sucursales ) ;
El operador exists devuelve verdadero si la consulta interna no es vaca.

Ejemplo: encontrar los clientes que tienen una cuenta y un prstamo en el banco.
1
2
3
4
5
SELECT cliente - nombre

WHERE EXISTS ( SELECT *
FROM tiene - cuenta
WHERE pidio - prestamo . cliente - nombre =
tiene - cuenta . cliente - nombre ) ;
El operador unique devuelve verdadero si la consulta interna no contiene tuplas duplicadas.

SQL no ofrece en forma nativa la posibilidad de ejecutar el operador divisin. Sin embargo, este se puede
implementar usando consultas anidadas.
Ejemplo: dados los siguientes esquemas relacionales
Estudiante ( Enro , Enombre , Carrera , Anio_cursa , Edad )
Curso ( Cnombre , Horario , Aula , Pid )
Cursa ( Enro , Cnombre )
Profesor ( Pid , Pnombre , departamento )
Hallar los nombres de todos los profesores que ensean en todas las aulas en las que se dicta algn curso.
1
2
3
4
5
6
7
8
SELECT P . Pnombre
FROM Profesor P
WHERE NOT EXISTS ( SELECT C . Aula
FROM Curso C1
WHERE NOT EXISTS ( SELECT *
FROM Curso C2
WHERE C2 . Aula = c1 . Aula
AND C2 . Pid = P . Pid ) ) ;
Pgina 46 de 74
20.2
Delete
20.2.
Delete
Sintaxis para el borrado de tuplas de la relacin r para las cuales P es verdadera:

1
2
DELETE FROM r
WHERE P
Slo se borra de una relacin.

Slo se borran tuplas (no atributos de tuplas).
Primero se buscan todas las tuplas que satisfacen P , y luego se borran todas ellas.
20.3.
Insert
Sintaxis para la insercin de tuplas en la relacin r:

1
2
1
2
INSERT INTO r ( nombreAtributo1 , ... , nombreAtributoN )

VALUES ( valor1 , ... , valorN )
INSERT INTO r
SELECT (...)
Primero se buscan todas las tuplas que satisfacen el select, y luego se insertan todas ellas.
20.4.
Update
Sintaxis para la actualizacin de un atributo de una tupla de r:

1
2
3
1
2
3
4
5
6
UPDATE r
SET atributo = valor
WHERE condicion
UPDATE r
SET atributo = CASE
WHEN condicion1 THEN valor1
WHEN condicion2 THEN valor2
ELSE valor3
END
Pgina 47 de 74
Parte IV
Procesamiento de Consultas
Figura 21: Pasos en el procesamiento de consultas
Asumimos que toda la relacin se almacena de forma contigua en disco.

Metadatos que se almacenan para cada base de datos:
1. nr = cantidad de tuplas en la relacin r
2. lr = tamao de una tupla, en bytes
3. br = cantidad de bloques que ocupa la relacin r.
br =
lr n r
tam bloque en bytes
4. fr = factor de bloqueo de la relacin r (es decir, cuantas tuplas caben en un bloque)

nr
fr =
br
5. V (A, r) =cantidad de valores distintos que toma el atributo A en la relacin r

6. M IN (A, r) =mnimo valor que toma el atributo A en la relacin r
7. M AX(A, r) =mximo valor que toma el atributo A en la relacin r
Pgina 48 de 74
21 ndices
Figura 22: Estadsticas que se almacenan de la base de datos
21.
ndices
Ciertas consultas sobre algunos atributos son ms frecuentes que otras. Para acelerar estas consultas, se
utilizan los ndices. Podemos tener ms de un ndice sobre una relacin.
ndice Estructura de datos (usualmente rbol B+) que permiten encontrar rpidamente las tuplas de una
relacin que tengan un valor especifico para un atributo o atributos (el/los que el ndice almacena), con
la desventaja de que cada modificacin a la relacin requiere actualizar el ndice.
Un registro de un ndice tiene un valor de la clave de bsqueda, y punteros a uno o ms tuplas con esa
clave de bsqueda.
1
2
3
4
CREATE [ CLUSTERED ] INDEX estudianteID_indice

ON estudiante {
ID ASC
};
Tipos de ndices:
Segn la clave:
Clusterizado / primario: ndice cuya clave de bsqueda define el orden secuencial del archivo de
la tabla. Slo puede haber uno de estos ndices para cada relacin
Clusterizado / secundario.
El orden fsico de las tuplas no es igual al orden del ndice
Las columnas que se indexan son, tpicamente, atributos no claves
Siempre son densos
Segn la cantidad de registros que tiene:
Denso: tiene un registro para cada valor posible de la clave de bsqueda. Si es clusterizado, tiene
un puntero al primer registro con ese valor. Si es no clusterizado, tiene punteros a todos los registros
con ese valor.
Esparcido: tiene registros para algunos valores de la clave de bsqueda. Solo se pueden usar si el
archivo de datos est ordenado por la clave de bsqueda.
Esparcido = P rimario
Secundario = Denso
Pgina 49 de 74
21.1
Estructuras de ndices
(b) ndice esparcido
(a) ndice denso
Figura 23: ndices densos y esparcidos

ndice compuesto ndice cuya clave de bsqueda est formada por ms de un atributo. Conviene que los
atributos de ms a la izquierda sean ms discriminantes que los de la derecha. Ejemplo: para una relacin
pelicula(nombre, a
no), es esperable que haya ms consultas sobre el nombre que sobre el a
no. Entonces,
un ndice (nombre, a
no) sera mejor que (a
no, nombre).
ndice cubridor Es un ndice que contiene todas las columnas de una consulta, y por ende no se necesita
realizar bsquedas adicionales en el ndice clusterizado.
21.1.
Estructuras de ndices
rbol B+
Tabla de hash
rbol B+
Tabla de hash
22.
Ventajas
Desventajas
Soporta bsquedas por rango

La bsqueda tpica requiere solo
una operacin de I/O
Operaciones ms costosas
No soporta bsquedas por rango.
Formas de realizar consultas
1. Bsqueda lineal sobre toda la relacin

2. Usando ndices
3. Hashing
4. Ordenamiento
Los algoritmos pueden asumir que una relacin entra completamente en memoria, o que son muy grandes.
22.1.
Operadores
Scan
Table scan: se leen todos los bloques de la relacin en disco.
Index scan: se leen todos los bloques de la relacin en disco, utilizando un ndice.
Sort scan: ordena una relacin R sobre un atributo a.
Si hay un ndice sobre a, se lo usa.
Si R entra en memoria, se la trae a memoria con table o index scan, y se la ordena en memoria
Si R no entra en memoria, se la ordena externamente.
Pgina 50 de 74
23 Algoritmos
23.
Algoritmos
23.1.
Seleccin
A=a (r)
Bsqueda lineal sobre r:
Si la relacin es clusterizada: br
Si la relacin no est clusterizada: nr
Bsqueda con ndice sobre los atributos de A:
Si el ndice es clusterizado: costo
Si el ndice no es clusterizado:
23.2.
br
V (A,r)
nr
costo V (A,r)
Junta
R(X, Y ) ./ S(Y, Z), donde R es la relacin ms pequea. Suponemos que la memoria est formada por M
buffers.
Iteracin ingenua (tuple based nested-loop join):
costo ns nr
1
2
3
4
para cada tupla s en S :

para cada tupla r en R :
si ( s join r = t ) :
devolver t
Iteracin por bloques (block based nested-loop join):

Costo br +
br
m1 )
br
m1
bs (R se lee una vez, S se lee por cada pedazo de R, cada pedazo es de tamao
Conviene que la relacin del ciclo externo sea la ms pequea

1
2
3
4
5
6
7
desde i =1 hasta i =( bR / m -1) :

leer R en memoria ( ocupar M -1 buffers )
para cada bloque bs en S :
leer bs en memoria ( ocupar 1 buffer )
para cada tupla t en bs :
buscar las tuplas de R en que hacen join con t
devolver t
Indexed nested-loop join: suponer que se tiene un ndice sobre S del atributo Y .
Si el ndice es clusterizado: costo br +
Si el ndice no es clusterizado: costo
nr b s
V (Y,S)
r ns
br + Vn(Y,S)
Este mtodo es eficiente cuando S no est almacenada en forma contigua en disco.

1
2
3
4
5
para cada bloque br de R :

para cada tupla t de br :
buscar con el indice las tuplas de S que hacen join con t
para cada tupla s join t :
agregar <s ,t > al resultado
Sort-merge (sort based join):

Costo bs + br + bs log(bs ) + br log(br )
Pgina 51 de 74
23.2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Junta
ordenar R con respecto a Y

ordenar S con respecto a Y
mergear R y S :
encontrar min ( R ) y min ( S )
si min ( R ) > min ( S )
quitar las tuplas de S con Y como atributo
leer S
si min ( R ) < min ( S )
quitar las tuplas de R con Y como atributo
leer R
si min ( R ) == min ( S )
agregar r join s al resultado
leer R
leer S
Mtodo Simple de Junta Hash: utiliza una funcin de hash h. Requiere que la relacin R entre en memoria.
h [0, M 1].
Costo: 2 (br + bs )
1
TH = {} // en memoria
2
3
4
5
6
7
// fase constructiva
para cada bloque de R :
para cada tupla r del bloque :
calcular h ( r [ Y ])
guardar TH [ Y ] = r
8
9
10
11
12
13
// fase exploratoria
para cada bloque de S :
para cada tupla s del bloque :
calcular h ( s [ Y ])
agregar al resultado las tuplas de TH [ Y ] join " s "
Mtodo GRACE:
El mtodo de junta Hash versin GRACE se usa para calcular la junta R ./R.A=S.A S cuando ninguna
de las tablas entran en memoria. Lo que se hace es generar 2 conjuntos de M particiones. Se utilizan dos
funciones de hash: una para generar las particiones h : A [0, M 1], y otra para calcular qu tuplas
hacen join.
En una primera etapa, por cada tupla t de cada bloque de R se aplica la funcin de hashing h(t) para
saber a cul particin enviar la tupla. Se enva cada tupla a esa particin (un archivo) en disco. Al finalizar
la etapa, se tienen M archivos.
En una segunda etapa, se hace lo mismo con S, pero con otros M archivos. La clave est en que si dos
tuplas hacen join, entonces necesariamente deben estar en el mismo nmero de particin.
Finalmente, se leen las i particiones. A cada tupla leda de la particin i de R se le aplica la funcin de
hash h2 para saber dnde guardarla en una tabla de hash en memoria. Luego, se calcula h2 para cada
tupla de la particin i de S. Este valor nos dir la posicin en la tabla de hash donde estn las tuplas de
R que hacen join con dicha tupla. De esta forma se obtienen las tuplas que hacen join, y se las graba en
disco.
Costo: 3 (bs + br )
1
2
3
4
5
6
7
8
// particionamiento de R . Costo : 2* bR
para cada tupla r de R :
num buffer = calcular h1 ( r [ Y ])
guardar " r " en el buffer
si ( buffer completo )
guardarlo en disco Ri
// particionamiento de S . Costo : 2* bS
para cada tupla s de S :
Pgina 52 de 74
24 Evaluacin de expresiones
9
10
11
12
num buffer = calcular h1 ( s [ Y ])

guardar " s " en el buffer
si ( buffer completo )
guardarlo en disco Si
13
14
15
16
17
18
19
20
21
22
23
24.
// metodo simple de hash . Costo : bR + bS

para i desde 0 a M -1:
leer Ri
para cada tupla r en Ri :
calcular h2 ( r [ Y ])
guardar TH [ r [ Y ]] = r
leer Si
para cada tupla s en Si :
calcular h2 ( s [ Y ])
agregar al resultado las tuplas de TH [ r [ Y ]] join " s "
Evaluacin de expresiones
La forma obvia de evaluar una expresin que tiene varias operaciones es evaluar cada operacin en el orden
indicado, materializando en disco cada resultado intermedio como relaciones temporales.
Otra alternativa, ms eficiente, es evaluar las operaciones en simultneo en un pipeline, donde los resultados
de una operacin pasan a la prxima, y se elimina la necesidad de almacenar relaciones temporales. Esto se
puede utilizar para evaluar juntas mltiples: R1 ./ R2 ./ ./ Rk .
Ventajas de pipeline:
1. Elimina el costo de leer y escribir relaciones temporales.
2. Puede empezar a generar resultados inmediatamente.
Uso de pipelining:
Sort: no se puede aplicar. El resultado del sort no se puede mostrar hasta que no se hayan procesado
todas las tuplas.
Join: el mtodo GRACE no se puede aplicar porque requiere leer y particionar todas las tuplas antes
de que pueda producirse un resultado. Sin embargo, el mtodo indexed nested-loop puede aprovechar del
pipelining. Si las relaciones estn ordenadas por los atributos de join, merge join tambin puede aprovechar
del pipelining.
25.
Optimizacin de consultas
Plan de evaluacin conjunto de operaciones de lgebra relacional a ejecutar, junto con las instrucciones para
llevarlas a cabo (por ejemplo, los ndices a usar).
Optimizacin de consultas proceso de seleccionar el mejor plan de evaluacin. El costo de cada plan se evala
teniendo en cuenta informacin estadstica de las relaciones. Lo que se busca minimizar es la cantidad de
transferencias de bloques del disco a la memoria y la cantidad de seeks que se hacen en el disco.
Para ello se tiene en cuenta:
1. Cul de la de las expresiones equivalentes a la consulta es ms eficiente para resolver la misma?
2. Qu algoritmo se utilizar para implementar la operacin?
3. Cmo deberan las operaciones pasarse datos entre s? (Pipeline, buffers de memoria, disco)
1
EXPLAIN consulta
Pgina 53 de 74
25.1
25.1.
Reglas de equivalencia
Reglas de equivalencia
Reglas relacionadas con la seleccin:

1. ab (r) = a (b (r)) = b (a (r))
2. ab (r) = a (r) b (r)
3. a (r s) = a (r) a (s)
4. a (r s) = a (r) s = a (r) a (s)
5. a (r ./ s) = a (r) ./ a (s)
6. Si a solo tiene atributos de S: a (r s) = r a (s)
Reglas relacionadas con la proyeccin:
1. L (R S) = L (R) L (S)
2. L (a (R)) = L (a ((M (R)))) donde M es la lista de atributos que figuran en L o en a
Reglas relacionadas con el join:
1. r1 ./ r2 = r2 ./ r1
2. (r1 ./ r2 ) ./ r3 = r1 ./ (r2 ./ r3 )
25.2.
Heursticas de optimizacin de consultas
1. Ejecutar las selecciones () lo antes posible

2. Ejecutar las proyecciones () lo antes posible
3. El orden de las operaciones de join (./) es importante
4. Evitar cuando sea posible los productos cartesianos ()
26.
Estimacin de tamao de consultas
A continuacin se describe la estimacin de cantidad de tuplas para cada tipo de consulta.

Se utiliza el concepto de selectividad de una condicin A como la probabilidad de que una tupla satisfaga
una condicin A. Sea si = V (i , r) la cantidad de tuplas que satisfacen la condicin i . La probabilidad de
satisfacer i es nsir .
Seleccin
A=a (r)
Si A distribuye uniformemente:
nr
V (A,r)
Si se dispone de un histograma para A, y a rango:
f reqrango (A,r)
cantrangos
Av (r) con v conocido

Si A distribuye uniformemente y v < mn(A, r): 0
Si A distribuye uniformemente y v max(A, r): nr
En cualquier otro caso: nr
vmin(A,r)
max(A,r)min(A,r)
abz (r) donde hay x selectores: nr P (a) P (z) = nr
sa sb sz
(nr )x
abz (r) donde hay x selectores independientes entre s:

sa
sz
nr [P (a) + + P (z)] = nr 1 1
1
nr
nr
a (r): nr V (a, r)
Junta natural3
3 Se
introducen dos simplificaciones:
Pgina 54 de 74
26.1
Clculo de juntas con histogramas
Si R S = : nr ns
Si R S = P KR : nS (porque podra haber nulls)
Si R S = P KS : nR (porque podra haber nulls)
Si R S = F KS : nS
Si R S = F KR : nR
Si #(R S) = 1:
ns nr
m
ax(V (S,RS),V (R,RS))
ns nr
V (S,RS)
ns nr
V (R,RS)
Si #(R S) = 2 y el join es de tipo R.A1 = S.A2 R.B1 = S.B2 :

nr ns
m
ax (V (R, A1 ), V (S, A2 ) max (V (R, B1 ), V (S, B2 ))
Proyeccin: A (r) : V (A, r)
Agregacin A %f (r) : V (A, r)
Unin R S: nr + ns
Interseccin R S : mn (nr , ns ) (cota superior)
Diferencia R S : r (cota superior)
V (A, A op v (r)) : V (A, r) sA op v
V (A, r ./ s) :
Si A R: mn (V (A, r), nr./s )
Si a1 A y a2 A, mn (V (a1 , r) V (a2 a1 , s); V (a1 a2 , r) V (a2 , S); nr./s )
26.1.
Un sistema de bases de datos puede computar un histograma de valores para un atributo dado. Si V (R, A) no
es muy grande, el histograma puede consistir de la cantidad de tuplas que tienen cada posible valor del atributo.
Si V (R, A) es muy grande, entonces podra guardarse solamente los valores ms frecuentes, o agruparlos en
rangos.
Los tipos de histogramas ms frecuentes son:
1. Igual ancho: se escoge un ancho w y una constante v0 . Se almacena la cantidad de tuplas con valores v
en los rangosv0 v < v0 + w, v0 + w v < v0 + 2w, etctera.
2. Valores ms frecuentes: se listan los valores ms frecuentes y la cantidad de tuplas que tienen esos
valores. Tambin se puede proporcionar la cantidad de tuplas que tienen otros valores.
Ejemplo: sea la junta R(A, B) ./ S(B, C). Sabemos que V (R, B) = 14 y que V (S, B) = 13. Tenemos los
histogramas de valores ms frecuentes para R S = B.
R.B
S.B
0
150
100
1
200
80
2
?
70
5
100
?
Otros
550 (11 valores)
250 (10 valores)
Suponemos que cada valor que aparece en la relacin con menos valores de B (en este caso, S) tambin
aparecen en la otra relacin (en este caso, R). Tambin suponemos que la distribucin de los valores dentro de
Otros es uniforme, y estimamos la frecuencia de los datos desconocidos:
R.B
S.B
0
150
100
1
200
80
2
= 50
70
550
11
5
100
250
10 = 25
Otros
550 (10 valores)
250 (9 valores)
1. Si R(X, Y ) y S(Y, Z), y V (R, Y ) V (S, Y ) entonces cada valor de Y en R ser un valor de Y en S.
2. Si A es un atributo de R pero no de S, V (R ./ S, A) = v (R, A)
Pgina 55 de 74
26.1
Entonces, el tamao de la junta es:

T [R ./ S]
T [R ./B=0 S] + T [R ./B=1 S] + T [R ./B=2 S] T [R ./B=5 S] + T [R ./B6=0,1,2,5 S]

550 250
= (150 100) + (200 80) + (50 70) + (100 25) + mn(9, 10)
11
10
= 15,000 + 16,000 + 3,500 + 2,500 + 9 1250
=
48,250
Ejemplo: sean las relaciones Enero(dia, temp) y Julio(dia, temp). Sea la consulta
1
2
3
SELECT Enero . dia , Julio . dia

FROM Enero , Julio
WHERE Enero . temp = Julio . temp
Suponer los siguientes histogramas de igual ancho:

Rango C
-17, -13
-13, -9
-8, -4
-3, 1
2, 6
7, 11
12, 16
17, 21
22, 26
27, 31
Enero
0
0
0
0
5
20
50
100
60
10
Julio
40
60
80
50
10
5
0
0
0
0
Sabemos que si dos bandas tienen T1 y T2 tuplas respectivamente, y la cantidad de valores de la banda es V ,
entonces la estimacin del tamao de la junta es T1VT2 .
En el ejemplo anterior, las nicas bandas que contribuyen al resultado son las de [2,6] y [7,11]. Entonces, el
tamao de la junta es:
T [R ./ S]

T R ./temp[2,6] S + T R ./temp[7,11] S
5 10 20 5
=
+
4
4
= 12, 5 + 25
=
37, 5
Pgina 56 de 74
Parte V
Control de Concurrencia
tem de dato elemento al que accede una transaccin. Puede ser un registro de una base de datos, un bloque
de disco, un campo de un registro, o incluso toda la base de datos. Cada tem tiene un nombre nico que
lo identifica (por ejemplo, la direccin fsica de un bloque de disco).
Modelo de concurrencia intercalada la CPU ejecuta una transaccin a la vez, pero varias transacciones en
un perodo de tiempo.
Figura 24: El manejador de transacciones (a) le emite rdenes al manejador del log, (b) se asegura que transacciones concurrentes no interfieran entre ellas. El scheduler permite o bloquea transacciones
27.
Transacciones
Transaccin unidad lgica de procesamiento. Est formada por una o ms operaciones que acceden a la base
de datos. Tiene un identificador nico de transaccin.
Debe tener las siguientes propiedades ACID:
Atomicity
La transaccin debe ejecutarse en su

totalidad o no debe ejecutarse
Responsabilidad del gestor de

recuperacin, que mantiene un
log donde guarda los valores
viejos sobrescritos por una
transaccin
La transaccin debe llevar a la base de datos

de un estado consistente a otro (i.e. que
Responsabilidad de los
Consistency
respeten las reglas de integridad de la base
programadores
de datos)
La ejecucin de una transaccin no debe
Responsabilidad del gestor de
Isolation
interferir con otras
concurrencia
Los efectos de una transaccin commiteada
Gestor de recuperacin, que
deben persistir en la base de datos. Es decir,
debe garantizar que el log est
Durability
luego de commiteada, no deberamos
en disco antes de que termine la
necesitar ejecutar un rollback
transaccin
How transactions interact with the database. There are three address spaces that interact in important ways:
1. The space of disk blocks holding the database elements.
2. The virtual or main memory address space that is managed by the buffer manager.
3. The local address space of the transaction.
Pgina 57 de 74
28 Problemas de concurrencia
Cada transaccin est formada por una o ms operaciones:

start
leer(X): lee un item de dato de la base de datos a una variable local a la transaccin, que est en memoria
escribir(X): escribe una variable de programa en memoria, en la base de datos
commit: marca el fin exitoso de una transaccin. Los cambios que introdujo son seguros para guardar en
la base de datos.
abort: marca el fin con errores de una transaccin. Los cambios que introdujo se deben revertir.
Estados posibles de una transaccin:
Partially committed : luego de que se ejecut la ltima instruccin pero antes de ejecutar el commit o
abort
Commited : sus efectos fueron almacenados permanentemente en la base de datos
Aborted : se ejecut un roll back de la transaccin y la base de datos se restaur a su estado original
Figura 25: Diagrama de estados de una transaccin

Una transaccin llega al punto de commit cuando todas sus operaciones se ejecutaron correctamente y se
grabaron todos sus registros de operaciones en el log. Luego de este punto, la transaccin est commiteada y
se debe almacenar permanentemente en la base de datos. Esto se marca agregando un registro [commit,T] en
el log.
1. Si ocurre una falla y la transaccin an no grab [commit,T], se debe ejecutar un rollback de esta
transaccin.
2. Si ocurre una falla y la transaccin ya haba grabado [commit,T] en el log, se debe rehacer esta transaccin.
El protocolo WAL (Write-Ahead Logging ) indica que antes de commitear una transaccin se debe guardar
el log en memoria al log en disco.
28.
Problemas de concurrencia
1. The Lost Update Problem: una Escritura que sobrescribe a otra.

2. The Dirty Read Problem: una Lectura de un valor incorrecto.
3. The Incorrect Summary Problem: una Lectura de muchos valores incorrectos.
4. The Unrepeatable Read Problem: dos Lecturas consecutivas que producen resultados distintos, por
haber una transaccin intermedia que cambi el valor.
Pgina 58 de 74
28.1
Atributos de una transaccin
(a) Lost Update
(b) Dirty Read
(c) Incorrect Summary
Figura 26: Probemas de concurrencia
28.1.
Atributos de una transaccin
Modo de acceso: READ ONLY, READ WRITE
Nivel de isolation:
Nivel de
isolation
READ UNCOMMITTED
READ
COMMITTED
REPEATABLE
READ
SERIALIZABLE
Tipo de violacin que se puede producir para dos transacciones T y S

Escritura sucia
(T escribe el valor
X despus de que
una transaccin S
lo escribiera, y S
no comiti ni
abort)
Lectura Sucia (T
lee el valorX
despus de una
transaccin S que
no comiti ni
abort)
Lectura No
Repetible (T lee
el valor X, luego S
lo actualiza, luego
T lee X y es un
nuevo valor)
No
Si
Si
Phantoms (T lee
varios datos que
cumplen una
condicin, luego S
agrega un dato que
tambin lo verifica. Si
T lee de nuevo,
encontrar un nuevo
dato que antes no
estaba)
Si
No
No
Si
Si
No
No
No
Si
No
No
No
No
Cuadro 1: Violaciones que se pueden producir en cada nivel

Pgina 59 de 74
29 Schedules de transacciones
29.
Schedules de transacciones
(a) Schedules equivalentes
(b) Schedule no recuperable
Figura 27: Schedules de Transacciones

Schedule ordenamiento cronolgico de las operaciones de n transacciones. Se pueden intercalar operaciones de
distintas transacciones, pero las operaciones de una transaccin se deben ejecutar en forma secuencial.
Un schedule es recuperable si, para cada par de transacciones Ti y Tj tal que Tj lee un tem de dato
previamente escrito por Ti , el commit de Ti aparece antes del commit de Tj .
Un schedule es sin cascada (avoids cascading rollback , AVR) si, para cada par de transacciones Ti
y Tj tal que Tj lee un tem de dato previamente escrito por Ti , el commit de Ti aparece antes del read de
Tj .
Un schedule que usa locks es estricto si cada transaccin commitea o aborta, y luego libera todos sus
locks exclusivos.
estricto = sin cascada = recuperable
estricto = serializable
Figura 28: Relacin de schedules

Conflicto dos operaciones en un schedule entran en conflicto cuando se cumplen todas las condiciones siguientes:
1. Corresponden a distintas transacciones
2. Acceden al mismo tem de dato X
3. Al menos una de esas operaciones es escribir(X)
Dicho de otra forma, estn en conflicto cuando, si alteramos el orden de ejecucin, cambia el resultado
final de X.
Pgina 60 de 74
30 Protocolos de Control de Concurrencia: Protocolo de Locking
Un schedule es serial cuando ejecuta primero todas las operaciones de T1 , luego todas las operaciones de
T2 , ..., y finalmente todas las operaciones de Tn . Cualquier esquema serial preserva la consistencia de la base de
datos.
Un schedule es serializable cuando es equivalente a algn schedule serial con las mismas transacciones.
Dos schedules son conflicto-equivalentes si el orden de las operaciones en conflicto es la misma en ambos.
Es decir, si podemos transformar uno en el otro mediante una secuencia de swaps de acciones adyacentes que
no estn en conflicto.
Figura 29: Convirtiendo un schedule conflicto-serializable en uno serial mediante swaps de acciones adyacentes.
A cada paso estn subrayadas las acciones a punto de ser swappeadas
Un schedule es conflicto-serializable si es conflicto-equivalente a algn schedule serial.
Conf licto serializable = Serializable
Para verificar si un schedule S es conflicto-serializable se utiliza un grafo dirigido G = (N, E):
N es el conjunto de transacciones {T1 , T2 , . . . , Tn } que forman el schedule
E es el conjunto de aristas de la forma Ti Tj . Cada arista significa que Ti debe preceder a Tj en
cualquier schedule serial equivalente a S
Algoritmo 15 Verificacin de serializabilidad de un schedule
1
2
Entrada : schedule S
Salida : " verdadero " si es conflicto serializable
3
4
5
6
7
8
9
10
11
para cada transaccion Ti en S :

crear un nodo Ti en el grafo de precedencia
para cada caso donde Ti ejecuta READ ( X ) y luego Tj ejecuta WRITE ( X ) :
agregar una arista ( Ti -> Tj ) en el grafo de precedencia
para cada caso donde Ti ejecuta WRITE ( X ) y luego Tj ejecuta READ ( X ) :
para cada caso donde Ti ejecuta WRITE ( X ) y luego Tj ejecuta WRITE ( X ) :
12
13
14
15
16
si el grafo es aciclico :
devolver " verdadero "
si el gafo es ciclico :
devolver " falso "
Si el grafo de precedencia es acclico, el schedule serial equivalente puede construirse utilizando un orden
topolgico de la siguiente forma: siempre que exista una arista Ti Tj , Ti debe preceder a Tj en el schedule
serial.
En la prctica, los DBMS no utilizan este algoritmo para garantizar la serializabilidad (porque habra que
verificarlo para cada schedule).
30.
Protocolos de Control de Concurrencia: Protocolo de Locking
Una forma de garantizar el aislamiento de transacciones y prevenir comportamiento no serializable es mediante el uso de locks. Notar que este mecanismo no funciona bien cuando los locks se mantienen durante das,
Pgina 61 de 74
30.1 Lock
o cuando las decisiones humanas son parte de una transaccin.
30.1.
Lock
Lock variable que se asocia a un tem de dato. Describe el estado del tem con respecto a las posibles operaciones
que pueden aplicarse a el. Generalmente hay un lock por item de dato.
30.1.1.
Tipos de locks
1. Binarios: pueden tener dos valores: locked (1) o unlocked (0). Un lock binario impone la exclusin mutua
en el item de dato asociado, porque solo puede haber a lo sumo una transaccin con un lock para un
mismo dato.
El registro de este tipo de lock tiene la forma <Item de dato, LOCK, Transaccin con lock>
Reglas que deben aplicarse a cada transaccin:
a) lock(X) antes de cualquier leer(X) o escribir(X)
b) unlock(X) despus de todos los leer(X) y escribir(X)
c) no se permite ejecutar lock(X) si ya se tiene un lock de X
d ) no se permite ejecutar unlock(X) si no se tiene el lock de X
2. Compartidos/Exclusivos (Lectura/Escritura): es ms laxo que los locks binarios porque permite que
varias transacciones que solo van a ejecutar leer(X) tengan acceso a X. El lock puede tener dos valores:
read-locked o write-locked.
Lock exclusivo: puede leer y escribir el dato X.
Lock compartido: puede leer pero no puede escribir X.
El registro este tipo de lock tiene la forma <Item de dato, LOCK, # de lecturas, Transaccion(es)
con lock>
Reglas que deben aplicarse a cada transaccin:
a) read_lock(X) o write_lock(X) antes de cualquier leer(X)
b) write_lock(X) antes de cualquier escribir(X)
c) luego de todos los leer(X) y escribir(X), ejecutar unlock(X)
d ) si ya tiene un lock (compartido o exclusivo) de X, no se puede ejecutar ni read_lock(X) ni write_lock(X)
e) no se permite ejecutar unlock(X) si no se tiene un lock de X (compartido o exclusivo)
30.1.2.
Problemas con el uso de locks
1. El uso por s solo de locks no garantiza la serializabilidad de schedules.
Figura 30: El uso de locks no garantiza la serializabilidad. Si se produce una actualizacin a A entre unlock(A)
y lock(B), A + B sera incorrecto
Pgina 62 de 74
30.2
Lock de update
2. Deadlock : ocurre cuando cada transaccin en un schedule est esperando que se libere un lock que fue
adquirido por otra transaccin del schedule.
Para detectar y/o prevenir un deadlock, el gestor de concurrencia puede mantener un grafo de espera.
Cuando una transaccin T est esperando a que la transaccin S libere un lock, se dibuja una arista
T S. Cuando S libera el lock, la arista se borra. El deadlock se detecta cuando el grafo es cclico.
Cuando ocurre un deadlock, el sistema debe ejecutar el rollback de alguna de las dos transacciones, y
liberar los locks que sta posea.
Tambin se pueden arreglar deadlocks especificando un timeout para cada transaccin. Si se ejecutan por
ms tiempo que este timeout, es abortada y sus locks se liberan.
3. Starvation: ocurre cuando una transaccin se queda esperando indefinidamente a que se libere un lock.
Se puede evitar de la siguiente forma: cuando una transaccin Ti solicita un lock sobre X en un modo M ,
el gestor de concurrencia se lo provee si se verifica que:
a) No hay otra transaccin con un lock sobre X en un modo que conflicte con M .
b) No hay otra transaccin esperando obtener un lock sobre X antes que Ti
30.2.
Lock de update
Lock de update un lock de update le da a una transaccin el privilegio para leer X, pero no para escribirlo.
Sin embargo, este tipo de lock se puede actualizar a un lock exclusivo ms tarde.
30.3.
Matriz de compatibilidad de locks
Matriz de compatibilidad de locks se puede otorgar un lock de tipo C si y solo si, para cada fila R tal que
ya se otorg a otra transaccin un lock de tipo R, hay un Si en la columna C.
Se otorg un lock de tipo...
Exclusivo
Compartido
Se solicita un lock de tipo....

Exclusivo
Compartido
No
No
No
Si
(a) Para locks compartidos y exclusivos
Se otorg un lock de tipo...
Exclusivo
Compartido
Actualizacin
Se solicita un lock de tipo....

Exclusivo
Compartido
No
No
No
Si
No
No
Actualizacin
No
Si
No
(b) Para locks compartidos, exclusivos y de actualizacin
Cuadro 2: Ejemplos de matrices de compatibilidad
Pgina 63 de 74
30.4 Lock table
30.4.
Lock table
Lock table tabla que utiliza el gestor de concurrencia para almacenar el estado de los locks activos.
Para cada tem de dato con locks activos, mantiene una lista de transacciones que solicitaron el lock, en
el orden en que llegaron los pedidos. Se registra qu transaccin es y qu modo de lock solicit. Tambin
se registra si el lock le fue concedido.
Figura 31: Lock table
30.5.
Protocolo de dos fases (two-phase locking)
Una transaccin cumple con el protocolo two-phase locking (2PL) si todas las operaciones de lock
(read_lock, write_lock) preceden al primer unlock de la transaccin. Se dice entonces que la transaccin
se divide en dos fases: la creciente (donde se adquieren los locks) y la decreciente (donde se liberan los locks).
Si cada transaccin de un schedule cumple el protocolo 2PL, se garantiza que el schedule es serializable.
De hecho, las transacciones se pueden ordenar de acuerdo a sus lock points (el punto donde termina la fase
creciente).
Este protocolo limita la cantidad de concurrencia que se permite, porque una transaccin no puede liberar
un lock hasta que haya adquirido un lock para todos los dems tems, y entonces puede haber muchas otras
transacciones esperando que se libere el primer lock. Adems, no se previene el deadlock, ni los rollbacks en
cascada.
Figura 32: 2PL

Pgina 64 de 74
30.6
Protocolo de rbol
(a) Schedule 2PL con deadlock
(b) Schedule 2PL con cascading rollback si T5 falla al final

de todo
Figura 33: Schedule 2PL

Para prevenir el problema de deadlock, este protocolo puede ampliarse y exigir que las transacciones adquieran
por adelantado todos los locks que se necesitan; si un lock no se puede conseguir, no se adquiere ninguno. Esto
limita an ms la concurrencia.
Para prevenir el problema de rollbacks en cascada, existe el protocolo 2PL estricto. Este modo, adems de
requerir lo mismo que 2PL, requiere que todos los locks exclusivos adquiridos por una transaccin se mantengan
hasta que la misma ejecute commit.
30.6.
Protocolo de rbol
Protocolo de rbol protocolo especializado para transacciones que acceden a datos en forma de rbol (ejemplo: un ndice B). El protocolo viola 2PL, pero utiliza el hecho de que acceder a elementos debe ser hacia
abajo para garantizar serializabilidad.
Si una transaccin quiere insertar un registro, debera adquirir un lock exclusivo de la raz, ergo de todo el
rbol, y por ende estara bloqueando a todas las dems transacciones.
Puede aprovecharse la estructura de rbol del ndice de la siguiente forma:
Cuando se adquiere un read_lock en un nodo hijo, el lock del nodo padre puede liberarse porque no se
usar ms.
Cuando se adquiere un write_lock en un nodo hoja (para realizar una insercin), se debe adquirir un lock
exclusivo en el nodo hoja.
Utilizar la tcnica de index locking soluciona el problema de registros phantom.
El protocolo de rbol garantiza un orden serial en las transacciones. El orden de precedencia se define as:
si Ti y Tj adquieren un lock sobre X y Ti adquiere el lock primero, entonces Ti Tj .
Algoritmo 16 Protocolo de rbol
1. El primer lock de una transaccin puede hacerse sobre cualquier nodo del rbol.
2. Los locks subsiguientes pueden otorgarse slo si se posee un lock sobre el nodo padre.
3. Se puede ejecutar unlock de un nodo en cualquier momento.
4. No se puede adquirir lock de un nodo 2 veces, incluso cuando se tiene un lock sobre el nodo padre.
Pgina 65 de 74
Parte VI
Tcnicas de Recuperacin
31.
Necesidad de Recuperacin
Tipos de fallas que pueden ocurrir:

1. Fallas de la computadora: por ejemplo, una desconexin en la red
2. Fallas de transacciones: por ejemplo, una transaccin que intenta dividir por cero
3. Errores locales: por ejemplo, una transaccin que no encuentra datos
4. Aplicacin de procedimientos de control de concurrencia: por ejemplo, una transaccin abortada porque
viola la serializabilidad o para resolver un estado de deadlock
5. Fallas del disco
6. Catstrofes
Los algoritmos de recuperacin tienen dos partes:
1. Acciones que se toman durante el procesamiento normal de transacciones, para asegurar que, en caso de
falla, se dispone de suficiente informacin para recuperar
2. Acciones que se toman despus de una falla para devolver la base de datos a un estado consistente.
Idealmente, la base de datos en disco debera contener, para cada tem de dato, el ltimo valor escrito por
una transaccin que ejecut commit.
En la prctica, la base de datos podra:
Contener valores escritos por transacciones no commiteadas
No contener valores escritos por transacciones commiteadas
32.
Archivo de Log
La base de datos se almacena en disco. ste est formado por bloques. Como todos los bloques no caben en
memoria principal, se necesita una forma de trabajar con la base de datos en memoria. Por ende, se necesita
una forma de organizar los bloques en memoria y luego copiarlos en el disco (flush).
Figura 34: Operaciones sobre bloques

Para alcanzar el objetivo de transacciones atmicas, primero se debe guardar en disco informacin sobre las
modificaciones, sin modificar la base de datos en s. Para eso se utiliza un archivo de log. Este archivo permite:
Pgina 66 de 74
32.1
Checkpoints
Deshacer (undo) cambios hechos por transacciones que deben ser abortadas
Rehacer (redo) cambios hechos por transacciones que ejecutaron commit pero cuyos cambios no fueron
almacenados en la base de datos en disco.
Log archivo secuencial al que solo se le pueden agregar registros.
Decimos que una transaccin ejecut commit cuando su registro [commit,T] fue almacenado en disco. Si
hay una falla luego de esto, se ejecuta un redo. Si hay una falla antes de esto, se hace undo.
Redo debe hacerse en el orden en el que los cambios fueron hechos originalmente.
Undo escribe registros especiales llamados redo-only, que no tienen el valor viejo del item de dato. Al
finalizar las escrituras, se escribe un registro <abort,T> para indicar que el undo finaliz.
32.1.
Checkpoints
Cuando se produce una cada del sistema, hay que consultar el log para determinar aquellas transacciones que
deben rehacerse o deshacerse. En principio, habra que buscar en todo el log para determinar esta informacin.
Hay dos grandes dificultades con este enfoque:
1. El proceso de bsqueda lleva mucho tiempo.
2. La mayor parte de las transacciones ya han escrito sus actualizaciones en la base de datos.
Para reducir este tipo de gastos generales, se usan los checkpoints. La periodicidad con que se ejecutan
checkpoints la decide el administrador de base de datos.
32.1.1.
Checkpoints bloqueantes
Se describe a continuacin un esquema de control simple que (a) no permite realizar ningn cambio mientras
la operacin est en curso, y (b) se escriben en disco todos los buffers en memoria modificados.
Algoritmo 17 Checkpoint bloqueante en un log UNDO
1. Stop accepting new transactions.
2. Wait until all currently active transactions commit or abort and have written a COMMIT or ABORT record on
the log.
3. Flush the log to disk.
4. Write a log record <CHECKPOINT>, and flush the log again.
5. Resume accepting transactions.
32.1.2.
Checkpoints no bloqueantes
Algoritmo 18 Checkpoint no bloqueante en un log UNDO

1. Write a log record <START CHECKPOINT (T1, ... , Tk)>. Here, T1 , . . . , Tk are the identifiers for all the
active transactions (i.e., transactions that have not yet committed and written their changes to disk).
2. Flush the log.
3. Wait until all of T1 , . . . , Tk commit or abort, but do not prohibit other transactions from starting.
4. When all of T1 , . . . , Tk have completed, write a log record <END CHECKPOINT>.
5. Flush the log.
Algoritmo 19 Checkpoint no bloqueante en un log REDO
active transactions (i.e., transactions that have not yet committed).
2. Flush the log.
3. Write to disk all database elements that were written to buffers but not yet to disk by transactions that had
already committed when the <START CHECKPOINT>record was written to the log.
4. Write a log record <END CHECKPOINT>.
5. Flush the log.
Pgina 67 de 74
33 Protocolos de Recuperacin
Algoritmo 20 Checkpoint no bloqueante en un log UNDO/REDO

active transactions (i.e., transactions that have not yet committed).
2. Flush the log.
3. Write to disk all buffers that are dirty (not just those written by committed transactions).
4. Write a log record <END CHECKPOINT>.
5. Flush the log.
33.
Protocolos de Recuperacin
Para fallas de tipo 5 y 6, se necesita haber grabado con anterioridad un backup de la base de datos y
reconstruir la misma con el archivo de log hasta el momento de la falla.
Para fallas de tipo 1 a 4, existen dos tcnicas de recuperacin:
Deferred update
Immediate update
33.1.
Deferred update
Las transacciones y el manejador de buffers obedecen 1 regla:

Write-Ahead Logging (WAL): se deben grabar en disco todos los registros de log sobre las actualizacin
(incluyendo <UPDATE T,X,Nuevo_valor> y <COMMIT T>), y luego actualizar X en disco.
Tipos de registros
<START T>
<COMMIT T>
<ABORT T>
<UPDATE T,X,Valor_Nuevo>
Algoritmo 21 Procedimiento de recuperacin REDO sin checkpoints

1
2
t r a n s a c c i o n e s _ c o m mi t e a d a s = identificarlas
t r a n s a c c i o n e s _ i n c om p l e t a s = identificarlas
3
4
5
6
7
8
9
desde el comienzo del log hasta el fin :

si hay un registro < UPDATE <T ,X , Valor_Nuevo >:
si T esta en transacciones_commiteadas :
escribir Valor_Nuevo en X
si no :
no hacer nada
10
11
12
para cada T en transacciones_incompletas :

escribir < ABORT T >
13
14
flush_log ()
Pgina 68 de 74
33.2 Immediate update
Algoritmo 22 Procedimiento de recuperacin REDO con checkpoints no bloqueantes

1
2
t r a n s a c c i o n e s _ c o m mi t e a d a s = identificarlas
t r a n s a c c i o n e s _ i n c om p l e t a s = identificarlas
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
desde el comienzo del log hasta el fin :

si hay un registro < UPDATE <T ,X , Valor_Nuevo >:
si T esta en " t r a n sa c c i o n e s _ c o mm i t e a d a s ":
escribir " Valor_Nuevo " en X
si no :
no hacer nada
si el ultimo registro de checkpoint es < END CHECKPOINT >:
// se debe mirar el log hasta el < START Ti > que se ejecuto primero
si el ultimo registro de checkpoint es < START CHECKPOINT T1 ,... , TK >:
// la caida se produjo durante el checkpointing
// buscar el registro < END CHECKPOINT > anterior y su par < START CHECKPOINT
S1 ,... , SK >
// rehacer todas las transacciones commiteadas que empezaron despues de ese
START
// o son Si
// ( si no hay , rehacer desde el principio del log )
18
19
20
para cada T en t r a ns a c c i o n e s _ i nc o m p l e t a s :
21
22
flush_log ()
El algoritmo anterior puede ser ms eficiente si se ejecuta, para cada item de dato, slo el ltimo REDO
existente (porque todos los anteriores seran sobrescritos por ste).
Este mecanismo garantiza
Que no se deban hacer rollbacks de transacciones (porque las mismas slo escriben en la base de datos
luego de ejecutar commit)
Que no se deban hacer rollbacks en cascada (porque los tems tienen locks que no permiten leerlos antes
de que una transaccin que los escribi no ejecute commit)
33.2.
Immediate update
Immediate update tiene a su vez tiene dos variantes:

1. UNDO/REDO
2. UNDO
33.2.1.
UNDO/REDO
Las transacciones y el manejador de buffer obedecen 1 regla:

Si la transaccin T modifica el tem de dato X, el registro de log <UPDATE T,X,Valor_Viejo,Valor_Nuevo>
debe ser escrito al disco antes que el tem X sea escrito al disco.
Tipos de registros
<START T>
<COMMIT T>
<ABORT T>
<UPDATE T,X,Valor_Viejo,Valor_Nuevo>
Pgina 69 de 74
Algoritmo 23 Procedimiento de recuperacin UNDO/REDO

1
2
3
mantener dos listas de transacciones :

1) transacciones commiteadas desde el ultimo checkpoint
2) transacciones activas
4
5
6
ejecutar REDO de todos los ESCRIBIR de las transacciones de la primera lista ,

en el orden en que fueron escritos en el log
7
8
9
ejecutar UNDO de todos los ESCRIBIR de las transacciones de la segunda lista ,

en el orden inverso en que fueron escritos en el log
33.2.2.
UNDO
Las transacciones y el manejador de buffer obedecen 2 reglas:

1. Si la transaccin T modifica el tem de dato X, el registro de log <UPDATE T,X,Valor_Viejo> debe ser
escrito al disco antes que el tem X sea escrito al disco.
2. Force Log at Commi t (FLC): si la transaccin ejecuta commit, los tems de datos actualizados por la
transaccin se deben escribir en el disco, y luego el registro de log <COMMIT T> debe ser escrito al disco.
Tipos de registros
<START T>
<COMMIT T>
<ABORT T>
<UPDATE T,X,Valor_Viejo>
Algoritmo 24 Procedimiento de recuperacin UNDO con checkpoints bloqueantes

1
2
t r a n s a c c io ne s _c om pl e ta s = {}
t r a n s a c c i o n e s _ i n c om p l e t a s = {}
3
4
5
6
7
8
9
10
11
12
desde el fin del log hasta el comienzo : // o hasta que se encuentre un registro
< CHECKPOINT >
si hay un registro < COMMIT T > o < ABORT T >:
t r a ns a cc io ne s _c om pl e ta s += T
si hay un registro < UPDATE <T ,X , Valor_Viejo >:
si T esta en " tr an sa c ci on es _ co mp le t as ":
no hacer nada
sino :
t r a n s a cc i o n e s _ i n c om p l e t a s += T
escribir " Valor_Viejo " en " X "
13
14
15
para cada T en " t r a ns a c c i o n e s _ i nc o m p l e t a s ":

16
17
flush_log ()
Pgina 70 de 74
Algoritmo 25 Procedimiento de recuperacin UNDO con checkpoints no bloqueantes

1
2
t r a n s a c c i o n e s_ c om pl e ta s = {}
t r a n s a c c i o n e s _ i n c om p l e t a s = {}
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
desde el fin del log :

si hay un registro < COMMIT T > o < ABORT T >:
t r a n s a c c io ne s_ c om pl e ta s += T
si hay un registro < UPDATE <T ,X , Valor_Viejo >:
si T esta en " tr an sa c ci on e s_ co mp l et as ":
no hacer nada
sino :
t r a n s a c c i o n e s _ i n c om p l e t a s += T
escribir " Valor_Viejo " en " X "
si hay un registro < END CHECKPOINT >:
// se debe mirar el log hasta el < START CHECKPOINT > correspondiente
si hay un registro < START CHECKPOINT T1 ,... , TK > pero no un < END CHECKPOINT >:
// la caida se produjo durante el checkpointing
// se debe mirar el log hasta el comienzo de la primera transaccion incompleta
18
19
20
para cada T en " t r a ns a c c i o n e s _ in c o m p l e t a s ":

21
22
flush_log ()
Es necesario que las operaciones de UNDO y REDO sean idempotentes: ejecutarlas muchas veces debe
ser igual a ejecutarlas muchas veces. De hecho, todo el proceso de recuperacin debe ser idempotente para
garantizar que si existe una falla durante la recuperacin de una falla, la misma se pueda recuperar tambin.
Es necesario que el DBMS mantenga:
Lista de transacciones activas
Lista de transacciones que ejecutaron commit
Lista de transacciones abortadas desde el ltimo checkpoint
(b) Log REDO
(a) Log UNDO
(c) Log UNDO/REDO
Figura 35: Ejemplos de logs

Pgina 71 de 74
UNDO
Logs X = Bd X = Commit al log
Immediate update
REDO
Logs X & Commit al log = Bd X
Deferred update
UNDO/REDO
Log X = Bd X
Immediate update
Pgina 72 de 74
COLABORADORES
Colaboradores
Quienes se mencionan a continuacin han colaborado y aportado tanto al proyecto FIUBA Apuntes como
en este apunte, redactndolo, corrigindolo, agregando grficos, etc.
Mara Ins Parnisari (maineparnisari@gmail.com)
Ezequiel Prez Dittler
Quers colaborar en el proyecto? Conoc ms sobre el proyecto en fiuba-apuntes.github.io.
Pgina 73 de 74
HISTORIAL DE CAMBIOS
Historial de cambios
08/03/2015 Versin inicial
Pgina 74 de 74

Resumen - Base de Datos

Cargado por

Información del documentohacer clic para expandir la información del documento

Copyright:

Formatos disponibles

Resumen - Base de Datos

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Resumen - Base de Datos

Cargado por

Copyright:

Formatos disponibles

Base de Datos (75.15 - 95.

Esta obra est bajo una Licencia Creative Commons

ltima actualizacin: 08/03/2015

Usted es libre para:

Bajo los siguientes trminos:

Introduccin a las Bases de Datos

3. Modelo Entidad-Interrelacin (E-R)

Diseo de bases de datos

Base de Datos (75.15 - 95.05) - Resumen

11.Descomposicin de una relacin

13.Forma normal Boyce-Codd (FNBC)

14.Tercera forma normal (3FN)

16.Cuarta forma normal (4FN)

30.Protocolos de Control de Concurrencia: Protocolo de Locking

Base de Datos (75.15 - 95.05) - Resumen

ACERCA DEL PROYECTO

Acerca del proyecto

Por qu usamos LaTeX?

Por qu usamos Git?

Base de Datos (75.15 - 95.05) - Resumen

Introduccin a las Bases de Datos

Figura 1: Datos, informacin y conocimiento

Sistema de Base de Datos est formado por cuatro componentes:

Base de Datos (75.15 - 95.05) - Resumen

Consultan la base de datos

Crean programas para acceder a

Interfaz que utiliza

(a) Los datos se almacenan en una base de datos, que

Base de Datos (BD) conjunto de datos interrelacionados.

Figura 3: Base de datos

Por qu una base de datos y no un sistema de archivo?

Desventajas de usar un sistema de archivo:

Base de Datos (75.15 - 95.05) - Resumen

Diseo de una base de datos

Diseo de una base de datos

Figura 4: Metodologa de diseo de una base de datos

Modelos de bases de datos

Operaciones en una base de datos

Tipos de restricciones sobre una base de datos:

Modelos de bases de datos

1. Entidad-Interrelacin: para el diseo conceptual

Base de Datos (75.15 - 95.05) - Resumen

3 Modelo Entidad-Interrelacin (E-R)

Modelo Entidad-Interrelacin (E-R)

Interrelacin asociacin entre dos o ms conjuntos de entidades.

Figura 5: Tenencia es una interrelacin entre dos entidades

Figura 6: Grado de una interrelacin

Base de Datos (75.15 - 95.05) - Resumen

Se dice que la participacin de un conjunto de entidades E en un conjunto de interrelaciones R es total

Restricciones de cardinalidad de correspondencia

Base de Datos (75.15 - 95.05) - Resumen

Figura 10: Las fbricas le compran insumos a proveedores.

Restricciones de dependencia existencial

Si la existencia de la entidad S depende de la existencia de la entidad D, entonces se dice que S tiene

Base de Datos (75.15 - 95.05) - Resumen

Figura 14: Simbologa en los diagramas E-R

1. Conjuntos de entidades vs. Atributos?

Reduccin de un esquema E-R a un modelo relacional