Cálculo relacional de tuplas

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Modelo relacional

cálculo de tuplas es un cálculo que fue creado e introducido por Edgar F. Codd como parte del modelo relacional, con el fin de proporcionar un lenguaje de consulta de base de datos declarativo para la manipulación de datos en este modelo de datos. Formó la inspiración para los lenguajes de consulta de base de datos QUEL y SQL, de los cuales el último, aunque mucho menos fiel al cálculo y modelo relacional original, es ahora el lenguaje de consulta de base de datos estándar de facto; casi todos los sistemas de gestión de bases de datos relacionales utilizan un dialecto de SQL. Michel Lacroix y Alain Pirotte propusieron el cálculo de dominio, que está más cerca de la lógica de primer orden y, junto con Codd, demostraron que ambos cálculos (así como el álgebra relacional) son equivalentes en poder expresivo. Posteriormente, los lenguajes de consulta para el modelo relacional se denominaron relacionalmente completos si podían expresar al menos todas estas consultas.

Definición del cálculo

Base de datos relacional

Dado que el cálculo es un lenguaje de consulta para bases de datos relacionales, primero tenemos que definir una base de datos relacional. El bloque de construcción relacional básico es el dominio (algo similar, pero no igual a un tipo de datos). Una tupla es una secuencia finita de atributos, que son pares ordenados de dominios y valores. Una relación es un conjunto de tuplas (compatibles). Aunque estos conceptos relacionales están definidos matemáticamente, esas definiciones se corresponden vagamente con los conceptos de bases de datos tradicionales. Una tabla es una representación visual aceptada de una relación; una tupla es similar al concepto de fila.

Primero asumimos la existencia de un conjunto C de nombres de columna, ejemplos de los cuales son "nombre", "autor", "dirección& #34;, etcétera. Definimos headers como subconjuntos finitos de C. Un esquema de base de datos relacional se define como una tupla S = (D, R, h) donde D es el dominio de los valores atómicos (consulte el modelo relacional para obtener más información sobre las nociones de dominio y valor atómico), R es un conjunto finito de nombres de relaciones, y

h: R → 2^C

una función que asocia un encabezado con cada nombre de relación en R. (Tenga en cuenta que esta es una simplificación del modelo relacional completo donde hay más de un dominio y un encabezado no es solo un conjunto de nombres de columna, sino que también asigna estos nombres de columna a un dominio). Dado un dominio D definimos una tupla sobre D como una función parcial que asigna algunos nombres de columna a un valor atómico en D. Un ejemplo sería (nombre: "Harry", edad: 25).

t: C ⇸ D

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

Finalmente definimos una base de datos relacional dado un esquema S = (D, R, h) como una función

db: R → 2^T_D

que asigna los nombres de las relaciones en R a subconjuntos finitos de T_D, de modo que para cada relación nombre r en R y tupla t en db(r) sostiene que

dom()t) h()r).

El último requisito simplemente dice que todas las tuplas en una relación deben contener los mismos nombres de columna, es decir, aquellos definidos para ella en el esquema.

Átomos

Para la construcción de las fórmulas supondremos un conjunto infinito V de tuplas variables. Las fórmulas se definen dado un esquema de base de datos S = (D, R, h) y una función parcial tipo: V ⇸ 2^C, llamado en asignación de tipo, que asigna encabezados a algunas variables de tupla. Luego definimos el conjunto de fórmulas atómicas A[S,tipo] con las siguientes reglas:

si v y w dentro V, a dentro Tipo()v) y b dentro Tipo()wEntonces la fórmula v.a = w.b está dentro A[S,Tipo]
si v dentro V, a dentro Tipo()v) y k denota un valor en D entonces la fórmula v.a = k está dentro A[S,Tipo], y
si v dentro V, r dentro R y Tipo()v) h()rEntonces la fórmula r()v) está en A[S,Tipo].

Ejemplos de átomos son:

()t.age = s.age) — t tiene un atributo de edad y s tiene un atributo de edad con el mismo valor
()t.name = "Codd") — tuple t tiene un atributo de nombre y su valor es "Codd"
Libro(t. t está presente en relación Libro.

La semántica formal de dichos átomos se define dada una base de datos db sobre S y una variable de tupla que vincula val: V → T_D que asigna variables de tupla a tuplas sobre el dominio en S:

v.a = w.b es verdad si y sólo si val()v)a) val()w)b)
v.a = k es verdad si y sólo si val()v)a) k
r()v) es verdad si y sólo si val()v) está en db()r)

