VI LA PERSPECTIVA LÓGICA DEL MODELO RELACIONAL

1. INTRODUCCIÓN

2. CÁLCULO DE PREDICADOS DE PRIMER ORDEN

3. UNA BASE DE DATOS COMO UNA INTERPRETACIÓN DE UN LPO

4. FÓRMULAS SEGURAS

5. CÁLCULO RELACIONAL

Hemos visto que el álgebra relacional consiste en la especificación de

una secuencia de operaciones sobre las tablas de la base de datos de tal

forma que obtenemos una nueva relación resultado. Manejamos una

lista de operadores de los que conocemos, básicamente, su resultado.

Por ejemplo, la diferencia dará como resultado todas las filas del primer

operando que no pertenezcan también al segundo. O la selección, que

obtiene las tuplas que cumplen una determinada condición.

Imaginemos, ahora, que vamos a trabajar con expresiones que,

dependiendo de sus argumentos, se evalúan a cierto o falso, del tipo

CLIENTE(x) en la que si un valor está actualmente almacenado en la

tabla CLIENTE, sustituyendo x con ese valor el resultado de la expresión

es verdadero. Imaginemos, también, que un módulo de consultas es

capaz de probar todos los valores posibles y mostrarnos en pantalla

aquellos que hacen cierta la expresión anterior: ya tenemos un listado

de clientes.          

Aún más, podemos pensar en otra expresión tal como CLIENTE(x) y

x.ciudad=’Alicante’. Si sustituimos todos los valores posibles en x, los

que pertenezcan a la tabla y su atributo ciudad contenga ‘Alicante’ serán

los que hagan cierta esta expresión. Estamos dando por supuesto, claro

está, que x es una tupla. Estamos expresando, mediante una fórmula

qué características ha de tener la información esperada, “qué queremos

obtener”.

Sólo necesitamos unas reglas para escribir estas expresiones, una

sintaxis para comunicarnos con ese módulo de consultas imaginario y los

criterios por los que se obtendrán valores de cierto o falso. En este tema

veremos una nueva forma de describir una base de datos usando

conceptos del cálculo de predicados de primer orden.

100

VI1. introducción

Además del álgebra relacional (AR), Codd desarrolló dos lenguajes de

especificación de bases de datos relacionales basados en el cálculo de

predicados de primer orden (CPPO). Estos lenguajes son el cálculo

relacional orientado a tuplas y el cálculo relacional orientado a dominios.

El AR es cómodo para nosotros, en cierta medida, puesto que la forma de

escribir consultas se asemeja a escribir expresiones aritméticas. Además, sus

operadores se pueden alinear (más o menos) con las principales cláusulas de

la orden select de SQL.

Pues bien, con los cálculos relacionales, se describe el conjunto de

información deseado mediante fórmulas lógicas de primer orden. Así, la

consulta se convierte en algo así como “qué valores de la base de datos

hacen cierta la fórmula”27.

Lo que necesitamos es una guía (un “manual”) de cómo construir las fórmulas

y cómo evaluarlas, cuando son ciertas y cuando falsas. Nuevamente, Codd

hace uso de una teoría matemática ya existente, el CPPO. Si para el álgebra

relacional realizó una adaptación del modelo relacional a la teoría de

conjuntos (la definición de ciertos operadores, básicamente), para el cálculo

relacional esta adaptación consiste en la definición de una interpretación de

un lenguaje de primer orden y del concepto de fórmula segura.

Este tema trata del fundamento matemático que hay detrás del cálculo

relacional orientado a tuplas y del orientado a dominios, ese conocimiento

previo necesario para poder escribir fórmulas y saber cómo obtener su

resultado.

Dicho de otro modo, cómo podemos describir una base de datos relacional en

términos del CPPO. Para ello, debemos disponer de un lenguaje de primer

orden y de una interpretación de ese lenguaje. El lenguaje de primer orden

lo constituyen los símbolos que se utilizan al escribir las fórmulas, y la

interpretación la asignación de valores a esos símbolos, lo que nos permite

definir cuando una fórmula se evalúa a cierto o falso.

VI2. cálculo de predicados de primer

orden

El CPPO, y en general la lógica, nos permite hacer deducciones sobre un

