Storing a Graph in a Database
Applications such as Leo and FreeMind manipulate graphs. For the purposes of collaborative shared storage, a database may be the best choice of persistent storage. This note describes database table layout to contain such graphs.
- Nodes consist of
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 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.
- A list element consists of
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 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 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
How Do You Store a Tree In A Database?
Aguri: Coolest Data Structure You've Never Heard Of