Back to Main Page
Diploma Thesis (QUOGGLES)
Design and Implementation of an Extensible Query System for Graphs: dipthesis_paul_holleis.pdf
In 2003, Thomas Zimmermann, Daniel Gmach and me submitted a winning contribution to the Graph Draing Contest 2003 held in conjunction with the annual Graph Drawing Conference. The challange had been to emphasize the occurrences of many small subgraphs (called motifs in the context of biological research) in a large graph. To accomplish that, we experimented with several approaches. Our final contribution can be found in Graph Drawing Contest 2003.
During that time, it became clear that it would be fantastic to have a tool which could extract information from a graph: Nodes with certain properties should be selected, edges that connect certain nodes should be emphasized etc. This lead to my idea of creating a query system that
- is intuitive to use
- is simple to understand but still powerful enough
- has a graphical user interface
- can exchange information with a graph editor
- can save and load queries
- can use (intermediate) results as input to other queries
- is easily extensible
Having had those consideration in mind, I proposed this to Prof. Dr. Franz J. Brandenburg and Prof. Dr. Ulrik Brandes as the subject of my diploma thesis. They have both welcomed the idea and have been of great assistance and supported me from the start.
The project launched in July 2003 and I was able to hand the final version in after six month (i.e. the regular period for a diploma thesis in Passau) on January 12, 2004. It mainly comprised three parts:
- Design of the Query Language
- Design and Implementation of a Query Evaluation System
- Theoretical Comparison to Other Approaches (Relational Algebra, SQL)
The system has been implemented as a plug-in for the graph visualization toolkit Gravisto.
For inquieries, please contact me at firstname.lastname@example.org. The next part gives a short summary of the system.
QUOGGLES: QUery On Graphs - Graphical Largely Extensible System
QUOGGLES consists of
This system is available as a plug-in to the Gravisto toolkit (see the Gravisto page).
- a query language specially designed to work on graph data structures
- a graphical user interface to enter queries
- an algorithm for retrieving the result of a query
Why is QUOGGLES necessary?
Graph data structures are widely used to formalize and present information. Especially for data whose entities (nodes) are logically connected (edges).
Important for users of graphs is to retrieve information from such a graph. For a small set of nodes and edges, this might be done by looking at an arbitrary drawing of the graph. The reasons that some kind of query system is necessary are manifold: Larger graphs are nearly impossible to layout sensibly, complex attributes associated with graph elements can hardly be shown and a user presumably wants to work on the result of a query, to name but a few.
By using a carefully designed query language optimized for accessing graph data, an intuitive user interface and a powerful query evaluation algorithm, the QUOGGLES system provides the solution for the named problems.
How does it work?
The basic idea behind a QUOGGLES query is the pipeline principle. Input data (a graph) flows through several modules sequentially or in parallel. Those modules process this data, and produce some output. The user decides at which places she/he wants to observe the data. The output of a QUOGGLES query is a table the columns of which present the data of interest to the user.
This said, it is clear that a query form itself a graph. Since data is allowed to be passed in one direction only, the graph is directed. To avoid infinite loops, no circles are allowed. Thus, a query is a directed acyclic graph (DAG).
Executing a query means that the input is pushed into the first module, gets transformed and the output is pushed into the following module(s). This principle can only work if all inputs to a module are available before its outputs are accessed. Technically speaking, this implies a topological sorting which can be found for all DAGs.
More details can be found in the user manual.
As an example, the illustrated example page elaborates on a simple QUOGGLES query.
What Kind of Information can it Retrieve?
The theoretical part of the diploma thesis that initiated the project examined the power of queries in the QUOGGLES system. To summarize these considerations without going into more detail, it can be said:
- The basic system is not Turing complete. This results mainly from the absence of recursion in the query graph (the graph that describes the data flow is an acyclic graph).
- The basic system is relational complete. This means it is at least as powerful as relational algebra, i.e. it can simulate all those operations. This includes projection, selection, cartesian product and set union and set difference.
- The basic system can simulate SQL queries. This includes features like aggregate functions, arithmetic operations and grouping.
Remark: Since the system is very easy to extend in many ways, it is no problem to add functionality such that the system's power is enlarged to Turing completeness.
In order to be able to use QUOGGLES
- the Gravisto system must be installed and running
- the plugin files "plugin.xml" and "quoggles.jar" must have been downloaded
- the core Gravisto classes must be located on the classpath as must the following plugins:
Remark: Those plugins are automatically loaded when loading the "_Default Plugin Collection".
- Default GML Reader
- Default GML Writer
- Default Edit Components
There must be a running version of Gravisto. Choose the "Open plugin manager ..." item in the "Plugin" menu. Click on the "Open plugin ..." button and choose the "plugin.xml" file previously downloaded from the QUOGGLES web page. This should make the system available for Gravisto.
Open a (new) file. This enables the "QUOGGLES" (this name might be slightly different in your version) menu item in the "Plugin" menu. Choose this item and the QUOGGLES dialog window will appear.
Enter a query as described in the user manual. Clicking on the "Run Query" button will execute the query and show the result in a second table dialog.
Last modified: Wed Sep 20 17:19:59 W. Europe Daylight Time 2006