universo de discurso. Por ello, es imprescindible disponer de un lenguaje

preciso que nos permita describir aquellos aspectos relevantes de la realidad

objeto de estudio. Este lenguaje, que llamaremos lenguaje de primer orden

(LPO), consta de unos símbolos y unas reglas precisas para combinarlos en

expresiones sintácticamente correctas, en fórmulas. Una interpretación de

un LPO, define el valor de verdad de tales fórmulas.

27 En realidad, simplemente “qué valores hacen cierta la fórmula”; al adaptar el modelo relacional

al CPPO nos vamos a asegurar de que los datos con los que trabajamos son los de la

ocurrencia de la base de datos (se verá en fórmulas seguras)

organización física de las bases de datos

101

Podemos utilizar nuestro idioma para ilustrar estos dos conceptos. Una frase

escrita contiene, o puede contener, nombres, verbos, adjetivos, adverbios,

artículos, pronombres, etc. Algunas palabras tienen carga semántica

(significan algo, se pueden encontrar en un diccionario) y otras son

modificadores o conectores. Por ejemplo: “este señor dice tonterías” es una

frase correctamente escrita según nuestra gramática, pero no lo es “dice

señor este tonterías”. Pensemos ahora en un ciudadano de la ciudad de

Taipei: salvo que, por esas casualidades, aprendiera español en algún

momento de su vida, ni tan siquiera la primera frase tiene sentido para él.

Necesita conocer las palabras y, tanto o más importante, qué significan.

Asimilemos, pues, el LPO a las palabras y las reglas para construir frases, y la

interpretación a un diccionario que nos dice qué significan esas palabras

(pueden tener varios significados) y qué sentido tienen en una frase concreta.

Por ejemplo, aunque según la sintaxis es correcto decir “este árbol dice

tonterías”, la interpretación nos diría que no tiene sentido, que los árboles no

hablan.

Nuestro objetivo final es ver como podemos adaptar el modelo relacional y

verlo como una interpretación de un lenguaje de primer orden. Así pues,

estamos obligados a conocer que es un LPO y que es una interpretación.

VI2.1.lenguaje de primer orden

Un lenguaje de primer orden es un conjunto de símbolos, un alfabeto, y unas

reglas que nos dicen que unas secuencias de símbolos son correctas y otras

no (unas están “bien escritas” y otras no). Los símbolos podemos dividirlos en

dos tipos, aquellos a los que se les asignara valor y aquellos que actúan

como conectores o modificadores. Como veremos seguidamente, variables,

constantes, predicados y funciones pertenecen al primer tipo, y

cuantificadores, conectivas lógicas, y símbolos de comparación y puntuación

al segundo. La forma de combinar estos símbolos correctamente se concreta

en el concepto de fórmula bien formada, basado en la definición de fórmula

atómica, y éste a su vez en la de término.

alfabeto

Un lenguaje de primer orden, L, viene definido por un par (A, F), donde A es

un alfabeto de símbolos y F el conjunto de todas las expresiones

sintácticamente correctas (fórmulas bien formadas) que se pueden construir

utilizando los símbolos de A.

Como ya se ha dicho, el alfabeto A contiene las siguientes clases de

símbolos:

• Variables

• Constantes

• Símbolos de función

La declaración de la cantidad de argumentos de una función se

hace mediante puntos separados por comas. Por ejemplo, f( . , . )

representa a una función de 2 parámetros.

• Símbolos de predicado

BD1 2006-2007

102

Al igual que para las funciones se ha de indicar la cantidad de

argumentos.

• Símbolos de comparación: < > <= >= <>

• Símbolos de puntuación: ( ) ,

• Conectivas lógicas: ¬ ∧ ∨ →

Negación, conjunción, disyunción e implicación.

• Cuantificadores: ∃ (existencial), ∀ (universal)

F es el conjunto de todas las expresiones que se pueden construir

combinando los símbolos anteriores. La definición de fórmula bien formada

establece estas reglas de combinación de símbolos pero, dado que esta

definición se basa en ellos, antes es necesario introducir los conceptos de

término y fórmula atómica.

término

Un término se define recursivamente como sigue:

