Cálculo relacional de tuplas

Dado que el cálculo es un lenguaje de consulta para bases de datos relacionales , primero debemos definir una base de datos relacional. El elemento básico de una base de datos relacional es el dominio (similar, pero no idéntico, a un tipo de dato ). 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). Si bien estos conceptos relacionales se definen matemáticamente, dichas definiciones se corresponden vagamente con los conceptos tradicionales de bases de datos. 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 columnas, ejemplos de los cuales son "nombre", "autor", "dirección", etcétera. Definimos los encabezados 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 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 esto 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 cual se define una tupla t se llama 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 tal manera que para cada nombre de relación r en R y tupla t en db ( r ) se cumple que

dom ( t ) = h ( r ).

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

Para la construcción de las fórmulas asumiremos un conjunto infinito V de variables de tupla. Las fórmulas se definen dado un esquema de base de datos S = ( D , R , h ) y un tipo  de función parcial : V ⇸ 2 ^C , llamado en la 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:

1. si v y w 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 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 ], y
3. si v 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 .age = s .age) — t tiene un atributo de edad y s tiene un atributo de edad con el mismo valor.
• ( t .name = "Codd") — la tupla t tiene un atributo name y su valor es "Codd"
• Libro( t ) — la tupla t está presente en la relación Libro.

La semántica formal de tales átomos se define dado una base de datos db sobre S y una vinculación de variables de tupla val  : V → T _D que asigna variables de tupla a tuplas sobre el dominio en S :

1. v . a = w . b es verdadero si y solo si val ( v )( a ) = val ( w )( b )
2. v . a = k es verdadero si y solo si val ( v )( a ) = k
3. r ( v ) es verdadero si y solo si val ( v ) está en db ( r )

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:

1. cada átomo en A [ S , tipo ] también está en F [ S , tipo ]
2. Si F ₁ y F ₂ están en F [ S , tipo ] entonces la fórmula F ₁ ∧ F ₂ también está en F [ S , tipo ]
3. Si F ₁ y F ₂ están en F [ S , tipo ] entonces la fórmula F ₁ ∨ F ₂ también está en F [ S , tipo ]
4. Si F está en F [ S , tipo ] entonces la fórmula ⁠${\displaystyle \neg F}$⁠ también está en F [ S , tipo ]
5. Si v está en V , H es un encabezado y F es una fórmula en F [ S , tipo _{[ v → H ]} ] entonces la fórmula ⁠${\displaystyle \exists 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 mapea v a H ,
6. Si v está en V , H es un encabezado y F es una fórmula en F [ S , tipo _{[ v → H ]} ] entonces la fórmula ⁠${\displaystyle \forall v:H(f)}$⁠ también está en F [ S , tipo ]

Ejemplos de fórmulas:

• t.name = "CJ Date" ∨ t.name = "H. Darwen"
• Libro( t ) ∨ Revista( t )
• ${\displaystyle \forall t:\{{\text{autor, título, tema}}\}(\neg ({\text{Libro}}(t)\wedge t{\text{.autor}}=}$" Fecha del juez judicial "${\displaystyle \wedge \ \neg (t{\text{.subject}}=}$" modelo relacional "${\displaystyle )))}$

Nótese que la última fórmula indica que todos los libros escritos por CJ Date tienen como tema el modelo relacional. Como es habitual, omitimos los paréntesis si esto no genera ambigüedad en 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 vinculación de variables 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 verdadera si y solo si F ₁ es verdadera o F ₂ es verdadera o ambas son verdaderas,
3. ⁠${\displaystyle \neg f}$es verdadero si y solo si F no es verdadero,
4. ⁠${\displaystyle \exists v:H(f)}$es verdadero si y solo si existe una tupla t sobre D tal que dom ( t ) = H y la fórmula F es verdadera para val _{[ v → t ]} , y
5. ⁠${\displaystyle \forall 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 ]} .

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

{ v  : H | f ( v ) }

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

Ejemplos de expresiones de consulta son:

