VI3. una base de datos relacional
como una interpretación de un
lenguaje de primer orden.
VI3.1.otro enfoque de las bases de datos
relacionales
Ya disponemos de las
herramientas necesarias para efectuar la adaptación
del modelo relacional al
CPPO. La idea central es probar que una base de
datos puede ser
interrogada mediante fórmulas lógicas, fórmulas bien
formadas. Lo que a
continuación se va a exponer es otro punto de vista, otra
forma de “presentar” las
bases de datos relacionales.
Si para construir y
evaluar una FBF necesitamos una interpretación y un LPO,
para todo esquema de base
de datos relacional (BDR) y para cada estado de
base de datos tenemos que
asegurarnos que ambos, interpretación y
lenguaje, están bien
definidos.
De hecho, cuando
trabajamos con una BDR, cada operación provoca un
nuevo estado de base de
datos mientras que la estructura, el esquema de
base de datos permanece
inalterado. El LPO se basará en el esquema y cada
estado es una
interpretación distinta.
Por ejemplo, supongamos
una BDR muy simple, con una tabla de
departamentos y otra de
personas que trabajan en esos departamentos de tal
forma que un empleado
trabaja como máximo en un departamento y estos
pueden tener tantos
empleados como necesiten (relación uno a muchos). El
esquema de base de datos,
entre otras cosas, define los dominios en los que
los atributos toman
valores. Supongamos que todos los atributos son cadenas
de 20 caracteres. Todas
las combinaciones de caracteres en cadenas de 0 a
20 elementos son
susceptibles de ser almacenadas. Éste es nuestro universo
de discurso, el dominio, y
cada una de esas combinaciones tendrá su
correspondiente símbolo de
constante.
Por otro lado, necesitamos
predicados para poder determinar qué valores
“están” y qué valores “no
están” en la BD. Si cada tabla, departamento y
persona, se define como un
predicado, ya disponemos del LPO, ya podemos
escribir fórmulas.
Para trabajar normalmente
con la BD, esas fórmulas deben devolver un
resultado, deben poder
evaluarse, necesitamos una interpretación del LPO. Si
el esquema de BD es
estático, la información almacenada cambia
constantemente con las
inserciones, borrados y modificaciones. Por tanto,
una consulta que nos da un
resultado en un estado de la BD, podría darnos
otro en otra ocurrencia.
Como hemos visto, la
interpretación es la herramienta que rellena los
símbolos del LPO, da valor
a las constantes y a los símbolos de predicado. En
el caso de las constantes
es simplemente asegurarnos de que existe una
correspondencia entre el
símbolo y el valor del dominio. Volviendo a nuestra
pequeña base de datos las
constantes ya están definidas y son siempre las
mismas.
Los predicados son los que
van a definir, realmente, la ocurrencia de la base
de datos, los datos que
están almacenados en cada instante en las tablas. Si
BD1 2006-2007
110
suponemos que cada estado
de la BD define una interpretación, ya estamos
en disposición de evaluar
cualquier fórmula.
Insistimos en que,
simplemente, se trata de otro enfoque de una base de
datos relacional, lo que
antes llamábamos relación (tabla) ahora se llama
predicado, lo que antes
eran dominios ahora es universo de discurso... como
se muestra en las
equivalencias que se muestran a continuación.
dominios: universo del
discurso
valor de un dominio:
constante
relación: predicado
extensión de la relación:
extensión del predicado
atributos: argumentos de
predicado
consulta: FBF abierta
restricción de integridad:
FBF cerrada
estado de base de datos: interpretación
Ahora, en vez de utilizar
el modelo relacional para describir la BD, vamos usar
una interpretación de un
LPO:
Todo esquema de base de
datos relacional define un lenguaje de primer orden
y cada estado de base de
datos una interpretación.
Resumiendo, siempre
podemos utilizar el CPPO para describir e interrogar a
una base de datos
relacional. Se entiende que en cada estado de base de
datos disponemos de:
• universo del discurso
Sea D la unión de todos
los dominios que aparecen en el esquema
de BD.
• constantes
Por cada elemento de D, se
introduce un símbolo de constante y
nada más que uno. Para
simplificar, escogeremos como símbolos
de constante los símbolos
que denotan a los elementos de D; a
cada símbolo se le asigna
“su” elemento.28
• predicados
Por cada esquema de
relación de n atributos en el esquema de la
BD, se introduce un
símbolo de predicado de n argumentos. Para
simplificar, escogeremos
como símbolos de predicado los nombres
de las relaciones. A cada
símbolo se le asigna la extensión de “su”
relación.
En este alfabeto, por
simplicidad, no incluimos los símbolos de función29. Los
símbolos de variables se
asume que serán tantos como sean necesarios, y
las conectivas lógicas,
especiales y los cuantificadores son los mismos que
los definidos en el
apartado anterior. Así mismo, las FBF’s de este lenguaje se
construyen con las mismas
reglas que se han presentado en dicho apartado.
Puesto que disponemos en
todo momento de esa interpretación, podemos
construir fórmulas lógicas
y evaluarlas. Estas fórmulas pueden ser abiertas o
28 Es otra
vez la discusión del lenguaje de primer orden: desde un punto de vista formal,
una cosa
es el símbolo ‘1’ y otra
cosa el entero 1; una cosa es el símbolo ‘Pepe’ y otra el valor del dominio
de las cadenas de 10
caracteres Pepe. Tenemos conceptos y símbolos que representan a esos
conceptos. Nosotros, puesto
que utilizamos símbolos para comunicarnos, no somos conscientes
de esa asignación, la
asumimos el día en que “aprendimos a hablar”.
29 Aunque se
podrían utilizar si fuera necesario. Al igual que las constantes, son en cierto
modo
estáticas ya que tendrían
la misma definición en todos los estados de base de datos (en todas
las interpretaciones).
organización
física de las bases de datos
111
cerradas. Recordemos que
las restricciones de integridad son condiciones
que se desean de los
datos, un control de su almacenamiento. Se entiende
que integridad referencial
y de clave son mantenidas por los sistemas de
gestión de base de datos.
Pero también podemos desear introducir
restricciones de
existencia que el esquema no puede reflejar como, por
ejemplo, que los
departamentos han de tener al menos un empleado.
¿Cómo podemos estar
seguros de que nuestra BD, en un estado concreto, es
correcta, cumple con todas
las restricciones de integridad? Aquí es cuando
recuperamos el concepto de
modelo. Si la interpretación (el estado de la BD)
es modelo para el conjunto
de fórmulas cerradas con las que expresamos
esas restricciones, es que
los datos están correctamente almacenados.
VI3.2.un ejemplo
Partiendo del siguiente
esquema, vamos a ilustrar la formalización lógica de
una BDR, esto es, la
descripción de todos sus posibles estados. A partir de
esta descripción, y dada
la ocurrencia concreta, se propondrán fórmulas
abiertas y cerradas,
asumiendo que las primeras representan consultas que
han de devolver un
conjunto de tuplas, y las segundas un conjunto de
restricciones de
integridad.
Esquema
de la base de datos:
CONDUCTOR
( número : cadena(2), añoNac :
entero )
Clave Primaria: número
VEHÍCULO ( matrícula : cadena(9), marca : cadena(30), añoFab
: entero )
Clave Primaria: matrícula
CONDUCE ( conductor : cadena(2), vehículo : cadena(9) )
Clave Primaria: ( conductor, vehículo )
Clave Ajena: conductor → CONDUCTOR
Clave Ajena: vehículo → VEHÍCULO
Restricciones
de integridad:
R1: Los vehículos sólo pueden ser conducidos por conductores
(integridad
referencial de la relación CONDUCE respecto a la relación
CONDUCTOR).
R2: Los conductores sólo conducen vehículos” (I.R. de CONDUCE
respecto de
VEHÍCULO)
R3: Todo vehículo tiene al menos un conductor
Extensión
de las relaciones:
CONDUCE
conductor
vehículo
C1 A-0000-A
C2 A-0000-A
C1 A-2222-CB
C4 A-3333-CN
CONDUCTOR
VEHÍCULO
número
añoNac matrícula marca añoFab
C1 1950 A-0000-A SEAT 1980
C2 1950 A-1111-BM SEAT 1990
C3 1972 A-2222-CB
VOLKSWAGEN 1994
C4 1970 A-3333-CN AUDI 1995
BD1 2006-2007
112
Formalmente, un esquema
base de datos relacional y su ocurrencia se
describen, desde el punto
de vista del CPPO, como:
Sea L=(A, F) e I(D, K, H,
E), donde
• símbolos de constante:
C = { a : a es una
cadena(2) } ∪ { a : a
es una cadena(9) } ∪
{ a : a es una cadena(30)
} ∪ { a : a
es un entero }
• símbolos de predicados:
P = { CONDUCTOR( . , . ),
VEHÍCULO( . , . , . ), CONDUCE( . , . ) }
• dominio de la interpretación:
D = { a : a es una
cadena(2) } ∪ { a : a
es una cadena(9) } ∪
{ a : a es una cadena(30)
} ∪ { a : a
es un entero }
• Asignación a las
constantes:
K : C → D tal
que K = { (c, d) : c ∈ C y d ∈
D y c=d }30
• Asignación a los
predicados:
E(CONDUCTOR) =
Ext(CONDUCTOR)
E(VEHÍCULO) =
Ext(VEHÍCULO)
E(CONDUCE) = Ext(CONDUCE)
Se supone que todo posible
estado de base de datos se puede describir de
esta forma, por lo que en
todo momento podemos evaluar una fórmula escrita
en este LPO en esta
interpretación. Una BD así formalizada, puede
interrogarse con
naturalidad mediante fórmulas bien formadas del lenguaje
que tiene asociado de
manera que, el resultado de evaluar esas fórmulas en
la interpretación asociada
a esa base de datos proporciona la contestación a
la pregunta.
¿Qué conductores han
nacido en 1950?
F1 CONDUCTOR( x, 1950 )
x
C1
C2
¿Qué vehículos son
conducidos por el conductor número C2?
F2 CONDUCE(‘C2’, y)
y
A-0000-A
¿Qué conductores no
conducen ningún vehículo?
F3 ∃y
(CONDUCTOR(x, y) ∧
¬∃z (CONDUCE(x, z))
x
C3
30 Puesto que
c es un símbolo de constante y d es un valor del dominio, la expresión c=d
quiere
decir que “c se escribe
igual que d”
organización
física de las bases de datos
113
Por otra parte, como ya se
ha comentado, las restricciones de integridad
representan propiedades
semánticas que deben cumplirse para que la
ocurrencia de la base de
datos sea válida. Con la formalización que se ha
presentado, estas
restricciones de integridad pueden expresarse mediante un
conjunto de fórmulas cerradas
de modo que la interpretación asociada a la
base de datos debe ser
modelo de ese conjunto de fórmulas.
“los vehículos sólo pueden
ser conducidos por conductores”
F4 ∀x ∀y
(CONDUCE(x, y) →
∃z CONDUCTOR(x, z))
se evalúa a cierto
“Los conductores sólo
conducen vehículos”
F5 ∀y ∀x
(CONDUCE(x, y) →
∃z ∃t
VEHÍCULO(y, z, t))
cierto
“todo vehículo tiene al
menos un conductor”
F6 ∀x∀y∀z(VEHÍCULO(x,
y, z) → ∃t
CONDUCTOR(t, x))
falso
Si suponemos que F4, F5 y
F6 es el conjunto de fórmulas que representan
restricciones del sistema,
la interpretación no es modelo para este conjunto
de fórmulas, o lo que es
lo mismo, nuestra ocurrencia del esquema no es
consistente con las
restricciones explícitas del problema: la base de datos no
es correcta.
VI4. fórmulas seguras
Como se ha visto en el
apartado anterior, en una base de datos vista como
una interpretación de un
lenguaje de primer orden, las preguntas se expresan
mediante fórmulas
abiertas, y las restricciones de integridad se expresan con
fórmulas cerradas de ese
lenguaje.
Sin embargo nuestra base
de datos es un subconjunto de toda la información
que se puede llegar a
almacenar. Supongamos que tenemos una tabla de
clientes (con atributos
“D.N.I.” y “cuenta bancaria”): es obvio que sólo voy a
almacenar “mis clientes”
no “todos los posibles clientes”.
Supongamos también, que
todos “mis clientes” tienen cuenta bancaria (es
una restricción de
integridad de mi base de datos). El problema al construir
fórmulas en CPPO es que
estamos haciendo deducciones sobre todo el
universo de discurso.
Luego no es lo mismo decir que “todos mis clientes
tienen cuenta bancaria”
que “todos los clientes tienen cuenta bancaria”. En
este segundo caso, ¿cómo
puedo asegurarlo si no lo “conozco”, no está
almacenado en mi base de
datos?
Es más, expresiones como ¬CLIENTE(x, y) son correctas y tienen respuesta:
“clientes que no están en
la tabla CLIENTE” o “clientes desconocidos”. Pero
claro, clientes
desconocidos no son esas personas que aún no son mis
clientes, sino todas las
posibles combinaciones de “D.N.I.” y “cuenta
bancaria”, tanto si se
corresponden a personas reales como si no. No
olvidemos que CLIENTE es
un subconjunto del producto cartesiano de los
dominios de sus atributos:
todos los clientes son todas las tuplas de ese
producto cartesiano.
Aparte de que, en bases de
datos, no parece que haya ninguna justificación
para preguntas de este
tipo (la información que me interesa es la que está
almacenada; ¿para qué
necesito a los conductores que no “conozco”?), en el
BD1 2006-2007
114
peor de los casos, y
siempre a nivel teórico, los dominios son potencialmente
infinitos. Una pregunta
así, y no olvidemos que nuestra intención final es
trabajar con un ordenador
y un sistema de gestión de bases de datos, llevaría
a tener que apagar la máquina
ya que nunca pararía de mostrar todas las
infinitas tuplas de la
relación.
Por todo ello, es
necesario evitar tales expresiones, restringiendo el conjunto
de fórmulas permitido a un
subconjunto de F formado por aquellas fórmulas
que se denominan fórmulas
seguras. Podemos concretar el objetivo de usar
sólo fórmulas seguras para
interrogar a bases de datos relacionales en que
pretendemos preguntar
únicamente sobre información almacenada, evitar
expresiones que estén
afectadas por los datos que no están en mi base de
datos.
Antes de definir la
propiedad de seguridad de una fórmula es necesario
introducir el concepto de
dominio de una fórmula.
dominio
de una fórmula
Dada una fórmula G que
contiene los símbolos de predicado P1, P2, ..., Pk y
los símbolos de constante
a1, a2, ..., an, entonces el dominio de G, Dom(G), es
el siguiente conjunto:
Dom(G) = { K(a1), K(a2), ...,
K(an) } ∪
Ext(P1) ∪
Ext(P2) ∪
_____Ext(Pk)
El dominio de una fórmula,
dicho en otras palabras, es el conjunto de valores
que “maneja” la fórmula,
las extensiones de los predicados y las constantes
utilizados en la fórmula.
Ya que las relaciones
asociadas a cada símbolo de predicado son conjuntos
finitos, también Dom(G) lo
es.
fórmula
segura
Una fórmula G es segura
si, independientemente de la interpretación que se
esté considerando,
satisface las siguientes tres reglas:
• Si G tiene n
variables libres (x1, x2, ..., xn) y (a1, a2,
..., an) es una tupla tal
que al sustituir cada xi por ai la
fórmula que resulta es cierta, entonces
ai ∈ Dom(G).
• Para cada subfórmula de G de la
forma ∃x F, si a es un
valor tal que al
sustituir x por a en F la
fórmula se hace cierta, entonces a ∈ Dom(F).
• Para cada subfórmula de G de la
forma ∀x F, si a es un
valor tal que al
sustituir x por a en F la
fórmula se hace falsa31, entonces a ∈ Dom(F).
Intuitivamente, una
fórmula es segura si su evaluación depende sólo de las
extensiones de las
relaciones asociadas a los símbolos de predicado que en
ella aparecen (y de las
constantes utilizadas). Para entendernos, debemos
asegurarnos de que los
valores que hacen ciertas las fórmulas abiertas y las
cerradas por
cuantificadores existenciales, y los que hacen falsas las
cerradas por
cuantificadores universales, pertenecen a la base a la base de
31 ¿Porqué
para el cuantificador universal sólo miramos los valores que hacen falsa la
fórmula?
∀xF es igual a ¬∃x¬F
organización
física de las bases de datos
115
datos. De una manera un
poco menos formal, para que una fórmula G sea
segura debe cumplirse que:
• Los valores de variables
libres que no pertenecen al dominio de la
fórmula no hacen cierta la
fórmula.
• Los valores de variables
ligadas por cuantificadores existenciales que
no pertenecen al dominio
de la fórmula no hacen cierta la subfórmula
(el alcance del cuantificador).
• Los valores de variables
ligadas por cuantificadores universales que
no pertenecen al dominio
de la fórmula no hacen falsa la subfórmula
(el alcance del
cuantificador).
Por ejemplo, CLIENTE(x, y)
es una fórmula segura puesto que sólo nos va a
devolver valores
almacenados en la tabla CLIENTE, pero ¬CLIENTE(x,
y)
precisamente se hace
cierta para aquellos valores que no están en la tabla,
es una fórmula no segura.
Fórmulas seguras y no
seguras es una clasificación en fórmulas aplicables a
bases de datos
relacionales y fórmulas que no se deben utilizar. La definición
de fórmula segura es
independiente de la interpretación que se utilice. Es
evidente que una consulta
que es segura en un estado de una base de datos,
cuando cambie ese estado
(cuando insertamos datos nuevos, cuando
eliminamos, cuando
modificamos) debe seguir siendo segura. Como veremos
a continuación, sabremos
que una fórmula es segura o no sin necesidad de
utilizar valores
concretos, una fórmula si es segura, siempre lo será, sea cual
sea el contenido de mi
base de datos.
G1 ∀x ( P(x)
→ Q(x, y)
)
¿Es G1 una fórmula
segura?
La forma de proceder pasa
por verificar todas y cada una de
las variables, teniendo
en cuenta que si para una de ellas
llegamos a la conclusión
de que la fórmula no es segura, no
hace falta continuar con
el resto de las variables.
Para cada variable
primero hemos de establecer la fórmula
que vamos examinar, y
dependiendo de si es libre, ligada por
un cuantificador
existencial o ligada por un universal,
comprobar que cumple con
la definición de fórmula segura.
En este caso hay dos
variables, x e y:
Empecemos por la variable
y. Al ser libre, la fórmula a evaluar
es toda G1.
Los valores de y que
debemos comprobar son los que hacen
cierta la fórmula, todo
valor de y que haga cierta la fórmula
debe pertenecer al
dominio. G1 se hace cierta cuando son
ciertos P(x) y Q(x,y) o
cuando P(x) es falso32.
Si suponemos que la
extensión de P(.) no tiene tuplas
(representaría a una
tabla vacía), la fórmula G1 será cierta
valga lo que valga Q(x,
y). Concretamente, sería cierta para
valores de y que no
pertenecen al dominio de la fórmula, por
lo que la fórmula no es
segura33. Ya no haría falta comprobar
la variable x.
32 Véase la
tabla de verdad del operador implicación.
33 Nótese que
la definición de fórmula segura es muy restrictiva: esta fórmula sólo da
problemas
cuando la extensión de P(.)
está vacía, es decir, para ciertos estados de la base de datos no
BD1 2006-2007
116
En realidad, lo que
queremos constatar es que los valores que
no pertenecen al dominio
de la fórmula no la hacen cierta.
Simplificando, y por
entendernos, los valores no almacenados
en nuestra base de datos
no deberían aparecer en el
resultado de la consulta.
G2 ∀ x (Q(x,
y) → P(x) )
La fórmula no es segura
ya que cualquier valor de y que no
pertenezca a su dominio
hace falso Q(x,y), y la fórmula sería
cierta para todo x (de
dentro de y de fuera del dominio).
G3 ∀x ∀y
(CONDUCTOR(x, y) →
∃z CONDUCE(x, z))
variable
x: ligada por un cuantificador universal. La fórmula
a evaluar es toda G3.
Cualquier valor de x que
no pertenezca al dominio de la
fórmula hace falso
CONDUCTOR(x, y) y por tanto G3 cierta.
Cómo estos valores no la
hacen falsa, la fórmula puede ser
segura.
variable
y: la discusión es la misma que para la variable x.
variable
z: ligada por un cuantificador existencial. La fórmula
a evaluar es toda ∃z
CONDUCE(x, z).
Cualquier valor de z que
no pertenezca al dominio de la
fórmula hace falso ∃z
CONDUCE(x, z). Como los valores de
“fuera” del dominio no la
hacen cierta, la fórmula puede ser
segura.
Las tres variables de la
fórmula cumplen las reglas
respectivas; por lo
tanto, la fórmula es segura.
G4 ∀x ∀y
(CONDUCTOR(x, y) ∧
∃z CONDUCE(x, z))
variable x: ligada por un
cuantificador universal. La fórmula a
evaluar es toda G4.
Cualquier valor de x que
no pertenezca al dominio de la
fórmula hace falso
CONDUCTOR(x, y) y por tanto G3 falsa. La
fórmula no es segura.
devolvería valores
“incorrectos”: podríamos decir que utilizando fórmulas seguras “nos estamos
curando en salud”.
organización
física de las bases de datos
117
G5 ∃y
CONDUCTOR(x, y) ∧
¬∃z CONDUCE(x, z)
Esta fórmula abierta nos
devolvería aquellos conductores que
no conducen ningún
vehículo.
variable x: es la
variable libre. La fórmula a evaluar es toda
G5.
Cualquier valor de x que
no pertenezca al dominio de la
fórmula hace falso
CONDUCTOR(x, y) y por tanto G4 falsa.
Cómo estos valores no la
hacen cierta, la fórmula puede ser
segura.
variable y: ligada por un
cuantificador existencial. La fórmula a
evaluar es ∃y
CONDUCTOR(x, y).
Cualquier valor de y que
no pertenezca al dominio de la
fórmula hace falso
CONDUCTOR(x, y). Como los valores que
no pertenecen al dominio
no la hacen cierta, la fórmula puede
ser segura.
variable z: ligada por un
cuantificador existencial. La fórmula a
evaluar es ∃z
CONDUCE(x, z). Nótese que la negación no está
dentro del alcance del
cuantificador
Cualquier valor de z que
no pertenezca al dominio de la
fórmula hace falso
CONDUCE(x, z). Como los valores que no
pertenecen al dominio no
la hacen cierta, la fórmula puede ser
segura.
La fórmula es segura
puesto que ninguna variable incumple la
definición.
VI5. cálculo relacional
Ahora sabemos que una base
de datos relacional se puede describir
utilizando el CPPO. Eso
quiere decir, también, que la podemos consultar
usando fórmulas lógicas.
No obstante, el lenguaje y la interpretación antes
descritos pueden
“refinarse” y hacerlos un poco más útil para la aplicación
deseada, para las bases de
datos relacionales.
Se definieron dos
lenguajes de cálculo relacional: orientado a tuplas y
orientado
a dominios. La diferencia fundamental entre ambos reside en el
tipo de variables que
manejan. En el primero las variables se denominan
variables-tupla, y como
su nombre indica van a designar tuplas de relaciones.
En el segundo lenguaje las
variables se denominan variables-dominio, y van a
tomar valores de los
dominios asociados a los atributos de las relaciones.
Como ya se ha dicho, los
dos lenguajes están basados en el Cálculo de
Predicados de Primer Orden,
por lo que utilizaremos las definiciones del tema
anterior y las adaptaremos
a los nuevos tipos de variables, sin profundizar
más en dichas
definiciones.
BD1 2006-2007
118
VI5.1.cálculo relacional orientado a tuplas
Es necesario realizar unas
ligeras modificaciones a las definiciones
introducidas en el tema
anterior, para tener en cuenta el hecho de que las
variables de este lenguaje
son variables-tupla y, como ya se ha dicho,
designan tuplas de
relación.
Lo primero es definir cual
es el dominio de una variable de este lenguaje.
Anteriormente esto no ha
sido necesario porque habíamos supuesto una
lógica homogénea y, por
tanto, este dominio coincidía con el conjunto de
constantes del lenguaje.
La forma de realizar esta asignación es declarar la
variable. Cada
variable-tupla está definida sobre una intensión de una
relación R. Por
ejemplo:
R(a1 : dom1, a2 : dom2, ..., an : domn)
La declaración de la
variable-tupla sería de la forma:
x : R
Así, declarando las
variables sobre relaciones se especifica donde van a
tomar sus valores. En
nuestro ejemplo, la variable x tomará valores en el
producto cartesiano de
todos los dominios de R, dom1 × dom2 × ... × domn.
Aclarado este punto,
pasemos a ver cuales van a ser los diferentes objetos de
este lenguaje. Para
empezar, los símbolos de este lenguaje serán los mismos
que los vistos en el tema
anterior, con la única diferencia de que las variables
ahora son variables-tupla.
La construcción de
fórmulas bien formadas precisa, pues, de los conceptos
de término y fórmula
atómica.
término
Decimos que son términos
cualquiera de las dos expresiones siguientes:
• símbolos de constante
• s.A, donde s es una
variable-tupla y A es el nombre de un atributo de
la relación sobre la que
se declaró la variable
fórmula
atómica
Definimos formula
atómica o átomo como cualquier expresión del tipo:
• R(s), donde R es el nombre
de una relación y s es el nombre de una
variable-tupla que se
declaró sobre la relación R o sobre otra relación
compatible con R.
• t1 ⊗ t2, donde
t1 y t2 son dos términos y ⊗ es un operador de
comparación (<, >,
=, ...).
organización
física de las bases de datos
119
fórmulas
abiertas
En el caso de las fórmulas
abiertas añadimos una pequeña modificación de
tal forma que podemos
indicar qué atributos de las variables libres son los
que nos interesa obtener.
Es decir, podemos no necesitar las tuplas
completas, si no sólo
algunos de sus atributos, y lo especificamos así:
{ t1, t2, ..., tn | F }
Donde cada ti es un
término, y F una FBF en la que las únicas variables libres
son las que aparecen en
los ti.
ejemplos
“Matrícula y marca de los
vehículos”
x: VEHÍCULO
{ x.matricula, x.marca |
VEHÍCULO(x) }
“Matrícula y marca de los
vehículos de 2003”
x: VEHÍCULO
{ x.matricula, x.marca |
VEHÍCULO(x) ∧ x.añoFab=2003
}
“Matrícula y marca de los
vehículos de 2003 y número de los conductores
que los conducen”
x: VEHÍCULO y: CONDUCE
{ x.matricula, x.marca,
y.conductor | VEHÍCULO(x) ∧
x.añoFab=2003 ∧ CONDUCE(y)
∧ y.vehículo=x.matrícula
}
“Número de los conductores
que conducen vehículos de 2003”
x: VEHÍCULO y: CONDUCE
{ y.conductor |
CONDUCE(y) ∧ ∃x
(VEHÍCULO(x) ∧
y.vehículo=x.matrícula ∧ x.añoFab=2003)}
“Año de nacimiento de los
conductores que conducen vehículos de 2003”
x: VEHÍCULO y: CONDUCE z:
CONDUCTOR
{ z.añoNac | CONDUCTOR(z)
∧ ∃y
(CONDUCE(y) ∧
z.número=y.conductor ∧ ∃x
(VEHÍCULO(x) ∧
y.vehículo=x.matrícula ∧ x.añoFab=2003))
}
O de una forma más
concisa:
x: VEHÍCULO y: CONDUCE z:
CONDUCTOR
{ z.añoNac | CONDUCTOR(z)
∧ ∃y ∃x
(CONDUCE(y) ∧
VEHÍCULO(x) ∧ z.número=y.conductor
∧
y.vehículo=x.matrícula ∧ x.añoFab=2003)
}
“Todos los conductores
conducen al menos un vehículo”
BD1 2006-2007
120
y: CONDUCE z: CONDUCTOR
∀z (CONDUCTOR(z) → ∃y
(CONDUCE(y) ∧
z.número=y.conductor))
VI5.2.cálculo relacional orientado a dominios
Las expresiones del
cálculo relacional orientado a dominios se construyen
siguiendo unos principios
análogos al cálculo relacional basado en variablestupla.
Existen, sin embargo, un
pequeño número de diferencias, siendo la
principal precisamente el
concepto de variable. Las variables de este lenguaje
se denominan variables-dominio,
y toman valores de los dominios asociados
a los atributos de las
relaciones.
Análogamente, la
variable-dominio va a tomar valores en el dominio asociado
a alguno de los atributos
de una relación. Por ejemplo:
x : domk
De esta forma la variable x
tomará valores en el dominio domk.
Aclarado este punto,
veamos las adaptaciones del CPPO necesarias para
definir el lenguaje.
fórmula
atómica
Son fórmulas atómicas o
átomos las expresiones de la forma:
• R(a1 : t1, a2 : t2, ..., an : tn), donde R
es una relación de grado igual a n o
superior, a1, a2, ..., an son
atributos de R y t1, t2, ..., tn son
términos.
Los términos han de
pertenecer a los dominios asociados a los
atributos de la relación
• t1 ⊗ t2, donde t1 y t2 son dos
términos y ⊗ es un
operador de
comparación (<, >,
=, ...)
Al igual que en el cálculo
relacional orientado a tuplas, añadimos una
pequeña modificación en
las fórmulas abiertas indicando qué variables son
libres:
{ x1, x2, ..., xk | F }
Las únicas ocurrencias de
variable libres que aparecerán en F son x1, x2, ...,
xk; el
resto de ocurrencias serán ligadas. La evaluación de esta expresión
dará como resultado una
relación k-aria, de manera que al sustituir cada una
de las variables libres
por los valores de los atributos de una de las tuplas de
esta relación, da como
resultado una fórmula cerrada que se evalúa a cierto.
organización
física de las bases de datos
121
ejemplos
“Matrícula y marca de los
vehículos”
x: cadena(9) y:
cadena(30)
{ x, y |
VEHÍCULO(matrícula: x, marca: y) }
“Matrícula y marca de los
vehículos de 2003”
x: cadena(9) y:
cadena(30)
{ x, y |
VEHÍCULO(matrícula: x, marca: y, añoFab:2003) }
“Matrícula y marca de los
vehículos de 2003 y número de los conductores
que los conducen”
x: cadena(9) y:
cadena(30) z: cadena(2)
{ x, y, z |
VEHÍCULO(matrícula: x, marca: y, añoFab:2003) ∧
CONDUCE(conductor: z,
vehículo: x) }
“Número de los conductores
que conducen vehículos de 2003”
x: cadena(9) y:
cadena(30) z: cadena(2)
{ z | ∃x
(CONDUCE(conductor: z, vehículo: x) ∧
VEHÍCULO(matrícula: x,
añoFab:2003))}
“Año de nacimiento de los
conductores que conducen vehículos de 2003”
x: cadena(9) y:
cadena(30) z: cadena(2) t: entero
{ t | ∃z
(CONDUCTOR(número: z, añoNac: t) ∧
∃x (CONDUCE(conductor: z,
vehículo: x) ∧
VEHÍCULO(matrícula: x,
añoFab:2003)))}
“Todos los conductores
conducen al menos un vehículo”
x: cadena(9) z: cadena(2)
∀z (CONDUCTOR(número: z) →
∃x CONDUCE(conductor: z,
vehículo: x))
No hay comentarios:
Publicar un comentario