• Un símbolo de constante es un término.

• Un símbolo de variable es un término.

• Si f es un símbolo de función de n argumentos y t1, t2, ..., tn son

términos, entonces f(t1 , t2 , ..., tn) es un término.

• Nada más es un término.

fórmula atómica

Si P es un símbolo de predicado de n argumentos y t1, t2, ..., tn son términos,

entonces P(t1, t2, ..., tn) es una fórmula atómica o átomo.

fórmula bien formada

Una fórmula bien formada (FBF) se define recursivamente aplicando las

siguientes reglas:

• Una fórmula atómica es una FBF.

• Si F y G son FBF’s, entonces también lo son:

¬F

F ∧ G

F ∨ G

F → G

• Si x es un símbolo de variable y F es una FBF, entonces también lo

son:

∀x F

∃x F

• Si F es una FBF, entonces también lo es (F).

• Nada más es una FBF.

organización física de las bases de datos

103

En definitiva, una FBF se construye conectando fórmulas atómicas y estas

últimas mediante símbolos de predicado y términos. El objetivo de estas

definiciones es establecer las reglas de “escritura”. Por ejemplo,

∀x P(x) → Q(x) es una FBF, pero las siguientes no lo son:

x ∀ P(x) → Q(x)

∀x → Q(x)

∀(x P(x) → (x))

Nótese que en ningún momento hemos hablado de “resultados”, simplemente

estamos aprendiendo a “escribir” pero todavía no sabemos lo que “decimos”

(para esto necesitamos la interpretación).

fórmulas abiertas y cerradas

Este concepto nos será muy útil cuando, finalmente, interroguemos a la base

de datos. Adelantándonos al punto donde se expone su aplicación, digamos

que las fórmulas abiertas son las que obtienen una lista de valores (un

resultado en pantalla, por entendernos), y valores de cierto o falso las

cerradas, con lo que se pueden utilizar éstas para especificar restricciones de

integridad del tipo “los clientes de Alicante no pueden tener descuento”.

La diferencia entre unas y otras se basa en la utilización de los

cuantificadores existencial y universal. Cuando una variable está en el

alcance de un cuantificador se dice que es una ocurrencia de variable

ligada, en contraposición con la ocurrencia de variable libre, no afectada por

cuantificador alguno.

El alcance de un cuantificador es la FBF que se encuentra inmediatamente a

su derecha. En la expresión ∀x P(x) → Q(x), la primera FBF a la derecha del

cuantificador es P(x), por lo que este es el alcance del cuantificador universal,

y Q(x) queda fuera de él.

A partir de ahora, supongamos que x e y son símbolos de variable y que P(.),

Q(.), R(.,.) son símbolos de predicado. Las siguientes FBF ilustrarán los

conceptos de formulas abiertas y cerradas.

∀x P(x) → Q(x)

La primera ocurrencia de la variable x, la que aparece como

argumento del predicado P(.), es ligada, esto es, está bajo el

alcance del cuantificador universal, pero la segunda ocurrencia

es libre.

Nótese que cuando un símbolo de variable se utiliza, al mismo

tiempo, en ocurrencias libres y ligadas, su evaluación cuando

se defina la interpretación se hará como si utilizáramos

símbolos distintos. Es decir, que la fórmula podría haberse

escrito igualmente como ∀x P(x) → Q(y).

∀x (P(x) → Q(x)) ∨ ¬P(x)

En esta fórmula, y por la acción de los paréntesis, las dos

primeras ocurrencias de x están bajo el alcance del

cuantificador, y la interpretación que se defina las considerará

como la misma variable, mientras que la tercera y última es

libre y considerada una variable distinta. Al igual que antes, la

fórmula ∀x(P(x) → Q(x)) ∨ ¬P(y) será equivalente.

BD1 2006-2007

104

∃x (R(x, y) ∨ P(x))

Ahora todas las ocurrencias de x son ligadas mientras que la

de y es libre.

∃x ∃y (R(x, y) ∨ P(x))

Ahora todas las ocurrencias de variable son ligadas. Para

entendernos, si pudiéramos sustituir cada FBF por un símbolo,

el alcance del segundo cuantificador es ∃x ∃y F, y el alcance

