Storing a Graph in a Database

Motivation

Database Tables

• Nodes consist of
  • A unique identifier
  • Miscellaneous data associated with them (label, associated text, numbers, miscellaneous other singleton attributes), all of which are mutable.
  • An ordered, often empty, list of references to other nodes.
  The nodes are rows in a table. Each miscellaneous attribute is a column in the table. The list consists of a column containing foreign key to a table corresponding to the lists, and in the case of the empty list, may be NULL.
• A list element consists of
  • A unique ID
  • A reference to a node (a foreign key into the Node table)
  • A reference to the next element in the list (a "foreign" key into the lists table).
  A minimalist implementation puts a reference to the first element of the list into node. If the common use case is to access most siblings at once (e.g., representing the expansion of an outline node) then there may be justification for storing the list membership with the elements. In that case, there would be
  • a table consisting of unique identifiers for lists and a reference to the first element
  • the nodes would contain a reference not to the first element of the list but instead to a row in the the list table
  • each element of the list would contain an (indexed) foreign key referencing the table list

Other Ideas