Fórmulas

Los átomos se pueden combinar en fórmulas, como es habitual en la lógica de primer orden, con los operadores lógicos ∧ (y), ∨ (o) y ¬ (no), y podemos usar el cuantificador existencial (∃) y el cuantificador universal (∀) para vincular las variables. Definimos el conjunto de fórmulas F[S,tipo] inductivamente con las siguientes reglas:

cada átomo en A[S,Tipo] también está en F[S,Tipo]
si f₁ y f₂ están dentro F[S,TipoEntonces la fórmula f₁ ∧ f₂ también está F[S,Tipo]
si f₁ y f₂ están dentro F[S,TipoEntonces la fórmula f₁ Alternativa f₂ también está F[S,Tipo]
si f está dentro F[S,TipoEntonces la fórmula f también está F[S,Tipo]
si v dentro V, H un encabezado y f una fórmula en F[S,Tipo_[v-H]Entonces la fórmula v: H ()f) también está en F[S,Tipo], donde Tipo_[v-H] denota la función que es igual a Tipo excepto que mapas v a H,
si v dentro V, H un encabezado y f una fórmula en F[S,Tipo_[v-H]Entonces la fórmula v: H ()f) también está en F[S,Tipo]

Ejemplos de fórmulas:

t.name = "C. J. Date" t.name = "H. Darwen"
Libro(t) ∨ Revistat)
О t[autor, título, tema] (Libro(t∧ t.author = "C. J. Date"t.subject = "modelo relacional")

Tenga en cuenta que la última fórmula establece que todos los libros escritos por C. J. Date tienen como tema el modelo relacional. Como de costumbre, omitimos los corchetes si esto no causa ambigüedad sobre la semántica de la fórmula.

Supondremos que los cuantificadores cuantifican sobre el universo de todas las tuplas sobre el dominio en el esquema. Esto conduce a la siguiente semántica formal para fórmulas dada una base de datos db sobre S y una variable de tupla que vincula val: V -> T_D:

f₁ ∧ f₂ es verdad si y sólo si f₁ es verdad y f₂ es verdad,
f₁ Alternativa f₂ es verdad si y sólo si f₁ es verdad o f₂ es cierto o ambos son verdaderos,
¬ f es verdad si y sólo si f no es verdad,
∃ v: H ()f) es verdad si y sólo si hay un tuple t sobre D tales que dom()t) H y la fórmula f es verdad val_[v-t], y
О v: H ()f) es verdad si y sólo si para todos los tuples t sobre D tales que dom()t) H la fórmula f es verdad val_[v-t].

Consultas

Finalmente, definimos cómo se ve una expresión de consulta dado un esquema S = (D, R, h):

{} v: H Silencio f()v)

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

Ejemplos de expresiones de consulta son:

