Entwicklung einer Graphentechnologie für verteilte hierarchische Hypergraphen
Final Report Abstract
Der praktische Einsatz von Graphen als diskrete Modelle strukturierter Information in vielen Teilgebieten der Informatik hat gezeigt, dass binäre flache Graphen zur Repräsentation komplexer Zusammenhänge nicht immer ausreichen. Insbesondere mehrstellige Beziehungen und verschiedene Detaillierungsstufen einzelner Elemente und ganzer Modelle lassen sich mit binären flachen Graphen nicht auf natürliche Weise repräsentieren. Innerhalb dieses Projektes wurden binäre Graphen auf allgemeinere diskrete Strukturen, nämlich verteilte und hierarchische Hypergraphen (DHHTGraphen), verallgemeinert, um eine noch höhere Modellierungsmächtigkeit und damit eine noch breitere Anwendbarkeit zu erreichen. Gerichtete Hyperkanten mit angeordneten benannten Enden erlauben die natürliche Repräsentation mehrstelliger Beziehungen zwischen beliebig vielen Knoten. Die Modellierung verschiedener Granularitätsstufen von Knoten und Kanten wird dabei durch die Schachtelung von Graphen in Graphelementen ermöglicht. Darüber hinaus erlaubt das Konzept der Sichtbarkeitsebenen auch die Repräsentation unterschiedlicher Detaillierungsebenen von Graphen unabhängig von der Verfeinerung einzelner Elemente. Zum Einsatz als Datenstruktur in verteilten Anwendungen können DHHTGraphen auf verschiedene voneinander unabhängige Stationen verteilt und als lokal autonome Teilgraphen sowie als Gesamtgraph betrachtet werden. Ausgehend von einer Analyse existierender Ansätze für hierarchische Graphen und Hypergraphen und ihrer Erfassung in Referenzdefinitionen wurden in diesem Projekt Verteiltheit, Hierarchie und Hyperkanten konsistent miteinander integriert und als DHHTGraphen formal definiert. Die existierenden Ansätze lassen sich größtenteils durch Einschränkungen auf diese mathematische Definition abbilden. DHHTGraphen sind also eine sehr allgemeine Form verteilter hierarchischer Hypergraphen auf Basis der etablierten und sehr allgemeinen binären TGraphen. Deren Fähigkeit zur Typisierung und Attributierung von Knoten und Kanten sowie der Anordnung von Elementen in Graphen und der Inzidenzen an Knoten wurde für DHHTGraphen übernommen und insbesondere hinsichtlich des Hypergraphenkonzeptes angepasst. Zur Darstellung solcher Graphen wurde über den geplanten Projektumfang hinaus eine Visualisierung entwickelt. Auf der Grundlage der Definition wurde eine nahtlose Realisierung von DHHTGraphen geschaffen. Die Graphenmodellierungssprache grUML zur Spezifikation von Graphenschemata ermöglicht die flexible Verwendung des Ansatzes in einem breiten Anwendungsbereich. Die Sprache wurde in abstrakter und konkreter Syntax sowie formaler Semantik definiert und auf Basis des Rational Software Architect implementiert. Eine effiziente und vollständige Implementation aller formal definierten Eigenschaften in der Programmiersprache Java ist zusammen mit einer generischen Programmierschnittstelle die Grundlage des praktischen Einsatzes von DHHTGraphen. Diese bietet verschiedene Möglichkeiten zur gerichteten und ungerichteten Traversierung von Hyperkanten und erlaubt die die Betrachtung von allen durch die Hierarchie und Verteiltheit definierten Formen von Teilgraphen in gleicher Art und Weise. Die Möglichkeit zur automatischen Generierung einer schemaspezifischen Programmierschnittstelle aus grUML Schemata ermöglicht eine nahtlose Integration von DHHTGraphen als Datenstruktur in objektorientierte Anwendungen. Zum Zugriff auf die in DHHTGraphen hinterlegten Informationen sowie zur Formulierung komplexer Constraints in grUML Graphenschemata wurde die Graphanfragesprache GReQL um Sprachelemente zur Berücksichtigung der neu eingeführten Konzepte der Verteiltheit, der Hierarchie und der Hypergraphen erweitert. Als Grundlage dieser Erweiterung wurden über über den geplanten Projektumfang hinaus auch Algorithmen auf DHHTGraphen untersucht. Dabei wurde am Beispiel eines generischen Suchverfahrens gezeigt, wie sich Graphenalgorithmen an DHHTGraphen anpassen lassen und es wurde diskutiert, welche Einschränkungen insbesondere hinsichtlich der verteilten Anwendung von Graphenalgorithmen existieren.
Publications
-
On the relationships between Subsetting, Redefinition and Association Specialization. In Janis Barzdins and Marite Kirikova, editors, Proc. of the Ninth Int.Baltic Conf.on Databases and Information Systems, Riga, 7 2010. University of Latvia Press
Daniel Bildhauer
-
Associations as first-class elements. In Janis Barzdins and Marite Kirikova, editors, Databases and Information Systems VI: Selected Papers from 9th Int. Baltic Conf.on Databases and Information Systems, Frontiers in Artificial Intelligence and Applications, Amsterdam, 1 2011. IOS Press
Daniel Bildhauer
-
DHHTGraphs - Modeling Beyond Plain Graphs. In Serge Abiteboul, Klemens Böhm, Christoph Koch, and Kian-Lee Tan, editors, Workshops Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany, pages 100–105. IEEE, 2011
Daniel Bildhauer and Jürgen Ebert
-
Verteilte Hierarchische Hyper-TGraphen: Definition und Implementation eines ausdrucksstarken Graphenkonzepts. Logos Verlag, Berlin, 5 2012
Daniel Bildhauer
