03. El modelo relacional de datos: perspectiva lógica

En este apartado, como ya se ha comentado, se va a presentar el Modelo Relacional desde un punto de vista lógico lo que permitirá posteriormente introducir el lenguaje SQL, convertido desde 1987 en el lenguaje estándar para los sistemas de bases de datos relacionales.

En el apartado 2.3.1 se hace un repaso de la lógica de 1er orden, para más tarde, en el apartado 2.3.2 justificar su adecuación como lenguaje de consulta para bases de datos relacionales.

La lógica de 1er orden

La lógica de 1er orden es un sistema formal que permite razonar sobre un universo de discurso o dominio. Para poder realizar esta tarea, la lógica proporciona dos instrumentos: un lenguaje con el cual hacer afirmaciones o aserciones sobre el universo de interés y unas reglas con las cuales determinar el valor de verdad de las aserciones o afirmaciones realizadas.

Considérese un universo de discurso (D) relativo a una escuela universitaria de la que sólo interesan sus alumnos y su plan de estudios; por simplicidad se considera que la única información relevante sobre los alumnos es su nombre y la única información relevante sobre las asignaturas es un código interno que las identifica.

Las propiedades (P) de los individuos (alumnos y asignaturas) de este universo sobre las que se desea razonar son: ser un alumno, ser una asignatura, y estar matriculado.

Figura 2.5

Posibles aserciones que se puede hacer sobre estos individuos relativas a las propiedades indicadas son:

“Existe algún alumno matriculado de BDA”

"Todo alumno está matriculado de alguna asignatura"

Pero, ¿son ciertas estas aserciones?. Evidentemente para poder contestar a esta pregunta, se necesita tener información sobre las propiedades P en el dominio D, es decir es preciso conocer para qué individuos del dominio se cumplen estas propiedades. Si esta información es la siguiente:

Juan, Luis y María son alumnos, AD1 y BDA son códigos de asignatura y Luis está matriculado de AD1 y Juan está matriculado de BDA, entonces se puede responder a las preguntas anteriores diciendo que, para el conocimiento que se tiene de las propiedades P en el dominio D, la primera aserción es cierta y la segunda aserción es falsa.

Si se utiliza la lógica de 1er orden para formalizar el discurso anterior y evitar la ambigüedad del lenguaje natural, el resultado es el siguiente:

-Hay que tener en cuenta que en un lenguaje de 1er orden, no son necesarias todas las conectivas lógicas ni los dos cuantificadores. Un subconjunto mínimo de conectivas es { ¬, ∧} ya que la implicación y la disyunción pueden definirse en términos de éstas: A → B ≡ A ∧ ¬B y A ∨ B ≡ ¬(¬A ∧ ¬B). Por otra parte, cualquiera de los cuantificadores se puede expresar en términos del otro: ∀xF(x) ≡ ¬∃x (¬ F(x)).-

a) Se debe definir un lenguaje de 1er orden (L) para poder referirse a los individuos y a las propiedades del universo de discurso:

L:

Constantes = {Luis, María, Juan, AD1, BDA, Pedro}

Predicados = {Alumno (.), Asignatura (.), Matrícula(.,.)}

Variables = {x, y}

Conectivas = {→, ¬, ∧, ∨ }

Cuantificadores = {∀, ∃}

En este lenguaje, las constantes sirven para denotar a los individuos (a través de sus atributos), y los predicados sirven para denotar las propiedades; estos dos conjuntos son específicos de cada lenguaje de 1er orden, los restantes conjuntos son comunes a todos ellos.

Con este lenguaje ya se pueden escribir formalmente las dos afirmaciones anteriores, que quedan representadas respectivamente por las siguientes fórmulas:

F1: ∃ x (Alumno(x) ∧ Matrícula (x, BDA))

F2: ∀ x (Alumno(x) → ∃ y Matrícula (x,y))