{} t################################################################################################################################################################################################################################################################ s######################name, wage}(Employee(#s∧ s.wage = 50.000 ∧ t.name = s.name) }
{} t: {supplier, article} Silencio s- ¿Qué?s∧ s.sname = t.supplier ∧ ∃ p: {p#, pname} (Producto(p∧ p.pname = t.article ∧ ∃ a(Suplica)a∧ s.s# = a.s# ∧ a.p# = p.p#)

Restricción semántica y sintáctica del cálculo

Consultas independientes del dominio

Debido a que la semántica de los cuantificadores es tal que cuantifican sobre todas las tuplas sobre el dominio en el esquema, puede ser que una consulta arroje un resultado diferente para una determinada base de datos si se supone otro esquema. Por ejemplo, considere 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 encabezados h = { ("r₁", {"a"}) }. Ambos esquemas tienen una instancia común:

db ################################################################################################################################################################################################################################################################₁", { ("a", 1)

Si consideramos la siguiente expresión de consulta

{} t# Silencio t.a = t.a }

entonces su resultado en db es { (a: 1) } bajo S₁ o { (a: 1), (a: 2) } debajo de S₂. También quedará claro que si tomamos el dominio como un conjunto infinito, entonces el resultado de la consulta también será infinito. Para resolver estos problemas restringiremos nuestra atención a aquellas consultas que son independientes del dominio, es decir, las consultas que devuelven el mismo resultado para una base de datos bajo todos sus esquemas.

Una propiedad interesante de estas consultas es que si asumimos que las variables de tupla oscilan entre tuplas sobre el llamado dominio activo de la base de datos, que es el subconjunto del dominio que ocurre en menos una tupla en la base de datos o en la expresión de consulta, la semántica de las expresiones de consulta no cambia. De hecho, en muchas definiciones del cálculo de tuplas, así es como se define la semántica de los cuantificadores, lo que hace que todas las consultas sean, por definición, independientes del dominio.

Consultas seguras

Para limitar las expresiones de consulta de modo que expresen solo consultas independientes del dominio, se suele introducir una noción sintáctica de consulta segura. Para determinar si una expresión de consulta es segura, derivaremos dos tipos de información de una consulta. El primero es si un par variable-columna t.a está vinculado a la columna de una relación o una constante, y el segundo es si dos pares de columnas de variables se equiparan directa o indirectamente (denotados t.v == s.w).

Para derivar la acotación, presentamos las siguientes reglas de razonamiento:

en " v.a = w.b " ningún par de columna variable está atado,
en " v.a = k "el par de columna variable v.a está atado,
en " r()v"todos pares v.a están obligados a dentro Tipo()v),
en " f₁ ∧ f₂ "todos los pares están atados que están atados en f₁ o dentro f₂,
en " f₁ Alternativa f₂ "todos los pares están atados que están atados ambos en f₁ y dentro f₂,
en " f "no hay pares atados,
en " v: H ()f"un par w.a está atado si está atado f y w ■ v, y
en " v: H ()f"un par w.a está atado si está atado f y w ■ v.

Para derivar la equiparación introducimos las siguientes reglas de razonamiento (junto a las reglas de razonamiento habituales para las relaciones de equivalencia: reflexividad, simetría y transitividad):

en " v.a = w.b "tiene que v.a == w.b,
en " v.a = k "no hay pares equiparados,
en " r()v"No hay pares equiparados,
en " f₁ ∧ f₂ "tiene que v.a == w.b si se mantiene dentro f₁ o dentro f₂,
en " f₁ Alternativa f₂ "tiene que v.a == w.b si se mantiene en ambos f₁ y dentro f₂,
en " f "no hay pares equiparados,
en " v: H ()f"tiene que w.a == x.b si se mantiene en f y w■v y x■v, y
en " v: H ()f"tiene que w.a == x.b si se mantiene en f y w■v y x■v.

Entonces decimos que una expresión de consulta { v: H | f(v) } es seguro si

para cada nombre de columna a dentro H podemos derivar que v.a es equiparado con un par atado en f,
para cada subexpresión de f de la forma " w: G ()g) " podemos derivar eso por cada nombre de columna a dentro G podemos derivar que w.a es equiparado con un par atado en g, y
para cada subexpresión de f de la forma " w: G ()g) " podemos derivar eso por cada nombre de columna a dentro G podemos derivar que w.a es equiparado con un par atado en g.

La restricción a las expresiones de consulta seguras no limita la expresividad, ya que todas las consultas independientes del dominio que podrían expresarse también pueden expresarse mediante una expresión de consulta segura. Esto se puede probar mostrando que para un esquema S = (D, R, h), un dado establecer K de constantes en la expresión de consulta, una variable de tupla v y un encabezado H podemos construir una fórmula segura para cada par v.a con a en H que indica que su valor está en el dominio activo. Por ejemplo, suponga que K={1,2}, R={"r"} y h = { ("r", {"a, "b"}) } entonces la fórmula segura correspondiente para v.b es:

v.b = 1 v.b = 2 ∨ w (r(w) ∧ (v.b = w.a Alternativa v.b = wb)

Esta fórmula, entonces, se puede usar para reescribir cualquier expresión de consulta no segura a una expresión de consulta segura equivalente agregando dicha fórmula para cada variable v y nombre de columna a en su tipo donde se usa en la expresión. Efectivamente, esto significa que dejamos que todas las variables oscilen sobre el dominio activo, lo que, como ya se explicó, no cambia la semántica si la consulta expresada es independiente del dominio.

Sistemas

DES – Una herramienta educativa para trabajar con el cálculo relacional Tuple y otros idiomas formales
WinRDBI – Una herramienta educativa para trabajar con el cálculo de Relación Tuple y otros idiomas formales

Contenido relacionado

Más resultados...