System and method for optimizing pattern query searches on a graph database

• US 9,292,570 B2
• Filed: 04/04/2013
• Issued: 03/22/2016
• Est. Priority Date: 11/19/2009
• Status: Active Grant

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Inventors: Sargeant, Daniel, Hollinger, Morgan
• Primary Examiner(s): Chau, Dung K
• Application Number:
  US13/856,960
• Publication Number:
  US 20130226893A1
• Time in Patent Office: 1,083 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

An embodiment of the system and method for optimizing pattern query searches on a graph database uses a pattern query optimizer to optimize execution of the search plan for any sequence of SQL expressions by separating or breaking a pattern query into multiple subpattern queries before converting the subpattern queries into SQL expressions. An embodiment of the pattern query optimizer algorithmically, without intervention by an analyst, decomposes any pattern query into a set of subpattern queries by first identifying branches and cycles within a pattern query and then decomposing each identified branch and cycle into equivalent straight line paths, i.e., straight line nodes joined by edges. Cardinality may be used to improve the performance of pattern searches.

Claims

1. A method for optimizing pattern query searches on a graph database, the method being implemented by a computer including at least one processor and comprising:

providing a pattern search engine operative to generate a search plan on the graph database from a first pattern query, the pattern search engine being executed by the processor;

identifying, by the at least one processor, in the first pattern query a first subpattern query and a second subpattern query that is structurally equivalent to the first subpattern query;

wherein the first subpattern query and the second subpattern query each comprise a single path;

wherein the structural equivalence meets criteria of;

the paths have a same number of nodes;

nodes in a same position on the paths are of a same type;

nodes in a same position on the paths have same qualifications;

only start and end nodes are shared;

none of non-shared nodes between the paths are exported;

any shared node is shared with both paths in a same position;

having one shared node between both paths; and

non-shared nodes in the paths are not used in pattern query language (PQL) value or constraint expressions; and

reducing the number of search expressions in the search plan based on the structural equivalence between the first subpattern query and the second subpattern query.

2. The method of claim 1, wherein the graph database is implemented in a relational database management system (RDBMS).

3. The method of claim 1, wherein the pattern query comprises one or more branches.

4. The method of claim 1, wherein the pattern query comprises one or more cycles.

5. The method of claim 1, wherein the pattern query comprises one or more branches and one or more cycles.

6. The method of claim 1, wherein the first subpattern query and the second subpattern query are each straight line nodes joined by edges.

7. The method of claim 1, wherein the reduction of the number of search expressions in the search plan is converted into a single search query language (SQL) expression.

8. The method of claim 1, wherein the first subpattern query and the second subpattern query each comprise a single path.

9. The method of claim 8, wherein the structural equivalence meets a criteria of the paths having a same number of nodes.

10. The method of claim 8, wherein the structural equivalence meets a criteria of nodes in a same position on the paths are of a same type.

11. The method of claim 8, wherein the structural equivalence meets a criteria of nodes in a same position on the paths have same qualifications.

12. The method of claim 8, wherein the structural equivalence meets a criteria of only start and end nodes are shared.

13. The method of claim 8, wherein the structural equivalence meets a criteria of none of non-shared nodes between the paths are exported.

14. The method of claim 8, wherein the structural equivalence meets a criteria of any shared node is shared with both paths in the same position.

15. The method of claim 8, wherein the structural equivalence meets a criteria of having one shared node between both paths.

16. The method of claim 8, wherein the structural equivalence meets a criteria of non-shared nodes in the paths are not used in pattern query language (PQL) value or constraint expressions.