b) El conocimiento que se tiene sobre las propiedades en el dominio se denomina interpretación (I) del lenguaje (L) en el dominio (D), en nuestro ejemplo en el que el dominio es D = {Luis, María, Juan, AD1, BDA, Pedro}, y con el conocimiento que se ha supuesto, esta interpretación sería:

Alumno = {Juan, Luis, María}

Asignatura = {AD1, BDA}

Matrícula = {(Luis, AD1), (Juan, BDA)}

(Juan Luis y María son alumnos)

(AD1 y BDA son asignaturas)

(Luis está matriculado de AD1 y Juan de BDA)

Este conocimiento sobre los predicados se puede representar de una forma más gráfica por medio de tablas:

Es importante destacar que este conocimiento puede variar con el tiempo.

c) La evaluación de una fórmula en una interpretación I se realiza siguiendo unas reglas fijas11 que indican cómo evaluar (interpretar) cada componente de la fórmula en I; estas reglas son:

  • si p es un predicado de aridad n, la fórmula p(c1, c2, ..., cn) es cierta en I si (c1, c2, .., cn) pertenece a la interpretación de p en I, en caso contrario es falsa.

  • si F y G son fórmulas, entonces F ∧ G, F ∨ G, F → G, y ¬ F se evalúan según las tablas de verdad de estas conectivas lógicas.

  • si F es una fórmula cuantificada existencialmente, de la forma ∃xF(x), entonces F es cierta en I si existe un valor del dominio D que asignado a la variable x hace cierta la fórmula, en caso contrario es falsa.

  • si F es una fórmula cuantificada universalmente, de la forma ∀xF(x), entonces F es cierta en I si para todo valor del dominio D se cumple que al asignar el valor a la variable x la fórmula se hace cierta, en caso contrario es falsa.

Con este lenguaje L, no sólo se pueden hacer aserciones sino que también se puede interrogar sobre las propiedades P en el universo D. Por ejemplo, la fórmula F3: Alumno(x) ∧ Matrícula (x,AD1), sirve para preguntar por los alumnos matriculados de la asignatura AD1. La evaluación de la fórmula F3, consiste en buscar los valores de la variable x para los que la fórmula es cierta en I, en el ejemplo x={Luis}.

Es decir, si la fórmula es cerrada (todas sus variables están ligadas a cuantificadores), como en el caso de F1 y F2, entonces la fórmula representa una aserción o afirmación que será cierta o falsa en I, y si la fórmula es abierta (tiene variables libres que no están ligadas a un cuantificador), como en el caso de F3, entonces la fórmula representa una consulta cuya evaluación devolverá los valores de sus variables libres que hacen cierta la fórmula en I.

Interpretación lógica de una base de datos relacional. La lógica de 1er. orden como lenguaje relacional

Como se desprende del ejemplo del apartado anterior, dar una interpretación de un lenguaje de 1er orden en un dominio D, consiste en asociar a cada predicado n-ario del lenguaje L una relación n-aria definida sobre el dominio D. Estas relaciones representan el conocimiento que se tiene de cada predicado en el universo de interés; como se ha visto, este conocimiento es el que permite evaluar cualquier afirmación o aserción escrita en el lenguaje lógico. Así, la primera tupla de la relación Matrícula se puede interpretar como el conocimiento: "Luis está matriculado de AD1".

Este paralelismo entre una interpretación de un lenguaje de 1er orden y una base de datos relacional conduce de forma natural a la segunda aproximación al estudio del Modelo Relacional de Datos: la aproximación lógica.

En esta aproximación los nombres de las relaciones de la base de datos se ven como predicados de un lenguaje de 1er orden y la extensión de estas relaciones como el conocimiento (interpretación) de los predicados en el universo de interés.

Por lo tanto y de acuerdo a las reflexiones del punto anterior, el lenguaje de la lógica de 1er orden es perfectamente adecuado para ser utilizado como lenguaje de consultas en una base de datos relacional. Estas ideas se van a ilustrar con un ejemplo.