del primero es ∃x F’.

Esta clasificación de las ocurrencias de una variable nos permite distinguir

entre fórmulas cerradas, aquellas que no tienen ocurrencias libres de

variable, y fórmulas abiertas, con al menos una ocurrencia libre de variable.

De los ejemplos anteriores, las tres primeras fórmulas son ejemplos de

fórmula abierta, y la cuarta de fórmula cerrada.

VI2.2.interpretación

Un lenguaje de primer orden nos permite efectuar deducciones sobre un

universo de discurso, siendo éste el conjunto de todos los valores posibles.

Sin embargo, aunque sabemos construir expresiones, debemos dotar a cada

símbolo del lenguaje de un “contenido”, establecer los valores que definen la

evaluación a cierto o falso de las fórmulas.

En este sentido pretendemos que:

• las constantes denoten objetos (individuos) de ese universo de

discurso.

• los predicados denoten propiedades sobre los objetos del universo de

discurso.

• las fórmulas bien formadas sean enunciados o sentencias sobre el

universo.

Dicho de otra forma, dado un lenguaje de primer orden L=(A, F), el objetivo es

la asignación a cada símbolo del alfabeto A de un valor del universo de

discurso de forma que, utilizando esta asignación como base, podamos definir

el valor de verdad de cualquier fórmula de dicho lenguaje. Para ello

introducimos el concepto de interpretación.

interpretación

Una interpretación I de un lenguaje de primer orden, L=(A, F), es una

cuádrupla (D, K, H, E) donde:

• D es un conjunto no vacío, llamado dominio de I, en el que las

variables de A toman valores, y que constituye el universo de

discurso.

• K es una aplicación que asigna a cada símbolo de constante un

elemento de D.

organización física de las bases de datos

105

• H es una aplicación que asigna a cada símbolo de función n-aria una

función de Dn en D.

• E es una aplicación que asigna a cada símbolo de predicado n-ario

una relación sobre Dn (esta relación se denomina extensión del

predicado).

Para ilustrar la definición anterior, vamos a suponer que D es el conjunto de

los números enteros. Supongamos, también, que L=(A, F) está bien definido

(tiene símbolos de constante, de variable, de predicado, etc.).

De forma general, una constante es un valor del dominio. Otra cosa es el

símbolo que utilizamos para representarlo. En nuestra vida cotidiana

utilizamos ideas intangibles, manejamos objetos, nos relacionamos con

personas, y cuando pretendemos comunicar a otros esos conceptos o

referirnos a esas cosas o individuos utilizamos símbolos, palabras, que

representan a esas ideas, objetos o personas, justo lo que estamos haciendo

nosotros al escribir este texto y al leerlo.

Todos sabemos, hablando de los enteros, lo que significa el “uno” o el “dos”.

Para referirnos a ellos escribimos ‘1’ y ‘2’. El número entero 1 es un concepto,

una idea, que para poder ser manejado e interpretado de igual forma por

todos, está representado por un símbolo (gráfico en nuestro caso) que es el

carácter ‘1’. Luego, antes de poder utilizar estos caracteres en una expresión

aritmética como 1 + 2, se han asignado los valores del dominio a los símbolos

de constante. Lo que pasa es que no somos conscientes de esa asignación,

la hemos aprendido desde pequeños en la escuela y es la que se maneja en

todo el mundo porque necesitamos comunicarnos y ser entendidos.

K define esa asignación. Si suponemos que el conjunto de símbolos de

constante esta compuesto por {1, 2, 3, 4, ...}, K(1) = 1, K(2) = 2, K(3) = 3, ..., o

de forma general:

K = { (c, d) , c es un símbolo de constante, d es un entero}

Es decir, el argumento de K es un símbolo y el resultado un valor del dominio

(cuando escribimos ‘1’ estamos representando al entero 1). Por eso mismo,

ya que la interpretación la definimos nosotros, también podíamos haber

establecido que K(1) = 2 y K(2) = 1.

Obviamente, si así fuera necesario, el conjunto de constantes podría ser otro,

por ejemplo {a, b, c}, y K definido como {(a,1), (b,2), (c,3)} (a representa al

entero 1, b al 2, y c al 3).

