DERIVABILIDAD, REDUNDANCIA Y CONSISTENCIA DE RELACIONES

DERIVABILIDAD, REDUNDANCIA Y CONSISTENCIA DE RELACIONES

ALMACENADOS EN GRANDES BANCOS DE DATOS

E. F. Codd Research Division San José, California

RESUMEN: Los grandes bancos de datos integrados del futuro contendrán muchas relaciones de varios grados en forma almacenada. No será inusual que este conjunto de relaciones almacenadas sea redundante. Se definen y discuten dos tipos de redundancia. Se puede emplear un tipo para mejorar la accesibilidad de ciertos tipos de información que resultan tener una gran demanda. Cuando existe cualquier tipo de redundancia, los responsables del control del banco de datos deben conocerlo y tener algún medio para detectar cualquier inconsistencia "lógica" en el conjunto total de relaciones almacenadas. La verificación de coherencia puede ser útil para rastrear cambios no autorizados (y posiblemente fraudulentos) en el contenido del banco de datos.RJ 599(# 12343) Agosto 19, 1969

AVISO DE DISTRIBUCIÓN LIMITADA: este informe se ha enviado para su publicación en otro lugar y se ha emitido como un informe de investigación para la difusión temprana de su contenido. Como cortesía para el editor previsto, no debe distribuirse ampliamente hasta después de la fecha de publicación externa.

Se pueden solicitar copias en IBM Thomas J. Watson Research Center, Post Office Box 218, Yorktown Heights, Nueva York 10598

CONTENIDO

1. Una visión relacional de los datos 2. Algunos aspectos lingüísticos 3. Operaciones en las relaciones

3.1 Permutación 3.2 Proyección 3.3 Unir

3.4 Composición 4. Relaciones expresables, nombradas y almacenadas 5. Derivabilidad, redundancia y consistencia 6. Control del banco de datos

Wooouuu

INTRODUCCIÓN

La primera parte de este artículo se ocupa de una explicación de una visión relacional de los datos. Esta vista (o modelo) de datos parece ser superior en varios aspectos al modelo gráfico o de red (1, 2) actualmente en boga. Proporciona un medio para describir datos con su estructura natural únicamente: es decir, sin superponer ninguna estructura adicional para fines de representación de la máquina. En consecuencia, proporciona una base para un lenguaje de recuperación de alto nivel que producirá la máxima independencia entre los programas, por un lado, y la presentación y organización de la máquina de datos, por el otro. Una ventaja adicional de la visión relacional es que forma una base sólida para tratar la derivabilidad, la redundancia y la consistencia de las relaciones, que se analizan en la segunda parte de este artículo. El modelo de red, por otro lado, ha generado una serie de confusiones, entre las cuales la la derivación de conexiones para la derivación de relaciones Finalmente, la visión relacional permite una evaluación más clara del alcance y las limitaciones lógicas del presente sistema de información de gestión. temas, y también los méritos relativos (desde un punto de vista lógico) de las representaciones de datos en competencia dentro de un solo sistema.

1. Una visión relacional de los datos

El término relación se utiliza aquí en su sentido matemático aceptado. Dados los conjuntos S, S2, ..., S, (no necesariamente distintos), R es una relación en estos n conjuntos si es un conjunto de n-tuplas, cada uno de los cuales tiene su primer elemento de Suits segundo elemento de Sy, y así. Nos referiremos a S. como el i-ésimo dominio de R. Como se definió anteriormente, se dice que R tiene el grado n. Las relaciones de grado 1 a menudo se denominan unarias, grado 2 binarias, grado 3 ternarias y grado n n-arias.

Por razones expositivas, usaremos frecuentemente una representación de arreglo de relaciones, pero debe recordarse que esta representación particular no es una parte esencial de la visión relacional que se expone. Una matriz que representa una relación n-aria R tiene las siguientes propiedades:

(1) Cada fila representa una n-tupla de R; (2) El orden de las filas es irrelevante; (3) Todas las filas son distintas; (4) El orden de las columnas es significativo:

corresponde al pedido S., Sy, ... SK

de los dominios en los que se define R; (5) El significado de cada columna es parcialmente

transmitido etiquetándolo con el nombre del dominio correspondiente.

El ejemplo de la Figura 1 ilustra una relación de grado 4 denominada buque que refleja los envíos en curso de piezas de proveedores específicos a proyectos específicos en cantidades específicas.

barco (cantidad de proyecto de pieza de proveedor)

1

2 5

17 1 3 5 23

379

ANN

11 12

FIGURA 1: Una relación del grado 4

Uno podría preguntarse: si las columnas están etiquetadas por el nombre de los dominios correspondientes, ¿por qué debería importar el orden de las columnas? Como muestra el ejemplo de la Figura 2, dos columnas pueden tener encabezados idénticos (que indican dominios idénticos), pero poseer significados distintos con respecto a la relación. La relación representada es

llamado componente. Es una relación binaria, cada uno de cuyos dos dominios se llama parte. El significado de componente (x, y) es que la parte x es un componente inmediato (o subensamblaje) de la parte y.

componente (parte parte)

1 5 2 5

3 5. 26 36

Figura 2: Una relación con dos dominios idénticos

00

Ahora afirmamos que un banco de datos es una colección de relaciones que varían en el tiempo. Estas relaciones son de diversos grados. A medida que avanza el tiempo, cada relación n-aria puede estar sujeta a la inserción de n-tuplas adicionales, la eliminación de las existentes y la alteración de componentes de cualquiera de sus n-tuplas existentes.

Considere, por ejemplo, un banco de datos que contiene información sobre piezas, proyectos y proveedores. La descripción individual de un objeto individual (como una parte en particular) se denomina entidad (3). La descripción del prototipo de una clase de objetos se denomina tipo de entidad. El conjunto de entidades de un tipo de entidad determinado puede verse como un relación, y llamaremos a dicha relación una relación de tipo de entidad. En el ejemplo en consideración, podría haber una relación de tipo de entidad llamada parte cefinida en el

siguientes dominios:

(1) número de pieza (2) nombre de pieza (3) color de pieza (4) peso de pieza (5) cantidad disponible (6) cantidad solicitada

y posiblemente también otros dominios. Cada uno de estos dominios es, en efecto, un conjunto de valores, algunos o todos pueden estar representados en el banco de datos en cualquier momento. Si bien es posible que, en algún momento, estén presentes todos los colores de las piezas, es poco probable que lo estén todos los pesos, nombres y números de piezas posibles. Los dominios enumerados anteriormente corresponden a lo que comúnmente se denominan atributos de la parte del tipo de entidad.

Normalmente, un atributo (o combinación de atributos) de un tipo de entidad dado tiene valores que identifican de forma única a cada entidad. Tal atributo (o combinación) se llama clave. En el ejemplo anterior, el número de pieza sería una clave, mientras que el color de la pieza no lo sería. Una clave no es redundante si es un atributo simple (no una combinación) o una combinación tal que ninguno de los atributos participantes sea superfluo para identificar de forma única cada entidad. Un tipo de entidad puede poseer más de una clave no redundante. Este sería el caso en el ejemplo, si diferentes partes siempre tuvieran nombres distintos.

Las relaciones restantes en un banco de datos son entre tipos de entidad y, por lo tanto, se denominan relaciones entre entidades. Una propiedad esencial de toda relación entre entidades es que sus dominios incluyen al menos dos claves que se refieren a tipos de entidad distintos o se refieren a un tipo de entidad común que cumple funciones distintas.

Los ejemplos de las Figuras 1 y 2 ayudarán a aclarar esto. La relación que se muestra en la Figura 1 involucra tres claves, una para cada uno de los tipos de entidad proveedor, parte, proyecto. La relación que se muestra en la Figura 2 involucra dos claves que se refieren a la parte del tipo de entidad común, la primera clave sirve para identificar un componente, la segunda para identificar un conjunto que contiene ese componente. Ambas relaciones son relaciones entre entidades.

Hasta ahora, hemos discutido ejemplos de relaciones que se definen en dominios simples, dominios cuyos elementos son valores atómicos (no descomponibles). Los valores no atómicos se pueden discutir dentro del marco relacional. Por tanto, algunos dominios pueden tener relaciones como elementos. Estas relaciones pueden, a su vez, definirse en dominios no simples, y así sucesivamente. Por ejemplo, uno de los dominios en los que se define el tipo de entidad relación empleado podría ser el historial de salarios. Un elemento del dominio del historial salarial es un binario

relación definida en la fecha del dominio y el salario del dominio. El dominio del historial salarial es el conjunto de todas esas relaciones binarias.

2. Algunos aspectos lingüísticos

La adopción de una visión relacional de los datos, como se describió anteriormente, permite el desarrollo de un sublenguaje de recuperación universal basado en el cálculo de predicados de segundo orden. * Tal lenguaje proporcionaría un criterio de poder lingüístico para todos los demás lenguajes de recuperación propuestos, y sería ser en sí mismo un fuerte candidato para incrustar (con la modificación sintáctica adecuada) en una variedad de lenguajes host (programación, comandos o orientados a problemas).

...