Cálculo relacional basado en tuplas

El cálculo relacional basado en tuplas es un cálculo introducido por Edgar Frank Codd como parte del cálculo relacional, el cual pertenece al modelo relacional para bases de datos. Fue la inspiración para la creación de los lenguajes de consulta QUEL y SQL, de los cuales este último, aunque menos fiel al original, es ahora el lenguaje de consulta más usado. El cálculo relacional basado en dominio, formulado por Michel Lacroix and Alain Pirotte, se aproxima más a la lógica de primer orden, sin embargo ambos son equivalentes en su poder expresivo.

Definición

Base de datos relacional

Debido a que es un lenguaje de consulta para bases de datos relacionales, primero se debe definir una base de datos relacional. El bloque de construcción relacional básico es el dominio o tipo de datos. Una tupla o registro es un multiconjunto de atributos, los cuales son pares ordenados de dominio y valor, o sólo una fila. Una relación es un conjunto de tuplas. Una tabla es una representación visual aceptada de una relación.

Se asume la existencia de un conjunto C de columnas, por ejemplo, "nombre", "autor" o "dirección"; y de cabeceras como subconjuntos finitos de C. Un esquema de bases de datos relacional es definido como una tupla S = (D, R, h), donde:

• D es el dominio de los valores atómicos (un atributo es atómico si los elementos del dominio son simples e indivisibles).
• R es un conjunto finito de nombres de relación.
• h es una función que asocia una cabecera con cada nombre de relación en R y se define como: h: R → 2^C

Dado un dominio D se define una tupla sobre D como una función parcial que mapea algunos nombres de columna a un valor atómico en D; por ejemplo, name: "Harry", age : 25.

t : C → D

El conjunto de todas las tuplas sobre D se denota como T_D. El subconjunto de C para el cual se define una tupla t se conoce como el dominio de t (que no debe confundirse con el dominio en el esquema) y es escrito como dom(t).

Entonces se puede definir una base de datos relacional dado un esquema S = (D, R, h) como una función:

db : R → 2^T_D

que mapea los nombres de relación en R a subconjuntos finitos de T_D, tales que por cada nombre de relación r en R y tupla t en db(r) se cumple que:

dom(t) = h(r).

Es decir, que todas las tuplas de una relación deben contener los mismos nombres de columna que se definen para el esquema.

Átomos

Para la construcción de las fórmulas se asume un conjunto infinito V de variables de tupla. Las fórmulas se definen dado un esquema de bases de datos S = (D, R, h) y una función parcial tipo : V -> 2^C que define una asignación de tipo que asigna cabeceras a algunas variables de tupla. Entonces se definen el conjunto de fórmulas atómicas A[S,tipo] con las siguientes reglas:

1. Si v y w están en V, a en tipo(v) y b en tipo(w) entonces la fórmula "v.a = w.b" está en A[S,tipo].
2. Si v está en V, a en tipo(v) y k denota un valor en D entonces la fórmula "v.a = k" está en A[S,tipo].
3. Si v está en V, r en R y tipo(v) = h(r) entonces la fórmula "r(v)" está en A[S,tipo].

Ejemplos de átomos son:

• (t.edad = s.edad) — la tupla t tiene un atributo de edad y s tiene un atributo de edad con el mismo valor
• (t.nombre = "Codd") — la tupla t tiene un atributo de nombre y su valor es "Codd"
• Libro(t) — la tupla t se encuentra en la relación Libro.

La semántica formal de aquellos átomos es definida dada una base de datos db sobre S y una variable de tupla val : V -> T_D que mapea las variables de tupla a tuplas sobre el dominio en S:

1. "v.a = w.b" es verdadero si y sólo si val(v)(a) = val(w)(b)
2. "v.a = k" es verdadero si y sólo si val(v)(a) = k
3. "r(v)" es verdadero si y sólo si val(v) is in db(r)

Fórmulas

