Back to Main Page
The QUOGGLES logo, inspired by its application.

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

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:

The system has been implemented as a plug-in for the graph visualization toolkit Gravisto.

For inquieries, please contact me at paulholleis@web.de. The next part gives a short summary of the system.

QUOGGLES: QUery On Graphs - Graphical Largely Extensible System

Overview

QUOGGLES consists of This system is available as a plug-in to the Gravisto toolkit (see the Gravisto page).

Description

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:

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.

Prerequisites

In order to be able to use QUOGGLES

Starting

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.

FAQ

Downloads


Last modified: Wed Sep 20 17:19:59 W. Europe Daylight Time 2006