Debido a que la semántica de los cuantificadores es tal que cuantifican sobre todas las tuplas del dominio en el esquema, puede ocurrir que una consulta devuelva un resultado diferente para una base de datos determinada si se presupone otro esquema. Por ejemplo, consideremos 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 = { ( r ₁ , { ( a , 1) } ) }

Si consideramos la siguiente expresión de consulta

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

Entonces, su resultado en la base de datos es { (a  : 1) } bajo S ₁ o { (a  : 1), (a  : 2) } bajo S _2. También será evidente que si consideramos el dominio como un conjunto infinito, el resultado de la consulta también será infinito. Para resolver estos problemas, limitaremos 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 abarcan tuplas del llamado dominio activo de la base de datos (el subconjunto del dominio que aparece en al menos una tupla de 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.

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. La primera es si un par variable-columna t . a está vinculado a la columna de una relación o una constante, y la segunda es si dos pares variable-columna están directa o indirectamente igualados (denotado t . v == s . w ).

For deriving boundedness we introduce the following reasoning rules:

1. in v.a = w.b no variable-column pair is bound,
2. in v.a = k the variable-column pair v.a is bound,
3. in r(v) all pairs v.a are bound for a in type(v),
4. in f₁ ∧ f₂ all pairs are bound that are bound either in f₁ or in f₂,
5. in f₁ ∨ f₂ all pairs are bound that are bound both in f₁ and in f₂,
6. in ⁠${\displaystyle \neg f}$⁠ no pairs are bound,
7. in ⁠${\displaystyle \exists v:H(f)}$⁠ a pair w.a is bound if it is bound in f and w≠v, and
8. in ⁠${\displaystyle \forall v:H(f)}$⁠ a pair w.a is bound if it is bound in f and w≠v.

For deriving equatedness we introduce the following reasoning rules (next to the usual reasoning rules for equivalence relations: reflexivity, symmetry and transitivity):

1. in v.a = w.b it holds that v.a is equal to w.b,
2. in v.a = k no pairs are equated,
3. in r(v) no pairs are equated,
4. in f₁ ∧ f₂ it holds that v.a is equal to w.b if it holds either in f₁ or in f₂,
5. in f₁ ∨ f₂ it holds that v.a is equal to w.b if it holds both in f₁ and in f₂,
6. in ⁠${\displaystyle \neg f}$⁠ no pairs are equated,
7. in ⁠${\displaystyle \exists v:H(f)}$Se cumple que w . a es igual a x . b si se cumple en f y w ≠ v y x ≠ v , y
8. en​${\displaystyle \forall v:H(f)}$Se cumple que w . a es igual a x . b si se cumple en f y w ≠ v y x ≠ v .

Entonces decimos que una expresión de consulta${\displaystyle \{v:H\mid f(v)\}}$es seguro si​

• para cada nombre de columna a en H podemos derivar que v . a se iguala con un par ligado en f ,
• para cada subexpresión de f de la forma ⁠${\displaystyle \forall w:G(g)}$Podemos derivar que para cada nombre de columna a en G podemos derivar que w . a se iguala con un par ligado en g , y
• para cada subexpresión de f de la forma ⁠${\displaystyle \exists w:G(g)}$Podemos derivar que para cada nombre de columna a en G podemos derivar que w . a se iguala con un par ligado en g .

La restricción a 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 demostrar mostrando que para un esquema S = ( D , R , h ), un conjunto dado 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 indique que su valor está en el dominio activo. Por ejemplo, supongamos que K ={1,2}, R ={"r"} y h = { ("r", {"a, "b"}) } entonces la fórmula segura correspondiente para v .b es:

${\displaystyle v{\text{.b}}=1\vee v{\text{.b}}=2\vee \exists w(r(w)\wedge (v{\text{.b}}=w{\text{.a}}\vee v{\text{.b}}=w{\text{.b}}))}$

Esta fórmula, por lo tanto, puede utilizarse para reescribir cualquier expresión de consulta insegura en una expresión de consulta segura equivalente, añadiendo dicha fórmula a cada variable v y nombre de columna a en su tipo donde se utilice en la expresión. En la práctica, esto significa que permitimos que todas las variables varíen en el dominio activo, lo cual, como ya se explicó, no cambia la semántica si la consulta expresada es independiente del dominio.