Los átomos pueden ser combinados en fórmulas, como es común en la lógica de primer orden, con los operadores lógicos ∧ (and o y), ∨ (or u o) y ¬ (not o no), y puede usarse el cuantificador existencial (∃) y el cuantificador universal (∀) para enlazar o unir las variables. Se define el conjunto de fórmulas F[S,tipo] por inducción con las siguientes reglas:

1. Cada átomo en A[S,tipo] está también en F[S,tipo].
2. Si f₁ y f₂ están en F[S,tipo] entonces la fórmula "f₁ ∧ f₂" está también en F[S,tipo].
3. Si f₁ y f₂ está en F[S,tipo] entonces la fórmula "f₁ ∨ f₂" está también en F[S,tipo].
4. Si f está en F[S,tipo] entonces la fórmula "¬ f" está también en F[S,tipo].
5. Si v está en V, una cabecera H y una fórmula f en F[S,tipo_[v->H]] entonces la fórmula "∃ v: H (f)" está también en F[S,tipo], donde tipo_[v->H] denota la función que es igual a tipo excepto que esta mapea v a H.
6. Si v está en V, una cabecera H y una fórmula f en F[S,tipo_[v->H]] entonces la fórmula "∀ v: H (f)" está también en F[S,tipo].

Ejemplos de fórmulas son:

• t.autor = "René Descartes" ∨ t.autor = "Óscar Gómez"
• Libro(t) ∨ Revista(t)
• ∀ t : {autor, título, materia} ( ¬ ( Libro(t) ∧ t.autor = "René Descartes" ∧ ¬ ( t.materia = "revolución científica")))

Asumimos que los cuantificadores se aplican sobre el universo de todas las tuplas sobre el dominio en el esquema. Esto lleva a la formulación de las siguientes semánticas para fórmulas dada una base de datos db sobreS y una variable de tupla val: V -> T_D:

1. "f₁ ∧ f₂" es verdadero si y solo si "f₁" es verdadero y "f₂" es verdadero.
2. "f₁ ∨ f₂" es verdadero si y solo si "f₁" es verdadero o "f₂" es verdadero o ambos son verdaderos.
3. "¬ f" es verdadero si y solo si "f" es falso.
4. "∃ v : H ( f )" es verdadero si y solo si hay una tupla t sobre D tal que dom(t) = H y la fórmula "f" es verdadera para val_[v->t].
5. "∀ v : H ( f )" es verdadero si y solo si para todas las tuplas t sobre D tales que dom(t) = H la fórmula "f" es verdadera para val_[v->t].

Consultas

Dado un esquema S = (D, R, h), se expresa una consulta como:

{ v : H | f(v) }

Donde v es una variable de tupla, H es una cabecera y f(v) una fórmula en F[S,tipo] donde tipo = { (v, H) } y con v como su única variable libre. El resultado de una consulta como estas para una base de datos db sobre S es el conjunto de todas las tuplas t sobre D con dom(t) = H tales que f es verdadero para db y val = { (v, t) }.

Ejemplos de consultas son:

