- I - TESIS CARACTERIZACIÓN MATEMÁTICA DE LAS ¡{ASES DE...
151
- I - TESIS CARACTERIZACIÓN MATEMÁTICA DE LAS ¡{ASES DE DATOS RELACIÓNALES A ¡'W'riR DE LOS AXIOMAS DE ARMSTROMG: UNA APROXIMACIÓN DESDE EL i .INTO DE VISTA ANALÍTICO. Por MARÍA COVADONGA FERNANDEZ BAIZAN Ingeniero Superior de Telecomunicación Presentada en la FACULTAD DE INFORMÁTICA de la UNIVERSIDAD POTECNICA DE MADRID Para la obtención del ORADO DE DOCTOR EN INF T- l Madrid, Septiembre de 1.981
Transcript of - I - TESIS CARACTERIZACIÓN MATEMÁTICA DE LAS ¡{ASES DE...
- I -
T E S I S
CARACTERIZACIÓN MATEMÁTICA DE LAS ¡{ASES DE DATOS RELACIÓNALES
A ¡'W'riR DE LOS AXIOMAS DE ARMSTROMG: UNA APROXIMACIÓN DESDE
EL i .INTO DE VISTA ANALÍTICO.
Por
MARÍA COVADONGA FERNANDEZ BAIZAN
Ingeniero Superior de Telecomunicación
Presentada en la
FACULTAD DE INFORMÁTICA
de la
UNIVERSIDAD POTECNICA DE MADRID
Para la obtención del
ORADO DE DOCTOR EN INF
T- l
Madrid, Septiembre de 1.981
- II -
T E S I S D O C T O R A L
CARACTERIZACIÓN MATEMÁTICA DE LAS BASES DE DATOS RELACIÓNALES
A PARTIR DE LOS AXIOMAS DE ARMSTRONG: UNA APROXIMACIÓN DESDE
EL PUNTO DE VISTA ANALÍTICO.
Por: D- María Covadonga Fernández Baizán
Director de Tesis: D. Rafael PORTAENCASA BAEZA
LB_LLy_!LA_L_9-LLLLl-C_A_L9_R.
Presidente :
Vocales :
Madrid, de Septiembre de 1.981
- III -
PLANTEAMIENTO Y RESUMEN DE LA TESIS
El contenido de este trabajo se inscribe dentro del campo de
las Bases de Datos, más concretamente, de las Bases de Datos Relacióna
les, para las que los resultados obtenidos son de inmediata aplicación.
El so.ftwarede gestión de una Base de Datos Relaciona!, debe
ría incluir un modo de conocer el grado de normalización de una relación,
ya que, del manejo de relaciones no normalizadas, pueden derivarse cier
tas inconsistencias (son las denominadas anomalías de inserción, borrado
y actualización). Nuestro objetivo es proporcionar un fundamento matemá
tico para tales técnicas.
El método utilizado, parte de las dependencias funcionales -
definidas en el esquema inicial, calculando todas las claves. Esta dete£
minación, unida a un estudio en detalle de las propiedades matemáticas -
de las Formas Normales, y a la caracterización de los atributos principa_
les y no principales; permite la elaboración de dos sencillos Algoritmos,
que,aplicados a una relación, producen como resultado su nivel de norma
lización.
- IV -
ABSTRACT
The matter dealt with in this paper belongs to the Data Bases
field or, more specifically, to Relational Data Bases; results obtained
are therefore suitable for being appied directly.
A relational Data Bases management software should include so_
me way knowing the standardizaron degree of a relation because the use
of non-standarized relations may entail inconsistencies (called ente-
ring, erasing and bringing up to date anomalies). Our purpose in to -
fing a mathematica! basis for such techniques.
The method employed starts from functional dependencies shown
in the initial diagram, all the code groups being calculated. This dete£
niination together with a detailed examination of the mathematical proper_
ties of standard forms and with the identification of the chief and less
important inherent characteristics, allows to work out two simple Algo--
rithms that when applied to a relation show its standardization level.
- V -
AGRADECIMIENTOS
Deseo expresar en primer lugar mi gratitud al Profesor D. Ra_
fael Portaencasa Baeza, director de la Tesis, por la valiosa ayuda, con
sejo y orientación que en todo momento me ha prestado a los largo de su
realización.
El desarrollo de este trabajo no habría sido posible sin las
facilidades que para ello se me han brindado en la Facultad de Informátj_
ca de Madrid, a cuyo Decano, D. Antonio Insua Negrao, deseo expresar por
ello mi agradecimiento.
Me ha sido asimismo de gran utilidad la colaboración manteni_
da con la Profesora D- Adoración de Miguel, por su gran experiencia pro
fesional en el campo de las Bases de Datos.
Debo mencionar también a todas las personas e instituciones
cuya labor de investigación constituye el punto de partida de este traba_
jo. Agradezco en particular la ayuda prestada en este sentido por I.B.M.,
S.A.E.
La recopilación de la bibliografía "consultada ha sido fácil
con la eficiente ayuda del Centro de Documentación y Biblioteca de la Fa_
cuitad de Informática de Madrid, a cuyo Departamento de Publicaciones de_
seo también dar las gracias por su ayuda.
Vaya por fin la expresión de mi profunda gratitud a mis p a
dres, cuyo aliento y confianza en mí, han constituido un importante estj_
mulo en la realización de este trabajo.
- VI -
L I S T A DE S Í M B O L O S
V
i
<
u
V
A
I /
Cuantificador universal
Cuantificador existencial
No existencia de
» A continuación de cualquiera de los anteriores, expresa
una condición y se lee "tal que"
CZ. Inclusión
C Inclusión o igualdad
G Pertenencia
Menor o igual
Menor
Mayor o igual
Mayor
Unión de conjuntos
O Intesección de conjuntos
Or
And
Cardinal de un conjunto
Í N D I C E
Páqina
CAPITULO 0. INTRODUCCIÓN 1
CAPITULO I. GENERALIDADES ACERCA DE LAS BASES DE
DATOS RELACIÓNALES.
1. El modelo relacional 6
2. Algebra relacional 7
3. Restricciones y esquemas de relación 12
4. Dependencia funcional 12
4.1. Dependencia funcional completa 13
4.2. Dependencia funcional transitiva 13
5. Implicación lógica de dependencias 14
5.1. Cálculo del cierre de un descriptor
con respecto a un conjunto dado de
dependencias 15
6. Claves 17
7. Descomposición de relaciones conservando
las dependencias : Normalización 17
7.1. Primera Forma Normal 18
7.2. Segunda Forma Normal 19
7.3. Tercera Forma Normal 19
CAPITULO II. DETERMINACIÓN DE LAS CLAVES DE UNA
RELACIÓN
1. Introducción 22
2. Matriz de implicación. Sistematización
del Cálculo del cierre de un conjunto de
dependencias funcionales 23
3. Fundamentos Matemáticos 25
4. Algoritmo para determinar las claves de
una relación 33
5. Ejemplo de determinación de las claves
de una relación 36
6. Función "cierre" APL para determinar el
cierre de una matriz de implicación 39
CAPITULO III. PARTICIÓN FUNCIONAL: UN FUNDAMENTO
MATEMÁTICO PARA REDUCIR EL ESPACIO DE
MEMORIA NECESARIO EN EL PROCESO DE BUS
QUEDA DE LAS CLAVES DE UNA RELACIÓN
1. Introducción 43
2. Partición Funcional 43
3. Determinación de una partición funcional 46
4. Propiedades de una partición funcional 54
5. Caracterización de los atributos princi
pales y no principales 59
6. Reducción de las dependencias funcionales
del esquema inicial 63
7. Supresión de dependencias en forma refle
xiva 66
CAPITULO IV. CARACTERIZACIÓN MATEMÁTICA DE LA SE
GUNDA Y TERCERA FORMA NORMALES
1. Introducción 70
2. Caracterización matemática de la Segunda
Forma Normal
3. Algoritmo para establecer si un cierto es
quema de relación está ó no en Segunda For
ma Normal 80
4. Caracterización matemática de la Tercera
Forma Normal 83
5. Algoritmo para establecer si un cierto
esquema de relación está ó no en Tercera
Forma Normal 88
CAPITULO V. SÍNTESIS DE ESQUEMAS EN TERCERA FORMA
NORMAL.
1. Introducción 90
2. Conceptos previos 91
2.1. Recubrimiento mínimo 91
2.2. Conexión múltiple entre atributos 94
3. Semántica de las dependencias funcionales 95
4. Procedimiento de síntesis 95
4.1. Descripción del Algoritmo 95
4.2. Conexiones múltiples entre atributos 97
5. Esquemas en Tercera Forma Normal 97
6. Minimización del número de relaciones sin
tetizadas 105
7. Resumen 107
CAPITULO VI. CONSIDERACIONES PARA UN ESTUDIO POSTE
RIOR: EVOLUCIÓN ACTUAL DE LA TEORÍA DE
NORMALIZACIÓN.
1. Introducción 109
2. La unión sin pérdida : Un criterio para
la descomposición de esquemas de relación 110
3. Forma Normal de Boyce-Codd (BCNP) 115
3.1. Definición 115
3.2. "Descomposición LJ" en Forma Normal
de Boyce-Codd 116
4. Dependencias muí ti valuadas 125
5. Definición de la Cuarta Forma Normal 128
6. Consideraciones en la integración de los
tres tipos de restricciones estudiados:
dependencias funcionales, dependencias mul-
tivaluadas y dependencias respecto de la
unión 131
7. Conclusión: Posibles puntos de partida
para posteriores trabajos sobre el tema 132
CAPITULO VII. CONCLUSIONES. 134
BIBLIOGRAFÍA. 136
C A P I T U L O O
JJ^RODUCCION
El estudio y potenciación de los Sistemas de Bases de Da
tos Relaciónales ha experimentado un interés creciente, fundamen
talmente en esta última década, por la diversidad de sus posibles
aplicaciones e implicaciones en todo desarrollo informático fu
turo, dados los importantes avances de la tecnologia electrónica
y de las Comunicaciones que han permitido diseñar y fabricar má
quinas cada vez más potentes y económicas.
Así pues, las técnicas de Bases de Datos Relaciónales que
fueron concebidas inicialmente con fines docentes y de investigación
(tales como el sistema EDBMS desarrollado por el Profesor Tschiritzis
déla Universidad de Toronto) se empiezan a utilizar progresivamente
en instalaciones informáticas reales (podemos citar como ejemplos
de tales Sistemas el Query-By-Example y el IMPS , desarrollados por
un Centro de Investigación de EE.UU.).
Todos los Sistemas de Bases de Datos Relaciónales tienen como
característica fundamental el que los datos se presentan al usuario
organizados en tablas, y no en forma de jerarquías o en red, como
los modelos IMS ó CODASYL. El formato de almacenamiento interno
de los datos no es relevante para la percepción relacional. Esto
no quiere decir que las técnicas de acceso y almacenamiemto inter
nos no sean importantes, puesto que determinan si el rendimiento
- 1 -
del sistema es aceptable. Ahora bien, las consideraciones de
rendimiento no son parte de la definición del modelo relacional
en si mismo. Los sistemas anteriormente mencionados no son en
este sentido puramente relaciónales, sino que proporcionan el
modo de gestionar relacionalmente los datos organizados en tablas
en el área de trabajo de usuario.
Prototipos en desarrollo de Sistemas estrictamemte relació
nales son el Sistema R y el IS/1- PRT V.
En los modelos jerárquico y en red, los caminos de acceso
tienen que ser previamente definidos en el subesquema o percepción
del usuario. Por lo tanto, cualquier nueva necesidad de acceso
que no pueda derivarse directamente de ese camino, requiere una
lógica de programación adicional.
En el modelo relacional la búsqueda se realiza por valores
de campo (elementos de la tabla) y ya que no hay lugares privi
legiados en cuanto a facilidad de acceso, existen potencialmente
muchos posibles caminos lógicos y no es necesario definir ninguno
previamente.
Los actuales lenguajes relaciónales de manipulación de datos
suelen ser generalmente muy sencillos, lo que les hace muy atrac
tivos para el usuario final no informático.
Pueden ser de tipo procedural, basados en el Algebra Rela
cional, como el SQL (el lenguaje del Sistema R), ó no procedura-
- 2 -
les, basados en el Cálculo Relacional, como el ALPHA, que diseñó
el profesor norteamericano, E.F. Codd. En cualquier caso, si se
trabaja con tablas muy grandes, y aparte de los problemas de alma
cenamiento que ello pueda suponer, pueden producirse problemas
en las operaciones usuales de inserción, borrado o actualización.
La búsqueda de estructuras queobviasen estos problemas, redu
jeran la necesidad de reestructuraciones en la Base ;al añadir nue
vos tipos de datos y alargasen la vida de los programas de aplica
ción, llevó a E.F. Codd a la definición de las Tres Formas Norma
les, definición basada en dos importantes conceptos: Dependencia
funcional y clave.
En el trabajo que hemos desarrollado al hablar de Base de
Datos ncs estamos refiriendo, tal como hemos especificado al prin
cipio, al nivel lógico. Este nivel lógico es el modelo de una
realidad determinada, modelo realizado en base a unos cuantos ele
mentos (atributos), sujetos a unas ciertas limitaciones (especifi
caciones del usuario). Estas restricciones pueden ser tan comple
jas como lo sea la realidad a modelar, siendo preciso en cualquier
caso poder establecer una definición y caracterización matemática
precisa de estas restricciones, para poder establecer la validez
de la sutitución del modelo inicial por otros más adecuados (en el
sentido, por ejemplo de que contenga matrices de menor tamaño y
planteen por ello menos problemas de espacio en memoria . con el
consiguiente ahorro económico que ello implica ).
Para poder elaborar una teoria matemática sólida en esta
línea, es preciso contar con un conjunto completo de reglas de
- 3 -
inferencia para el tipo de restricciones dado. Sólo en dos
casos muy concretos existen conjuntos completos de reglas de
inferencia (recordemos que un conjunto de reglas de inferencia
sea completo quiere decir que cualquier restricción que pueda
tener lugar en el modelo en estudio, puede derivarse de las enun
ciadas inicialmente por aplicación de dichas reglas ): Cuando
las restricciones son dependencias funcionales o bien dependen
cias funcionales y multivaluadas.
De estos dos casos, sólo en el primero es fácil calcular la
totalidad de las dependencias implicadas por las inicialmente
enunciadas, aun cuando su número sea muy grande. Además, las de
pendencias funcionales son suficientes para modelar con precisión
un importante número de casos reales.
En el Capítulo V figuran las técnicas de Bernstein para
síntesis de relación en Tercera Forma Normal a partir de un modelo
inicial, técnicas que se apoyan en criterios de diseño incluyendo
un número mínimo de relaciones, y que completan este estudio.
En nuestro trabajo, pretendemos inicialmente elaborar un
Algoritmo que permita determinar todas las claves de una relación,
lo que es fundamental en la definición de las Formas Normales.
Basándonos exclusivamente en el conjunto completo de re
glas de inferencia para las dependencias funcionales (Axiomas
de Armstrong), establecemos los criterios que definen si una
cierta relación está o nó normalizada, y su correspondiente ni-
- 4 -
vel de normalización, en caso afirmativo.
Consideramos que este trabajo puede ser de indudable inte
rés en el desarrollo futuro de los sistemas de Bases de Datos Re
laciónales.
En el Capitulo VI figuran diversas consideraciones para un
estudio posterior, de acuerdo con la evolución actual de la teo
ría de Normalización.
- 5 -
C A P I T U L O I
GENERALIDADES ACERCA DE LAS BASES DE DATOS RELACIÓNALES
1. EL MODELO RELACIONAL
En el modelo relaciona!, los datos se organizan en tablas
llamadas relaciones. Una relación tiene un número fijo de co
lumnas (a cada ima de las cuales se la designa por un nombre de
atributo) y un número variable de filas (tupias) ., Cada tupia
de una relación describe una entidad mediante una asignación de
valores a los atributos que dan nombre a las columnas de la re
lación.
Una Base de Datos relaciona! consiste en un conjunto de re
laciones de formato fijo, pero cuyo contenido es variable en el
tiempo.
Las relaciones y Bases de Datos relaciónales se describen
mediante esquemas. Un esquema de relación consiste en un nombre
de relación, un conjunto de atributos y un conjunto de restric
ciones. Una ocurrencia del esquema es una relación definida sobre
el conjunto de atributos del mismo y que satisface todas sus res
tricciones. Un esquema de Base de Datos relaciona! es un conjun
to de esquemas de relación (uno por cada relación de la Base), y
una ocurrencia de la Base es un conjunto adecuado de ocurrencias
de estos esquemas de relación.
- 6 -
2. ALGEBRA RELACIONA!.
Los operandos del álgebra relaciona! son relaciones cons
tantes, o bien variables que representan relaciones de grado
(número de columnas )fijo.
Los atributos son símbolos tomados de un conjunto finito U
("universo " del modelo conceptual). Usaremos A, B, C para
denotar atributos simples y S, T, X.... para designar conjuntos
de los mismos (en lo que sigue denominaremos indistintamente
"descriptor" a un atributo simple o a un conjunto de atributos).
Con cada atributo se asocia un conjunto de valores que pueden
serle asignados, conjunto que denominamos "dominio". Dado un
descriptor T e U, un valor de T es una correspondencia t que
asigna a cada elemento de T un valor de su dominio. El valor
que t asigna al atributo A se representa por t [A].
Una relación sobre T es un conjunto de valores de T. Si re
presentamos poiL^Jna relación^J/^lT) quiere decir que la rela--
ció¿y¿£e define sobre el conjunto de atributos T.
Con las convenciones de notación expuestas, pasamos a des
cribir brevemente las principales operaciones de Algebra Relacio
nal:
la) Unión : la unión de dos relaciones^vvT tís%> denotada,
P°CS¿s\VtS/¿? ?> e s e^ conjunto de tupias que pertenecen
a -/0%> a > y ? ° a a m D a s - Aplicamos el operador de unión
tan sólo a aquellas relaciones que tengan el mismo gra
do y el mismo nombre de a t r ibuto en columnas íiomóloqas.
2°) Di ferencia: Cumpl ienájryjr! (y^ las condiciones ante
riormente expuestas, la diferenci&yfi^^yfo es el con
junto de tupias que pertenecen^ayfc pero no t_a^„.
3o) Intersección: de r\ueyoy¿, ^y/^ cumpliendo las condi-
ciones exigidas para la unión, la interseco i6rr//fn
es el conjunto de tupias comunes ^
4o) Proyección : La proyección d e ^ y y (T) sobre el descrip
tor X ^ l¿/¿[^) , se define así :
{t W ,&}
5o) Selección : Conjunto de tupias deyT(T) en las que el
valor que adquiere el descriptor X cumple una cierta
condición prefijada.
6o) Producto cartesiano : Sí . M l M son relaciones de
grado K, y K9, respectivamente, el producto cartesia
no se define como el conjunto de todas las (K, x K?)
tupias cuyas primeras K., componentes son una tupia <^/A
y cuyas últimas K„ componentes son una tupia &$y¡h
se representa por El producto cartesiano d e ^ f , tL/í?
i *
7o) Div is ión : Seárf^X TyÁ relaciones de grado K, y Kr
respectivamente, siendo K. > K? y -2 f 0. Definimos
"iente<_y/i '~tj/t? c o m o e l conjunto de (K -K„) el COCÍ
tupias "t" tales que, para toda tupia "u" >_ *-/?. ?, la
tupia "tu"
Ilustremos esta definición con un ejemplo:
A
1
1
2
5
5
1
B
2
2
3
4
4
2
C
3
5
5
3
5
4
D
4
6
6
4
6
5
M C
3
5
_D
4
6
2
4
8o) Asociación : La 9 - Asociación ü_
de las columnas j y K, denotada p
r, respecto
fer 1 l^y¿2 es el
j 6 K
conjunto de tupias del producto cartesiapte^T;.. x<^L?
tales que el j-ésimo elemento dé~^/£ está en relación
0 (cualquier operador ar i tmét ico de comparación) con
el K-ésimc elemento
9o) Unión natural : Sean las re lac ione j r ^ f ( T i ) , i = l , 2 . . n 1
...n y sea T= U T. . La unión natural de esas n re
n
i=l
laciones, denotada por *^yi~- ^ es una relación de-i = l
finida sobre T de la forma siguiente:
- { t / vi , t 1 ¿ ^ : t [,^t.jMr.
Para entender cómo se construye la unión natrual, considérese
una secuencia t , , t 0 . . . . , t ; donde t - . t ^ / T • Estos valores 1 2 n r~^ Li
pueden combinarse para constituir un valor de T, ttéí^x,
si y sólo si son compatibles dos a dos , esto es:
Vi ¿ l.VJÍ n , t. [T. H Tj] = t . [T. D Tj]
Obsérvese que si los T. son disjuntos dos a dos, la asociación
natural es el producto cartesiano.
Ilustremos esta definición con un sencillo ejemplo:
1 A B C <^¿2 B C D
a b e b c d
d b c b c e
b b f a d b
c a d
i = l A
a
a
d
d i
B
b
b
b
b
C
c
c
c
c
D
d
e
d
e
10 -
Mencionemos a continuación alguna de las propiedades de
la unión natural. Se trata de una operación conmutativa y aso
ciativa. Además se tiene que :K^r$_y? - ~
Si para algún i j, T. Pl T. i 0, pero
i CTi n T j i O ^ íTi n T.]= 0, la unión natu-
ral es el conjunto vacio. De modo más general : si proyectamos
¿jxLi sobre algún T., obtenemos un subconjunto dé i = l J
Será un subconjunto propio cuando para algún elemento dé^r , no
haya ningún elemento compatible con las otras relaciones, en cu
yo caso estos elementos se pierden en la unión.
Un conjunto <J/¿- (T.) } de relaciones se dice que es com
patible respecto de la unión, si es el conjunto de proyecciones de
una relación sencilla. En este caso se verifica:
i=i L J J v ' j
Obsérvese sin embargo que si proyectamoj^/Ten subrelacio
nes, la unión natural de las proyecciones, no tiene por qué ser
necesariamente igual a^J^f. Por ejemplo : Sea la relacionara),
T = / A , B, C I , que proyectamos sobre T = / A, B i y T? =|B, C£ .
Delobel y Casey [22], demostraron que si C depende funciona]^
mente de B (el concepto de dependencia funcional se ilustrará
más adelante en este mismo capítulo), entonce{s^rjt"] ¿SC¿\
- 11 -
3. RESTRICCIONES Y ESQUEMAS DE RELACIÓN
Una restricción es, en esencia, un predicado sobre una
relación. A veces estaremos interesados en restricciones que
afectan tan sólo a una parte del universo descrito por un esque
ma de relación.
\.
Definiremos pues formalmente una res t r i cc ión como un par
(S, p ) , donde p es un predicado y S es un conjunto de atrj_
butos. La r e s t r i c c i ó n / se define para una r e l a c i q r f x í u ) ,
s i S g T y p se define par5aj^r[S] > siendo entonces / v á l i d a
e r j j ^ s i p es c i e r t o , e¿yf\f¡ • Al conjunto S se le denomina
contexto de la res t r i cc ión / .
Un esquema de relación es un Vz¿/¿- *• ~^\y>'-> siendo T
un conjunto de at r ibutos y j¿u r i conjunto de res t r icc iones. Con
cada esquema de re l ac i ón^Tx , asociamos un conjunto de re lac io
nes, REL(^Y' ( const i tu ido por todas las relaciones definidas
i T que ver i f i can las restr icc iones de_¿/| SJr;
, decimos qu¿^r (T) es una ocurrencia d%_^/¿,
sobre T que ver i f i can las restr icc iones de_¿/| ^ r ^ r U ) ' R E ^ ^ ¿
4. DEPENDENCIA FUNCIONAL
Una clase particularmente importante de restr icc iones la
constituyen las denominadas dependencias funcionales.
Sea la re lac iq r f^T lT) y los descriptores X e Y, ta les que
X U Y £ T. Decimos que Y depende funcionalmente de X, lo
- 12 -
cual se expresa como X —*• Y ("X" implica "Y"), cuando para
cada dos f i las d¿^7, t ¡ y t 2 ; t [x ]= t „ ["xjimpl ica t [Y] =
t2 [ y].
En otras palabras: El descriptor Y depende funcionalmente
de X en la relación^y(l) cuando en dicha relación a cada valor
de X se le asocia un valor determinado de Y (y sólo uno). Por el
contrario, si Y no depende de X, representaremos este hecho por
X -^ Y. Por fin, la mutua dependencia entre X e Y se simbolizan
así : x •*—>Y (en este caso también se suele decir que ambos des_
criptores son equivalentes).
4.1. Dependencia funcional completa:
Y tiene dependencia funcional completa respecto de
X, X=^Y, si tienen lugar las siguientes condiciones:
a) X -> Y
b) Y no depende de ningún subconjunto propio de X.
4.2. Dependencia funcional transitiva:
El descriptor Y depende transitivamente del descrip
tor X, X — > Y, si tienen lugar las siguientes condiciones:
a) X n Y = 0
b) Existe un descriptor Z tal que :
- 13 -
z n x = 0
z r> Y = 0
x - » z
z -/-> x
Z -> Y
Si además se verifica que Y-/->Z, de la dependencia transi
tiva se dice que es estricta.
Veremos enseguida cómo todos estos tipos de dependencias
funcionales son el fundamente del importante concepto de norma
lización.
IMPLICACIÓN LÓGICA DE DEPENDENCIAS
Sea^j/T^T^/^ un esquema de relación, donde^j^" (conjun
to de restricciones ) es un conjunto de dependencias funcionales.
Decimos que J¿, implica lógicamente la dependencia X —» Y, si
ésta tiene lugar v Jyp REÍ jf
El conjunto de todas las dependencias funcionales implica
das lógicamente porS/^se representa por C/y-v y se denomina
"cierre de^-f^". S i O ^ C / ^ , de ('y se dice que es un conjunto
completo de dependencias.
Los axiomas de Armstrong [2] , que se enuncian a conti
nuación constituyen un conjunto completo de reglas de inferencia
que permiten calcular el cierre de cualquier conjunto de depen-
- 14 -
dencias funcionales.
Al
A2
A3
A4:
A5:
Refle;xividad : S -> S
Transitividad: Si S—>V y V-rX, entonces S-^X
Aumentación: Si S-^V, entonces S ' —•-, V para todo
S' 2 S
Proyectividad: Si S ->V, entonces S -~r V' para todo
V'cV (V 1 0 )
Aditividad : Si S-*V y X-^Y, entonces SUX-^VUY
se Dado el conjunto de dependencias^/^ el descriptor X,
define el cierre de X con respecto a ^~r, X' , como el conjunto
daatributos A tales que X—>A puede deducirse a partir de(
por aplicación de los axiomas de Arrnstrong.
Exponemos a continuación un sencillo algoritmo descrito por
ULLMANN f3lj para calcular el cierre de un descriptor.
5.1. Calculo del Cierre de un Descriptor con respecto a un
Conjunto dado de Dependencias.
Se calcula una secuencia de conjuntos de atributos, X^° ,X ''
.... X de la forma siguiente :
- X(0) = X
- X^ ' es X^ ' más el conjunto de atributos A, tales que
hay alguna dependencia Y —•> Z en^r , en la que A e Z e
ye J('j'. Ya que X = X (°t .... c X ^ C .... c T , y T es
un conjunto finito, tiene que alcanzarse eventualmente un j tal
15
que: X ^ = X ' J + 1 ) . Se sigue entonces que X ^ = X^J + 1^ =
X .... Por lo que puede detenerse en este momento el
proceso.
Se demuestra fácilmente por inducción que efectivamente
(i) +
XVJ/ = X para este valor de j, (la demostración puede encontrarse en [31] )
Ejemplo : Sea el conjunto l_ de dependencias:
A B -> C D —> E G
C —-» A B E —> C
BC ^ D C G —* BD
A C D - ^ B CE —* A G
Aplicando el algoritmo de cálculo de X , tendremos X^0^
BD. Para calcular X , busquemos las dependencias que tengan
como primer mienbro B, D ó BD. Hay sólo una : D — > EG, así
que añadimos E y G a x'0', obteniendo : X^1' = BDEG.
(2) Para calcular X , buscamos aquellas dependencias cuyo
primer miembro sea subconjunto de X . Estas son: D->EG ,
BE — > C. Por tanto : X ^ = BCDEG
(3) Para calcular X buscamos las dependencias funcionales
(2) cuyo primer miembro sea subconjunto de Xv , y encontramos:
D —• EG, BE —••> C, C -* A, BC — > D, CG --->• BD, CE * AG.
(3) Asi pues: Xv = ABCDEG, que coincide con el conjunto de todos
16
los atributos. Se tiene por tanto en este caso que (BD)
ABCDEG.
6. CLAVES
Denominaremos clave de una relaciqrí^Y(T) a un subconjunto
no vacio de T, K, tel que T tiene de dependencia funcional coinple
ta respecto de K : K zr> T.
En una relació¿f^77(T) se denominan atributos principales a
aquellos que son miembros de alguna clave d¿y¿[T). A los demás
atributos se les denomina no principales.
Entre todas las claves dejy¿\T), elegiremos una como clave
primaria.
Ningún atributo de la clave primaria puede tener un valor
indefinido.
7. DESCOMPOSICIÓN DE RELACIONES CONSERVANDO LAS DEPENDENCIAS:
NORMALIZACIÓN
Descomponer una relaciQj^^fT), es reemplazarla por un con-
junto de proyecciones. De un modo muy general, esta descomposi
ción se realizará con el criterio de conservar la información
contenida en la tabla original.
Un criterio para realizar esta descomposición es que el con
junto de dependencias funcionales verificadas p o r ^ ¿ , sea im-
- 17 -
plicado por la proyección de_^/sobre las relaciones de la des
composición. Formalmente, la proyección de'/sobre un conjunto
O? de atributos Z><=J/^fZJ , es el conjunto de dependencias X —* Y
d e y ^ ' tales que XUY € Z. S¿^/Tse ha proyectado en las sub
repciones t_^?i \_yTo • • • • Z//^ '•> nay preservación de depen
dencias si la unión de todas las dependencias de^/ fT-1 >
i=l, 2 n; implica lógicamente todas las dependencias d e /
El proceso de normalización consiste en esencia en una sis
temática de realización de sucesivas proyecciones a partir del
esquema original, con conservación de las dependencias funciona
les. Codd [141 enumeró hasta seis objetivos que se realizan
al normalizar las relaciones, de los que destacamos los siguien
tes:
- Se reduce la necesidad de reestructuraciones en la Base
al introducir nuevos tipos de datos, con lo que se alarga
la vida de los programas de aplicación.
- Se reduce la incidencia de anomalias de inserción, borrado
y actualización (ver Date [21] y Ullmann [31] ).
7.1. Primera Forma Normal:
^yy(T) está en Primera Forma Normal (FNF) si todas sus en
tradas son simples (no hay grupos repetitivos, o sea: Está cons
tituida por elementos atómicos).
- 18 -
7.2. Segunda Forma Normal
ST :
Una relaciórr/7}T) está en Segunda Forma Normal (SNF),
- Está en Primera Forma Normal y
- Cada atributo no principal tiene dependencia funcional
completa respecto de cada una de las claves.
7.3. Tercera Forma Normal
Una relaciQrV^r(T) está en Tercera Forma Normal (TNF) si:
- Está en Segunda Forma Normal y
- Ningún atributo no principal ókyfy(l) depende transiti
vamente de ninguna clave de^/T(T)
Ejemplo:
Consideremos el conjunto de dependencias:
A
AB
AB.
C .
E .
C
D
E
D
D
T
El descriptor AB es evidentemente la clave de cualquier
relación definida sobre A, B, C, D, E; que cumpla el conjunto de
restricciones especificado.
Sea pues una relació,n^r(A, B, C, D, E) que verifica el
19
esquema anterior. Si queremos normalizarla, procedemos a pro
yectarla en subreíaciones que se ajusten a las definiciones de
las formas normales.
Si, como supondremos, los atributos son simples, la rela
ción ya se encuentra en Primera Forma Normal.
Segunda Forma Normal:
Ó¿ Sustituimos la relación_^?, por el conjunto de proyecciones
Síi ^ , C, D) = J^CA, C, D] ¿ffi 2 (A, B, E, D) ^cJ/rfA, B, E, DJ J f 3 ( A , B, D) - J f [ A , B, D]
Y el diagrama de dependencias funcionales es ahora :
Ó2r A > C — > D & : AB E ~» D
->D
Tercera Forma Normal
JfáU (A, C) ¿ ^ [A,C] ¿/Yn (A,B,E) {%, [A,B,E"
c_Í719 (C, D) C^?T? f C , D j ¿ ^ 2 (E, D) ¿/f2 [E, D] Ly M
(A, B, D)
Con las dependencias funcionales:
(11) A -^ C
(12) C —+ D
(21) AB
.'22) E
E
(3) AB
D
20
Cuya unión es precisamente el conjunto inicial de dependencias
dado.
En lo que sigue, consideraremos como criterio de normaliza
ción la proyección en subrelaciones conservando las dependencias
funcionales descritas para el esquema inicial. Ya hemos visto
que las claves juegan un papel fundamental en la definición de
las fechas normales, así como en el proceso de normalización pro
piamente dicho.
El siguiente Capitulo está dedicado a la búsqueda de las
claves de una relación.
Partiendo de los Axiomas de Armstrong, hemos deducido un con
junto de Lemas y Teoremas en los que se basa un Algoritmo que
permite determinar todas las claves candidatas.
- 21 -
C A P I T U L O II
DETERMINACIÓN DE LAS CLAVES DE UNA RELACIÓN
1. INTRODUCCIÓN
En el Capítulo primero hemos puesto de manifiesto cómo
las Claves juegan un papel decisivo en el proceso de normaliza
ción.
Dado el esquema de relación o/^CT,^/^ , una clave del
mismo es un descriptor K, tal que:
- K £ T
- (K-^TjeJ^
- No existe ningún subconjunto propio de K, K', tal que:
K'-*. T
La propiedad de transitividad de las dependencias funciona
les condujo a Delobel y Casey F 22 ] a establecer el isomorfisnio
entre la estructura inferencia! de las dependencias funcionales
y la estructura inferencial de las funciones Booleanas de conmu
tación. Este isomorfisnio les permitió desarrollar un algoritmo
para encontrar todas las claves de una relación, algoritmo basado
en la correspondencia entre dependencias funcionales y una fun
ción Booleana y en la determinación de implicantes principales.
22
Aquí presentamos un procedimiento alternativo, basado ex
clusivamente en los Axiomas enunciados por Annstrong para las de
pendencias funcionales que, tal como hemos señalado con anterio
ridad, constituyen un conjunto completo de reglas de inferencia
para este tipo de restricciones.
2. MATRIZ DE IMPLICACIÓN. SISTEMATIZACIÓN DEL CALCULO DEL
CIERRE DE UN CONJUNTO DE DEPENDENCIAS FUNCIONALES.
El dato de partida en el proceso de la búsqueda de Claves
(y posterior normalización) es el Conjunto de dependencias fun
cionales | S . —> X . t i = 1,2 m especificadas por el usuario
o por el Administrador de la Base, que tienen lugar en^y^T).
Sin pérdida de generalidad podemos suponer que S. , S. ,
vi f j y que S. O X. = 0 vi (ya que si S -> X también,
por proyectividad, se verifica S —> X— (S n X)).
Designaremos la matriz de implicación por la misma letra
» Sr> con que hemos denominado al conjunto de dependencias fun
cionales del esquema.
La matriz de implicación de una relaciqrf/^u) definida
sobre T = I A., A„ - - - A | es una matriz m x n cuyas filas
se identifican por los primeros miembros de las m dependencias
funcionales: S., S„.... S y sus columnas por los n atributos:
A. ,A„ A , de modo que : 1 2 n '
1 si A, 6 (S. U X.)
1 J i i
0 en caso contrario.
- 23 -
El problema de encontrar el cierreC/^ de la matriz de
implicación se reduce al de encontrar el cierre de los descrip
tores de fila con respecto al conjunto ^r de dependencias fun
cionales dado. Ya hemos visto cómo se calcula el cierre de un
descriptor, ahora expondremos sobre un ejemplo una sistematiza
ción del proceso que permite hallar facilmemte el cierre/'
del conjunto de dependencias dado.
Consideremos la relación <J/<Í(T) definida sobre
T = j A,B,C,D,E,F,G j con el conjunto de restricciones dado
por:
ABC — *
A B —>
C D - ^
EG — ^
DEG
C F
E F
A C
La matriz de implicación es :
^
A B C
A B
C D
E G
A
1
1
0
1
B
1
1
0
0
C
1
1
1
1
D
1
0
1
0
E
1
0
1
1
F
0
1
1
0
G
1
0
0
1
Para encontrar la correspondiente matriz de cierre,
seguiremos los pasos siguientes :
+
2 - Para cada dos filas distintas S. y S. ds / , si i J j ra
para todo A. € S. se verifica S. A. = 1, copiamos K J i k
todos los unos de la fila S. en los lunares homólonos J
de la fila S i - 24 -
En nuestro ejemplo la aplicación del anterior algoritmo
produce el resultado siguiente:
jar
A B C D E F G
ABC 1 1 1 1 1 1 1
A B 1 1 1 1 1 1 1
C D 0 0 1 1 1 1 0
E G 1 0 1 0 1 0 1
En lo que sigue, salvo que se indique lo contrario, traba
jaremos con el cierreC/? y no con el conjunto de dependencias
inicialmente definido. Las nuevas dependencias funcionales son
ahora S. —* Y., i = 1, 2 m, donde Y. o X.,
S. O Y. = 0 , ta l como puede deducirse fácilmente del proceso
del cálculo cle>
El conjunto de atributos que corresponden a entrada 0 en
la fila S. lo denotaremos por Y'..
Es obvio además queJ S., Y., Y'.| constituye una partición
de T si Y' . f 0. i
Al final de este Capítulo, se incluye una función APL que
realiza el algoritmo de cálculo de la matriz de cierre.
FUNDAMENTOS MATEMÁTICOS
Exponemos a continuación un conjunto de Lemas y Teoremas
- 25 -
que, partiendo exclusivamente de las propiedades axiomáticas
de las dependencias funcionales tal como fueron enunciadas
por Armstrong, constituyen el fundamento teórico para el algo
ritmo de determinación de las claves de la relación.
Lema 3.1
ene lugar la dependencia funcional £f « S.U Y' . - * T vi (i= 1, 2 .... m)
Prueba :
S. U Y. U Y' . r T 1 1 1
S.(j Y' . —*• Y . (aumentación) (1)
S.<JY'.->S.U Y', (reflexividad) (2)
Luego, por aditividad entre (1) y (2)
S. U Y' . -> T i i
Lema 3.2
EnO^7 , s i S. C S. [J Y. , y además Y ' . = 0 , entonces
también Y*. = 0
Prueba:
S J -» VJ (1)
S. _* S. (reflexividad) (2) «J \J
Por aditividad entre (1) y (2)
Sj -> T (3) (ya que Y'j = 0)
26
además
S. —* S. (reflexividad) (4)
S. __ Y. (5)
Por aditividad entre (4) y (5), resulta :
S. — * S.U Y. (6)
Ahora bien: S. C. S. (j Y. por hipótesis, luego de (6) se
deduce por.proyectividad que
Si entre (7) y (3) aplicamos la propiedad de transitividad, se
tendrá que:
S. - > T , luego Y' . = 0
Lema 3.3
r^T . si i S . C %.\) Y., e Y'.?* 0, entonces
Y^.fl Y'j f 0
Prueba:
Cualquier entrada de valor 1 de la fila S. es una entrada
de valor 1 en la fila S. (recuérdese el proceso de cálculo de
la matriz de cierre^r ). Por tanto, cualquier entrada de va
lor 0 de S. es una entrada 0 en S. , de modo que,
Y1 . O Y' ., por lo cual: Y'. O Y'. f J — i 3 i
Lema 3.4
Er^^\ si S. £ S.U Y. ; siendo Y' . i 0, para cualquier
27
¿~. c Y' . t a l que S. ta l que S. u &. —> T, se ve r i f i ca J ~™~ «J U J u
Prueba:
Razonemos por reducción al absurdo. Si a . D Y'. = 0,
y ya que S., Y. , Y'. tconstituye una partición de T, necí
seriamente a • c S. U Y. .
Por otra parte S. d S.c/ Y., de. modo que
¿2?. t S. c S. U Y.. Se tendrá entonces que:
S . -> Sn. U Y. _ > S. v ^ j _> T, o sea :
S. -> T (transitividad), lo cual es imposible por contener la
fila correspondiente a S. elementos nulos. Así, pues, debe ser
*i n v. f 9
Lema 3.5
EjvC , s i S. <t S. O Y. siendo Y ' , f 0, se t iene que
Sjnr, 1 1
Prueba:
Ya que\S., Y., Y'.J constituyen una participación de T,
si S. O Y'. = 0 se tendrá que S.c S. u Y., contra la hipó-
tesis. Luego debe ser S.OY1. f 0 3 J i
Lema 3.6
&¿y\ , si S.c S. \j Y., se tiene que S. y S. U S.. impli
- 28
can el mismo subconjunto de T
Prueba:
S. — > S. (1) (reflexividad)
S. ^ Y. (2)
De (1) y (2)>por aditividad:
S. __» S. U Y. (3)
S. —> S. (4) (reflexividad) vJ J
De (3) y (4) por ad i t i v i dad :
S .U S. - * (S. \J Y.) U S., o sea, ya que S . e S . u Y. ' \J \J «J
S. U S. _ » S. U Y. (5)
Luego, S. y S. U S. implican ambos el mismo descriptor,
S. U Y., de T. i i
Teorema 3.1.
^/ r> S 1 S-; ^ s - ^ Y. , existe un descr iptor ¿ z c S i
ta l que S.\j¿z y S. U S. implican ambos el mismo descrip
tor (subconjunto de T) .
Prueba:
En el caso de que S.—> T, basta con considerar ¿sr= 0,
siendo obvio que S.U S. -^ T.
Si por el contrario S. -/-> T, en virtud del Lema 3.5 sabe
mos que S. f) Y1 . f 0. Sea ¿t = S. O Y' ., se tendrá entonces
que a£S. .
29 -
Puesto que) S., Y., Y'.j- es una partición de T, se tendrá
que, o bien S. c Y.', o bien S. f) (S.Ü Y.) f C/. J — i j i i
mo-En el primer caso, S,c Y'., ¿ = S . f) Y ' . = S ., de J ' J ' J
do que S.y^ = S. o S., por lo cual ambos implican el mismo
subconjunto de T. Si por el contrario S. <jt Y'., se tendrá que
S. O (S. U Y.) T< 0. Ya que ^ S., Y., Y' . constituye una J
partición de T, se tiene:
Sj = (Sj.n s.) u (Sj o Y.) \j (s. n Y V =
= [S-C\ (S^Y.JJU^ C (Si U Y.)U«, que
nos permite escribir: S. c (S. \j a ) Y.
Ahora bien, S. -> Y., así que también {S.\ja- )->Y.; por lo
que, usando el Lema 3.5, ya que S. c. (S.j ¿z ) O Y. , con
(S- \J & ) -» Y., podemos afirmar que el descriptor que depende
funcionalmente de $.\)a es el mismo que el que depende de
(S.ua ) \j s. = S. S., (ya que a c s.)
Teorema 3.2
Cualquier clave que pueda derivarse de S. o S., puede
serlo también a partir de S. ó S. independientemente
Prueba:
Del Lema 3.6 y el Teorema 3.1., se deduce la existencia
de un descriptor a L- S. tal que S.(J¿z y S. U S. implican
- 30 -
el mismo subconjunto de T. En el caso de que %.\ja -^ T,
también S. V S. —^ T, pero, ya que que ¿5? c S. se tendrá que
(S. u a ) o (S. v> S.) por lo cual (y excepto en el caso
particular en que - S.), S. U S. no podrá ser una clave si
S . U¿zlo es,
Si S.Vtz ++ T ( por tanto S.\J S. -/- T), sabemos (Lema
3.1.) que existirá un subconjunto b mínimo tal que : (S.K)a )u
(Jb->T y ( S . u S.) 1/ b -> T. Pero tal como hemos razonado
antes, ya que « c S . , (S. US.) u b no podrá ser una clave si
(S.U¿z) O b lo es, excepto en el caso : (S. U ñ )ub = (S . \J S.v^
Ü b.
Lo que hasta aquí hemos deducido, nos permite asegurar que
para encontrar las claves de una relaciónj^; (T) basta con consi
derar el conjunte/-/^ = \S. —> Y. 1,1'= 1, .... m procediendo
a la aplicación reiterada de la propiedad transitiva para encon
trar el mínimo a tal que S. \j¿¿ — > T.
Teorema 3.3.
Si S es un subconjunto de T tal que S — > T, siendo
Y'. f 0, se tiene que S. u (Y1 . f) S ) —y T.
Prueba:
Los Lemas 3.3., 3.4 y 3.5 nos permiten afirmar que si
T, Y'. n S f 0 siempre que Y'. f 0.
- 31 -
Realicemos la partición de S en S, c S. u Y. y
S a Y'
Una tal partición es siempre posible ya que \ S., Y., Y'. ír
constituye una partición de T y S = SOY'- / ? •
Se tienen las siguientes dependencias funcionales:
S. __> Y. (1)
S. _ * S. (reflexividad) (2]
De (1) y (2), aplicando la propiedad de aditividad resulta:
S. _ > S. U Y. (3)
Ya que S, C S.U Y., por proyectividad de (3) se dedu
ce:
Sn. - > S2 (4)
Por otro lado, S ?0 Y'. = S?, así que, por reflexividad:
S2 O Y'. -* S2 (5)
Y ya que S O Y ' . _3 Spn Y'., aplicando a (5) la propiedad
de aumentación, se tiene:
snv.-> s2 (6)
Por aditividad entre (4) y (6) resulta:
S. V (Y'.D S) - * S (7)
Y ya que por hipótesis S*T, resulta finalmente por tran-
sitividad:
- 32 -
Si \J (Y'. O S )
4. ALGORITMO PARA DETERMINAR LAS CLAVES DE UNA RELACIÓN
La formalización matemática que hemos desarrollado, con
duce al siguiente algoritmo de búsqueda de las Claves de una
relación (en el que por JA Idesignamos la cardinalidad o número
de elementos del Conjunto A ):
I - Calcula^; , matriz mxn de cierre de la matriz de
impli cae ion.
II - Mj = 0
M2 = 0
III - Introducir en M. S. U Y1., i= 1,2.... m
IV - Si con I Y1. I c 1 I Y' . I ¿ 1 se tiene que :
S.^Y'. c S . ^ Y 1 . ( M j ) , borrar S.V V.
de M r
V - Si para todas las restantes entradas de M, se tie
ne que i Y' . | _£- 1, el algoritmo concluye: M con
tiene todas las Claves.
En caso contrario :
1) v i : |Y'.|^ 2, hallar «ij = Y1. O (S-0 Y'J)
V j ' 'i ( !Y'jl >s o).
2) y , borrar cualquier &\ j' : i j ' P ^ i j (j f j')
3) Introducir en M? S. U ^ i j , i = 1, 2 m
- 33 -
Luego suprimir en M« cualquier entrada que sea super-
conjunto de otra ya existente en M?.
4) V i e n M r | Y' . \>y 2 y \J . en ^ : S. t Sy
hal lar ¿*iKj = Y ' . O ( S ^ j K )
5 ) v . borrar ^ i K ' j ' : « i k ' j ' 2 ^ i k j ( (K ' , j ' ) f (K, j ))
6) Introducir en M„ todos los Conjuntos S. 0 ^ikj,
a condición de que no sean superconjuntos de otros ya
existentes en M„.
Si así se crea alguna nueva entrada en M„, volver al
punto V.4. En caso contrario , ir a VI
VI -Copiar en M„ los conjuntos S.\J Y1 . de M, con | Y' . ¡ /. 1.
VII -Borrar de M? las entradas que sean superconjunto de otras
ya existentes en NL.
Los conjuntos restantes en M„ son todas las claves, y el
algoritmo concluye.
Por construcción, las entradas de NL satisfacen:
S. \J Y'. _> T y, en virtud del Teorema 3.3. todas
las entradas de M? satisfacen S. Ü aij -> T. Nos que
da solo comprobar que el algoritmo es completo en el sen
tido de que encuentra todas las claves.
34
Teorema 4.1.
Sí Si S. \J ¿z- es una clave de^/¿(T) (siendo | a. \ ¿, 1)
entonces y. i i : ai=Y'.n (S. U b.), |b.| o
Prueba:
Siendo Z. \)a. una Clave, se tiene que S . ^ ^ . — ^ T.
Ahora bien, ya que S./> T, debe existir una subconjunto
Z.c S. \j Y • K) a • tal que Z._*. Y' ., y que podemos escribir
como :
2i = (z. n y,) »/ [z.n (s,y| Y,.)] -
-a. y [z. O (Sj u V.)]
(siempre es posible la existencia de una tal Z., en particular:
Z. = S.v a^ , Z. -» T - > Y'.)
Asi pues, si Z.. _^ Y'., hay que demostrar la existencia
de un j f i tal que
Z. - S j v b j
En el caso en que S. —=> Y1., hacemos Z. = S. (y esto
y .: S. —$. Y'.)- Luego, elegimos el mínimo a. '• a- = Y'f)
H S. y S. U ^. ___• T.
Si por el contrario, S. -/-> Y'., por aplicación de los
axiomas de aditividad y aumentación,
V S, \J b, U b' . = T, donde b' . c S. U Y.; por lo que b' . fl Y' .= 0 J J J J I I J I
35
(ya que \ S., Y., Y'A sabemos constituye una partición de T).
Sea Z. = S. {) b.. En este caso se tendrá: i J v J
Y' 1 O (S,U bjUb'j) - Y'.n (Sju bj) = Y ' . ^ Z r
Este proceso se realiza para cada S. \j bj : Sj U bj —* Y'i
Esto es precisamente lo que el algoritmo realiza: Encontrar itera
tivamente los descriptores ^i : Si U ^ i — > T, eligiendo
luego los mínimos de entre estos a \
Cuando el Algoritmo concluye, cada entrada de M2 es una
clave; y no se ha omitido ninguna (el Algoritmo es completo ).
5. EJEMPLO DE DETERMINACIÓN DE LAS CLAVES DE UNA RELACIÓN.
Consideremos de nuevo el esquema porpuesto como ejemplo
cuando tratamos del cálculo de la matrizC^ de cierre de una
matriz de implicación definida por un Conjunto de dependencias
funcionales dado:
T = jA, B, C, D, E, F, G \
J¿; : ABC —«y DEG
AB — > CF
CD — > EF
EG — > AC
36
A B C D E F G
j £ + : ABC 1 1 1 1 1 1 1
AB 1 1 1 1 1 1 1
CD 0 0 1 1 1 1 0
EG 1 0 1 0 1 0 1
M2 = 0
Mj : ABC ( S ^
AB (S 2 )
Y
CD U (ABG) (S 3 y Y ' 3 )
EG U (BDF) (S 4 U Y ' 4 )
í =0 , Y¿ =0, ABC AB
BORRAR ABC EN Mj
1)
^32 = Y,3 ° (S2 U Y V = ABG n (AB) = AB
^ 3 4 = Y'3 S4 U Y V = ABG ñ ^EG " BDF):: BG
^ 4 2 = Y'4 O (S2 UY'2) = BDF n (AB) =B
^43 = Y' 4n (s3 O
Y'3) = B D ™ (CDUABG) = BD
2) BORRAR a43 (a43 a42)
37 -
3) M2
S3 U a21 = C D Ü A B = ABCD
Sn U ¿z„. = CD UBG - BCDG o 34
S4 U «41 = E G Ü B = BEG
4) anA = Y ' 3 0 (S4 U ^ 4 2 ) = ABG A (EGt/B ) = BG
¿z4a3 = Y ' 4 A (S3 U ^ 3 i ) = BDFA (CDÜAB) = BD
^443 = Y ' 4 A (S3 U ^ 3 4 ) = BDF A (CDÜBG) - BD
5) BORRAR a 4 4 3 (a 4 4 3=a 4 2 3 )
6) S3 U a^. = CDUBG = CDBG (ya existente en M2)
S* U ¿S"„„ = EGUBD = EGBD (Superconjunto de BEG 4- 423
ya existente en M?)
No se ha creado ninguna nueva entrada en M?
VI - M2 : ABCD
BCDG
EEG
AB
VII- Borrar en M? los superconjuntos'
BCDG
BEG
AB
Las claves de^^T T» x > , son:
38
A3
BEG
BCDG
6. FUNCIÓN "CIERRE" APL PARA DETERMINAR EL CIERRE DE UNA
MATRIZ DE IMPLICACIÓN
El Algoritmo que hemos desarrollado es de una gran sen
cillez de cálculo, incluso (tal como hemos hecho en nuestro
ejemplo) para computación manual.
El único paso que puede resultar laborioso es el primero,
en el que se calcula el cierre de la matriz de implicación.
La función "CIERRE" APL facilita el cálculo de la matriz
de cierre.
Por "implicante" designamos al primer miembro de una depen^
dencia funcional. La matriz de implicantes tiene sus filas idejn
tificadas por cada uno de los implicantes del conjunto de depen
dencias inicialmente dado, y sus columnas por los atributos sobre
los que se define la relación. Sus elementos vienen dados por:
1 Si A. fc S.
í 0 en caso contrario *
A continuación se muestra el Algoritmo de cálculo en APL,
realizando de nuevo como ejemplo el cierre del conjunto de depen
- 39 -
dencias :
ABC
AB •
CD
EG
—+ — ^
>
— *
DEG
CF
EF
AC
40
VCIERRE I I . .1 'MATRIZ DE IMPLICAÍM'DN' I".! 3 PH'J 1:3:1 'MATRIZ DE I M P L I C A N T E ; ; ; '
I;M;;I I.H:I I"'r¡:.l P1 <••( V«-,'>P)pO i.ó;i i . i : i.<o l"7J L 2 : J < ( ) I.Ü3 •••< < ] > I + :I. ) > V i : i 3 ) / L ' l 1.93 L3 : -K<J<- . . JM)>Vr : 13 >/!...:! c i ü 3 • > < ~ A / < P I : J ; 3 A L I : : J ; 3 ) ~ L I : J ; : D / L 3
I: I I 3 P Í c i ; 3<-Pi c i ; 3 V P C J ; 3 I I123 ->L3 I I133 L4-: -> < A / A / P = P 1 ) /END C143 P<~P1 11153 Plt-VpO L'163 -»L1 I I173 END: 'LA MATRIZ DE CCERRÉ ES ' i : i83 PV
- 41 -
CIERRE MATRIZ DE IMPLICACIÓN 11:
1 7p1 I 1 .1 1 0 1. j 1 .1. 0 0 I. 0 0 0 I I I I ii I >• ! O ! .i ! MATRIZ l.i£ IMPLICANTES D •'
'+ 7p.l I 1 0 0 0 0 :i I. 0 O O O l) O 0 .1. 1 O O O O !; 0 O I í! I LA MATRIZ HE CIERRE ES J. 1. I 1 .1 I 1 1 1 :l 1 1 i 1 O ü 1 1 1 1 O 1 0 1 0 1 0 1
- 42 -
C A P I T U L O III
PARTICIÓN FUNCIONAL: UN FUNDAMENTO MATEMÁTICO PARA REDUCIR
EL ESPACIO DE MEMORIA NECESARIO EN EL PROCESO DE BÚSQUEDA DE
LAS CLAVES DE UNA RELACIÓN.
1. INTRODUCCIÓN
La partición funcional proporciona el modo de encontrar las
claves de una relación^/¿{T), definida sobre T y sujeta a un
conjunto de restricciones a partir de sus proyecciones en
subrelaciones definidas sobre subconjuntos de T. Esto implica el
que los cierres se tomen en submatrices de la matriz de implica-
cion)cJ¿>, de modo que se disminuye el espacio de memoria necesa
rio.
El concepto de partición funcional y su cálculo algebraico,
que exponemos a continuación en los puntos 2 al 4, han sido toma
dos del libro de Youssef Fadous [35] , adaptando la notación al
resto de nuestro trabajo e incluyendo dos funciones APL que faci
litan el cálculo de una partición funcional.
2. PARTICIÓN FUNCIONAL
En el Capítulo II, hemos presentado al Algoritmo que en
cuentra las claves de una relación a partir del conjunto de res
tricciones definidas por el Administrador de la Base o por el
43
usuario.
Ahora bien, si el número de estas restricciones es muy
grande, el número de pasos de computación es enorme, por lo que
trataremos de determinar si es posible encontrar las claves de
a partir de subconjuntos del conjunto original de dependen
cias funcionales y, em caso afirmativo, encontrar tales subcon
juntos.
Sea pues el conjunto inicial de dependencias funcionales:
££ \ S T h \ -* V i = 1.2 - - - m f , en el
que supondremos : T = y (S.i/X.) (esta suposición la uti-
i = l 1 1
Tizaremos a lo largo de todo el Capítulo salvo que se especifi
que lo contrario, y no es en absoluto restrictiva, ya que cual
quier conjunto de dependencias puede, sin más que aplicar alguno
de los Axiomas de Armstrong, completarse si fuera necesario de
modo que tenga lugar la igualdad T = y (S, U X.). i = l i i
Definición 2-1
Dos dependencias funcionales^^/' y fí pertenecientes a
¿¿i^ denominan adyacentes.^y^J^f , si (S. U X.) 1 (S. U X.)
f 0 . En caso contrario, ^*. y (Qfc son no adyacentes:
44
i T y^J
Definición 2-2
Dos dependencias funcional es<Q^. y ^ . pertenecientes ©>>
están conectadas, <-# <S£ , si tiene lugar una al menos de
las siguientes condiciones:
< ^ ¿ ^
Teorema 2-1
cía en
La relación de conexión, , es una relación de equivaler
Prueba:
De la definición de relación de conexión es evidente dedu
cir las propiedades de reflexividad, simetría y transitividad.
Luego se trata de una relación de equivalencia, que determinará
en | t[^'• \ una partición en clases de equivalencia, denota
das po r&/ .~ . Cada clase puede representarse por uno cualquiera
de sus elementos.
Definición 2- 3
Si enj^rse tiene que j / ' ^y / ' .
conexión induce la partición identidad.
y . f i, la relación de
- 45 -
Definición 2 - 4
¡i enS/se tiene que*-^ ^ T \ V ' i l a r e l ación
de conexión induce la partición universal
Lema 2 - 1
T.
Una partición en y~\ S*- r > induce otra partición en
Prueba:
^T"„ ¿3 Si~// y ~v£ están en diferentes clases de equivalencia
se sigue, o bien que ^fi.-*¿Q6. o que iM^ ¿ ¿ # •
Luego, si C. es el conjunto de atributos de¿^. es obvio que
C. O C. = 0 V , f j, y UC, = T. Luego ( C. \ es una
partición de T.
DETERMINACIÓN DE UNA PARTICIÓN FUNCIONAL
Dado el Conjunto^^=JJ/T [de dependencias funcionales,
los pasos necesarios para obtener la partición inducida por la
relación de conexión entre sus elementos, son los siguientes:
I - Formar la matriz de implicación/
II - Formar la matriz de incidencia,/•> que se de
fine como sigue:
46 -
bélica tomada de la notación APL cuyo significado es el si
j;J expresión sim-
guiente: Realizar la operación AND lógica entre los elementos
homólogos de las filas i-ésima y j-ésima de Cf^ . Luego, rea
lizar la operación OR lógica entre todos los elementos del
Vector binario resultante.
III Hallar el cierre d ¿f'^T IV - Los "unos" de cada diferente fila de ( 7^ , defi
nen una clase de equivalencia bajo r^ (Teniendo en
cuenta que las filas y columnas cüe/^' y, por tanto,
de su cierreVyr , son ahora las dependencias fun
cionales <^T»Oo» * &
<OJ m)
Ejemplo :
* & < & . Sea el esquema de relación
T = \A,B,C,D,E,F,G,H,I,J,K,L,M i
> con
y el conjunto de dependencias funcionales ,
H -» KL ,J^ BD ->FG, 'Oí \ AE
AB-* C,
La correspondiente matriz de implicación es
- 47 -
**ZL>~ 07^" 3
J^4
A B C D E F G H I J K
1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0
0 1 0 1 0 1 1 0 0 0 0
1 0 1 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1
De la que se deduce la matriz de incidencia ;
۟T
& - . %
^
i
o
1
1
o
o
1
o
o
1
1
o
1
o
o
^ A a a OÍ a ^y\ <~/i c / 3 « - / í ^ y s
i
o
i
o
o
i
o o
o
i
Cuyo cierre es:
<a¿~ i
i
o
1
1
o
2 ^3 <_A <^5
0
1
0
0
1
1
0
1
1
o
1
o
1
1
o
o
1
o
1
Las clases de equivalencia inducidas por la relación de conexión,
son pues :
- 48 -
^i | t yi '^3 ' J> 4 f
Damos a continuación dos funciones APL que realizan el
cálculo de una partición funcional.
La función INCD P calcula la matriz de incidencia de
una matriz de implicación dada cuyo contenido se ha asignado a la
variable P. La matriz de incidencia queda almacenada en otra
variable, P PRIMA, lo que permite su uso en cálculos posteriores.
CIERRE1 X es una modificación de la función CIERRE que he
mos utilizado en el Capitulo II. A diferencia de aquella, ésta
es una función monádica (se aplica a un argumento) que actúa
sobre una variable definida en el área de trabajo de usuario con
anterioridad a su ejecución (la función no solicita entrada de
datos al usuario al ejecutarse ). Téngase en cuenta asimismo
que ahora la matriz de implicantes es la matriz unidad m x tn
(si la matriz de implicación era m x n), y que dicha matriz de
implicantes debe haberse definido antes de llamar a la función.
Las clases de equivalencia están definidas por los "unos"
de las filas de la matriz
CIERRE! (INCD P)
Como un segundo ejemplo, hemos tomado el utilizado a lo
- 49 -
largo del Capitulo anterior, es decir, el esquema de relación:
¿/l*>x¿£> siendo:
T = |A, B, C, D, E, F, G \
& ABC — ^ > DEG
AB — „ CF
CD —==* EF
EG —*? AC
Obteniendo en este caso como resultado la partición uni
versal (por simple inspección de las dependencias funcionales
dadas ya se ve que todas están conectadas entre si).
- 50 -
VPPRIMA«-INCL1I' ÍA1 M < - ( 2 p ( l t p P ) ) p O Í21 I«-Q C33 L 2 : J < 0 C«+3 -»<<]>I + l>>ltpP>/END C53 Ll :->( (J<-J+l)>ltpP)/L2 \:¿:i M C I ; J 3 < - V / P C I ; 3 A P C J ; 3
m ->u. I:O:J END:PPRIMA<-MV
- 51 -
I
7CP«-CIERRE1 X C U PK-(V<-pX)pO C2J L l : K-0 C3."J L2 :J«-0 C'+II •+< < : i > . l > l ) > V C U ) / L > + C51 L3 : -* < < J f -J +1 > > Vi: 1 3 ) /L .2 €.61 - > ( ^ A / ( X C I ; I A L C J ; 3 ) = L C J ; : ] ) / L 3 C73 P l C I U < - P l C I U v X L " J ; 3 C8I! ->L3 C93 L M : - > < A / A / X = P 1 ) / E N D
C Í O : X<--PI n.u Pi<-vpo C12II ->L1 C13 3 END:CP«-XV
- 52 -
1 I 1. 1 ! 0 1 .1 :l. .1. 0 O 1 O 0 0 1 1 1 1 0 1 0 1 0 1 0 1
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
I N C D P 1 1 1 1 1 1 1 1 1 1 1 1 1 :i 1 1
1 I 1
.1. J.
1 1
,í
1 .1.
1 1 1 .1 :i i
::: :i 1.
i i
ERREl ( I N C DI ' )
- 53 -
4. PROPIEDADES DE UNA PARTICIÓN FUNCIONAL
Sea | J , T? .... T \ la partición inducida en T por una
partición en \y^\- La relación ^/¿(T) definida sobre T pue
de proyectarse en subrelaciones.
(T.) - «J-/£T. , definidas sobre T., i= 1, 2 — n.
Sea ÍS..—> K..I el conjunto de dependencias funcionales
S. —fr X. que tienen lugar en <_S¿ • .
El Lema y Teorema siguiente demuestran que las claves de
se pueden obtener a partir de las de_yX , i= 1, 2,.... n.
Lema 4 - 1
Seáis..—> X..\ el conjunto de dependencias funcionales de
, (T.). Si S. — > X. es una dependencia funcional de
7J), S. C. T, X. . = X. Q T., entonces existe K.. £ S. i — íj i J i J — i
tal que K.. c, T. Y K. . -* X..
Prueba:
La aplicación de las propiedades de reflexividad, proyectivi-
dad, transitividad y aditividad a las dependencias funcionales de
<~^, produce como resultado dependencias funcionales cuyos atri
butos pertenecen a T.. Sin embargo, la aplicación de la propiedad
de aumentación con atributos no pertenecientes a T. produce como ü
- 54 -
resultado dependencias funcionales S. • > X. que tienen
lugar enJy£(T), con S. Q T X.. = X. <== T.. Por tanto, tiene
que existir un descriptor K..C.T. tal que K..—b-X..
Teorema 4 - 1
Si T = I T., T? ...., T es la partición inducida en T
por una partición funcional en , [ / } , y si K S , T, la condición
necesaria y suficiente para que K sea una clave de T es que se
cumpla:
K = UK., donde K. # 0 y K. c T. es una clave de i i J i — i
• i
Prueba
- Condición necesaria
Sea K una clave dej^lT). Ya que \ T , T,,, , T \
es una partición de T, se tendrá :
K = (K O Tj) U (K O T2) U.... U (K O T ). Sea
K. = K O T. . Hay que demostrar que i . K. i 0 Y K. es i _ 1 ^ ^ M i i i
clave de^j^^. . Supongamos que 3 . : K. f 0 , en ese caso:
K = K.U K0 U ... U K. .UK.^. U U K , Y K — • T -• T., 1 2 i-l í+l n i
resultado que contradice el Lema 4 - 1 al no tener K ningún sub-
conjunto perteneciente a T. . De aquí que deba ser K.= 0 y' .,
por lo que : K = K'¿ K„ U ...U K.U UK , K -* T -* T. .
1 2 i n i Por el Lema 4 - 1 debe e x i s t i r M. c. K ta l que M . - - T . Y M.—>J..
i •— ^ i i i i 5^ -
Pero K. C. K es el único subconjunto de K que pertenece a T.,
luego M.£ K. Y M. — > T . . Por lo tanto M = Mn U...U M 3 i i i i 1 n
es tal que que M & K Y M —*-T, pero esto contradice la hipóte
sis de partida según la cual K es clave áo^y¿{~\). Debe ser por
tanto M. = K., por lo que K. es clave de, ^
- Condición suficiente
Si K. c.T. es clave doJ?'/ \/ ., entonces K = UK. es tal
que K —> T (aditividad). Nos queda ahora demostrar que no existe
ningún subconjunto propio de K que a su vez implique T. En efec
to: Supongamos M c K y M —> T. Se tendrá pues que M=UM..,
donde Mi c. Ki, M.. f 0. De nuevo, siguiendo el mismo razona
miento anterior, Mi —•Ti, lo cual contradice el hecho de que
de M Ki sea clave dej/ T. , excepto si Mi = Ki. Luego K = UKi es clave
Corolario 4 - 1
Si la relación de conexión induce en {, T. } la partición
identidad, K = US. es la única clave áety?(T).
Prueba
Se siguedel Teorema 4 - 1 ya que cada c/í : Si —> Xi
constituye una clase de equivalencia en sí misma. Sea Ti =(SiUXi)
y proyectémosla/en subrelaciono¿X¿i (Ti). Se tiene que Si es
'¿5 la única clave de<_
56
Corolario 4 - 2
Si no hay dependencias funcionales definidas en el esquema
< T, ,J2T> , esto es: <^¿ = 0, entonces T es la única cla
ve áe<_y¿ (1).
Corolario 4 - 3
Sea t_V¿-una relación definida sobre el conjunto de atribu
tos T, y supongamos que las dependencias funcionales se definen
en T CZ T.
Sea Jsi-, (T-) = L-^-TT,"] la proyección de t.>v (T) sobre
T.. Si K, es una clave de .yj,, entonces K = K U (T-T,) es 1 l ó¿ ^ 1 1 una clave de<^/¿(T).
Prueba :
Seajg? (T - Tj) = ^ f r - T j la proyección de ¿%
sobre T-T1. Está claro que, al no haber dependencias funcionales
definidas parajp^ , en virtud del Corolario 4-2, T- T es
la única clave „. Ya que "L y T - T. son disjuntos, se ten
drá que T = T U (T-T..) y, en virtud del Teorema 4-1, K = K U
(T-TJ es una clave de/y7{T).
Ejemplo
Consideremos de nuevo el esquema de relación sobre el que
- 57 -
realizamos en primer lugar una partición funcional.
T = { A,B,C,D,E,F,G,H,I,J,K,L,Mj
j¿f: AB > C
H __—• KL
BD > FG
AE •> C
KM > L
Vimos que la partición funcional comprendía dos clases de
equivalencia. Añadiremos ahora que dicha partición induce otra
en el conjunto T de atributos, a saber : T = \ T , T 0^ , con
^7' T = J A,B,C,D,E,F,G } y T2= j H,K,L,M ¡ . ProyectemosJ/Tsobre
T y sobre T„. Las dependencias funcionales son ahora, pa-
BD > FG
AE > C
y para, S%¡T¿ =J^f (T2) : H -—> KL
KM > L
ABDE Fácilmente se obtiene que la única clave de ¿s¿ •, es K
y que la única clave deJ^TX es K„ = HM.
La única clave d e o V . e s K = Kr U K = ABDEHM.
- 58
5 - CARACTERIZACIÓN DE LOS ATRIBUTOS PRINCIPALES Y NO PRIN
CIPALES
La caracterización de los atrnbutos principales y no prin
cipales juega un importante papel en la determinación del grado
de normalización de una relación. De ahí la importancia de su
estudio.
Supondremos que nuestro esquema es ahorat^-/^ T, c=^7,>, donde
es ahora un conjunto de relaciones conectadas en
tre sí y tales que T = U (Si U Xi).
Lema 5 - 1
Si un atributo A. no pertenece a ningún implicante S.5 no
existe ninguna dependencia S —^ X en <J/¿, tal que A. £ S
y A, ¿ X, excepto en el caso de que exista un descriptor S'c S
tal que A k £ S' y S" — > X.
Prueba
Si 9 i: A. £ S., entonces 3 j: A, £ X. (ya que T=
U (Si U Xi)).
Por aumentación del implicante de la dependencia S. —*• X
con el atributo A, , obtenemos : S — & • X., y por proyectividad K J
se verifica también : S — > (X. - A, ), de modo que existe
S —fc» X con A, £. S y A, <£ X sólo en el caso de que exis
ta S' c: S tal que S' —1> X. - 59 -
Teorema 5 - 1
Si A, no pertenece a ningún implicante S., A, es no princi
pal .
Prueba
En el Capítulo anterior hemos visto cómo toda clave de
(T) es de la forma S.U ^., siendo S. alguno de los implicantes
del conjunto de dependencias funcionales inicialmente definido
y con ^ . c V . , \a .\ >. 0. Si y • \ a \ = 0, S.
es una clave y ya que, por hipótesis, A no pertenece a ningún
implicante, se tendrá que A, es no principal.
Si, por el contrario, para algún i se tiene que \a-\>Q,
Si U . ¿ . —*» T, Si -/>T, tiene que existir
Zi C Si U Y. \] a. tal que Z. = &. U Z. (S.UY.)
Y Z. —* Y' . — ¿ . . Además, a . = Z. n Y' y ^ . es el
mínimo subconjunto de Y'i tal que Z. —> Y'.. - ¿¿.. Pero si A, ^
a ., entonces Ak £ 1. y Ak £ Y'. - <*. ya que Z{ y
Y'. - <#. son disjuntos. Por tanto, Zi —*• Y -¡-^j es
una dependencia funcional cuya verificación contradice el Lema
5 - 1 ya que A. {=¡ Z_. y A, (fr Y'i - ^i. Debe por tanto suceder
que A, ^ a , con lo cual A, ^ S. U a., o sea A es no princi
pal .
Corolario 5 - 1
Si A, es principal, entonces es miembro de algún implicante
Si - 60 -
Corolario 5 - 2
Toda clave K de ,^/£es un subconjunto de US.
Lema 5 - 2
Si A. no pertenece a ningún X., no existe ent-^- ninguna K 1
9 dependencia funcional S — * X con A, ^. S y A. €: X.
Prueba:
Si jj . : Ak € X., entonces j% : AR £ Sj
Por aditividad entre las dependencias S. —>X. y A, —>A. , J j k k
se obtiene otra nueva, S ->X, tal que A, £ X (pero en la que Ak
también forma parte del implicante ). Y no hay más dependencias
en las que A. e X que las así obtenidas.
Teorema 5 - 2
Si A. no pertenece a ningún X., entonces A, entra a formar
parte de todas las claves de ^y¿.
Prueba :
COI Sea K = S. U &. una clave dec y supongamos que A, fc
K. Entonces K —-& T ^ A, , por aplicación de proyectividad.
61
Entramos pues en contradicción con el Lema 5 - 2, lo que quiere
decir que A. £ K, \/K que sea clave de
Corolario 5 - 3
Si un atributo A. no forma parte de ningún X-, entonces A,
es principal.
Corolario 5 - 4
Si un atributo A, es no principal, entonces debe pertenecer
a algún X.
Corolario 5 - 5
Si todos los atributos de UX. son principales, entonces to
dos los atributos de T son principales.
Corolario 5 - 6
Si cada atr ibuto de UX. es p r i n c i p a l , T = US.
Corolario 5 - 7
Sea T = US., T = UX.. Si i 1 , T 1 es una partición de
T, entonces T- es la única clave de J ^ V ) .
62
Prueba :
Ya que < T,, JÁ constituye una partición de T, ningún atri
buto de "L puede pertenecer a ningún X. y ningún atributo de T„
puede pertenecer a ningún S..
Pero, en virtud del Teorema 5-1, ningún atributo de J? es
principal y según el Teorema 5-2, todo atributo de T es miembro
de alguna clave de^j^r; Por lo tanto, si K es una clave dejyl,
T. c K; y según el corolario 5-2, K c T . Luego debe ser K=T ,
única clave de
Lo expuesto en los Teoremas y Corolarios precedentes, pone de
relieve cómo las claves de una relación son subconjuntos de US..,
siendo S. los implicantes o primeros miembros de las dependencias
funcionales S. —#>X. definidas inicialmente.
Este resultado nos lleva a afirmar que podemos, en el proce
so de la búsqueda de claves, borrar en la matriz de implicación las
columnas correspondientes a los atributos del conjunto diferencia:
(UX.) - (US.), obteniendo exactamente el mismo resultado
y con la consiguiente economía de almacenamiento.
6 - REDUCCIÓN DE LAS DEPENDENCIAS FUNCIONALES DEL ESQUEMA INICIAL,
Sea^/7(T) una relación definida sobre T y sujeta al conjun-
63
to de restricciones J Qp. : S. .—> X. r , todas ellas conec
tadas entre si, siendo además T = U (S.UX.) i i
Sea K^/¿I (TJ la proyecció TJ de la reía
i s
ción J^/sobre el conjunto de atributos T1 . Las dependencias
funcionales "reducidas", se obtienen a partir de las dependencias
funcionales definidas pargyjXT) sin más que borrar los atribu
tos pertenecientes a T„. Nótese que, \/ . las dependencias fun-cionales de Cyí, (T-.) , son de la forma : S. -—>X'.,
*"A i i i
con X1 . cL X. siempre que T? ^> 0 y X'. = X. solo si
T? =j0f ; de modo, que, por proyectividad, las dependencias fun
cionales de •*^/[A (T,) siguen verificándose.
El Teorema siguiente es un resultado fundamental que mues
tra cómo las claves de v-/¿(T) pueden obtenerse exclusivamente
a partir de las dependencias funcionales de ¿si-\ ("!"-,).
Teorema 6 - 1
El descriptor K o T es una clave de J/¿.(T) si Y sólo
si es clave de la proyección de ^ Y sobre US..
Prueba
Condición necesaria
Si K es clave de_/2(T), se tiene por definición que K—*T,
64
luego K —1> T1, por proyectividad, además, K es el subconjunto
mínimo de T tal que K->T. Pero, en virtud del Corolario 5-2,
podemos afirmar que K— T1 , o sea que K es un subconjunto mínimo
de "!\ tal que K —>T\.
Sea K. c K y supongamos que K.. — > T 1 .
Por aditividad resulta: T, (=US.) -*• UX., y por transitivi
dad: K1 —é*(US.) U (UX.) = T. Sin embargo, K. _*. T contradice
la hipótesis de partida, según la cual K es una clave áer/y'J).
Luego K es también clave deJ^X (T,).
- Condición suficiente -
Si K es una clave ¿e/vl (T.), entonces K-*- T. y K-+-T,—*-UX. • i l i i i
por transitividad. Por tanto K—»(US.) U (UX.) = T, por aditivi
dad. Ahora bien: Si existe un subconjunto propio K-.dK tal que
K. —&•"!", entonces K, •—&.T. por proyectividad, lo cual contradice
la hipótesis de que K sea clave $§?£,•, (T,). Luego K es clave
de^T).
Ejemplo:
Sea el esquema de r e l a c i ó J T ^ ¿ < T , J ^ > , siendo:
T = \ A ,B,C,D,E,F,G,H,K|
J § T : AB —-* CD
ABE > FG
CE > HK
AH — _ » BFK
65
El Algoritmo de búsqueda de claves expuesto en el Capitu
lo segundo, produce como resultado.
ABE, AEH, ACE
Proyectamos_^/£sobre T, = US. = ABCEH, T„ es el conjunto
T - T = JD,F,G,K| . Las dependencias funcionales reducidas son:
AB —-* C
ABE . * ABE (Reflexividad)
CE . » H
AH — » B
El cierre de la matriz de implicación relativa a las depen
dencias reducidas es ahora :
A B C E H
AB 1 1 1 0 0
ABE 1 1 1 1 1
CE 0 0 1 1 1
AH 1 1 1 0 1
Y obtenemos a partir de ella como resultado el mismo conjun
to de claves: ABE, AEH y ACE.
SUPRESIÓN DE DEPENDENCIAS EN FORMA REFLEXIVA
Una dependencia funcional de la forma S. —» S., se denomina i i
- 66 -
forma reflexiva. En caso contrario, se denominará no reflexi
va.
Propiedad 7 - 1
Si S —» X es una dependencia funcional obtenidad del con
junto inicialmente dado jL'MPor aplicación de los Axiomas de
Arsmtrong, entonces 3 • '• S o S., ya que la aplicación de di
chos Axiomas, o bien no altera el implicante (primer miembro)
de una dependencia, o bien lo incrementa en algún nuevo elemento.
Lema 7 - 1
<3T Si ^T- es una forma reflexiva y 3 . , .: S. c S. en ei
^ 1 J -^ 3 f i J "i
conjunto original de dependencias, entonces cualquier clave que
pueda obtenerse a partir de S. puede serlo también a partir de
S.. J
Sea S.. = S. - S.. Si S.U b. — > T, entonces (S.U S..) U i j i i j U
Ub. = S. U (S..U b.) = S.U b. —b- T. Así pues hay siempre al i J i J i J J
menos un b. c S.U b. (y de aquí que S.U b.cS.U b.), tal que
S.U b. — • T. Por tanto, S.U b. no puede ser clave áe^y~¿{l) si vi J • '
S.U b- lo es, excepto en el caso de que S.U b. = S.U b..
Lema 7
Sit^s'. es una forma reflexiva y si y . , . se tiene que
S. <¡£ S. en el conjunto de dependencias funcionales original,
- 67
cuaquier clave que pueda deducirse a partir de S. puede serlo
también de S. para algún K f i.
Prueba
Si V • / • se tiene que S.. cjl S. en el conjunto original
de dependencias, las únicas dependencias que pueden deducirse de
la matriz C ^ de cierre son del tipo : S. — > S. . De este
modo , Y. = 0 , Y' . = T -S., ya que hemos supuesto S.n Y. = 0. ) i i i J ^ ' i i
De aquí que, si S.U b. —&> T para b. c Y ., tiene que existir
Z- £• S. U b. tal que Z. —*. Y', de modo que, según la Propie
dad 7-1, Z. = S. Ug. para algún K f i, y S.Ug. - > Y'.-
Ahora bien, ya que S. cz S.U b. y S.U b. —e>T, existen ' J \ k — i i i i
entonces b, Sr S.U b. tal que S, U b, cz S.U b. c ,, , T k — i i ! k k — i i y S . U b, — * . T
(Lema 7 - 1 ) . Por tanto, S. U b. no puede ser clave si S.U b. lo i i K k k
es, excepto si S. U b. = S. U b.. i 1 K K
Teorema 7 - 1
Cualquier forma reflexiva puede suprimirse de (-/ = j jfc-. \ Ó/) ' \ 1 )
sin alterar por ello las claves de t_J/¿ul
Prueba :
Si <_y\ es una forma reflexiva, por los Lemas 7 - 1 y 7 - 2,
toda clave que pueda deducirse de S. puede serlo también a partir
de S., para algún j ?' i. Por tanto, sólo queda demostrar que si,
con j f i, S.U &. es una clave, entonces^^^/! no necesita
- 68 -
usarse para determinar ^
En efecto, si S.U b. •—&• T, b. 3 a. , tiene que existir J J J J
Z. £ s. UY. U b. tal que Z. —h. Y'.. De aquí que, si J J J J J J
Z. = s.Ug. (propiedad 7 - 1 ) , entonces para g' i c S.UY.,
S.Ug.Ug'i = S.U b. —» T -^ Y'.; siendo bj = Y' . O(S.U g.) =
Y', n (S.U b.) ; de modo que, por los Lemas 7-1 y 7-2, existe
siempre S.U b, c. S.U b. para algún Kf i, tal que S. U b —*• T
-f» Y'..
Por tanto, si S.U & . es una clave, y recordando cómo pro-
cede el Algoritmo de búsqueda de las claves de una relación, S.U b.
no precisa ser usado ya que es un superconjunto.
Podemos pues borrar t_y. del conjunto original ^¿, Tíy^• \
de dependencias funcionales sin alterar por ello las claves de
una relación definidad sobre T y sujeta a ese conjunto de restric
ciones.
69
C A P I T U L O IV
CARACTERIZACIÓN MATEMÁTICA DE LA SEGUNDA Y TERCERA FORMAS
NORMALES.
1. INTRODUCCIÓN
El objetivo del presente Capítulo, es dada una relación nor
malizada (es decir, una relación en Primera Forma Normal con en
tradas simples ) poder determinar si además se encuentra en Según
da Forma Normal (y, en caso afirmativo, si además está en Tercera
Forma Normal).
Este es un enfoque analítico: Dado un esquema de relación,
averiguar cuál es su nivel de normalización. En un Capítulo pos
terior esbozaremos el problema de síntesis: Construir un conjunto
de relaciones normalizadas (y además en TNF) a partir de un univer
so de atributos y de un conjunto de restricciones (dependencias
funcionales).
CARACTERRIZACION MATEMÁTICA DE LA SEGUNDA FORMA NORMAL
Sea la relaciónjy^, . (T) una ocurrencia del esquerna^vyxT,c^/'>
tal que las dependencias funcionales f jr. : S. — * X.,
i = 1,2, m (siendo J ¡r -[J^r- \ )> están todas conecta
das entre sí, y además T = U (S.U X.
70
Sea T = US. y T0 = UX., P^ y O, son respectivamente,
los conjuntos de elementos principales y no principales de T.
Por p representaremos un elemento cualquiera de P y por q un ele
mento cualquiera de Q . Resulta evidente que, si todo elemento
de T? es principal, entonceSjJ^está en Segunda Forma Normal, ya
que, en ese caso (ver Corolario 5-5 en el Capitulo anterior)
P*. = T y Por tanto Q = 0 (existen sin embargo relaciones en Se
gunda Forma Normal en las que Q = 0)
Resulta asimismo fácil demostrar que, si K es una clave, en
tonces ningún subconjunto propio de K puede depender de otro sub-
conjunto propio de K, ya que, en caso de que así fuera, un subcon
junto propio de K implicaría T y K no podría ser clave.
En efecto: Sean K.. y K? dos subconjuntos propios diferentes
de una misma clave K. Las siguientes dependencias funcionales re
sultan evidentes (sin más que aplicar los Axiomas de reflexivi-
dad y proyectividad, respectivamente):
K - (K2 - Kj) — » K - (K2 - Kj) (1)
K - (K2 - Kj) — * Kj (2)
Supongamos que tiene lugar la dependencia :
Kj->K2 (3)
De (2) y (3), por la propiedad transitiva, se sigue que
K - (K2 - Kj) ». K2 (4)
Y de (1) y (4), por aditividad, resulta :
K - (K2 - Kj) ~ * K (5)
71
que por transitividad permite escribir :
K - (K„ - K1) - ^ T , lo que contradice el hecho de
que K sea clave. Luego debe ser !< ~—f~^. K? .
Como consecuencia, si con /Jo !**' ^i es ^a única clave
de<_y£(T), se tendrá que Q = T? f 0, así que J/L (T) no pue
de estar en Segunda Forma Normal, ya que tienen lugar las depen-
dencias funcionales ^ / . : S. ± X. con S. ci T, y
X- c. Q (en efecto, si fuese X. P. f 0, un subconjunto pro
pio de T1 dependería funcionalmente de otro subconjunto propio de
T-,» y ya hemos visto que esto no es posible al ser T. la clave).
Las anteriores reflexiones, conducen fácilmente a enunciar
los resultados siguientes:
Teorema 2-1
Si { T., T_ í constituye una partición de T, <^s? (T) no
está en Segunda Forma Normal.
Prueba :
En este caso, según el Corolario 5-7 (Capítulo Tercero),
Oú 02) T. es la única clave do^yZiT); de modo que 7 O ) no puede es
tar en Segunda Forma Normal.
Teorema 2-2
Si J? . : S.U tz ., \a . | ¿. 1, es la única clave
- 72
d&tJ^ÍT), y además Q f SÍ, entoncest_yl¿(T) no está en Segun
da Forma Normal.
Prueba :
Si S.U a. es la única clave de,_Xc(T), es obvio que
P, = S.U tz . . Ahora bien, al conjunto inicial de dependencias t i l r
funcionales pertenece la dependencia : S. —-v X.,
S. CL S.U & . (ya que 1^-1^.1» Por hipótesis).
Si X- c. S.U &., entonces la verificación de la dependen
cia funcional S. — **> X-, supone que un subconjunto propio de
una clave sea funcionalmente dependiente de otro subconjunto pro
pio de la misma clave, lo cual no es posible. Por tanto, debe ser
X. c Q., con lo cual Jyt(T) no está en Segunda Forma Normal.
Deduciremos a continuación la siguiente interesante propiedad,
como inmediata consecuencia de la definición de la Segunda Forma
Normal.
Propiedad 2-1
Si toda clave dej^/tl") consiste en un tributo simple^Jx¿(T)
está en Segunda Forma Normal. Esto es evidente ya que, en este ca
so, ninguna de las claves tiene un subconjunto propio del que pue
da ser dependiente algún atributo no principal.
Cuando en el Capitulo Segundo nos ocupamos de cómo podrían
- 73 -
determinarse las claves de una relación, vimos que éstas eran
siempre de la forma S.U &. , \ a . \ )> 0; para algún S., 1 T * 1 i -^ 1
implicante extraido del conjunto de dependencias asociado al es
quema de relación. Así pues, si S.U a. es una clave y si zi . ¿ i : S.cr. S. en el conjunto inicial de dependencias — J J i
funcionales, entonces S.U tz . = S.U ¿z., es también la mis-J J i i
ma clave ( es decir: Ya que las claves son subconjuntos mínimos,
por aumentación de S. y S. con descriptores diferentes, llegare-
mos a claves idénticas ).
En lo que sigue supondremos pues que si S.U a . es una cla
ve, S. (¿z S. \/j f i (en el conjunto original de dependencias
funcionales).
Lema 2-1
Si tiene lugar la dependencia funcional S. — ^ X. y el con
junto original de dependencias funcionales no existe ningún S.
tal que S - o S - , entonces, para cualquier S, a. S.. y S ? o T,
se tiene que S. -t-> S .
Prueba :
Razonemos por reducción al absurdo, suponiendo que tiene
lugar la dependencia funcional 5 -—e*S„ . En este caso (Propie
dad 7-1, Capítulo Tercero), ¿f , : S, £=L S,, de modo que : K K 1
Sk — $i C^ S., lo que contradice la hipótesis de en el con
junto original de dependencias funcionales S, <¿. S. \/ , f i .
74
Luego debe ser S1 -7 » S„.
A continuación exponemos unos Teoremas que constituyen otros
tantos casos particulares en el proceso de determinación del nivel
de normalización de una relación.
Teorema 2-3
Si toda clave &§~/¿{7) es un implicante S. del conjun to
inicial de dependencias funcionales, entoncejrxi. (T) está en Se
gunda Forma Normal.
Prueba
Si S. es una clave, para cualquier S.. <^ S. y S„cT,
Sj -++S2 (Lema 2-1)
Si q & Qt» hagamos S? = q. De nuevo tendremos (Lema 2-1
S- -H> q. Luego (T) está en Segunda Forma Normal.
Teorema 2-4
Si toda clave deJ^x(T) es de la forma S.U a ^ \&\<.}
</ . :S. c S.U a . se cum| ) 3 3 ^~ i i
T) está en Segunda Forma Normal
y si V,-:S. c SJJ a. se cumple que S. _y_>q; entonces
Prueba :
Si S c Sn.U * . y si S £, X es una dependencia
75 -
obtenida a partir del conjunto de dependencias inicialmente dado,
entonces 3 ^ : S. c: S (Propiedad 7-1, Capítulo Tercero). De mo
do que: S, c S cS.li a..
Pero S.U & . es una clave, asi que S cp. S. v/, f i,
y por tanto S <¡z S.. En consecuencia, o bien S = S., o S=S 1 1 K
para algún K i . Según esto, por la hipótesis del Teorema, S_¿_$,q,
así que si q £ Qt entonces q € X, por lo que con!uirnos afir
mando que<_J £(T) está en Segunda Forma Normal.
Para determinar si una cierta relación está o no en Segunda
Forma Normal, obsérvese que basta con considerar los dependencias
funcionales S. —*»• Y. que se deducen de la matriz de cierre cal-i i
culada sobre las dependencias S.—t*X. oriainales cuyos implican-i i J t
tes S. sean subconjuntos del conjunto P de elementos principales. 1 &
Esto es así ya que, si <_VY-(T) no está en Segunda Forma Normal,
existe al menos una clave, por ejemplo S.U ¿z ., tal que S c S.U
a . y S — > q, q £ Qt.
Por tanto, según la propiedad 7-1 (ver Capítulo Tercero),
3 • i S.U b. = S. Pero S c P,, ya que S es subconjunto de J. J J t J M
una clave, de modo que : S. c: Se P .
Sea T. el conjunto de atributos de T, tales que S.U b.—> T. J M J J J
Para encontrar T., hay aue hallar el cierre del descriptor S.U b.
con respecto al conjunto =-¿^de dependencias funcionales corres
pondientes al esquema dado. Ya vimos (Capítulo Primero), que el
Algoritmo de cálculo del cierre de un descriptor respecto de un
- 76 -
conjunto de dependencias dado, procede por pasos sucesivos,
que aquí resumimos así :
S.U b . — H , ., S.U b. >T 0., S.U b. — *>T . = T.
Si para algún K se verifica : S. cfc P y J3 .:
S, cr S. U b.U T.. , entonces S,ch.S.U b., ya que K J J 1J K"r~" J J
S.U b. cz P , por lo cual T.. C\ S, f 0. De aquí que tenga J J t IJ K que existir q 6 Qt tal que: q £ (T . n S
R ) -
En conclusión, si S. g£ P, , ^ .: S, cS.Ub.UT.. .
excepto si S = S.U b.—> q, en cuyo caso<_y¿(T) no está en Segun
da Forma Normal ya que S —>q, y S, no se necesita.
Exponemos a continuación una condición cuya verificación ase
gura que<Jy¿CT) está en Segunda Forma Normal (condición suficiente]
Corolario 2-1
Sea K una clave arbitraria de (T). Si y..: S. ,- Pt,
S. f K; se cumple que S.+*^ (siendo q, tal como hemos venido
considerando, un elemento arbitrario de Q ), entonces_v?T(T) es
tá en Segunda Forma Normal.
Prueba :
Acabamos de ver cómo para determinar si una cierta relación
t"T) está o no en Segunda Forma Normal, basta con considerar
- 77 -
las dependencias funcionales S. > Y. der/ en ^as clue
S. c: Pf. Si S. cr P.,., entonces S._y-^q, excepto en el caso
de que se trate de una clave (hipótesis del Corolario ). Pero,
si S. es una clave, s/ . ^ i S. cfz S.. Además siendo K i
y continuando en el supuesto de que S. sea clave, si S, U a r,
{¿z. | ^ 1 también lo es, y si S = S.U b, , b. <r a. ,
entonces S. dz S.U Y, U b, , ya que, en caso contrario S.U b, — ^ T 1 "i**— K t\ K K K
(ya que S. es clave) y S.U a , no podría ser una clave. Por tan
to, si SkU b, —t> q, tomando el cierre transitivo de S.U b. res
pecto dejs. — * Y.l(S. c P ), tiene que llegarse a determinar
la existencia de S. c. p (j f k, S. f K), tal que S. —%, q . J ** J J
Pero S. — * q , S. f K, contradice la hipótesis del Corolario; lúe-J J
go S.U bk"/*q; y podemos afirmar queJ//(T) está en Segunda For
ma Normal.
Ejemplos:
Sea el esquema de relación definido por
T = ( A , B, C, D, E^
A B > C
CE * D
AD :» B
Las claves son : A B E, A D E, A C E; por lo tanto:
Px = T, Q = 0. Así pues, por definición^Jí/¡^Tv^/''>está
en Segunda Forma Normal
78 -
- Sea el esquema de relación definido por
T = (A, B, C, D \
tzf: A B —* D
D . > A
C — & . A D
La única clave es BC. Por tanto: P = B C y Q = A D.
Luego, por e
Forma Normal.
1 Teorema 2-4<J^í^T,J¿'fj>no está en Según da
- Sea el esquema de relación definido por
T - \ A, B, C, D, E, F \
¿f: A B . » C D
A C - * B E F
D F ^ A E
B E -fr D C
Las claves son : AB, AC, BEF, BDF, CDF. Por lo tanto :
Pt = T y Q. = 0 . Así pues, por definición^^^^T, J^/^no está
en Segunda Forma Normal.
79
3. ALGORITMO PARA ESTABLECER SI UN CIERTO ESQUEMA DE RELACIÓN
ESTA O NO EN SEGUNDA FORMA NORMAL.
Este Algoritmo resume y utiliza todos los resultados anterio
res.
Emplearemos la notación siguiente:
Y = S. / ( S . c r P j , ( S. -*,X.) es una de-
pendencia funcional dadaj .
Z C = i Si / ( Si U *i> es c 1 a v e ) l«¡l * l í
(Es obvio que £ c £ 21 p )
l ^ c l = c
El conjunto de dependencias funcionales definidas en el es
quema es :
\T: S, -w ^ • .,- — Xi , i = 1, 2 -
El subconjunto constituido por aquéllas dependencias cuyos
implicantes pertenezcan a JT :
\SC\* i = I- 2, H_p ( np ¿ m)
80
Habiendo ordenado ambos conjuntos de forma tal que :
Sl' Sk é ^o) V 1 ^ K < n.
Si S. e ^ c Y si S. G ( p - ^ c ) , entonceí J ' *- P
i < 3-
& \ En el Algoritmo el cierre se calcula respecto de /<__
i = 1,2 K- . excepto en el cálculo de CJ? (punto II),
I <CY I que se realiza sobre í, yr. y i = 1,2, m.
r
Por N \y¡) » representaremos simbólicamente el nivel de
normalización dej/¿, que puede tomar el valor 2 (Segunda Forma
Normal) ó 1 (Primera Forma Normal)
Algoritmo
I - N (J^j = 2
II - Calcular claves de ver Capítulo Segundo)
Hallar Pt, Qt , Z p, Z Q
III - Si Q = 5?, acabar Algoritmo . (ya vimos que si
Qt = 0 , N t(9l) = 2 )
IV - Si <2~. - 0 , acabar Algoritmo, (ya que entonces
toda clave deJ^x¿(T) es una de las originales S.,
y ya vimos cómo en este caso, N ¿yZ ) =2 )
81
Si Q. H y T i 0, hay que averiguar si al t c
gún subconjunto propio de una clave implica q:
¿ ~-{ • : 1 ^ i í H, , para el que S—t» q ?
En caso afirmativo, N kyi) = 1- Acabar Algoritmo
En caso contrario :
Si V : S.U fí . es clave, se tiene que \a. 1 ¿ 1,
Acabar Algoritmo (ver Teorema 2-4)
En caso contrario :
1. - i = o
2. - i - i + 1
3. - ¿ i > n c ?
En caso afirmativo : Acabar Algoritmo
En caso contrario:
J J ^ p
¿ (S.CZ S.U Y.U ^.) A ( <z.. = S.t\<*-.? 0) *
( ^-j 1 a .) ?
En caso negativo : Siguiente j
En caso afirmativo:
Calcular (S.U a. .) + con respecto ai y: '\ y
Fin
1
¿Tiene luegar la denendencia S.U «..-^o ?
En caso afirmativo : N ¿^/i) = 1
Acabar Algoritmo
En caso negativo : siguiente j.
5. Ir a VII.2
82
4. CARACTERIZACIÓN MATEMÁTICA DE LA TERCERA FORMA NORMAL.
En el Capitulo Segundo hemos dado la definición de Tercera
Forma Normal. Teniendo en cuenta esta definición a continuación
formalizamos sus propiedades matemáticas en un conjunto de Lemas
y Teoremas.
Teorema 4 - 1
Dada una relaciónt-^¿(T) (no necesariamente en Tercera For
ma Normal ), si los descriptores K1 y K son ambos claves de la
misma relación entonces tienen una mutua dependencia funcional
completa :
Kj <==z> K2
Prueba :
Es evidente que tiene lugar la dependencia funcional :
K1 • s» K„, ya que K.. es clave. Si esta dependencia no es com
pleta 3 S, c=_ K1 : S, t, K„. Pero ya que K? es clave,
por transitividad tiene entonces lugar la dependencia:
S, •—í> T, y ya que S¿ cz. K., K. no puede ser
clave. Debe ser por tanto:
Razonando análogamente a partir de la dependencia funcional
evidente:
83
K9 - > K1 llegaríamos a establecer que dicha de
pendencia funcional debe ser completa; de donde resulta que :
Lema 4 - l
S¿^j(T) es una relación en Tercera Forma Normal, todo atri
buto no principal depende de sí mismo, de las claves y eventual-
mente de descriptores cuya intersección como P, (conjunto de los
atributos principales ) es no vacia:
Prueba :
Sean q, y q9 elementos arbitrarios de Qf. Si K es cla
ve, por definición se tendrá que : K — * q, , K •—*• q,,.
Ahora bien, ya quec_J/7;(T) está también en Segunda Forma
Normal, se tiene que K r=>q., K rrr>q„.
Además q, > q. (reflexividad). Si q, * q9, enton
ces, ya que q,, q? y K son disjuntos, y puesto que k — * q,--> o
(transitividad) llegamos a una contradicción respecto a la hipó
tesis de que£/2 ("O esté en Tercera Forma Normal. Por tanto :
qx —f^ qr
Mediante un ejemplo (ver más adelante en este mismo Capítu
lo), veremos que pueden existir subconjunto S tales que :
- 84
S n Pt f 0 y S __*. q2 ó S _.^ q2
Cualquier otra dependencia contradeciría la definición de
Tercera Forma Normal.
Teorema 4 - 2
Una relaciórf/2;(T) en Segunda Forma Normal, esta en Terce-
cera Forma Normal si y sólo si para dos subconjuntos propios
cualesquiera no vacios y disjuntos, S y S?, de Q,, se verifica:
Sj —/-;> S2, S2 —/-* S r
Prueba :
- Condición necesaria -
Si i~/j{^) está en Tercera Forma Normal, ningún atributo
no principal depende transitivamente de ningún descriptor que sea
clave de la relación. Si S.—e> S?, entonces se verifica
K ^ S1 •—•& S„ (siendo K una clave). Pero K, S y S_ son dis
juntos, de modo que la anterior dependencia contradice la hipóte
sis de qu esté de Tercera Forma Normal. Así pues, S,-H>S9
( y S„—f* S,, resultado que puede establecerse sin más que razo
nar análogamente partiendo del supuesto de que S „ — & S,).
Condición suficiente
Si S, -/-* S„ y S _y_&, S1 , entonces S.. y S? son sólo de-
pendientes de sí mismos de las claves y de descriptores cuya
intersección con Pf es no vacia (ver Lema 4-1). Ahora bien, en
cualquiera de estos casos, es fácilmente demostrable que S. y S
no depende transitivamente de ninguna clave de^/2(T) (véase en
el Capítulo Primero la definición de dependencia funcional tran
sitiva ). Luego<_>/AT) está en Tercera Forma Normal.
Corolario 4 - 1
O/? Si todo atributo de UX. es principal, entonces<><¿(T) está
en Tercera Forma Normal.
Prueba :
Si UX. c= P. , entonces P = T y Q = 0 (ver Corolario
5-5, en el Capítulo Tercero). Ya que no hay atributos no princi
pa les c/2( "O está en Tercera Forma Normal.
Corolario 4 - 2
Sit^^T) está en Segunda Forma Normal y 1 Q 1 = 1 , enton-
ces<y¿(T) está en Tercera Forma Normal.
Prueba:
Si Q = 1, no hay que Q. subconjuntos propios disjuntos,
luego, según el Teorema 4-2 ^/^T) está en Tercera Forma Normal
86
Teorema 4 - 3
Si S c Q . , entonces S-y-*-p . \/ p £ P
Prueba
Supongamos que S —s»p. Al ser p principal, es miembro de
digamos S. U ¿z., \a . í >. 0. al menos una clave deC/¿(T), digamos S. U a., \a . j
Sea M = (S.U ^.) - o; se ti
clave ya que S.U & . lo es
Sea M = (S.U ¿z.) - o; se tiene que M c S.U ¿z. y M no es
Portante SUM —*• pUM = S.U a. —*>T, por adit.ividad y tran-
sitividad. Pero SUM -»T y SUM no es superconjunto de ninguna
clave, ya que SH P = 0. Por lo tanto SUM es clave, o sea :
S SL P . Pero esto contradice la hipótesis de partida, según la
cual S £L Q . Luego, S -f^p.
Teorema 4 - 4
Una relación en Segunda Forma Nomral está en Torcera Forma
Normal si y sólo si S.A P f 0 , y ..
Prueba :
- Condición necesaria -
Supongamos quec/¿(T) está en Tercera Forma Normal. Si para
algún i se tiene que S. f\ P = (?, entonces S. c-Q , de modo que
87
v/ c. P. , S. -*-» P (ver Teorema 4-3). Siendo S. —»X. v p ~ t i i i
una dependencia funcional del conjunto correspondiente del esque
ma de relación, debe ser (S.U X.) c Q En efecto, ya hemos
visto cómo S.cQ . Si X. f) P. i 0, para algún p £ (X.flPJ
se cumpliría : S. —=* X. => P (por proyectividad y transitivi-
dad). Pero la dependencia S.—*P contradice el Teorema 4-3
al ser S. c Q t - Luego , X. c= Q, y, por tanto, (S..U X.)cQ
Por el Teorema 4-2, en este cascc/¿(T) no puede estar en
Tercera Forma Normal, ya que S.—> X., S. O X. = 0 y (S.UX.. ) c
Q. contradice la hipótesis de o.xx^y) (T') esté en Tercera Forma
Norma 1. Por lo tanto debe ser S. ñ P f 0, j .
- Condición suficiente -
Supongamos S. f\ P. f 0 y .. Si j Q \ . 2, sean S, y S„
dos subconjuntos propios no vacios, disjuntos , de Q . Si S.—>S ,
"3. : S, D S. (ver Propiedad 7-1, Capítulo Tercero). Por lo —* i i — i
tanto : Si c S. C Qt de modo que S. O p
t = 0 ya que P (1 Q =0.
Luego , con S. y S9 arbitrarios y disjuntos, S.-f- S„, así que
(T) está en Tercera Forma Normal (ver Teorema 4-2)
5. ALGORITMO PARA ESTABLECER SI UN CIERTO ESQUEMA DE RELACIÓN
ESTA 0 NO EN TERCERA FORMA NORMAL.
I - Establecer sí el esquema dado está o no en Segunda
Forma Normal - Hallar P y Q
II - Si no está en Segunda Forma Normal, ir a V
En caso contrario, ir a III.
III Si "3 . : S. c (1 , ir a V. En caso contrario, ir a
IV.
IV - El esquema está en Tercera Forma Normal - FIN DEL
ALGORITMO.
V - El esquema no está en Tercera Forma Normal - FIN DEL
ALGORITMO.
Ejemplo :
Sea el esquema de relación definida así :
T = \ A,B,C,D,E,F(
J^f7: AB —» CD; BE — > AF; DE — * BC; BD —-*A
Las claves son : BE, DE. Por lo tanto :
P = BDE y Q = ACF (obsérvese que BE <j=> DE)
En virtud del Teorema 2-3 <^/¿< T,C/>está en Segunda Forma
Normal. Por aplicación del Algoritmo correspondiente, comprobamos
que también está en Tercera Forma Normal.
Obsérvese también que BDO P f 0, BD—* A y A es no prin
cipal. Esto sirve como comprobación de lo que afirmamos anterior
mente en el Lema 4-1. (en una relación en Tercera Forma Normal
pueden tener lugar dependencias del tipo S—>q a condición de que
C A P I T U L O V
SÍNTESIS DE ESQUEMAS EN TERCERA FORMA NORMAL
1. INTRODUCCIÓN
Los Capítulos Segundo, Tercero y Cuarto, constituyen el nú
cleo fundamental de nuestro trabajo: Partiendo de los Axiomas de
Armstrong, hemos enunciado y demostrado un Conjunto de Lemas y
Teoremas sobre los que hemos construido Algoritmos de búsqueda de
claves y de caracterización del nivel de normalización de una re
lación. Este es por tanto un enfoque analítico del problema.
Sin embargo, hemos considerado interesante presentar aquí otra
forma de abordarlo; es el enfoque desde el punto de vista de sín
tesis.
El problema de la síntesis de Bases de Datos lógicas, puede
considerarse como el de convertir e'l .conocimiento que el usuario
posee acerca de un conjunto de datos en un modelo lógico. Concre
tamente : Dado un universo T de atributos y un Conjunto res
tricciones (dependencias funcionales), construir un esquema de
relación que esté en Tercera Forma Normal. Intuitivamente, la so
lución puede no ser única. Como criterio de diseño, añadiremos
el que dicho esquema contenga el mínimo número de relaciones.
Este Capítulo se basa en los trabajos de W. Cheng [19] ,
P. Bernstein T8] , y Bernstein et al. [101 , especialmente en
el segundo de los trabajos mencionados, de donde hemos tomado los
- 90 -
dos Algoritmos de Síntesis que incluiremos más adelante.
reci-
com-
2. CONCEPTOS PREVIOS: RECUBRIMIENTO MÍNIMO Y CONEXIÓN MÚLTI
PLE ENTRE ATRIBUTOS.
2.1. Recubrimiento mínimo
^eanj2/j y Jy/p dos conjuntos de dependencias funciona
les. Decimos que son equivalentes siO^j ~Sy? • ^'«-¿"i
y ¡S/n son equivalentes, decimos §ue_y-/K recubre &J^/n (y
procamente ). Para cada dependencia ^ : Y —» Z, ^^ (-/?
pruébese ^j/Z^y? calculando-el cierre Y de Y respecto
de <-¿I y luego comprobando si Z C y , Si j ? y € y\ '•
yfc £ (y^ , entonces Jy\ f C ^ • Si por el contrario,
y^ c yTV^^^T'p es fácil demostrar que cualquier dependencia
funcional perteneciente a ^ / , está también en <->/? (ver [31J)
Del mismo modo, si todo elemento de V i está presente en J^¿\ >
entonces todo elemento de^-fK, también pertenecerá a\}y 1 . Po
demos pues concluir afirmando que «J^i ^«¿p son equivalente
si y sólo si toda dependencia de O ^ está en C^p y toda depen
dencia O ^ p está en 0 ^ | .
Lema 2-1-1
Todo conjunto ¿^de dependencias funcionales está recubierto
por un conjuntq^^ftal que ningún miembro de la derecha tiene
más de un elemento.
-91 "
Prueba :
Sea<^/¿Zel conjunto de dependencias de la forma X—*A., tal
q u e ^ J ^ T X -* Y ^ ^ €-<i¿í A. € Y. Es evidente que
X — > A. se deduce de X — * Y por proyectividad. Por lo tanto :
C ^ + . Ahora b i e n í e ^ / s / ^ ;+ y a que Y = A} A2 — A ^
por lo que X —>Y puede obtenerse a partir del conjunto de depen
dencias: X A v X — » A, A , por aditividad. n
Luego debe ser '-^¿^ " = J/f
Un conjunto de dependencias se dice que es mínimo si:
- Todo miembro a la derecha del signo de implicación es un
atributo simple.
No hay en ^^f ninguna dependencia X-»A tal que
^^¿^- i X —> A sea equivalente &s¿
- No hay en ^^/ninguna dependencia X—»A, ni existe nin
gún subconjunto propio de X, Z, tales que :
X •—» A] -f-j Z —> A y sea equivalente a
La segunda condición garantiza que ninguna dependencia de
^^ es redundante y la ultima garantiza que ningún implicante es
redundante.
- 92 -
Teorema 2-1-1
Todo conjunto^^/. de dependencias, equivale a un conjunto
que es mínimo.
Prueba
Supongamos que ningún miembro a la derecha del signo de im
plicación en el conjunto^/I tiene más de un atributo. Para satis
facer la segunda condición de recubrimiento mínimo, consideremos
cada dependencia X —* Y der-H/, en el mismo orden, y, si
S^- \ X —> Y| equivale a O ^ s e suprime la dependencia en
cuestión. (Obsérvese que si se consideran las dependencias en ór
denes diferentes se llega a la eliminación de distintos grupos de
dependencias ).
Ejemplo :
Sea el conjunto J ¿ : AB — » C
C » A
BC , D
ACD » B
Equivale a : AB * C
C ^ A
BC > D
ACD * B
D
BE
CG
CE
D
D
BE
CG
CG
CE
CE
— »
=r
>
»
>
»
•>
>
,
1
EG
C
BD
AG
E
G
C
B
D
A
G
- 93 -
Dependencias redundantes : CE > A (ya que C — * A )
CG -—=» B (ya que puede dedu
cirse de CG —^ D, C -—> A y
ACD —-> B)
Además, y ya que C >A,, la dependencia ACD -—>B puede
sustituirse por CD —* B
El conjunto de dependencias queda así
Jf: AB _ r
BC
en
D
D
BE
CG
CE
/
>
>
— • >
A
D
B
F
G
C
D
G
Y esta solución no es única.
2.2. Conexión múltiple entre atributos
Tiene lugar cuando a un conjunto de valores de A correspon
de un conjunto de valores de B. Esta conexión múltiple se repre
senta mediante una dependencia funcional del siguiente modo:
5^7 AB _* 9 9 es un atributo que toma sus valores en el dominio í 0,1j
- 94
Para cada elemento (a,b)£ Dominio (A) X Dominio (B), -
, y\z., b) = 1 si y solo si a y b están relacionadas bajo^*'.
(Este concepto se extiende fácilmente a cualquier número de atri
butos) .
3. SEMÁNTICA DE LAS DEPENDENCIAS FUNCIONALES
Las dependencias funcionales que van a constituir la entra
da del Algoritmo de síntesis satisfacen no sólo los Axiomas de
Armstrong, sino también la suposición de unicidad, esto es : Si
dos dependencias funcionales^/T y t jTT tienen iguales sus
implicantes y sus segundos miembros, entonces ^ y = yfr?.
4. PROCEDIMIENTO DE SÍNTESIS.
4.1. Descripción del Algoritmo
Diremos que un atributo A. es extraño en una dependencia
funcional ^jf\ A. A„ A A > Y , si 1 ¿ i p
Aj — A.^ A.+1 ---- Ap _ » Y pertenece a C / ^ •
La eliminación previa de atributos extraños, ayuda a evitar depen
dencias parciales y superclaves (descriptores que incluyen claves'
Si dos relaciones tienen claves que dependen funcionalmente
la una de la otra (claves equivalentes), ambas relaciones pueden
sintetizarse conjuntamente. Esto puede realizarse agrupando las
95 -
dependencias funcionales cuyos implicantes sean equivalentes.
El Algoritmo de síntesis queda pues como sigue
Primer Algoritmo de Síntesis :
Eliminar los atributos extraños en los implicantes
de cada dependencia funcional de^,/, obteniendo
el Conjuntq_y^ (la eliminación de atributos extra
ños no altera el cierre del conjunto de dependen
cias ).
II - Hallar un recubrimiento mínimo do y ' 1
III - Dividi£/^¿en grupos tales que todas las dependen
cias de cada grupo tengan los mismos implicantes.
IV - Unir los grupos cuyos implicantes sean equivalentes.
V - Para cada grupo,construir una relación consisten
te en todos los atributos que aparecen en ese gru
po. Todo implicante que aparezca en cualquier de
pendencia del grupo, es una clave de la relación.
El conjunto de todas las relaciones así construi
das, constituyen un esquema para el conjunto de
dependencias dado.
96
4.2. Conexiones múltiples entre atributos
Para representar una conexión múltiple entre atributos
(atributos que escribiremos abreviadamente como el descriptor X),
introdujimos la notación de dependencia funcional :r ^r : X—> 9.
En [8] se demuestra el Lema siguiente :
Lema 4-2-1
Si X —* 9 pertenece al conjunto de dependencias funcionales
r^¿, entonces, para cualquier recubrimiento minimgy^^de,^^ o
bien X —¡» 9 pertenece a Jw Y — * 9 pertenece a
siendo X e Y descriptores equivalentes.
Esto garantiza que las conexiones múltiples (no funcionales)
entre atributos, siguen teniendo lugar en el esquema sintetizado
en la misma forma en que se habian especificado en el conjunto ori
ginal de dependencias funcionales.
5. ESQUEMAS EN TERCERA FORMA NORMAL
5.1. Si en el Algoritmo de síntesis anteriormente expuesto se
suprime el paso IV (Agrupación de claves equivalentes),
las relaciones resultantes están en Tercera Forma Normal.
En [8j se encuentra la prueba del siguiente Lema :
- 97 -
Lema 5-1-1
Sear-^/un conjunto de dependencias funcionales y sea
O, 3? = X Y una de tales dependencias. Si L(-frn'- V—•=» W
está en^ / y ^S se usa para alguna derivación de £jf¿ a
partir d e ^ ¿ , entonces V — > X está e n O ^ .
Teorema 5-1-1
Sea (A.,, A„,
ción al conjunto
A ) una relación sintetizada por aplica-ir * '
de dependencias los pasos I, II, íII y V
_depende t ran
sitivamente de ninguna clave deC/Z(esto es. 'C/zestá en Tercera
Forma Normal )
del Algoritmo. Ningún atributo no principal
tve deC/2(e
Prueba :
Supongamos que A. es no principal y depende transitivamen
te de una clave K de/2- Esto es : Hay un descriptor
X ^iv A, A \ tal que :
K
X
X
A . i
í, X
- ^ K
. >, A .
i *
Sea Z la clave dec/Zque aparece como implicante en el con
junto de dependencias usado en la síntesis d e / / Z —-> X
- 98
está e n ^ " , ya que Z es clave de Q/¿ . Además X — / -> Z,
ya que si X •—>Z entonces X — » Z y Z — > K implicarían X „l-
contradiciendo el hecho de que X •+->» K (en la hipótesis de depen
dencia transitiva). Por tanto-, X -*-* Z, Z . > X y X ,. A.
(que constituye una dependencia transitiva).
Sea^/^el recubrimiento mínimo d e ^ , calculado en el
Algoritmo de síntesis. Demostraremos que Z—>A. (que aparece en
) es redundante. Para ello basta con mostrar que 1-—>X y
X —» A. pueden ambas derivarse &%yft¿ — \ Z — > A . \ . Ya que
las únicas dependencias usadas en la síntesis áeQ^/¿sor\ de la for
ma Z—»A., Z — * X, tiene que pertenecer a^^fi/X, £. X.
Como A. £ X, Z — ^ X, está en íy$t — \ l —> A. \
Supongamos ahora que X —»A. puede derivarse de Z — ? A..
Entonces (ver Lema 5-1-1) debe tener lugar la dependencia X — > Z
(dependencia transitiva ). De modo que X—>A. debe poder dedu
cirse sin usar Z — » A.. i
Ya que Z — * X y X •—•? A. pueden derivarse 1 -* A.},
se tiene que Z —?h. es redundante e^/Oy* lo cual contradice el
hecho de que^/^/ es un recubrimiento mínimo. Luego, concluimos
que no puede tener lugar la dependencia transitiva.
5.2. Decimosque un atributo A satisface la propiedad jyen la re
lación c/7 , si la siguiente proposición es cierta.
99
Sea /// el recubrimiento mínimo hallado en el paso II
del Primer Algoritmo de Síntesis. Si K — ) A está ex\^///y se
usa para sintetizare//; para cualquier atributo principal de
Si, B, la dependencia K —» B puede derivarse sin usar
K _^ A (puede derivarse a partir de ///- \ K —>A \
Teorema 5-2-1
Seac/¿{h,, A A ) una de las relaciones sintetizadas
usando el Primer Algoritmo de Síntesis a partir de un conjunto
Jarcie dependencias. Si todos los atributos no principales de,
satisfacen la propiedad (_^y, entonces c/¿ está en Tercera Forma
Normal.
Prueba :
Sea A. un atributo no principal de£//que dependa transiti
vamente de una clave Y áeQy¿. Esto es : Existe un descriptor
Z c | Aj, A2, , A ] tal que Y — y Z, Z -t~> Y y Z —»A.,
A. i I.
Sea 1 recubrimiento mínimo calculado en el Primer Al
goritmo de Síntesis. Sea K una clave tal que la dependencia :
«_/f K —frA. está en ^ f .
Ya que K es una clave, K —> 1. Además Z ....., -> K, ya que
si Z — > K, entonces Z „ > K y K > Y implicarían Z . >, Y,
- 100
lo que es una contradicción. Así que tenemos una dependencia
transitiva: K — > Z, Z -*-» K y Z — > A..
Ahora demostraremos que K — » Z y 1-a, A. pertenecen a
( t/VZ - | K-» A. } ) , y es por tanto redundante (lo que
entra en contradicción con el hecho de que sea un recubrimiento
mínimo). En efecto : Sea Z = B.. , .... B i.
Distinguiremos dos casos : si B. es principal, la pro-
piedad ^Vgarantiza que K _^ B. se puede derivar sin usar
K _> A.. Si B. es no principal, existe una dependencia fun
cional K' __> B. que permite incluir a B. en el conjunto de atri
butos d&cs¿ • Ya que K —> K' es derivable (propiedadl/J
a partor de | K-»A.J^ y K' - ^ B pertenece a (jfí-
{ K —9 A.} j se tiene que K' T B. es derivable sin el uso de
K_^,A. . Por tanto, K __• Z está en [/0£- \ K —* A - ) ) +-
Supongamos ahora que Z _^A. usa la dependencia K _^ A.
en su derivación. Entonces (ver Lema 5-1-1), tiene lugar la
dependencia K ^ Z, contradiciendo la suposición de dependencia
transitiva. Luego Z . ? A. pertenece a ( jtff- <K _^ A.t ) .
Las dependencias K_J> Z y Z -^ A. pertenecen a [/yf~
\ K — > A. [ ) , luego ^ / e s redundante, lo que se contradice
con el hecho de que sea un recubrimiento mínimo. Concluiremos
por tanto que no puede tener lugar dependencia transitiva.
5.3. Eliminación de dependencias transitivas.
101
Teorema 5-3-1
Sea R, (A,, A ) una relación del conjunto
i,,/i,, tv/vl r > sintetizado empleando el Primer Algo-
ritmo de Síntesis. Seg/^el conjunto de dependencias funcionales
implícitas en y luna dependencia implícita en una relación Qy¿.
es una dependencia X—»A, siendo X una clave y A un atributo sim
ple). Sea A. un atributo de^/^k 9ue n 0 aparece en ninguna de las
claves sintetizadas dec/7., y es transitivamente dependiente
~ k á? de una clave dec/?»- Si eliminamos A. d e C / Z resul ta una nue-^ ¿K i k ¿O-
:iónc/2u va relaciónc/¿7 y en el nuevo conjunto de relaciones sintetiza
das:
' (« *? . - - - ^ ' , - - - ^ ¡ se tiene que el cierre de las dependencias implícitas en él es
igual a ^ .
Prueba :
Supongamos que A. se elimina ent/¿,. Ya que no aparece en
ninguna clave sintetizada, su supresión puede sólo afectar a las
dependencias implícitas de la forma X —*A., donde X es una cla
ve sintetizada deo/¿, . Sea /// el conjunto de dependencias
implícitas de ~r . Si demostramos que toda dependencia X—=>A.
está en ( y / f f , entonces^^= Ó^lf'J' * En e f e c t 0 : Si Ai
depende transitivamente de cualquier clave de/yí., entonces, de
pende transitivamente de todas ellas. Ya que X es una clave,
X—>V, V -/^X; y si V—>A., A. £ V. Esto constituye una
- 102 -
dependencia transitiva.
Ya que A. ¿ V, la dependencia X—>V sigue implícita en
t / ¿ \ , aunque A. se suprima. Luego X — » V , sigue presente en
'JA-*
Para demostrar que ^ V . ^ A. \ r 'yffl J, Y/\+ demostrare
mos que V — > A. no puede usar ninguna dependencia de la for
ma X —¡»A. en su derivación. En efecto, esto se sigue direc-
tamente del hecho de que si X . * A. se usa en la derivación de
V . ? A . , entonces (ver Lema 5-1-1), debe ser V _ •> X, lo que
contradice el supuesto de que Vy.» X, que tiene que tener lugar
si debe existir dependencia transitiva.
'/1 **
Ya que X __, V y V _^A. están en [^Jpf /, X — > A.
está en /^"Por tanto : j j f * ^ ' ) *
Podemos ahora modificar el Primer Algoritmo de Síntesis
para obtener relaciones que estén en Tercera Forma Normal.
Sea recubrimiento mínimo calculado y ^ r e l conjunto
de dependencias X —^ Y, siendo X e Y claves equivalentes, (ver
paso IV del Algoritmo). Sea Z — > A. , una dependencia
implícita Q^cy¿^ de modo que A. es no principal y depende tran
sitivamente de una clave d e ( / ¿ , . El Teorema 5. 3. 1.
que acabamos de ver nos permite afirmar que-Z—> A. es re
dundante, esto es : { Z -» A. } fc {^0*¿71- \ z —* Ai\)
Así pues, la eliminación de las dependencias de la forma Z-*A.
- 103 -
+
cuyo miembro derecho no forma parte de ninguna clave sinteti
zada y tales que : 1 Z -* A.} £ y > ^ J ^ ( l -» A. ) ) '* nos
asegura la eliminación de cualquier dependencia transitiva. El
siguiente Algoritmo sintetiza relaciones en Tercera Forma Normal
Segundo Algoritmo de Síntesis
Sea^jTel conjunto dado de dependencias funcionales.
Eliminar los atributos extraños existentes en los
implicantes de cada dependencia funcional de ^/,
(Un atributo es extraño si su supresión no altera el
cierre del conjunto de dependencias funcionales).
II - Hallar un recubrimiento mínimo de Sf„
III- Dividir^/^X en grupos tales que todas las dependen
cias de cada grupo tengan idéntico implicante.
IV JT¿ Para cada dos grupos y//- yypf- c o n implicantes X
e Y respectivamente, tales que X¿—> Y; in t roduc i r
en ¡^7£las dependencias X —> Y, Y .—> X y asociar
dichos g r u p o s ^ ^ J , ^ - y y j
Borrar de ^ / ^ f t o d a dependencia X __&A, ta l que A£Y.
Borrar de ¡/v¿ toda dependencia Y _ ^ B , ta l que Be.X
V - Hal lar un s u b c o n j u n t o ^ / ^ ^ y ^ f t a l Que :
¿/fz "^{yC^ \jWC "^¿/C^ y ningún subconjunto propio
de £ / ^ £ t iene esta propiedad.
- 104
Incluir cada dependencia de/^xén su correspondiente
grupo áe^ypf. (Un Algoritmo que permite encontrar
tal subconjunto ha sido desarrollado por Bernstein et
al. [10J ).
VI - Para cada grupo, construir una relación consistente en
todos los atributos que aparecen en el mismo. Cada
conjunto de atributos que aparezca a la izquierda de
cualquier dependencia del grupo, es una clave de la
relación. (El paso I asegura que ninguno de tales
conjuntos contiene atributos redundantes.)
6. MINIMIZACION DEL NUMERO DE RELACIONES SINTETIZADAS
Comprobemos que todos los recubrimientos mínimos producen
el mismo número de relaciones sintetizadas.
Lema 6-1
Sean , ^ y # dos recubrimientos del mismo
conjuntoJ¿/ae dependencias funcionales, de modo que^^rj 7//yo •
Si y¿s : X — > A está en^/^/ ,, entonces existe una
^ " : Í ^ B con J ^ ~ £ ^ % y con {Y —> X ) y
(X ._» Y)pertenecientes a jfí¿, •
Prueba
Si J ^ f y / ' - X T entonces j f ^ f .
- 105 -
así que también estará e «J?;.
Si ningún <&r
requiere .,v-,v. 1 para su derivación e n j / ,
'ivación para^^T' ex\cy^¿. sin más que
reproducir su derivación ^^/^¿7 y sustituir cada ^jn' por un
(~¥í derivado e n ^ ^ . . Ya que esta derivación no utiliza a
yf-> t^f"sería redundante en^f^ > lo que se contradice con
el hecho de que/^/T sea un recubrimiento mínimo.
podemos construir una deri
Asi que al menos un ^/Z necesitara ^ T e n su d erivacion
Supongamos q ue^Jj T : Y —> B precisa ^ , : X — f A en su
derivación ^^/y¿^ • Entonces Y —» X (Lema 5-1-1). Del mismo
modo, y ya que Qraparece en la derivación de ^ ^ e n / ^ ?
X >Y Por t a n t o ^ V : Y > B está en
y X v Y , completando la prueba.
2' con X
Teorema 6 - 1
Sea cJ^un conjunto de dependencias funcionales. Dos recu
brimientos mínimos cualesquiera de<=2^producirán el mismo número
de relaciones al aplicar el Segundo Algoritmo de Síntesis.
Prueba :
Se a n / ^ ^ y ¿Jr^ ¿ dos recubrimientos mínimos cualesquie
ra . El Lema 6-1 asegura que s i Qtf~ : X * A está e
entonces existe una dependencia iQfá : Y _ V B e n / ^ £ ? > con
- 106
Y > X y X —3» Y . Asi pues, para cualquier grupo de
dependencias funcionales con implicantes funcionalmente equiva
lentes, tiene que existir en^/o otro grupo que tiene los mis
mos implicantes funcionalmente equivalentes. Ya que cada grupo
genera una relación, y^\ y ///? generan el mismo número de re
laciones.
Corolario 6-1
Sea yün conjunto de relaciones sintetizado a partir del
conjunto de dependencias mediante el Segundo Algoritmo de
Síntesis. Sea otro conjunto cualquiera sintetizado a par
tir de un recubrimiento de . Entonces \( >
Prueba
Sea^/yc^T/Vun recubrimiento mínimo de ^ /f- ¿/re gen era
rá mediante el Segundo Algoritmo de Síntesis, un número de rela-
C ciones no superior al d^jy . Además, por el Teorema 6-1, el
Segundo Algoritmo de Síntesis generará el mismo número de reía-
G ciones a partir de ^¿^ó| a partir de^yf. Por lo tanto:
RESUMEN
En este Capítulo hemos pretendido dar una visión exhausti-
-107 -
va del problema de síntesis de relaciones en Tercera Forma Nor
mal, utilizando los resultados de P. Bernstein £87 , que cons
tituyen el primer intento satisfactorio para instrumentar el pro
ceso de normalización de Codd, de que tengamos conocimiento.
La principal conclusión es que los recubrimientos mínimos
producen todos el mismo número de relaciones sintetizadas (lo
que no es fácil ver intuitivamente, ya que podría ser lógico
suponer que recubrimientos mínimos con distinto número de depen
dencias condujesen a distinto número de relaciones ), y este nú
mero es mínimo.
- 108 -
C A P I T U L O VI
CONSIDERACIONES PARA UN ESTUDIO POSTERIOR :
EVOLUCIÓN ACTUAL DE LA TEORÍA DE NORMALIZACIÓN
1. INTRODUCCIÓN
El objetivo de nuestro trabajo ha sido la caracterización
matemática de las Formas Normales, tal como fueron definidas por
Codd [13] , a partir de los Axiomas de Arsmtrong que consti
tuyen (la demostración puede encontrarse en [3l] ) un conjunto
completo de reglas de inferencia para las dependencias funciona
les (es decir : Dado un esquema de relación^^r< T,J//>, donde
<=>2Tes un conjunto de dependencias funcionales, cualquier otra
dependenciafJ^que tenga luegar en^^y¿ , puede derivarse d e j ^ /
por aplicación de dichos Axiomas ).
El resumen de los Lemas y Teoremas que hemos enunciado y
demostrado lo constituyen los Algoritmos de búsqueda de claves
y de determinación del nivel de normalización de una relación.
Estos Algoritmos sólo se han descrito, no hemos escrito ningún
programa que los ejecute, ya que nuestra intención ha sido simple
mente sintetizar en ellos unas conclusiones de tipo puramente ma
temático (De todas formas, las funciones APL que se incluyen para
hallar el cierre de una matriz de implicación y para realizar
el cálculo algebraico de una partición funcional, resuelven la par-
109
te más laboriosa de cálculo manual, por lo que, en caso no ex
cesivamente complicados, la ejecución manual de los Algoritmos
es simple y sistemática ).
2. LA UNION SIN PERDIDA: UN CRITERIO PARA LA DESCOMPOSICIÓN
DE ESQUEMAS DE RELACIÓN.
Sea el esquema de relación ^J^T^s T v = j £ > que descomponernos
en subesquemas :
yv (GP2 <-^n; s i e n d 0 T i e l u n i v e r s o d c , J7£ i
n 1 . T = » i T.. Decimos que esta descomposición es una des-
i = 1
C/7 composición^Lj^(de1 inglés "Lossless j o i n " ) con respecto a
si para toda relación ¿y? def inida
to de restr icc iones J ^ , se ve r i f i c a
si para toda relación /¡r def inida sobre T y sujeta al conjun
te * yjV •) ( ° sea ; J í ^ res igual a la unión natural de
i = l i
sus proyecciones).
Introduzcamos la notación siguiente :
*r&> -.«v^N n
i = 1
Lema 2-1
Si V? - /) \Tl\ , entonces i
no
c) mr(mf (¿71) ) = ^ /
Prueba
Ó/) a) Sea t una tupia de <_V¿T. Para todo i , t - =t £ T. ~]
es una tupia de^yT^. Por definición de unión natural,
t es una tupia de m p (//>> ^a c'ue coincide con t.
en los atributos T. para todo i.
b) Ya que^/lk-/^^^ , se tendrá quecy/7ÍT.~} c
esto es '-¿/^l\ cr m p e~/¿^ íT-]« Demostraremos
ahora que m A~/¿) [ T - ] ^ ^ ^ - En efecto,supongamos
que, para un cierto i, t. es una tupia de m A/¿
[T.J . Entonces hay una tupia t en m ¿yl) tal
que t rT.~j = t.. Ya que t está en m \~/¿)» naY
(para todo j) algún t* . enyY.. tal que t [" T.] =
t- . En particular, t [T.] está en y \ . Pero t
ÍT.] = t., asi que t. está en yy- y por tanto m©
[T0
c) Se t iene que m p i¿?¥) \.^{i~ ^/l y A s i ' P u e s :
111
Obsérvese que m (c-/2 ) I "''•l no tiene por qué ser
necesariamente igual a &//• • Pongamos un ejemplo :
1 " ll "1
m r *~si)
Y se tiene que : m p J^f-f) [BCj = \ b]_ } ^ \ f^ ¿?
Si las relaciones
irrespondienl
gebra Relaciona! )
En general: m ^ ¿yf) [ T.] ^ ^
son las proyecciones de una cierta relación'p/V' entonces
m y/Z ) l ' • J C/£\ ^ver en e^ Capítulo Primero el apar
tado correspondiente a la unión natural en las operaciones de Al-
Un método sencillo para comprobar si una determinada descom
posición es una "descomposición LJ" con relación a un conjunto
de dependencias funcionales dado, se describe y demuestra en [_3lJ
y es como sigue:
y Sea el e s q u e m a J ^ T , ¿£ > , T = j A ^ A2 AR ^
una descomposición del mismo : p = L / / i ' s)\k i
se construye una tabla de n f i l a s (correspondientes a los a t r ibu
tos del esquema ) y K columnas (correspondientes a los subesque-
- 112 -
mas). Representando pori_y¿.l\. el elemento correspondiente
a la fila i-ésima y a la columna j-ésima, se tendrá :
¿?si A. g T.
.A. - \ , 1 J ^.si A. ¿ T.
y J ^ T
A continuación se consideran repetidamente cada una de las
dependencias funcionales de^S^C X —$>Y, hasta que ya no haya
cambios en la tabla, del modo siguiente :
Buscar la existencia de filas que coincidan en todos los va
lores correspondientes a X. Si se encuentran dos filas con estas
características, igualar los valores correspondientes a los atri
butos de Y, en la forma siguiente : Si uno de ellos es a , hacer
al otro igual a él. Si son dos valores b,no varíen.
Si en el proceso se produce una fila ¿z ¿zt • a^
el Algoritmo termina y la descomposición es del tipo LJ.
Ejemplo : ^ ^
T = \A, B, C, D \
^J: A . , B
AC ^ D
Consideremos la descomposición sobre AB y ACD.
El Algoritmo anterior se aplica en la forma siguiente:
- 113 -
C D
¿13 V t,
Ya que A _> B y ambas filas coinciden en el valor de A,
igualamos los correspondientes valores de B a a^ , obteniendo:
A B C D
Y puesto que la segunda fila es ez a tz a
el Algoritmo termina y podemos afirmar que la descomposición
efectuada es una "descomposición LJ ".
Teorema 2-1
Si f = C¡S¿-\ • <L*/¿ o \ es una descomposición de*-
y ¿/ es un conjunto de dependencias funcionales, entonces la
descomposición es una "descomposición LJ" respecto de <^¿ •, si
y sólo si ( T x <\ T2) — * (T rT 2) o bien (^ n ^ —i
( T ^ ) .
Prueba:
Indicaremos solamente cómo se realiza, ya que se trata tan
sólo de aplicar el anterior Algoritmo de verificación a la tabla:
- 114 -
a a
T„ - T
a a a a / /
1
7 a a, a ' i / / / \ a a a
En el sencillo ejemplo que acabamos de proponer:
I A. B >
l A, C, D "V
Tl " T2 " B
Luego la descomposición realizada tiene la propiedad de
unión sin pérdida.
3. FORMA NORMAL DE BOYCE - CODD (BCNF)
3.1. DEFINICIÓN
c/y De un esquema de relaciónc_>7<'T,r-></ > se dice que está
en Forma Normal de Boyce-Codd cuando las únicas dependencias no
triviales son aquéllas cuyos implicantes contienen alguna claví;
Teorema 3-1
Si en un esquema de relación en Forma Normal de Boyce-Codd,
<-<• es un conjunto de dependencias funcionales, entonces /Testa
en Tercera Forma Normal
115
Prueba:
Si'-yT no estuviera en Tercera Forma Normal, existirá al
guna dependencia transitiva de la forma:
K ^ Y ^ A, siendo K una clave de
A ^ K, A <fc Y, y f_
no incluye ninguna clave dec^l (ya que, en caso contrario, ten
dría que verificarse Y . K )
Ahora bien : A ^= Y, luego Y ^A contradice la condición
de Forma Normal de Boyce-Codd.
3.2. "Descomposición LJ" en Forma Normal de Boyce-Codd.
Lema 3-2-1
O? Sea vJ^T^T, c x / > un esquema de realción (donde^^/'es un
conjunto de dependencias funcionales ) y p - ] 3 ¿ i ¿yL \
una descomposición de
respecto de «-,</, .
con la propiedad de unión sin pérdida
Daremos sin demostración (que puede encontrarse en [3lJ
y procede por manipulación algebraica de la definición de descom
posición con la propiedad de unión sin pérdida) los resultados
siguientes :
- 116 -
o a) Sea s¿f- ^a proyección de ^T sobre S o ^ , esto es,
el conjunto de dependencias decJ£ tales que los descrip-
tores a derecha e izquierda del signo de implicación,
son subconjuntos de T. ; y sea a" \ , s •, y
una descomposición áé^/Y. con la propiedad de unión sin
pérdida respecto ÓQ(-/<. Se tiene que la descomposición
de. 77^ ,r7>¡ ^ . i f - • • • • J/f,
. .,.... - j / ^ / tiene la propiedad de unión sin pérdi
da respecto de
» - T-ha- J ^ J U . # P Í una descomposición de Ó22 en un conjunto de subesquemas
que incluya a p . Entonces 7T tiene la propiedad de
unión sin pérdida respecto de
Veamos ahora cómo descomponer el esquema <y7en subesque
mas en Forma Normal de Boyce-Codd, de modo que esta descomposi
ción presente la propiedad de unión sin pérdida respecto d e ^
? \m II - Si en p hay un esquema de relación (y% que no está
en BCNF, tendrá lugar alguna dependencia de la forma
X c, A; donde X no es superconjunto de ninguna cla
ve y A £ x .
Tiene entonces que haber algún atributo de /distinto de
A y que tampoco pertenezca a X, pues, en caso contrario, X sería
- 117 -
superconjunto de alguna clave de C r Se reemplaza _yen P
P°r3l yJ/9» donde ^/\ se define sobre los atributos de X y
sobre A, y^7^ consiste en todos los atributos de J^T excepto
En virtud del Teorema 2-1, ya que T.. C\ T» = X y X ^ T1
— T? = A, la descomposición de C/ en^r y \ y ^ tiene la propie
dad de unión sin pérdida con respecto a la proyección de J^T sobre
J / \ Por Lema 3-2-1 ( a ) \ p sigue teniendo la propiedad
de unión sin pérdida si la tenia antes de efectuar la descompo
sición de ^/ . Ya que J/., y L_y^ tienen menos atributos que
KS , la repetición del proceso permite alcanzar un punto en
que todos los esquemas estén en la Forma Normal de Boyce-Codd.
En todo momento, p conserva la propiedad de unión sin pérdida (ya
que inicialmente, p - l <-ST\).
Ejemplo :
Consideremos el esquema de relación <~/í- ^ T , J > ^ >
Sf: \ A , B, C , D, E, F }
A _ > B
CD . ^ A
CB > D
AE - > •
CE ^ D
La única clave del esquema se determina fácilmente, es CE.
- 118 -
El esquema no está en Forma Normal de Boyce-Codd. En efecto:
La dependencia AE __v F, no contiene ningún superconjunto de
la clave. Descomponemos { A,B,C,D,E,F ) en A,E,F I yJl\,B,C ,D,E ^
Calculamos ottXal final del ejemplo viene señalado el cál
culo del cierre de la matriz de implicación ), y proyectamos
sobre IA,E,F\ y j A,B,C,D,E1 .
Podemos trabajar con recubrimientos mínimos de dichas pro
yecciones, ya que cualquier otra dependencia puede derivarse a
partir de ellos por los Axiomas de Armstrong. Las proyecciones
(obtenidas decodificando la matriz binaria, resultado de la
función CIERRE APL) son :
\ A, E, F ] : AE - — f F (coincide con el recubri
miento mínimo)
^A,B,C,D,E ) A -
CD
CD _
CB
CB
AE
CE
CE _
CF ..
— *
— >
—>
— ^
—>
-—>
>
B
A
B
A
D
B
A
B
D
Y un recubrimiento mínimo :
- 119
A
CD
BC __
CE
>
=»
B
A
D
D
De donde resulta que la única clave es CE.
El esauema :¡ A,E,F} , AE —fe F está en Forma Normal de
Boyce-Codd.
El segundo subesquema, no lo está. Fijémonos por ejemplo
en la dependencia: A ^ B , donde A no es superconjunto de la
( 1 clave. Efectuamos una segunda descomposición en j, A,B y y
1 A,C,D,E j. Los recubrimientos mínimos de las dependencias pro
yectadas son ahora :
A t, B para \ A,B "V ; y AC — * D,
CE _4> D, CD A para} A,C,D,E ^
Las claves (únicas) son, respectivamente, A y CE.
El esquema: \ l\,B) , A -^ B está en Forma Normal de
Boyce-Codd . El segundo subesquema no, ya que tiene lugar la
dependencia AC ^ D , y AC no es superconjunto de la clave.
La nueva descomposición se realiza sobre ] A,C,D -¡y
(A,C, E) .
- 120 -
El esquema: \ A,C,D 7 ; AC _ ^ D, CD __.^ A: está en Forma
Normal de Boyce-Codd (ya que las claves son AC y CD ).
El esquema: I A,C,E \ ; CE _...%A ; también lo está, ya que
la clavé única es CE.
A continuación se esquematiza en un árbol el proceso seguido.
Obsérvese que la dependencia BC ^-^D no se conserva en la
descomposición. Es decir : la proyección de c-cT sobre AEF,
AB, ACD, ACE; que puede representarse por el recubrimiento:
AE
A
AC
CD
CE
* •
*.
. =t>
/».
F
B
D
A
A A, no implica BC . ¿. D
121
CLAVE: AE
BCNF
CLAVE.'A
BCNF
CLAVES:
AC, CD
BCNF
CLAVE: CE
V
I CLAVE: CE
A
AC
CD
C
-~>
D
D
A
í
A
AC
CD
CE
C
• —
D E
~ * D
- * A
— D
CLAVE: CE
A C E
CE CLAVE: CE
BCNF
122
Podemos concluir afirmando que una descomposición en For
ma Normal de Boyce-Codd no conserva necesariamente las depen
dencias funcionales (de hecho, para un esquema dado, puede no
existir ninguna descomposición en Forma Normal de Boyce-Codd
que las conserve ).
- 123 -
CAI .CUUÍ u n . CJFRRF ni: I.A MATRIZ nr IMIM/K-ACIDN
¡'
1 1 II
1 II
1 1)
II 1
1 1 II 1)
II 1
ti (i n
1 (1 0
! (1 0
ii i 1 I ! ü
I ., MATRIZ ME OIFRI \- \A)
I 1 0 I) ü l) i I ! I l ) l l
I I ! I 0 l l
! ! i) ii I I
I I I I I l l
- 124
4. DEPENDENCIAS MULTIVALUADAS
4.1. DEPENDENCIAS MULTIVALUADAS
De acuerdo con la definición de Fagin f24j , una depen
dencia multivaluada es una sentencia X —*-> Y, donde X e Y
son descriptores tales que un cierto valor de X determina un
conjunto bien definido de valores Y.
Sea una relación<^X¿(X, Y, Z), donde X, Y, Z son Conjuntos
disjuntos de atributos.P o ry^/2lx , z^l ' representamos la proyec
ción sobre Y de conjunto de tupias t tales que t [ Xj = x,
t í ZJ = z ( esto es 5 <yy íx , z, Y "1 representa abreviada
mente la secuencia de dos operaciones: selección y proyección ).
Del mismo modo.^/^fx» Yj representa la proyección sobre Y del
conjunto de tupias t tales que t f"x"| = x.
La dependencia multivaluada X _^*Y, tiene lugar en
(X, Y, Z) (con X, Y, Z conjunto disjuntos) si para todo valor
(x, z) de XZ se cumple:
[x, z, Y] = o>T[x, Y]
SiX U Y U Z = T, y no son conjuntos d is jun tos , sino
que se cumple YO Z ^ X, la condición necesaria y suf ic iente
para que en (T) tenga lugar la dependencia multivaluada
X _ _ ^ Y, es que ^/¿(T) = J / f [ x U Y ] * y f y U zJ
125
(la demostración puede encontarse en f3ll )
4.2. Axiomas para Dependencias Funcionales y Muítivaluadas
Beerin, Fagin y Howard Í6j ; demostraron que los ocho
Axiomas siguientes constituyen un conjunto completo de reglas de
inferencia para el caso de que el conjunto de restricciones de
un esquema relación esté constituido por dependencias funcionales
y multivaluadas, exclusivamente :
A1 : Reflexividad : X > X
A? : Aumentación : V X' ZD X,, si X . ^Y también
X ' — f Y
A„ : Transitividad : Si X -—> Y y Y .—*, Z, entonces
X __* Z
A. : Complementad'ón : Si X —>-*Y, entonces X-y* T-X-Y
Aj- : Aumentación para dependencias multivaluadas :
Si X - » Y y V C W, entonces XW _ » V Y
A, : Transitividad para dependencias multivaluadas :
Si X-**Y y Y-^» Z, entonces X->>Z-Y.
A7 : Si X — 5 Y entonces X — » Y
126
Ag : Si X- -i, Y, Z c Y y para algún W tal que W O Y=0
se tiene que W—> Z, entonces X —> Z
4.3. Descomposición con la propiedad de unión sin pérdida con
respecto a un conjunto ^¡T de dependencias muí ti valuadas
y funcionales.
El concepto de descomposición con la propiedad de unión
sin pérdida respecto de un conjunto de restricciones, es idén
tico al que expusimos con detalle en el apartado 2 de este Capí
tulo. Una modificación del método para verificar si una des
composición de un esquema de relación tiene la propiedad de unión
sin pérdida respecto de un conjunto^r de dependencias muí ti va
luadas es la siguiente :
En primer lugar, se constituye la tabla de elementos "a"
y "b" como en el caso de dependencias funcionales solamente.
A continuación, se construye un conjunto de tablas por modifica
ción de la primitiva en la forma siguiente:
Identificando dos símbolos si se considera una dependencia
funcional o bien, si se considera una dependencia multivaluada
X_y_¿Y, y en una misma tabla hay dos tupias t. y t?, tal que :
t.. íX j = t? Fx] , añadiendo a dicha tabla la tupia
11 tal que : U.[x] - tj [x] , «-[Y] = t]_ [ Y ] y
U, [T-X-Yj = t2 1 T-X-Yj , en el caso de que [ no estuviese ya
en la tabla en cuestión.
- 127 -
El proceso finaliza cuando ya no se produzcan modificacio
nes. Si en alguna tabla hay una fila que sólo contenga elemen
tos tipo " a " , la descomposición tiene la propiedad de unión
sin pérdida. En caso contrario, no.
5. DEFINICIÓN DE LA CUARTA FORMA NORMAL
En Í6"j se encuentra la definición de una nueva Forma Nor
mal que se aplica a esquemas de relación que incluyen dependencias
multivaluadas.
Seac.x'Y^T > o o > un esquema de relación, donde &£, es un
conjunto de dependencias (funcionales y/o multivaluadas) Dicho es
quema está en Cuarta Forma Normal si toda dependencia muí ti valuada
X _-*»Y, en la que Y f 0, Y ^L X, X U Y f T ; es tal que
X es superconjunto de alguna clave. (Obsérvese que en el caso de
9 u e 0^7 contenga sólo dependencias funcionales, si \^/¿¿ T>o¿>
está en Cuarta Forma Normal también está en Forma Normal de
Boyce-Codd).
f'\¿JV \¿Í2 -S^n
Podemos siempre encontrar para ^ / ¿ u n a descomposición :
ta l que cada uno de los n
subesquemas resultantes estén en Cuarta Forma Normal y P tenga
la propiedad de unión sin pérdida respecto de &
Ejemplo :
Consideremos el esquema i^/¿<T,oC> , siendo:
128
T = A, B, C, D, E, F
0 6 : A — > B AE > F .
CD .—j. A CE . 5 D
CB .—> D A y -CD
Para descomponer el anterior esquema en un conjunto de sub-
esquemas en Cuarta Forma Normal, podríamos comenzar por conside
rar la dependencia A —y>CD, que no cumple la condición de ser
superconjunto de alguna clave el primer miembro (el esquema pro
puesto coincide,salvo en la dependencia multivaluada A _ ^ CD,
con el del ejemplo desarrollado anteriormente en este Capítulo
al estudiar la descomposición en Forma Normal de Boyce-Codd, y ya
vimos que la clave era CE ).
La dependencia multivaluada A — » CD no contradice sin embar
go la definición de Cuarta Forma Normal para JA, C, D y ,
ni tampoco ninguna otra dependencia funcional o multivaluada pro
yectada sobre este subconjunto. Así pues, no es preciso seguir
descomponiéndolo.
Si consideramos ahora el conjunto ( A, B, E, Fjcuya única
clave es AE, podemos ver que la dependencia multivaluada A - » B
(que se deriva de A —> B), contradice la definición de Cuarta For
ma Normal.
La descomposición de A, B, E, Fl en JA, B!J y i A, E, FL
finalizará el proceso, ya que las dependencias proyectadas sobre
129
estos dos últimos subconjuntos verifican la definición de Cuar
ta Forma Normal. Tenemos pues la descomposición en: i A, C, D (,
l A, B \ y L A, E, F'j . Comprobemos que tiene la propiedad
de unión sin pérdida respecto de ¿¡¿7 :
A B C D E F
ACD & / & & / /
AEF a / / / a a T a b l a x
AB a a
Usando A .—& B :
A B C D E F
ACD a a a a
AEF & a Tabla 2
AB a a / / / /
Usando A
A B C D E F
ACD a ^ a a / /
AE a *• / / a a Tabla 3
AB a a / / / /
Usando A —J>-»CD y las dos primeras filas de la tabla 3, cons-
truiriamos una nueva tabla con una tupia ÍL adicional
IL [AJ =
U,[CD] =
U[BEFJ =
h t A 3 t j [CDJ
t2 [BEFJ
= ¿?
- a a
= a a ¿z
130
Luego aquí podemos detener el Algoritmo de test y concluir
con que efectivamente la descomposición realizada tiene la pro
piedad de unión sin pérdida respecto de áf-
6. CONSIDERACIONES EN LA INTEGRACIÓN DE LOS TRES TIPOS DE RES
TRICCIONES ESTUDIADOS: DEPENDENCIAS FUNCIONALES, DEPENDEN
CIAS MULTIVALUADAS Y DEPENDENCIAS RESPECTO DE LA UNION.
Al presentar en este Capitulo dos nuevas Formas Normales
(La Forma Normal de Boyce -Codd y la Cuarta Forma Normal, defini
da por Fagin), hemos introducido también el concepto de descompo
sición con la propiedad de unión sin pérdida respecto del conjun
to o/Tde restricciones (dependencia funcionales y/o multivalua-
das) del esquema original. Este concepto sirve para definir un
nuevo tipo de dependencia: la dependencia de orden n respecto
de la unión; que tiene lugar en el esquema(_(//2 ^ o o * S1
existe una descomposición del universo T en subconjuntos X,, X„.
Xn tal que :
Sí. }^n Esta dependencia se representa asi : * lhlhl-k]
Si recordamos la condición necesaria y suficiente para que
X_^»Y tenga lugar en (X, Y, Z) (con : Y H Z S X ;
Y \J X U Z = T ) , condición indicada en el punto 4.1. de este
- 131 -
Capítulo; vemos que una dependencia multivaluada equivale a una
dependencia binaria respecto de la unión. En efecto, X— y»Y
equivale a : * [XUY] f"xuz1
Por último, toda dependencia funcional es una dependencia
multivaluada con una restricción de funcionalidad (el conjunto de
valores de Y determinado por un valor de X se reduce a un sólo ele
mento) .
7. CONCLUSIÓN: POSIBLES PUNTOS DE PARTIDA PARA POSTERIORES
TRABAJOS SOBRE EL TEMA.
En nuestro trabajo hemos ahondado en el estudio y caracteri
zación matemática de la Formas Normales tal como fueron definidas
por Codd. Considerando que las restricciones impuestas por el es
quema eran sólo dependencias funcionales, y apoyándonos por tanto
en los Axiomas de Armstrong, hemos deducido una serie de propieda
des que caracterizan a las claves y a las Formas Normales en sí
mismas. En todos los procesos (búsqueda de claves y caracteriza
ción del nivel de normalización) es fundamental el uso del cierre
de la matriz de implicación, cuyo cálculo es extremadamente senci
llo con la función CIERRE APL (e incluso manualmente en casos no de-
mas i do complicados ).
Si consideramos el caso más general en el que^Vyrepresenta
un conjunto de dependencias funcionales y/o multivaluadas, el con
junto de reglas de inferencia se complica notablemente y no exis-
- 132 -
te hasta el presente un Algoritmo que permita el cálculo siste
mático y rápido del cierrej^V^ . Si además consideramos las
dependencias de orden n respecto de la unión, no existe hasta es
te momento, ni siquiera un conjunto completo de reglas de infe
rencia para este tipo de restricciones.
El fundamento matemático y posterior elaboración teórica
(como para el caso de las Tres Formas Normales de Codd) para este
tipo de restricciones en una cuestión pendiente de solución hasta
la fecha.
Otros tópicos interesantes son la compleción de un esquema
de relación con un conjunto de operaciones permitidas ( la
unión y proyeccción constituyen la base de la Quinta Forma Normal,
PJ/NF, definida por Fagin 125] ) ; la búsqueda de procedi
mientos de descomposición con la propiedad de unión sin pérdida
que conserven también las dependencias funcionales (representacio
nes "Faithfull" [5] ) e incluso el tratamiento de las cone
xiones de tipo jerárquico como un tipo especial de dependencias
[23] )•
- 133 -
C A P I T U L O V I I
CONCLUSIONES
Ya se han expuesto en la ,introducción las líneas generales
de nuestro trabajo, incluyendo los resultados del mismo y algunas
consideraciones sobre últimos desarrollos del mismo, con las ven
tajas claras e inherentes que pueden reportar estos resultados al
desarrollo y evolución de los Sistemas de Bases de Datos Relacióna
les.
La novedad aportada por nuestro trabajo supone además de
una nueva filosofia conceptual, unos Algoritmos que permiten deter
minar todas las claves de una relación, lo que es fundamental en
la definición de las Formas Normales, enunciadas por el Profesor
E.F. Codd. Asimismo, hemos establecido, como trabajo original, y
basándonos en el conjunto completo de reglas de inferencia para
las dependencias funcionales (Axiomática de Armstrong), los crite
rios que determinan el nivel de normalización de una relación.
Nuestro trabajo abre además las puertas a una nueva línea
de investigación, en donde aparecen como problemas primarios a in
vestigar; el cálculo del cierre de un conjunto de dependencias mul-
tivaluadas; el establecimiento de una estructura inferencia! com
pleta para dependencias de orden n respecto de la unión (que
resolvería incluso como caso particular la caracterización matemá
tica de las estructuras jerárquicas ) y la búsqueda de procedimien
tos de descomposición de esquemas que presentan la propiedad de
- 134 -
unión sin pérdida respecto del conjunto de restricciones ,
conservando dichas restricciones cualquiera que sea su naturale
za.
- 135 -
B I B L I O G R A F Í A
ALTMAN, E.B., et al (1973)
"Specifications in a Data Indepent Accessing Model " IBM
Research Report, RJ 1141, IBM Research Laboratory, San Jo
sé, California
ARMSTRONG, W.W. (1974)
"Dependency Structures of Data Base Relationships", InjFor-
mation Processing 74, North Holland Publishing Compañy, pp.
580-583
ASTRAHAN, M.M., et al (1972)
"Concepts of a Data Independent Accessing Model". _I_BM__
Research Report, RJ 1105, IBM Research Laboratory, San José,
Californnia
BEERI, C. BERNSTEIN, P.A. , GOODMAN, N. (1978)
"Asophisticate Introduction to Data Base Normalization Theo-
ry" » IEEE , CH1389, 6/78.
BEERI, C , RISSANEN, J. (1980)
"Faithfull Representations et Relational Datábase Schemas".
IBM Research Report, RJ2722, IBM Research Laboratory , San
José, California.
BEERI, C , FAGIN R., HOWARD, J.ll. (1977)
"A Complete Axiomatization for Functional and Multivalued
Dependencies in Datábase Relations" ACM/SIGMOD, pp 47-61
- 136 -
BERNSTEIN. P.A., GOODMAN, N. (1980)
"What does Boyce-Codd Normal form do ?, IEEE , CH1534,
7/80.
BERNSTEIN, P.A. (1976)
"Synthesizing Third Normal Form Reíations From Functional
Dependencies".
ACM Transactions on Datábase Systems, Vol 1, No.4, pp.
277-298
BERNSTEIN, P.A., BEERI, C. (1976)
"An Algoritmic Approach to Normalization of Relational
Datábase Schemas"
Technical Report CSRG- 73, Computer Systems Research Group
University of Toronto, Canadá
BERNSTEIN, P.A. DAYAL, U. BISKUP, J (1979)
"Synthesizing Independent Datábase Schemas " ACM/SIGMOD
pp 143-152.
BOYCE, R.F. et al (1973)
"Specifying Queries as Relational Expressions Square",
IBM Research Report , RJ 1291, IBM Research Laboratory,
San José, California.
CODD, E.F. (1970)
"A Relational Model of Data for Large Shared Data Banks"
CACM, Vol.13, No. 6, pp. 377-387
- 137 -
13. CODD. E.F. (1971)
"Further Normalization of the Data Base Relational ModeI"
IBM Research Report, RJ 909, IBM Research Laboratory,
San José, California
14. CODD, E.F. (1971)
"Normalized Data Base Structure: A Brief Tutoría!",
IBM Research Report, RJ 935, IBM Research Laboratory, San
José, California.
15. CODD, E.F. (1971)
"A Data Base Sublanguage Founded on the Relational
Calculus" IBM Research Report, RJ 893, IBM Research La
boratory, San José , California.
16. CODD, E.F. (1971)
"Relational Completeness of Data Base Sublanguage",
IBM Research Report, RJ 987, IBM Research Laboratory,
San José, California.
17. CODD, E.F. (1974)
"Recent Investigations in Relational Data Base Systems"
IBM Research Report, RJ 1385, IBM Research Laboratory,
San José, California.
18. CHAMBERLIN, D.D. (1931)
"A Summary of'user Experience With the SQL Data Sublangua
ge", IBM Research Report, RJ 2767, IBM Research Laborato
ry, San José , California
- 138 -
CHENG, W. (1978)
"Optimization Techm'ques in Designing Relational Data
Base Systems", PhD Dissertation, Department of Computer
Science, Üniversity of Michigan, Ann Arbor, Michigan
DATE, C.J. (1975)
"An Introduction to Data Base Systems", Addison Wesley
New York.
DATE, C.J. (1972)
"Relational Data Base Systems: A Tutorial," Fourth Inter
national Symposium on Computer an d Info r nía t i o n_S cien ees ,
Miami Beach, Florida, Plenum Press.
DELOBEL. C. CASEY R.G. (1973)
"Decomposition of a Data Base andthe Theory of Boolean
Switching Functions". IBM Journal of Research and__D_eveJo_p-
ment, Vol. 17, No. 5, pp. 374-386
DELOBEL, C. (1980)
"An Everview of the Relational Data Theory" Information
Processing, 80, NorthHolland Publishine Company, pp 413-
426.
FAGIN, R. (1977)
"Multivalued Dependencies and a new normal Form for Rela
tional Databases", ACM Transactions on Datábase Systems
Vol 2, No. 3, pp.262-278.
- 139 -
FAGIN, R. (1979)
"A Normal Form for Relational Databases That is Based
in Domains and Keys", IBM Research Report, RJ 2520,
IBM Research Laboratory, San José, California.
FAGIN, R. (1981)
"Horn Clauses and Datábase Dependencies ", IBM Research
Report, RJ 2741, IBM Research Laboratory, San José,
California.
FAGIN R. (1979)
"Normal Forms and Relational Datábase Operators" ACM/
_S_IGN0D, pp 153-160.
KING, W. F. (1980)
"Relational Datábase Systems Where we Stand Today",
Information Processing 80 , North Holland Publishing
Company , pp 369-381.
NEUHOLD, E.J. 0LNH0FF, T.
"The Vienna Development Method (VDM.) And Its Use For
The Specification Of a Relational Datábase System" , _In-
formation Processing 80 , Northl-lol 1 and Publishing Compa
ny, pp. 3-16.
STRNAD, A.L. (1971)
"The Relational Approach to the Management of Data Bases"
Proc. IFIP Congress ¿Jubljana, Yougoslavia.
- 140 -
ULLMAN, J.D. (1981)
"Principies of Datábase Systems" Ritman, London, 1981
VETTER , M. (1980)
"Datábase Design by Applied Pata Synthesis", IBM Eoropean
Systems Research Institute, La Hulpe, Belgium.
WONG, H.K.T., SHU, N.C. (1981)
"An Approach to Relational Datábase Schema Design"
IBM Research Report, RJ 2888, IBM Research Laboratory, San
José, California
WONG H.K.T. , SHU N.C, LUM, V.Y. (1980)
"Froms Approach to Application Specification for Datábase
Design", IBM Research Report, RJ 2687, IBM Research Labora
tory, San José, California,
YOUSSEF FALOUS.R. (1974)
"A Summary of Relational Datábase Theory" Technicaí Report r
Department of Computer Science, University of Michigan, Ann
Arbor, Michigan.
- 141 -
