SQL Diagram creation

sql2diagram

We wrote this tool a while ago in C/C++ and uploaded it to sourceforge: http://sql2diagram.wiki.sourceforge.net/

functionality:

• it reads the SQL tables and attributes from the SQL file with all the CREATE TABLE statements
• it generates HTML documentation
• it is able to generate diagrams for the DIA program (http://live.gnome.org/Dia)
• it generates an HTML map for the diagram png file, and links to it from the HTML documentation

The generation of the HTML documentation works fine.

diagrams

There are some problems with generating the diagrams. On the one hand it allows manual moving of the tables and connections in the dia editor, and the sql2diagram tool should pick up the manual positions and reuse them. But on the other hand, it is quite tedious to move the tables and foreign key constraints all by hand.

Task 1: Use the new Database tools, instead of the ER shapes

Database shapes were only added recently to dia, and might look better than the ER shapes we are using currently.

Task 2: Do an automatic layout of the tables and connections

Alternatives:

• I had a look at autodia, but it seems you still have to rearrange the result in the dia editor.
• http://www.rbt.ca/autodoc/output-dia.html states on the website that they do not do the positioning.
• MS Visio can do it ;) http://soccerproject.wordpress.com/2008/12/05/creating-a-postgresql-database-diagram/
• http://sqldeveloper.solyp.com/index.html: works against a Mysql database; automatic layout of diagram

Some discussions and first hints:

• There was a discussion on the mailing list Avoiding connection conflicts/cross-overs in UML diagrams
• The ZigZag links have already an autoroute functionality: http://git.gnome.org./cgit/dia/tree/lib/autoroute.c
• there could be python plugin similar to http://svn.gnome.org/viewvc/dia/trunk/plug-ins/python/autolayoutforce.py
  • (I was not able to get the python plugin to work with dia on windows)
• the discussion on the mailing list mentions Force based algorithms for the positioning

So my approach to Task 2 would be to use some good algorithms when arranging the diagram, and make sure the generated diagram has the tables in the best position (most referenced tables in the centre, tables that are most linked to each other closest to each other), and the linking constraints are not crossing any tables, and are still possible to be read.

• For the maths side: The Boost Graph Library (BGL) might be helpful.
  • see explanation of shortest path algorithms: http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/graph_theory_review.html#sec:shortest-paths-algorithms (I am not sure if that is really the right answer to the problem; this is a bit too complicated for me...)

• path finding: Once the tables are positioned, we could use a pathfinding algorithm for the constraints:
  • http://ai-depot.com/Tutorial/PathFinding.html Good Tutorial about path finding
  • http://en.wikipedia.org/wiki/Pathfinding
  • http://www.gamedev.net/reference/programming/features/astar/ A* Pathfinding for Beginners
  • a GPL path finding implementation in C: http://marathon.svn.sourceforge.net/viewvc/marathon/trunk/Source_Files/GameWorld/pathfinding.cpp
  • see also http://lib2dp.sourceforge.net/ 2DPathfinder is a C library for performing fast pathfinding on 2D maps.