Lógica y Bases de Datos
1. Lógica y Bases de Datos: introducción.
2. Bases de datos deductivas: definición y formalización.
3. Actualización de vistas.
3.1. Introducción al problema
3.2. Estudio avanzado del problema
4. Comprobación de restricciones de integridad en esquemas con vistas
4.1 Introducción al problema
4.2 Estudio avanzado del problema
5. SGBD deductivos.
5.1. Evaluación de consultas
5.2. SQL3
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].
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
La lógica de primer orden ya había sido utilizada en el desarrollo del modelo relacional de datos [Dat93], [Ull80] desde su aparición en 1970 [Cod70]. Los problemas más relevantes que la lógica ha ayudado a estudiar y algunos de los primeros trabajos en este área se exponen a continuación:
- formalización [NG78], [Kow78], [Kow81], [GMN84a], [Rei84]: un estado de una base de datos relacional puede formalizarse en lógica de primer orden como una interpretación de un lenguaje de primer orden o como una teoría de primer orden.
- definición de lenguajes de interrogación [Cod72]: cálculo relacional de tuplas y cálculo relacional de dominios.
- definición del concepto de independencia del dominio y caracterización de clases de fórmulas que cumplan dicha propiedad: fórmulas de rango separable [Cod72], fórmulas de rango restringido [Nic82], fórmulas seguras [Ull80], ...
- formulación y evaluación simplificada de restricciones de integridad: [Nic79], [Nic82], [NY78].
- optimización de consultas: uso de criterios de simplificación sintácticos [ChM76], uso de información estadística [Dem80], uso de criterios de simplificación semánticos [Kin81].
- diseño de bases de datos: especificación formal [VCF81], [BW81], definición y análisis de dependencias funcionales [Fag82].
La idea básica que subyace en el 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 puede pro
1. Lógica y Bases de Datos: introducción
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
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) Estructuras de datos Tupla
Relación
1. Lógica y Bases de Datos: introducción
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 Estructuras de datos Tupla
Relación
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
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
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
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
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
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)
Ext(Profesor) Ext(Alumno) Ext(Curso) Ext(Matriculado) Ext(Enseña) Base de Datos: Ext (S)
1. Lógica y Bases de Datos: introducción
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: cidi, 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 Formalización lógica de una base de datos relacional: interpretación de un lenguaje de 1er orden.
Sea D la unión de todos los dominios que aparecen en el esquema de la base de datos entonces, los símbolos de constantes y de predicados del lenguaje son los siguientes:
• Constantes: por cada elemento de D, se introduce un símbolo de constante y nada más que uno. Para simplificar, se escogen como símbolos de constantes los símbolos que denotan a los elementos de D.
• Predicados: por cada esquema de relación n-aria,, en el esquema de la base de datos, se introduce un símbolo de predicado n-ario. Para simplificar, se escogerán como símbolos de predicado los nombres de las relaciones. Por razones que se justificarán posteriormente, se incluye el predicado =, que se interpretará como la igualdad.
En este alfabeto, por simplicidad, no se incluyen los símbolos de función. Los símbolos de variables, las conectivas lógicas, los símbolos especiales y los cuantificadores son los propios de un lenguaje de primer orden. Las fbfs de este lenguaje se construyen de la forma usual.
1. Lógica y Bases de Datos: introducción
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 Formalización lógica de una base de datos relacional: interpretación de un lenguaje de 1er orden.
En la interpretación, a cada predicado se le asigna su extensión en la base de datos. Si no está en la extensión de p, entonces p(d1, d2, …, dn) es falso.
Es decir, en una interpretación se dice, implícitamente, para cualquier predicado n-ario p y para cualquier n-tupla de valores si p(d1, d2, …, dn) es cierto o falso. La evaluación de p(d1, d2, …, dn) se hace por simple observación en la base de datos, si está en la extensión de p, entonces la fórmula es cierta en caso contrario es falsa. La información negativa (qué no es cierto) no se tiene por extensión, se deriva usando la hipótesis del mundo cerrado: si A D entonces A es cierto.
Las reglas de evaluación de una fórmula de L en I son comunes a todos los lenguajes de 1er orden.
Estas reglas de evaluación permiten asociar a toda fórmula cerrada de L un valor de verdad (cierto, falso) en la interpretación.
1. Lógica y Bases de Datos: introducción
En la definición del lenguaje L, hemos convertido cada relación n-aria del esquema S en un predicado n-ario, definiendo un orden en el conjunto de atributos del esquema de la relación. De esta forma el concepto de relación coincide con el concepto de relación matemática (subconjunto del producto cartesiano de los dominios): se pierde el concepto de atributo de una relación. Predicados P Nombres de relación del esquema:
P = { Rn: R (A1: D1, A2 : D2 , ..., An : Dn) S } {=}
Con esta simplificación se pierde el concepto de atributo. Las tuplas pasan a ser listas de valores y la referencia a un atributo es por posición no por el nombre de atributo.
Esta simplificación no quita generalidad al estudio teórico de las bases de datos.
1. Lógica y Bases de Datos: introducción
En la definición de la interpretación I de L, hemos definido el dominio como la unión de los dominios de definición de las relaciones del esquema. De esta forma se pierde el concepto de dominio de un atributo (lógica homogénea). Esta simplificación no quita generalidad a la formalización, ya que podría trabajarse en una lógica con tipos (lógica heterogénea). Asignación
(K, E) 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 }
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}
Con esta simplificación se pierde el concepto de atributo. Las tuplas pasan a ser listas de valores y la referencia a un atributo es por posición no por el nombre de atributo.
Esta simplificación no quita generalidad al estudio teórico de las bases de datos.
Comments