Ejemplo 2.22

Sea la base de datos con información geográfica del Ejemplo 2.8 utilizada en la presentación de la perspectiva algebraica del Modelo Relacional en el apartado 2.1.

Como se ha dicho, para interrogar la base de datos con un lenguaje lógico, lo primero que hay que hacer es establecer una correspondencia entre cada relación de grado n del esquema con un predicado n-ario del lenguaje lógico que se va a utilizar.

Esquema E:

Río (rcod: dom_rcod, nombre: dom_nom)

Otros_Ríos (rcod: dom_rcod, nombre: dom_nom)

Provincia (pcod: dom_pcod, nombre: dom_nom)

Pasa_por (pcod: dom_pcod, rcod: dom_rcod)

Predicados de L:

Río (. , .)

Otros_Ríos (. , .)

Provincia(. , . )

Pasa_por(. , .)

Con este lenguaje ya se pueden escibir consultas a la base de datos; éstas consultas serán fórmulas de L cuya evaluación se realizará sobre la extensión actual de la base de datos, siguiendo las reglas expuestas en el apartado anterior. Por ejemplo:

F1: Río(x, y) ∧ Pasa_por(44, x)

F2: Río(x, y) ∧ ¬∃z Pasa_por(z, x),

La fórmula F1 representa la consulta ¿qué ríos pasan por la provincia de código 44?, cuya evaluación en la extensión actual devuelve los valores de las variables libres que hacen cierta la fórmula, en el ejemplo x={r2} e y={'Turia'}, es decir el único río que pasa por la provincia 44 en la base de datos es el río Turia de código r2.

La fórmula F2 representa la consulta ¿qué ríos no pasan por ninguna provincia?, cuya evaluación en la extensión actual no devuelve valores para las variables x e y ya que en la base de datos del ejemplo todos los ríos pasan por alguna provincia.

Es importante destacar, en las consultas anteriores, cómo al utilizar un lenguaje lógico para interrogar la base de datos, se prescinde de los nombres de atributos que aparecen en el esquema de las relaciones, haciendo referencia a los atributos de las tuplas por su posición relativa en el esquema de la relación. Así cuando, en la fórmula F1, se escribe Pasa_por(44, x), se está asumiendo que el primer atributo de su esquema es pcod (el código de provincia), y el segundo atributo es rcod (el código de río). Otra observación importante es la relativa al supuesto que se hace en lógica de 1er orden, de considerar un único dominio D en el que toman valor todas las variables; en base de datos este supuesto es incómodo ya que como es obvio, los dominios (valores posibles) de ríos y provincias vienen dados por las extensiones en la base de datos de las relaciones Río y Provincia respectivamente.

Para evitar el uso de una notación excesivamente matemática y poco cómoda en el contexto de las bases de datos, en los lenguajes relacionales de tipo lógico se utilizan variables-tupla, es decir variables que se declaran sobre las relaciones de la base de datos y cuyos componentes pueden referirse por un nombre de atributo. Es importante destacar que la declaración de una variable-tupla sobre una relación del esquema, restringe sus valores posibles a las tuplas de la relación en la extensión actual de la base de datos.

Ejemplo 2.23

En el caso de las consultas del Ejemplo 2.22 representadas por las fórmulas F1 y F2, éstas se reescribirían como:

F1: RX:Río∃PPX:Pasa_por (PPX.rcod=RX.rcod ∧ PPX.pcod=44)

F2: RX:Río¬∃PPX:Pasa_por (RX.rcod=PPX.rcod)

En la sintaxis de estas fórmulas se indica que la variable-tupla RX (resp. PPX) se declara sobre la extensión actual de la relación Río (resp. Pasa_por) en la base de datos, es decir sus valores al evaluar las fórmulas serán tomados de esta extensión. Observar que ahora las componentes de las tuplas son referidas por el correspondiente nombre de atributo, no por su posición relativa. Los valores devueltos en la evaluación de estas fórmulas son valores de la variable-tupla RX que es la única variable libre en dichas fórmulas, es decir se devolverán tuplas completas de la relación Río.

