Method of implementing an acyclic directed graph structure using a relational data-base

A method of maintaining a computer stored data structure in a relational database system for representing an acyclic diagraph comprising a plurality of nodes directionally coupled to one another so that each node has at least one child node in a forward coupling direction and/or at least one parent node in a reverse coupling direction, the data structure comprising:

• a node table structure storing a relationship between each node in the acyclic diagraph and at least one node property, the node table structure including a record for each node in the acyclic diagraph, each node table structure record including a node identification field and at least one node property field;
• an edge table structure storing a relationship between each pair of coupled parent and child nodes in the acyclic diagraph, the edge table structure including a record for each pair of parent and child coupled nodes, each edge table structure record including respective fields to identify the parent node and the child node;
• and
• a path table structure storing representation of a path between any two nodes in the acyclic diagraph, the path table structure including a record for each pair of parent and child coupled nodes and pair of ancestor and descendant coupled nodes wherein two nodes are coupled through an intermediate, each path table structure record including a respective fields to identify each of the pair of nodes,
• the method comprising:
• a node creation procedure for creating a new node in the acyclic diagraph by inserting a new record to the node table structure with a unique value in said node identification field;
• a node linking procedure for linking a child node to a parent node in the acyclic diagraph, comprising the steps of:
• inserting a new record in the edge table structure identifying the child node and the parent node and a coupling direction from the parent node to the child node;
• inserting a new record in the path table structure identifying the child node and the parent node and a coupling direction from the parent node to the child node;
• selecting from the path table structure each ancestor node coupled to the parent node and inserting a new record in the path table structure identifying the child node and each ancestor node and a coupling direction from the ancestor node to the child node;
• and
• selecting from the path table structure each descendant node to which the child node is coupled and inserting a new record in the path table structure identifying the child node and each descendant node and a coupling direction from the child node to the descendant node;
• a node unlinking procedure for unlinking a child node from a parent node in the acyclic diagraph, comprising the steps of:
• removing from the edge table structure the record identifying the child node and the parent node;
• removing from the path table structure each record identifying the child node;
• selecting and removing from the path table structure each record identifying an ancestor node of the parent node and a descendant node of the child node;
• and
• systematically reviewing the edge table structure beginning with records identifying an ancestor node of the parent node to determine any path from an ancestor node of the parent node to a descendant node of the child node, reviewing the path table structure to identify if any such path has already been identified by a path table structure record and inserting a new record into the path table structure identifying that path if none exists in the path table structure;
• and
• a remove node procedure for removing a node which has been unlinked from the acyclic diagraph, comprising removing from the node table structure the record identifying the unlinked node.

A method of maintaining a product and/or service classification system comprising a computer stored data structure in a relational database system for representing an acyclic diagraph comprising a plurality of nodes directionally coupled to one another so that each node has at least one child node in a forward coupling direction and/or at least one parent node in a reverse coupling direction, the data structure comprising:

• a node table structure storing a relationship between each node in the acyclic diagraph and at least one node property, the node table structure including a record for each node in the acyclic diagraph, each node table structure record including a node identification field and at least one node property field;
• an edge table structure storing a relationship between each pair of coupled parent and child nodes in the acyclic diagraph, the edge table structure including a record for each pair of parent and child coupled nodes, each edge table structure record including respective fields to identify the parent node and the child node;
• and
• a path table structure storing representation of a path between any two nodes in the acyclic diagraph, the path table structure including a record for each pair of parent and child coupled nodes and pair of ancestor and descendant coupled nodes wherein two nodes are coupled through an intermediate, each path table structure record including a respective fields to identify each of the pair of nodes,
• wherein the at least one node property in said node table structure represents a particular product or service associated with the corresponding node of the acyclic diagraph,
• the method comprising:
• a node creation procedure for creating a new node in the acyclic diagraph by inserting a new record to the node table structure with a unique value in said node identification field and a product or service identification in said node property field;
• a node linking procedure for linking a child node to a parent node in the acyclic diagraph, comprising the steps of:
• inserting a new record in the edge table structure identifying the child node and the parent node and a coupling direction from the parent node to the child node;
• inserting a new record in the path table structure identifying the child node and the parent node and a coupling direction from the parent node to the child node;
• selecting from the path table structure each ancestor node coupled to the parent node and inserting a new record in the path table structure identifying the child node and each ancestor node and a coupling direction from the ancestor node to the child node;
• and
• selecting from the path table structure each descendant node to which the child node is coupled and inserting a new record in the path table structure identifying the child node and each descendant node and a coupling direction from the child node to the descendant node;
• a node unlinking procedure for unlinking a child node from a parent node in the acyclic diagraph, comprising the steps of:
• removing from the edge table structure the record identifying the child node and the parent node;
• removing from the path table structure each record identifying the child node;
• selecting and removing from the path table structure each record identifying an ancestor node of the parent node and a descendant node of the child node;
• and
• systematically reviewing the edge table structure beginning with records identifying an ancestor node of the parent node to determine any path from an ancestor node of the parent node to a descendant node of the child node, reviewing the path table structure to identify if any such path has already been identified by a path table structure record and inserting a new record into the path table structure identifying that path is none exists in the path table structure;
• and
• a remove node procedure for removing a node which has been unlinked from the acyclic diagraph, comprising removing from the node table structure the record identifying the unlinked node.