Métricas sobre modularización de KB

Cuando tengo un sistema desarrollado, tengo muchísimas formas de dividirlo en módulos. Segun la bibliografia, el problema mas general de particionar un grafo en diferentes agrupamientos de nodos (clusters) es considerado NP-Completo, por lo que no se ha encontrado aun una forma eficiente de resolverlo.

Al tener tantas opciones, es bueno contar con alguna herramienta que me permita medir que tan buena o mal es dicha division, en el caso de una KB, seria medir que tan buena o mala es la modularizacion que he realizado.

Algunas de las características perseguidas por la modularizacion, son la de tener un gran cohesion entre los nodos que están dentro de un modulo y tener poco acoplamiento con otros módulos.

Esto se traduce, a que queremos maximizar las  aristas dentro de los módulos y minimizar las aristas entre los módulos.

Resulta mas facil, verlo en imagenes. Supongamos que tenemos un grafo que representa la relaciones entre objetos. Los objetos pueden ser cualquier objeto ejecutable (procedimientos, data providers, data selectors, web panels, SDPanels, etc) y tambien tablas que son leidas o actualizadas por dichos programas. No se consideran ningun de los objetos "no ejecutables" como las instancias de patterns, atributos, folders, modulos, documentacion, diagramas, etc.

Un ejemplo, de una KB muy sencilla con un unico modulo, seria:

En este caso, todos las llamadas serian INTRA-modulo.

En el otro extremo, podemos definir un modulo, por cada objeto:

En este caso, todas las llamadas serian INTER-modulos.

En un caso mas util, podria definir dos modulos de la forma:

con lo cual, tendriamos llamadas INTER e INTRA modulos.

Indicador de cohesion. 

Para cada modulo, podemos contar la cantidad de aristas intra-modulos y dividirla por la mayor cantidad de aristas posibles (es la cantidad de nodos del modulo al cuadrado).

Por ejemplo, si tengo el módulo1:

que tiene

Cantidad de aristas intra-modulo = 3
Cantidad de aristas posibles = (Cantidad de Nodos del Modulo) al cuadrado = 9

Indicador A1 = 3/9 = 0.3333....

Este valor, (que va a estar entre 0 y 1) querriamos que fuera lo mas alto posible y lo podremos mejorar, moviendo nodos de un modulo a otro.

Indicador de acoplamiento. 

Dado dos modulos, M1 y M2, cada uno con N1 y N2 nodos respectivamente.
Queremos medir que tan acoplados estan dichos modulos, por lo que podemos definir un indicador que mire la cantidad de aristas que une un modulo con el otro y dividir entre la cantidad posible de arcos que puede tener entre ambos (2 * N1 * N2)

Por ejemplo, si tenemos

M1
Cantidad de Nodos = N1 = 3

M2
Cantidad de Nodos = N2 = 4

El indicador de acoplamiento entre M1 y M2 se llama E12 y se puede calcular

E12 = Cantidad de aristas entre M1 y M2 / Cantidad de aristas posibles entre M1 y M2

E12 = 1 / (2*3*4) = 1/24.

Este indicador va a estar entre 0 y 1.
Siempre trataremos de minimizar este indicador entre los diferentes modulos, de forma que queden bien desacoplados, o sea tener modulos lo mas independientes posibles, lo cual hara que sean mas faciles de mantener.

Indicador de Modularizacion MQ  

Si tenemos un buen indicador para la cohesion (que queremos maximizar) y un buen indicador para el acoplamiento (que queremos minimizar) podemos unirlos en un unico indicador que sea:


MQ = Suma indicadores de cohesion de todos los modulos - Suma indicadores de acoplamiento para todo par de modulos.

Para poder tener un indicador que sea comparable en forma independiente de la cantidad de modulos que tenga la KB, se puede normalizar por dicha cantidad, con la que la formula definitiva quedaria.

donde k es la cantidad de modulo de la KB, Ai es el indicador de acoplamiento del modulo i y Eij es el indicador de acoplamiento entre el modulo i y el modulo j.

Algunos ejemplos

Solo un modulo

En el caso de tener solo un modulo en la KB, tendriamos

k = 1
A1
 Cantidad de aristas intra-modulo = 9
 Cantidad de aristas posibles - intra-modulo = 7 Nodos al cuadrado = 49

A1 = 9 / 49 = 0,183

MQ = 0.183

Siete Módulos

En este caso, tenemos 

k=7

A1-A7 

 Cantidad de Aristas intra-modulo = 0

 Cantidad de Aristas posibles intra-modulo = 1

  A1-A7 = 0

E12

Cantidad de Aristas entre modulos 1 y 2 = 1

Cantidad de Aristas posibles entre modulos 1 y 2 = 2*1*1 = 2

E12= 0.5

Se puede seguir calculando y tenemos

Por lo que el indicador MQ quedara

MQ = Suma A1-A7 - (1/(k(k-1)/2) * Suma Eij (i=1 a 7, j=1 a 7)

MQ = 0 - (1/(7*6/2)) * 4,5 = -0.214 

MQ=-0.214

Ejemplo 2 Módulos. 

A1 = 3 aristas intra modulo / 9 aristas posibles = 0.333

A2= 5 aristas intra modulo / 16 aristas posibles = 0.313

E11 = 0

E12 = 1 arista entre modulos / (2* 3 nodos en M1 * 4 nodos en M2) = 0,041

E21 = 0

E22 = 0

MQ = 1/2 * (A1+A2) -  (1/(2*1)/2) (E11+E12+E21+E22) = 0.343  - 0,041 = 0,302

MQ = 0,302

Conclusiones

El indicador MQ, va a estar entre -1 (sin nada cohesion) y 1 (sin acoplamiento entre módulos y un grafo con todas las aristas dentro de los nodos del modulo).

Cuanto mayor sea el MQ va a ser una modularizacion mejor.

Esta metrica no es demasiado eficiente en su cálculo, pero es fácil de entender.

Teniendo un indicador, hace posible tener una herramienta que compare dos modularizaciones y elija la mejor. Es el primer paso para hacer una modularizacion semi-automática.

UPDATE: En caso de querer utilizar pesos en las aristas, por ejemplo para hacer pesar mas una referencia del tipo ACCEDO A TABLA, que LLAMADO A API, se puede utiliar el siguiente indidador.

donde

= suma de los pesos de arcos intra-modulo

= suma de los pesos de los arcos inter-modulos

Es un poco mas rápida para calcular y permite manejar mejor referencias de diferente peso. El 1/2 es para hacer pesar en ambos módulos el peso de las aristas entre ambos modulos.