Patent ID: 6633886
Filing Date: 2003-10-14
Classification: G06F,Y10S

Abstract:
A method for generating an acyclic directed graph structure, or acyclic diagraph, utilising a computer operated relational database, the 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, comprising:generating a node table structure indicating a relationship between each node in the acyclic diagraph and at least one node property; generating an edge table structure indicating a relationship between each directly coupled pair of nodes in the acyclic diagraph; and generating a path table structure indicating existence of a path between any two nodes in the acyclic diagraph, wherein: the node table structure includes 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; the edge table structure includes a record for each directly coupled pair of nodes, each edge table structure record including respective fields to identify each of the pair of nodes, the order of the fields in each edge table structure record indicating a direction of coupling of the nodes identified in the record; and the path table structure includes a record for each directly coupled pair of nodes and each indirectly coupled pair of nodes, each path table structure record including respective fields to identify each of the pair of nodes, and the order of the fields in each path table structure record indicating a direction of coupling of the nodes identified in the record, and wherein the method further includes 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 the existence of any other 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.