FPlus: Algunos algoritmos para bases de datos


* fplus website
* Public CVS web access
* fplus project page
* fplus Admin Page
* Download fplus
* fplus nightly CVS Tree tarball

  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
 

Relació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.

Dependencias funcionales

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;

Proyecciones

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;

Clausura

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]

Claves

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]]

Fmin

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]
 

Eficiencia

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.
 

Forma normal de Relación

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
 

Forma normal de Proyecciones

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
SourceForge Logo