# US 2012/0254254 A1 · Directed Graph Transitive Closure

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254254 A1
- Document ID: US20120254254A1
- Status: Published application
- Kind: A1
- Application number: 13/074,983
- Filed: 2011-03-29
- Published: 2012-10-04
- Earliest claimed: 2011-03-29
- Assignees: BMC Software, Inc.
- Inventors: Zack Milousheff
- Web page: https://patentgrep.com/patent/US20120254254A1

## CPC

- G06F 16/282: {Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Disclosed are methods and systems to provide for using database triggers to maintain a relational persistence of the transitive closure and path structure of an object hierarchy in the form of an object hierarchy bridge table. In one embodiment, database triggers fire when objects or relationships are added or deleted from the hierarchy. Based on the additions and deletions, a delta can be calculated and applied to an object hierarchy bridge table and the graph transitive closure and path structure can be dynamically built and maintained as corresponding changes to the graph occur. Later, more efficient access and retrieval of a graph transitive closure and path structure can be retrieved without necessarily having to perform recursion to calculate the graph transitive closure and path at request time.

## Claims

### Claim 1

A method of using one or more data tables to maintain an object transitive closure and path structure for a hierarchical relationship of objects, the method comprising:
receiving a change indication, the change indication identifying a change to a digraph model stored in a computer system, the digraph model representing a parent child relationship between a plurality of information technology (IT) components, the plurality of IT components comprising computing resources; and
initiating a procedural algorithm to apply a delta change to a stored representation of an object transitive closure and path structure of the digraph model, the delta change reflecting:
adding an IT component;
deleting an IT component;
adding the parent child relationship between two IT components; or
deleting the parent child relationship between two IT components.

### Claim 2 (depends on 1)

The method of claim 1, wherein the digraph model is stored in a database.

### Claim 3 (depends on 2)

The method of claim 2, wherein the procedural algorithm is initiated via a trigger function of the database.

### Claim 4 (depends on 3)

The method of claim 3, wherein the trigger function of the database is fired because of the change indication.

### Claim 5 (depends on 1)

The method of claim 1, wherein the parent child relationship reflects a dependency/impact relationship.

### Claim 6 (depends on 1)

The method of claim 1, wherein the plurality of IT components comprise physical and virtual IT components.

### Claim 7 (depends on 1)

The method of claim 1, wherein an initial digraph model stored in the computer system is empty and the change indication indicates a first node representing an IT component has been added to the digraph model.

### Claim 8 (depends on 1)

The method of claim 1, wherein the delta change is applied to tables comprising hierarchy bridge tables.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
recalculating the object transitive closure and path structure by only adding or deleting information to the stored representation of the object transitive closure and path structure for nodes directly adjacent to a modified node.

### Claim 10 (depends on 1)

The method of claim 1, wherein the change indication comprises an indication resulting from adding a node representing an IT component to the digraph model.

### Claim 11 (depends on 1)

The method of claim 1, wherein the change indication comprises an indication resulting from deleting a node representing an IT component to the digraph model.

### Claim 12 (depends on 10)

The method of claim 10, wherein the change indication comprises an indication resulting from adding a node between two already existing nodes.

### Claim 13 (depends on 11)

The method of claim 11, wherein the change indication comprises an indication resulting from deleting a node from between two already existing nodes.

### Claim 14 (depends on 1)

The method of claim 1, wherein the change indication comprises an indication resulting from adding a relationship between two nodes, each of the two nodes representing an IT component, in the digraph model.

### Claim 15

A method of using one or more data tables in a database to maintain an object transitive closure and path structure for a hierarchical relationship of objects, the method comprising:
receiving a change indication, the change indication indicating a change to a representation of a graph stored in a database on one or more computer systems, the graph representing a plurality of information technology (IT) components and relationships between at least a portion of the plurality of IT components; and
firing a trigger for a procedural algorithm to apply a delta change to one or more hierarchical bridge tables, the hierarchical bridge tables storing a representation of the graph's structure and representative of an object transitive closure and path structure for the representation of the graph.

### Claim 16 (depends on 15)

The method of claim 15, wherein the trigger is fired because of the change indication.

### Claim 17 (depends on 15)

The method of claim 15, wherein an initial representation of the graph stored in the database is empty and the change indication comprises an indication resulting from adding a first node, the first node representing an IT component.

### Claim 18 (depends on 15)

The method of claim 15, further comprising:
recalculating the object transitive closure and path structure by only adding or deleting information to the stored representation of the object transitive closure and the path structure for nodes directly adjacent to a modified node.

### Claim 19 (depends on 15)

The method of claim 15, wherein the change indication comprises an indication resulting from adding a node.

### Claim 20 (depends on 15)

The method of claim 15, wherein the change indication comprises an indication resulting from deleting a node.

### Claim 21 (depends on 15)

The method of claim 15, wherein the change indication comprises an indication resulting from adding a node between two nodes.

### Claim 22 (depends on 15)

The method of claim 15, wherein the change indication comprises an indication resulting from deleting a node from between two already existing nodes.

### Claim 23 (depends on 1)

A non-transitory computer readable medium comprising computer readable instructions stored thereon to cause a processing device to perform the method of claim 1.

### Claim 24 (depends on 15)

A non-transitory computer readable medium comprising computer readable instructions stored thereon to cause a processing device to perform the method of claim 15.

### Claim 25 (depends on 1)

A computer network comprising:
a plurality of processing units communicatively coupled to a computer network;
a first processing unit configured to perform at least a portion of the method of claim 1 wherein the entire method of claim 1 is performed collectively by the plurality of processing units.

### Claim 26 (depends on 15)

A computer network comprising:
a plurality of processing units communicatively coupled to a computer network;
a first processing unit configured to perform at least a portion of the method of claim 15 wherein the entire method of claim 15 is performed collectively by the plurality of processing units.

### Claim 27 (depends on 1)

A computer system comprising one or more programmable control devices communicatively coupled to each other and to a computer network, wherein the one or more programmable control devices are programmed to perform the method of claim 1.

### Claim 28 (depends on 15)

A computer system comprising one or more programmable control devices communicatively coupled to each other and to a computer network, wherein the one or more programmable control devices are programmed to perform the method of claim 15.
