For acceleration of pathway selection, application, and ranking in a hybrid network

• US 10,089,410 B2
• Filed: 05/03/2010
• Issued: 10/02/2018
• Est. Priority Date: 04/02/2010
• Status: Active Grant

• Current Assignee: Objectivity, Inc.
• Original Assignee: Objectivity, Inc.
• Inventors: Guzenda, Leon
• Primary Examiner(s): McAdams, Robert B
• Application Number:
  US12/772,277
• Publication Number:
  US 20110246671A1
• Time in Patent Office: 3,074 Days
• Field of Search: 709240
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Methods, systems and computer-readable medium are provided for selecting and ordering pathways identified between two selected nodes of a hybrid network. Nodes within the network have named relationships that may have 1:1, 1:many, many:1 or many:many cardinality. An algorithm is applied to predetermine the optional search path for finding relationships between any two rows of any of one or more tables of one or more relational databases, including relationships defined between other tables. The schemas of one or more target relational databases, either derived or input, is converted into an object-oriented schema that explicitly defines relationships between columns in the tables of the relational database and represents the tables as object classes. The schemas are analyzed and optimal search paths are derived and stored for subsequent use. A query engine accesses the predefined search paths in order to execute queries.

Claims

1. In a computer that accesses a hybrid network representation, the hybrid network representation comprising a schema describing a plurality of nodes of differing node types, a method comprising:

a. Receiving a user selection of a first node of a first type and a second node of a second type;

b. Determining a plurality of possible pathways between the first node and the second node;

c. Ordering the plurality of possible pathways according to a link count of each pathway, wherein each link count is equal to a quantity of links observed between each node pathway pair of a comprising pathway; and

d. Further ordering the plurality of possible pathways by ranking pathways having a one-to-one link between two pathway nodes, whereby pathways having at least one one-to-one link are ordered for earlier examination than pathways having equal link counts and comprising one-to-one links.

2. The method of claim 1, wherein a human administrator modifies the ordering of the plurality of possible pathways.

3. The method of claim 1, further comprising ordering the plurality of possible pathways by ordering pathways having more than one one-to-one links between two pathway nodes of a comprising pathway, whereby pathways having more one-to-one link are ordered for earlier examination than pathways having equal link counts and fewer one-to-one links.

4. The method of claim 1, further comprising ordering the plurality of possible pathways by ordering pathways having a many-to-one link between pathway nodes, whereby pathways having at least one many-to-one link are ordered for earlier examination than pathways having equal link counts and no many-to-one links.

5. The method of claim 4, wherein a human administrator modifies the ordering of the plurality of possible pathways.

6. The method of claim 4, further comprising ordering the plurality of possible pathways by ordering pathways having more than one many-to-one links between pathway nodes, whereby pathways having more many-to-one links are ordered for earlier examination than pathways having equal link counts and fewer many-to-one links.

7. The method of claim 1, wherein the ordering of the plurality of possible pathways is stored for later access.

8. The method of claim 1, wherein the pathway ordering is modified at least partially on the basis of a cardinality of at least one node.

9. The method of claim 1, wherein the pathway ordering is modified at least partially on the basis of a cardinality of at least one link.

10. The method of claim 1, wherein the pathway ordering is modified at least partially on the basis of an assigned weight of a link type.

11. A method of directing a computer that accesses hybrid network representation, the hybrid network representation having a schema describing a plurality of node types and link types, the method comprising:

a. Receiving an identification from a user of a type of start node and a type of end node

b. Determining a plurality of pathways from each node of the start node type to each node of the end node type

c. Counting the links between nodes of each of the plurality of pathways;

d. Ordering the plurality of pathways in order of fewest links per pathway to most links per pathway; and

e. Ranking the ordered plurality of pathways on the basis of a cardinality of at least one node of at least one pathway.

12. The method of claim 11, further comprising examining a first pathway for instances of start nodes and end nodes that comprises information that satisfies a query, the first pathway selected from the group of pathways between matching node types having a fewest link count.

13. The method of claim 11, further comprising examining a plurality of pathways for start nodes and end nodes that comprise information that satisfies a query, wherein the plurality of paths examined in an order of pathways from a pathway having a fewest link count to pathways having a higher link count.

14. The method of claim 12, wherein the pathway ordering is modified by a human administrator.

15. The method of claim 12, further comprising ordering the plurality of pathways by ordering pathways having at least one one-to-one links between two pathway nodes of a comprising pathway, whereby pathways having at least one one-to-one link are ordered for earlier examination than pathways having equal link counts and fewer one-to-one links.

16. The method of claim 12, further comprising ordering the plurality of pathways by ordering pathways having at least one many-to-one links between pathway nodes, whereby pathways having more many-to-one links are ordered for earlier examination than pathways having equal link counts and no many-to-one links.

17. The method of claim 12, wherein the pathway ordering is modified at least partially on the basis of a cardinality of at least one node.

18. The method of claim 12, wherein the pathway ordering is modified at least partially on the basis of a cardinality of at least one link.

19. The method of claim 12, wherein the pathway ordering is modified at least partially by a weighted property of at least one link.

20. A tangible, non-transitory computer-readable media comprising machine-readable instructions that direct a computational system to execute the method comprising:

a. Generating an object-oriented schema from a hybrid network schema or a relational schema;

b. Analyzing the object-oriented schema to determine a plurality of search pathways that link rows in one table with rows in the same or another table of a same or two different relational database of the hybrid network;

c. Ranking each of the plurality of search pathways for expected computational efficiency, the ranking derived in consideration of a cardinality of at least an object representation of a row, wherein a pathway between a first source node and a first destination node exhibiting at least one link have a one-to-one cardinality is ranked for earlier instantiation than an alternate pathway having the first source node as a source node and the first destination node as a destination node and equal link count;

d. Informing a user of the ranking of the plurality of pathways;

e. Receiving a modification of the ranking of the plurality of pathways; and

f. Providing the search pathways in a user modified order to a query engine in accordance with the expected computational efficiency search ranking and the user ranking modification.