FPlus: Algunos algoritmos para bases de datos
Copyright (C) 2002 German Viscuso
E-mail: netquake@netquake.com.ar
This program is free software; you can redistribute it and/or modify
it , under the terms of the GNU General Public License as published
by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
FPlus es una aplicación que permite calcular:
-La clausura de un juego de atributos.
-Las claves de una relación.
-Un conjunto minimal de dependencias funcionales
(Fmin).
-La clausura de un conjunto de dependencias funcionales
(F+).
-Si hay perdida de información en un
esquema dado (Tableaux).
-Si hay perdida de dependencias
funcionales en un esquema.
-Si un esquema dado es eficiente.
-La forma normal de la Relación.
-La forma normal de las Proyecciones dadas.
-Una descomposición en
3FN eficiente.
-Una descomposición en FNBC
sin perdida de información.
El applet FPlus requiere Java plug-in 1.3.1 o superior (ver al pie el motivo)
Para ver el applet dirijase a:
http://fplus.sourceforge.net/AppletFPlus.html
(Si no cuenta con el plug-in
se descargará automaticamente)
FPlus trata los siguientes tópicos:
-Relación
-Dependencias funcionales
-Proyecciones
-Clausura
-Claves
-Fmin
-F+
-Perdida de información
-Perdida de dependencias funcionales
-Eficiencia
-Forma normal de Relación
-Forma normal de Proyecciones
-Descomposición en 3FN
eficiente
-Descomposición en FNBC sin
perdida de información
Los atributos de la relación (solapa Relación) se
ingresan separados
por coma (,) y terminan con punto y coma (;). Todo lo que sea
ingresado luego del primer punto y coma (;) será descartado.
Ej:
A,B,C,D,E;
Note que FPlus es sensible a minúsculas y mayúsculas
por lo que el
atributo A no es igual al atributo a.
También note que AB es distinto de A,B. Si se ingresa AB
sin comas
de separación AB se considera como un único atributo
denominado AB.
Las dependencias funcionales (solapa Dependencias) se ingresan
separadas por (;) y Enter. Los atributos tanto a derecha como a
izquierda se separan con coma (,). La flecha que indica que el
lado izquierdo determina el derecho es el simbolo mayor (>).
(Para los atributos, tanto a izq. como a der., caben las mismas
consideraciones hechas en la sección titulada Relación.)
Ej:
A>B,C,D;
A,B>D,E;
B,E>A,C;
Las proyecciones (solapa Proyecciones) son juegos de atributos que
se
utilizan en el algoritmo Tableaux para comprobar el cumplimiento
de la descomposición con junta sin perdida (solapa Tableaux).
Cada
juego de atributos determina una fila en la matriz del tableaux.
Cada juego se separa con punto y coma (;) y Enter y cada atributo
con
coma (,).(Para los atributos involucrados caben las mismas
consideraciones hechas en la sección titulada Relación)
Ej:
A,D;
A,B;
B,E;
C,D,E;
A,E;
Tanto el applet como la aplicación permiten realizar la clausura
de atributos a voluntad.
Ej:
Dependencias:
[[A] -> [C], [B] -> [C], [C] -> [D], [D, E] -> [C], [C, E] -> [A]]
Atributos:
[A, B]
Clausura:
[A, B, C, D]
Con el botón Claves se realiza el cálculo de todas
las superclaves y
claves candidatas realizando la clausura de los atributos de la
relación (solapa Relación)
dadas las dependencias funcionales de
la solapa Dependencias.
Para realizar esta operación debe completar correctamente,
según
se indico previamente, los atributos de la relación (solapa
Relación)
y las dependencias funcionales originales (solapa Dependencias).
Ej:
Conjunto de superclaves:
[[B, C, D, E], [B, D, E], [B, E], [B, C, E], [A, C, D, E], [A,
D, E], [A, E], [A], [A, D], [A, C, E], [A, C], [A, C, D], [A, B, D, E],
[A, B, E], [A, B], [A, B, D], [A, B, C, E], [A, B, C], [A, B, C, D]]
Conjunto de claves candidatas:
[[B, E], [A]]
La solapa mostrará, una vez presionado el botón
correspondiente a esta operación, el resultado del algoritmo
Fmin
(que calcula un nuevo conjunto de dependencias funcionales
equivalentes al dado pero sin redundancia).
Para realizar esta operación debe completar correctamente,
según
se indico previamente, los atributos de la relación (solapa
Relación)
y las dependencias funcionales originales (solapa Dependencias).
Ej:
Conjunto de dependencias funcionales originales:
[[A] -> [B, C, D], [A, B] -> [D, E], [B, E] -> [A, C]]
Conjunto de dependencias funcionales luego de FMIN paso 1:
[[A] -> [B], [A] -> [C], [A] -> [D], [A, B] -> [D], [A, B] -> [E],
[B, E] -> [A], [B, E] -> [C]]
Conjunto de dependencias funcionales luego de FMIN paso 2:
[[A] -> [B], [A] -> [C], [A] -> [D], [A] -> [E], [B, E] -> [A],
[B, E] -> [C]]
Conjunto de dependencias funcionales luego de FMIN paso 3:
[[A] -> [B], [A] -> [D], [A] -> [E], [B, E] -> [A], [B, E] -> [C]]
F+ (ARREGLAR: faltan dependencias)
Encuentra la clausura del juego de dependencias funcionales dado.
(Todas las dependencias que pueden derivarse del conjunto original)
Ej:
Conjunto de dependencias funcionales originales:
[[A] -> [C], [B] -> [C], [C] -> [D], [D, E] -> [C], [C, E] -> [A]]
Clausura de dependencias funcionales originales:
[[B, C, D, E] -> [A], [C, D, E] -> [A], [D, E] -> [C], [D, E] ->
[A], [C, E] -> [D], [C, E] -> [A], [C] -> [D], [B, D, E] -> [C], [B, D,
E] -> [A], [B, E] -> [C], [B, E] -> [D], [B, E] -> [A], [B] -> [C], [B]
-> [D], [B, D] -> [C], [B, C, E] -> [D], [B, C, E] -> [A], [B, C] -> [D],
[A, D, E] -> [C], [A, E] -> [C], [A, E] -> [D], [A] -> [C], [A] -> [D],
[A, D] -> [C], [A, C, E] -> [D], [A, C] -> [D], [A, B, D, E] -> [C], [A,
B, E] -> [C], [A, B, E] -> [D], [A, B] -> [C], [A, B] -> [D], [A, B, D]
-> [C], [A, B, C, E] -> [D], [A, B, C] -> [D]]
La clausura EQUIVALE a las dependencias funcionales originales.
B,C,D,E>A;
C,D,E>A;
D,E>C;
D,E>A;
C,E>D;
C,E>A;
C>D;
B,D,E>C;
B,D,E>A;
B,E>C;
B,E>D;
B,E>A;
B>C;
B>D;
B,D>C;
B,C,E>D;
B,C,E>A;
B,C>D;
A,D,E>C;
A,E>C;
A,E>D;
A>C;
A>D;
A,D>C;
A,C,E>D;
A,C>D;
A,B,D,E>C;
A,B,E>C;
A,B,E>D;
A,B>C;
A,B>D;
A,B,D>C;
A,B,C,E>D;
A,B,C>D;
Perdida de información (Tableaux)
El algoritmo de tableaux permite comprobar el cumplimiento de la
descomposición con junta sin perdida de información.
Para utilizar este algoritmo debera completar correctamente los
datos de Proyecciones, Dependencias
y de la Relación. Se mostrarán
los datos intermedios de la matriz que resulta en una descomposición
con perdida de información o sin ella.
Ej:
Relación:
[A, B, C, D, E]
Dependencias:
[[A] -> [C], [B] -> [C], [C] -> [D], [D, E] -> [C], [C, E] -> [A]]
Proyecciones:
[[A, D], [A, B], [B, E], [C, D, E], [A, E]]
[A] -> [C]
[A, D]:
A:a1 B:b12 C:b23 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:b23 D:b24 E:b25
[B, E]:
A:b31 B:a2 C:b33 D:b34 E:a5
[C, D, E]:
A:b41 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:b23 D:b54 E:a5
-
[B] -> [C]
[A, D]:
A:a1 B:b12 C:b23 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:b33 D:b24 E:b25
[B, E]:
A:b31 B:a2 C:b33 D:b34 E:a5
[C, D, E]:
A:b41 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:b23 D:b54 E:a5
-
[C] -> [D]
[A, D]:
A:a1 B:b12 C:b23 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:b33 D:b34 E:b25
[B, E]:
A:b31 B:a2 C:b33 D:b34 E:a5
[C, D, E]:
A:b41 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:b23 D:a4 E:a5
-
[D, E] -> [C]
[A, D]:
A:a1 B:b12 C:b23 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:b33 D:b34 E:b25
[B, E]:
A:b31 B:a2 C:b33 D:b34 E:a5
[C, D, E]:
A:b41 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:a3 D:a4 E:a5
-
[C, E] -> [A]
[A, D]:
A:a1 B:b12 C:b23 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:b33 D:b34 E:b25
[B, E]:
A:b31 B:a2 C:b33 D:b34 E:a5
[C, D, E]:
A:a1 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:a3 D:a4 E:a5
-
[A] -> [C]
[A, D]:
A:a1 B:b12 C:a3 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:a3 D:b34 E:b25
[B, E]:
A:b31 B:a2 C:b33 D:b34 E:a5
[C, D, E]:
A:a1 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:a3 D:a4 E:a5
-
[B] -> [C]
[A, D]:
A:a1 B:b12 C:a3 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:a3 D:b34 E:b25
[B, E]:
A:b31 B:a2 C:a3 D:b34 E:a5
[C, D, E]:
A:a1 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:a3 D:a4 E:a5
-
[C] -> [D]
[A, D]:
A:a1 B:b12 C:a3 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:a3 D:a4 E:b25
[B, E]:
A:b31 B:a2 C:a3 D:a4 E:a5
[C, D, E]:
A:a1 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:a3 D:a4 E:a5
-
[D, E] -> [C]
[A, D]:
A:a1 B:b12 C:a3 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:a3 D:a4 E:b25
[B, E]:
A:b31 B:a2 C:a3 D:a4 E:a5
[C, D, E]:
A:a1 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:a3 D:a4 E:a5
-
[C, E] -> [A]
[A, D]:
A:a1 B:b12 C:a3 D:a4 E:b15
[A, B]:
A:a1 B:a2 C:a3 D:a4 E:b25
[B, E]:
A:a1 B:a2 C:a3 D:a4 E:a5
[C, D, E]:
A:a1 B:b42 C:a3 D:a4 E:a5
[A, E]:
A:a1 B:b52 C:a3 D:a4 E:a5
-
La descomposición es SIN perdida.
Perdida de dependencias funcionales
Esta opción aplica un algoritmo para identificar la
perdida de dependencias funcionales que resultan de
determinada proyección. Debe completar correctamente
las ventanas de: Relación, Dependencias
y Proyecciones.
Relación:
[A, B, C, D, E]
Dependencias:
[[A] -> [C], [B] -> [C], [C] -> [D], [D, E] -> [C], [C, E] -> [A]]
Proyecciones:
[[A, D], [A, B], [B, E], [C, D, E], [A, E]]
Se pierden las dependencias funcionales:
[A] -> [C]
[B] -> [C]
[C, E] -> [A]
Calcula perdidas de información (tableaux)
y de dependencias funcionales.
Si no las hubo el diseño de la base de datos dadas las proyecciones
es
eficiente. Debe completar correctamente las ventanas de: Relación,
Dependencias y Proyecciones.
Ej:
Relación:
[A, B, C, D, E]
Dependencias:
[[A] -> [C], [B] -> [C], [C] -> [D], [D, E] -> [C], [C, E] -> [A]]
Proyecciones:
[[A, D], [A, B], [B, E], [C, D, E], [A, E]]
El diseño es INEFICIENTE.
Esta opción analiza en que forma normal se encuentra la relación
según las dependencias dadas y la forma normal que cumple
cada dependencia.
Debe completar correctamente
las ventanas de: Relación y Dependencias.
Ej:
Relación:
[A, B, C, D, E]
Dependencias:
[[A] -> [C], [B] -> [C], [C] -> [D], [D, E] -> [C], [C, E] -> [A]]
Claves Candidatas:
[[B, E]]
Forma Normal: 1FN
[A] -> [C] -> 2FN
[B] -> [C] -> 1FN
[C] -> [D] -> 2FN
[D, E] -> [C] -> 2FN
[C, E] -> [A] -> 2FN
Calcula la forma normal de cada Proyección
dividiendo las
dependencias funcionales entre todas
las proyecciones.
Debe completar correctamente las ventanas de: Dependencias
y Proyecciones.(Actualmente no deriva
dfs por Armstrong)
Ej:
Dependencias:
[[A] -> [C], [B] -> [C], [C] -> [D], [D, E] -> [C], [C, E] -> [A]]
Proyecciones:
[[A, D], [A, B], [B, E], [C, D, E], [A, E]]
[A, D] -> FNBC
con dfs: []
cc: [[A, D]]
[A, B] -> FNBC
con dfs: []
cc: [[A, B]]
[B, E] -> FNBC
con dfs: []
cc: [[B, E]]
[C, D, E] -> 3FN
con dfs: [[C] -> [D], [D, E] -> [C]]
cc: [[D, E], [C, E]]
[A, E] -> FNBC
con dfs: []
cc: [[A, E]]
Descomposición en 3FN eficiente
Este algoritmo encuentra una descomposición en 3FN
(tercera forma normal) eficiente. Cada
proyección
encontrada estará en 3FN o FNBC
y no habrá perdida de
información o de dependencias.
Si el esquema original
ya está en 3FN se da un aviso pero el algoritmo se aplica
igual.
Ej:
Descomposición en 3FN eficiente:
R1(A,C) F1: [A] -> [C]
R2(B,C) F2: [B] -> [C]
R3(C,D) F3: [C] -> [D]
R4(D,E,C) F4: [D, E] -> [C]
R5(C,E,A) F5: [C, E] -> [A]
R6(B,E) F6: 0
El diseño es EFICIENTE.
[A, C] -> FNBC
con dfs: [[A] -> [C]]
cc: [[A]]
[B, C] -> FNBC
con dfs: [[B] -> [C]]
cc: [[B]]
[C, D] -> FNBC
con dfs: [[C] -> [D]]
cc: [[C]]
[D, E, C] -> 3FN
con dfs: [[C] -> [D], [D, E] -> [C]]
cc: [[E, C], [D, E]]
[C, E, A] -> 3FN
con dfs: [[A] -> [C], [C, E] -> [A]]
cc: [[E, A], [C, E]]
[B, E] -> FNBC
con dfs: []
cc: [[B, E]]
Descomposición
en FNBC sin perdida de información
(FALTA ARREGLAR)
Encuentra una descomposición en FNBC (forma normal de Boyce-Codd)
sin perdida de información.
Ej:
Descomposición sin perdida de información en FNBC.
Relación:
[A, B, C, D, E]
Dependencias:
[[A] -> [C], [B] -> [C], [C] -> [D], [D, E] -> [C], [C, E] -> [A]]
(A,C)
dfs:
A->C
FN: FNBC cc: [[A]]
(D,E,A)
dfs:
A->D
D,E->A
FN: 3FN cc: [[E, A], [D, E]] <--- ESTA MAL!
(B,D)
dfs:
B->D
FN: FNBC cc: [[B]]
(B,E)
dfs:
FN: FNBC cc: [[B, E]]
NO SE PIERDE INFORMACION.
SE PIERDEN DEPENDENCIAS.
------------------------------------------------------------------------
Notas:
Si desea ingresar un juego de dependencias funcionales nulo ingrese
todos los atributos de la relación determinando a todos
los atributos
de la relación (R>R):
Ej:
Relación:
A,B,C;
Dependencias:
A,B,C>A,B,C;
------------------------------------------------------------------------
Porque FPlus Applet usa Java plug-in?
Lamentablemente el soporte nativo para Java de Internet Explorer
5.x o
Netscape Communicator 4.x es OBSOLETO. Estos navegadores soportan
Java
1.1 o inferior y la version actual de Java es la 1.4. Esta version
previa
al lanzaminto de los componentes graficos Swing solo puede hacer
uso
de unos 10 componentes AWT (interface gráfica obsoleta de
Java).
Lo que es peor, cada browser implementa Java 1.1 de forma diferente
e
inconsistente.
Además FPlus hace uso de ciertas clases introducidas
en versiones de Java
posteriores a 1.1 como:
- Set
- Collection
- Iterator
- Vector (nueva versión)
Esperamos que los browsers más usados actualizen pronto su
implementación
de Java hasta por lo menos la version 1.2.2. Mientras tanto solo
nos queda
usar el Java plug-in
u optar por browsers con un buen soporte de Java como:
- HotJava
- Opera
FPlus: Algunos algoritmos para bases de datos
by German Viscuso
netquake@netquake.com.ar