GraphDB: A Data Model and Query Language for Graphs in Databases

Ralf Hartmut Güting

Praktische Informatik IV, FernUniversität Hagen, D-58084 Hagen, Germany

Abstract: We propose a data model and query language that integrates an explicit modeling and querying of graphs smoothly into a standard database environment. For standard applications, some key features of object-oriented modeling are offered such as object classes organized into a hierarchy, object identity, and attributes referencing objects. Querying can be done in a familiar style with a derive statement that can be used like a select ... from ... where. On the other hand, the model allows for an explicit representation of graphs by partitioning object classes into simple classes, link classes, and path classes whose objects can be viewed as nodes, edges, and explicitly stored paths of a graph (which is the whole database instance). For querying graphs, the derive statement has an extended meaning in that it allows one to refer to subgraphs of the database graph. A powerful rewrite operation is offered for the manipulation of hetereogeneous sequences of objects which often occur as a result of accessing the database graph. Additionally there are special graph operations like determining a shortest path or a subgraph and the model is extensible by such operations. It is possible to compute additions to the database graph as well as restrictions in a query.

Besides being attractive for standard applications, the model permits a natural representation and sophisticated querying of networks, in particular of spatially embedded networks like highways, public transport, etc. The GraphDB model is meant to be implemented; system architecture and a representation and query processing strategy are outlined in the paper.

Keywords: Graphs in databases, data model, query language, explicit paths, object-oriented modeling, relationships, sequence rewriting, system architecture, extensibility

This work was supported by the ESPRIT Basic Research Project 6881 AMUSING.

Published: FernUniversität Hagen, Informatik-Report 155, February 1994.