• { t : {nombre} | ∃ s : {nombre, salario} ( Empleado(s) ∧ s.salario = 500.000 ∧ t.nombre = s.nombre ) }
• { t : {proveedor, artículo} | ∃ s : {s#, snombre} ( Proveedor(s) ∧ s.snombre = t.proveedor ∧ ∃ p : {p#, pnombre} ( Producto(p) ∧ p.pnombre = t.artículo ∧ ∃ a : {s#, p#} ( Suministros(a) ∧ s.s# = a.s# ∧ a.p# = p.p# ) }

Semántica y restricción sintáctica

Consultas independiente del dominio

Debido a que la semántica de los cuantificadores es tal que ellos cuantifican sobre todas las tuplas en el dominio del esquema, puede ser que una consulta retorne un resultado diferente para una base de datos específica si se presume otro esquema. Por ejemplo, considerando los dos esquemas S₁ = ( D₁, R, h ) y S₂ = ( D₂, R, h ) con dominios D₁ = { 1 }, D₂ = { 1, 2 }, nombres de relación R = { "r₁" } y cabeceras h = { ("r₁", {"a"}) }. Ambos esquemas tienen una instancia común:

db = { ( "r₁", { ("a", 1) } ) }

Si consideramos la siguiente consulta:

{ t : {a} | t.a = t.a }

Entonces su resultado en db o es { (a : 1) } bajo S₁ ó { (a : 1), (a : 2) } bajo S₂. Es claro también que si tomamos el dominio como un conjunto infinito, entonces el resultado de la consulta será infinito. Para resolver esos problemas se consideran las consultas independiente del dominio, aquellas que retornan el mismo resultado para una base de datos bajo todos sus esquemas.

Consultas seguras

Con el fin de limitar las consultas de manera que expresen únicamente consultas independiente del dominio, una noción sintáctica de consulta segura es introducida. Para determinar si una consulta es segura is safe se derivan dos tipos de información de una consulta. La primera es si un par columna-variablet.a está acotado a la columna de una relación o una constante, y la segunda es si hay dos pares columna-variable que son directa o indirectamente equivalentes (denotado t.v == s.w).

Por derivar el acotamiento se introducen las siguientes reglas:

1. en "v.a = w.b" ningún par columna-variable está acotado,
2. en "v.a = k" el par columna-variable v.a está acotado,
3. en "r(v)" todos los pares v.a están acotados por a en tipo(v),
4. en "f₁ ∧ f₂" todos los pares están acotados de manera que están acotados o en f₁ o en f₂,
5. en "f₁ ∨ f₂" todos los pares están acotados de manera que están acotados ambos en f₁ y en f₂,
6. en "¬ f" ninguno de los pares está acotado,
7. en "∃ v: H (f)" un par w.a está acotado si está acotado en f y w <> v,
8. en "∀ v: H (f)" un par w.a está acotado si está acotado en f y w <> v.

Por derivar la equivalencia se introducen las siguientes reglas:

1. en "v.a = w.b" se mantiene que v.a == w.b,
2. en "v.a = k" ninguno de los pares son equivalentes,
3. en "r(v)" ninguno de los pares son equivalentes,
4. en "f₁ ∧ f₂" se mantiene que v.a == w.b si se mantiene o en f₁ o en f₂,
5. en "f₁ ∨ f₂" se mantiene que v.a == w.b si se mantiene en f₁ y en f₂,
6. en "¬ f" ninguno de los pares son equivalentes,
7. en "∃ v : H ( f )" se mantiene que w.a == x.b si se mantiene en f y w<>v y x<>v,
8. en "∀ v : H ( f )" se mantiene que w.a == x.b si se mantiene en f y w<>v y x<>v.

Entonces se dice que una consulta { v : H | f(v) } es segura si:

• para cada nombre de columna a en H podemos derivar que v.a es equivalente a un par acotado en f,
• para cada subexpresión de f de la forma "∀ w : G (g)" podemos derivar que para cada nombre de columna a en G podemos derivar que w.a es equivalente a un par acotado en g,
• para cada subexpresión de f de la forma "∃ w : G (g)" podemos derivar que para cada nombre de columna a en G podemos derivar que w.a es equivalente a un par acotado en g.

Sistemas

• DES – Una herramienta educativa con cálculo relacional de tuplas y otros lenguajes formales
• WinRDBI - Una herramienta educativa con cálculo relacional de tuplas y otros lenguajes formales

Bibliografía

• Edgar Frank Codd: A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, 13(6):377–387, 1970.

Véase también

• Álgebra relacional
• Cálculo relacional
• Cálculo relacional basado en dominio
• Modelo relacional
• Modelo entidad-relación
• SQL

•   Datos: Q1000462