informatica




CÁLCULO RELACIONAL
INTRODUCCIÓN
El cálculo relacional (CR), herramienta formal utilizada como lenguaje de consulta a bases de datos relacionales (BDR). Frente al álgebra relacional (AR) que provee de una colección de operadores que actúan sobre relaciones para obtener otras relaciones, el CR formula la relación resultante en términos de las relaciones originales. Es decir, mientras el ARes procedural (se indica un procedimiento para resolver el problema), el CR es descriptivo (se indica cuál es el problema y no cómo resolverlo).
El CR está basado en una rama de la lógica matemática, llamada Lógica de Predicados, ó
Cálculo de predicados de primer orden. Es por ello, que al principio haremos una breve exposición de los fundamentos de dicha lógica de predicados.
La primerapropuesta de usar la lógica de predicados (LP) en bases de datos relacionales la hizo Codd en [CODD72].
Según el tipo de variables que se manejan, existen dos tipos de CR. El cálculo relacional de tuplas (CRT) emplea variables-tupla, que designan a tuplas de relaciones. En el cálculo relacional de dominios (CRD) se utilizan variables-dominio, que toman valores de los dominios asociados a losatributos de las relaciones. Estudiaremos ambos tipos de lenguajes y los compararemos entre sí, y con el AR.
Por último, presentaremos dos lenguajes comerciales fundamentados en dichos tipos de CR, el lenguaje SQL que utiliza aspectos del CRT (Aunque está basado principalmente en el AR), y el lenguaje QBE basado en el CRD.
Lógica de Predicados de Primer Orden
En este primer apartado vamos arepasar los conceptos fundamentales de la lógica de predicados de primer orden. Fundamentalmente nos centraremos en los aspectos sintácticos concernientes con las fórmulas bien formadas (expresiones correctas) del lenguaje. También se comentarán más brevemente los aspectos semánticos, referidos al significado de dichas fórmulas y de los símbolos que las forman. Introduciremos los conceptos deinterpretación, evaluación y modelo.





Símbolos del Lenguaje
Los símbolos básicos del lenguaje son:
- símbolos de puntuación: paréntesis "(", ")" y coma ",".
- símbolos de variables: se representan mediante letras minúsculas del final del alfabeto: r, s,
t, u, v, w, x, y, z.
- símbolos de constantes: se representan mediante letras minúsculas del principio del alfabeto:
a, b, c, d, e.- símbolos de funciones: también se representan con letras minúsculas, pero del centro del
alfabeto: f, g, h, i ..
- símbolos de predicados: se representan mediante letras mayúsculas.
- operadores lógicos: ¬ (negación), → (implicación), ∧ (conjunción) y ∨ (disyunción).
- cuantificadores: ∀ (cuantificador universal) y ∃ (cuantificador existencial).
La jerarquía en la precedencia de losoperadores y cuantificadores es (de mayor a menor):
1) ¬, ∀, ∃ 2) ∨ 3) ∧ 4) →

Fórmulas.
Vamos a definir las fórmulas (expresiones) correctas del lenguaje.
Términos.
Empezamos definiendo lo que son los términos:
i) Los símbolos de constantes y variables son términos.
ii) Si f es un símbolo de una función n-aria y t1, t2 ... tn son términos, entonces f(t1, t2 ... tn) es
también untérmino.
Ejemplos:
c (constante)
x (variable)
f(c1,x1,c2,x2,x3)
f(c,g(x,y,z),d,x,z)
Fórmulas atómicas.
Si P es un símbolo de predicado n-ario y t1, t2 ... tn son términos, entonces P(t1, t2 ... tn) es una
fórmula atómica, también llamada átomo.
Ejemplos:
Padre(juan,ana) C(f(x,y),a,z)

Fórmulas bien formadas.
De todas las expresiones o fórmulas que podemos construirempleando los símbolos de este
lenguaje, solamente son correctas las que se construyen siguiendo las siguientes reglas. Estas fórmulas
se denominan fórmulas bien formadas (fbf):
i) Una fórmula atómica es una fbf.
ii) Si F1 y F2 son fbf's, entonces también lo son:
F1∧ F2
F1∨ F2
F1→ F2
y
¬ F1


iii) Si F es una fbf, entonces también lo son:
∀x F y
∃x F
iv) Si F es una...