H y E realizan la misma tarea para los símbolos de función y de predicado. Si

f(.,.) es un símbolo de función podríamos asignarle una función de D2 en D,

con una expresión general como por ejemplo f(x,y)=x+y, o de forma explícita

como f(1,1)=2, f(1,2)=3, f(2,1)=3, ...

La asignación de extensión a un símbolo de predicado consiste en establecer

los valores que hacen cierto el predicado (como se verá más adelante), por

ejemplo para un predicado de un argumento P(.) el conjunto de valores {1, 3,

5} o para otro de dos argumentos Q(.,.) el conjunto {(1,1), (1,2), (2,2), (2,4)}.

De esta forma, P(1) y Q(1,2) se evalúan a cierto, mientras que P(5) y Q(3,3) a

falso. También Q(f(1,1),2) se evalúa a cierto.

VI2.3.evaluación de fórmulas

En realidad, no debemos olvidar que nuestro objetivo final es hacer

deducciones acerca del universo de discurso, y esto se consigue evaluando

BD1 2006-2007

106

las fórmulas que se precisen. Es decir, dada una fórmula, ésta será cierta o

falsa, o informará sobre qué elementos del universo de discurso la hacen

cierta.

Si nos adelantamos una vez más, su aplicación a bases de datos relacionales

es clara: mediante fórmulas queremos saber si los datos almacenados en ella

cumplen una cierta condición o no, o recuperar un conjunto de información.

Por evaluar fórmulas entendemos obtener una respuesta según la

interpretación que se haya definido. Las reglas de evaluación se distinguen

según el tipo de fórmula, cerrada o abierta. Cuando la fórmula es cerrada, el

resultado es cierto o falso, y cuando es abierta, devuelve una lista de valores.

En todos los casos, se asume el orden de precedencia de los operadores que

se muestran en el siguiente cuadro, de tal forma que fórmulas entre

paréntesis serán evaluadas en primer lugar, y fórmulas con conjunciones,

disyunciones o implicaciones serán las últimas en evaluarse:

( )

<, >, <=, >=, <>

∀, ∃

¬

∧, ∨, →

evaluación de fórmulas cerradas

La evaluación de una fórmula cerrada G en una interpretación da como

resultado el valor cierto o falso, y se define como sigue:

• Si G es una fórmula atómica, G = P(t1, t2, ..., tn), y (a1, a2, ..., an) una

tupla tal que ai sustituye a ti, entonces G se evalúa a cierto si la tupla

está en la extensión que la interpretación asigna a P, y a falso en caso

contrario.

• Si G contiene alguna conectiva lógica, se evalúa de acuerdo a las

siguiente tabla (F y H son fórmulas bien formadas).

F H F∧H F∨H F→H ¬F

cierto cierto cierto cierto cierto falso

falso cierto falso cierto cierto cierto

cierto falso falso cierto falso

falso falso falso falso cierto

• Si G = ∀ x F entonces G es cierta si, al sustituir la variable x en F por

todos los elementos del dominio, F es cierta siempre, y G es falsa en

cualquier otro caso.

• Si G = ∃ x F entonces G es cierta si F es cierta al menos para un

elemento del dominio que sustituya la variable x en F, y G es falsa en

cualquier otro caso.

evaluación de fórmulas abiertas

• El resultado de evaluar una fórmula abierta G con n (n > 0) variables

libres en una interpretación, es una relación n-aria, RG, definida sobre

el dominio de la interpretación D.

Cada tupla de esta relación es tal que, al sustituir las variables

libres por las correspondientes componentes de la tupla, la fórmula

cerrada que resulta es cierta en la interpretación. Si la relación RG

organización física de las bases de datos

107

coincide con Dn la fórmula se evalúa simplemente a cierto; si RG no

contiene ninguna tupla, entonces la fórmula se evalúa a falso.

Resumiendo, con el LPO definimos los símbolos y la forma de las fórmulas

que los utilizan, y con la interpretación establecemos los valores que definirán

el resultado de esas fórmulas.

VI2.4.un ejemplo

Sea A el alfabeto de un lenguaje de primer orden:

Variables = { x, y }

Constantes = { a, b, c }

