GraphDB: Modeling and Querying 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 heterogeneous 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. 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.

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

Published: Proc. of the 20th Intl. Conf. on Very Large Databases, Santiago, 1994, 297-308.