The Stanford GraphBase: 1990 Football Season

This book is -as the title says- a platform for combinatorial computing, based on literate programming also developed by Knuth. It has good sets of data, samples and good and speak at length on of them.

There are several challenge problems and one on unsolved most popular is the 1990 season football: Stanford against Harvard. In the book appears Knuth's best solution, however later appears a research made by Buel Chandler with genetic algorithm obtaining a better result and lately in 2002 Mark Cooke found an even better (the best until now).

Despite to these solution this is a similar to TSP, where still is unknown the best solution, then you can give time to research on this problem.

A nice problem was to do a Regular Expression to parse from the file of games the teams, score and stats from reporters. My best solution is this huge RegExp: (which is accurate enough and to be used with java.util.regexp).

([A-Z]\\&?\\-?)+\\ (([A-Z][a-z]*\\\\?\\&?\\,?\\-?\\ ?)+\\(([A-Z][a-z]+\\-?\\'?\\ ?(\\\\\\&)?\\ ?)+\\)([A-Z][a-z]+\\ ?\\-?)+)\\;[0-9]*\\,[0-9]*\\;[0-9]*\\,[0-9]*

There are 120 teams (nodes) with 638 games (edges). The following graph shows the season:

Knuth has provided all the files for the Stanford Combinatorial platform, where you can find the football.dat file with all the teams and games between them. Above is the graph representing the whole season and following is the data in a more graph viewing of the games (different from the original file that is a single row result of a game pattern).

JAAS y SecurityFilter

La seguridad es uno de los aspectos a resolver con importancia en estos dias tal como nos dice Cobit y también diferentes ISO's, y por ello un punto importante dentro de cualquier proyecto.

La seguridad se centra sobre dos conceptos básicos: autenticación y autorización. Usuarios se autentican al sistema probando que son lo que dicen ser, por mientras la autorización permite/no-permite acceso a ciertas áreas de la aplicación.

La arquitectura J2EE tiene resuelto (y sus contenedores) este paradigma a través de Java Authentication and Authorization Service (JAAS), la cual es un conjunto de packages con servicios para autenticar y controlar de acceso de una manera centralizada (en un descriptor), conviviendo con el contenedor web que la aplicación este utilizando (Jakarta Tomcat, JBoss, otros).


Esta forma de seguridad puede ser administrada a base del contenedor (container-managed security) o de la aplicación (application-managed security).

1. Esta primera opción, de tener dependencia del contenedor, aumenta la complejidad de administración ya que hay que preocuparse de este contenedor en particular aparte de la aplicación como tal, quedando dividida y preocupándose de ambas. (Ejemplo especificar el repositorio donde se encuentra el real, nombre de usuario, password de roles, etc.).

2. La segunda forma es lograr que la aplicación posea toda la responsabilidad haciéndola más compleja de desarrollar y logrando que su escalabilidad queda segmentada a la solución hecha. La solución implementada en nuestro proyecto es una solución híbrida en la cual dejamos la responsabilidad de la seguridad a la aplicación (autenticación y autorización) a través de un robusto proyecto open source llamado SecurityFilter que genera filtros Servlet para su control. Se logra tener la flexibilidad de una seguridad de aplicación, logrando dejar independiente el contenedor (por ejemplo por su posible migración de arquitectura de conexión de base de datos).

Autenticación Form-Based + SecurityFilter

Los contenedores web J2EE ofrecen tres tipos de mecanismos de autenticación: basic, form-based, y autenticación mutua. La mayoría de las aplicaciones web usan el tipo de form-based ya que permite que la interfaz del usuario sea personalizable (HTML). La autorización es implementada por los contenedores a través de roles de seguridad definidos en el descriptor de la aplicación web (web.xml).

SecurityFilter usa la misma arquitectura que Form-Based donde se configura a través de descriptores en la aplicación.

Existe web.xml donde colocamos el uso del filtro de servlet en la aplicación y que realmente es nuestra forma de seguridad, esta se ve así:

<filter>
  <filter-name>Security Filter</filter-name>
  <filter-class>org.securityfilter.filter.SecurityFilter</filter-class>
  <init-param>
    <param-name>config</param-name>
    <param-value>/WEB-INF/securityfilter-config.xml</param-value>
    <description>Configuracion</description>
  </init-param>
  <init-param>
    <param-name>validate</param-name>
    <param-value>true</param-value>
    <description>Validar debe ser verdadero</description>
  </init-param>
</filter>

Con ello nos permite personalizar cuales son las páginas de ingreso y no-autorización a la aplicación (con sus URLs respectivas):

<login-config>
  <auth-method>FORM</auth-method>
  <form-login-config>
    <form-login-page>/jsp/publico/Index.jsp</form-login-page>
    <form-error-page>/jsp/publico/errorauth.jsp</form-error-page>
    <form-default-page>/LoginCliente.do</form-default-page>
  </form-login-config>
</login-config>
Se pueden mencionar los siguientes Tags principales que pueden ser descritos en el web.xml

• <login-config>: especifica el tipo de configuración de registro (login). Puede incluir los siguientes subelementos
• <auth-method>: opcional
• <realm-name>: opcional
• <form-login-config>:opcional


• <form-login-config>: Específica los recursos utilizados en el registro login basado en formularios. Debe contener los subelementos siguientes:
  
  <form-login-page> y <form-error-page> siendo los dos requeridos.


• <form-login-page>: especifica el nombre de un recurso (html, página JSP, servlet) que solicita el nombre de usuario y la contraseña. Esta página debe cumplir los siguientes requisitos


1. El formulario debe utilizar METHOD = “POST” y ACTION=”j_security_check”
2. El campo de nombre de usuario debe denominarse j_username
3. el campo de contraseña debe denominarse j_password.


• <form-error-page>: Especifica el nombre de un recurso (HTML, JSP, servlet) a mostrar cuando el registro basado en el formulario no sea correcto.


• <auth-constraint>: Especifica una lista de nombres de funciones (o roles) tratada colectivamente en un elemento <security-constraint>. Puede contener los siguientes subelementos <description> el cual es opcional y <role-name> (cero o más).


• <role-name>: Un nombre utilizado para identificar una función o rol con el que un usuario autenticado se puede registrar. Es el mismo valor especificado en el método request.isUserInRole() para permitir la ejecución condicional de partes de un servlet a
  usuario con roles o funciones diferentes.

Por motivos de estructura similar a J2EE el formulario HTML tiene que tener la siguiente estructura de los campos j_username y j_password con el nombre de acción j_security_check como lo podemos ver en el ejemplo:

<form method="POST" action="j_security_check">
  <input type="text" name="j_username">
  <input type="password" name="j_password">
</form>
Esta forma de conexión usa codificación de base64, que puede exponer el nombre de usuario y clave a menos que sea con conexiones SSL.

Así los pasos que usamos son:

1. Si el usuario no ha sido autenticado, le pide al usuario que de sus datos para tal acción recarga -a la página de ingreso (login) definida en el descriptor.


2. Valida las credenciales del usuario contra la base de datos ya que es parte de nuestra aplicación.


3. Determina si el usuario autenticado entonces está autorizado a ingresar al área solicitada según el descriptor.

Autorización

Una vez autenticado obtenemos el rol que posee y se verifica si puede asignar a los recursos solicitados, SecurityFilter tiene un archivo llamado securityfilter-config.xml el cual tiene centralizado todas las páginas que se puedan acceder según rol definidos en la aplicación (y también aparezcan en la base de datos, cual es nuestro repositorio).

De esta forma podemos administrar de manera fácil que rol tiene derecho de acceso a que Actions de Struts o JSP, según la lógica de negocio diseñada.

Ejemplo:

<security-constraint>
  <web-resource-collection>
  <web-resource-name>Pagina seguras Clientes</web-resource-name>
    <url-pattern>/jsp/cliente/*.jsp</url-pattern>
    <url-pattern>/RegistroObra.do*</url-pattern>
  </web-resource-collection>
  <auth-constraint>
    <role-name>cliente</role-name>
  </auth-constraint>
</security-constraint>

En este ejemplo podemos ver como se está asignando acceso a los JSP y un Action en particular únicamente a los usuarios que posean rol de “cliente”:

Además SecurtyFilter nos permite aun utilizar los métodos getRemoteUser(), isUserInRole(), y getUserPrincipal() para generar dentro de la aplicación reglas de seguridad a nivel de código Java.

Ventajas

• La aplicación no necesita tener implementado el mecanismo de autenticación, sólo configurar los descriptores.

• Con SecurityFilter la idea es empaquetar la seguridad dentro de la aplicación web, incluyendo la administración de roles, permitiendo generar un .war que puede liberarse en cualquier contenedor sin necesidad de configurar nada extra.

Bibliografía

• http://securityfilter.sourceforge.net/ Security Filter utilizado en el proyecto
• http://java.sun.com/products/jaas/reference/docs/index.html JAAS Reference Documentation
• http://www.onjava.com/pub/a/onjava/2002/06/12/form.html J2EE Form-based Authentication

iBATIS - The Beauty of Simplicity

When I was involved in a project for a Strength of Materials Certification Laboratory for my University, the solution included open source frameworks as Struts as presentation tier. but I had a doubt of connection tier.

The good point is Data model, tables, data, exist already, SQL queries I was going to be help for a student of last year, even more I could use some and I needed a simple solution, so EJB is discard immediately, Hibernate sound good (I reckon is the Object related tool on web today, but I need something simple and clean) then I remember I heard iBATIS as a easy-fast productivity SQL Mapper framework.

iBATIS gives all what I need, centralized management, easy of implement writing down all the SQL queries I need, linking them in a ResultSet (and JavaBean) and another doing the JSP interface (actually the html:form tags).



Thus the code could be reduce a lot, not doing those JDBC statement (mention above), besides I made a simple Java code to help writing down SQL maps and JavaBean (well, later on I knew there is Perl tool that do this better with DDL from the database: http://alxeg.narod.ru/ibatis/index.html . However my tool worked parsing , so it can read the name of the fields and make the JavaBean and XML; (this reduce even more the coding).

Another parameter to consider was iBATIS born mature :) because after sun shows Jpetstore with better performance than Microsoft and release the interesting framework layer including SQL Maps and DAO.

Finally, the iBATIS web scene was mature enough to get support for any issue on it. Plus the development team is still working hard enough to get more update version, solving some unexpected issues (you never know and it’s better to have some backup).
iBATIS mapped framework according to ibatis.apache.org, it has two important features, SQL maps and DAO -the last one we are going only mention because mapping is our main issue-

SQL Maps makes development much easier, and the maintenance too.

The Architecture of iBATIS is:

Centralized SQL Mappings inside XML files, this way is easy to maintenance, flexible , scability, fix problems. Every java programmer knows how tedious is to code many times JDBC connection, making the code larger, more complex to read and worse to maintain and scability.



figure 1, taken from http://ibatis.apache.org/

architecture of iBATIS










<-- figure 2 --> data model of the example: entities (client, application_form, application_form_detail).

Here we configure the database properties (too redundant? :P)database.properties:
driver=org.firebirdsql.jdbc.FBDriver
url=jdbc:firebirdsql:localhost/3050:C:/development/database/SAMPLEDBS.GDB
username=administrator
password=development2006

This file contains all the XML with SQL Maps
sql-map-config.xml:
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE sqlMapConfig
PUBLIC "-//iBATIS.com//DTD SQL Map Config 2.0//EN"
"http://www.ibatis.com/dtd/sql-map-config-2.dtd">

<sqlMapConfig>

<properties resource="database.properties" />

<transactionManager type="JDBC">
<dataSource type="SIMPLE">
<property name="JDBC.Driver" value="${driver}"/>
<property name="JDBC.ConnectionURL" value="${url}"/>
<property name="JDBC.Username" value="${username}"/>
<property name="JDBC.Password" value="${password}"/>
</dataSource>
</transactionManager>

<sqlMap resource="TmpIndicesSQL.xml" />
<sqlMap resource="DetalleSolicitudSQL.xml" />

</sqlMapConfig>

An example of SQL Map, showing how to make ResultSet, INSERT, SELECT and UPDATE statement, with dynamic concatenation of condition in the statement (AND/OR in the WHERE).
DetalleSolicitudSQL.xml:
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE sqlMap PUBLIC "-//iBATIS.com//DTD SQL Map 2.0//EN"
"http://www.ibatis.com/dtd/sql-map-2.dtd">
<sqlMap namespace="DetalleSolicitudSQL">

<cacheModel id="detallesolicitud_cache" type="MEMORY" >
<flushInterval hours="24"/>
<flushOnExecute statement= "insertDetalleSolicitud" />
<property name="reference-type" value="WEAK" />
</cacheModel>

<resultMap id="detallesolicitud_result" class="cl.unab.dicemat.utils.facade.DetalleSolicitud">
<result property="detsol_descripcion" column="x_detsol_descripcion" />
<result property="detsol_cantidad" column="x_detsol_cantidad" />
<result property="ens_cod_tipo" column="x_ens_cod_tipo" />
<result property="solcer_id" column="x_solcer_id" />
</resultMap>

<statement id="insertDetalleSolicitud">
INSERT INTO detalle_solicitud ( detsol_descripcion, detsol_cantidad, ens_cod_tipo, solcer_id )
VALUES ( #detsol_descripcion#, #detsol_cantidad#, #ens_cod_tipo#, #solcer_id# )
</statement>

<statement id="viewDetalleSolicitud" resultMap="detallesolicitud_result" cacheModel="detallesolicitud_cache">
SELECT detsol_descripcion AS x_detsol_descripcion,
detsol_cantidad AS x_detsol_cantidad,
ens_cod_tipo AS x_ens_cod_tipo,
solcer_id AS x_solcer_id
FROM
detalle_solicitud
</statement>

</sqlMap>
with a select to get a autoincrement key for Firebird database (also there is commented examples for PostgreSQL, in (2) you can get more code to different engines). This features that iBATIS has implemented for most DB engines, but still aren't 100% solve in the current time, however I could solved doing another query, leaving atomized and thread-safe. (I can show the example with Firebird). The good thing was the flexibility iBATIS has to go through this problem.

IndiceSQL.xml:

<resultMap id="tmpindices_result" class="cl.unab.dicemat.utils.facade.TmpIndices">
<result property="tabla" column="x_tabla" />
<result property="obra_id" column="x_obra_id" />
</resultMap>

<!--obra_id y tabla hacen solo de nombres genericos -->

<statement id="viewTmpIndices" resultMap="tmpindices_result" cacheModel="tmpindices_cache">
SELECT gen_id(GEN_SOLICITUDCERTIFICADO, 1) as x_obra_id,
rdb$$relation_id as x_tabla
FROM
rdb$$database
</statement>
SolicitudCertificadoAction.java snippet
The simple method dao.insertSolicitudCertificado(solicitudCertificadoDTO); insert the data in the javabean. Using beanutils commons.

SolicitudCertificadoForm.java, dynaform can be used, however I prefer to use normal JavaBean thus I can maintain the kind of data (int, String, Date).


Conclusion:

We finally are in the last stages of the project doing QA, the SQL Mapping was a success, I saved a lot of time though this framework. Getting a simpler and cleaner code, the performance of the application.


Bibliography:

iBATIS Home- ibatis.apache.org
iBATIS Wiki- http://opensource.atlassian.com/confluence/oss/display/IBATIS/Home
iBATIS mailing-list

Dragon Book New Edition

After 20 years appears Compilers: Principles, Techniques, and Tools, 2/E by Alfred V. Aho, from AW page says: "The authors, recognizing that few readers will ever go on to construct a compiler", this is a big truth nevertheless is an must reading. (besides if you ever need to know formal introduction and beyond from Regular Expressions this is the book you must read).

New chapters include:

Chapter 10 Instruction-Level Parallelism

Chapter 11 Optimizing for Parallelism and Locality

Chapter 12 Interprocedural Analysis

Besides the cover always have caught my attention, right now has a graphics render against pencil drawing.

Bitwise Tricks and Techniques

Dr. Knuth has released a new version Pre-Fascicle from his famous TAOCP called Bitwise Tricks and Techniques.

Please, go to http://www-cs-staff.stanford.edu/~knuth/news.html to download the postscript, also can be found an update to:


* Pre-Fascicle 0b: Boolean Basics (version of 20 Dec 2006)
* Pre-Fascicle 0c: Boolean Evaluation (version of 20 Dec 2006)


As usual it’s a important collection of many paper, books, articles retrieved through years by Donald Knuth and includes many work by himself (also asking if someone has done some research before to give correct acknowledge).

XML + RegExp = Relax NG

Although it’s an “old” definition for validation of XML, now Relax NG is being considered to integrated inside Sun development mentioned by: Tim Bray. With this has a new revival interest on it.
We can see the beauty of simplicity on this project:

In science, strong theories tend to be simple, yet have almost infinite potential for complexity in application. RELAX NG is, because of its simplicity, one of those theories that is easy to explain, easy to implement, and generic and flexible enough to meet the most stringent requirements.

Eric van der Vlist, RELAX NG, O’Reilly ,2003.
more information can be found at: http://relaxng.org and its most important implementations at the moment in Java are Jing and The Sun Multi-Schema XML Validator (MSV).

Balanced Design

Like most thing in life we have to choose, become, behave in a balanced way. Always there are consequences opting an extremity. Similar to Statistics where it can be shown in a graph like the Gaussian Distribution:

This also can be seen in language programming (i.e. the level of encapsulation, factorization, etc.) and even in design. The classic book Design Patterns from GoF identifies 23 patterns cataloging them under 3 classifications (creational, structural, behavioral).

The level, granularity and quantity you use them depends on several factor, nevertheless it is not advisable apply to used all of them at once, like in the following interview Eric makes mention of a similar case.

Do not start immediately throwing patterns into a design, but use them as you go and understand more of the problem. Because of this I really like to use patterns after the fact, refactoring to patterns. One comment I saw in a news group just after patterns started to become more popular was someone claiming that in a particular program they tried to use all 23 GoF patterns. They said they had failed, because they were only able to use 20. They hoped the client would call them again to come back again so maybe they could squeeze in the other 3.

Trying to use all the patterns is a bad thing, because you will end up with synthetic designs—speculative designs that have flexibility that no one needs. These days software is too complex. We can’t afford to speculate what else it should do. We need to really focus on what it needs. That’s why I like refactoring to patterns. People should learn that when they have a particular kind of problem or code smell, as people call it these days, they can go to their patterns toolbox to find a solution.

How to Use Design Patterns A Conversation with Erich Gamma,
http://www.artima.com/lejava/articles/gammadp.html

From Ajax in Action book called this symptom (or condition) of overused of patterns as paralysis by analysis.

We can conclude, First try to make your first effort coding (of course there is analysis and design before, but we are stand at development and trying to refactor the solution) unless you have already the experience to use a known pattern to a particular problem then try to use some pattern from the catalog, and use them carefully, remember the first and final idea is to make things more simple, elegant and not chaos.

Knuth Selected Papers

Dr Knuth has been publishing compilations of his papers in different subject he is involved, as wide as literate programming until recreational mathematics, This is a good compendium of his work.
the list is:

1. Literate Programming (1992)
2. Selected Papers on Computer Science (1996)*
3. Digital Typography (1999)
4. Selected Papers on Analysis of Algorithms (2000)*
5. Selected Papers on Computer Languages (2003)
6. Selected Papers on Discrete Mathematics (2003)
7. Selected Papers on Design of Algorithms (2007)*
8. Selected Papers on Fun and Games (2007)*

at his page you can find more information.
http://www-cs-faculty.stanford.edu/~knuth/selected.html

Besides there is

• Companion to the Papers of Donald Knuth*

Eclipse JSP Styles

I have been seen how Eclipse IDE has been growing by the community, sometimes with huge improvement for code donation, however there are some features left that can be found in the plug-ins, but not always, by instance in JSP editing (inherated form Lomboz plug-in) it use to be yellow all the tags from Struts/JSTL/etc. and leaving blank the rest helping to see more easily the JSP/Tag code from Javascript/HTML.

This works great for Struts framework pages, where coexistence between HTML and Struts/JSTL Tags is important, but now working with JSF it is not for much help because here (at least for a average scenario) our code doesn’t contain traditional HTML tags (or a few tags) only JSF-HTML tags, so the final rendering it’s only a yellow stain, thus we better change under:

Window->Preferences->Web and XML->JSP Files->JSP Styles

the “Restore Defaults” and has a better looking. nevertheless if we open a struts projec again we loose this yellow easy to see feature, just right here we can change outside the IDE itself the following file

org.eclipse.jst.jsp.ui.prefs

which can be found at

.metadata/.plugins/org.eclipse.core.runtime/.settings

inside can be seeing verbatim the codes of the colors:

#Fri Sep 30 15:10:35 VET 2005
tagBorder=\#008080 | \#ffff80 | false
tagAttributeName=\#7f007f | \#ffff80 | false
tagName=\#3f7f7f | \#ffff80 | false
org.eclipse.wst.sse.ui.custom_templates=\r\n
SCRIPT_AREA_BORDER=\#bf5f3f | \#ffff80 | false
tagAttributeValue=\#2a00ff | \#ffff80 | false
jsp_content=null | \#ffff80 | false
eclipse.preferences.version=1
commentBorder=\#3f5fbf | \#ffff80 | false
commentText=\#3f5fbf | \#ffff80 | false

the .metadata directory can be found in your workspace -your workspace by default is under eclipse directory, however is a good practice is to have it in a different place (and your plug-ins too).

Fractal Pop Beverage

although today fractal are used commonly in graphics design, television and any graphics interpretation, seeing spectacular images from http://ziza.ru/2006/05/24/otlichnaya-podborka.html, this image in particular still takes my attention for using in a very good way a fractal sensation
(please see the original image, there you can appreciate what I mean).

I don’t know which tool the artist used however you can do interesting artwork with: ultra fractal (shareware) and with povray also (but this last program is not fractal oriented as the first one and it uses a script language).