miércoles, septiembre 24, 2008

Generalizando

Me voy a poner un poco técnico, pero es una historia que puede ser útil para algún otro investigador allá afuera; y si no le sirve a nadie, al menos es una anécdota interesante.
Tengo que explicar primero en qué he estado trabajando. En pocas palabras, supongan que tienen un complejo sistema de información de negocios, así como una serie de permisos que se le asignan a la gente que dicen qué información pueden ver. Como un ejemplo, un empleado no debe poder ver el salario de su jefe, pero sí su propio salario. Dualmente, el jefe debe poder ver su propio salario y el de su empleado.
Ahora, para simplificar la asignación de permisos, estos están estructurados, formando un órden de tal forma que alguien que tiene un permiso "arriba" de otro permiso, puede ver todo lo que autoriza el permiso inferior (y posiblemente, algunas cosas adicionales). Por supuesto, este órden no tiene por qué ser total en general. Como ejemplo, el jefe de desarrollo no tendría por qué estar arriba o abajo del jefe de ventas. En ese sentido, los permisos que ellos tienen son incomparables.
Básicamente, esta estructura de permisos forma una lattice. Si empezamos con eso, es muy simple demostrar que podemos diseñar algoritmos basados en reglas que digan qué cosas puede ver alguien y qué no. Una propiedad interesante de estos algoritmos es que dan el mismo resultado (correcto) independientemente del órden en que se apliquen las reglas.
La pregunta es, ¿podemos generalizar esto?
Bueno, pues empezamos a analizar y vemos que, debido a ciertas operaciones que necesitamos en nuestro algoritmo, lo mínimo que necesitamos es un semianillo. Listo. Ahora, nos gustaría tener la misma propiedad en que no importa el órden en que las reglas se apliquen, para eso necesitamos un semianillo distributivo. ¿Algo más? Parece que no. Empezamos a demostrar cosas y vemos que todo parece funcionar. Las demostraciones son un poco más complicadas, pero eso no es un impedimento para la veracidad de la teoría. Y seguimos demostrando.
Habiendo visto que todo parece funcionar, lo único que nos falta es definir un orden adecuado. Y aquí nos topamos con algo extraño y útil: ¡en todo seminaillo distributivo, el producto es idempotente! Esto es útil porque nos da una forma de definir el órden que queremos, es extraño porque los axiomas de semianillos, junto con la distributividad hacen que el producto y la adición se comporten más o menos de la misma forma. Y la pregunta obvia es ¿es la adición también idempotente?
Pues sí, lo es. Y esto significa que todo semianillo distributivo es de hecho una lattice. Y regresamos a donde empezamos.

1 comentario:

juan antonio dijo...

Jeje.. cuando lo iba leyendo pensaba: “si, lo que está intentando parece muy natural, ¿no habrá ya alguien hecho esto antes?” Cuando leí el final, entendí porque quizá si alguien lo hizo no lo llegó a publicar :-P

Odio/adoro cuando esto igual me pasa.