Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Representing Entity-Relationship Models using Adjacency Lists

IP.com Disclosure Number: IPCOM000111948D
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 82K

Publishing Venue

IBM

Related People

Potok, TE: AUTHOR

Abstract

This article describes a method for minimizing the storage requirements for Entity-Relationship (ER) models. By using graph theory adjacency lists, the storage needed for both ER model schema and instances is significantly reduced.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 60% of the total text.

Representing Entity-Relationship Models using Adjacency Lists

      This article describes a method for minimizing the storage
requirements for Entity-Relationship (ER) models.  By using graph
theory adjacency lists, the storage needed for both ER model schema
and instances is significantly reduced.

      A directed graph can be viewed as a modelling convention where
a finite set of vertices (nodes) are connected by a finite set of
edges (lines), very similar to the way ER models are represented.  A
very efficient way of storing directed graphs is with an adjacency
list.  In an adjacency list, all of the vertices are stored in an
array.  For each vertex, there is a linked list originating at the
array position of the vertex.  This list contains the connected
vertices (vertices related by an edge), as shown in Figs. 1 and 2.

      The invention is in two parts.  The first is to represent an ER
model as a directed graph.  The notations are very similar, and
directed graphs can easily be extended to support the characteristics
of different ER modelling schemes.  Basically, an entity is
represented by a vertex, and a relationship is represented by an
edge.  Entity attributes, relationship cardinalities, and
relationship attributes can be stored with the adjacency list
information, as shown in Fig. 4.  (To represent ER models, the formal
directed graph notation has to be extended to allow an edge
(relationship) to connect a vertex (entity) to itself.)  T...