Predicados = { P( . ), Q( . ), R( . , . ) }

Sea I(D, K, H, E) definida como sigue

D = {1, 2, 3}

K(a) = 1, K(b) = 2, K(c) = 3

E(P)={2}, E(Q)={1, 3}, E(R)={(1,1), (1,2), (1,3)}

F1 Q(x)

Esta es una fórmula abierta por lo que el proceso de

evaluación consiste en sustituir la variable x por todos y cada

uno de los valores del dominio y comprobar si la fórmula

cerrada correspondiente es cierta o falsa, que es lo mismo

que decir que el resultado de esta fórmula son todos los

valores pertenecientes a la extensión del predicado.

Como Q(1) y Q(3) se evalúan a cierto y Q(2) a falso, el

resultado de la formula consiste en dos tuplas de una

componente:

Q(x) = {1, 3}

F2 Q(x) ∧ ∀y R(x, y)

Esta es otra fórmula abierta pero se combinan variables

ligadas y libres. Por la precedencia de operadores, podemos

resumir la fórmula como F ∧ G, por lo que ambas subfórmulas

han de ser ciertas para que toda la fórmula lo sea; los únicos

valores que hacen cierto Q(x) son el 1 y el 3.

Q(1) ∧ R(1, 1) = cierto

Q(1) ∧ R(1, 2) = cierto

Q(1) ∧ R(1, 3) = cierto

Cuando x vale 1, se cumple que en R hay una tupla para

todos los elementos del dominio en la que la primera

componente es 1. Luego el valor 1 hace cierta la fórmula Q(x)

∧ ∀y R(x, y).

Q(3) ∧ R(3, 1) = falso

Puesto que el par (3,1) no pertenece a la extensión de R, ya

hemos encontrado un valor de y para el que la fórmula se

BD1 2006-2007

108

hace falsa, luego ya no se cumple para todo valor de y, y toda

la fórmula se evalúa a falso.

El resultado final de la fórmula Q(x) ∧ ∀y R(x, y) es una única

tupla:

Q(x) ∧ ∀y R(x, y) = {1}

G1 ∀x(P(x) →  3) =¬Q(x))

Esta fórmula es cerrada ya que las dos ocurrencias de la

variable x están en el alcance del cuantificador universal, por

lo que la fórmula se describiría como que todo valor que esté

en P no lo está en Q. Podemos decir que vamos a trabajar con

una única variable. Así, debemos comprobar todos los valores

del dominio, y si para todos ellos la fórmula se evalúa a cierto,

es que la fórmula es cierta.

(P(1) → ¬Q(1)) = (falso → ¬cierto) = (falso → falso) = cierto

(P(2) → ¬Q(2)) = (cierto → ¬falso) = (cierto → cierto) =cierto

(P(3) → ¬Q(3)) = (falso → ¬cierto) = (falso → falso) = cierto

∀x(P(x) → ¬Q(x)) = cierto

G2 ∀x(P(x) → ∃y R(x, y))

Para x=1 y x=3 el antecedente de la implicación es falso por

lo que, valga lo que valga ∃y R(x, y), el resultado es cierto.

No existe ningún par en R cuya primera componente sea 2, ∃y

R(2, y) es falso por lo que la fórmula P(2) → ∃y R(2, y) se

evalúa a falso.

Como no se cumple para todo valor de x, la fórmula se evalúa

a falso:

∀x(P(x) → ∃y R(x, y)) = falso

G3 ∃x(P(x) ∨ ∃y R(x, y))

Se puede comprobar que para x=1, la fórmula se evalúa a

cierto. Si se cumple para un valor ya podemos decir que el

resultado es:

∃x(P(x) ∨ ∃y R(x, y)) = cierto

VI2.5.definición de modelo

Dada una interpretación I y un conjunto de fórmulas bien formadas T, se dice

que I es modelo para T si y sólo si todas las fórmulas de T se evalúan a

cierto en I.

En el ejemplo anterior, si únicamente consideramos las fórmulas cerradas G1,

G2 y G3 la interpretación no es modelo para ellas ya que G2 se evalúa a

falso. Sin embargo la interpretación sí es modelo para las fórmulas G1 y G3.