1
1. Lógica y Bases de Datos: introducción
La idea básica que subyace al uso de la lógica para el estudio de los sistemas de bases de datos es una idea común a todos los campos de la computación lógica: “la semántica por teoría de modelos de la lógica proporciona una base para la representación del conocimiento, y la semántica por teoría de la demostración proporciona una base para la computación” [J.W. Lloyd, en Computational Logic, 1990].
2
1. Lógica y Bases de Datos: introducción
La lógica de primer orden ha sido utilizada en el desarrollo del modelo relacional de datos desde su aparición en 1970.
Problemas:
formalización
definición de lenguajes de consulta
estudio del concepto de independencia del dominio
actualización de vistas
– comprobación y restauración de la integridad.
– optimización de consultas
– diseño de bases de datos
3
Modelo Relacional de Datos
Estructuras de datos
Tupla
Relación
Operadores
(lenguajes)
Álgebra Relacional
Cálculo Relacional de Tuplas/Dominios
SQL
Restricciones
Definición de relaciones
Restricciones generales
(estáticas)
1. Lógica y Bases de Datos: introducción
4
tupla º registro
· esquema de tupla: t = {(A1, D1), (A2, D2), …, (An, Dn)}
tupla t de esquema {(A1, D1), (A2, D2), …, (An, Dn)}:
t = {(A1, v1), (A2, v2), …, (An, vn)}: ?i ( vi ? Di)
1. Lógica y Bases de Datos: introducción
Estructuras de datos
Tupla
Relación
5
Relación: conjunto de tuplas del mismo esquema al que se denomina esquema de la relación.
Definición de una relación R: R (A1: D1, A2: D2 , …, An: Dn )
Extensión de R: { { (A1, v1), (A2, v2), …, (An, vn)}: ?i ( vi ? Di ) }
R
representación tabular de la extensión de la relación
A1
A2
A3
…
An
R
representación del esquema de una relación
1. Lógica y Bases de Datos: introducción
Estructuras de datos
Tupla
Relación
6
1. Lógica y Bases de Datos: introducción
Restricciones de Integridad
Valor No Nulo (NOT NULL)
Unicidad (UNIQUE)
Clave Primaria (PRIMARY KEY)
Clave Ajena (FOREING KEY)
CHECK
CREATE ASSERTION
7
1. Lógica y Bases de Datos: introducción
Lenguajes
Álgebra Relacional
Cálculo Relacional de Dominios
Cálculo Relacional de Tuplas
SQL (estándar)
Operadores del Álgebra Relacional:
insertar una tupla en una relación
borrar una tupla de una relación
seleccionar tuplas de una relación que cumplen una condición
proyectar los valores de las tuplas de una relación sobre un conjunto de atributos.
concatenar relaciones (join)
unión, intersección, diferencia, ……
actualización
consulta
8
1. Lógica y Bases de Datos: introducción
Consulta: “Nombre de los ríos que sólo pasan por una provincia”
( ( Pasa_por [rcod]
–
( (Pasa_por P1 ? Pasa_por P2 )
DONDE P1.rcod = P2.rcod AND P1.pcod ? P2.pcod) [rcod] )
Río) [nombre]
producto cartesiano
selección
proyección
concatenación
diferencia
Lenguaje de tipo algebraico
9
1. Lógica y Bases de Datos: introducción
Lenguajes
Álgebra Relacional
Cálculo Relacional de Dominios
Cálculo Relacional de Tuplas
SQL (estándar)
INSERT (insertar tupals)
DELETE (borrar tuplas)
actualización
consulta
SELECT
SQL
10
1. Lógica y Bases de Datos: introducción
Consulta: “Nombre de los ríos que sólo pasan por una provincia”
SELECT nombre FROM Río R
WHERE EXISTS (SELECT * FROM Pasa_por P1 WHERE P1.rcod = R.rcod
AND
NOT EXISTS (SELECT * FROM Pasa_por P2 WHERE P2.rcod = R.rcod
AND
P1.pcod <> P2.pcod ) ) )
Lenguaje de tipo lógico
11
1. Lógica y Bases de Datos: introducción
Relación: conjunto de tuplas del mismo esquema.
Definición de una relación R: R (A1: D1, A2: D2 , …, An: Dn )
Extensión de R: { { (A1, v1), (A2, v2), …, (An, vn): ?i ( vi ? Di )} }
El Álgebra Relacional es un conjunto de operadores definidos para la estructura de datos relación (conjunto de tuplas).
El CRT, CRD y SQL son lenguajes lógicos definidos sobre ???
Aproximación algebraica
Aproximación lógica
12
1. Lógica y Bases de Datos: introducción
Formalización lógica de una base de datos relacional:
Interpretación de un lenguaje de 1er orden (Teoría de Modelos)
Teoría de un lenguaje de 1er orden (Teoría de la Demostración)
13
1. Lógica y Bases de Datos: introducción
Dominios:
dom_P= { A, B, C }
dom_A = { a, b, c, d }
dom_C = { CS100, CS200, P100, P200 }
Enseña (cod_prof: dom_P, cod_curso: dom_C)
CP: {cod_prof, cod_curso}
CAj: {cod_prof} ? Profesor
CAj: {cod_curso} ? Curso
Matriculado (cod_alum: dom_A, cod_curso: dom_C)
CP: {cod_alum, cod_curso}
CAj: {cod_alum} ? Alumno
CAj: {cod_curso} ? Curso
Restricciones:
"Todo curso es impartido por algún profesor"
Relaciones:
Profesor (cod_prof: dom_P)
CP: {cod_prof}
Alumno (cod_alum: dom_A)
CP: {cod_alum}
Curso (cod_curso: dom_C)
CP: {cod_curso}
Esquema S:
14
1. Lógica y Bases de Datos: introducción
Ext(Profesor)
Ext(Alumno)
Ext(Curso)
Ext(Matriculado)
Ext(Enseña)
Base de Datos: Ext (S)
15
Esquema S: (L, RI)
Constantes C
Un conjunto de símbolos biyectivo con la unión de los dominios de definición de las relaciones del esquema:
C = {ci: ci?di, di ? ?i (Di), Di es un dominio de S }
Predicados P
Nombres de relación del esquema:
P = { Rn: R (A1: D1, A2: D2 , …, An: Dn) ? S } ? {=}
Lenguaje L
Restricciones de Integridad (RI)
Fórmulas bien formadas (f.b.f) de L
RI
1. Lógica y Bases de Datos: introducción
Formalización lógica de una base de datos relacional: interpretación de un lenguaje de 1er orden.
16
Interpretación I de L : (D, K, E)
Dominio D
Unión de los dominios de definición de las relaciones del esquema:
D = {di : di ? ?i (Di), Di es un dominio de S}
Asignación
(K, E)
K : C ? D / K = { (c, d): c ? C, d ? D, c ? d}
E : P ? ?i:1..n ( 2Di ) / E(pk) ? (2Dk), E(pk) = Ext(p)
(pk es un predicado de aridad k)
E(=) = { (d, d): d ? D }
Interpretación
1. Lógica y Bases de Datos: introducción
Formalización lógica de una base de datos relacional: interpretación de un lenguaje de 1er orden.
Página siguiente |