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.




Comentarios

  1. Ojala que este año el tema de los módulos en el encuentro de GeneXus sea un tema relevante. Interesante como siempre tus entradas en este Blog.

    ResponderEliminar
    Respuestas
    1. No creo que el tema módulos sea un tema relevante, en este Encuentro. A pesar de ser un tema que ayuda muchísimo al desarrollo de aplicaciones, no despierta el interés necesario (aun) en la comunidad Genexus.

      Eliminar
    2. Muy bueno el análisis
      Tener este tipo de herramientas que nos permitan ver de manera objetiva, cuantificable es para profesionalizar el desarrollo

      Eliminar
    3. Gracias, me alegro que te gustara.

      Eliminar
  2. Justo estaba viendo algo de cómo agrupar (armar 'comunidades') las tablas y sus subordinadas para una Knowledge Base. Usando un software graficador [Gephi].
    Modularidad lo llama (Community detection algorithm)
    Y tiene otras varias estadísticas del grafo.

    Por ahora sólo 'jugando' con los gráficos que se arman y los grupos que quedan. Sólo con tablas, pero de ahí se puede llegar a los objetos GX que las usan/definen/etc.

    ResponderEliminar
    Respuestas
    1. Gephi es el mejor manejador de grafos que conozco.
      Hice una opcion en KBDoctor, para generar archivos .gexf.
      Tengo una opcion para generar el grafo de la relacion entre tablas y otro para los objetos y sus llamadas.
      Despues determino los componentes conexos de dicho grafo y generalmente me quedo con el mayor, es el que da mas dolores de cabeza.
      Teniendo ese, puedo determinar Clusters dentro del grafo, que ayuda a agrupar objetos y tablas, para definir modulos.

      Eliminar

Publicar un comentario

1) Lee el post
2) Poné tu opinión sobre el mismo.
Todos los comentarios serán leidos y la mayoría son publicados.

Entradas más populares de este blog

El Sordo

Paleta de colores en GeneXus