Con el lenguaje lógico derivado del esquema de la base de datos, y asumiendo las variaciones sintácticas que se han comentado (uso de variables-tupla), se puede plantear cualquier consulta o aserción sobre la base de datos.

Ejemplo 2.24

Consulta: ¿Qué ríos pasan por al menos dos provincias?

RX:Río

∃PPX:Pasa_por, ∃PPY:Pasa_por

(RX.rcod=PPX.rcod ∧ RX.rcod=PPY.rcod ∧ PPX.pcod ≠ PPY.pcod)

Consulta: ¿Qué ríos pasan por todas las provincias?

RX:Río

∀PX:Provincia (∃PPX:Pasa_por (PPX.rcod=RX.rcod ∧PPX.pcod=PX.pcod))

o utilizando la equivalencia entre el cuantificador universal y el cuantificador existencial: ∀xF(x) ≡ ¬∃x (¬ F(x)).

RX:Río

¬∃PX:Provincia (¬∃PPX:Pasa_por (PPX.rcod=RX.rcod ∧PPX.pcod=PX.pcod))

Resumiendo, en este apartado se ha presentado la aproximación lógica al estudio del Modelo Relacional de Datos, y se ha demostrado la utilidad del lenguaje de la Lógica de 1er orden como lenguaje relacional.

La idea de utilizar el lenguaje de la Lógica de 1er orden (o Cálculo de Predicados) como lenguaje relacional fue planteada inicialmente por E.F. Codd en su propuesta de Cálculo Relacional; la idea era definir un Cálculo de Predicados aplicado específicamente a relaciones, en el que las variables se declaraban sobre relaciones del esquema (al estilo del Ejemplo 2.23). Basado en este Cálculo Relacional se implementó el lenguaje QUEL que durante muchos años fue un competidor del estándar actual SQL. Mas tarde, se propuso una versión alternativa del Cálculo Relacional, denominada Cálculo de Dominios, en el cual las variables se declaran sobre los dominios de los atributos, una implementación de este lenguaje fue el lenguaje QBE. A partir de este momento se diferenció entre Cálculo Relacional de Tuplas (Codd) y Cálculo Relacional de Dominios (Lacroix y Pirotte), ambos son lógicamente equivalentes.

Cualquier sistema relacional se puede implementar basándose en el Álgebra Relacional o en el Cálculo Relacional. E.F. Codd demostró la equivalencia de estos dos lenguajes en el siguiente sentido: "toda relación definida por una expresión escrita en cualquiera de los dos lenguajes puede ser también definida por una expresión escrita en el otro". La diferencia entre ambos lenguajes es una diferencia de estilo. El Álgebra Relacional es un lenguaje de estido procedimental; en una expresión de Álgebra Relacional se indica la secuencia de operaciones que se debe realizar para obtener una relación. El lenguaje del Cálculo Relacional es un lenguaje de tipo declarativo; en una expresión de Cálculo Relacional, se define la relación que se desea obtener en términos de las relaciones de la base de datos. Estos lenguajes pueden servir como medida de la expresividad de un lenguaje relacional. Se dice que un lenguaje es relacionalmente completo si es por lo menos tan poderoso como el Cáculo Relacional (o su equivalente el Álgebra Relacional), es decir si cualquier relación definida como una expresión del Cálculo Relacional es también definible como una expresión del lenguaje en cuestión.

A mediados de los setenta, y basándose en el Cálculo Relacional (de tuplas), se inició el desarrollo del lenguaje SQL. El lenguaje que básicamente era de tipo lógico, fue incorporando aspectos (operadores) de la visión algebraica, pudiendose afirmar que es un lenguaje que integra las dos perspectivas: lógica y algebraica.